КОДЫ РИДА-СОЛОМОНА

Пример

Коды Боуза-Чоудхури-Хоквингема (коды БЧХ)

В теории кодирования доказано, что для любых значений m и tсуществует циклический код длиной n=2^m-1, исправляющий все ошибки веса t и менее и содержащий не более r=m*t проверочных символов.

Требуется определить число проверочных символов r для кода с длиной информационной последовательности k=20, который может исправлять двойные ошибки t_и=2.

Решение

Пусть m=3. Тогда 2^m=8, n=7. Это значение меньше k=20, то есть, значение m следует выбирать больше.

Пусть m=5. Тогда 2^m=32, n=31.

R=m*t_и=5*2=10, получаем код с параметрами (n, k)=(31, 21).

Этот код обеспечивает кодовое расстояние не менее d_min=2*t_и+1=5.

Коды БЧХ – это циклические коды, которые используются для исправления ошибок весом . Коды нашли широкое применение в цифровых системах записи звука (речь, музыка). Очень широкое распространение нашли коды БЧХ с кодовым расстоянием d_min =5, исправляющие двойные ошибки.

Длина кодовой комбинации кодов БЧХ должна удовлетворять условию n=2^m-1,где n – всегда нечетное число.

Это очень широко используемый подкласс недвоичных кодов БЧХ. Коды Рида – Соломона используются в современных высокоскоростных системах передачи данных совместно со сверточным кодированием, а также при записи информации на различные устройства хранения данных. Коды позволяют исправлять ошибки, возникающие при передаче, и восстанавливать информацию с поврежденных устройств хранения данных.

Данные обрабатываются порциями по m бит, которые принято называть символами. Как правило, порция представляет собой байт, то есть m=8. Код Рида-Соломона (RS) характеризуется следующими параметрами:

Длина символа	m бит
Длина блока	n=2^m-1 символов
Кодовое расстояние	d_min=(2t+1) символов, где t – число символов, в пределах которых мы хотим исправлять ошибки
Длина контрольной части	n-k=2t символов

Пусть t=1, m=8.

Длина блока равна 2⁸-1=255 символов или 2040 бит.

Длина контрольной части – 2 символа или 16 бит

Код обнаруживает любой пакет ошибок, длина которого не более 16 бит, и исправляет ошибки в пределах одного байта.

Пример – Кодирование в технологии ADSL

В ADSL-модеме используется код Рида-Соломона (255, 239). То есть кодовая комбинация содержит 255 байт, из которых 239 байт – информационные и 16 байт – проверочные. Избыточность кода составляет 16/255=0,063. Минимальное кодовое расстояние равно 17 байт, обнаруживаются все 16-байтовые ошибки, исправляются – 8-байтовые ошибки. Если в кодовой комбинации разрушено более 8 байт, она отбрасывается и не обрабатывается, то есть происходит потеря блока в 255 байт. Чтобы уменьшить вероятность потери блоков, в системе используется режим передачи с чередованием байтов из различных блоков (кодовых комбинаций) – interleaving. Таким образом, помеха (например, импульсная), разрушившая на линии несколько байт подряд, на входе декодера разрушает не более одного байта в каждом блоке из 255 байт. Конечно, использование режима с чередованием приводит к дополнительной задержке за счет буферизации данных перед отправкой их в линию и на приемной стороне перед декодированием.