Проверочная матрица и ее связь с исправляющей способностью кода

 

Рассмотрим систематический линейный код , задаваемый порождающей матрицей , и построим матрицу вида

, (6.5)

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

. (6.6)

Из (6.6) следует, умножение любого кодового вектора на транспонированную матрицу дает нуль, в связи с этим матрицу (6.5) называют проверочной матрицей. Кроме того, говорят, что линейный код является нуль–пространством проверочной матрицы, либо что код ортогонален проверочной матрице.

На основании соотношений (6.4) и (6.6) имеем

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

. (6.7)

Таким образом, линейный код может быть задан как порождающей (6.3) и проверочной (6.5) матрицами, так и соотношениями (6.7), устанавливающими связь между проверочными и информационными символами кодовых слов.

Теорема 6.4.1. Линейный код имеет минимальное расстояние, равное , тогда и только тогда, когда проверочная матрица содержит множество из линейно зависимых столбцов, а любое множество из столбцов матрицы линейно независимо.

Доказательство: Рассмотрим линейный код, задаваемый проверочной матрицей размерности в виде

,

где – –компонентный вектор-столбец проверочной матрицы. Тогда, на основании теоремы 6.3.1, найдется хотя бы один кодовый вектор, имеющий ненулевых компонент, для которого

,

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

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

,

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

,

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

Рассматривая структуру матриц и можно вынести следующее заключение. Обе матрицы состоят из множества линейно независимых векторов, поскольку наличие в их структуре единичной матрицы делает невозможным существование линейной комбинации строк с нулевой суммой. Следовательно, каждая из матриц может рассматриваться как базис некоторого линейного пространства. Более того, каждое из этих пространств является подпространством векторного пространства, состоящего из всех векторов длины . Учитывая сказанное выше, можно их «поменять ролями» и использовать в качестве порождающей, а – проверочной матрицы некоторого другого кода. Коды, связанные с таким преобразованием, называются дуальными друг другу. Таким образом, если исходным являлся кодом, то дуальным ему будет код.

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

Теорема 6.4.2. (Граница Синглтона). Минимальное расстояние (минимальный вес) любого линейного кода удовлетворяет неравенству:

. (6.8)

Доказательство: Согласно теореме 6.3.1, ненулевое слово минимального веса в коде имеет вес, равный . В систематическом коде существуют слова с одним ненулевым информационным символом и проверочными. Ясно, что такое кодовое слово не может иметь вес, больший , и, значит, .

Граница Синглтона показывает, что для исправления ошибок слова линейного кода должны содержать не менее проверочных символов. Большинство кодов, даже оптимальных, имеют значительно большее количество проверочных символов. Вместе с тем, существуют коды, для которых неравенство (6.8) обращается в равенство.

Любой код с кодовым расстоянием , удовлетворяющим соотношению (6.8), называется кодом с максимальным расстоянием.

Замечание. Граница Синглтона (6.8) бесполезна для двоичных кодов, поскольку значительно уступает в точности границам Плоткина и Хэмминга. Однако, она играет значительную роль в случае –ичных кодов.