Глубоко копаешь .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке Lin Costello Error Control Coding Fundamentals and Applications (только 2е издание). Скачать ее можно здесь
http://bookzz.org/md5/8032998F071B09E087B9E8D81E7FFC1F
Тебе потребуется глава 9, а именно секция 9.5. Но хочу предупредить сразу - чтение не из легких.
Если кратко, получается, что код представляется (n+1)-секционной решеткой, метки ветвей соответствуют закодированным битам, метки состояний - линейная комбинация столбцов проверочной матрицы и кодовых бит, по которым пришли в это состояние. Очевидно, что n-ое состояние решетки будет единственным и будет состоять из (n-k) нулей по свойству проверочной матрицы. 0-е состояние - тоже 0. Из него начинаем.

Идем дальше. Рассмотрим кодовые слова кода, из которых вырезали к-ий бит. Предположим, что они все у нас есть (так проще) и будем строить решетку для них по тем же правилам, используя все столбцы проверочной матрицы оригинального кода, кроме к-го. В результате получим n-секционную решетку, начинающуюся в 0, и имеющую два хвоста. Почему хвостов 2? Да потому, что если в невыколотом кодовом слове в к-ой позиции был 0, то придем в нулевое состояние, если выколота была единица, то получим состояние, равное выколотому столбцу проверочной матрицы. Других вариантов нет. Именно про такую решетку пишут в статье.



Именно поэтому чистый MAP для длинных блочных кодов не используется. Структура решетки не позволяет.



В книжке есть секция 10, написанная проф. Fossorier. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

Сообщение отредактировал andyp - Dec 28 2014, 23:39

спасибо за объяснение...
тогда и махlog-map тоже не подходит.

А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?

Для длинных кодовых блоков и скорости, близкой к 1/2?

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)
Длинные эти коды или нет я не знаю
Интересуют именно алгоритмы мягкого декодирования
Момент итеративности(количества итераций) сейчас можно пока опустить...

при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо.

Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

Сложность алгоритма Чейза 2 растет (ну и всех основанных на нем алгоритмов SISO) экспоненциально от d/2. Если у тебя например 128-битный код Хамминга, то у него d=3 и декодировать его - плевое дело. Если будешь его декодировать по решетке, то в каждой секции будет не больше 2^7 состояний (количество состояний в решетке будет пропорционально 2^(n-k) или 2^k, смотря что меньше), так что MAP декодирование для составных кодов, остнованных на кодах Хемминга, опять же возможно для широкого диапазона битовых скоростей.

Есть еще всякие алгоритмы типа recursive MLD и итеративное декодирование по minimum weight subtrellis, но все они зависят от структуры кода.

Наверное, я не про то пишу и все-таки и не понимаю вопроса.

По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)

Тогда мой ответ про Хемминга релевантен. Для MAP декодирования наибольшую проблему составляет скорость ~1/2 - наиболее сложная решетка. Да и для Чейза сложность с ростом кодового расстояния увеличится.

совершенно верно
спасибо...
Просто я думал вначале сделать декодирование блока например (128*120), а потом уже перенести на 2D/3D TPC код.
Алгоритм же остается тот же...

andyp спасибо за помощь


Все равно я не понимаю как достигаются такие высокие скорости у AHA декодирования
- 311 Mbits/sec TPC Encoder/Decoder IC
КАК???

естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход )

да, тогда алгоритм Чейза не подходит...
из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы...
а другого алгоритма я не знаю....

с чего Вы это взяли? все алгоритмы, о которых я упоминал способны генерировать мягкий выход

погорячился...
попробую посмотреть в сторону мажоритарного декодера...
ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте
Вот это читаю...

На 3 странице



вопрос как?

количество метрик для (128*120) очень большое получается - как обойти этот момент?

ссылка мертвая , уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал

знаю, прежде чем попросить проверил ...
И все равно я не понимаю как сделано тут , чтобы достичь таких высоких скоростей обработки и повторить такое...