Линейные блочные коды

Для блочного кода с 2^k кодовыми словами длиной в n символов, если он только не обладает специальной структурой, аппарат кодирования и декодирования является очень сложным. Поэтому ограничим свое рассмотрение лишь кодами, которые могут быть реализованы на практике.

Одним из условий реализуемости блочных кодов при больших k является условие их линейности.

Что такое линейный код?

Блочный код длиной n символов, состоящий из 2^k кодовых слов, называется линейным (n, k)-кодом при условии, что все его 2^k кодовых слов образуют k -мерное подпространство векторного пространства n- последовательностей двоичного поля GF(2).

Если сказать проще, то двоичный код является линейным, если сумма по модулю 2 (mod2) двух кодовых слов также является кодовым словом этого кода.

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

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

Возьмем простейшее поле, состоящее из двух элементов − нуля - 0 и единицы - 1. Определим для него операции сложения и умножения:

0+0=0, 0× 0=0;
0+1=1, 0× 1=0;
1+0=1, 1× 0=0;
1+1=0, 1× 1=1.

Определенные таким образом операции сложения и умножения называются сложением по модулю 2 (mod2) и умножением по модулю 2.

Отметим, что из равенства 1+1 = 0 следует, что -1 = 1 и, соответственно, 1+1=1-1, а из равенства 1×1=1 − что 1:1=1.

Алфавит из двух символов 0 и 1 вместе со сложением и умножением по mod2 называется полем из двух элементов и обозначается как GF(2). К полю GF(2) применимы все методы линейной алгебры, в том числе матричные операции.

Еще раз обратим внимание на то, что все действия над символами в двоичных кодах выполняются по модулю 2.

Желательным качеством линейных блочных кодов является систематичность.

Систематический код имеет формат, изображенный на рис. 1.1, то есть содержит неизменную информационную часть длиной k символов и избыточную (проверочную) длиной n – k символов.

Рис. 3.1

Блочный код, обладающий свойствами линейности и систематичности, называется линейным блочным систематическим (n, k)-кодом.

Дата добавления: 2014-01-07