106 Глава 9. Другие коды
Таким образом, код Рида-Маллера RM(r, m) порядка r имеет параметры:
• длина кода равна n = 2
m
;
• мощность кода равна 2
k
, где k = 1 +
µ
m
1
¶
+ ··· +
µ
m
r
¶
;
• кодовое расстояние d = 2
m−r
.
Коды Рида-Маллера имеют быстрые процедуры кодирования и декодирования и
широко используются на практике, в частности, коды Рида-Маллера третьего поряд-
ка представляют собой хороший экземпляр кодов, которые могут быть использованы
в криптографии для шифрования информации в криптосистемах с открытыми клю-
чами, а именно в криптосистеме МакЭлиса.
Теорема 61. Для любых r, 0 ≤ r ≤ (m −1) код Рида-Маллера RM(m −r −1, m)
ортогонален коду Рида-Маллера RM(r, m).
Доказательство. Рассмотрим произвольные векторы f и g, где
f ∈ RM(m−r −1, m), g ∈ RM(r, m). По определению кодов Рида-Маллера, степени
многочленов f(x
1
, . . . , , x
m
) и g(x
1
, . . . , x
m
) не превосходят m−r−1 и r соответствен-
но. Следовательно, степень многочлена f(x
1
, . . . , x
m
) · g(x
1
, . . . , x
m
) не превосходит
m−1 и отвечающий этому многочлену вектор принадлежит коду RM(m−1, m). По-
скольку в коде RM(m−1, m) все вершины имеют четный вес, то есть скалярное про-
изведение векторов f и g равно нулю, то получаем RM(m −r −1, m) ⊆ RM(r, m)
⊥
.
Но
dimRM(m − r − 1, m) + dimRM(r, m) = 2
m
,
откуда следует, что
RM(m − r − 1, m) = RM(r, m)
⊥
,
что доказывает теорему. N
9.2.1. Коды с параметрами кодов Рида-Маллера
Выколотый код Рида-Маллера RM
∗
(r, m) получается удалением какой-либо ко-
ординаты и имеет параметры
(n = 2
m
− 1, M = 2
k
, d = 2
m−r
− 1), где k = 1 +
µ
m
1
¶
+ ··· +
µ
m
r
¶
.
Покажем, как, используя свитчинговые и каскадные конструкции, можно строить
мощные классы кодов с параметрами кодов Рида-Маллера и выколотых кодов Рида-
Маллера. Двоичные коды (не обязательно линейные) с параметрами выколотого кода
Рида-Маллера порядка r будем обозначать LRM
∗
(r, m) и называть выколотыми
кодами Рида-Маллера. Линейный код RM
∗
(r, m) является частным случаем кодов
LRM
∗
(r, m).
Сначала рассмотрим применение конструкции Васильева из теоремы 13. Посред-
ством этого метода построения кодов можно получить много нелинейных выколотых
кодов Рида-Маллера LRM
∗
(r, m)) порядка r.
Пусть LRM
∗
(r, m − 1) и LRM
∗
(r − 1, m − 1) — произвольные выколотые коды
Рида-Маллера порядков r и r − 1 соответственно длины n = 2
m−1
− 1. Справедливо
следующее утверждение: