Jump to content

    

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

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

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

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