Главная > Теория связи > Введение в теорию помехоустойчивого кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Глава VI. Синтез линейных кодов с заданным кодовым расстоянием

1. Вводные замечания

Вопросы теории линейных кодов в этой и последующих главах излагаются применительно к кодам с основанием, равным степени простого числа. Дело в том, что при этом несущественном ограничении оказывается возможным рассматривать комбинации кода как упорядоченные совокупности элементов конечного поля и широко использовать ряд хорошо разработанных разделов высшей алгебры [104, 84, 56].

В соответствии со сказанным в дальнейшем термины «элемент поля» и «символ» используются как синонимы.

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

(VI.1.1)

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

(VI.1.2)

где , а умножение и сложение проводится по правилам, определенным для данного поля Галуа.

Положим

(VI.1.3)

и будем считать, что линейная форма не тривиальна (среди коэффициентов имеется хотя бы один, не равный 0).

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

(VI.1.4)

где — информационные символы, a - линейная форма (VI.1.3), с помощью которой находится проверочный символ комбинации (VI. 1.1).

Совокупность линейных форм (VI.1.4) задает преобразование каждой -значной комбинации исходного кода в -значную комбинацию кода с избыточностью. Запись кода в виде (VI.1.4) представляет большие удобства как при исследовании общих вопросов, так и при построении конкретных кодов. Знание линейных форм (VI.1.4) позволяет легко выписать все комбинации кода в виде матрицы, имеющей строк и столбцов:

(VI.1.5)

В матрице (VI.1.5) первая строка задает правило синтеза комбинации кода, а остальные строки — это уже конкретные комбинации. Так, например, комбинации соответствуют информационные символы и проверочные символы .

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

Предположим, что и линейные формы, представляющие код (табл. VI.1), имеют вид

(VI.1.6)

Здесь информационные символы принимают а запись, например, означает, что контрольный символ, стоящий на четвертой позиции каждой комбинации кода (VI. 1.6),

представляет собой сумму первого информационного символа с «удвоенным» значением второго информационного символа той же комбинации. Естественно, что сложение и умножение здесь производятся по правилам, определенным для элементов поля , см. табл. VI.2 и VI.3.

В качестве второго примера рассмотрим код с основанием

(VI.1.7)

Здесь информационные символы принимают значения 0, 1, 2, а запись, например, означает, что проверочный символ,

Таблица VI.2

Таблица VI.3

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

Таблица VI.4

<< Предыдущий параграф Следующий параграф >>
Оглавление