Кодер и декодер Рида-Соломона на С++

Кодирование Рида-Соломона

Как и у всех помехоустойчивых кодов, исправляющая способность кода Рида-Соломона основана на добавлении избыточности в информационные данные. Коды были разработаны в 1960 году в Массачусетском технологическом институте Ирвином Ридом и Густавом Соломоном и являются частным случаем БЧХ-кодов (кодов Боуза-Чоудхури-Хоквингема).

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

Коды Рида-Соломона используются в следующих современных системах цифровой передачи и хранения информации:

• спутниковая связь;
• мобильная связь;
• цифровое DVB-телевидение;
• модемы передачи данных;
• запись и хранение данных на CD и DVD дисках;
• штрих-коды и QR-коды.

При передаче информации в каналах связи возникают помехи, при хранении информации на DVD дисках могут появиться царапины, QR-код может нечётко пропечататься, и всё это приводит к ошибкам в первоначальной информации. Искажения информации для двоичных сигналов выражаются в замене битов “0” на “1” и наоборот, битов “1” на “0”. Использование кода Рида-Соломона позволяет не только обнаружить факт искажения первоначальной информации, но и локализовать искажённую позицию, а для двоичной информации это равносильно исправлению ошибки. На практике впервые коды Рида-Соломона были применены при записи информации на лазерные компакт-диски.

При построении кода Рида-Соломона вся информационная последовательность разбивается на блоки длиной k символов, к каждому такому блоку добавляются m проверочных символов, в итоге на выходе кодера образуется кодовое слово длиной n = k + m. Исправляющая способность такого кода в общем случае равна m/2, то есть такой код может исправить m/2 ошибочных символов в блоке длиной n символов. Эта информация отображается в названии кода: RS (255, 223) обозначает код Рида-Соломона с кодовым словом длиной 255 символов, из которых 223 являются информационными, а 32 проверочными, исправляющая способность кода 16 символов. Например, существуют такие разновидности кода Рида-Соломона: RS(126,112), RS(194,178), RS(208, 192), RS(219, 201), RS(225, 205), RS(204, 188), RS(255, 239), RS(146, 130), RS(160, 146).

В блочных кодах каждый блок кодируется и декодируется отдельно, независимо от других блоков. Кодер блочного кода можно условно представить некоторой функцией, на вход которой поступают k символов, а на выходе образуется n символов. Декодер представляет функцию, на вход которой поступают n символов, а на выходе образуется k символов. Блочный код можно задать несколькими способами – с помощью кодовой таблицы, порождающей матрицы или порождающего полинома.

Реализация кодера и декодера на С++

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

Также надо обратить внимание на то, что существуют две разновидности кодов Рида-Соломона – систематический и несистематический. При систематическом кодировании исходные $k$ информационных символов остаются неизменными, а проверочные $m$ символов добавляются в конце информационного слова. Поэтому при декодировании такого кода, в случае если ошибки в текущем блоке не обнаруживаются, то просто отбрасываются проверочные символы, а остаются чистые информационные символы. Если ошибки были обнаружены, то они исправляются в информационном блоке, а затем также отбрасывается проверочный блок.

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

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

Алгоритм кодера можно представить следующими операциями:

• кодируемые данные передаются через массив $data[i]$, где $i=0...(k-1)$;
• сгенерированные проверочные символы заносятся в массив $b[0]…b[2*m-1]$;
• элементы порождающего полинома содержатся в массиве $g[]$;
• сгенерированное кодовое слово определяется следующей формулой:

$c(x) = data(x)*x^{(n-k)} + b(x)$.

Текст программы, реализующей кодер на языке C++, приведен ниже.

Рисунок 1. Текст программы. Автор24 — интернет-биржа студенческих работ

Алгоритм декодера можно представить следующими операциями:

• вычисление синдрома ошибки, т.е. остатка от деления декодируемого слова на порождающий полином (если остаток равен нулю, то ошибок в принятом слове нет);
• построение полинома локатора ошибки, т. е. если синдром ошибки ненулевой, то вычисляется полином локатора ошибок, коэффициенты которого соответствуют искажённым символам;
• нахождение корней полинома ошибки, обычно решающееся перебором (корни полинома определяют местоположение ошибочных символов в принятом слове);
• построение битовой маски, в которой каждый из её единичных битов соответствует позиции ошибочного бита в принятом слове;
• исправление ошибочных символов путём наложения битовой маски на информационное слово и инвертирования всех искажённых бит через операцию XOR.