[Rundll 0]

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

 

Столкнулся с задачей турбокодирования и сразу возникли проблемы с документацией и литературой касательно темы. Единственный неплохой на мой взгляд источник информации (на русском языке), который я нашел, это книга Б. Скляра "Цифровая связь". Но все же, эта информация дает базовые теоретические знания о турбокодировании и не раскрывает до конца всех тонкостей проектирования турбокодека применительно к практике (программные или аппаратные реализации).

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

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

 

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

[Serg76 0]

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

 

Столкнулся с задачей турбокодирования и сразу возникли проблемы с документацией и литературой касательно темы. Единственный неплохой на мой взгляд источник информации (на русском языке), который я нашел, это книга Б. Скляра "Цифровая связь". Но все же, эта информация дает базовые теоретические знания о турбокодировании и не раскрывает до конца всех тонкостей проектирования турбокодека применительно к практике (программные или аппаратные реализации).

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

[Rundll 0]

Вы не уточнили о каком декодере идет речь: сверточном или на базе компонентных (блоковых) кодах.

 

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

 

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

 

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

 

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

Изменено 30 ноября, 2008 пользователем Rundll

[Serg76 0]

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

Посмотрите еще здесь

SPRA629.PDF

Изменено 30 ноября, 2008 пользователем Serg76

[Rundll 0]

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

Посмотрите еще здесь

 

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

 

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

 

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

Изменено 30 ноября, 2008 пользователем Rundll

[Serg76 0]

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

 

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

 

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

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

 

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

49vt06_woodard.pdf

[Rundll 0]

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

 

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

 

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

 

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

 

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

[Serg76 0]

log-MAP я так понимаю по эффективности не уступает классическому (неаппроксимированному) MAP......

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

 

По поводу перемежителя достаточно подробно можно почитать: Дж.Кларк.Дж. Кодирование с исправлением ошибок в системах цифровой связи. На мой взгляд это вообще одна из самых лучших книг по помехоустойчивому кодированию, классика. А если вкратце, то псевдослучайное устройство перемежения записывает N символов последовательно в память с произвольной длиной выборки (база перемежителя) и затем считывает их псевдослучайным образом. Закон перемежения может быть задан следующим образом:

I(n+1)=(a*I(n)+b)mod(N).

где константы a и b выбираются определенным образом.

Закон перестановки может быть выбран и другим образом по Вашему усмотрению.

Кроме того, работа устройств перемежения и деперемежения должна быть синхронизирована. Для этого в перемеженный поток могут вводиться дополнительные биты синхронизации. При малой базе перемежения N синхронизация может быть осуществлена с использованием перебора всех вариантов фазирования связки деперемежитель – помехоустойчивый декодер с использованием в качестве критерия правильной синхронизации деперемежителя оценки частотности ошибок на выходе декодера. В свое время я разрабатывал декодер Витерби с матричным деперемежителем базой 16. Так там я использовал как раз последний описанный вариант синхронизации.

[Rundll 0]

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

 

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

 

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

[Serg76 0]

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

 

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

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

[SKov 0]

...

И вот ещё такой вопрос: существует множество алгоритмов перемежения (чередования), опять же, блочный, сверточный, псевдослучайный и некоторые специализированные алгоритмы.

Мое мнение

...

Примите совет: поищите документацию на стандарт IEEE 802.16.

Там конкретные параметры кодов (как блоковых так и сверточных) и конкретные параметры перемежителей.

Если вы новичек в этих вопросах,

то лучше реализовать стандарт, а не изобретать велосипед ;)

[Rundll 0]

Примите совет: поищите документацию на стандарт IEEE 802.16.

Там конкретные параметры кодов (как блоковых так и сверточных) и конкретные параметры перемежителей.

Если вы новичек в этих вопросах,

то лучше реализовать стандарт, а не изобретать велосипед ;)

 

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

 

Нет, ну это естественно, изобретать велосипед я не собирался.

Я вобще преследую цель познания функционирования системы турбокодов на аппаратном уровне (можно и на программном), т.е. пока остановился на этапе "как это все дело работает на практике".

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

[Rundll 0]

to Serg76:

 

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

 

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

 

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

[Serg76 0]

to Serg76:

 

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

 

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

 

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

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

[Rundll 0]

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

 

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