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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:59, 12 мая 2016.

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

TemplateDifinitionIcon.svg Определение «Циклический код»
Код - циклический, если для любого вектора верно то есть циклический сдвиг координат кодового вектора всегда приводит к некому вектору, который также

- многочлен, , - формальный параметр. Если рассматривать множество многочленов степени меньшей , то оно может быть представлено как .


Пусть - идеал, . Тогда существует соответствие между и , то есть .


Это означает, что возможно не только сложение векторов, но и их умножение.

TemplateExampleIcon.svg Пример Пример


Профакторизуем (возьмём остаток от деления)


Полиномиальный код

TemplateDifinitionIcon.svg Определение «Полиномиальный код»
Линейный код - полиномиальный код, если - идеал в кольце
TemplateTheoremIcon.svg Теорема Теорема
Если - линейный код в ,то - циклический - полиномиальный код.
Доказательство

Достаточность:

Пусть - идеал и пусть

- произвольное кодовое слово, тогда

Так как - идеал, то , то есть - циклические код.

Необходимость:

Пусть - линейный циклический код и пусть снова

- произвольное кодовое слово. Тогда

  • в силу
  • в силу для произвольных , а также
  • , где - произвольный многочлен - идеал.


TemplateExampleIcon.svg Пример Пример
- циклический код, нелинейный и неполиномиальный код т.к. -не является кодовым словом.


Рассмотрим процесс построения циклического кода.

Код

Если порождающий элемент.
........
размерность кода, степень порождающего элемента;

, если .

Рассмотрим линейный код:

Многочлен порождающий.
Порождающая матрица:
ATK 4.6.2 22.png
TemplateTheoremIcon.svg Теорема Теорема
Множество идеал в
Доказательство

элемент , порожденному , -элемент кольца

противоречие,т.к. Следовательно:


Проверочный многочлен

TemplateDifinitionIcon.svg Определение «Определение - Проверочный многочлен»
Проверочный многочлен кода
где порождающий многочлен[1].
TemplateLemmaIcon.svg Лемма «Утверждение»
Связь между и  :


TemplateLemmaIcon.svg Лемма «Лемма»
- проверочный многочлен


Построение проверочной матрицы при помощи проверчного многочлена

ATK 4.6.2 23.png
TemplateDifinitionIcon.svg Определение «Определение»
Синдромный многочлен: где проверочная матрица. Синдром зависит только от ошибки в сообщении,а не от сообщения,которое передавалось.

Обнаружение пакетов ошибок

TemplateTheoremIcon.svg Теорема Теорема

Пакеты ошибок длины область из подряд идущих разрядов, внутри которой имеются ошибки (на границе области - обязательно):

Если циклический код над полем то обнаруживает любой пакет ошибок длины
Доказательство
(От противного)

Пусть необнаруживаемый пакет ошибок длины .

необнаружим
Но противоречие.


TemplateExampleIcon.svg Пример Пример:

поле

Коды можно характеризовать с помощью корней , Если -порождающий полином,то -расширенное поле. кодовое слово представимо так: кодовое сообщение на корнях будет занулятся :

И обратное верно : ,то
Слово коду оно на некотором наборе элементов зануляется.
- примитивный многочлен,
- корни примитивного многочлена
,
Если мы рассмотрим код такой длины,то это будет примитивный многочлен.
Если -это параметры кода Хемминга,т.е. примитивный код- это частный случай кода Хемминга и он будет обнаруживать блоки ошибок.


Кодирование и декодирование циклических кодов

1 подход: - несистематическое кодирование.

Кодирование: умножим на .
Раскодирование:делим на .

2 подход:Систематическое кодирование.

Нам нужно чтобы первые символы были такими же как в :
Возьмем

См. также

Код Боуза — Чоудхури — Хоквингема

Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.

Примечания

  1. Любой ли многочлен может быть порождающим?