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

Если кодер инициализируется 0-ми на границах блоков и в конце каждого блока засовываются 0 (хвостовые биты), то начинать нужно в нулевом состоянии. (0-вая метрика = 0, остальные - наименьшее возможное значение). В конце блока трейсбек тоже надо из нулевого состояния начинать. Иначе в битах в начале и конце блока будет больше ошибок, чем в тех, которые в середине.

Если поток данных непрерывный (кодер не переинициализируется), то начинать надо с одинакового значения всех метрик (обычно это минимальное возможное значение). В конце блока трейсбек начинать из состояния с максимальной метрикой. Между блоками метрики при таком раскладе сбрасывать не нужно - нормализовать разве что.

Сообщение отредактировал andyp - Dec 26 2013, 16:24

Спасибо Вам большое. Да, поток непрерывный.

А почему из состояния с максимальной метрикой? Мы же на всех этапах декодирования, наоборот, максимальные метрики отбрасываем и сохраняем только пути с минимальными.

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

+1. Так и думал, что тут неоднозначность будет, да поздно было - уже запостил...

Если метрика корреляционная - то максимум, если расстояние Хамминга - то минимум (ну по месту подрихтовать надо).

Сообщение отредактировал andyp - Dec 26 2013, 18:17

Спасибо. Про корреляционную метрику и не подумал... Ясно.

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

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

На каждом шаге декодирования для каждого пути вам нужно будет сделать 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

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

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

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

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

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

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

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

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

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

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

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

Вы наверняка понимаете, что на каждое изменение SNR пересчитывать квантователь LLR очень накладно, поэтому можно разбить весь диапазон возможных SNR на поддиапазоны и подготовить квантователь для каждого из поддиапазонов. Это довольно прямолинейное решение, которое для каналов с АБГШ более-менее согласуется с теорией.

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

1. Сделать неравномерное квантование на входе декодера. простейший случай: логарифмический или комбинированный (log+lin) компрессор. придется посмотреть, как ухудшилась корректирующая способность

2. сделать ару на входе декодера. не мгновенно же у вас меняется отношение сигнал-шум.

3. Квантовать толко область "слабых" сигналов. Выше - ограничивать. Тогда если у вас отношение сигнал-шум низкое, выход коррелятора не слишком достоверный, то декодер работает во всей красе почти всегда с "мягкими" символами. Если отношение сигнал-шум высокое, выход коррелятора достоверный, то проигрыш за счет перехода к жесткому декодированию будет незаметен. Квантователь и порог в этой схеме в теории будет зависеть от отношения сигнал-шум, но вы сумеете выбрать компромиссный вариант на все случаи жизни.

Все эти методы запросто дадут вам 4 и тем более 8 бит для LLR, что согласуется с 16 бит путевой метрики. Но есть и решение "в лоб": не усложнять себе жизнь и оставить на путевые метрики 32 бита.

Угу, думал про поддиапазоны SNR, но решил не заморачиваться с этим. Потом после варианта "в лоб" пришла мысль про АРУ. В принципе реализовать программно его не сложно. Благодарен вам за столько предложенных вариантов. Буду пробовать.