Декодер Витерби, Программная реализация на C под ARM Опции

[Grizzzly]

Необходимо реализовать декодер Витерби на C под ARM 7, код (133, 171), скорость 200 бит/с. Однако вопросы, скорее, теоретические.
Собираюсь копить в буфере несколько сотен символов, затем их декодировать, потом переходить к следующей порции. При переходе к новому блоку нужно сохранять предыдущее состояние декодера и метрики ребер или же начинать всё с нуля?
Во всех книгах и статьях декодирование начинается из нулевого состояния. Обязательно ли нужна начальная синхронизация декодера или можно обойтись без неё, сразу начав декодирование?

[Grizzzly]

Реализовал вариант с traceback'ом, всё работает. Теперь задача стоит в уменьшении объема требуемой памяти. Хочу использовать другую модификацию алгоритма (с обметом путей через регистры), тогда можно будет обойтись без большого буфера и декодировать непрерывно по биту. Возник вопрос: если ли у кого-нибудь опыт по сравнению алгоритмов с traceback и с register exchange (реализация на микропроцессоре или DSP)? Какой алгоритм эффективнее с точки зрения быстродействия?

[Fat Robot]

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

На каждом шаге декодирования для каждого пути вам нужно будет сделать ACS и после поместить результат (метрику пути и обновленную историю пути) в другой массив. Одновременно с этим обновлять максимально правдоподобную путевую метрику и индекс массива, ей соответствующий.

В конце выбрать историю пути по получившемуся индексу и оттуда с нужной глубины взять информационный бит.

Очень быстро.

Что касается объема памяти:

Для указанного кода при 4-х битовых входных (реберных) метриках будет достаточно 11 бит для путевых метрик (при любой схеме нормализации). При 5 входных битах достаточно 12 бит для путевых метрик и т.д. Буду считать, что с разрядностью ваших входных метрик вы уложитесь в 16 бит для путевых.

Если при кодировании не используется выкалывание, то длина памяти путей должна быть > 5*7 т.е. > 35. Если используется, то память путей глубже. Буду считать, что не используется.

Итого для программной реализации схемы с обменом вам нужно

uint64_t path_history[2][64];
uint16_t path_metric[2][64];

Вы можете оценить, как ухудшится корректирующая способность декодера (зависимость Pош на выходе декодера от входного SNR) если укоротить память путей до 32. Если для вас это приемлемо (думаю, что да), то ресурсы будут такими:

uint32_t path_history[2][64];
uint16_t path_metric[2][64];

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

Подробнее:
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0

[Grizzzly]

Спасибо большое за столь исчерпывающий ответ. Я как раз по книге Морелоса-Сарагосы и реализовывал, скачав пример с его сайта (http://the-art-of-ecc.com/5_Convolutional/index.html). Лишнее убрал, что-то оптимизировал. Про прочтении книги меня смутила фраза про слишком большие затраты на чтение и запись путей, что существенно уменьшает быстродействие. Видимо, это относится к реализации на ПЛИС.
Я использовал для хранения путей двумерные массивы размером 64*5 типа CHAR. В 5 байт запаковывал 40 бит, что чуть больше рекомендуемой длины. Примимаемые сигналы - спутниковые навигационные, поэтому может быть достаточно низкое отношение C/Ш. Из-за этого не взял 32 бита. В общем в понедельник в MATLAB промоделирую такую ситуацию, возможно, что не сильно снизится помехоустойчивость. 64 бита брать не хотелось опять из-за всё той же экономии памяти. В системе несколько десятков структур декодеров.
С нормализацией надо будет аккуратно разобраться. Дело в том, что на вход декодера поступают 16-битные значения. Это из-за того, что такая разрядность приходит из коррелятора. Были попытки перейти на 8-битное или 4-битное представление данных, путем усечения младших разрядов. Не вышло. С/Ш сигнала может быть в очень широком диапазоне, поэтому нужно постоянно его измерять, чтобы понять, на сколько бит можно произвести усечение.

[Fat Robot]

Ваши затраты памяти я оставлю без комментариев, если позволите.

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

[Grizzzly]

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

Про то, что достаточно всего трех бит, при которых будет проигрыш всего 0.2 дБ по сравнению с неквантованными данными? Это знаю. Приведу две ситуации. В первой сигнал занимает все 16 разрядов, во второй только 7. В этих ситуациях нужно >> на разное число бит. Поэтому нужно постоянно знать энергетику. Коррелятор аппаратной, он всегда выдает данные в 16-битном представлении, тут уже ничего не изменить.

А что с памятью не так? Вы имеете ввиду, что выигрыш от 40 бит по сравнению с 60 будет совсем незначительный?

[Fat Robot]

Про память: я не пытался понять ваших выкладок.

Про "выигрыш от 40 бит по сравнению с 60": вы не должны его заметить, если у вас нет выкалывания.

По поводу сдвигов "на разное число бит": Разбирайтесь, что такое LLR. Морелос - отправная точка.

Про то, что достаточно всего трех бит, при которых будет проигрыш всего 0.2 дБ по сравнению с неквантованными данными? Это знаю. Приведу две ситуации. В первой сигнал занимает все 16 разрядов, во второй только 7. В этих ситуациях нужно >> на разное число бит. Поэтому нужно постоянно знать энергетику. Коррелятор аппаратной, он всегда выдает данные в 16-битном представлении, тут уже ничего не изменить.

А что с памятью не так? Вы имеете ввиду, что выигрыш от 40 бит по сравнению с 60 будет совсем незначительный?

[Grizzzly]

По поводу сдвигов "на разное число бит": Разбирайтесь, что такое LLR. Морелос - отправная точка.

Спасибо. Буду разбираться.

Прочитал. Может, я как-то некорректно выразился. Из коррелятора на декодер приходят 16-битные знаковые символы (short).
Ситуация №1 (слабый сигнал): 0x005B (фактически занято 7 разрядов, положительное число).
Ситуация №2 (сильный сигнал): 0xFF3A (заняты все разряды, отрицательное число).
Я хочу преобразовать для декодирования их к 3-битному представлению. В первом случае я могу сдвинуть вправо на 4 разряда. Во втором случае при сдвиге на 4 разряда и применении маски 0x3 я получу разряды из середины числа вместо старших, к тому же потеряю знак. То есть нельзя заранее знать, какое нужно сделать усечение. Я это имел ввиду.