Golay (12,6,6) Опции

[GeGeL]

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

[Serg76]

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

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

[GeGeL]

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

[Serg76]

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

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

[GeGeL]

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

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

[Serg76]

Я думал об этом, но для 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) дает неплохой прирост помехоустойчивости, практически минимум ошибки для кодового слова, при относительно малой сложности реализации.

[smoke_111]

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

[andyp]

Табличный - это тот же синдромный, для данного кода таблица синдромов будет содержать 3^(12-6) = 729 векторов ошибок

Могу быть не прав, но у меня получается 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

[GeGeL]

Может вам вполне подойдет троичный ldpc из мягких

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

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

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

[des00]

В моем случае используются короткие блоки (до сотни бит).

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

[andyp]

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

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

[GeGeL]

Вам бы требования по требуемому 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), отсюда вспомнился троичный Голей. Не факт, что это верный путь, надо пробовать.

[petrov]

...

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

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

[GeGeL]

тут в первую очередь надо думать о модуляции-синхронизации устойчивой к пропускам

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

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

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

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

[andyp]

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

Смотрите, есть 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

[petrov]

Модуляция...

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

[Serg76]

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

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

[GeGeL]

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

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

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

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

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

[andyp]

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

Почему 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 - количество ошибок в кодовом слове.

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

[Serg76]

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

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

[andyp]

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

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

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

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

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

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

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

[Serg76]

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

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

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

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

Сообщение отредактировал Serg76 - Feb 18 2015, 21:14

[andyp]

Понятное дело, что сложение с нулем - это не исправление ошибки, но как я понял, Вы рассматриваете только те синдромы, для которых компоненты вектора ошибки все должны быть отличны от нуля? Что же тогда будет содержать таблица в случае двоичного кода, один вектор?

Нет. Если какой-то компонент равен 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), что и следовало ожидать, так как код совершенный.

[Serg76]

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

[petrov]

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

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

[GeGeL]

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

[thermit]

Скажем, если речь идет об 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 бит/с.

[andyp]

пока сосредоточился на этом варианте, пытаясь его улучшить оптимальным кодированием.

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

[GeGeL]

Скажем, если речь идет об amr-nb, то скорость в канале передачи информации

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

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

Что-то подумалось, а что бы Вам обычный сверточный код не поиспользовать?

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

[Serg76]

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

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

[GeGeL]

Спасибо, витерби выглядит весьма привлекательно к задаче.
Почитал лекцию:
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 можно скомпенсировать и в какой мере?
Буду пробовать.

[Serg76]

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

[andyp]

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

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

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

Сообщение отредактировал andyp - Feb 19 2015, 21:57

[Serg76]

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

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

[andyp]

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

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

Сообщение отредактировал andyp - Feb 19 2015, 22:13

Эскизы прикрепленных изображений

 

[Serg76]

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

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

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

[andyp]

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

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

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

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

Сообщение отредактировал andyp - Feb 19 2015, 22:48

[Serg76]

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

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

[andyp]

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

[GeGeL]

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

[des00]

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

[Serg76]

Сверточные коды с длинным регистром - совершенно забытая сейчас тема. Раньше делали в погоне за d_free.

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

[GeGeL]

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

[andyp]

После беглого ознакомления с темой у меня возник конкретный вопрос: очевидно, существует какой-то максимальный исходный 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

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

[petrov]

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

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

[GeGeL]

Ошибки не группируются по заказу

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

Оценить вероятность ошибки жесткого декодирования грубо можно по следующей формуле:
P_e ~ B*2^(d_free)*p^(d_free/2)
Только не спрашивайте, откуда я это взял

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

рекурсивный двубинарный турбокод систематический

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

[andyp]

Я, наверное, нашел расчет, откуда получена эта эмпирическая формула: в Скляре (ссылку на книгу давал выше) глава 7.4.4, d_free там называют просветом.

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

Если ваша эмпирическая формула работает на верхней границе, то равенство P_e==p получаем при BER 7%, что меньше, чем у Голея. Из формулы также видим, что эта граница резко повышается при снижении d_free. В книге в таблице 7.1 видим, что d_free для аналогичного систематического кода всего 6.

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

Далее я сам не могу осмыслить и сделать выбор, прошу совета: исходные BER в моей задаче могут быть и 20%, а в результате достаточно и 1% после декодера. Как конкретно решить проблему?

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