Линейные блочные коды
Для блочного кода с 2k
кодовыми словами длиной в n символов, если он только не обладает специальной структурой, аппарат кодирования и декодирования является очень сложным. Поэтому ограничим свое рассмотрение лишь кодами, которые могут быть реализованы на практике.
Одним из условий реализуемости блочных кодов при больших k является условие их линейности.
Что такое линейный код?
Блочный код длиной n
символов, состоящий из 2k кодовых слов, называется линейным (n, k)-кодом при условии, что все его 2k кодовых слов образуют 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 символов.
Рис. 1.1
Блочный код, обладающий свойствами линейности и систематичности, называется линейным блочным систематическим (n, k)-кодом.
