Циклические коды

Одной из самых важных конструкций кодов являются циклические коды.

Определение 4.8. Код С называется циклическим, если он инвариантен относительно циклических сдвигов: из того, что набор (по,..., an_i) принадлежит С, следует, что и всякий набор (as, as+i,..., an_i, ao,..., as-i) принадлежит С.

По теореме 3.54 циклические линейные коды совпадают с идеалами в кольце РгМДя” — 1). Поэтому построить циклический код можно так: возьмем многочлен х11 — 1, выберем некоторый делитель <р(х) этого многочлена и в кольце вычетов по модулю хп — 1 рассмотрим идеал, порожденный <р(х). Оказывается, что при удачном выборе р(х) коэффициенты многочленов, принадлежащих этому идеалу, будут давать хороший код.

Давайте рассмотрим простой пример.

Пример 4.9. Пусть п = 7. Запишем разложение на неприводимые множители:

В качестве возьмем последний множитель. Умножая его на степени х получим базис в подпространстве, которое является кодом:

Можно проверить, что кодовое расстояние для этого кода равно 3.

В самом деле, умножение на х в кольце вычетов по модулю х7 1 приводит к циклическому сдвигу коэффициентов. Если есть набор коэффициентов с двумя единицами, то расстояние между единицами в наборе не больше 2 (либо в одну сторону, либо в другую). По тогда есть такой циклический сдвиг этого набора, у которого единицы помещаются в младшей (левой половине). Значит, это либо многочлен степени не выше 2, чего не может быть по теореме 3.52, либо многочлен 1 + х3. Но 1 +а;3 = х mod (1 Н-ж-Ьа;3), поэтому в последнем случае мы бы получили все кольцо вычетов. Таким образом, минимальное число единиц (равное кодовому расстоянию) для этого кода равно 3.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >