algebcodes (1)

Теорема 4.9.1. Строки матрицы Mm линейно независимы.

Д о к а з а т е л ь с т в о. Переставим строки матрицы, располагая их сверху вниз в следующем порядке:

—Сначала всевозможные различные произведения векторов, не содержащие множителем вектор vm,

—Затем все остальные.

мы, читатель легко докажет, что таковы и строки матрицы

Mm. Тем самым будет произведен индукционный шаг. Невырожденность же матрицы

[ 1 1 ]

M1 = 0 1

очевидна. На случай m = 5 матрица (4.9.26) изображена в примере 4.8.

Определение 4.9.2. Кодом Рида — Маллера r-го порядка называется код длины n = 2m, порождающая матрица которого образована всеми различными произведениями векторов vi (i = 0, 1, . . . , m), состоящими из r и менее сомножителей.

Из этого определения следует, что РМ-код r-го порядка —

это линейный код, число информационных символов которого выражается соотношением

Порождающую матрицу РМ-кода r-го порядка будем обозна-

чать символом Mmr . Легко видеть, что РМ-код порядка r = m

— это все пространство двоичных векторов длины n = 2m, и потому его рассмотрение не представляет интереса.

П р и м е р 4. 7.

Процесс формирования матрицы Mm на случай m = 5.

точности 2m−l единиц, так как в любых l векторах vi1 , vi2 , . . . , vil имеется именно такое число компонент, которые во всех l векторах содержат единицы. Единственный вектор нечетного веса в матрице Mm, согласно правилу (4.9.25), это вектор v0vmvm−1 . . . v1, так как в одном наборе векторов v0, vm, vm−1, . . . , v1, и только

в нем существует в точности 2m−m = 1 компононта, в которой все эти векторы равны 1. Но этот вектор принадлежит только коду порядка r = m. Таким образом, в порождающей матри-

це Mmr нетривиального РМ-кода (r < m) все векторы четного веса. Применяя аналогичные рассуждения, получим, что все векторы в любом РМ-коде порядка r < m имеют четный вес.

Произведение двух базисных векторов двух РМ-кодов порядков r и m − r − 1 содержит не более чем m − 1 различных

сомножителей vi. Отсюда следует, что скалярное произведение двух этих векторов содержит заведомо четное число единиц,

а потому равно нулю. Отсюда следует, что РМ-код порядка r < m является нулевым пространством для РМ-кода порядка

m−r−1. Действительно, размерность РМ-код порядка m−r−1 есть

Сумма размерностей (4.9.27) и (4.9.29) в точности равна длине n = 2m кода, т.е. размерности пространства E2(n) :

Рассмотрим, порождающую матрицу РМ-кода первого порядка. Нулевым подпространством строк этой матрицы, согласно предыдущим рассуждениям является РМ-код порядка r = m−2. Если из этой порождающей матрицы удалить строку v0 и образовавшийся нулевой столбец, то получим матрицу, в которой все 2m − 1 ненулевых столбцов расположены в лексикографическом порядке. Не придавая значения порядку следования столбцов (ибо, как мы знаем, он не влияет на корректирующую способность кода), мы узнаем в этой матрице проверочную матрицу кода Хэмминга. Например, для случая m = 3 в этой матрице мы узнаем матрицу (0.4.11) для кода Хэмминга при m = 3. Так же будет и в общем случае при любом m. Это означает только, что РМ-код порядка r = m − 2 есть рас-

ширенный код Хемминга, а порождающая матрица РМ-кода первого порядка есть проверочная матрица расширенного кода

Хэмминга. Это означает также, что выколотый РМ-код порядка r = m − 2 есть код Хэмминга. Это в свою очередь значит, что код Хэмминга, как и все РМ-коды, о чем подробно изложено ниже, допускает мажоритарное декодирование. Однако в связи с простейшим способом декодирования кода Хэминга,

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

Здесь же обратим внимание на один частный случай, когда m = 3. Так как 3 − 2 = 1, то при m = 3 РМ-код (m − 2)− го порядка есть также и РМ-код первого порядка. Иначе говоря, расширенный (8, 4)-код Хэмминга (РМ-код первого и одновременно (m − 2)− го порядка) самоортогонален (т.е. самодвойственный). В этом, кстати, легко убедиться и непосредственно: числа информационных и проверочных символов совпадают, и скалярные произведения строк в каждой из матриц (4.7.14) и (4.7.15) равны нулю.

Теорема 4.9.3. Минимальное кодовое расстояние d(m, r) РМкода длины 2m, порядка r выражается равенством

Д о к а з а т е л ь с т в о. Предположим, что равенство (4.9.30) справедливо для некоторого m − 1 при всех r ≤ m − 1, и покажем, что оно справедливо для m при всех r ≤ m.

Расположим строки матрицы Mmr в следующем порядке:

— Сначала все rj=0Cmj −1 различных произведений векто-

ров v0, vm−1, . . . , v1 по одному, по два,..., по r (вектор vm не входит ни в одно из них; вектор v0 есть единственный базисный вектор кода порядка r = 0, а его вхождение или невхождение в какое-нибудь произведение строк никак не проявляется: умножение на 1 не вносит в произведение ничего нового: "истинный конъюнктивный член может быть отброшен".)

— Затем rj=0Cmj −1 различных произведений векторов по

одному, по два,..., по r, обязательно содержащих сомножитель vm. После этого матрица Mmr примет вид

Легко видеть, что при r = m совпадают как матрицы Mm и Mmm, так и способы их построения; надо только принять во внимание что при r = m имеет место Cmr −1 = 0, и при этом

условии Mmr −1 = Mmm−−11. (Продолжение доказательства на стр. 138).

П р и м е р 4. 9.

Процесс формирования РМ-кода на случай m = 5 и r = 3.

Из определения РМ-кода следует, что РМ-код порядка r1

целиком содержится в РМ-коде порядка r2 > r1. Далее, для каждого не сплошь нулевого кодового вектора, являющегося

линейной комбинацией строк матрицы (4.9.31), имеет место од-

но из двух: либо и правый и левый его отрезки длины 2m−1 не сплошь нулевые, и тогда по предположению индукции их веса

не меньше, чем 2m−r−1, а значит, вес всего вектора не меньше,

чем 2·2m−r−1 = 2m−r, либо один из этих отрезков сплошь нулевой, и, значит, другой отрезок с необходимостью принадлежит

коду длины 2m−1 и порядка r − 1, а тогда по предположению индукции минимальный вес таких отрезков равен в точности

2m−1−(r−1) = 2m−r. Вспомним теперь, что в линейном коде значения попарных расстояний исчерпываются весами кодовых векторов. Остается заметить, что при m = r = 1 равенство d(1, 1) = 1 очевидно, чем и завершается доказательство.

4.10. Кодирование кода Рида—Маллера

Кодирование для РМ-кода происходит обычным образом (см. (4.2.1)). Подлежащий кодированию информационный вектор u = (u1, u2, . . . , uk) умножается на порождающую матрицу

Mmr . Результатом процесса кодирования является кодовый век-

тор b = br = (br1, br2, . . . , brn) = uMmr . Иначе говоря, каждая строка матрицы Mmr умножается скалярно на соответствую-

щий символ вектора u, а затем эти произведения складываются поразрядно по модулю два. Помня, что строки матрицы Mmr

обозначены символами 2

v0, vm, . . . , v1, vmvm−1, vmvm−2, . . . , vrvr−1 · · · v1,

обозначим соответствующие им компоненты вектора u символами

u0, um, . . . , u1, um,m−1, um,m−2, . . . , ur,r−1, ... ,1. (4.10.34)

Таким образом,

b = b(r) = (b(1r), b(2r), . . . , b(nr)) = u0v0 + umvm + . . . + u1v1+

2Вообще говоря, нижние индексы могут располагаться в любом поряд-

ке. Расположение их в порядке убывания предпринято здесь только ради сохранения стиля

+um,m−1vmvm−1 + . . . + u21v2v1 + . . . + ur,r−1,...1vrvr−1 . . . v1

(4.10.35) Символы (4.10.34) — информационные, и символ uilil−1...i1 , на который умножается вектор vil vil−1 · · · vi1 , называется информационным символом l−го порядка.

Итак, вектор (4.10.35) представляет собой вектор РМ-кода r-го порядка, отвечающий информационному вектору

u = (u0, um, . . . , u1, um,m−1, um,m−2, . . . , ur,r−1, ... ,1.)

(4.10.36) Читатель, знакомый с булевой алгеброй, заметил, что сумма в правой части равенства (4.10.35) есть в точности многочлен Жегалкина от переменных vi. Информационные символы являются его коэффициентами. В соответствии с (4.10.36) все ин-

формационные символы порядка выше, чем r, заведомо равны нулю.

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

4.11.Сложность кодирования кода Рида — Маллера

Легко видеть, что кодирование для РМ-кода реализуется только посредством операций суммирования, так как операция умножения в (4.10.35) есть операция умножения на константу 1 или 0, а это не требует никаких новых действий. Обращаясь к (4.9.31), видим, что в соответствии со строением матрицы Mmr суммы (4.10.35) можно разбить на две. К первой, обозна-

чим ее символом b(vm), отнесем те векторы-слагаемые, которые не содержат vm в качестве сомножителя. Эти векторы получаются умножением на соответствующие информационные символы строк верхней полосы матрицы (4.9.31). Для получения

вектора-суммы b(vm) достаточно просуммировать только пра-

вые отрезки длины 2m−1 входящих в него векторов-слагаемых. Тем самым будут вычислены и левые отрезки такой же длины, вследствие строения матрицы (4.9.31).

Ко второй сумме, обозначим ее символом b(vm), отнесем те векторы-слагаемые, которые содержат вектор vm в каче-

стве сомножителя. Левые отрезки длины 2m−1 этих векторов

— сплошь нулевые, и потому суммировать следует опять-таки только правые отрезки вектора b(vm).

Пусть векторы b((vm)) и b(vm) уже получены. Тогда для получения их суммы b = br = b(vm) + b(vm) требуется еще

2m−1 двуместных операций сложения их компонент. Обозначим через Qrm число операций сложения для полу-

чения вектора (4.10.35). Тогда из (4.9.31) следует

Mmm−1 = Mmm−−11,

Опираясь на рекуррентное соотношение (4.11.37), можно найти величину Qrm. Этому служит следующая

Теорема 4.11.1.

Д о к а з а т е л ь с т в о будем вести индукцией по m. Предположим, что теорема верна для m − 1 при всех r ≤ m −1. Тогда в силу (4.11.37) имеем