Код Рида — Маллера

Интересно отметить, что в нескольких случаях можно построить нелинейный код с большим числом кодовых слов, чем у наилучшего линейного кода при тех же самых значениях п и d. Слоуэн построил класс нелинейных двоичных кодов, исправляющих одиночные ошибки, которые содержат больше кодовых слов, чем соответствующий наилучший линейный код. Препарата, обобщая работы Грина и Нордстрома и Робинсона, построил класс систематических нелинейных кодов, исправляющих две ошибки, с наибольшим возможным числом кодовых слов. Эти коды тесно связаны с циклическими кодами, и кодирование может производиться с помощью нелинейного регистра сдвига с обратной связью. Для них была также разработана процедура декодирования.
Коды Рида — Маллера образуют класс двоичных групповых кодов, существующих в широкой области значений скоростей передачи и минимальных расстояний. Фактически эти коды эквивалентны циклическим кодам с дополнительной проверкой на четность по всем символам. Они являются основой для мажоритарно-декодируемых кодов, рассматриваемых в гл. 10.
Для любых т и г < т существует код Рида — Маллера, для которого Построение этих кодов не требует применения большого математического аппарата. Рассмотрим следующую совокупность векторов над полем из двух элементов. Пусть v0 — вектор длины 2т, все компоненты которого равны 1, a vb v2, vm — строки матрицы, столбцами которой являются все возможные двоичные наборы длины т. (См. фиг. 5.1 для т = 4.) Определим следующим образом векторное произведение двух векторов: При таком определении векторы образуют коммутативную линейную ассоциативную алгебру. Рассмотрим, наконец, совокупность векторов, образованную произведениями векторов Vj, взятых по Векторы, используемые в качестве базиса для кодов Рида — Маллера длины 16. два, три, четыре и т. д. вплоть до trt одновременно. Можно показать, что эти векторы линейно независимы. (Заметим, что строки можно переставить так, чтобы получилась матрица с единицами на главной диагонали и нулями всюду ниже главной диагонали.