Код Голея в APCO-25, Проблема декодирования Опции

[Pavel_I]

В стандарте цифровой радиосвязи APCO-25 используется расширенный код Галея (24, 12) со следующей генераторной матрицей:

Код

Oct                  Bin

4000     6165     100000000000  110001110101
2000     3073     010000000000  011000111011
1000     7550     001000000000  111101101000
400     3664     000100000000  011110110100
200     1732     000010000000  001111011010
100     6631     000001000000  110110011001
40          3315     000000100000  011011001101
20          1547     000000010000  001101100111
10          6706     000000001000  110111000110
4            5227     000000000100  101010010111
2            4476     000000000010  100100111110
1            4353     000000000001  100011101011

С помощью этой же матрицы можно получить стандартный код Голея (23, 12) (порождающий полином x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1 или 0xC75) путем отбрасывания наименее значимого бита контроля четности. Это проверено и работает.


В литературе по помехоустойчивому кодированию приводятся генераторные матрицы для кода Голея (24, 12), которые выглядят иначе (после отбрасывания единичной матрицы) – они симметричны относительно главной диагонали, строки матрицы циклически сдвинуты друг относительно друга. На основе симметричности строится алгоритм арифметического декодирования.

Приведенная выше матрица не обладает описанными свойствами.

Непонятно:
- каким образом она могла быть получена.
- как из нее получается циклический код (23, 12), хотя строки не цикличны.
- как декодировать расширенный код (24, 12) (таблица из синдромов не устраивает)

[Serg76]

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

[SKov]

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

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

[Serg76]

Т.е. вообще говоря, их всегда 2^r, но некоторые вектора ошибок заведомо менее вероятны, чем другие с таким же синдромом, поэтому их можно не рассматривать. Часто оказывается, что надо проанализировать совсем мало векторов ошибок.

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

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

[SKov]

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

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

[Serg76]

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

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

[SKov]

А Вы не снимали кривую помехоустойчивости Вашего декодера?

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

А реализация TPC декодера у Вас программная или аппаратная? Если программная, то каких символьных скоростей удалось достигнуть?

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

[Serg76]

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


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

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

[SKov]

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

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

Т.е. числа примерно одинаковые .

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

[Serg76]

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

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

Какие числа? Я опять не понял.

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

[SKov]

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

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

[Serg76]

Это не выигрыш - я ничего такого не писал!
Это отношение сигнал/шум на бит в канале, при котором на выходе декодера
вероятность ошибки в символе порядка 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. Так что Ваши данные неверны.

[SKov]

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

Указанный мною алгоритм относился к декодированию одного кода Хемминга.
Из этих кодов строилась итеративная конструкция. Кажнтся, трехмерная. Для нее я и приводил результаты.
Просто голый код Хемминга никому не интересен.
Конечно, я могу и ошибаться. На пару десятых дБ. Но не на пару дБ ))
Уважаемый 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) - там наверняка есть моделирование.

должно быть соотношение С/Ш никак не меньше 3,5 дБ. а Вы говорите про 1,8 дБ. Не стыковочка

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

[Serg76]

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

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

Уважаемый Serg76! Вы меня заставляете тратить время на копание в работах 15-летней давности,
которые кроме вас уже никому не интересны..

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

Ну вот,я нашел свои бумажки. Написано: на выходе 10^-5 при входе 1.8..2.0 дБ. Код трехмерный (16*16*16,11*11*11,4*4*4).
Со скоростью около 0.3
Смотрю чужие результаты моделирования той же конструкции. Написано: на выходе 10^-5 при входе 1.5 дБ.

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

Найдите работу Хагенауэра(Hagenauer) - там наверняка есть моделирование.

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

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

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

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