в частности, каждый (2" - 1,2" - 1 - т)-код Хэмминга может быть расширен до (2™, 2" - т)-кода, исправляющего одиночные ошибки и обнаруживающего двойные ошибки; обычно этот код также называется кодом Хэмминга.

Можно произвести и редукцию кода, переходя к коду над меньшим полем. Из некоторого кода над полем GF (q") выберем все слова с координатами из подпол я GF (<?). Получившийся код называется подкодом над подполем исходного кода. Если исаддный код является линейным, то подкод над подполем также линеен, но не является подпространством исходного кода. Это происходит потому, что подпространство должно содержать все возможные произведения кодовых слов на элементы поля GF {q"). Подкод над подполем является линейным потому, что над подполем GF (q) все линейные комбинации кодовых слов будут оставаться в подкоде над подполем. Любое множество базисных векторов в подкоде над подполем является линейно независимым также и в поле GF ((/"), и поэтому размерность исходного поля не меньше размерности подкода над подполем. Обычно, однако, исходный код имеет большую размерность; подкод над подполем имеет меньшую скорость, чем исходный код.

3.7. КОДЫ РИДА-МАЛ Л ЕРА

Коды Рида-Маллера представляют собой класс линейных кодов над GF{2) с простым описанием и декодированием, осуществляемым методом простого голосования. По этим причинам коды Рида- Маллера играют важную роль в кодировании ),хотя если судить об этих кодах по минимальному расстоянию, то, за некоторыми исключениями, они не заслуживают особого внимания. Для любых целых т и г < т существует код Рида-Маллера длины 2", который называется кодом Рида-Маллера г-го порядка длины 2".

Код Рида-Маллера является линейным кодом. Мы определим этот код через порождающую матрицу; эту матрицу будем строить

) Коды Рида-Маллера были использованы при передаче фотографий Марса космическим кораблем Маринер в 1972 г. В настоящее время для этой цели можно было бы использовать более эффективное кодирование.

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

1 1 ... Г

в удобной для декодирования несистематической форме. Прежде всего определим покомпонентное произведение двух векторов а и Ь; если

а = (оо, Gi, ..., a„ i) и b = (bg, .... fc„ j),

TO их произведение равно вектору

ab = {Oobo, a A, .... a„ ifc„ ,).

Порождающая матрица кода Рида-Маллера г-то порядка длиной 2" определяется как совокупность блоков

,G, J

где Go - вектор размерности п = 2", состоящий из одних единиц; Gj есть (тХ2")-матрица, содержащая в качестве столбцов все двоичные т-последовательности; строки матрицы G получаются из строк матрицы G как все возможные произведения / строк из G. Для определенности будем считать, что первый столбец в Gi состоит из одних нулей, последний - из одних единиц, а остальные т-последовательности в G расположены в порядке возрастания, считая, что младший бит расположен в нижней строке.

Поскольку существует всего способов выбора / строк,

входящих в произведение, то матрица G имеет размер (/) X X 2". Ясно, что для кода Рида-Маллера порядка г

*-+(:)+••+(:).

что обеспечивается линейной независимостью строк в матрице G. Код Рида-Маллера нулевого порядка является (п, 1)-кодом. Это просто код с повторением, который тривиально декодируется с помощью мажоритарного метода. Минимальное расстояние такого кода равно 2".

В качестве примера положим т = 4, п = 16, г = 3. Тогда

Go = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] = [а,],

0000000011111111 0000111100001111 0011001100110011 0101010101010101

аз а,

78 гл. 3. ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

Поскольку Gi имеет 4 строки, матрица G. имеет (j) строк:

Таким образом порождающая матрица кода Рида-Маллера третьего порядка длины 16 является (15х 16)-матрицей вида

"Go

Ga Gs

Эта порождающая матрица задает (16, 15)-код над GF (2) (на самом деле это просто код с проверкой на четность). Другой код Рида-Маллера может быть получен с использованием этих матриц, если мы положим г = 2. В этом случае порождающая матрица имеет вид

и задает (16, 11)-код над (2). (В действительности это (15, 11)-код Хэмминга, расширенный с помощью проверки на четность.)

Из определения порождающей матрицы ясно, что код Рида- Маллера г-го порядка может быть получен пополнением кода Рида-Маллера {г - 1)-го порядка, а код Рида-Маллера (г- 1)-го порядка получается из кода г-го порядка с помощью выбрасывания. Поскольку код Рида-Маллера г-го порядка содержит код (г - 1)-го порядка, ясно что его минимальное расстояние не может быть больше минимального расстояния кода (г - 1)-го порядка. В дальнейшем мы докажем, что код Рида-Маллера г-го порядка имеет минимальное расстояние d* = 2"-.