Код Рида – Мюллера

Код Рида-Мюллера RM(r,m)
Назван в честь	Ирвинг С. Рид и Дэвид Э. Мюллер
Классификация
Тип	Линейный блочный код
Длина блока	$2^{m}$
Длина сообщения	$k=\sum _{i=0}^{r}{\binom {m}{i}}$
Ставка	$k/2^{m}$
Расстояние	$2^{m-r}$
Размер алфавита	$2$
Обозначения	$[2^{m},k,2^{m-r}]_{2}$-код

Коды Рида-Мюллера — это коды с исправлением ошибок , которые используются в приложениях беспроводной связи, особенно в связи в дальнем космосе. Более того, предлагаемый стандарт 5G опирается на тесно связанные полярные коды для исправления ошибок в канале управления. Благодаря своим благоприятным теоретическим и математическим свойствам коды Рида – Мюллера также широко изучались в теоретической информатике .

Коды Рида-Мюллера обобщают коды Рида-Соломона и код Уолша-Адамара . Коды Рида-Мюллера — это линейные блочные коды , которые можно локально тестировать , локально декодировать и декодировать списком . Эти свойства делают их особенно полезными при разработке вероятностно проверяемых доказательств .

Традиционные коды Рида-Мюллера представляют собой двоичные коды, а это означает, что сообщения и кодовые слова представляют собой двоичные строки. Когда r и m являются целыми числами с 0 ≤ r ≤ m , код Рида–Мюллера с параметрами r и m обозначается как RM( r , m ). Когда его просят закодировать сообщение, состоящее из k бит, где $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ выполняется, код RM( r , m ) создает кодовое слово, состоящее из 2 ^м биты.

Коды Рида-Мюллера названы в честь Дэвида Э. Мюллера , открывшего эти коды в 1954 году. и Ирвинг С. Рид , предложивший первый эффективный алгоритм декодирования.

Описание с использованием полиномов низкой степени

Коды Рида – Мюллера можно описать несколькими разными (но в конечном итоге эквивалентными) способами. Описание, основанное на полиномах низкой степени, весьма элегантно и особенно подходит для их применения в качестве локально проверяемых кодов и локально декодируемых кодов .

Кодер

Блочный код может иметь одну или несколько функций кодирования. ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ это отображает сообщения ${\textstyle x\in \{0,1\}^{k}}$ к кодовым словам ${\textstyle C(x)\in \{0,1\}^{n}}$. Код Рида-Мюллера RM( r , m ) имеет длину сообщения $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ и длина блока $\textstyle n=2^{m}$. Один из способов определить кодировку для этого кода основан на вычислении полилинейных полиномов с m переменными и общей степенью не более r . Любой полилинейный многочлен над конечным полем из двух элементов можно записать следующим образом: $$p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.$$ ${\textstyle Z_{1},\dots ,Z_{m}}$ являются переменными полинома, а значения ${\textstyle c_{S}\in \{0,1\}}$ являются коэффициентами многочлена. Обратите внимание, что существуют именно ${\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ коэффициенты. Учитывая это, входное сообщение состоит из ${\textstyle k}$ ценности ${\textstyle x\in \{0,1\}^{k}}$ которые используются в качестве этих коэффициентов. Таким образом, каждое сообщение ${\textstyle x}$ дает уникальный полином ${\textstyle p_{x}}$ в m переменных. Чтобы составить кодовое слово ${\textstyle C(x)}$, кодер оценивает полином ${\textstyle p_{x}}$ во всех точках ${\textstyle Z=(Z_{1},\ldots ,Z_{n})\in \{0,1\}^{m}}$, где полином берется с умножением и сложением по модулю 2 ${\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}$. То есть функция кодирования определяется через $$C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.$$

Тот факт, что кодовое слово $C(x)$ достаточно, чтобы однозначно восстановить $x$ следует из интерполяции Лагранжа , которая утверждает, что коэффициенты многочлена определяются однозначно, когда задано достаточно много оценочных точек. С $C(0)=0$ и $C(x+y)=C(x)+C(y){\bmod {2}}$ сохраняется для всех сообщений $x,y\in \{0,1\}^{k}$, функция $C$ представляет собой линейную карту . Таким образом, код Рида-Мюллера является линейным кодом .

Пример

Для кода RM( 2 , 4 ) параметры следующие:

${\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}$

Позволять ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ быть только что определенной функцией кодирования. Чтобы закодировать строку x = 1 1010 010101 длины 11, кодер сначала строит полином ${\textstyle p_{x}}$ в 4 переменных: $${\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}$$Затем он оценивает этот полином во всех 16 точках оценки (0101 означает $Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)$: $$p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;$$

$$p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;$$

$$p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;$$

$$p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.$$В результате имеет место C(1 1010 010101) = 1101 1110 0001 0010.

Декодер

Как уже упоминалось, интерполяцию Лагранжа можно использовать для эффективного извлечения сообщения из кодового слова. Однако декодер должен работать, даже если кодовое слово было повреждено в нескольких позициях, то есть когда полученное слово отличается от любого кодового слова. В этом случае может помочь процедура локального декодирования.

Алгоритм Рида основан на следующем свойстве: вы начинаете с кодового слова, которое представляет собой последовательность точек оценки неизвестного полинома ${\textstyle p_{x}}$ из ${\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}$ степени максимум ${\textstyle r}$ который вы хотите найти. Последовательность может содержать любое количество ошибок до ${\textstyle 2^{m-r-1}-1}$ включено.

Если рассматривать моном ${\textstyle \mu }$ высшей степени ${\textstyle d}$ в ${\textstyle p_{x}}$ и суммируем все точки оценки полинома, где все переменные в ${\textstyle \mu }$ имеют значения 0 или 1, а все остальные переменные имеют значение 0, вы получаете значение коэффициента (0 или 1) ${\textstyle \mu }$ в ${\textstyle p_{x}}$ (Есть ${\textstyle 2^{d}}$ такие моменты). Это связано с тем, что все младшие мономиальные делители ${\textstyle \mu }$ появляется в сумме четное количество раз, и только ${\textstyle \mu }$ появляется один раз.

Чтобы учесть возможность ошибок, можно также отметить, что значение других переменных можно зафиксировать на любое значение. Поэтому вместо того, чтобы суммировать только один раз для других переменных, не входящих в ${\textstyle \mu }$ со значением 0, вы делаете это ${\textstyle 2^{m-d}}$ раз для каждого фиксированного значения других переменных. Если ошибки нет, все эти суммы должны быть равны значению искомого коэффициента. Алгоритм заключается в том, чтобы принять большинство ответов в качестве искомого значения. Если меньшинство превышает максимально возможное количество ошибок, этап декодирования завершается неудачей, поскольку во входном коде слишком много ошибок.

После вычисления коэффициента, если он равен 1, обновите код, чтобы удалить моном. ${\textstyle \mu }$ от входного кода и переходим к следующему моному в порядке, обратном их степени.

Пример

Давайте рассмотрим предыдущий пример и начнем с кода. С ${\textstyle r=2,m=4}$ мы можем исправить максимум 1 ошибку в коде. Рассмотрим входной код как 1101 1110 0001 0110 (это предыдущий код с одной ошибкой).

Мы знаем степень многочлена ${\textstyle p_{x}}$ самое большее ${\textstyle r=2}$, начнем с поиска монома степени 2.

• ${\textstyle \mu =X_{3}X_{4}}$
  • мы начинаем с поиска точек оценки с помощью ${\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$. В коде это: 1101 1110 0001 0110. Первая сумма равна 1 (нечетное число 1).
  • мы ищем оценочные баллы с ${\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$. В коде это: 1101 1110 0001 0110. Вторая сумма равна 1.
  • мы ищем оценочные баллы с ${\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$. В коде это: 1101 1110 0001 0110. Третья сумма равна 1.
  • мы ищем оценочные баллы с ${\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$. В коде это: 1101 1110 0001 0110 . Третья сумма равна 0 (четное число 1).

Четыре суммы не согласуются (поэтому мы знаем, что есть ошибка), но отчет меньшинства не превышает максимально допустимое количество ошибок (1), поэтому мы берем большинство и коэффициент ${\textstyle \mu }$ это 1.

Мы удаляем ${\textstyle \mu }$ из кода перед продолжением: код: 1101 1110 0001 0110, оценка ${\textstyle \mu }$ 0001000100010001, новый код 1100 1111 0000 0111.

• ${\textstyle \mu =X_{2}X_{4}}$
  • 11 00 11 11 0000 0111. Сумма равна 0.
  • 11 00 11 11 0000 0111. Сумма равна 0.
  • 1100 1111 00 00 01 11. Сумма равна 1.
  • 1100 1111 00 00 01 11 . Сумма равна 0

Обнаружена одна ошибка, коэффициент равен 0, текущий код не изменяется.

• ${\textstyle \mu =X_{1}X_{4}}$
  • 11 00 1111 00 00 0111. Сумма равна 0.
  • 11 00 1111 00 00 0111. Сумма равна 0.
  • 1100 11 11 0000 01 11. Сумма равна 1.
  • 1100 11 11 0000 01 11 . Сумма равна 0

Обнаружена одна ошибка, коэффициент равен 0, текущий код не изменяется.

• ${\textstyle \mu =X_{2}X_{3}}$
  • 1 1 0 0 1 1 1 1 0000 0111. Сумма равна 1.
  • 1 1 0 0 1 1 1 1 0000 0111. Сумма равна 1.
  • 1100 1111 0 0 0 0 0 1 1 1. Сумма равна 1.
  • 1100 1111 0 0 0 0 0 1 1 1 . Сумма равна 0

Обнаружена одна ошибка, коэффициент 1, оценка ${\textstyle \mu }$ 0000 0011 0000 0011, текущий код теперь 1100 1100 0000 0100.

• ${\textstyle \mu =X_{1}X_{3}}$
  • 1 1 0 0 1100 0 0 0 0 0100. Сумма равна 1.
  • 1 1 0 0 1100 0 0 0 0 0100. Сумма равна 1.
  • 1100 1 1 0 0 0000 0 1 0 0. Сумма равна 1.
  • 1100 1 1 0 0 0000 0 1 0 0 . Сумма равна 0

Обнаружена одна ошибка, коэффициент 1, оценка ${\textstyle \mu }$ 0000 0000 0011 0011, текущий код сейчас 1100 1100 0011 0111.

• ${\textstyle \mu =X_{1}X_{2}}$
  • 1 100 1 100 0 011 0 111. Сумма равна 0.
  • 1 1 00 1 1 00 0 0 11 0 1 11. Сумма равна 1.
  • 11 0 0 11 0 0 00 1 1 01 1 1. Сумма равна 0
  • 110 0 110 0 001 1 011 1 . Сумма равна 0

Обнаружена одна ошибка, коэффициент равен 0, текущий код не изменяется. Теперь мы знаем все коэффициенты степени 2 для многочлена, можем начать монониалы степени 1. Обратите внимание, что для каждой следующей степени сумм в два раза больше, и каждая сумма вдвое меньше.

• ${\textstyle \mu =X_{4}}$
  • 11 00 1100 0011 0111. Сумма равна 0.
  • 11 00 1100 0011 0111. Сумма равна 0.
  • 1100 11 00 0011 0111. Сумма равна 0.
  • 1100 11 00 0011 0111. Сумма равна 0.
  • 1100 1100 00 11 0111. Сумма равна 0.
  • 1100 1100 00 11 0111. Сумма равна 0.
  • 1100 1100 0011 01 11. Сумма равна 1.
  • 1100 1100 0011 01 11 . Сумма равна 0

Обнаружена одна ошибка, коэффициент равен 0, текущий код не изменяется.

• ${\textstyle \mu =X_{3}}$
  • 1 1 0 0 1100 0011 0111. Сумма равна 1.
  • 1 1 0 0 1100 0011 0111. Сумма равна 1.
  • 1100 1 1 0 0 0011 0111. Сумма равна 1.
  • 1100 1 1 0 0 0011 0111. Сумма равна 1.
  • 1100 1100 0 0 1 1 0111. Сумма равна 1.
  • 1100 1100 0 0 1 1 0111. Сумма равна 1.
  • 1100 1100 0011 0 1 1 1. Сумма равна 1.
  • 1100 1100 0011 0 1 1 1 . Сумма равна 0

Обнаружена одна ошибка, коэффициент 1, оценка ${\textstyle \mu }$ 0011 0011 0011 0011, текущий код сейчас 1111 1111 0000 0100.

Тогда мы найдем 0 для ${\textstyle \mu =X_{2}}$, 1 для ${\textstyle \mu =X_{1}}$ и текущий код станет 1111 1111 1111 1011.

Для степени 0 у нас есть 16 сумм всего по 1 биту. Меньшинство по-прежнему имеет размер 1, и мы обнаружили ${\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}$ и соответствующее начальное слово 1 1010 010101

Обобщение на более крупные алфавиты с помощью полиномов низкой степени

Использование полиномов низкой степени над конечным полем $\mathbb {F}$ размера $q$, можно распространить определение кодов Рида–Мюллера на алфавиты размера $q$. Позволять $m$ и $d$ — целые положительные числа, где $m$ следует рассматривать как нечто большее, чем $d$. Чтобы закодировать сообщение ${\textstyle x\in \mathbb {F} ^{k}}$ ширины $k=\textstyle {\binom {m+d}{m}}$, сообщение снова интерпретируется как $m$-вариативный полином $p_{x}$ общей степени не более $d$ и с коэффициентом от $\mathbb {F}$. Такой полином действительно имеет $\textstyle {\binom {m+d}{m}}$ коэффициенты. Кодировка Рида-Мюллера $x$ список всех оценок $p_{x}(a)$ общий $a\in \mathbb {F} ^{m}$. Таким образом, длина блока равна $n=q^{m}$.

Описание с помощью порождающей матрицы

Матрица -генератор для кода Рида – Маллера RM( r , m ) длины N = 2 ^м можно построить следующим образом. Запишем набор всех m -мерных двоичных векторов как:

$X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.$

Определим в N -мерном пространстве $\mathbb {F} _{2}^{N}$ векторы индикаторов

$\mathbb {I} _{A}\in \mathbb {F} _{2}^{N}$

на подмножествах $A\subset X$ к:

$\left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}$

вместе с, также в $\mathbb {F} _{2}^{N}$, бинарная операция

$w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),$

называется клиновым произведением (не путать с клиновым произведением, определенным во внешней алгебре). Здесь, $w=(w_{1},w_{2},\ldots ,w_{N})$ и $z=(z_{1},z_{2},\ldots ,z_{N})$ являются точками в $\mathbb {F} _{2}^{N}$ ( N -мерные двоичные векторы) и операция $\cdot$ — обычное умножение в поле $\mathbb {F} _{2}$.

$\mathbb {F} _{2}^{m}$ представляет собой m -мерное векторное пространство над полем $\mathbb {F} _{2}$, поэтому можно написать

$(\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.$

Определим в N -мерном пространстве $\mathbb {F} _{2}^{N}$ следующие векторы длиной $N:v_{0}=(1,1,\ldots ,1)$ и

$v_{i}=\mathbb {I} _{H_{i}},$

где 1 ≤ i ≤ m и H _i — гиперплоскости в $(\mathbb {F} _{2})^{m}$ (размерностью m − 1 ):

$H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.$

Генераторная матрица

код Рида–Мюллера RM( r , m ) порядка r и длины N = 2. ^м - это код, сгенерированный v ₀ и секционными произведениями до r из v _i , 1 ≤ i ≤ m (где по соглашению клиновое произведение менее одного вектора является идентификатором операции). Другими словами, мы можем построить матрицу-генератор для кода RM( r , m ) , используя векторы и их перестановки клиновых произведений до r за раз. ${v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}$, как строки порождающей матрицы, где 1 ≤ i _k ≤ m .

Пример 1

Пусть m = 3. Тогда N = 8 и

$X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},$

и

${\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}$

Код RM(1,3) генерируется набором

$\{v_{0},v_{1},v_{2},v_{3}\},\,$

или более явно по строкам матрицы:

${\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}$

Пример 2

Код RM(2,3) генерируется набором:

$\{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}$

или более явно по строкам матрицы:

${\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}$

Характеристики

Имеются следующие свойства:

1. Набор всех возможных клиновых произведений размером до m из vi _{образует} основу для $\mathbb {F} _{2}^{N}$.
2. Код RM ( r , m ) имеет ранг

   $\sum _{s=0}^{r}{m \choose s}.$

3. РМ ( р , м ) знак равно РМ ( р , м - 1) | RM ( r − 1, m − 1) , где '|' обозначает штриховое произведение двух кодов.
4. RM ( r , m ) имеет минимальный вес Хэмминга 2. ^{м - р} .

Доказательство

1. Есть

   $\sum _{s=0}^{m}{m \choose s}=2^{m}=N$

   такие векторы и $\mathbb {F} _{2}^{N}$ имеют размерность N, поэтому достаточно проверить, что N векторов охватывают; эквивалентно, достаточно проверить, что $\mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}$.

   Пусть x двоичный вектор длины m , элемент X. — Пусть ( x ) _i обозначает i ^й элемент х . Определять

   $y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}$

   где 1 ≤ я ≤ м .

   Затем $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$

   Разложение за счет распределительности клинового произведения дает $\mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)$. Тогда, поскольку векторы $\{\mathbb {I} _{\{x\}}\mid x\in X\}$ охватывать $\mathbb {F} _{2}^{N}$ у нас есть $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$.
2. По значению 1 все такие клиновые произведения должны быть линейно независимыми, поэтому ранг RM( r, m ) должен быть просто количеством таких векторов.
3. Опущено.
4. По индукции.

   Код RM(0, m ) представляет собой код повторения длины N =2. ^м и вес N = 2 ^{м −0} = 2 ^{м - р} . на 1 $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ и имеет вес 1 = 2 ⁰ = 2 ^{м - р} .

   В статье « Стержневое произведение (теория кодирования)» доказано, что вес штрихового произведения двух кодов C ₁ , C ₂ определяется выражением

   $\min\{2w(C_{1}),w(C_{2})\}$

   Если 0 < r < m и если

   1. RM( r , m − 1) имеет вес 2 ^{м −1− р}
   2. RM( r − 1, m − 1) имеет вес 2 ^{м −1−( r −1)} = 2 ^{м - р}

   тогда батончик имеет вес

   $\min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.$

Расшифровка кодов РМ

Коды RM( r , m ) могут быть декодированы с использованием мажоритарного логического декодирования . Основная идея мажоритарного логического декодирования заключается в следующем. построить несколько контрольных сумм для каждого полученного элемента кодового слова. Поскольку каждая из различных контрольных сумм должна быть имеют одинаковое значение (т. е. значение веса элемента слова сообщения), мы можем использовать мажоритарное логическое декодирование для расшифровки значение элемента слова сообщения. После декодирования каждого порядка полинома полученное слово модифицируется. соответственно, путем удаления соответствующих кодовых слов, взвешенных по вкладам декодированного сообщения, до настоящего этапа. Таким образом, для RM-кода r- го порядка нам придется итеративно декодировать r+1 раз, прежде чем мы придем к окончательному результату. получено кодовое слово. Кроме того, значения битов сообщения рассчитываются по этой схеме; наконец-то мы можем рассчитать кодовое слово путем умножения слова сообщения (только что декодированного) на матрицу генератора.

Одним из признаков успешного декодирования является наличие модифицированного полученного слова, состоящего из всех нулей, в конце ( r + 1)-этапа декодирования. посредством мажоритарного логического декодирования. Этот метод был предложен Ирвингом С. Ридом и является более общим при применении. другим кодам конечной геометрии.

Описание с использованием рекурсивной конструкции

Код Рида – Мюллера RM( r,m ) существует для любых целых чисел. $m\geq 0$ и $0\leq r\leq m$. RM( m , m ) определяется как вселенная ( $2^{m},2^{m},1$) код. RM(−1,m) определяется как тривиальный код ( $2^{m},0,\infty$). Остальные коды RM могут быть построены из этих элементарных кодов с использованием конструкции удвоения длины.

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

Из этой конструкции RM( r,m ) представляет собой двоичный линейный блочный код ( n , k , d ) длины n = 2. ^м , измерение $k(r,m)=k(r,m-1)+k(r-1,m-1)$ и минимальное расстояние $d=2^{m-r}$ для $r\geq 0$. Двойственный код к RM( r,m ) — это RM( m - r -1, m ). Это показывает, что повторение и SPC-коды двойственны, биортогональные и расширенные коды Хэмминга двойственны и что коды с k = n /2 самодуальны.

Особые случаи кодов Рида – Мюллера.

Таблица всех кодов RM(r,m) для m≤5

Все коды RM( r , m ) с $0\leq m\leq 5$ и размер алфавита 2 отображаются здесь с аннотациями стандартной теории кодирования [n,k,d] для блочных кодов . Код RM( r , m ) представляет собой $\textstyle [2^{m},k,2^{m-r}]_{2}$-код, то есть линейный код в двоичном алфавите , имеет длину блока $\textstyle 2^{m}$, сообщения длина (или размерность) k и минимальное расстояние $\textstyle 2^{m-r}$.

0	1	2	3	4	5	м
						РМ( м,м ) ( 2 м , 2 м , 1)	коды вселенной
					РМ(5,5) (32,32,1)
				РМ(4,4) (16,16,1)		RM( м - 1, м ) (2 м , 2 м −1, 2)	SPC Коды
			РМ(3,3) (8,8,1)		РМ(4,5) (32,31,2)
		РМ(2,2) (4,4,1)		РМ(3,4) (16,15,2)		RM( м - 2, м ) (2 м , 2 м − м −1, 4)	расширенные коды Хэмминга
	РМ(1,1) (2,2,1)		РМ(2,3) (8,7,2)		РМ(3,5) (32,26,4)
РМ(0,0) (1,1,1)		РМ(1,2) (4,3,2)		РМ(2,4) (16,11,4)
	РМ(0,1) (2,1,2)		РМ(1,3) (8,4,4)		РМ(2,5) (32,16,8)	RM( р , м =2 р +1) (2 2 р +1 , 2 2 р , 2 р +1 )	самодвойственные коды
РМ(-1,0) (1,0, $\infty$)		РМ(0,2) (4,1,4)		РМ(1,4) (16,5,8)
	РМ(-1,1) (2,0, $\infty$)		РМ(0,3) (8,1,8)		РМ(1,5) (32,6,16)
		РМ(-1,2) (4,0, $\infty$)		РМ(0,4) (16,1,16)		RM(1, м ) (2 м , м +1, 2 м −1 )	проколотые коды Адамара
			РМ(-1,3) (8,0, $\infty$)		РМ(0,5) (32,1,32)
				РМ(-1,4) (16,0, $\infty$)		RM(0, м ) (2 м , 1, 2 м )	коды повторения
					РМ(-1,5) (32,0, $\infty$)
						RM(−1, м ) (2 м , 0, ∞)	тривиальные коды

Свойства кодов RM(r,m) при r≤1 или r≥m-1

• RM(0, m ) Коды представляют собой коды повторения длины N = 2. ^м , ставка ${R={\tfrac {1}{N}}}$ и минимальное расстояние $d_{\min }=N$.
• RM(1, m ) Коды представляют собой коды проверки четности длины N = 2. ^м , ставка $R={\tfrac {m+1}{N}}$ и минимальное расстояние $d_{\min }={\tfrac {N}{2}}$.
• RM( m − 1, m ) Коды представляют собой коды одинарной проверки на четность длины N = 2. ^м , ставка $R={\tfrac {N-1}{N}}$ и минимальное расстояние $d_{\min }=2$.
• Коды RM( m − 2, m ) представляют собой семейство расширенных кодов Хэмминга длины N = 2. ^м с минимальным расстоянием $d_{\min }=4$.

Дальнейшее чтение

• Шу Линь; Дэниел Костелло (2005). Кодирование контроля ошибок (2-е изд.). Пирсон. ISBN  978-0-13-017973-9 . Глава 4.
• Дж. Х. ван Линт (1992). Введение в теорию кодирования . ГТМ . Том. 86 (2-е изд.). Спрингер-Верлаг . ISBN  978-3-540-54894-2 . Глава 4.5.

Внешние ссылки

• MIT OpenCourseWare , 6.451 Принципы цифровой коммуникации II, конспект лекций, раздел 6.4
• GPL Matlab-реализация RM-кодов
• Исходный код GPL Matlab-реализация RM-кодов
• Вайс, Э. (сентябрь 1962 г.). «Обобщенные коды Рида-Мюллера». Информация и контроль . 5 (3): 213–222. дои : 10.1016/s0019-9958(62)90555-7 . ISSN   0019-9958 .