Введение

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

Коды Рида — Мюллера — это коды коррекции ошибок, применяемые в приложениях беспроводной связи, в частности, в связи в дальнем космосе. Более того, предлагаемый стандарт 5G использует тесно связанные поляризационные коды для коррекции ошибок в управляющем канале. Благодаря своим благоприятным теоретическим и математическим свойствам, коды Рида — Мюллера также широко изучались в теоретической информатике. Коды Рида — Мюллера обобщают коды Рида — Соломона и код Уолша — Адамара. Коды Рида — Мюллера являются линейными блочными кодами, которые локально тестируемы, локально декодируемы и декодируемы списком. Эти свойства делают их особенно полезными при разработке вероятностно проверяемых доказательств. Традиционные коды Рида — Мюллера являются двоичными кодами, то есть сообщения и кодовые слова представляют собой двоичные строки. Если r и m — целые числа, удовлетворяющие условию 0 ≤ r ≤ m, то код Рида — Мюллера с параметрами r и m обозначается как RM(r, m). При кодировании сообщения, состоящего из k бит, где выполняется условие , код RM(r, m) генерирует кодовое слово, состоящее из 2m бит. Коды Рида — Мюллера названы в честь Дэвида Э. Мюллера, который открыл эти коды в 1954 году, и Ирвинга С. Рида, предложившего первый эффективный алгоритм декодирования.

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

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

Кодировщик

Блочный код может иметь одну или несколько функций кодирования, отображающих сообщения в кодовые слова. Код Рида — Мюллера RM(r, m) имеет длину сообщения и длину блока. Один из способов определения кодирования для этого кода основан на вычислении значений многочленов с m переменными и полной степенью r. Любой многолинейный многочлен над конечным полем из двух элементов может быть записан следующим образом:

Переменными многочлена являются , а значения – коэффициентами многочлена. Поскольку существует ровно коэффициентов, сообщение состоит из значений, которые могут быть использованы в качестве этих коэффициентов. Таким образом, каждое сообщение однозначно определяет многочлен от m переменных. Для построения кодового слова кодировщик вычисляет значение многочлена во всех точках вычисления, интерпретируя сумму как сложение по модулю два для получения бита. То есть функция кодирования определяется следующим образом:

Тот факт, что кодового слова достаточно для однозначного восстановления , следует из интерполяции Лагранжа, которая утверждает, что коэффициенты многочлена однозначно определяются при задании достаточного количества точек вычисления. Поскольку и выполняется для всех сообщений , функция является линейным отображением. Следовательно, код Рида — Мюллера является линейным кодом.

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

Используя полиномы низкой степени над конечным полем размера *q*, можно расширить определение кодов Рида-Мюллера до алфавитов размера *q*. Пусть *n* и *k* – положительные целые числа, где *n* должно быть больше *k*. Для кодирования сообщения ширины *k*, сообщение снова интерпретируется как *n*-арный полином общей степени не более *d* и с коэффициентами из конечного поля размера *q*. Такой полином действительно имеет *q<sup>n</sup>* коэффициентов. Кодировка Рида-Мюллера сообщения – это список всех вычислений значения полинома во всех точках из конечного поля, то есть в *q<sup>n</sup>* точках. Таким образом, длина блока равна *q<sup>n</sup>*.

Матрица генератора

Код Рида — Мюллера RM(r, m) порядка r и длины N = 2m — это код, порождаемый вектором v0 и клиновыми произведениями до r векторов vi, 1 ≤ i ≤ m (где по соглашению клиновое произведение менее чем одного вектора является тождественным элементом для данной операции). Иными словами, можно построить образующую матрицу для кода RM(r, m), используя векторы и все возможные клиновые произведения из них, взятые по r штук, в качестве строк этой матрицы, где 1 ≤ ik ≤ m.

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

Код Рида — Мюллера RM(r, m) существует для любых целых чисел, и RM(m, m) определяется как код вселенной. RM(-1, m) определяется как тривиальный код. Остальные коды RM могут быть построены из этих элементарных кодов с помощью построения удвоения длины.

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

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

Коды 1=RM(0, m) — это коды повторения длиной 1=N = 2^(m), со скоростью и минимальным расстоянием. Коды 1=RM(1, m) — это коды проверки четности длиной 1=N = 2^(m), со скоростью и минимальным расстоянием. Коды 1=RM(m − 1, m) — это коды проверки одиночной четности длиной 1=N = 2^(m), со скоростью и минимальным расстоянием. Коды 1=RM(m − 2, m) — это семейство расширенных кодов Хэмминга длиной 1=N = 2^(m) с минимальным расстоянием.