Jump to content

    
Sign in to follow this  
Michael358

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

Recommended Posts

Спасибо большое. Практически всё понял, кроме следующих моментов:

15 hours ago, des00 said:

Просто складывайте, по всем правилам знаковой/беззнаковой арифмтетики, смотря какое решение используется.

Беззнаковая - для жёсткого решения, знаковая - для мягкого?

 

15 hours ago, des00 said:

Но, надо считать их в типах, с ограниченной разрядностью, без учета битов переноса: на плис - нужная, на 8 ми битном МК - 8мибитная, на 32 бита проце - 32-х битная и т.д. 

На 32-х битном проце можно ведь взять 8-битный тип? Не обязательно использовать 32 бита?

 

15 hours ago, des00 said:

и добавленного запаса битов на кодирование квадранта круга (2 бита сверху). 

Про квадранты не понял... как и для чего эти два бита используются?

Share this post


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

Беззнаковая - для жёсткого решения, знаковая - для мягкого?

Именно так, все зависит от метрики входного символа: если она всегда положительна, то и отрицательным числам, взяться не откуда. Если может быть отрицательная (LLR например), тогда состояния могут быть с минусом. Но, в целом, разница не принципиальна.

 

29 minutes ago, Michael358 said:

 

На 32-х битном проце можно ведь взять 8-битный тип? Не обязательно использовать 32 бита?

Зависит от производительности. Не силен в процессорах и не знаю как, на 32-х битной платформе, реализуются вычисления с 8ми битными переменными. Если на лету, то ок, в противном случае, там будут использоваться маска слова 0x0000_00FF. А это, дополнительная операция.

29 minutes ago, Michael358 said:

 

Про квадранты не понял... как и для чего эти два бита используются?

просто учитывается в разрядности метрики состояний.

IMG_20190524_162638.jpg

Share this post


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

просто учитывается в разрядности метрики состояний.

Т.е. это для графического представления?

И разве числа бегут не против часовой стрелки? Или это не имеет значения?

IMG_20190524_142202.thumb.jpg.5d22c53e6a79c9830071e3dbbe948aad.jpg

 

UPD:

а... 2 бита - это модуль = 2 * разрядность_метрик ?

Edited by Michael358

Share this post


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

Т.е. это для графического представления?

нет, это запас разрядности на корректные вычисления, ну или эффективная разрядность.

53 minutes ago, Michael358 said:

И разве числа бегут не против часовой стрелки? Или это не имеет значения?

это без разницы, кому как удобно) мне удобно так)

53 minutes ago, Michael358 said:

а... 2 бита - это модуль = 2 * разрядность_метрик ?

эмм, не совсем понял) 2*разрядность метрики - по сути это эффективная разрядность на сложение, что бы переполнение не возникало сразу, а 2 бита на квадратны, что бы был полный круг. отвлекитесь и рассмотрите на свежую голову, тогда у вас все уложиться в голове)

Share this post


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

это эффективная разрядность на сложение, что бы переполнение не возникало сразу, а 2 бита на квадратны, что бы был полный круг

Ну вот для своего декодера (1/2, К=3): разница метрик путей не превышает 3, и если взять на метрики только 4 бита, то сразу переполнения не происходит, и метрики бегают по кругу, и знаковое вычитание считается (проверил несолько значений...)

 

1 hour ago, des00 said:

отвлекитесь

видимо, надо... только из головы не идёт этот декодер

Share this post


Link to post
Share on other sites
On 5/24/2019 at 8:52 PM, Michael358 said:

Ну вот для своего декодера (1/2, К=3): разница метрик путей не превышает 3, и если взять на метрики только 4 бита, то сразу переполнения не происходит, и метрики бегают по кругу, и знаковое вычитание считается (проверил несолько значений...)

Вполне возможно что двойная метрика это моя эмпирическая привычка перестраховываться и 4-х битов хватит) хорошо что все заработало.

ЗЫ. Для вашей работы, еще интересно сравнить производительность вашего первого варианта, с определением минимума и нормировкой вычитанием и вариант с модульной арифметикой. Можно  любых попугаях: тактах/времени исполнения, битрейте. Заодно и узнаете стоила ли овчинка выделки)

Share this post


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

интересно сравнить производительность вашего первого варианта

На МК 1901ВЦ1Т при тактовой 80 МГц декодирование одной пары бит:

- с поиском минимума = 9 микросекунд;

- с модульной нормализацией = 7 мкс.

Share this post


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

На МК 1901ВЦ1Т при тактовой 80 МГц декодирование одной пары бит:

 - с поиском минимума = 9 микросекунд;

- с модульной нормализацией = 7 мкс. 

2/9 ~= 22% улучшение) 7мкс, 565 тактов, незнаю архитектуры этого чипа, но ради интереса, я бы попробовал вариант с оптимальной, для 1901ВЦ1Т разрядностью. Думаю часть уходит на операции по двочиному модулю (хотя это и простой AND в  случае 2^N). Судя по гуглу, это будет 16 бит для дсп ядра и 32 для риск. Там просто, на каждое состояние сложить две метрики, вычесть, по знаку выбрать) и так для каждого. думаю можно выжать что-то еще)

Share this post


Link to post
Share on other sites
On 5/27/2019 at 6:37 PM, des00 said:

это будет 16 бит для дсп ядра и 32 для риск

Делал на риск-ядре. Изменение разрядности особого прироста не дает. В дсп-ядре есть устройство сравнения, выбора и хранения. Если руки дойдут - попробую.

 

Я вот ещё не понимаю по алгоритму. У меня метод registers exchange: в каждой итерации для каждого состояния из двух путей выбрал выживший, переписал его в выходной регистр, на следующем шаге сделал его входным и т.д. 

Метод trackback: для каждого состояния выбрали выживший путь, в регистр состояния записали номер состояния, из которого пришел выживший путь; достигнув нужной глубины, выбираем путь с лучшей метрикой, по запомненным переходам, следуя из конца в начало, восстанавливаем исходную последовательность.

 

В литературе пишут, что trackback требует в два раза меньше памяти для путей, но в разы медленнее.

 

Но, если входные данные идут непрерывным потоком: для кодера 1/2 (5,7) длина кодового ограничения К=3, пути сливаются на глубине примерно 5*К. Для метода registers exchange мне нужно для каждого пути 2 регистра (входной и выходной) размером 5*К. В каждой итерации в младшем разряде запоминаю декодированный бит, из старшего разряда выдаю результат декодирования. Т.к. на глубине 5*К все пути сливаются, то можно не искать из всех путей меньшую метрику, а всегда выдавать старший разряд первого пути. Итого для 4-х путей нужно 5*К*2*4= 120 бит.

 

С trackback-ом:  если в канале будут ошибки, то при выборе из четырех путей меньшего может быть несколько путей с одинаковой метрикой, которые до глубины 5*К не слились. Можно выбрать неправильно. Значит, надо уйти на глубину 2*(5*К)=10*К , запустить trackback, а результат выдать с 10*К по 5*К, где пути слились. Тут опять же получается, что можно не искать минимальный... Тогда для памяти путей нужно столько же бит, сколько при register exchange. 10*К*4=120 бит.

В чём я ошибаюсь?
Edited by Michael358

Share this post


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

Делал на риск-ядре. Изменение разрядности особого прироста не дает. В дсп-ядре есть устройство сравнения, выбора и хранения. Если руки дойдут - попробую.

Странно, но наверное так и есть. я плисовод, мне сложно адекватно оценивать производействие процессоров в том или ином алгоритме. 

3 hours ago, Michael358 said:

Я вот ещё не понимаю по алгоритму.

В чём я ошибаюсь?

Сам метод register exchange я не реализовывал, тем более програмно. Когда изучал витерби, посмотрел модель в матлабе, лежит тут \toolbox\hdlcoder\hdlcoderdemos\hdlcoderviterbi.mdl. Увидел что сохраняются решения и выбранное состояние, по сути считается вперед комбинационно. Да, это можно конвейризировать, но тогда, нужно пробрасывать индексы состояний по всей линейке. Это ресурс. Но зато никаких обратных пробегов, LIFO и т.д..

В traceback сохраняется только вектор решений, в соответствии с индексами состояний. Затем, когда получено значение, делается обратный пробег, на котором определяется значение выходного бита. И действительно, памяти, для путей нужно меньше. Но нужно LIFO для восстановления порядка следования бит.

А вот с определением индекса состояния, с которого нужно начинать обратный пробег, возможны варианты:

1. Размер блока кодирования меньше L - выбора нет, считаем решетку, ищем минимальный, декодируем. Символы хвоста защищены намного слабее чем символы головы. Но, ИМХО, для таких блоков применение витерби сомнительно, лучше MAP. а еще лучше короткий сверточный турбокод.

2. Размер блока кодирования меньше 2*L, все тоже самое, только первые L символов защищены лучше чем вторые L.

3. Размер блока кодирования больше 2*L. Нарезаем блок на перекрывающиеся подблоки по 2*L. В каждом подблоке первые L символов 99.9% будут в слитом пути, и для определения этого пути, можно сделать обратный пробег из любого состояния, на момент 2*L. Т.е. берем блок 2*L, берем любое состояние, запускаем обратный пробег, ищем состояние в момент L и с него декодируем. Так будет до тех пор, пока не доберемся до последнего блока 2*L, его декодируем как 2.

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

ЗЫ. Да, вам не показалось, при traceback блоки пробегаются по 2 раза. Поэтому была придумана техника pre-traceback. Что бы убрать один пробег и сразу знать состояние с которого надо декодировать данные.

Т.е. классический traceback конвейер выглядит так :

вперед 2*L -> назад L -> назад L(решения) -> LIFO L -> вперед L -> назад L -> назад L (решения)  -> LIFO L и .т.д.

с pre-traceback выглядит так:

вперед 2*L -> назад L(решения) -> LIFO L -> вперед L -> назад L (решения)  -> LIFO L и .т.д.

быстрее, но на плис это выливается в ресурс, а в проце - вычислительная мощность)

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this