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

Как и в предыдущем параграфе вектор, пробегающий пространство вектор длины соответствующий булевой функции

Определение. Для произвольного двоичный код Рида-Маллера порядка и длины определяется как множество всех векторов задаваемых булевыми функциями, равными всем многочленам, степень которых не превосходит Например, РМ-код первого порядка длины 8 состоит из 16 слов вида где о; равны 0 или 1, и представлен на рис. 13.1,

Рис. 13.1. Код Рида — Маллера первого порядка длины 8

Этот код приведен также на рис. 1.14, и легко видеть, что код всегда дуален расширенному коду Хэмминга. Код совпадает также с кодом полученным в § 2.3 из матрицы Адамара типа Сильвестра.

Вес всех слов кода за исключением векторов 0 и 1, равен Действительно, согласно упражнению (2) любая булева функция степени 1 соответствует вектору веса

В общем случае РМ-код порядка состоит из всех линейных комбинаций векторов, соответствующих произведениям (вплоть до степени ), которые, таким образом, задают базис кода. Всего имеется

таких базисных векторов (как мы видели в § 13.2, все они линейно независимы). Следовательно, размерность кода равна

На рис. 13.2 в качестве примера приведены все 16 возможных базисных векторов для РМ-кодов длины (проверить!).

Базисными векторами для РМ кода порядка длины 16 являются:

Рис. 13 2, Базисные векторы РМ-кодов длины 16

РМ-коды длины очень просто могут быть получены из РМ-кодов длины при помощи конструкции из § 2.9. Теорема 2.

Например, именно таким способом в § 2.9 был построен код . Эквивалентное утверждение можно сформулировать для порождающих матриц. Пусть — порождающая матрица кода Тогда теорема означает, что

(Ясно, что кодовое слово, порождаемое этой матрицей, имеет форму где

Доказательство. Типичное слово кода соответствует многочлену степень которого не превосходит Можно записать (так же как в упражнении (1)), что

где и Пусть векторы (длины соответствующие функциям Очевидно, что Рассмотрим теперь как многочлен от Соответствующие им векторы (теперь уже длины равны (см. упражнение (7)). Следовательно,

Отметим сходство между рекурсией для РМ-кодов, описываемой теоремой 2, и рекуррентным соотношением для биноминальных коэффициентов:

(см. упражнение (4)).

Теорема 2 позволяет легко вычислить минимальное расстояние кодов Рида — Маллера.

Теорема 3. Минимальное расстояние кода равно

Доказательство. Индукцией по используя теорему 33 гл. 2.

На рис. 13.3 приведены размерности для нескольких первых кодов (проверить!).

Рис. 13.3. Коды Рида — Маллера

Заметим, что код состоит из всех векторов длины код из всех векторов четного веса, а код только из векторов 0 и 1 (упражнение (5)).

Теорема 4. Для всех код дуален коду

Доказательство Пусть Тогда» степень многочлена не превосходит а степень многочлена не превосходит так что степень произведения не превосходит Следовательно, и вес вектора четен. Таким образом, скалярное произведение (модулю 2). Следовательно, но

откуда вытекает, что

Свойства кодов Рида — Маллера подытожены на рис. 13.4.

Рис. 13.4. Свойства кодов Рида — Маллера

Выколотые коды Рида — Маллера. Определение. Для любого выколотым РМ кодом называется код» который получается из кода выкалыванием (или вычеркиванием) из всех кодовых слов координаты, соответствующей: нулевой -последовательности

(В следующем параграфе мы увидим, что на самом деле не существенно, какую из координат выколоть, — во всех случаях получаются эквивалентные коды.)

Очевидно, что код имеет длину минимальное расстояние и размерность

Упражнения. (3). Доказать, что является подкодомг кода Показать точнее, что

многочлен от степень которого равна точно

(4). Используя теорему 2 в качестве рекуррентного определения РМ кодов, вычислить на основании уравнения (13.5) размерность РМ «ода. Проверить рис. 13.3, используя треугольник Паскаля для биноминальных коэффициентов.

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

(6). Пусть Доказать, что где пробегает те смежные классы по коду которые содержатся в коде

(7). Пусть — булева функция от переменных, и пусть соответствующий двоичный вектор длины Доказать, что векторы, длины соответствующие многочленам равны