коды, исправляющие ошибки Опции

[mluk]

Всем здравствуйте.
Есть блок данных размером 8 байт. Кодовое слово состоит из 12 байт. Данные кодируются при помощи кода Рида-Соломона, реализованного в IP Core пакета Xilinx ISE. Этот кодер исправляет 2 байта из 12. Хотелось бы реализовать код с большей корректирующей способностью при той же длине кодового слова. К примеру код исправляющий те же 16 бит, но размазанных по всему пакету. Подскажите, кто знает.

[Methane]

Всем здравствуйте.
Есть блок данных размером 8 байт. Кодовое слово состоит из 12 байт. Данные кодируются при помощи кода Рида-Соломона, реализованного в IP Core пакета Xilinx ISE. Этот кодер исправляет 2 байта из 12. Хотелось бы реализовать код с большей корректирующей способностью при той же длине кодового слова. К примеру код исправляющий те же 16 бит, но размазанных по всему пакету. Подскажите, кто знает.

Перетасовать биты шоли?

[mluk]

нет, не перетасовать. Код исправляет 2 байта из 12 при 8 информационных. Есть ли возможность его улучшить. Например, исправляя 16 бит из 96 при 64 информационных.
Суть в том, что в первом случае алфавит кодирования состоит из 2^8 символов, есть ли возможность его уменьшить.

[des00]

нет, не перетасовать. Код исправляет 2 байта из 12 при 8 информационных. Есть ли возможность его улучшить. Например, исправляя 16 бит из 96 при 64 информационных.

перемежение и будут те же яйца только в профиль.

Суть в том, что в первом случае алфавит кодирования состоит из 2^8 символов, есть ли возможность его уменьшить.

при генерации корки указать размер символа меньше байта ?

[petrov]

Таких мощных как вы хотите нету или они неизвестны.

БЧХ(127,64) исправляет 10 ошибок, расположенных в любых местах, в кодовом слове из 127 бит при 64 бит данных.
Код Голея(23,12) исправляет 3 любых ошибки в кодовом слове из 23 бит при 12 бит данных.
Если известно расположение ошибок(так называемые стирания) то можно исправить вдвое больше.
Ещё больше можно исправить если мягкая информация доступна с выхода демодулятора.

[Serg76]

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

[MrYuran]

кроме того код даже с простой проверкой на четность способен исправить пакет ошибок.

???
Скорее, способен выявить некоторые ошибочные пакеты (но далеко не все)

[mluk]

перемежение и будут те же яйца только в профиль.

Перемежение - к сожалению не те же яйца. Оно даже может ухудшить рабоду кодера. Например байт с большим количеством ошибок "испортит" много других байт пакета.

при генерации корки указать размер символа меньше байта ?

при генерации корки минимальный размер символа 3 бита, но естественно чем меньше - тем лучше.
И еще вопрос: в Блейхуте рассматриваются коды Рида Соломона "мультипликативный порядок алфавита которых делится на длину кода". Каким образом может получаться код (12,8) с байтовым алфавитом (в корке этот код можно сгенерить).

Сообщение отредактировал mluk - Jun 8 2010, 05:45

[Methane]

Перемежение - к сожалению не те же яйца. Оно даже может ухудшить рабоду кодера. Например байт с большим количеством ошибок "испортит" много других байт пакета.

От распределения шума зависит. Так либо будет несправимая ошибка, либо просто исправимая, но не в одном а в нескольких байтах.

[MrYuran]

Перемежение - к сожалению не те же яйца. Оно даже может ухудшить рабоду кодера. Например байт с большим количеством ошибок "испортит" много других байт пакета.

Для начала определитесь с характером ошибок и вообще с требованиями.
При увеличении длины пакета резко возрастает сложность кодека. Если для байта можно просто тупо таблицу забить, то для больших пакетов применяются сложные алгоритмы. Скремблирование применяется, если ошибки вываливаются редкими пачками (например, при чтении компактного диска или при мощных импульсных помехах на линии).

[mluk]

Для начала определитесь с характером ошибок и вообще с требованиями.
При увеличении длины пакета резко возрастает сложность кодека. Если для байта можно просто тупо таблицу забить, то для больших пакетов применяются сложные алгоритмы. Скремблирование применяется, если ошибки вываливаются редкими пачками (например, при чтении компактного диска или при мощных импульсных помехах на линии).

Сформулирую вопрос так: пакет состоит из 96 бит, информационных 64, ошибки случайным образом (с гауссовым распределением) встречаются по всей длине пакета. Какое кодирование в такой ситуации может быть оптимальным.

Сообщение отредактировал mluk - Jun 8 2010, 06:17

[Serg76]

???
Скорее, способен выявить некоторые ошибочные пакеты (но далеко не все)

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

[SKov]

Сформулирую вопрос так: пакет состоит из 96 бит, информационных 64, ошибки случайным образом (с гауссовым распределением) встречаются по всей длине пакета. Какое кодирование в такой ситуации может быть оптимальным.

Все просто. У Вас двоичный код длины 96 и избыточностью 32. По таблице лучших кодов определяем, что
наилучший код с такими параметрами исправляет 4 ошибки. Кстати, укороченный БЧХ код над GF(2^7)
тоже имеет такую же корректирующую способность, так что нет смысла городить огород. Берете БЧХ код,
алгоритм Берлекэмпа - и с песнями вперед!

[mluk]

Все просто. У Вас двоичный код длины 96 и избыточностью 32. По таблице лучших кодов определяем, что
наилучший код с такими параметрами исправляет 4 ошибки. Кстати, укороченный БЧХ код над GF(2^7)
тоже имеет такую же корректирующую способность, так что нет смысла городить огород. Берете БЧХ код,
алгоритм Берлекэмпа - и с песнями вперед!

Большое спасибо за совет, но как я понимаю укороченный БЧХ код над GF(2^7) код будет исправлять "недобайты" - последовательности из 7 бит и уж лучше сохранить укороченный код Рида соломона имеющийся в корке. Не подскажете, что за таблица лучших кодов, и где ее посмотреть.

[SKov]

Большое спасибо за совет, но как я понимаю укороченный БЧХ код над GF(2^7) код будет исправлять "недобайты" - последовательности из 7 бит и уж лучше сохранить укороченный код Рида соломона имеющийся в корке. Не подскажете, что за таблица лучших кодов, и где ее посмотреть.

Нет, Вы неправильно понимаете, "недобайты" Вы исправлять не сможете. Или я Вас неправильно понял. Вы писали о том, что хотите исправлять любые ошибки, и желательно никак не привязанные к границам байтов. Например, ваш РС код заткнется и на 3-х одиночных ошибках, если они лягут в три разных байта.
Для исправления независимых (непакетных) ошибок код РС подходит плохо. Как видите, можно исправлять одиночные ошибки в 4-х разных байтах и вообще в любых местах кодового слова. Как это делать - я Вам и написал. Но оказалось, что Вы хотите исправлять и как код PC и как двоичный код ВЧХ. На этот счет есть одна известная русская пословица, смысл который сводится к тому, что так не бывает.
С таблицей наилучших кодов все сложно. Свежие таблицы мне не известны.
Была хорошая таблица в книжке Теория кодов, исправляющих ошибки,
авторы: Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А.
Она есть в И-нете.
Но она (таблица, не книга) сильно устарела. Попробуйте поискать такой препринт:
Зиновьев В. А., Лицын С. Н. Таблица наилучших известных двоичных кодов: Препринт. М.: ИППИ АН СССР. 1984.
Эта таблица тоже немножко устарела, но не слишком
Кроме того, в этих таблицах указаны любые коды, в том числе и нелинейные, в том числе и с очень хитроумными (сложными) алгоритмами построения (и декодирования), так что практическое использование этих лучших кодов может быть не так просто.

[mluk]

Нет, Вы неправильно понимаете, "недобайты" Вы исправлять не сможете. Или я Вас неправильно понял. Вы писали о том, что хотите исправлять любые ошибки, и желательно никак не привязанные к границам байтов. Например, ваш РС код заткнется и на 3-х одиночных ошибках, если они лягут в три разных байта.
Для исправления независимых (непакетных) ошибок код РС подходит плохо. Как видите, можно исправлять одиночные ошибки в 4-х разных байтах и вообще в любых местах кодового слова. Как это делать - я Вам и написал. Но оказалось, что Вы хотите исправлять и как код PC и как двоичный код ВЧХ. На этот счет есть одна известная русская пословица, смысл который сводится к тому, что так не бывает.
С таблицей наилучших кодов все сложно. Свежие таблицы мне не известны.
Была хорошая таблица в книжке Теория кодов, исправляющих ошибки,
авторы: Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А.
Она есть в И-нете.
Но она (таблица, не книга) сильно устарела. Попробуйте поискать такой препринт:
Зиновьев В. А., Лицын С. Н. Таблица наилучших известных двоичных кодов: Препринт. М.: ИППИ АН СССР. 1984.
Эта таблица тоже немножко устарела, но не слишком
Кроме того, в этих таблицах указаны любые коды, в том числе и нелинейные, в том числе и с очень хитроумными (сложными) алгоритмами построения (и декодирования), так что практическое использование этих лучших кодов может быть не так просто.

Что Вы имеете ввиду под словами бчх код над GF(2^7):

[SKov]

Что Вы имеете ввиду под словами бчх код над GF(2^7):

Наберите в Гугле "БЧХ код" и почитайте в Википедии, что я имею в виду.
Мне кажется, Вы путаете код Рида Соломона, например
в вашем случае - над GF(256) и двоичный БЧХ код, например над GF(2^8).
GF(256) и GF(2^8) - это не совсем одно и то же

[mluk]

Наберите в Гугле "БЧХ код" и почитайте в Википедии, что я имею в виду.
Мне кажется, Вы путаете код Рида Соломона, например
в вашем случае - над GF(256) и двоичный БЧХ код, например над GF(2^8).
GF(256) и GF(2^8) - это не совсем одно и то же

Я прекрасно понимаю, что вы имеете в виду. По Вашему совету посмотрел в гугле и википедии, однако не нашел различия между бчх над GF(256) и над над GF(2^8).
Есть некоторое поле галуа НАД которым строится код. Корни порождающего многочлена лежат в его расширении

[SKov]

Я прекрасно понимаю, что вы имеете в виду. По Вашему совету посмотрел в гугле и википедии, однако не нашел различия между бчх над GF(256) и над над GF(2^8).
Есть некоторое поле галуа НАД которым строится код. Корни порождающего многочлена лежат в его расширении

Разница в символах кода и кодовых параметрах (длина, число инф. символов, мин. расстояние).
Грубо говоря, кодовыми словами над полем GF(2^8) являются многочлены с двоичными коэффициентами из GF(2),
а кодовыми словами над полем GF(256) являются многочлены с коэффициентами из GF(256).
В поле GF(2^8) символом кода является элемент поля GF(2). Соответственно вычисляются кодовая длина в битах, и грубая оценка на число исправляемых ошибок(в двоичных символах кода) = число проверочных символов, деленных на 8(для GF(2^8)).
В поле GF(256) символом кода является элемент поля GF(256), т.е. байт. Соответственно ошибка в символе - это любая ошибка в пределах байта, и один оскаженный бит в байте это одна ошибка, и все 8 бит искажены в байте - это тоже одна ошибка в одном символе кода. И кодовая длина уже может быть другая(например, если считать ее в байтах - то 256 символов, а если в битах - то 256*8), и точная оценка на число исправляемых ошибок = число проверочных символов(байтов)/2.
Так что разница в полях, может, и небольшая, а вот разница в параметрах кодов над этими полями уже существенна.

[mluk]

Разница в символах кода и кодовых параметрах (длина, число инф. символов, мин. расстояние).
Грубо говоря, кодовыми словами над полем GF(2^8) являются многочлены с двоичными коэффициентами из GF(2),
а кодовыми словами над полем GF(256) являются многочлены с коэффициентами из GF(256).
В поле GF(2^8) символом кода является элемент поля GF(2). Соответственно вычисляются кодовая длина в битах, и грубая оценка на число исправляемых ошибок(в двоичных символах кода) = число проверочных символов, деленных на 8(для GF(2^8)).
В поле GF(256) символом кода является элемент поля GF(256), т.е. байт. Соответственно ошибка в символе - это любая ошибка в пределах байта, и один оскаженный бит в байте это одна ошибка, и все 8 бит искажены в байте - это тоже одна ошибка в одном символе кода. И кодовая длина уже может быть другая(например, если считать ее в байтах - то 256 символов, а если в битах - то 256*8), и точная оценка на число исправляемых ошибок = число проверочных символов(байтов)/2.
Так что разница в полях, может, и небольшая, а вот разница в параметрах кодов над этими полями уже существенна.

Это все понятно, я Вас просил уточнить, что вы имеете ввиду под "бчх над GF(2^8)", чтобы не было недоразумений. Как таковая эта запись не означает, что алфавит кодирования бинарен, а поле разложения порождающего многочлена есть GF(2^8).

[SKov]

Это все понятно, я Вас просил уточнить, что вы имеете ввиду под "бчх над GF(2^8)", чтобы не было недоразумений. Как таковая эта запись не означает, что алфавит кодирования бинарен...

Я как раз именно такой смыл вкладывал в эту запись.
Обычно так и пишут: GF(алфавит кода ^ расширение поля алфавита).
Ведь запись GF(256) совсем не обязательно означает, что речь идет о байтах
Это просто поле из 256 элементов (корова, яблоко, морковка...), для которых заданы таблицы
сложения и умножения и выполняются аксиомы поля. Просто удобно вместо коров и морковки использовать байты, тем более, что таблица сложения совпадает с операцией XOR для байтов. А могла бы и не совпадать
Аналогично для GF(2^8). Есть исходное поле из двух элементов (корова, яблоко), которые удобно представлять в виде 0 и 1. И есть расширение этого поля (вектора, элементы которых состоят из коров или морковок).
Ну, это я пожалуй совсем уж все упростил для детского сада. Извиняюсь

[mluk]

Я как раз именно такой смыл вкладывал в эту запись.
Обычно так и пишут: GF(алфавит кода ^ расширение поля алфавита).
Ведь запись GF(256) совсем не обязательно означает, что речь идет о байтах
Это просто поле из 256 элементов (корова, яблоко, морковка...), для которых заданы таблицы
сложения и умножения и выполняются аксиомы поля. Просто удобно вместо коров и морковки использовать байты, тем более, что таблица сложения совпадает с операцией XOR для байтов. А могла бы и не совпадать
Аналогично для GF(2^8). Есть исходное поле из двух элементов (корова, яблоко), которые удобно представлять в виде 0 и 1. И есть расширение этого поля (вектора, элементы которых состоят из коров или морковок).
Ну, это я пожалуй совсем уж все упростил для детского сада. Извиняюсь

Большое спасибо за подробное объяснение столь нетривиальных вещей. Думаю мы поняли друг друга

[mluk]

Уважаемый SKov, не могли бы Вы поделиться одной из таблиц оптимальных кодов, если они у Вас имеются.

[SKov]

Уважаемый SKov, не могли бы Вы поделиться одной из таблиц оптимальных кодов, если они у Вас имеются.

Если можно, завтра сделаю. Надо сканер доставать и подключать - сегодня нет времени.
И еще есть маленькая надежда, что один из авторов последней таблицы пришлет
мне какой-то электронный свежий вариант таблицы - я отослал такую просьбу
Подождем до завтра.

[mluk]

Большое спасибо

[SKov]

Большое спасибо

На здоровье
http://www.eng.tau.ac.il/~litsyn/tableand/index.html

[mluk]

На здоровье
http://www.eng.tau.ac.il/~litsyn/tableand/index.html

Спасибо)

[mluk]

Не подскажете, как этой таблицей пользоваться. Не очень понимаю

[SKov]

Не подскажете, как этой таблицей пользоваться. Не очень понимаю

Там перед таблицами все написано. Слова хоть и английские, но пикселы все наши, русские
Задайте более конкретный вопрос - поясню.

[mluk]

Что есть алфавит кодирования и количество исправляемых ошибок.

[SKov]

Что есть алфавит кодирования и количество исправляемых ошибок.

Обычно под алфавитом понимается количество различных символов кода. В этих таблицах все коды двоичные.
А количество исправляемых ошибок - это... количество исправляемых ошибок! Не знаю, как это можно сказать понятнее.
Если можно, приведите английские фразы из ссылки, которые вызвали у Вас эти вопросы.

[mluk]

Скажем так, есть ли возможность найти по таблице укороченный код рида соломона изправляющий 2 байта из 12 при 8 информационных. Как это сделать

[petrov]

Скажем так, есть ли возможность найти по таблице укороченный код рида соломона изправляющий 2 байта из 12 при 8 информационных. Как это сделать

Нету там хорошего кода 96,64.
Берите таблицу бинарных БЧХ кодов и выбирайте подходящий, только вам придётся изменить длину блока.

[mluk]

я не понял как таблицей пользоваться и совета прошу. Был бы благодарен если бы вы описали алгоритм поиска любого выбранного Вами кода по какой нибудь из приведенных там таблиц.

[SKov]

Скажем так, есть ли возможность найти по таблице укороченный код рида соломона изправляющий 2 байта из 12 при 8 информационных. Как это сделать

Не понял. Причем здесь РС-коды? Они же не двоичные. Их, конечно, можно рассматривать как двоичные,
но двоичное минимальное расстояние у них плохое. Что-то около 5. Вместо 9 у эквивалентного по длине и скорости двоичного кода.
Мы это обсуждали выше.

[petrov]

я не понял как таблицей пользоваться и совета прошу. Был бы благодарен если бы вы описали алгоритм поиска любого выбранного Вами кода по какой нибудь из приведенных там таблиц.

n - длина блока
(d-1)/2 количество ошибок исправляемых
k - количество бит информационных

В тех таблицах есть очень хорошие коды, но скорее всего их не так то просто будет сделать, в указанных статьях может не быть практического алгоритма декодирования. БЧХ же коды вдоль и поперёк изучены и расписаны и исходники и корки при желании найти можно.

[SKov]

Нету там хорошего кода 96,64.

Там есть все лучшие известные двоичные коды длины до 512 и расстояния до 29. Надо только уметь пользоваться таблицами.
В частности, там есть код 91,64,9. Код с расстоянием 11 имеет уже параметры 98,64,11.
Так что для длины 96 и 64-х информационных символов нет известного кода с мин. расст. 11. Следовательно,
нужно ориентироваться на расстояние 9 (или 10 - это не принципиально).
А такие коды есть среди укороченных БЧХ кодов над GF(2^7), о чем я и писал ранее.

[mluk]

Спасибо, все прояснилось. А нет ли таких же таблиц для бчх кодов (в том числе и укороченных).

[SKov]

Спасибо, все прояснилось. А нет ли таких же таблиц для бчх кодов (в том числе и укороченных).

Для укорочения БЧХ кода достаточно вырезать в нем несколько (сколько надо) информационных символов. Их можно считать нулевыми при кодировании и декодировании. Например. Есть БЧХ код 127,120,3 , исправляющий одну ошибку (он же - код Хемминга). Укорачиваем его на 5 инф. символов - получаем 122,115,3 код.
Относительно таблицы кодов, то мне всегда хватало таблицы из книжки Питерсона и Уэлдона, но там все кончается длинами 63.
Поищите таблицы в И-нете. И еще совет - поковыряйтесь в последних версиях МатЛаба.
Там, кажется, есть библиотеки для постоения БЧХ-кодов.
И еще маленький совет. Проще всего взять примитивный код БЧХ длины 127 с расстоянием 9. И укоротить его до нужной длины.
Должно получится что-то вроде 127,99,9, а после укорочения- 96,68,9.
Любой другой способ построения БЧХ кода даст вам, возможно, пару лишних инф. символов,
но не увеличит мин. расстояние, как мы это выяснили выше.

[petrov]

Цифровая связь - Скляр, есть таблица до 255.

[SKov]

Цифровая связь - Скляр, есть таблица до 255.

Мой совет все равно короче
Набираем в МатЛабе:
>> genpoly = bchpoly(127,99)
и имеем счастье
Все счастье можно посмотреть здесь:
http://www.nsu.ru/matlab/MatLab_RU/communi...bchpoly.asp.htm

[SKov]

А вот и таблица линейных кодов разыскалась:
http://www.codetables.de/
На здоровье!

[e-serg]

Вот еще сайт на эту тему, с примерами.
http://www.eccpage.com/

[valera1234]

народ, помогите пожалуйста, мне надо сделать программку для компа для турбокодов на кодах Хемминга, информация после демодулятора с жестким решением поступает.
Пробовал табличным методом (т.е. каждую строку и каждый столбец декодирую незавизимо), но для скоростей 7/8 например блоков (128,120)х(128,120) очень неэффективно работает.
Продумывал алгоритм Чейза2, но если я все правильно понял, то он хорошо работает с поступающей мягкой информацией, т.к. ему тогда легче расставить надежность бит , а в данном случае получается . что надежность у всех одинаковая и ему легко ошибиться с выявлением ненадежных бит.
Продумывал LLR, наверно это даже самое надежное средство было бы. Но как я понял по Скляру где пример приводится с двумя инфо битами и битом четности, и по приложению 8A в книге вывел формулу для четырех инфо бит и одной проверки (для примера), уже получается довольно большое уравнение, а для 127 инфо бит(блок выше ), вообще нереальная формула будет.
Подскажите, или я что то не правильно понимаю или может другие алгоритмы эффективные есть для данной задачи?

[Serg76]

народ, помогите пожалуйста, мне надо сделать программку для компа для турбокодов на кодах Хемминга, информация после демодулятора с жестким решением поступает.
Пробовал табличным методом (т.е. каждую строку и каждый столбец декодирую незавизимо), но для скоростей 7/8 например блоков (128,120)х(128,120) очень неэффективно работает.
Продумывал алгоритм Чейза2, но если я все правильно понял, то он хорошо работает с поступающей мягкой информацией, т.к. ему тогда легче расставить надежность бит , а в данном случае получается . что надежность у всех одинаковая и ему легко ошибиться с выявлением ненадежных бит.
Продумывал LLR, наверно это даже самое надежное средство было бы. Но как я понял по Скляру где пример приводится с двумя инфо битами и битом четности, и по приложению 8A в книге вывел формулу для четырех инфо бит и одной проверки (для примера), уже получается довольно большое уравнение, а для 127 инфо бит(блок выше ), вообще нереальная формула будет.
Подскажите, или я что то не правильно понимаю или может другие алгоритмы эффективные есть для данной задачи?

Лучше, чем алгоритм MAP ( с использованием алгебры отношения правдоподобия - LLR), на данный момент не существует, но для этого необходим мягкий выход демодулятора, для Чейза тоже нужен мягкий выход.