Совершенные и квазисовершенные коды

Линейные коды

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

Если записать k линейно-независимых блоков в виде k строк, то получится матрица размером n´ k, которую называют порождающей или производящей матрицей кода G.

Множество линейных комбинаций образует линейное пространство, содержащее 2^k блоков, т.е. линейный код, содержащий 2^k блоков длиной n, обозначают (n, k). При заданных n и k существует много различных (n, k)-кодов с различными кодовыми расстояниями d, определяемых различными порождающими матрицами. Все они имеют избыточность e _k=1-k/n или относительную скорость R_k=k/n.

Чаще всего применяют систематические линейные коды, которые строят следующим образом. Сначала строится простой код длиной k, т.е. множество всех k-последовательностей двоичных символов, называемых информационными. Затем к каждой из этих последовательностей приписывается r = n - k проверочных символов, которые получаются в результате некоторых линейных операций над информационными символами.

Простейший систематический код (n,n-1) строится добавлением к комбинации из n-1 информационных символов одного проверочного, равного сумме всех информационных символов по модулю 2. Такой код (n,n-1) имеет d=2 и позволяет обнаружить одиночные ошибки и называется кодом с одной проверкой на четность.

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

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

Совершенными (плотно упакованными) называют коды, в которых выполняются соотношения , где D - максимальная кратность исправляемых ошибок; b - основание кода; r - число проверочных символов.

Они отличаются тем, что позволяют исправлять все ошибки кратностью D или меньше и ни одной ошибки кратности больше D.

Число известных совершенных кодов ограничено кодами Хэмминга значности и бинарным циклическим кодом Голея.

Квазисовершенными принято называть коды, исправляющие все ошибки кратности D и ошибок кратности D +1 при условии, что .

Класс квазисовершенных кодов значительно шире, чем класс плотно упакованных кодов.

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