Циклические коды. Кодер и декодер циклического кода, страница 3

Для этого разряда такое деление выглядит следующим образом:

00…010000 / 11001

Å11001

     1001

Остаток 1001 и все последующие остатки, полученные аналогичным образом, делятся на образующий многочлен 11001 до тех пор, пока последний не достигнет значения 1001, после чего они начнут повторяться. Если количество различных остатков будет 15, то образованный таким g(x) код способен исправить любую одиночную ошибку. Аналогичные результаты получаются и в случае выбора g(x) = (х⁴ + х + 1). Однако использовать для тех же целей многочлен (х⁴ + х³ + х² + х +1) оказывается, нельзя, поскольку число различных остатков у него не 15, а только 5. Это объясняется тем, что он входит в разложение не только двучлена (х¹⁵ + l), но и двучлена (х⁵ + 1). Следовательно, в качестве образующего необходимо выбирать такой неприводимый многочлен g(x) (или произведение таких многочленов), который, являясь делителем двучлена (хⁿ + 1), не входит в разложение ни одного двучлена (х^z + 1), степень которого z меньше п (в этом случае говорят, что многочлен g(x) принадлежит показателю степени п).

Образующие многочлены кодов, способных обнаруживать одиночные, двойные и тройные ошибки, можно определить следующим образом. Если известен образующий многочлен р^m(х) кода длины п, позволяющего обнаруживать ошибки некоторой кратности q, то образующий многочлен g(x) код, способный обнаружи­ть ошибки следующей кратности (q + 1), может быть получен умножением многочлена р^m(х) на многочлен (х + 1), что соответствует введению дополнительной проверки на четность. При этом число символов в комбинациях кода за счет дополнительного проверочного символа увеличивается до (n +1).

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

1. По заданному k определяется необходимое для исправления одной ошибки значение (n – k) и строится (n, k) код.

2. Рассматривая (n, k) код как n–разрядный некорректирующий, определяется (n₁ – n) дополнительных разрядов для обеспечения исправления одной ошибки в этом коде и строится код (n₁, n).

3. Повторяя данную процедуру t раз, можно получить код, исправляющий независимые ошибки кратности до tвключительно.

Полученный описанным образом код, однако, оказывается неоптимальным по числу проверочных символов при данном k. Этого недостатка лишены циклические коды БЧХ и их подкласс — коды Рида-Соломона, которые требуют, однако, значительно более сложных устройств для обнаружения и исправления шибок.

В случае циклических кодов, исправляющих пачки ошибок, образующий многочлен g(x) представляет собой произведение неприводимого многочлена степени т на другой многочлен, вид которого определяется типом кода, а старшая степень с – длиной пачки ошибок, на исправление которой код рассчитан. Следовательно, показатель степени g(x) равен (с + т).

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

В настоящее время из циклических кодов для исправления пачек ошибок наиболее известны коды Файра, Абрамсона, Миласа-Абрамсона и Рида-Соломона. Первые три разновидности кодов рассчитаны на исправление в кодируемом блоке одной пачки ошибок, а коды Рида-Соломона — нескольких пачек.

В кодах Файра образующий многочлен имеет вид: g(x) = R(х^m)(х^c + 1), где R(х^m) – неприводимый многочлен степени m, а с – некоторое постоянное число. Общее число символов п в комбинации кода равно общему наименьшему кратному с и (2^m – 1); число проверочных символов (и максимальная длина пачки) – (с+m).