для слова.

2 SKov Суть алгоритма можете изложить или ссылку на первоисточник?

Суть алгоритма простая. Сначала упорядочиваются все надежности по возрастанию. Потом для упорядоченной последовательности задается правило перебора самых ненадежных символов принятого слова таким образом, что инвертирование этих символов всегда соответствует тому же синдрому, что и у исходного слова. Т.е. формируются все вектора ошибок, которые могут иметь место, но за счет надежностей часто оказывается, что таких векторов мало. Т.е. вообще говоря, их всегда 2^r, но некоторые вектора ошибок заведомо менее вероятны, чем другие с таким же синдромом, поэтому их можно не рассматривать. Часто оказывается, что надо проанализировать совсем мало векторов ошибок.
Ссылки так вот сразу не дам, но если ОЧЕНЬ надо, могу поискать. Я использовал похожий алгоритм для декодирования кодов Хемминга в двумерном турбо-коде. А Гугл не рулит? Попробуйте.

Получается, что эти алгоритмы очень схожи (по крайней мере, с методом 1), но вот вычислительная нагрузка Вашего алгоритма будет выше вследствие формирования и анализа большего числа векторов ошибок.
1. Совсем мало векторов - это сколько в среднем? скажем, для среднего качества канала. В тоже время для упомянутых Вами расширенных кодов Хемминга с расстоянием d min=4, в алгоритме Чейза (метод 2) надо будет сформировать всего 4 комбинации векторов ошибки.
2. Насколько этот алгоритм выигрывает по отношению к Чейзу при одной и той же вероятности битовой ошибки?
3. Я для декодирования такого же самого семейства турбокодов использовал алгоритм Чейза (метод 2). И думаю, что как раз для итеративного декодирования большой разницы между этими алгоритмами не будет вследствие схожести алгоритмов формирования векторов ошибок и самой по себе итеративной процедуры декодирования. Кстати, еще один вопрос: как Вы рассчитывали оценки правдоподобия на выходе компонентных декодеров?
А вообще, чтобы не было никаких вопросов, то для декодирования турбокодов лучше использовать MAP - получаем потенциальную помехоустойчивость. Это я уж проверил - Чейз отдыхает

Сообщение отредактировал Serg76 - Jan 15 2011, 18:58

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

А Вы не снимали кривую помехоустойчивости Вашего декодера?
Я, конечно же, посмотрю первоисточники (мне это самому интересно), но думаю, что большой разницы в помехоустойчивости не будет, пара десятых децибелла выигрыша за счет усложнения декодера это не выход. И если уже говорить об оптимальности, то еще раз повторюсь, что только алгоритм максимального правдоподобия даст минимум ошибки на символ, а по сложности декодирования он будет находиться на уровне того же Чейза (все-таки главный недостаток Чейза и ему подобных - это тяжелая операция сортировки символов по достоверности), т.к. чистый MAP не используется, а применяются его аппроксимации - LOG-MAP и MAX-LOG-MAP.
А реализация TPC декодера у Вас программная или аппаратная? Если программная, то каких символьных скоростей удалось достигнуть?

Да, конечно. Только было это лет 15 назад, (когда еще не было никаких упоминаний этой конструкции в литературе.)
И сейчас я уже мало что помню .
Вроде произведение двух кодов (16,11,4) давало порядка 10^-6 при порядка 1.8 дБ Eb|N0.


Была программная. На РС. Моделирование шло довольно быстро. Но конкретных чисел скоростей не помню.
Потом вернулся к LDPC и забыл про блоковые турбо.

Если не изменяет память, то у меня на двумерном TPC (64,57)x(46,39) с декодированием по Чейзу (метод 2) получался энергетический выигрыш порядка 1,7 дБ при Pb=1e-6 по сравнению с синдромным декодером. Т.е. числа примерно одинаковые .

Это я не понял. Синдромный декодер - это просто "жесткий" декодер? Ну, тогда вполне правдоподобно. Хоть мне и казалось,
что выигрыш мягкого декодера над жестким в итеративной конструкции должен быть бльше 2-х дБ.

Какие числа? Я опять не понял. Если Вы о разнице между мягким и жестким
декодером, то 1,7 дБ на мой взгляд очень заметная разница
Если Вы о том, что у меня результаты были похожи на Ваши, то тут у нас ничего похожего быть не может,
т.к. кодовые скорости сильно разные.
Мне кажется, мы уже вышли за пределы исходного топика. Если Вам интересно, можем продолжить в личке.

Да, синдромный декодер - это жесткий декодер, относительно него у меня и получался выигрыш в 1,7 дБ, а 2 - это среднестатистический показатель, на который примерно и равняются при переходе на мягкую схему декодирования. коме того, здесь надо учитывать еще и вопросы реализации, т.е. насколько правильно и полно был реализован алгоритм декодирования, какова использовалась разрядность квантователя, ну и т.д.


Наверное, я тоже ничего не понял. Выигрыш в 1,8 дБ - это энергетический выигрыш относительно чего?

Это не выигрыш - я ничего такого не писал!
Это отношение сигнал/шум на бит в канале, при котором на выходе декодера
вероятность ошибки в символе порядка 10^-6.

Такого вообще быть не может. Ваш код имеет относительную скорость кодирования примерно 0,5 и Вы хотите сказать, что указанный Вами алгоритм может обеспечить битовую ошибку 1e-6 при соотношении С/Ш на входе декодера 1,8 дБ. Это нереально реализовать даже с применением MAPа. На вскидку могу сказать, что при такой битовой ошибке и скорости кодирования с использованием MAPа, вашему декодеру потребуется как минимум 2,5 дБ на входе. А упомянутый Вами алгоритм потребует еще дополнительной энергетики на входе для достижения требуемой битовой ошибки (т.к. он не оптимален в смысле минимума ошибки на бит и проигрывает тем самым MAPу), т.е. подводя итог с учетом дополнительных потерь на реализацию, на входе должно быть соотношение С/Ш никак не меньше 3,5 дБ. а Вы говорите про 1,8 дБ. Не стыковочка

2 SKov

Только что посмотрел спецификацию на турбокоды произведения для модемов Comtech. Так вот указанный Вами турбокод обеспечивает вероятность битовой ошибки 1e-6 при соотношении С/Ш=2,9 дБ. И это при условии, что потери при реализации декодера ничтожно малы и используется MAP. Так что Ваши данные неверны.

Указанный мною алгоритм относился к декодированию одного кода Хемминга.
Из этих кодов строилась итеративная конструкция. Кажнтся, трехмерная. Для нее я и приводил результаты.
Просто голый код Хемминга никому не интересен.
Конечно, я могу и ошибаться. На пару десятых дБ. Но не на пару дБ ))
Уважаемый Serg76! Вы меня заставляете тратить время на копание в работах 15-летней давности,
которые кроме вас уже никому не интересны..
Ну вот,я нашел свои бумажки. Написано: на выходе 10^-5 при входе 1.8..2.0 дБ. Код трехмерный (16*16*16,11*11*11,4*4*4).
Со скоростью около 0.3
Смотрю чужие результаты моделирования той же конструкции. Написано: на выходе 10^-5 при входе 1.5 дБ.
Это все написано в сборнике тезисов докладов "Seventh joint Swedish-Russian international workshop on infomation theory", 1995, St.Petersburg,Russia.
Кстати, нашлась полезная ссылка: J.Snyders. Reduсed lists of error patterns for maximum likelihood soft
decoding. IEEE Trans.Inform.Theory. , vol. IT-37,pp 1194-1200, 1991.
Насколько я помню, именно такая конструкция(из расширенных кодов Хемминга) рассматривалась в работе Хагенауэра в IT в
95-м или 96-м году, там приводились аналогичные результаты, что и послужило главной причиной забрасывания
мной этой темы. Найдите работу Хагенауэра(Hagenauer) - там наверняка есть моделирование.

Я давно не смотрел блоковые турбо-коды. Но вообще цифры вполне реальные.
Вот перед глазами характеристики (из статей в IT) сравнимых низкоплотностных.
У них 10^-5 достигается на отношении сигнал/шум около 1.6 (для длины 4000 и скорости1/2) или около 1.4дБ (для длины 8000 и скорости1/2)
Так что характеристики в пределах 2дБ вполне реальны и не являются чем-то выдающимся даже для скорости 1/2.

подождите, давайте по порядку:
1. Речь шла о двумерном турбокоде, в качестве компонентных которого использовались расширенные коды Хемминга (16,11). При такой конструкции относительная скорость кодирования составляет 0,47. Вы по-внимательнее почитайте, что Вы писали выше:

".... Вроде произведение двух кодов (16,11,4) давало порядка 10^-6 при порядка 1.8 дБ Eb|N0."

2. Во-вторых, речь шла о битовой ошибке 1е-6, а не 1е-5, как Вы говорите сейчас. согласитесь, разница существенная, на целый порядок.
Из этого всего следует, что для такой двумерной конструкции для получения битовой ошибки 1е-6 необходимо соотношение С/Ш=2.9 дБ, но никак не 1,8 дБ. Я на этих турбокодах, можно сказать, собаку съел, и не одну . И поэтому боролся за каждую долю децибелла. Так, что в этих характеристиках немного понимаю



Уважаемый SKov! Странный спич, но по-моему, Вы находитесь на форуме, где принято общаться, и, соответственно, тратить свое время. Пожалуйста, не расходуйте Ваше драгоценное время. Если Вам это уже не интересно, то зачем по-просту сотрясать воздух. Но инициатива исходила с Вашей стороны, поэтому я не понимаю Ваших упреков А работы эти в настоящее время очень интересны и продолжают развиваться.



Эти результаты уже ближе к действительности. Но опять же хочу Вас спросить: какой алгоритм декодирования использовался? Завтра я промоделирую этот трехмерный турбокод и сравню результаты с приведенными Вами.


Спасибо, в качестве встречного предложения могу порекомендовать ознакомиться с результатами, полученными фирмой AHA (сейчас их поглотила Comtech), которая является законодателем моды в области турбокодов. И, таким образом, эти результаты могут служить неким эталоном.


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

Сообщение отредактировал Serg76 - Jan 16 2011, 14:51

да, согласен. На два дБ я ошибиться не мог, а вот на единицу в размерности кода - запросто.
Причем, я так и написал - Вроде произведение двух кодов.... Т.е. я был не уверен.
И мое время не стоило того, чтобы это точно вспоминать. Но у меня не было выбора, т.к. Вы меня совсем закритиковали
Поэтому я так и написал про потраченное время. На будущее буду устойчивее к провокациям

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