7.3. Систематический циклический код.

Построение кодового полинома путем перемножения информационного и порождающего полиномов приводит к не систематическому кодовому слову, в котором отсутствует явное разделение информационных и проверочных символов.

Пример 7.3.1.Возьмем, как и в примере 7.2.2, в качестве порождающего (7.4) двоичный код полином. Информационному сообщению вида (1110) отвечает информационный полином. Тогда кодовый полином, получаемый прямым перемножениеми, имеет вид

,

а соответствующее ему слово будет (1000110). Очевидно, что оно представлено не в систематическом виде, поскольку не содержит в начале (или конце) слова последовательность информационных символов.

Для того чтобы прийти к систематической форме кодового слова необходимо осуществить некоторое согласование между информационным и кодовым полиномами. Пусть – информационный полином, а– кодовый. Систематическое правило кодирование предполагает получение кодового полинома в таком виде, чтобы коэффициенты при старших степенях полиномасоответствовали информационным символам. Данное требование достигается путем умножения информационно полинома на многочлен:

,

что эквивалентно сдвигу информационного слова на позиций вправо и добавления слева аналогично числа нулей.

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

, (7.6)

или, в развернутом виде

.

Пример 7.3.2.Для условий примера 7.3.1 построим кодовый полином в систематической форме согласно (7.6). В этом случае, а остатокот делениянанаходим из соотношения

.

Тогда систематический кодовый полином , а соответствующий ему кодовый вектор, где информационные биты занимают крайне правые позиции.

7.4. Порождающая и проверочная матрицы циклического кода.

Задание циклического кода с помощью порождающего или проверочного полинома не исчерпывает всех возможностей задания циклического кода. Как и любой линейный код циклический может быть определен с помощью порождающей и проверочной матрицы. Что касается порождающей матрицы, то ее структура очевидным образом следует из систематической формы представления кодовых полиномов. Рассмотрим элементарных информационных векторов:,, …,. Первым шагом по построению соответствующих им систематических полиномов является нахождение произведений вида, которые в рассматриваемом варианте будут:

,,…,.

На втором шаге осуществляется вычисление остатков , как результат деления полученных произведений на порождающий полином. После построения согласно правилу (7.6) систематических кодовых полиномов

,

становятся известными соответствующие им кодовых векторов, которые представимы в виде:

,

где ––компонентные вектора коэффициентов полиномов остатков. Линейная независимость полученных подобных образом кодовых векторов позволяет использовать их в качестве базиса кода, а значит, построить порождающую матрицу в виде:

, (7.7)

где матрицасостоит из коэффициентов полиномов остатков. Полученная таким образом порождающая матрица позволяет построить систематический линейный код, в котором информационные символы занимаюткрайних позиций справа. Если же, по какой-либо причине, желательно, чтобы информационные символы занималикрайних позиций слева, то необходимо осуществить–кратный циклический сдвиг всех строк матрицы, т.е. по сути дела осуществить перестановку подматрици.

Пример 7.4.1.Найдем порождающую матрицу (7,4) циклического кода с порождающим полиномом. Для рассматриваемого примераи, значит,,,и. Вычисляя остатоксогласно алгоритму, описанному в примере 7.1.3, получаем, и, следовательно,и. Поступая аналогично, можно определить и остальные базисные вектора. Однако не трудно убедиться, что вектораимогут быть получены в результате однократного циклического сдвигавправо и влево соответственно, т.е.и. Нахождение векторатакже возможно без нахождения остатка. Оказывается достаточно осуществить циклический сдвигвлево и сложить полученный вектор с исходным:. В итоге имеем

.

Если необходимость построения систематического кода отсутствует, то порождающая матрица может быть построена непосредственно по порождающему полиному: строками матрица служатразличных циклических сдвигов–мерного вектора коэффициентов порождающего полинома

.

Аналогично, проверочная матрица несистематического кода может быть прямо построена по проверочному полиному :

.