8.1.1. Порождающая и проверочная матрицы

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

,

а выходом кодера является вектор из  символов

.

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

                    (8.1.2)

где  или , а  представляют произведение  и . Линейные уравнения (8.1.2)

можно также представить в матричной форме

,                    (8.1.3)

где  - порождающая матрица кода, равная

                    (8.1.4)

Заметим, что произвольное кодовое слово – это просто линейная комбинация векторов  из ,

                      (8.1.5)

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

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

,                     (8.1.6)

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

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

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

.                    (8.1.7)

Типичное кодовое слово можно выразить так:

,

где  представляют четыре информационных бита, a  представляют три паритетных бита, определённых так:

                                  

              (8.1.8)

                                                                    

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

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

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

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

,                    (8.1.9)

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

,                     (8.1.10)

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

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

                     (8.1.11)

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

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

                     (8.1.12)

Теперь уравнение  распадается на три уравнения

                      (8.1.13)

Таким образом, видим, что произведение  эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления  Это значит, что (8.1.13) эквивалентно (8.1.8).

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

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

                       (8.1.14)

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

,                    (8.1.15)

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

,

мы можем удалить первые  столбцов матрицы . Укороченный код  состоит из  кодовых слов. Минимальное расстояние этих  кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного  кода.