реклама на сайте
подробности

 
 
16 страниц V  < 1 2 3 4 > »   
Reply to this topicStart new topic
> Вопросы по итеративному декодированию, Реализация CTC/BTC/LDPC кодов
andyp
сообщение Dec 28 2014, 23:36
Сообщение #16


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Maverick @ Dec 28 2014, 23:26) *
В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном).

Глубоко копаешь wink.gif .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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 - Dec 28 2014, 23:39
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 09:48
Сообщение #17


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(andyp @ Dec 29 2014, 01:36) *
Глубоко копаешь wink.gif .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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.gif
тогда и махlog-map тоже не подходит.

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 10:13
Сообщение #18


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Maverick @ Dec 29 2014, 12:48) *
А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?


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

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 10:58
Сообщение #19


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(andyp @ Dec 29 2014, 12:13) *
Для длинных кодовых блоков и скорости, близкой к 1/2?

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

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 12:13
Сообщение #20


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(Maverick @ Dec 29 2014, 13:48) *
спасибо за объяснение... a14.gif
тогда и махlog-map тоже не подходит.

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

при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо.
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 13:02
Сообщение #21


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



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


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

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

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

Наверное, я не про то пишу и все-таки и не понимаю вопроса.
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 13:23
Сообщение #22


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(andyp @ Dec 29 2014, 17:02) *
Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)
Go to the top of the page
 
+Quote Post
andyp
сообщение Dec 29 2014, 13:55
Сообщение #23


Местный
***

Группа: Участник
Сообщений: 425
Регистрация: 23-07-08
Пользователь №: 39 163



Цитата(Serg76 @ Dec 29 2014, 16:23) *
По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)


Тогда мой ответ про Хемминга релевантен. Для MAP декодирования наибольшую проблему составляет скорость ~1/2 - наиболее сложная решетка. Да и для Чейза сложность с ростом кодового расстояния увеличится.
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 15:39
Сообщение #24


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 15:23) *
По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)

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

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


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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 16:28
Сообщение #25


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



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

естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход )
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 19:29
Сообщение #26


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 18:28) *
естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход )

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 20:53
Сообщение #27


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(Maverick @ Dec 29 2014, 23:29) *
да, тогда алгоритм Чейза не подходит...
из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... sad.gif
а другого алгоритма я не знаю....

с чего Вы это взяли? все алгоритмы, о которых я упоминал способны генерировать мягкий выход
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 21:40
Сообщение #28


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



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

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

На 3 странице

Цитата(Serg76 @ Jul 22 2010, 18:38) *
MAP (maximum-a-posteriori) и его аппроксимации LOG-MAP и MAX-LOG-MAP. AHA так и делает (например, чип AHA4540)


вопрос как?

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


--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post
Serg76
сообщение Dec 29 2014, 21:48
Сообщение #29


Профессионал
*****

Группа: Участник
Сообщений: 1 029
Регистрация: 4-04-07
Пользователь №: 26 775



Цитата(Maverick @ Dec 30 2014, 01:40) *
погорячился...
попробую посмотреть в сторону мажоритарного декодера...
ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте sad.gif

ссылка мертвая sad.gif, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал
Go to the top of the page
 
+Quote Post
Maverick
сообщение Dec 29 2014, 22:25
Сообщение #30


я только учусь...
******

Группа: Модераторы
Сообщений: 3 394
Регистрация: 29-01-07
Из: Украина
Пользователь №: 24 839



Цитата(Serg76 @ Dec 29 2014, 23:48) *
ссылка мертвая sad.gif, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал

знаю, прежде чем попросить проверил ...
И все равно я не понимаю как сделано тут , чтобы достичь таких высоких скоростей обработки и повторить такое...
Цитата
Four-SISO option achieves a data rate of 155 Mbps with five iterations using (64,57)^2 code




--------------------
If it doesn't work in simulation, it won't work on the board.

"Ты живешь в своих поступках, а не в теле. Ты — это твои действия, и нет другого тебя" Антуан де Сент-Экзюпери повесть "Маленький принц"
Go to the top of the page
 
+Quote Post

16 страниц V  < 1 2 3 4 > » 
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 23rd November 2017 - 05:12
Рейтинг@Mail.ru


Страница сгенерированна за 0.01361 секунд с 7
ELECTRONIX ©2004-2016