Вопрос 3. Циклические коды




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

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

Подпространство V наборов длины п называется циклическим подпространством или циклическим кодом, если для любого век­тора v = (аn-1, аn-2,..., а0) из подпространства V вектор v’ = (а0, аn-1, аn-2,..., а1), получаемый в результате циклического сдвига компонент вектора v на единицу вправо, также принадле­жит подпространству V.

Циклические коды строятся на алгебре многочленов.

Вторым свойством всех разрешенных комбинаций циклических кодов является их делимость без остатка на некоторый специальным образом выбранный[2] полином степени rG (x), называемый производящим.

Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином.

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

Здесь k – количество информационных символов,

r – количество проверочных символов.

n = к + r.

По полиному G(x) строится порождающая матрица линейного кода.

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

G(x)×H(x) = xn – 1,

для q = 2

G(x)×H(x) = xn + 1, (3.1)

где H(x) – некоторый полином, степени n – r не обязательно неприводимый, он порождает проверочную матрицу.

Справка. Собственно, как составное число раскладывается на произведение простых чисел, так и многочлен xn + 1 раскладывается на произведение неприводимых многочленов меньшей степени, один из которых и берется за G(x), а произведение остальных – H(x).

Из выражения (3.1) следует, что xn + 1 делится на G(x).

По определению, если кодовая комбинация длины n записанная в виде

принадлежит коду, то и

тоже принадлежит коду.

Проверим это.

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

.

Чтобы принадлежал коду, достаточно, чтобы он делился на G(x) нацело.

По определению F(x) делится на G(x) нацело, значит и тоже.

также делится на G(x), т.к. xn + 1 делится на G(x) – см. выше (3.1).

Значит делится на G(x) нацело.

 

Кодирование.

Пусть последовательность информационных элементов длины k

а0, а1, …, аi, …,аk-1

представляется в виде полинома от формальной переменной x степени k – 1

.

Далее I (x) умножается на одночлен xr степени r и делится на G (x) – производящий полином. Не нацело.

(3.2)

где R (x) – остаток от деления т.е.

Здесь C(x) – той же степени, что и I(x).

Пример деления:

Перенесем в (3.2) дробь из правой части в левую

(3.3)

Обе части умножим на G (x)

(3.4)

Коэффициенты полинома F(x) и есть последовательность символов помехоустойчивой кодовой комбинации длины n = k + r.

Полином F(x) без остатка делится на G(x). Если в F(x) закралась ошибка, он не поделится нацело на G(x) и остаток будет синдромом, позволяющим обнаружить, а при достаточной степени r и устранить ошибку.

Если представить

(2.4)

то F(x) будет выглядеть неразделимым.

Если представить

(2.4)

то видно, что F(x) будет разделимым, в нем старшие k разрядов будут информационными, а младшие r разрядов – проверочными, т.к. умножение информационного k-разрядного полинома I(x) на xr

перенесут k разрядов полинома I(x) влево на r разрядов. А младшие r разрядов заполнятся операцией

Пример.

Пусть I = 1011

G(x) = x4 Å x Å 1

xr = x3

Тогда I(x) = x3 Å x Å 1

I(x) ∙ xr = x6 Å x4 Å x3

 

C(x) = x2 Å 1,

проверка

= (x4 Å x Å 1)(x2 Å 1) Å x2 Å x Å 1 = x6 Å x4 Å x3

Еще коды:

Среди циклических кодов особое место занимает класс кодов, предложенных

Боузом и Чоудхури и независимо от них Хоквингемом. Коды Боуза—Чоудхури-Хоквингема получили сокращённое наименование БЧХ- коды.

БЧХ- коды являются обобщением кодов Хемминга на случай исправления нескольких независимых ошибок (eи > 1). Частными случаями БЧХ- кодов являются коды Файра, предназначенные для обнаружения и исправления серийных ошибок ("пачек" ошибок), код Голея - код, исправляющий одиночные, двойные и тройные ошибки (d min=7), коды Рида-Соломона (РС- коды), у которых символами кода являются многоразрядные двоичные числа.

 

В.КНЯЗЕВ


[1] 1. Перестановка любых двух строк, 2. Умножение любой строки на ненулевой элемент поля, 3. Прибавление произведения одной из строк матрицы на ненулевой элемент поля к другой строке матрицы.

[2] Неприводимый в данном поле полином – т.е. полином, который не может быть представлен в виде произведения многочленов низших степеней в данном поле.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2021-04-15 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: