andyp 10 28 декабря, 2014 Опубликовано 28 декабря, 2014 (изменено) · Жалоба В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 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. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной. Изменено 28 декабря, 2014 пользователем andyp Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба Глубоко копаешь ;) . Сам метод построения решетки блочного кода по проверочной матрице описан в книжке 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 тоже не подходит. А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 10 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы? Для длинных кодовых блоков и скорости, близкой к 1/2? Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба Для длинных кодовых блоков и скорости, близкой к 1/2? Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался. Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64) Длинные эти коды или нет я не знаю :) Интересуют именно алгоритмы мягкого декодирования Момент итеративности(количества итераций) сейчас можно пока опустить... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Serg76 0 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба спасибо за объяснение... :a14: тогда и махlog-map тоже не подходит. А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы? при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [128x128], результат получается даже на уровне AHA, можно и другие алгоритмы попробовать, как-то уже с Вами обсуждали здесь, даже кое-что высылал. посмотрите в сторону мажоритарного декодера, для расширенных кодов Хемминга, о которых, как я понимаю, идет речь, сложность реализации будет невелика (для этих кодов каждый бит может быть представлен 4-мя уравнениями), а эффективность будет находиться где-то на уровне Чейза. к уже упомянутым алгоритмам можно еще добавить семейство вероятностных алгоритмов BPA (Belief Propagation Algorithm) или SPA (SumProduct Algorithm) алгоритмов и их аппроксимации на основе все той же алгебры логарифмов правдоподобия, но опять же, сложность реализации будет на уровне MAPa. а MAP, как правильно сказали, будет тяжеловат для кодов типа [128x128], хотя для [64x64] еще приемлемо. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 10 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба Да, для блоковых кодов до (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, но все они зависят от структуры кода. Наверное, я не про то пишу и все-таки и не понимаю вопроса. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Serg76 0 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код? По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 10 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120) Тогда мой ответ про Хемминга релевантен. Для MAP декодирования наибольшую проблему составляет скорость ~1/2 - наиболее сложная решетка. Да и для Чейза сложность с ростом кодового расстояния увеличится. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120) совершенно верно спасибо... Просто я думал вначале сделать декодирование блока например (128*120), а потом уже перенести на 2D/3D TPC код. Алгоритм же остается тот же... andyp спасибо за помощь Все равно я не понимаю как достигаются такие высокие скорости у AHA декодирования - 311 Mbits/sec TPC Encoder/Decoder IC КАК??? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Serg76 0 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба совершенно верно спасибо... Просто я думал вначале сделать декодирование блока например (128*120), а потом уже перенести на 2D/3D TPC код. Алгоритм же остается тот же... естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход ) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба естественно, за исключением того, что кроме мягкого входа еще нужен будет и мягкий выход ) да, тогда алгоритм Чейза не подходит... из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... :( а другого алгоритма я не знаю.... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Serg76 0 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба да, тогда алгоритм Чейза не подходит... из-за этого начал смотреть на max log-map алгоритм, но и с ним возникли проблемы... :( а другого алгоритма я не знаю.... с чего Вы это взяли? все алгоритмы, о которых я упоминал способны генерировать мягкий выход Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба при правильном подходе Чейз дает весьма неплохие результаты даже для кодов типа [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) очень большое получается - как обойти этот момент? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Serg76 0 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба погорячился... попробую посмотреть в сторону мажоритарного декодера... ЗЫ Просьба если не затруднит вышлите мне еще раз - не могу найти у себя на винте :( ссылка мертвая :(, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Maverick_ 15 29 декабря, 2014 Опубликовано 29 декабря, 2014 · Жалоба ссылка мертвая :(, уже не помню, что я там выкладывал, надо собирать заново, пока можно спросить у des00, ему тоже высылал знаю, прежде чем попросить проверил ... И все равно я не понимаю как сделано тут , чтобы достичь таких высоких скоростей обработки и повторить такое... Four-SISO option achieves a data rate of 155 Mbps with five iterations using (64,57)^2 code Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
