Код Рида – Мюллера - Reed–Muller code

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

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

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

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

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

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

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

Кодировщик

А блочный код может иметь одну или несколько функций кодирования ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ что сообщения карты ${\textstyle x\in \{0,1\}^{k}}$ к кодовым словам ${\textstyle C(x)\in \{0,1\}^{n}}$. Код Рида-Мюллера RM (р, м) имеет длина сообщения ${\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}$ коэффициенты, сообщение ${\textstyle x\in \{0,1\}^{k}}$ состоит из ${\textstyle k}$ значения, которые можно использовать в качестве этих коэффициентов. Таким образом, каждое сообщение ${\textstyle x}$ дает единственный многочлен ${\textstyle p_{x}}$ в м переменные. Чтобы построить кодовое слово ${\textstyle C(x)}$, кодировщик оценивает ${\textstyle p_{x}}$ во всех точках оценки ${\textstyle a\in \{0,1\}^{m}}$, где сумма интерпретируется как сложение по модулю два, чтобы получить бит ${\textstyle (p_{x}(a){\bmod {2}})\in \{0,1\}}$. То есть функция кодирования определяется через

$${\displaystyle C(x)=\left(p_{x}(a){\bmod {2}}\right)_{a\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}}}$

Позволять ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ быть только что определенной функцией кодирования. Чтобы закодировать строку x = 1 1010 010101 длины 11, кодировщик сначала строит многочлен ${\textstyle p_{x}}$ в 4 переменных:

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

Затем он оценивает этот многочлен во всех 16 точках оценки:

$${\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=1,\;p_{x}(0011)=1,\;p_{x}(0100)=1,\;p_{x}(0101)=0,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;p_{x}(1000)=0,\;p_{x}(1001)=1,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=0,\;p_{x}(1111)=0\,.}$$

В результате сохраняется C (1 1010 010101) = 1111 1010 0101 0000.

Декодер

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

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

Использование многочленов низкой степени над конечным полем ${\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 (р, м) длины N = 2^м можно построить следующим образом. Запишем набор всех м-мерные двоичные векторы как:

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

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

${\displaystyle \mathbb {F} _{2}^{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 ≤ м и ЧАС_я находятся гиперплоскости в ${\displaystyle (\mathbb {F} _{2})^{m}}$ (с размером м − 1):

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

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

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

Пример 1

Позволять м = 3. Тогда N = 8 и

${\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(1,0,0),(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. Набор всех возможных клиновых изделий до м из v_я сформировать основу для ${\displaystyle \mathbb {F} _{2}^{N}}$.
2. РМ (р, м) код имеет ранг

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

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

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

1. Есть

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

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

   Позволять Икс быть двоичным вектором длины м, элемент Икс. Позволять (Икс)_я обозначить я^th элемент Икс. Определить

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

   где 1 ≤ я ≤м.

   потом ${\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 (г, м) должно быть просто количеством таких векторов.
3. Опущено.
4. По индукции.

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

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

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

   Если 0 < р < м и если

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

   тогда барное изделие имеет вес

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

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

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

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

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

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

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

Частные случаи кодов Рида – Маллера.

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

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

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

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

• RM (0,м) коды коды повторения длины N = 2^м, показатель ${\displaystyle {R={\tfrac {1}{N}}}}$ и минимальное расстояние ${\displaystyle d_{\min }=N}$.

• RM (1,м) коды коды проверки четности длины N = 2^м, показатель ${\displaystyle R={\tfrac {m+1}{N}}}$ и минимальное расстояние ${\displaystyle d_{\min }={\tfrac {N}{2}}}$.

• RM (м − 1, м) коды коды однократной проверки на четность длины N = 2^м, показатель ${\displaystyle R={\tfrac {N-1}{N}}}$ и минимальное расстояние ${\displaystyle d_{\min }=2}$.

• RM (м − 2, м) коды - это семейство расширенные коды Хэмминга длины N = 2^м с минимальным расстоянием ${\displaystyle d_{\min }=4}$.^[7]

использованная литература

1. Мэсси, Джеймс Л. (1992), "Космическая связь и кодирование: брак, заключенный на небесах", Передовые методы спутниковой связи и связи в дальнем космосе, Конспект лекций по управлению и информатике, 182, Springer-Verlag, стр. 1–17, CiteSeerX  10.1.1.36.4265, Дои:10.1007 / bfb0036046, ISBN  978-3540558514pdf
2. «Итоговый отчет совещания №87 3GPP RAN1». 3GPP. Получено 31 августа 2017.
3. Арикан, Эрдал (2009). «Поляризация канала: метод построения кодов, обеспечивающих пропускную способность для симметричных каналов с двоичным входом без памяти - журналы и журнал IEEE». IEEE Transactions по теории информации. 55 (7): 3051–3073. arXiv:0807.3917. Дои:10.1109 / TIT.2009.2021379. HDL:11693/11695.
4. Мюллер, Дэвид Э. (1954). «Применение булевой алгебры для проектирования коммутационных схем и обнаружения ошибок». Сделки I.R.E. Профессиональная группа по электронным компьютерам. ИС-3 (3): 6–12. Дои:10.1109 / irepgelc.1954.6499441. ISSN  2168-1740.
5. Рид, Ирвинг С. (1954). «Класс кодов с множественными исправлениями ошибок и схемы декодирования». Сделки IRE Professional Group по теории информации. 4 (4): 38–49. Дои:10.1109 / tit.1954.1057465. HDL:10338.dmlcz / 143797. ISSN  2168-2690.
6. Прахлад Харша и др., Пределы приближенных алгоритмов: PCP и уникальные игры (Учебные заметки по DIMACS), Раздел 5.2.1.
7. Решетка и турбо-кодирование, К. Шлегель и Л. Перес, Wiley Interscience, 2004, стр. 149.

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

• Шу Линь; Даниэль Костелло (2005). Кодирование с контролем ошибок (2-е изд.). Пирсон. ISBN  978-0-13-017973-9. Глава 4.
• J.H. ван Линт (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. Дои:10.1016 / s0019-9958 (62) 90555-7. ISSN  0019-9958.