Код Голея в 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 и забыл про блоковые турбо.