Коды Рида – Маллера - это коды с исправлением ошибок , которые используются в приложениях беспроводной связи, особенно в связи в дальнем космосе. [1] Кроме того, предлагаемый стандарт 5G [2] полагается на тесно связанные полярные коды [3] для исправления ошибок в канале управления. Благодаря своим благоприятным теоретическим и математическим свойствам коды Рида – Мюллера также широко изучались в теоретической информатике .
Код Рида-Мюллера RM (r, m) | |
---|---|
Названный в честь | Ирвинг С. Рид и Дэвид Э. Мюллер |
Классификация | |
Тип | Линейный блочный код |
Длина блока | |
Длина сообщения | |
Показатель | |
Расстояние | |
Размер алфавита | |
Обозначение | -код |
Рида-Мюллера коды обобщают кодов Рида-Соломона и код Уолша-Адамара . Коды Рида – Маллера - это линейные блочные коды, которые можно локально тестировать , локально декодировать и декодировать по списку . Эти свойства делают их особенно полезными при разработке вероятностно проверяемых доказательств .
Традиционные коды Рида – Маллера представляют собой двоичные коды, что означает, что сообщения и кодовые слова представляют собой двоичные строки. Когда r и m являются целыми числами с 0 ≤ r ≤ m , код Рида – Маллера с параметрами r и m обозначается как RM ( r , m ). На запрос закодировать сообщение, состоящее из k бит, гдекод RM ( r , m ) создает кодовое слово, состоящее из 2 m битов.
Коды Рида – Маллера названы в честь Дэвида Э. Мюллера , открывшего коды в 1954 г. [4], и Ирвинга С. Рида , который предложил первый эффективный алгоритм декодирования. [5]
Описание с использованием полиномов низкой степени
Коды Рида – Маллера можно описать несколькими разными (но в конечном итоге эквивалентными) способами. Описание, основанное на полиномах низкой степени, довольно элегантно и особенно подходит для их применения в качестве локально тестируемых кодов и локально декодируемых кодов . [6]
Кодировщик
Кодовый блок может иметь одну или несколько функций кодирования что сообщения карты к кодовым словам . Код Рида – Маллера RM ( r , m ) имеет длину сообщения и длина блока . Один из способов определения кодировки для этого кода основан на вычислении полилинейных многочленов с m переменными и общей степенью r . Каждый полилинейный многочлен над конечным полем с двумя элементами можно записать следующим образом:
Тот факт, что кодовое слово Достаточно однозначно восстановить следует из интерполяции Лагранжа , которая утверждает, что коэффициенты многочлена однозначно определяются, когда задано достаточно много точек оценки. С а также удерживается для всех сообщений , функция является линейным отображением . Таким образом, код Рида – Маллера является линейным кодом .
Пример
Для кода RM ( 2 , 4 ) параметры следующие:
Позволять быть только что определенной функцией кодирования. Чтобы кодировать строку x = 1 1010 010101 длины 11, кодировщик сначала строит многочлен в 4 переменных:
Декодер
Как уже упоминалось, интерполяция Лагранжа может использоваться для эффективного извлечения сообщения из кодового слова. Однако декодер должен работать, даже если кодовое слово было повреждено в нескольких позициях, то есть когда полученное слово отличается от любого кодового слова. В этом случае может помочь процедура локального декодирования.
Обобщение на более крупные алфавиты через многочлены низкой степени
Использование полиномов низкой степени над конечным полем размера , можно расширить определение кодов Рида – Маллера до алфавитов размера . Позволять а также - натуральные числа, где следует рассматривать как больше, чем . Чтобы закодировать сообщение ширины , сообщение снова интерпретируется как -переменный многочлен общей степени не более и с коэффициентом от . Такой многочлен действительно имееткоэффициенты. Кодировка Рида – Мюллера список всех оценок общий . Таким образом, длина блока равна.
Описание с использованием образующей матрицы
Порождающая матрица для кода Рида-Мюллера RM ( г , м ) длины N = 2 м может быть построена следующим образом . Запишем множество всех m -мерных двоичных векторов как:
Определим в N -мерном пространствето векторы индикаторные
на подмножествах от:
вместе с , бинарная операция
называется продуктом клина (не путать с продуктом клина, определенным во внешней алгебре). Здесь, а также точки в ( N -мерные двоичные векторы) и операция обычное умножение в поле .
является m -мерным векторным пространством над полем, поэтому можно написать
Определим в N -мерном пространстве следующие векторы длиной а также
где 1 ≤ i ≤ m, а H i - гиперплоскости в(при размерности м - 1 ):
Генераторная матрица
Код Рида – Маллера RM ( r , m ) порядка r и длины N = 2 m - это код, генерируемый v 0 и произведениями клина до r из v i , 1 ≤ i ≤ m (где по соглашению произведение клина из менее чем одного вектора является тождеством операции). Другими словами, мы можем построить матрицу генератора для кода RM ( r , m ) , используя векторы и их перестановки произведения клина до r за раз., как строки образующей матрицы, где 1 ≤ i k ≤ m .
Пример 1
Пусть m = 3. Тогда N = 8 и
а также
Код RM (1,3) порождается множеством
или более явно строками матрицы:
Пример 2
Код RM (2,3) генерируется набором:
или более явно строками матрицы:
Характеристики
Имеют место следующие свойства:
- Набор всевозможных клиновых изделий до m из v i составляет основу для.
- Код RM ( r , m ) имеет ранг
- RM ( r , m ) = RM ( r , m - 1) | RM ( r - 1, m - 1), где '|' обозначает штриховое произведение двух кодов.
- RM ( r , m ) имеет минимальный вес Хэмминга 2 m - r .
Доказательство
- Есть
такие векторы и имеют размерность N, поэтому достаточно проверить, что N векторов охватывают; эквивалентно, достаточно проверить, что.
Пусть х быть двоичным вектором длины м , элемент X . Пусть ( x ) i обозначает i- й элемент x . Определять
где 1 ≤ i ≤ m .
потом
Расширение за счет распределения продукта клина дает . Тогда, поскольку векторы охватывать у нас есть . - Согласно 1 , все такие произведения клина должны быть линейно независимыми, поэтому ранг RM ( r, m ) должен быть просто количеством таких векторов.
- Опущено.
- По индукции.
- Код RM (0, m ) - это код повторения длины N = 2 м и веса N = 2 m −0 = 2 m - r . К 1и имеет вес 1 = 2 0 = 2 m - r .
- Если 0 < r < m и если
- RM ( r , m - 1) имеет вес 2 m −1− r
- RM ( r - 1, m - 1) имеет вес 2 m −1− ( r −1) = 2 m - r
- тогда барное изделие имеет вес
Расшифровка кодов RM
Коды RM ( r , m ) могут быть декодированы с использованием декодирования с использованием мажоритарной логики . Основная идея декодирования по мажоритарной логике состоит в построении нескольких контрольных сумм для каждого принятого элемента кодового слова. Поскольку каждая из различных контрольных сумм должна иметь одно и то же значение (т. Е. Значение веса элемента слова сообщения), мы можем использовать декодирование с помощью логики большинства, чтобы расшифровать значение элемента слова сообщения. После декодирования каждого порядка полинома принятое слово соответствующим образом модифицируется путем удаления соответствующих кодовых слов, взвешенных по вкладам декодированного сообщения, вплоть до настоящего этапа. Итак, для кода RM r- го порядка мы должны декодировать итеративно r + 1 раз, прежде чем мы придем к окончательному принятому кодовому слову. Также по этой схеме вычисляются значения битов сообщения; наконец, мы можем вычислить кодовое слово, умножив слово сообщения (только что декодированное) на матрицу генератора.
Одним из ключей к успеху декодирования является получение модифицированного со всеми нулями принятого слова в конце ( r + 1) -этапного декодирования посредством декодирования по мажоритарной логике. Этот метод был предложен Ирвингом С. Ридом и является более общим в применении к другим программам с конечной геометрией.
Описание с использованием рекурсивной конструкции
Код Рида – Маллера RM ( r, m ) существует для любых целых чисел а также . RM ( m , m ) определяется как вселенная () код. RM (−1, m) определяется как тривиальный код (). Остальные коды RM могут быть построены из этих элементарных кодов с использованием конструкции удвоения длины
Исходя из этой конструкции, RM ( r, m ) представляет собой двоичный линейный блочный код ( n , k , d ) с длиной n = 2 м , размерностью и минимальное расстояние для . Двойственный код для RM ( R, M ) является РМ ( м - г -1, м ). Это показывает, что коды с повторением и SPC двойственны, биортогональные и расширенные коды Хэмминга двойственны, а коды с k = n / 2 самодвойственны.
Частные случаи кодов Рида – Маллера.
Таблица всех кодов RM (r, m) для m≤5
Все коды RM ( r , m ) си размер алфавита 2 отображаются здесь, аннотированные стандартными обозначениями теории кодирования [n, k, d] для блочных кодов . Код RM ( r , m ) является-код, то есть это линейный код над двоичным алфавитом , имеет длину блока , длина сообщения (или размер) k и минимальное расстояние .
RM ( м, м ) ( 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) | |||||
RM (0,1) (2,1,2) | РМ (1,3) (8,4,4) | РМ (2,5) (32,16,8) | самодуальные коды | ||||
RM (−1,0) (1,0,) | РМ (0,2) (4,1,4) | РМ (1,4) (16,5,8) | |||||
RM (−1,1) (2,0,) | РМ (0,3) (8,1,8) | РМ (1,5) (32,6,16) | |||||
RM (−1,2) (4,0,) | РМ (0,4) (16,1,16) | RM (1, м ) (2 м , м +1, 2 м −1 ) | Проколотые коды хадамара | ||||
RM (−1,3) (8,0,) | РМ (0,5) (32,1,32) | ||||||
RM (−1,4) (16,0,) | RM (0, м ) (2 м , 1, 2 м ) | коды повторения | |||||
RM (−1,5) (32,0,) | |||||||
RM (−1, м ) (2 м , 0, ∞) | тривиальные коды |
Свойства кодов RM (r, m) для r≤1 или r≥m-1
- Коды RM (0, m ) - это коды с повторением длины N = 2 м , скорости и минимальное расстояние .
- Коды RM (1, m ) - это коды проверки на четность длины N = 2 м , скорость и минимальное расстояние .
- Коды RM ( m - 1, m ) представляют собой однократные коды проверки на четность длины N = 2 м , скорость и минимальное расстояние .
- Коды RM ( m - 2, m ) представляют собой семейство расширенных кодов Хэмминга длины N = 2 м с минимальным расстоянием. [7]
Рекомендации
- ^ Мэсси, Джеймс Л. (1992), «Глубокая космическая связь и кодирование: брак, заключенный на небесах», Advanced Methods for Satellite and Deep Space Communications , Lecture Notes in Control and Information Sciences, 182 , Springer-Verlag, pp. 1-17, CiteSeerX 10.1.1.36.4265 , DOI : 10.1007 / bfb0036046 , ISBN 978-3540558514pdf
- ^ «Итоговый отчет собрания №87 3GPP RAN1» . 3GPP . Проверено 31 августа 2017 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Арикан, Эрдал (2009). «Поляризация каналов: метод построения кодов, обеспечивающих пропускную способность для симметричных каналов с двоичным входом без памяти - журналы и журнал IEEE». IEEE Transactions по теории информации . 55 (7): 3051–3073. arXiv : 0807.3917 . DOI : 10.1109 / TIT.2009.2021379 . hdl : 11693/11695 .
- ^ Мюллер, Дэвид Э. (1954). «Применение булевой алгебры для проектирования коммутационных схем и обнаружения ошибок». Сделки IRE Professional Group по электронным компьютерам . ИС-3 (3): 6–12. DOI : 10.1109 / irepgelc.1954.6499441 . ISSN 2168-1740 .
- ^ Рид, Ирвинг С. (1954). «Класс кодов с множественными исправлениями ошибок и схемы декодирования». Труды профессиональной группы IRE по теории информации . 4 (4): 38–49. DOI : 10,1109 / tit.1954.1057465 . hdl : 10338.dmlcz / 143797 . ISSN 2168-2690 .
- ^ Прахлад Харша и др., Пределы алгоритмов приближения: PCP и уникальные игры (Учебные примечания к лекциям по DIMACS) , раздел 5.2.1.
- ^ Треллис и турбокодирования, C. & Schlegel L. Perez, Wiley Interscience, 2004, P149.
дальнейшее чтение
- Шу Линь; Даниэль Костелло (2005). Кодирование контроля ошибок (2-е изд.). Пирсон. ISBN 978-0-13-017973-9. Глава 4.
- Дж. Х. ван Линт (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 .