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

Коды исправления ошибок, используемые в беспроводной связи

Коды Рида-Маллера являются кодами исправления ошибок , которые используются в беспроводных коммуникационных приложениях, особенно в дальнем космосе. ^[1] Более того, предлагаемый стандарт 5G ^[2] опирается на тесно связанные полярные коды ^[3] для исправления ошибок в канале управления. Благодаря своим благоприятным теоретическим и математическим свойствам коды Рида-Маллера также широко изучались в теоретической информатике .

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

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

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

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

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

Кодировщик

Блочный код может иметь одну или несколько функций кодирования , которые сопоставляют сообщения кодовым словам . Код Рида-Маллера RM( r , m ) имеет длину сообщения и длину блока . Один из способов определения кодирования для этого кода основан на оценке полилинейных полиномов с m переменными и общей степенью не более r . Каждый полилинейный полином над конечным полем с двумя элементами можно записать следующим образом: являются переменными полинома, а значения являются коэффициентами полинома. Обратите внимание, что существует ровно коэффициентов. Имея это в виду, входное сообщение состоит из значений , которые используются в качестве этих коэффициентов. Таким образом, каждое сообщение порождает уникальный полином от m переменных. Чтобы построить кодовое слово , кодер оценивает полином во всех точках , где полином берется с умножением и сложением по модулю 2 . То есть функция кодирования определяется с помощью ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ ${\textstyle x\in \{0,1\}^{k}}$ ${\textstyle C(x)\in \{0,1\}^{n}}$ ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ ${\displaystyle \textstyle n=2^{m}}$ $${\displaystyle 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}}$ ${\textstyle C(x)}$ ${\textstyle p_{x}}$ ${\textstyle Z=(Z_{1},\ldots ,Z_{n})\in \{0,1\}^{m}}$ ${\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}$ $${\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}$$

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

Пусть будет только что определенной функцией кодирования. Чтобы закодировать строку x = 1 1010 010101 длины 11, кодер сначала строит многочлен с 4 переменными: Затем он оценивает этот многочлен во всех 16 точках оценки (0101 означает : ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle p_{x}}$ $${\displaystyle {\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}}}$$ ${\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}$ $${\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}$$

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

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

$${\displaystyle 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}$

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

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

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

Пример

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

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

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

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

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

• ${\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, оценка равна 0000 0011 0000 0011, текущий код теперь 1100 1100 0000 0100. ${\textstyle \mu }$

• ${\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, оценка равна 0000 0000 0011 0011, текущий код теперь 1100 1100 0011 0111. ${\textstyle \mu }$

• ${\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, оценка равна 0011 0011 0011 0011, текущий код теперь 1111 1111 0000 0100. ${\textstyle \mu }$

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

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

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

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

Описание с использованием матрицы-генератора

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Код Рида–Маллера RM( r , m ) порядка r и длины N  = 2 ^m — это код, сгенерированный v ₀ и произведениями клиньев до r из v _i , 1 ≤ i ≤ m (где по соглашению произведение клиньев менее одного вектора является тождеством для операции). Другими словами, мы можем построить матрицу генератора для кода RM( r , m ) , используя векторы и их перестановки произведений клиньев до r за раз , как строки матрицы генератора, где 1 ≤ i _k ≤ m . ${\displaystyle {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

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

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

и

${\displaystyle {\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) генерируется набором

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

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

${\displaystyle {\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) генерируется набором:

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

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

${\displaystyle {\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 из v _i образуют основу для . ${\displaystyle \mathbb {F} _{2}^{N}}$
2. Код RM ( r , m ) имеет ранг

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

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

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

1. Есть

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

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

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

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

   где 1 ≤ i ≤ m .

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

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

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

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

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

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

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

   тогда продукт в виде стержня имеет вес

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

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

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

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

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

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

${\displaystyle \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 ^m , размерностью и минимальным расстоянием для . Двойственный код к RM( r,m ) - это RM( m - r -1, m ). Это показывает, что коды с повторениями и SPC являются двойственными, биортогональные и расширенные коды Хэмминга являются двойственными, а коды с k  =  n /2 являются самодвойственными. ${\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}$ ${\displaystyle d=2^{m-r}}$ ${\displaystyle r\geq 0}$

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

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

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

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

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

Ссылки

1. Massey, James L. (1992), «Связь и кодирование в дальнем космосе: брак, заключенный на небесах», Advanced Methods for Satellite and Deep Space Communications , Lecture Notes in Control and Information Sciences, т. 182, Springer-Verlag, стр. 1–17, CiteSeerX  10.1.1.36.4265 , doi :10.1007/bfb0036046, ISBN 978-3540558514pdf
2. "3GPP RAN1 meeting #87 final report". 3GPP . Получено 31 августа 2017 .
3. Арикан, Эрдал (2009). «Поляризация канала: метод построения кодов, обеспечивающих пропускную способность, для симметричных каналов без памяти с двоичным входом — журналы и журналы IEEE». Труды IEEE по теории информации . 55 (7): 3051–3073. arXiv : 0807.3917 . doi : 10.1109/TIT.2009.2021379. hdl : 11693/11695. S2CID  889822.
4. Мюллер, Дэвид Э. (1954). «Применение булевой алгебры к проектированию коммутационных схем и обнаружению ошибок». Труды Профессиональной группы IRE по электронным компьютерам . EC-3 (3): 6–12. doi :10.1109/irepgelc.1954.6499441. ISSN  2168-1740.
5. Рид, Ирвинг С. (1954). «Класс кодов с исправлением множественных ошибок и схема декодирования». Труды Профессиональной группы IRE по теории информации . 4 (4): 38–49. doi :10.1109/tit.1954.1057465. hdl : 10338.dmlcz/143797 . ISSN  2168-2690.
6. Прахлад Харша и др., Пределы алгоритмов аппроксимации: PCP и уникальные игры (конспект лекций по учебнику DIMACS), раздел 5.2.1.
7. Треллис и турбокодирование, C. Schlegel & L. Perez, Wiley Interscience, 2004, стр. 149.

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

• Шу Линь; Дэниел Костелло (2005). Кодирование с контролем ошибок (2-е изд.). Пирсон. ISBN 978-0-13-017973-9.Глава 4.
• JH van Lint (1992). Введение в теорию кодирования . GTM . Том 86 (2-е изд.). Springer-Verlag . 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. doi :10.1016/s0019-9958(62)90555-7. ISSN  0019-9958.