Код Рида-Маллера: параметры, построение и декодирование

Коды Рида-Маллера - один из первых семейств линейных блоковых кодов, у которых параметры выводятся прямо из двух чисел $r$ и $m$, а декодирование сводится к простому голосованию. Их любят в учебных курсах теории кодирования: на них наглядно видно, как растёт избыточность ради надёжности, и как одна и та же конструкция даёт целую решётку кодов от повторения до проверки на чётность. Ниже разберём, как по $r$ и $m$ посчитать длину, размерность и кодовое расстояние, откуда берётся рекурсивная схема $(u \mid u+v)$ и как работает мажоритарное декодирование. Чтобы сразу прикинуть параметры для своих $r$ и $m$, покрутите калькулятор.

Что такое код Рида-Маллера

Код Рида-Маллера $RM(r, m)$ - это двоичный линейный код, кодовые слова которого получаются как значения булевых функций степени не выше $r$ от $m$ переменных. Каждое кодовое слово - это таблица истинности такой функции, выписанная по всем $2^m$ наборам аргументов. Параметр $m$ задаёт число переменных (и тем самым длину блока), а $r$ - максимальную степень многочлена, то есть «богатство» кодируемых функций.

Чем больше $r$, тем больше различных функций мы можем закодировать (выше размерность), но тем меньше гарантированное различие между словами (ниже расстояние). Эта пара $(r, m)$ полностью определяет код: ни таблиц, ни перебора порождающих матриц для вычисления базовых параметров не нужно.

Частные случаи задают «края» семейства. При $r = 0$ получается код повторения длины $2^m$, при $r = m - 1$ - код проверки на чётность, а $RM(1, m)$ тесно связан с кодами Адамара. Между этими крайностями лежит вся практическая середина.

Длина, размерность и расстояние

Три ключевых параметра кода $RM(r, m)$ считаются по компактным формулам.

Длина блока - это число всех наборов аргументов булевой функции:

$$n = 2^m$$

Размерность (число информационных бит) равна количеству одночленов степени не выше $r$ от $m$ переменных, то есть сумме биномиальных коэффициентов:

$$k = \sum_{i=0}^{r} \binom{m}{i}$$

Минимальное кодовое расстояние, от которого зависит способность исправлять ошибки:

$$d = 2^{m-r}$$

Рассчитать для своей задачи

Например, для $RM(1, 3)$ получаем $n = 8$, $k = \binom{3}{0} + \binom{3}{1} = 1 + 3 = 4$ и $d = 2^{3-1} = 4$. Это код $[8, 4, 4]$ - он способен исправлять одну ошибку и обнаруживать ещё одну. Скорость кода $R = k/n = 1/2$ - ровно половина бит несёт данные, остальное уходит на избыточность ради помехоустойчивости; теоретический предел такой избыточности в зашумлённом канале задаёт формула Шеннона.

Рекурсивное построение: схема u, u+v

Самый изящный способ строить коды Рида-Маллера - рекурсия Плоткина $(u \mid u+v)$. Кодовое слово $RM(r, m)$ длины $2^m$ собирается из двух половин длины $2^{m-1}$:

$$RM(r, m) = \{\, (u \mid u+v) : u \in RM(r, m-1),\ v \in RM(r-1, m-1) \,\}$$

Левая половина $u$ берётся из кода той же степени $r$, но на единицу меньшей размерности по переменным, а правая половина - это $u + v$, где $v$ приходит из кода степени $r-1$. Сложение здесь побитовое по модулю 2.

Эта конструкция объясняет рекуррентные соотношения для параметров: длина удваивается ($n_m = 2 n_{m-1}$), размерность складывается из размерностей двух меньших кодов, а расстояние нового кода равно меньшему из $2 d(RM(r,m-1))$ и $d(RM(r-1,m-1))$ - что и даёт ровно $2^{m-r}$.

Базовые случаи рекурсии: $RM(0, m)$ - код повторения (всё слово состоит из одинаковых бит), а $RM(m, m)$ - полное пространство $\mathbb{F}_2^{2^m}$ без избыточности. Раскручивая $(u \mid u+v)$ от этих оснований, можно получить порождающую матрицу любого кода семейства.

Порождающая матрица

Порождающая матрица $RM(r, m)$ строится из строк-индикаторов одночленов. Каждая переменная $x_j$ задаёт строку длины $2^m$, в которой стоит её значение на всех наборах; произведения переменных дают строки для одночленов высших степеней.

Берём все одночлены $x_{j_1} x_{j_2} \cdots x_{j_s}$ степени $s \le r$ (включая пустое произведение - строку из одних единиц для степени 0) и выписываем их таблицы значений. Совокупность этих $k$ строк и есть порождающая матрица. Её строки линейно независимы, поэтому ранг равен размерности $k$.

Удобно, что строки естественно группируются по степеням: одна строка степени 0, $m$ строк степени 1, $\binom{m}{2}$ строк степени 2 и так далее. Сумма этих количеств до степени $r$ и даёт формулу размерности из предыдущего раздела.

Мажоритарное декодирование

Главная практическая ценность кодов Рида-Маллера - простое декодирование по большинству (мажоритарное, алгоритм Рида). Идея в том, что каждый информационный бит можно восстановить несколькими независимыми способами - через разные «проверочные суммы» принятого слова, - а итоговое значение определяется голосованием.

Рассчитать для своей задачи

Декодирование идёт по слоям, от старшей степени к младшей. Для каждого коэффициента старшего одночлена составляется набор проверочных сумм; их у каждого коэффициента ровно $2^{m-r}$, и большинство из них указывает на правильное значение, пока число ошибок не превышает порога. Восстановив старший слой, его вклад вычитают из принятого слова и переходят к следующему слою с меньшей степенью.

Код $RM(r, m)$ с расстоянием $d = 2^{m-r}$ гарантированно исправляет до

$$t = \left\lfloor \frac{d-1}{2} \right\rfloor = 2^{m-r-1} - 1$$

ошибок. Голосование устойчиво, пока ошибок не больше $t$: даже если часть проверок сбита, верное значение остаётся в большинстве. Это устойчивость через избыточность: одно и то же значение подтверждается многими независимыми проверками, и пока ошибок мало, большинство всегда право.

Где применяются

Коды Рида-Маллера ценны там, где нужна простая аппаратная реализация и устойчивость к большому числу ошибок при умеренной скорости. Классический исторический пример - код $RM(1, 5)$ длины 32, которым кодировались снимки с межпланетной станции «Маринер-9»: он исправлял до 7 ошибок в каждом 32-битном блоке.

Сегодня семейство востребовано в нескольких областях:

• Связь и хранение - там, где канал сильно зашумлён, а декодер должен быть быстрым и дешёвым.
• Теория сложности и криптография - $RM$-коды связаны с тестированием функций на близость к многочленам низкой степени.
• Полярные коды - современные полярные коды, принятые в стандарте 5G, родственны кодам Рида-Маллера по структуре рекурсивного построения.

Частые ошибки

• Путают $r$ и $m$ местами в формулах. Длина зависит только от $m$ ($n = 2^m$), а расстояние - от разности $m - r$. Поменяв их, получите неверный код.
• Считают расстояние как $2^r$ вместо $2^{m-r}$. Запомните: чем выше степень $r$, тем расстояние меньше, а не больше.
• Забывают слагаемое $\binom{m}{0} = 1$ в сумме для размерности. Степень 0 - это строка из единиц, она всегда входит в базис.
• Берут $t = d/2$ вместо $\lfloor (d-1)/2 \rfloor$. При чётном $d$ (а у $RM$ оно всегда степень двойки) число исправляемых ошибок на единицу меньше половины расстояния.
• Считают мажоритарное декодирование единственным. Для $RM(1, m)$ выгоднее быстрое преобразование Адамара, оно работает за $O(n \log n)$.

FAQ

Чем код Рида-Маллера отличается от кода Рида-Соломона? Это разные семейства. Код Рида-Маллера двоичный и строится из булевых функций многих переменных; код Рида-Соломона работает над большим полем $\mathbb{F}_q$ и опирается на многочлены одной переменной. У них разные применения и разные алгоритмы декодирования.

Какое кодовое расстояние у $RM(2, 4)$? По формуле $d = 2^{m-r} = 2^{4-2} = 4$. Размерность $k = \binom{4}{0} + \binom{4}{1} + \binom{4}{2} = 1 + 4 + 6 = 11$, длина $n = 16$. Получается код $[16, 11, 4]$, исправляющий одну ошибку.

Почему $RM(1, m)$ называют кодом, связанным с Адамаром? Кодовые слова $RM(1, m)$ без постоянной составляющей - это строки матрицы Адамара в $\pm 1$-форме. Поэтому декодирование $RM(1, m)$ сводится к быстрому преобразованию Адамара: ищется строка, наиболее коррелированная с принятым словом.

Коротко

Код Рида-Маллера $RM(r, m)$ полностью задаётся парой чисел: длина $n = 2^m$, размерность $k = \sum_{i=0}^{r} \binom{m}{i}$, расстояние $d = 2^{m-r}$. Он строится рекурсией Плоткина $(u \mid u+v)$ из меньших кодов, а декодируется голосованием по большинству, исправляя до $t = 2^{m-r-1} - 1$ ошибок. Рост $r$ повышает размерность ценой расстояния - это и есть основной компромисс семейства.