Добрый день!!!

Гуру кодирования, проясните такую вещь.

Рассмотрим пример.
Возьмем кодер RS 7/8 работающий с байтами. Длинна блока 240 символов, 30 проверочных символов(байт). Кодер может восстановить 15 символов или 15*8= 120 бит.
Теперь возьмем более менее похожий по структуре кодер БЧХ. n/k/t = 255/223/4. 32 проверочных символа, но восстановить можно всего 4 символа.

Почему нельзя при генерации генераторного полинома БЧХ, вместо НОК неприводимых полиномов, взять простой полином из RS и работать с ним в битовом поле? Нигде в книгах ответа на этот вопрос я не нашел %(

Спасибо.

Можно
Получится двоичный циклический код Хэмминга, исправляющий одну ошибку.
Частный случай двоичного БЧХ кода.
См. в книге Берлекэмпа вывод БЧХ-кодов на основе кода Хэмминга.

UPD. Выше касалось простого полинома в поле GF(2).

Код Рида-Соломона можно рассматривать как некий двоичный код.
Если не вру, это называется код Юстенсена.
Это описано у Блейхута.

UPD2. Следует обратить внимание, что БЧХ исправит любую конфигурацию из 32 ошибочных бит.
Рид-Соломон исправит 120 бит только если они сгруппированы по 15 байтам.

неа, в сабжевом случае он исправит только 4 бита, потому что кодовое расстояние d = 79 (матлаб со мной солидарен)

вот еще какой мне момент не понятен.

Возьмем кодер RS в поле GF(2^6), с параметрами : длинна блока 42 символа (252 бита), из них 6 проверочных (36 бит). Т.е. с точки зрения количества битов код близок к БЧХ коду n/k/t = 255/223/4. Но RS исправит от 3-х до 18 ти бит. А БЧХ только 4. Тогда с чего в книгах пишут что БЧХ коды, для маленьких блоков близки к оптимальным кодам ?

Да, ошибся, 4 бита. Символы тут будут двоичными.

Конструктивное расстояние этого кода d = 9 = 2t+1.
А истинное минимальное расстояние >= d.

ошибся по конец рабочего дня %) вопрос про БЧХ vs RS актуален

В вашем примере RS код не исправляет некоторые из 4-х кратных ошибок. А БЧХ исправляет все 4-х кратные.
В большинстве каналов ошибки малого веса намного более вероятны, чем ошибки бОльшего веса.
Поэтому исправление некоторых ошибок веса 30 мало кого интересует. А вот неисправление ошибки веса 4 - это плохо.
Поэтому минимальное расстояние кода часто выступает как основная характеристика эффективности кода.
У БЧХ кодов мин.расст. больше, чем у двоичных версий RS-кода при прочих равных кодовых параметрах.

но ведь RS код можно пропустить через перемежитель. тогда он исправит больше чем 3 ошибки %)


хмм, если я правильно понимаю исправляющая способность определяется минимальным расстоянием.

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

В примере есть 32 проверочных бита, код РС, с 32 проверочными стмволами должен исправить 16 битовых ошибок. Это явно больше 4-х ошибок кода БЧХ. Или я ошибаюсь и в двоичных РС кодах все по другому?

Символы исправляет РС а не биты, 3 символа может исправить и пофиг сколько бит ошибочных в этих символах, но 4 символа уже не исправит, даже если там по одной битовой ошибке в каждом.

Надо приравнять двоичную длину RS кода и бчх кода и их двоичную избыточность.
Вы это уже делали выше и получили, что RS исправляет 3 любые ошибки, а бчх = 4.
Так что в этой части я не понимаю, откуда снова возник вопрос, на который вы сами уже ответили.
А что касается перемежения, то простое перемежение еще никогда не увеличивало минимальное расстояние никакого кода.
Оно обычно делается для "размазывания" пакета ошибок по нескольким кодовым словам - тогда этот пакет может быть исправлен.

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

Есть двоичный код БЧХ с параметрами : n/k/t = 255/223/4. В этом коде на 223 информационных бита, приходится 32 проверочных бита и исправляется 4 битовых произвольных ошибки. Почему нельзя сделать двоичных код РС, с параметрами (ну положим) n/k/errs 240/30/15. т.е. на 210 информационных символов (битов), 30 проверочных и исправляется 15 битовых произвольных ошибок?

Ведь недвоичный код РС в поле GF(2^8) 240/30/15 существует. Что мешает сделать такой же двоичный? Ведь генераторный полином будет построен по одним и тем же правилам.

БЧХ подразумевает два разных алфавита: канальный и локаторный.
Канальный алфавит является подполем локаторного.
РС - частный случай БЧХ, там эти алфавиты совпадают.
Локаторы из алфавита GF(2) могут поддерживать кодовые слова длины 1
Поэтому двоичный Рид-Соломон это по сути недокод - одиночная цифра без избыточности

Но пользоваться вы им будете по-разному.
В том смысле, что символы кодового слова будут уже не двоичные, а q-ичные, что дает дополнительную степень свободы для формирования существенно "менее совпадающих" кодовых слов.
Поэтому и расстояние у RS получается максимально возможное, но не в двоичном поле, а в q-ичном.

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

вот теперь пасьянс сложился, нутром чувствовал что литр, а доказать.... %) большое спасибо.


тут от канала зависит. в случае пакетной ошибки будет один результат, в случае одиночной другой. но уважаемый petrov прав, 4 произвольных ошибки, сабжевый RS не исправит.