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

[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 символов, есть ли возможность его уменьшить.

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

[mluk]

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

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

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

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

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

[MrYuran]

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

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

[mluk]

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

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

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

[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 информационных. Как это сделать

[SKov]

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

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