Здравствуйте!

Столкнулся с задачей турбокодирования и сразу возникли проблемы с документацией и литературой касательно темы. Единственный неплохой на мой взгляд источник информации (на русском языке), который я нашел, это книга Б. Скляра "Цифровая связь". Но все же, эта информация дает базовые теоретические знания о турбокодировании и не раскрывает до конца всех тонкостей проектирования турбокодека применительно к практике (программные или аппаратные реализации).
С кодером проблем, естественно, не возникло. Трудности появились с реализацией так называемого SISO декодера, а точнее с вычислением логарифмического отношения функций правдопродобия (LLR), по алгоритму MAP (Maximum A Posteriori). С математикой в принципе все ясно, применяем теорему Байеса, вычисляем прямую, обратную метрику состояний и метрику ветви и т.д. Но это в теории. Хотелось бы взглянуть на аппроксимированную практическую реализацию, т.к. исходный алгоритм MAP существует только в теории, а на практике применяют его модификации, такие как log-MAP и MAX-log-MAP.
Вобщем, буду рад, если у кого-нибудь найдется достаточно подробная информация по вычислению LLR декодера турбокодов применительно к практической реализации (программная или аппаратная).

Благодарю за внимание!

Вы не уточнили о каком декодере идет речь: сверточном или на базе компонентных (блоковых) кодах. В Скляре описаны алгоритмы для построения обоих видов. В книге достаточно хорошо описан алгоритм декодирования блоковых турбокодов с аппроксимацией MAX-log-MAP, где в качестве компонентных кодов используются коды с проверкой на четность. По этому описанию я делал программный декодер, все работает на УРА. Можете для блоковых кодов также применить алгоритм Чейза, но по сравнению с MAP данный алгоритм обладает меньщей помехоустойчивостью. Этот алгоритм минимизирует вероятность ошибки в последовательности и реализующий его декодер является декодером максимального правдоподобия (наподобие декодера, реализующего алгоритм декодирования Витерби). Алгоритм MAP дает минимум вероятности ошибки для каждого символа в отдельности и в этом смысле является оптимальным алгоритмом. По Чейзу я тоже делал декодер, помехоустойчивость, конечно, ниже чем у МАРа, но выше, чем у жесткого декодера (например, реализующего табличный алгоритм) и, кроме того, выше быстродействие чем у МАРа.
Со сверточными кодами все по-сложнее, но описание в Скляре тоже достаточное для понимания.
Еще есть хорошая книга: Morelos-Zaragoza R.H. The art of error-correcting coding. Кроме того, на этом сайте приведены исходные коды на С построения различных кодеков, в том числе и турбокодов. Можно еще поискать на сайте компании AHA. Она специализируется как раз на разработке турбокодов и круче их в этой области нет.

Благодарю за развернутый ответ и ссылки на ценную информацию!

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

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

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

Вспомнил, достаточно глубоко сверточными турбодекодерами занимались в University of South Australia. Как-то на глаза попадалась кандидатская диссертация, автор Sorin Adrian Barbulescu. У них эти декодеры были реализованы аппаратно.
Посмотрите еще здесь

TI spra629 ранее просматривал, но не ковырял и особо не разбирался. Очень близко к теме, по крайней мере код есть и разжеванно вроде как понятным образом. Если не ошибаюсь, в этой публикации реализуется алгоритм max-log-MAP. Вот что при первом просмотре насторожило: использование библиотек типа "poly2.h". Каково Ваше собственное мнение по поводу этой документации?

А насчет диссертации из University of South Australia, сейчас проверю. Спасибо за помощь!

И вот ещё такой вопрос: существует множество алгоритмов перемежения (чередования), опять же, блочный, сверточный, псевдослучайный и некоторые специализированные алгоритмы. Мое мнение такого - для аппаратной реализации самый простой это блочный алгоритм (собственно матрица в ОЗУ: записываешь построчно, читаешь по столбцам). Подойдет ли такой блочный перемежитель для сверточного кода? В принципе, при такой реализации сверточный код преобразуется в квазиблочный, длина которого определяется длиной перемежителя + число хвостовых бит необходимых для погашения бесконечной импульсной характеристики систематического рекурсивного сверточного кодера.

В реализованном в этом документе алгоритме используется Log-MAP аппроксимация. Не могу понять, что Вас насторожило в библиотеке "poly2.h". Там приведены макросы для расчета метрик состояния декодера, которые затем используются для расчета прямых и обратных метрик состояний, на основании которых позже рассчитываются оценки внешних правдоподобий. Немного сумбурно получилось, но, по-моему, логика не нарушена.

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

log-MAP я так понимаю по эффективности не уступает классическому (неаппроксимированному) MAP, аппроксимация max-log-map напротив, уступает по эффективности но упрощена в реализации. Мне как раз log-MAP и необходим, т.е. spra629 соответствует моим потребностям.

Диссертацию товарища Sorbin'а пока не нашел.

По поводу перемежителя, не найдется ли у вас информации по поводу алгоритма псевдослучайного перемежения. Или, если можно, хотя бы в общем описании идею подбросьте.

По эффективности Log-MAP ничем не отличается от классического представления отношения функций правдоподобия. Если взять логарифм от этого соотношения, то получается очень удобная метрика. В отличие от Log-MAP, аппроксимация Max-Log-MAP выбирает минимальное (или максимальное, кому как удобно) из всех значений, при этом соответствующим образом учитывается знак всего этого преобразования.

По поводу перемежителя достаточно подробно можно почитать: Дж.Кларк.Дж. Кодирование с исправлением ошибок в системах цифровой связи. На мой взгляд это вообще одна из самых лучших книг по помехоустойчивому кодированию, классика. А если вкратце, то псевдослучайное устройство перемежения записывает N символов последовательно в память с произвольной длиной выборки (база перемежителя) и затем считывает их псевдослучайным образом. Закон перемежения может быть задан следующим образом:
I(n+1)=(a*I(n)+b)mod(N).
где константы a и b выбираются определенным образом.
Закон перестановки может быть выбран и другим образом по Вашему усмотрению.
Кроме того, работа устройств перемежения и деперемежения должна быть синхронизирована. Для этого в перемеженный поток могут вводиться дополнительные биты синхронизации. При малой базе перемежения N синхронизация может быть осуществлена с использованием перебора всех вариантов фазирования связки деперемежитель – помехоустойчивый декодер с использованием в качестве критерия правильной синхронизации деперемежителя оценки частотности ошибок на выходе декодера. В свое время я разрабатывал декодер Витерби с матричным деперемежителем базой 16. Так там я использовал как раз последний описанный вариант синхронизации.

Книгу скачал, - то что нужно!

Большое Вам человеческое спасибо за помощь в данном вопросе!

Пожалуйста, обращайтесь .

Примите совет: поищите документацию на стандарт IEEE 802.16.
Там конкретные параметры кодов (как блоковых так и сверточных) и конкретные параметры перемежителей.
Если вы новичек в этих вопросах,
то лучше реализовать стандарт, а не изобретать велосипед

Совет принял.

Нет, ну это естественно, изобретать велосипед я не собирался.
Я вобще преследую цель познания функционирования системы турбокодов на аппаратном уровне (можно и на программном), т.е. пока остановился на этапе "как это все дело работает на практике".
Выбор параметров кода - это уже чисто подбор статистически оправданных реализаций после их тщательного моделирования и тестирования при различных наборах параметров (на эту тему есть множество публикаций, поэтому здесь проблем не будет, и действительно, как Вы правильно заметили, лучше придерживаться выбранного стандарта, например CDMA-2000)

to Serg76:

Вот ещё один момент заинтересовал, касающийся алгоритма псевдослучайного перемежения. Я так понимаю генератор псевдослучайной последовательности при генерации N чисел иногда будет их повторять, т.е. если необходимо перемешать, скажем, числа от 0 до 99 (в нашем случае это и будут 100 адресов зашитые в ПЗУ для дальнейшего использования в перемежителе), то ГПСП при рандомизации все равно какое-то число, но повторит, получается нужна какая-то защита от повторения чисел в массиве или как?

Допустим программно, воспользовавшись встроенной функцией ГПСП Random(N), где N - диапазон чисел, и циклом для заполнения массива случайными числами, также будут наблюдаться повторения, поэтому алгоритм псевдослучайного перемежения программно выглядит относительно не просто, как могло бы показаться (да так, чтобы ещё и об оптимизации не забыть, длины перемежителя то достаточно большие).

Может что упустил и не правильно понял?

По-моему, в Кларке описана подобная ситуация, п.8.3.2, с.327-330. Кроме того, по моему мнению, для предотвращения подобных "критических" ситуаций, когда выходная последовательность приобретает периодический характер с периодом меньшим периода ПСП могут быть предусмотрены специальные схемы контроля, которые выявляют периодичность элементов на входе и нарушают ее. Так, например, сделано в самосинхронизирующихся дескремблерах согласно рекомендации ITU-T (к сожалению номер не помню).

Предложение по реализации ГПСП у Кларка читал, жаль не могу найти документ "Coding for Navy UHF satellite communications" предложенный им как ссылка на аппаратную реализацию такого алгоритма.

У меня очередная порция вопросов Вопрос касается кодовой скорости R (степень кодирования). Ладно, с кодовой скоростью 1/2 и 1/3 все просто, если есть необходимость мультиплексируем биты и пускаем по каналу. Интересуют кодовые скорости типа 6/7, 4/5, 3/4 и т.д. Взять к примеру кодовую скорость 6/7. т.е. на 6 входных бит приходится 7 выходных, по какому принципу происходит выкалывание? Зависит ли количество RSC-кодов кодера или количество полиномов генератора кодов кодера на блок формирования выходного пакета (т.е. блок выкалывания). Ставлю вопрос ребром: можно ли на классическом кодере турбокода с двумя идентичными параллельно расположенными сверточными систематическими кодами реализованных на двух полиномиальных генераторах сформировать скорость кодирования 6/7 и др. скоростя?

Заранее благодарен за ответ!

Можно. Используется схема как в стандарте dvb-rcs. Идея состоит в том, чтобы уйти от кодера 1/1 на, допустим, 2/2. При этом улучшается сходимость процесса декодирования, уменьшается чувствительность к выкалыванию, но декодер надо перевести в недвоичный режим.

Кратко ознакомится можно в прикрепленном файле.

Нажмите для просмотра прикрепленного файла

А как быть с нормализацией? На аппаратном уровне все оперируемые величины представляют собой действительные числа с разрядностью R (в программном же эквиваленте при расчете LLR используют вещественные данные). Вот скажем такой пример:
Рассчитываем метрики ветвей Gamma. В программе можно было бы использовать выражение

где AP- априорная вероятность (т.е. апостериорная вероятность предыдущей итерации. При первой итерации AP=0.5), X-Систематические данные, Y-проверочные данные, U и V -данные определяющие выход кодера в момент времени k. Естественно Gamma имела бы тип double или float.

Так вот, для облегчения вычислений в аппаратуре, это выражение представляет собой как логарифм метрики ветви, т.е.:

Причем априорную вероятность хранят, я так понимаю, в ПЗУ (заренее вычисляется вобщем, т.к. натуральный логарифм вычислять это целое дело, хотя могу и ошибаться, так что это дело также пока под вопросом).
Основной вопрос такой, в каком виде лучше хранить вычесленные метрики, ну и соответственно логарифм априорной вероятности? Я представляю себе систему вот такую: на вход SISO декодера подаются мягкие решения с АЦП, допустим с 32-х уровневым квантованием. т.е. логический '0' будет представлять собой "00000", логическая единица - "11111", соответственно, например, аналоговый уровень 0.5, будет представляться как "10000". Далее, уже внутри системы разрядность может быть увеличена. Соответсвенно все вычисления на аппаратном уровне будут представляться именно в таком виде. Можно ли использовать такой подход к решению задачи? Или все-таки необходимо привести все к вещественному виду по правилу машинного представления дробных чисел. Соответственно при таком подходе увеличится и масштаб вычислений. Очень интересно Ваше мнение.

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

Я не говорил что квантование 32-х битное Я сказал что оно 32-х уровневое, т.е. как раз 2^5=32, а значит шина 5 битная и соответственно АЦП 5-ти разрядный.
А как насчет логарифма априорной вероятности? Вычислять, квантовать и зашивать в ПЗУ?

Да, действительно, невнимательно прочитал. Я в своем декодере использовал Max-Log-MAP аппроксимацию и поэтому вычисление функций правдоподобия там делается просто: выбором максимального (минимального) абсолютного значения элемента с учетом знака. При использовании Log-MAP аппроксимации для вычисления LLR используется заранее подготовленная таблица всех возможных расчетных значений.

Да, но если Ваш декодер итеративный, то вы должны были использовать выходную апостериорную вероятность (внешнее LLR декодера) в качестве входа априорной вероятности. Кстати, я так понял, что в принципе, от алгоритма Max-Log-MAP к алгоритму Log-MAP перейти довольно таки просто. Поэтому я решил пока с Max-Log-MAP аппроксимацией поэкспериментировать, он по-проще.
Вот, схемку прикрепил. Интересует блок Look-up Table в котором вычисляются, то-ли хранятся логарифмы априорной вероятности.

Декодер, конечно, итеративный, в этом и заключается принцип турбокодирования. После каждой итерации значения внешних LLR одного декодера служат для обновления априорной информации другого декодера и, соответственно, после каждой итерации оценки выходных LLR каждого из декодеров будут расти в правильном направлении. После определенного количества итераций решающее устройство выносит жесткое решение в пользу того или иного бита (0 или 1) в зависимости от знака апостериорного значения последнего декодера (выходного LLR).
По поводу схемы отвечу Вам в понедельник, есть кое-какие описания, но они на работе.

Благодарю, буду ждать.

Начните с этих материалов.

Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла

2Rundll
В принципе все то, что я хотел посмотреть изложено в доках, которые привел Grumbler_2002. В log-MAP алгоритме основные вычислительные затраты связаны с вычислением ф-ции логарифма

xEy = min ∗(x, y) = -ln(e^x + e^y) = x - ln (1+ exp(x-y)) = y - ln (1+ exp(y-x)) =

= min(x, y) - ln (1+ exp(−|x-y|)) = min(x, y) + fc (|y − x|) ,

которую необходимо затабулировать. На основании этой ф-ции происходит вычисление LLR.
Приведу код расчета на С для расчета ф-ции Е.

#define QQTZ_BIT 16
#define E_FUNCTION_SIZE (1<<QQTZ_BIT)

/* E function look-up table */
float E[E_FUNCTION_SIZE];


/* E function
compute min(x,y)-ln(1+exp(-abs(x-y)))
*/
float E_function(x,y)
float x,y;
{
long z;
float ab;
ab = fabs(x-y);
if (ab>16.0) return min(x,y);
z=(long) (ab*4096.0);
return min(x,y)+E[z];
}

/* Generate look-up table */
for (int k=0;k<E_FUNCTION_SIZE;k++)
{
E[k]=(float) -log(1.0 + exp(-(float)k/4096.0));
}

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

Я пользовался Max-Log_MAP аппроксимацией. Энергетические потери для разных кодов составляли значения в диапазоне от 0,5 до 1,5 дБ. Хватит ли ему такой помехоустойчивости при планировании бюджета канала связи или может не хватить. Окончательный выбор, конечно, за разработчиком.

Коррекцию extrinsic information использовали? У меня разница max-log-map и log-map от силы пару десятых дБ была.

Внешние LLR конечно использовал, это же вытекает из принципов турбокодирования. Просто я сравнивал свой декодер с реализованным фирмой AHA (лучше их в этой области нет) для различных компонентных кодов, построенных на базе кодов Хемминга, модуляция QPSK, квантование 3-х битное. Скорее всего у них есть какие-то фирменные примочки типа дополнительных коэффициентов обратных связей и пр.

Дык у Вас блоковые турбо-коды (коды-произведения с турбо-декодированием), а мы говорим о сверточных. Для них (сверточных турбо-кодов) есть видоизмененная схема декодера, позволяющая на max-log-map-алгоритме достигнуть эффективности log-map с потерей порядка 0.1 дБ путем коррекции extrinsic information.
По поводу Ваших результатов мне сложно заочно сказать, в чем могут быть отличия в реализациях. Мой отрицательный опыт был с гипер-кодами. Проигрыш был порядка 1 дБ по сравнению с эталоном. Что они там наворотили в декодере - неизвестно.

У меня к Вам просьба. Нет ли у Вас литературы по гиперкодам. Хотелось бы по-глубже с ними разобраться. Спасибо.

Выложил всё, что у меня есть на текущий момент. Собственно, это исследование десятилетней давности, и ничего нового, скорее всего, не появилось. У гипер-кодов ограниченное применение.

Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла

Еще раз спасибо за предоставленные материалы. Обязательно в них покопояюсь .

В продолжение темы выкладываю на мой взгляд лучшие публикации по теме турбокодирования сверточных кодов (для новичков). Публикация отличается более мягкой формой преподнесения материала, а также практическими примерами рассчета как PCCC кодера так и MAP декодера, что называется "step-by-step", все ясно, доступно и наглядно! Вдобавок прикрепляю EXCEL-файл, демонстрирующий все тонкости рассчетов и предлагающий возможность самостоятельно "пощупать" кодек, не прибегая к "расшифровкам" сторонних C++ файлов и т.д. Надеюсь, эта информация многим будет очень полезна.
После изучения данных материалов, можно спокойно приступать к освоению публикаций предложенных товарищем Grumbler_2002, за что ему отдельное спасибо, информация очень даже достойная.

Прочитал некоторую литературу насчёт систематических турбокодов, в том числе упомянутую тут.. Возник вопрос. После нахождения LLR первого декодера, LLR нужно перемешать (interleave)... В стандарте 802.16, например, перемешиватель построен таким образом, чтобы перемешивать дубиты (00, 01, 10, 11) А LLR вычисляется как 1 символ мягкого решения. Как его перемешивать?? Меня этот "деинтерливер" вообще в тупик поставил.. (( Может каждый символ LLRа тоже переводить в дубит??

Столкнулся сейчас с аналогичной проблемой. Скляра почитал, но у него всё в основном на формулах и теоремах, а мне б посмотреть где-нибудь алгоритм MAP для свёрточных рекурсивных кодов, разъяснённый "на пальцах" (т.е. в виде блок-схемы или, что лучше, фрагментов кода), чтоб было понятно человеку, который больше разработчик программ, нежели метематик. Никто ничего не посоветует?

Занимаюсь решением такой же задачи.
строю декодер.. точнее только приступаю.. собрал кучу всякого материала и изучаю его. пока понимание слабое всех процессов.
задача стоит в аппаратной реализации MAP турбодекодера на FPGA.. предположительно какой-то из Сцыклон3.

несколько вопросов тем кто уже решал и решил данную задачу.
1. сколько ресурсов матрицы занимает декодер.
2. скольоко использовано памяти (у меня максимальный размер блока 12306 ).
3. каких скоростей декодирования достигли.

и ещё.. (наверно нагло конечно).. если у кого-то есть наработки которыми могут поделиться для изучения - поделитесь )
если есть хорошие решения, то наверно можно попробовать обсудить даже вплоть до покупки.. в рамках разумного конечно.
для конечного применения или как базу для доработок.. т.к. с нуля долго и мутроно.
VHDL или Verilog.. (verilog предпочтительно)

Вот эта компания, предлагала нам свой LPDC кодек http://www.iprium.ru/ попробуйте может быт найдете общий язык %)

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

правильно ли я понимаю алгоритм Чейза для декодирования TPC:

1) Находим n наименее надежных битов
2) создаем 2^n тестовых векторов
3) декодируем, используя жесткий декодер все 2^n последовательностей
4) из всех декодированных, находим ту, которая находится на наименьшем Евклидовом расстоянии от принятой.
5) вычисляем коэффициенты обновления LLR каждого бита в кодовом слове, полученном в 4 пункте.
6) обновляем LLR всей строки/столбца, используя данные из п. 5, следуя схеме из прикрепленного рис.

Рисунок взят из статьи Near-Optimum Decoding of Product Codes: Block Turbo Codes. by ramesh pyndiah. Так же эту схему нашел в мореллосе и зарагозе и в книге channel_coding_in_communication_networks на стр. 347. Судя по всему она очень популярна.

Насколько я понимаю, бит четности не используется при декодировании кодового слова жестким декодером, а используется при вычислении Евкл. расстояния. так ли это?

Не могли бы порекомендовать лит-ру(кроме Скляра) по MAP (и его аппроксимациях) применительно к TPC, а не TCC?

В 5 пункте ещё конкурентные слова нужно учитывать.



Да.



Channel Coding in Communication Networks - Glavieux
Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Wireless Channels - Hanzo, Liew, Yeap

спасибо

гляньте еще вот эту статью, я по ней делал. там есть опечатка в разделе "Main processing loop" на 4 стр.

2 vadimuzzz,
а Вы дедодер TPC сделали только программно или еще железная реализация есть?


2 all,

есть ли алгоритм декодирования TPC (за исключением алгоритма Chase-Pyndiah, о котором я спрашивал выше), который бы легче можно было реалитзовать в железе (FPGA) ?


-thanks

MAP (maximum-a-posteriori) и его аппроксимации LOG-MAP и MAX-LOG-MAP. AHA так и делает (например, чип AHA4540)

Serg76, а откуда у Вас информация эта?
Если не секрет, дайте пожалуйста, почитать ссылку где это описано.

попробуйте погуглить - информации много

есть на FPGA

подскажите, пожалуйста, для 2D турбокодов с гипер осью (enhanced Turbo Product Codes),
могут ли базовые коды для осей Х и У быть различными?
например: X --> (32,26), y --> (16,11) ?

смотря на картинку (для одинаковых базовых кодов по осям (8,4) в данном случае) правило по которому вычисляется enhanced-parity row понятно,
как оно изменится если код, например, по оси Х будет "длинее" (если ответ на 1 вопрос - да)?

-спасибо

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