векторов не единственный и, следовательно, G не уникальна. Мы также заметим, что, поскольку пространство имеет размерность к, ранг матрицы G равен к.

Любую порождающую матрицу (",) кода путём проведения операций над строками (и перестановкой столбцов) можно свести к «систематической форме»;

"10 0 ••• О р,, /;,„ ,

О 1 О - О.р,, р,, - /л„ .

(8 1.6)

ООО ••• 1 р, р,2 •• А,,-* где li кхк единичная матрица, а P-kx{ii-k) матрица, которая определяет ii~k избыточных или проверочных символов. Заметим, что порождающая матрица систематического кода создаёт линейный блоковый код, в котором первые к бит любого кодового слова идентичны информационным битам, а остающиеся п-к бит любого кодового слова являются линейными комбинациями к информационных бит. Эти (п-к)

избыточных бита называют паритетными (проверочными) битами Результирующий {п.к) код называется в этом случае систематическим кодом.

Если {}t,k) код порожден матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим. Однако . такая матрица эквивалентна матрице в систематической форме в том смысле, что одна может быть получена из другой ( элементарными операциями над строками и перемещением столбцов. Два {п,к) линейных кода, порожденных двумя эквивалентными порождающими матрицами, называют эквивалентными и один может быть получен из другого перестановкой элементов. Таким \

образом, каждьи! линейный {п,к) код эквивалентен линейному систематическому {ii,k] коду. \

Пример 8.1.1. Рассмотрим код (7, 4) с порождающей матрицей

"1 0 0 0 1 0 1" О 1 О 0.1 1 1 О О 1 ol 1 О 0 0 0 1 0 1 1 Типичное кодовое слово можно выразить так:

(8 1.7)

шЗ -i;i4 па гяб пП

, где (х } представляют четыре информационных

бита, а {c,„j\ представляют три паритетных бита, определённых так:

с...

(8.1.8)

Линейный систематический (и, к) двоичный блоковый кодер можно реализовать, используя -битовый регистр сдвига, и-к сумматоров (mod 2), связанных с соответствующими ячейками регистра сдвига и генерирующих проверочные символы, которые потом временно располагаются во втором регистре сдвига длины п-к . Затем к информационных бита, а за ними п-к проверочных бита последовательно покидают два регистра и подаются на модулятор. Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1)

Выходные данные

Рис. 8.1.1. Линейный регистр сдвига для получения двоичного юда (7,4)

С любым линейным кодом (п, к) кодом связан дуальный код размерностью п-к.

Дуальный код является линейным (п,п-к) кодом с 2"~* кодовыми векторами, которое образуют нуль-пространство по отношению к (w, к ) коду. Порождающая матрица для дуального кода, обозначаемая Н, состоит из п-к линейно независимых кодовых векторов, выбираемых в нуль-пространстве. Любое кодовое слово С„, из {п, к) кода ортогонально любому кодовому слову дуального кода. Следовательно, любое кодовое слово (», к) кода ортогонально любой строке матрицыН, т.е.

СХ = 0, (8-1-9)

где О означает вектор-столбец, состоящий из п-к нулей, а С,„- кодовое слово (п,к) кода. Поскольку (8.1.9) справедливо для любого кодового слова ( , к ) кода, то следует

GH = 0, (8.1.10)

где 0-теперь к х{п- к) матрица со всеми нулевыми элементами.

Теперь предполох<им, что линейный (п, к) код является систематическим, и его

порождающая матрица дана в систематической форме (8.1.6). Тогда, поскольку GH -0. следует, что

(8.1.11)

Отрицательный знак в (8.1.11) может быть опущен при работе с двоичными кодами, поскольку вычитание по niod2 идентично сложению по mod2.

Пример (8.1.2). Для систематического кода (7, 4), генерируемого матрицей G, определяемой (8.1.7), имеем согласно (8.1.11) матрицу Н в виде

1 1 1 О 1 О о"

О 1 1 НО 1 О

110 10 0 1

Теперь уравнение С„Д = О распадается на три уравнения

(8 1.12)

(8.1.13)

Таким образом, видим, что произведение СН эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления с;„, у - 5, 6, 7. Это значит, что (8.1.13)

эквивалентно (8.1.8).

Матрицу Н можно использовать в декодере для проверки того, удовлетворяет ли принимаемое кодовое слово Y условию (8.1.13), т.е. YH = О. Таким образом, декодер сверяет принятые проверочные символы с соответствующей линейной комбинацией символов y, у, Уз и у, которые формируют проверочные символы на передаче. Поэтому принято называть Н проверочной матрицей, связанной с (я, к) кодом.

Выскалсем соображение, касающееся связи минимального расстояния кода и его проверочной матрицы Н. Произведение С с С„, О представляют линейную комбинацию п столбцов . Поскольку С„,Н О, векторы-столбцы Н линейно зависимы. Допустим, что Cj означает кодовое слово с минимальным весом линейного

кода ( , к) . Оно должно удовлетворять условию СН = О . Поскольку минимальный вес равен минимальному расстоянию, следует, что б/,„ столбцов Н линейно зависимы. Альтернативно, мы можем сказать, что не более, чем d -1 столбцов Н линейно независимы. Поскольку ранг матрицы Н не больше п-к, имеем п-к >d 1. Следовательно, имеет верхнюю границу

й? <« + 1. (8.1.14)

Задаваясь линейным двоичным кодом (п, к) с минимальным расстоянием d, мы молсем синтезировать линейный двоичный код (п+1,к) путём добавления одного дополнительного проверочного символа к каждому кодовому слову. Проверочный символ обычно выбирается так, чтобы быть проверочным символом по всем символам кодового слова. Таким образом, добавляемый проверочный символ равен О, если исходное кодовое слово имеет чётное число единиц, и равен 1, если кодовое слово имеет нечетное число единиц. Следовательно, если минимальный вес и, следовательно, минимальное расстояние кода нечётно, добавляемый проверочный символ увеличит минимальное расстояние на 1. Мы называем код (л +1, к) расширенным кодом. Его проверочная матрица

О" О

(8.1.15)

1 1 1 ••• 1

где Н - проверочная матрица исходного кода. Систематический («, к) код может быть также укорочен размещением в начале информационного блока нулевых символов. Это значит, что линейный код («, к), состоящий из к информационных символов и ti-k проверочных может быть укорочен до линейного кода (п-/, к-/), если установить первые / информационных символов (во всех кодовых комбинациях) нулями. Эти / символов не передаются по каналу, а п-к проверочных символа рассчитываются обычным образом, как в исходном коде. Поскольку С„, = X,,,G, замена первых / символов Х„, нулями эквивалентна сокращению числа строк матрицы G за счёт удаления первых / строк. Аналогично, вследствие того, что

мы молсем удалить первые / столбцов матрицы Н. Укороченный код (п-/, к-1) состоит

из 2* кодовых слов. Минимальное расстояние этих 2*" кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного (п, к) кода.