2.3.2. Конечные геометрии и мажоритарное декодирование.

Определение кодов РМ может быть дано и в терминах конечных геометрии. Евклидова геометрия, EG(m,2), размерности т над GF(2) содержит 2^т точек, которые представляют собой все двоичные вектора длины т. Заметим, что столбцы матрицы, образованной последними тремя строками порождающей матрицы PM_1,3 кода, см. Пример 16, представляют собой 8 точек EG(3,2). Удалением нулевой точки это множество точек преобразуется в проективную геометрию PG(m-1,2). Коды над конечными геометриями являются по существу обобщением кодов РМ.

Связь между кодами и конечными геометриями можно объяснить следующим образом. Возьмем EG(m,2). Столбцы матрицы (x^T₁ , х^т₂ … х^т_m)^т (где Т - операция транспонирования матрицы) рассматриваются как координаты точек геометрии EG(m,2). Тогда имеет место взаимно однозначное соответствие между компонентами двоичного вектора длины 2^т и точками EG(m,2). Заданный двоичный вектор длины 2^т ассоциируется с подмножеством точек EG(m,2). В частности, подмножество EG(m,2) может быть ассоциировано с двоичным вектором w = (w₁ , w₂, …, w_n) длины п=2^т, если интерпретировать значение его координат w_i =1 как выбор точки. Другими словами, w является вектором инцидентности (совпадений).

Теперь двоичный код Рида-Маллера можно определить следующим образом: кодовыми словами PM_r,m кода являются вектора инцидентности всех подпространств (т.е. линейных комбинаций точек) размерности т-r в EG(m,2) Из этого определения следует, что число кодовых слов минимального веса РМ_r,m кода равно

(2.6)

Код, который получается после удаления (перфорации) координат, соответствующих условию х₁ = х₂ = ... = х_m = 0, из всех кодовых слов PМ_r,m кода является двоичным циклическим РМ*_r,m кодом. Число слов минимального веса циклического РМ кода равно

(2.7)

Декодирование РМ кодов может быть выполнено на основе мажоритарной логики (МЛ). Идея мажоритарного декодирования состоит в следующем. Как известно, проверочная матрица порождает 2^п-к проверочных уравнений. Построение МЛ декодера сводится к выбору такого подмножества проверочных уравнений, чтобы решение о значении кодового символа на определенной позиции формировалось по большинству «голосов», причем каждый «голос» связан с одним из проверочных уравнений. В качестве иллюстрации рассмотрим код РМ_1,3 из Примера 16.

Пример 17. Пусть векторявляется кодовым словом кода PM_1,3. Как уже упоминалось ранее, выражение (2.5) определяет порождающую, а также и проверочную матрицу PM_1,3 кода, поскольку в данном случае r = 1 и m-r-1=1 и, следовательно, код является самодуальным. Все возможные ненулевые линейные комбинации (всего 15) проверочных уравнений (строк проверочной матрицы Н) имеют вид:

(2.8)

Читателю предлагается проверить, что сумма v_i + v_j любой пары кодовых символов v_i и v_j появляется точно в четырех уравнениях. Более того, в уравнениях, которые содержат одинаковую сумму (v_i + v_j), любые другие суммы пар появляются не более одного раза (т.е. не более чем в одном уравнении). Такие проверочные уравнения называют ортогональными относительно пары символов v_i и v_j.

Покажем теперь способ исправления одиночной ошибки. Пусть в результате передачи кодового слова v по ДСК получен вектор

r = v + e = ( r₁, r₂, r₃, r₄, r₅, r₆, r₇, r₈)

Предположим, что ошибка, которая должна быть исправлена, находится в v₅. Построим процедуру мажоритарного декодирования для данного случая.

Выберем два уравнения, включающие сумму v_i + v₅, i≠ 5, и два других уравнения, содержащие сумму v_j+ v₅, j≠5 , i≠j. Примем, например, i = 3 и j = 4. Имеется четыре проверки ортогональные сумме v₃ + v₅. Выберем любые две из них. Выполним тоже самое для суммы v₄ + v₅. Ассоциированные с выбранными проверками синдромы обозначим S₁ и S₂ для суммы v₃ + v₅, а также S₃ и S₄ для суммы v₄ + v₅. В результате имеем:

(2.9)

Так как вектор v является кодовым словом PM_1,3 кода, то система уравнений (2.9) эквивалентна следующей

(2.10)

Поскольку проверки S₁ S₂, S₃, S₄ ортогональны относительно е₃ + е₅ и е₄ +e₅ , то может быть построена новая пара уравнений ортогональных относительно е₅.

(2.11)

где e'_j, j = 3, 4, 5, представляют мажоритарные оценки, полученные из уравнений (2.9). Уравнения (2.11) ортогональны относительно е'₅ и, следовательно, значение е'₅ может быть получено голосованием. Например, в данном случае это может быть результат операции «И» с входами S’₁ и S'₂

Предположим, что передавалось слово v = (111 10000) и было принято слово r = (11111000). Тогда из (2.10) получаем

(2.12)

Таким образом, оба терма е₃ + e₅ и е₄ + е₅ оцениваются равными «1». Из (2.11) получаем оценку е₅ = 1 и оценку исправляющего вектора е = (00001000). Окончательно, оценка переданного слова равна v = r + е = (11110000). Таким образом, продемонстрирован двух шаговый способ мажоритарного исправления одной ошибки на пятой позиции.

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

В общем случае код РМ_r,m может быть декодирован (r + 1) -шаговой мажоритарной процедурой декодирования с исправлением любой из возможных комбинаций случайных ошибок веса |_(2^{m - 2} - 1) / 2_| или меньше .

Дополнительно заметим, что циклический код РМ*_r,m декодируется несколько проще. В циклическом коде С, если (v₁, v₂,..., v_n) любое кодовое слово, то и его циклический сдвиг (v_n, v₁, ... , v_n-1) тоже кодовое слово. Отсюда следует, что, если некоторая позиция может быть декодирована по мажоритарному методу, то и все n позиций будут декодированы тем же самым способом с использованием циклического сдвига.

Пример 18. В этом примере рассматривается декодер циклического PM*_1,3 кода, который совпадает с двоичным (7,4,3) кодом Хемминга. Для того, чтобы получить проверочные уравнения циклического кода из проверок PM_1,3 кода, достаточно удалить во всех уравнениях координату v₁, для которой x₁ = х₂ =...= х_m. После удаления v₁ изменим нумерацию позиций PM*_1,3 кода следующим образом:

Как и раньше, можно построить мажоритарный декодер для произвольной позиции (например, пятой), учитывая семь линейно независимых проверочных уравнений:

(2.13)

По аналогии с предыдущим примером находим, что синдромы S₁ и S₂ ортогональны относительно символов v₄ и v₅, а S₂ и S₃ ортогональны относительно v₅ и v₆:

(2.14)

Используя промежуточные оценки сумм v₄ + v₅ и v₅ + v₆, получаем дополнительно два ортогональных уравнения относительно v₅:

(2.15)

где e'_j, j = 4, 5, 6, обозначены мажоритарные оценки, полученные на предыдущем шаге. Этот алгоритм представлен на Рисунке 15 в виде логической схемы.

Эта схема работает следующим образом. Начальное состояние семи ячеек регистра памяти устанавливается нулевым. Предположим, что принятое слово содержит ошибку в позиции с номером i, 1 ≤ i ≤ 7. На каждом такте содержимое регистра памяти сдвигается вправо на одну позицию. Время в тактах представлено на схеме нижним индексом.

Рис. 15. Мажоритарный декодер циклического кода РМ*(1,3)

Рассмотрим случай i = 1. Это означает, что ошибка находится в первой позиции принятого слова. Через три такта эта ошибка переместится в пятую ячейку регистра (v₅). Выход мажоритарной логической схемы примет состояние е_п = 1. Еще через четыре такта (на седьмом такте) первый принятый символ попадет на выход декодера и будет исправлен. Рассмотрим теперь случай i = 7. Через девять тактов ошибка будет обнаружена и выход мажоритарной схемы примет значение е_п = 1. Спустя четыре такта (т.е. на тринадцатом такте) последний символ поступит на выход декодера и будет исправлен. Декодер, который здесь рассматривается, имеет задержку 13 тактов. Через 13 тактов содержимое регистра стирается и начинается обработка нового принятого слова.

В следующей части рассматриваются циклические коды и обширное семейство БЧХ кодов.

Вопросы для самоконтроля

Какие коды называются самодуальными?

Запишите параметры (n,k,d) двоичного кода Голея.

Что значит понятие систематический код в расширенном смысле?