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

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

Жесткое декодирование. На сколько я разобрался, 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 раз уменьшить таблицу и упростить вычисление синдромов.

В моем случае используются короткие блоки (до сотни бит). Боюсь, 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 Если ошибки барстами, то будет плохо. Интерливить придется

Вот на неё все усилия и направить, чтобы не была чувствительна к искажениям кодека, исправлять недостатки модуляции кодированием плохая идея.

а почему основание - 2, код ведь троичный, т.е. все преобразования надо делать в поле GF(3)? Во-вторых, насколько я понимаю, для линейных кодов размер таблицы определяется как B^(n-k), где B - основание кода. Уменьшить размер таблицы и сложность декодера можно за счет свойств цикличности, в этом я с Вами согласен.

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


Это понятно, вначале предполагалось использовать какую-либо устойчивую низкобитрейтную схему вообще без FEC, но вот подобрать ее оказалось непросто. Сперва показалось, что я просто плохо ориентируюсь в теме, но, изучив существующие варианты, понял, что большинство - по типу шаманства. Сапожников, например, вообще рассматривает кодек как "черный ящик" и использует методы стохастической оптимизации.
Поэтому решил попробовать пойти другим путем: используя какую-либо более-менее приемлемую модуляцию с избыточным битрейтом, и попытаться найти хороший алгоритм оценки вероятности ошибки каждого бита, таким образом, реализовать эффективный FEC с мягким декодированием.
Альтернативные пути (например, реализовать несколько копий блока с незначительными изменениями лишь части бит от копии к копии, и пускать их последовательно, эмулируя основной тон речи), тоже рассматриваются.

PS: буду благодарен за любые, самые дикие, идеи.

Почему 2? Потому что компоненты вектора ошибки могут быть 1 и 2, но не 0, т.е. 3-1 = 2. Всего синдромов может быть действительно B^(n-k), но не каждому синдрому соответствует только один error pattern. Для исправления нужно использовать только те синдромы, которым соответствует один возможный вектор ошибки. Вот, в википедии про синдромное декодирование тоже самое написано для случая бинарного кода:
http://en.wikipedia.org/wiki/Decoding_meth...ndrome_decoding

В случае тернарного кода биномиальные коэффициенты в формуле из википедии будут с весами (B-1)^i, i - количество ошибок в кодовом слове.

это опять же исходя из свойств цикличности?

Избыточности ~1/2, которая у Вас есть вроде бы вполне достаточно, чтобы получить выигрыш в 10 раз по BER при сыром BER 1%.

Ну т.е. можно начать пробовать с бинарного Галея или БЧХ. Можно даже с жестким декодированием - исправляющей способности вроде должно хватать. Потом, когда втянетесь , можно будет и о мягком декодере подумать.

Снижать скорость передачи особого смысла нет - выигрыш от кодирования нормальным кодом всегда больше, чем просто выигрыш по энергетике при передаче некодированных бит.



Да нет. Просто ненулевые компоненты вектора ошибки могут иметь значения 1 или 2. Ну или 0, только это уже не ошибка

Пусть вектор ошибки из n компонент [000...x00..x..0], Вот x может быть 1 или 2 в случае тернарного кода. Если позиций с x в векторе i, то таких векторов всего может быть nchoosek(n,i) (С из n по i)

Понятно, видимо я не правильно воспринял Вашу фразу:

"Потому что компоненты вектора ошибки могут быть 1 и 2, но не 0, т.е. 3-1 = 2"

Нет. Если какой-то компонент равен 0, то фактически это означает, что ошибок было меньше. Поэтому там получается сумма биномиальных коэффициентов. Т.е. в случае нашего тернарного Голея, который исправляет до 2 ошибок имеем 2*nchoosek(12,1) + 2^2*nchoosek(12,2) = 288 синдромов, которые стоит рассматривать. Всего возможных ненулевых синдромов 3^6 - 1 = 728

Для двоичного Голея, который (24, 12, 7) и исправляет 3 ошибки имеем

nchooosek(24,1) + nchoosek(24,2) + nchoosek(24,3) = 2324 синдрома из 4095 ненулевых.

Ну и еще для иллюстрации рассмотим не quasiperfect, а perfect код Хамминга (7, 4, 3), исправляющий одну ошибку. Для него количество рассматриваемых синдромов
nchoosek(7,1) = 7. Всего ненулевых синдромов тоже 7 (2^(7-4)-1), что и следовало ожидать, так как код совершенный.

ок, спасибо, уже сам понял, что имелось ввиду

В качестве бреда, может лучше тональные сигналы по частоте двигать несколькими некогерентными MFSK, чем импульсы по времени?

Может. В соседней теме я давал ссылку на hermes-модем на основе BFSK. Но там двигали одну частоту и настолько быстро, на сколько возможно. Как я понял из отзывов, ничего хорошего из этого не получилось. Интересно попробовать MFSK, причем сдвигать можно не каждую частоту одномоментно, а последовательно, растягивая изменения во времени.
Пульсы очень хорошо подходят для GSM FR кодека, который RTE и делает выборку, квантуя каждый третий сэмпл из последовательности с максимальной энергией. Сначала я хотел сделать универсальный модем, пригодный в том числе и для низкобитрейтного AMR, но потом понял, что это почти нереально. Учитывая, что все GSM сети и телефоны поддерживают GSM FR, и в большинстве случаем можно его включить принудительно (отключив другие варианты), пока сосредоточился на этом варианте, пытаясь его улучшить оптимальным кодированием.

Скажем, если речь идет об amr-nb, то скорость в канале передачи информации об огибающей спектра это 1150 - 1900 бит/с. (4.75 - 12.2 общая). Т е выше этой скорости на всяких угловых модуляциях едва ли можно получить. Да и есть проблема асинхронности нарезки на блоки кодеком и модулятора. Так что даже эти скорости два ли достижимы. Скорость в канале кодирования импульсного возбуждения 1800 - 7000 бит/с. Именно в этой связи используют модуляцию положения импульса с урезанной полосой. через 12.2 и 10.2 (7000 и 6200) ecall пролазит без проблем с 1-ой попытки (скорость данных 1245 бит/с). 7.95 (3400) и ниже уже начинаются проблемы. Скорость падает радикально. Ну и лучшесть гсм-фр перед амр-нб-12.2 вполне понятна. Ибо в гсм скорость канала кодирования положения импульсов 7800 бит/с.

Что-то подумалось, а что бы Вам обычный сверточный код не поиспользовать? Удобство заключается в том, что легко сделать нужную длину блока. К тому же, алгоритм витерби будет хорошо работать с битами разной надежности (как он нормально работает для pragmatic qam). Начать можно с обычного r =1/2; k = 7 кодера, блоков, скажем 2*81 бит, а затем, если лишняя помехоустойчивость будет, можно прикрутить выкалывание.

Интересные обобщенные оценки, под таким углом я не смотрел.

ECall делался с упором на универсальность, но для GSMFR гораздо лучше паттерн 4 позиции одного пульса в 12 сэмплах, чем 4 в 16: кодек использует RTE по каждому третьему сэмплу.
Также очень низкий BER получается при двух позициях одного пульса в 6 сэмплах + знак Манчестерским кодом, паттерн не требует отбеливания, хорошо вписывается в полосу пропускания и подходит в т.ч. и для EFR.
Пытался победить AMR475, изменил паттерн до 8 позиций одного пульса в 40 сэмплах (что хорошо вписывается в кодовую книгу - там 2 пульса на 40 сэмплов, т.о. никогда не будет превышения по количеству пульсов), но тогда искажается знак пульса: после кодека единичный пульс на осциллограмме вырождается в затухающую синусоиду ("звенит"). Похоже, для низкобитрейтных кодеков коррелятор в демодуляторе - не лучший вариант, надо пробовать другие техники.
Отдельная история - VAD, с ним я пока не играл, позже отпишу.


Спасибо, сейчас почитаю о витерби. Я так понял, он использует 7-битные символы в виде блока произвольной длины? Вариант 2*12 блоков выглядит интересным. Что он может скорректировать? Можно ли на входе использовать мягкие биты (в моем случае соотношение энергий в предполагаемых позициях пульсов в виде float)?

Это сверточный несистематический код, 7- кодовое ограничение (длина регистра сдвига). Декодер строится довольно просто, как для жесткого, так и мягкого входа, разница лишь в блоке подсчета метрик (Хемминга для жестких решений, Эвклида для мягких). Выигрыш от кодирования примерно 5,5 дБ для 1е-6. Может стоит добавить циркулярности к коду, чтобы убрать терминирование.

Спасибо, витерби выглядит весьма привлекательно к задаче.
Почитал лекцию:
http://web.mit.edu/6.02/www/f2010/handouts/lectures/L9.pdf
Нашел подходящую готовую реализацию:
http://gnuradio.org/redmine/attachments/do...io-3.7.5.tar.gz
Окно декодирования 64 бита (в принципе, приемлемо, для 81-битный MELPE-блок даст лишние 53 mS латентности и потребует буферизации 67.5 mS фрейма перед проигрыванием). Выдача декодера - каждые 16 бит, тоже приемлемо. K=7, rate=1/2.
Мягкое декодирование - именно то, что может существенно снизить BER в данном случае, надо подумать о вариантах адекватной оценки Es/N0 в демодуляторе.
Как думаете, какой BER можно скомпенсировать и в какой мере?
Буду пробовать.

Viterbi perfomance в сети полно, можете сами прикинуть какой ЭВК нужен, не забывайте, что сложность декодирования по Витерби экспоненциально зависит от длины кодового ограничения K. Если уж зашла речь о сверточных кодах, то может для лучшего согласования с модуляцией в вашем случае можно будет применить недвоичные сверточные коды (турбокоды), что-нибудь по мотивам DVB-RCS, о котором упоминал des00 в начале топика.

Нет 7 - это просто память регистра, используемого в кодере. Этот код сверточный, так что блоки могут быть любыми, больше примерно 30 бит. На счет BER на сколько помню, жесткое декодирование дает выигрыш ~7 dB ну и еще ~2.5 dB даст мягкое декодирование.

Это очень грубая оценка. К сожалению под рукой нет weight enumerator function стандартного кода, чтобы посчитать BER. Можете поискать в интернете кривые BER кода (133, 171) чтобы прикинуть результаты мягкого декодирования.

наверное, это все-таки для каскадной схемы RSV, для чистого Витерби многовато

Может быть. Книжек под рукой нет. Вот картинка для мягкого 8-уровней квантования:

как я и отмечал выше, где-то 5,5 дБ для Pb=1e-6 )))

кое что в памяти еще осталось )))

Там еще один стандартный код есть с K=9 (полиномов не помню). У него dfree побольше, он получше будет, но декодер сложнее

PS Добрался до Lin Costello и понял, откуда у меня 7 dB в голове оказалось

это asymptotic coding gain как 10log10(Rate*d_free/2)

на самом деле их достаточно, из практических есть даже с К = 15 { 0x45dd, 0x69e3 }, для К = 9 { 0x1af, 0x11d } - под стандарт IS-95 CDMA, да в том же GSM c К =5 { 0x13, 0x1b }, а сложность растет экспоненциально от К

Ну да. Я б все-таки K=15 и Витерби декодер советовать побоялся. Там что-то подоптимальное нужно типа Фано. Сверточные коды с длинным регистром - совершенно забытая сейчас тема. Раньше делали в погоне за d_free.

Спасибо, еще почитал Скляра:
http://www.rphf.spbstu.ru/dsp/lib/Sklar_Dig_Com_2003.pdf
теперь более-менее систематизировалось в моем понимании.

до кучи, если есть матлаб, то bertool строит кривые для сверточных кодов с мягким и жестким решением, также коды хэминга, БЧХ

Кстати, да. Я думаю это произошло из-за того, что несмотря на присущие достоинства методов последовательного декодирования (декодирование любых сверточных кодов с большими степенями порождающих полиномов как для мягкого, так и жесткого входа), у них есть один недостаток: в зависимости от уровня канального шума число вычислительных операций для продвижения в каждую следующую кодовую вершину является случайной величиной, что требует наличия достаточно большого объема памяти для буферизации данных, особенно, для мягкого входа, а во времена расцвета сверточного кодирования это было определяющим фактором. Сам как-то из спортивного интереса баловался с Фано, декодировал упоминавшийся здесь код с К = 7, по энергетике, конечно, проигрыш, но по скорости несравнимо выше по сравнению алгоритмом Витерби.

После беглого ознакомления с темой у меня возник конкретный вопрос: очевидно, существует какой-то максимальный исходный ber, начиная с которого, FEC работает эффективно. Например, Голей исправляет любые 3 ошибки в 23-битном слове, т.о. оценочно исходный BER должен быть не хуже 0.13 (13%).
Как оценить это значение для Витерби r=1/2, K=7, с окном 64 бита (ориентируясь пока на жесткое декодирование)?

Если так же грубо, то сверточный код характеризуется понятием d_free. Для кода r=1/2, K=7 d_free = 10.

Оценить вероятность ошибки жесткого декодирования грубо можно по следующей формуле:

P_e ~ B*2^(d_free)*p^(d_free/2)

Для рассматриваемого кода B = 36.

Для BER 1% на входе на выходе получится 3e-6

Только не спрашивайте, откуда я это взял

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

Это понятно, но пока что предполагаем равномерное распределение ошибок. В конце концов, можно интерливить биты в пределах 81-битного MELPE-блока, а больше блок нельзя использовать с точки зрения латентности. Оценки по Голею совпадают с моими тестами в программой цифрового радио FreeDV: при добавлении ошибок в канал до 13% качество субъективно почти не меняется, а потом - резкое ухудшение.


Я, наверное, нашел расчет, откуда получена эта эмпирическая формула: в Скляре (ссылку на книгу давал выше) глава 7.4.4, d_free там называют просветом. Если ваша эмпирическая формула работает на верхней границе, то равенство P_e==p получаем при BER 7%, что меньше, чем у Голея. Из формулы также видим, что эта граница резко повышается при снижении d_free. В книге в таблице 7.1 видим, что d_free для аналогичного систематического кода всего 6.
Далее я сам не могу осмыслить и сделать выбор, прошу совета: исходные BER в моей задаче могут быть и 20%, а в результате достаточно и 1% после декодера. Как конкретно решить проблему?


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

ужас. переводные книги - это что-то.

Формула выводится, она не эмпирическая, она описывает асимптотику BER по заданному спектру кода. Формула работает до долей, максимум одной-двух единиц процентов, пока ошибки декодирования определеяются d_free кода. На 7 думаю, что уже врет в разы. Систематические сверточные коды в чистом виде именно поэтому не используются, что у них при прочих равных меньший d_free. Несистематический код (133,171) оптимален в этом смысле (максимальный d_free при заданной длине регистра), поэтому и используется в куче систем связи. Народ его наизусть помнит



При 20% входной BER ни тот ни другой код нормально работать не будут. На сколько все будет плохо сказать не могу (будет на выходе процент или скажем 5). Сверточный код (133,171) в асимптотике точно лучше бинарного Голея.