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




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


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

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

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

декодируйте алгоритмами с мягким решением (например, Чейза или оптимального посимвольного декодирования)

Благодарю за совет. Но надеялся на более простой алгоритм. Модем выдает жесткие решения.

А почему?
Самое простое решение... Всего 4к 24-битных векторов ошибок

В DSP крутится еще модем, вокодер, другие кодеры/декодеры и пр. В нем и так все под завязку.
Хотелось бы обойтись без таблиц и сохранить место на будущее.

to Pavel_I,
насколько я помню как раз для расширенного кода Голея есть так называемый алгоритм алгебраического декодирования. Помню, что натыкалась на это в литературе. Если этот вопрос всё ещё интересует, могу в книжках поискать, где я это встречала, и Вам сообщить.
to Serg76,
А каким образом при декодировании с помощью алгоритма Чейза может не понадобиться таблица синдромов? Насколько я понимаю, генерируются пробные ошибочные векторы, которые добавляются к исходному жёстко декодированному вектору с помощью таблицы синдромов. Ну и потом расстояние считается уже. Поясните, пожалуйста, как синдромов можно избежать?

Сообщение отредактировал натошка - Jan 13 2011, 14:45

А Вы почитайте повнимательнее суть методов декодирования по алгоритму Чейза. Синдромов избежать нельзя, но для алгоритма Чейза (метод 2 и 3) не надо хранить всю таблицу синдромов. Достаточно хранить проверочную матрицу и уже на ее основе вычислять массив синдромов для всего семейства пробно сгенерированных ошибочных векторов. Их количество будет значительно меньше чем в методе 1, где как раз и надо проверять все комбинации ошибок на расстоянии не более (d-1) от принятого слова. Но большой необходимости в использовании метода 1 нет, так как он лишь незначительно (порядка 0,2 дБ) выигрывает в помехоустойчивости по сравнению с методом 2. А экономия в вычислительных ресурсах налицо. Метод 3 нет смысла тоже использовать, так как он уже сильно проигрывает методам 1 и 2.

Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Глава 2.2.3. Арифметическое декодирование расширенного (24,12,8) кода Голея


Я наверное что-то недопонимаю, но почему тогда такая схема(хранить проверочную матрицу и из неё получать по требованию вектор ошибки) не применяется при жёстком декодировании?

потому что после принятия жесткого решения демодулятором все биты имеют равновероятную оценку и декодер не может выделить среди них наименее (или наиболее) достоверные. мягкая схема принятия решения позволяет это сделать. поэтому при декодировании алгоритмом Чейза (метод 2) достаточно выделить наименее достоверные символы (в пределах корректирующей способности кода) и для них составить все возможные кодовые слова (их будет небольшое количество по сравнению с объемом сгенерированных кодовых слов по методу 1), затем вычислить для них синдром, и те кодовые слова, которые в результате будут давать нулевой синдром и будут правильными. если таких кодовых слов окажется несколько, то выбираем кодовое слово с минимальной эвклидовой метрикой. Алгоритм Чейза сродни алгоритму максимального правдоподобия Витерби и дает минимальную вероятность битовой ошибки для кодового слова.

Дело в том, что порождающая матрица, приведенная мной выше, непохожа на матрицы для (24,12) кода Голея, имеющиеся в литературе.
Порождающая матрица должна иметь подматрицу B такую, что B=B^T
Арифметическое декодирование основанно именно на этом свойстве.

1) Есть только один код Голея. Все варианты коды Голея эквивалентны, т.е. любую другую матрицу можно получить из любой методом перестановки строк и столбцов. Если вы хотите прийти к другой матрице - найдите эти перестановки.
2) Почитал Сарагосу. Паренек называет арифметическим декодированием известный сто лет метод декодирования по двум информационным совокупностям с покрывающими полиномами веса 1. Бог ему судья. Для этого метода не обязательно иметь B такую, что B=B^T. Достаточно самодуальности кода. Просто первую часть алгоритма надо делать , используя B , а вторую часть - по транспонированной B
3) Советую посмотреть в сторону метода вылавливания ошибок (Декодер Меггита).Для циклического кода самый простой вариант.
4) Разговор о Чейзе не имеет отношения к поставленному вопросу.

Если бы был мягкий выход, то почему бы и нет? Еще можно было бы использовать MAP, который является самым помехоустойчивым и дает минимум ошибки на символ. но необходимы достаточные вычислительные ресурсы

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

Я думал о перестановке строк и столбцов. Но что-то так с ходу не получилось.
А ведь еще можно суммировать строки.
К книжке Сарагосы имеются исходники. В том числе примеры кодирования-декодирования кодов Голея.
Так вот при кодировании расширенным Голеем у меня получается разный результат с теми примерами.
В тоже время, если из расширенного кода сделать обычный (23, 12), путем отбрасывания бита четности, то все сходится с Сарагосой.
Не пойму, где ошибаюсь.



В "Error Control Coding" Shu Lin, Daniel J. Costello арифмитическое декодирование выводится именно для самодуального кода с симметричной относительно главной диагонали подматрицы.
Но я подумаю над Вашим предложением.


Расширенный Голей (24,12) (а не (23,12)), насколько я понимаю, уже не является циклическим.

Это пофигу. Вы декодируете укороченный циклический вариант. Если получилось исправление 3 ошибок, то , возможно, было на самом деле 4. Это легко определить по четности или нечетности веса всего исходного расширенного слова с проверкой на четность.



Если бы был - тогда конечно. Но в вопросе шла речь об исправлении двоичных ошибок.
Кста, если уж декодировать Голея в полунепрерывном канале, то делать это лучше не по Чейзу,
а по Яше Снайдерсу (J.Snyders) с компанией. Они гарантируют максимум правдоподобия с относительно небольшой сложностью.
Были работы на эту тему в IEEE IT в середине 90-х.
А по Чейзу - субоптимальный алгоритм.

Максимум правдоподобия для каждого символа или кодового слова в целом?