[des00 25]

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

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

[Michael358 0]

11 hours ago, des00 said:

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

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

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

[des00 25]

1 hour ago, Michael358 said:

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

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

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

[Michael358 0]

4 hours ago, des00 said:

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

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

 

[des00 25]

12 hours ago, Michael358 said:

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

 

 

VLSI Architectures for Metric Normalization in the Viterbi Algorithm.pdf

[Michael358 0]

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. 

?

[des00 25]

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

[coding4dsp 0]

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

[des00 25]

28 minutes ago, coding4dsp said:

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

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

[coding4dsp 0]

13 минут назад, des00 сказал:

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

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

[des00 25]

17 minutes ago, coding4dsp said:

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

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

17 minutes ago, coding4dsp said:

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

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

[Michael358 0]

On 5/21/2019 at 4:41 AM, des00 said:

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

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

[des00 25]

57 minutes ago, Michael358 said:

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

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

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

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

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

 

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

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

[Michael358 0]

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

1 hour ago, des00 said:

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

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

 

1 hour ago, des00 said:

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

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

 

1 hour ago, des00 said:

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

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

Изменено 23 мая, 2019 пользователем Michael358

[des00 25]

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.