Jump to content

    

Декодер Витерби

Вот же известная всем, кто разбирался с витерби, картинка.

500px-Viterbi_Decoding.svg.png

пути сливаются, остается минимальная разница, хотя, судя вашим предположениям, метрики должны судорожно расти

Share this post


Link to post
Share on other sites
11 hours ago, des00 said:

Вы руками решётку распишите на длину кодового ограничения.

Спасибо. С этим разобрался.

Скажите, а в чём выгода нормализации метрик по модулю? Разве вычитание не быстрее?

Share this post


Link to post
Share on other sites
1 hour ago, Michael358 said:

Скажите, а в чём выгода нормализации метрик по модулю? Разве вычитание не быстрее?

Не просто вычитание, а поиск минимального и вычитание. которое, как я понимаю, вы делаете для простоты на каждом шаге. Сколько нужно будет сравнений, для поиска минимума на решетке 7/9?

В модульной арифметике, нормализации, как таковой, нет, там не нужно искать минимум и вычитать его. Там немного изменяется логика принятия решений. На плис это проще и быстрее, на процах надо смотреть, но, по логике здравого смысла, должно быть быстрее)

Share this post


Link to post
Share on other sites
4 hours ago, des00 said:

Там немного изменяется логика принятия решений

А можете разъяснить, как именно? Или что почитать по этому поводу? Я начал читать про модульную арифметику. Но как её применить к метрикам - не соображу. Пишут, что надо брать метрики по модулю = 2 * максимальную разность метрик. Но что это даёт - не пойму.

 

Share this post


Link to post
Share on other sites
12 hours ago, Michael358 said:

А можете разъяснить, как именно? Или что почитать по этому поводу? Я начал читать про модульную арифметику. Но как её применить к метрикам - не соображу. Пишут, что надо брать метрики по модулю = 2 * максимальную разность метрик. Но что это даёт - не пойму.

 

 

VLSI Architectures for Metric Normalization in the Viterbi Algorithm.pdf

Share this post


Link to post
Share on other sites
On 5/18/2019 at 9:01 AM, des00 said:

VLSI Architectures for Metric Normalization in the Viterbi Algorithm.pdf

Спасибо.

Правильно я понимаю, что:

для кодера 1/2 (5,7) С=4.  

Метрика_i = (Метрика_пути + Метрика_ребра + С/2) (mod 4) - С/2;

Если (Метрика_1 - Метрика_2) >= 0, то Метрика_состояния = Метрика_1; иначе Метрика_состояния = Метрика_2. 

?

Share this post


Link to post
Share on other sites

Извините, но я ничего не понял)) графически смысл в том что все метрики бегут по кругу и принимать решение, нужно с учетом заворота метрик. Математка тут нужна с ограничением разрядности (модульная), хоть числа и знаковые. Когда делал, брал ручку, тетрадь и проверял численные примеры.  Рисунок и примеры в таблице есть.

Share this post


Link to post
Share on other sites

С модульной нормализацией есть нюанс. Когда все метрики уже нормализованы и нужно найти состояние решетки с наилучшей метрикой, то может оказаться так, что нормализованные метрики расположены на границах переходов разрядной сетки от + к - (в квадрантах 2 и 3). Нужно это учитывать. Если все это и так знают, то хорошо. Я же с этим чуток повозился. Пришлось делать приведение всех метрик к одному квадранту перед определением состояния с наилучшей метрикой. 

Share this post


Link to post
Share on other sites
28 minutes ago, coding4dsp said:

С модульной нормализацией есть нюанс. Когда все метрики уже нормализованы и нужно найти состояние решетки с наилучшей метрикой, то может оказаться так, что нормализованные метрики расположены на границах переходов разрядной сетки от + к - (в квадрантах 2 и 3). Нужно это учитывать. Если все это и так знают, то хорошо. Я же с этим чуток повозился. Пришлось делать приведение всех метрик к одному квадранту перед определением состояния с наилучшей метрикой. 

как раз поэтому, в статье, классическое больше меньше, заменятся другой логикой принятия решений Figure 5. VLSI architecture for Modulo Normalized ACS

Share this post


Link to post
Share on other sites
13 минут назад, des00 сказал:

как раз поэтому, в статье, классическое больше меньше, заменятся другой логикой принятия решений Figure 5. VLSI architecture for Modulo Normalized ACS

На Figure 5 представлен алгоритм нормализации двух метрик, когда мы находимся в одном состоянии. Когда мы прошли все состояния, нужно выбрать одно из максимальных. Ну да, по всем состояниям тоже можно пройтись этой модульной логикой. Вы это имели в виду? Я сейчас понял, что я написал про нюанс в реализации в турбо-декодере, где нормализованные по модулю альфа и бетта суммируются с гаммой. Там мне пришлось сделать "вторичную" нормализацию к единому квадранту, потому что финальные LLR у меня без нормализации...

Share this post


Link to post
Share on other sites
17 minutes ago, coding4dsp said:

На Figure 5 представлен алгоритм нормализации двух метрик, когда мы находимся в одном состоянии. Когда мы прошли все состояния, нужно выбрать одно из максимальных. Ну да, по всем состояниям тоже можно пройтись этой модульной логикой. Вы это имели в виду?

именно так. это изменение в логике должно быть везде.

17 minutes ago, coding4dsp said:

 Я сейчас понял, что я написал про нюанс в реализации в турбо-декодере, где нормализованные по модулю альфа и бетта суммируются с гаммой. Там мне пришлось сделать "вторичную" нормализацию к единому квадранту, потому что финальные LLR у меня без нормализации...

Вот в MAP алгоритме, там да, метрика состояния автоматом, а вот вклад метрики в итог, требует доп логики обработки старших бит состояний.

Share this post


Link to post
Share on other sites
On 5/21/2019 at 4:41 AM, des00 said:

Когда делал, брал ручку, тетрадь и проверял численные примеры.

Что я делаю неправильно? (Это первый вариант с вычитанием)

IMG_20190523_134913.jpg

Share this post


Link to post
Share on other sites
57 minutes ago, Michael358 said:

Что я делаю неправильно? (Это первый вариант с вычитанием)

1. Не учли что витерби на жестких решениях не максимизирует метрику, а минимизирует (т.е. его решения инверсные)

2. Неправильно трактовали Figure 5 из статьи. 

3. Совсем не понял, откуда у вас взялась метрика -3, на жестких решениях, метрики которых, всегда положительны.

Должно быть, как то так.

 

ЗЫ. Ну и считать вам проще по модулю 2^N. в завимости от размера слова вашего ПК/М/ПЛИС.

Для решетки на рисунке (судя по всему это 1/2 CL=3) и жесткого решения, минимальная(она же реальная) разрядность метрики перехода - 2 бита, минимальная состояния - 5 бит (удвоеная метрика + 2 бита на кодирование квадрантов круга). 8ми бит для жестких решений, вам хватит за глаза)

IMG_20190523_184656.jpg

Share this post


Link to post
Share on other sites

Спасибо. Мне уже стыдно, что никак не могу понять процесс. :dash2: Но, если позволите, продолжу расспросы.

1 hour ago, des00 said:

1. Не учли что витерби на жестких решениях не максимизирует метрику, а минимизирует (т.е. его решения инверсные)

Я вроде так и вибирал меньшую... Т.е. вычитаем М1-М2 и смотрим бит знака результата . Единица - верхний переход, ноль - нижний. Правильно?

 

1 hour ago, des00 said:

Должно быть, как то так.

Когда надо считать по модулю? Я думал - складываем первую метрику с метрикой перехода и нормализуем результат по модулю, потом также со второй метрикой, а потом вычитаем нормализованные метрики и смотрим бит знака результата.

 

1 hour ago, des00 said:

минимальная состояния - 5 бит (удвоеная метрика + 2 бита на кодирование квадрантов круга)

Я, наверное, не понимаю, как работает сама модульная арифметика... 5 бит - это диапазон от 0 до 31... метрики будут бегать в этом диапазоне по кругу... дальше не понимаю, как их сравнивать при переполнениии одной из метрик...

Edited by Michael358

Share this post


Link to post
Share on other sites
20 hours ago, Michael358 said:

Я вроде так и вибирал меньшую... Т.е. вычитаем М1-М2 и смотрим бит знака результата . Единица - верхний переход, ноль - нижний. Правильно?

давайте по рисунку. правило для жесткого решения, если m1-m2 < 0 то метрика состояния m1 , если m1-m2 >= 0, то метрика состояния m2.  Но, вычитание - знаковое, с учетом используемой разрядной сетки (Это важно !!!)

20 hours ago, Michael358 said:

Когда надо считать по модулю? Я думал - складываем первую метрику с метрикой перехода и нормализуем результат по модулю, потом также со второй метрикой, а потом вычитаем нормализованные метрики и смотрим бит знака результата.

Я, наверное, не понимаю, как работает сама модульная арифметика... 5 бит - это диапазон от 0 до 31... метрики будут бегать в этом диапазоне по кругу... дальше не понимаю, как их сравнивать при переполнениии одной из метрик...

Модульная арифметика - это арифметика с ограниченной разрядностью. Простой числовой пример. В обычной арифметике 127+2 = 129. В арифметике по модулю 128, 127 +2 = 1 (129 % 128). Как видно, это арифметика чисел с разрядностью 7 бит. 

Рассмотрим пример для процессоров. положим слово 8 бит. Обычная арифметика 250 + 16 = 266, модульная 250 + 16 = 10 (266 % 256). 

Числа будут бегать по замкнутому кругу и никогда не переполнятся. Т.е. никаких специальных операций,  при сложении, с метриками делать не надо. Совсем. Просто складывайте, по всем правилам знаковой/беззнаковой арифмтетики, смотря какое решение используется. Но, надо считать их в типах, с ограниченной разрядностью, без учета битов переноса: на плис - нужная, на 8 ми битном МК - 8мибитная, на 32 бита проце - 32-х битная и т.д. 

Сравнивать числа, тем самым знаковым вычитанием с учетом разрядной сетки. Что это дает, это дает не кольцо 0...31, а кольцо 0..+15 -16....-1. (т.е. двоичное представление числа не изменяется, изменяется только его трактование в классической арифметике). 

Например, положим 5 ти битную арифметику. Круг 0...31(который, как мы помним 0..+15 -16....-1). Положим, что в конце решетки у нас числа 30, 2, 3,  31 (числа взяты от балды). В классической арифметике наименьшая метрика будет 2, в арифметике по модулю 5, будет 30. Покажем что это так. 

При знаковом вычитании, в модульной арифметике числа будут трактоваться как -2, 2, 3, -1. Распишем дерево решений

1 слой дерева

-2 - 2 = -4 < 0, выбираем метрику -2(30).

3 - (-1) = 4 >= 0, выбираем метрику -1 (31)

2 второй слой дерева  

-2 -(-1) = -1 < 0, выбираем метрику -2 (30). 

ЧТД, хотя изначально, было похоже на бред ;) 

Т.е. тут все работает на математике в ограниченной разрядной сетке, представлению чисел в дополнительном коде и добавленного запаса битов на кодирование квадранта круга (2 бита сверху). 

UPD. Вот еще интересный пример, чтобы расставить все точки над Ё

рассмотрим пару чисел 15 и 16. В дополнительном коде, 5 ти битной арифметрики это числа 15 и -16 соответственно.

15 -(-16) = 31 == -1 < 0, выбираем метрику 15

-16 -15 = -31 ...а вот это уже 6 ти битное число, в битовой нотации это 10_0001, но нас итересует не знак переноса, а знаковый бит 5 ти битного результата. 5 ти битный результат будет 0_0001 или 1 >= 0, выбираем метрику 15.

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this