Глава 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
