Подскажите, пожалуйста, ссылку на С-реализацию.

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

Жесткое декодирование. На сколько я разобрался, Golay (12,6,6) / (11,б,5) троичные, я хотел их использовать для tri-state сигнала. Может, есть более кошерные подходы?

А зачем, что может быть проще табличного метода?

Я думал об этом, но для Ternary Golay потребуется 3^12 * sizeof(short), что немало. Без синдромов не обойтись. Описание есть, например:
https://www.math.lsu.edu/~verrill/teaching/...oding/golay.pdf
но не хотелось самому корячиться, думал найти готовую реализацию.

Или Вы другое имели в виду под табличным методом? Задача, собственно, следующая: имеется tri-state последовательность, хочется релизовать оптимальный FEC.
Возможно, лучше приспособить что-то из софт-декодеров? Перфоманс важен, но не критичен.

Табличный - это тот же синдромный, для данного кода таблица синдромов будет содержать 3^(12-6) = 729 векторов ошибок, по-моему, немного. насчет оптимальности применения Голея к Вашей задаче мне трудно что-то сказать, не имея никаких данных. софтовая реализация даст дополнительный ЭВК, какой трудно сказать, в среднем где-то 2 дБ, будет зависеть от алгоритма и соответствующих потерь реализации. Чейз (метод 2) дает неплохой прирост помехоустойчивости, практически минимум ошибки для кодового слова, при относительно малой сложности реализации.

Для того чтобы fec был оптимальным необходимо знать требования к нему. Код голея, несмотря на совершенность, может оказаться не лучшим вариантом. Может вам вполне подойдет троичный ldpc из мягких.

Могу быть не прав, но у меня получается 2^2*nchoosek(12,2) + 2*12 = 288 исправляемых паттернов ошибок. nchoosek - биномиальный коэффициент C из 12.

Считал так:
Максимум исправляем 2 ошибки. Возможно С из 12 по 2 положений ошибочных символов в кодовом слове. Ошибка в символе может иметь 2 значения, символов 2. Аналогично для 1 ошибки

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

PS Интернет говорит, что код Golay(11,6,5) - циклический, соответственно (12,6,6) - тоже циклический. Можно в 12 раз уменьшить таблицу и упростить вычисление синдромов.

Сообщение отредактировал andyp - Feb 18 2015, 08:40

В моем случае используются короткие блоки (до сотни бит). Боюсь, ldpc будет не совсем эффективен. Да и оверхед r=1/3 не совсем приемлем.
Я больше склоняюсь к BCH 32.21 с мягким декодированием по М-алгоритму:

http://dsp-book.narod.ru/BCH_SOFT.ZIP

Но. учитывая полное отсутствие практического опыта в теме, не могу судить об эффективности данного алгоритма и целесообразности его использования в моем случае вместо Golay + tri-state квантованием. Наверное, результат определится сравнением в рабочей реализации, буду пробовать.

рекурсивный двубинарный турбокод систематический, минимальный размер данных что видел 6 байт (Wimax) + избыточность в зависимости от скорости кодирования. размер данных кратен байту (Wimax 6 - 1024 байт).

Вам бы требования по требуемому BER на выходе и вероятности ошибки в канале для себя сформулировать. Тогда станет ясно, что использовать. Для Голея и БЧХ помехоустойчивость известна. Для остальных кодов есть куча границ, позволяющих ее оценить.

Сформировал в первую очередь, но в виду отсутствия опыта сам определиться не могу, постараюсь изложить.

Речь идет о дата-модеме через сжатый GSM голосовой канал (негаусовский, неизвестные свойства). Экспериментально достигается чистый BER 1% на 2666 bps (импульсное кодирование по Kondoz, адаптированное к GSM FR каналу), с резким ростом при дальнейшем повышении битрейта. часть битов кодируется позицией пульса, а часть - его знаком (эти биты более устойчивы), можно оценить вероятность ошибки для каждого бита (для мягкого декодирвования).

Необходим битрейт 1200 c BER хотя-бы 0.1% (в канале будет использован кодек MELPE, имеющий собственный FEC). Фрейм MELPE содержит полезный 81 бит и должен обрабатываться целиком по получению.
Отсюда: максимальный оверхед для коррекции r=1/2 с соответствующей длиной блока. В принципе, требования не особо жесткие, но хочется иметь запас прочности. При меньшем оверхеде FEC можно снизить битрейт, скажем, до 1333, получив выиграш в чистом BER в 8 раз (до 2000 - в 4 раза). Есть ли смысл?

Буду благодарен за советы.

PS: Идея с tri-state возникла при анализе работы GSM-кодеков: "сгущать" пульсы можно до предела, определяемого кодовой книгой кодека, затем резко растет BER. Потенциал увеличения битрейта видится в квантовании пульса по амплитуде (0/1/-1), отсюда вспомнился троичный Голей. Не факт, что это верный путь, надо пробовать.

ИМХО тут в первую очередь надо думать о модуляции-синхронизации устойчивой к пропускам, короткие блоки, код Рид-Соломон со стираниями и перемежением, исправляющий пропущенные блоки.

А как вы собирались двоичные данные в троичный код упаковывать?

Модуляция определяется свойством канала, и пропуски - самая малая проблема. Я перелопатил массу литературы и понял, что задача реально сложная. Метоl кодирования позицией пульса - один из возможных, и, видимо, не самый оптимальный. Кодирование псевдоречевыми символами по специально подобранному алфавиту более интересно, но пока сложно для меня в реализации (я вообще не специалист в DSP), позже буду пытаться (Дэвид Ровэ обещал помочь).

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


Пока хотел только попробовать концепцию. Можно попытаться подобрать блок близко к 3^m > 2^n, еще не думал над этим. Но, скорее всего, от безумной идеи придется отказаться и по другим причинам.

Смотрите, есть union bound на корректирующую способность кода:

P_e < sum[i = t+1...n](nchoosek(n,i)*p^i*(1-p)^(n-i))

t = floor((dmin-1)/2)

У Вас p = 0.01 для нетернарного Галея n = 24, d_min = 12, имеем P_e < 1.5e-7 Избыточности явно многовато, чтобы получить P_e = 0.001.

Для БЧХ (31,21)
P_e < 0.0036 (может подойти, может - нет. надо моделировать)

Для БЧХ (31,16)
P_e < 2.5e-4 (подойдет точно)

ну и т.п.

PS Если ошибки барстами, то будет плохо. Интерливить придется

Сообщение отредактировал andyp - Feb 18 2015, 12:56