Перейти к содержанию
    

Вопросы по итеративному декодированию

В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном).

Глубоко копаешь ;) .

Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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, то придем в нулевое состояние, если выколота была единица, то получим состояние, равное выколотому столбцу проверочной матрицы. Других вариантов нет. Именно про такую решетку пишут в статье.

 

Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается...

 

Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже.

 

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

 

Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...

 

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

Изменено пользователем andyp

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Глубоко копаешь ;) .

Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

спасибо за объяснение... :a14:

тогда и махlog-map тоже не подходит.

 

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)

Длинные эти коды или нет я не знаю :)

Интересуют именно алгоритмы мягкого декодирования

Момент итеративности(количества итераций) сейчас можно пока опустить...

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

спасибо за объяснение... :a14:

тогда и махlog-map тоже не подходит.

 

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)

Длинные эти коды или нет я не знаю :)

Интересуют именно алгоритмы мягкого декодирования

Момент итеративности(количества итераций) сейчас можно пока опустить...

 

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

 

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

 

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

 

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

совершенно верно

спасибо...

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

Алгоритм же остается тот же...

 

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

 

 

Все равно я не понимаю как достигаются такие высокие скорости у AHA декодирования

- 311 Mbits/sec TPC Encoder/Decoder IC

КАК???

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

совершенно верно

спасибо...

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

Алгоритм же остается тот же...

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

да, тогда алгоритм Чейза не подходит...

из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... :(

а другого алгоритма я не знаю....

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

да, тогда алгоритм Чейза не подходит...

из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... :(

а другого алгоритма я не знаю....

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

погорячился...

попробую посмотреть в сторону мажоритарного декодера...

ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте :(

Вот это читаю...

 

На 3 странице

 

MAP (maximum-a-posteriori) и его аппроксимации LOG-MAP и MAX-LOG-MAP. AHA так и делает (например, чип AHA4540)

 

вопрос как?

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

погорячился...

попробую посмотреть в сторону мажоритарного декодера...

ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте :(

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

знаю, прежде чем попросить проверил ...

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

Four-SISO option achieves a data rate of 155 Mbps with five iterations using (64,57)^2 code

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...