5.5. Коды Рида — Маллера

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

из этого класса, для которого

Построение этих кодов не требует применения большого математического аппарата. Рассмотрим следующую совокупность векторов над полем из двух элементов. Пусть вектор длины все компоненты которого равны 1, и пусть строки матрицы, столбцами которой являются все возможные двоичные последовательности длины как это показано на рис. 5.1 для Определим следующим образом векторное произведение двух векторов:

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

Рис. 5.1. Векторы, используемые в качестве базиса для кодов Рида — Маллера.

(Заметим, что на рис. 5.1 строки можно переставить так, чтобы получилась матрица с единицами на главной диагонали и нулями всюду ниже главной диагонали.)

Код Рида — Маллера порядка определяется как код, базисом которого являются векторы и все векторные произведения из или меньшего числа этих векторов. Очевидно, скалярное произведение двух векторов равно 0, если число единиц в векторном произведении четно, и равно 1, если оно нечетно. Кроме того, для любого вектора его квадрат Наконец, единственным произведением, содержащим нечетное число единиц, является произведение всех векторов Далее, векторное произведение любого вектора из базиса кода порядка на любой вектор из базиса кода порядка является вектором из базиса для кода, порядком которого будет и в нем содержится четное число единиц. Следовательно, любой вектор, принадлежащий коду порядка ортогонален любому базисному вектору кода порядка т. е. любому вектору, являющемуся произведением или меньше векторов Так как сумма размерностей этих кодов равна следовательно, каждый из них является двойственным по отношению к другому. Отсюда следует также, что код Рида — Маллера порядка является нулевым пространством матрицы, образованной векторами и всеми векторными произведениями этих векторов в количестве не более чем взятыми в качестве ее строк. Поскольку матрица, образованная строками является проверочной матрицей кода Хэмминга, исправляющего одну ошибку и обнаруживающего две ошибки, то этот код Хэмминга совпадает с кодом Рида — Маллера порядка

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

Задача состоит в том, чтобы определить значения а по полученному вектору, несмотря на появившиеся, быть может, ошибки. Заметим, что сумма первых четырех компонент как элементов поля из двух элементов равна 0 для всех базисных векторов, за исключением Таким образом, если ошибок не было, то

То же самое верно для следующих четырех компонент, и

Аналогично

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

После того как они определены, выражение

может быть вычтено из полученного вектора. Тогда, если ошибок не было, останется вектор

так что следующая совокупность коэффициентов может быть определена аналогичным путем. Существует восемь уравнений, которым должен удовлетворять символ

Аналогичные уравнения справедливы Наконец, если предполагать, что ошибок не было, то

Этот вектор должен быть нулевым, если и единичным, если поэтому нужно выбирать равным тому из этих двух элементов, который появляется в векторе более часто.

Поскольку при такой системе декодирования могут быть исправлены все комбинации из или меньшего числа ошибок, то минимальное расстояние дожно быть равно самое меньшее а так как все кодовые векторы имеют четный вес, то оно дожно быть равно самое меньшее Но вес последнего базисного вектора равен т. е. в точности равен минимальному весу.

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

нулю в векторе и компоненту, соответствующую единице в вектсре парными компонентами вектора Тогда сумм парных компонент используются для определения Далее, каждая из сумм четырех компонент, используемых для определения а, образуются некоторыми двумя парными компонентами вектора и парными для этих уже выбранных компонент компонентами вектора Аналогично каждое соотношение, определяющее является суммой некоторых парных компонент вектора сложенной с суммой компонент вектора парных к этим компонентам. и с суммой компонент вектора парных к уже выбранным компонентам, так что в каждой сумме получается всего 8 слагаемых. Этот процесс можно продолжить аналогичным образом.

Эти коды допускают интересную геометрическую интерпретацию. Рассмотрим пространство измерений, координатами в котором являются элементы поля, образованного двумя элементами. Имеется всего точек, и каждый из столбцов на рис, 5.1 соответствует одной из этих точек Вектор содержит 1 во всех точках, коор дината которых равна 0, т. е. в каждой точке гиперплоскости размерности (Это — вектор инцидентности.) Вектор содержит 1 во всех точках, которые принадлежат одновременно гиперплоскостям следовательно, являются матрицей инцидентности для -мерной гиперплоскости, проходящей через начало координат, и так далее.

Так как код порядка является нулевым пространством для кода порядка то каждое произведение или меньше векторов задает проверочное соотношение. С геометрической точки зрения, если символы кода расположены в соответствующих точках -мерного пространства, то каждое проверочное соотношение представляет собой проверку на четность символов, связанных с точками проходящей через начало координат гиперплоскости размерности или больше. Каждая такая гиперплоскость определяет независимое проверочное соотношение.

Метод декодирования допускает следующую геометрическую интерпретацию. Каждый базисный вектор кода является произведением или меньше векторов Гиперплоскость размерности содержит точек, и, следовательно, произведение векторов содержит единиц. Через каждую из этих точек проходит перпендикулярная гиперплоскость размерности содержащая также точек. Это и есть совокупность точек, соответствующих суммам, используемым при декодировании информационных символов. Такая совокупность точек оказывается пригодной для этой

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

Эта геометрическая интерпретация подсказывает обобщение, в котором проверочная матрица состоит из всех векторов инцидентности для гиперплоскостей размерности или меньшей, проходящих через начало координат в -мерном пространстве над полем из элементов. Это приводит к символьному коду с минимальным весом и простой схемой декодирования, основанной на том факте, что сумма равных слагаемых равна 0 в поле из элементов, так же как в поле из двух элементов.