§ 3.8. Аналог кодов Рида — Маллера

Опишем еще один класс сверточных кодов, допускающих полную ортогонализацию. Метод их построения лучше всего можно пояснить на примере.

Рассмотрим таблицу

Она получена следующим образом: столбцы взяты так, что образованные ими строки из трех символов суть все возможные ненулевые последовательности из трех элементов. Затем к ним приписан справа вектор-столбец из одних единиц, а слева — векторы-столбцы, представляющие собой всевозможные попарные произведения векторов Снова положим, что строки таблицы суть последние строки из системы проверочных треугольников. Тогда, как показано выше, мы можем сложить эти строки, чтобы образовать набор из проверок, ортогональных относительно размера каждая. Кроме контролируется еще только один информационный шумовой символ Этот процесс может быть повторен на уровне предпоследних и третьих снизу строк проверочных треугольников Оставшиеся строки проверочных треугольников такие же, как и строки для равномерного кода с в § 3.7. Таким образом, для этого кода можно построить всего проверок размера 22 плюс проверок размера плюс проверок размера 2°, ортогональных относительно

Если обобщить этот пример так, чтобы таблица содержала все произведения векторов по К и менее, то будет справедлива следующая теорема.

Теорема 14. Для любых целых чисел существует сверточный код с и

такой, что

и этот код может быть полностью ортогонализован.

Доказательство. Доказательство проводится в два этапа. Во-первых, мы должны показать, что число проверок, ортогональных относительно на единицу меньше суммы в равенстве (101). Во-вторых, мы должны показать, что минимальное расстояние кода в точности равно этой сумме.

Заметим сначала, что если к таблице (100) добавить снизу строку то таблица станет матрицей, транспонированной к порождающей матрице кода Рида — Маллера второго порядка (В этом состоит причина, почему коды этого параграфа названы аналогом кодов Рида — Маллера.) Рид [14] показал, что в матрице, порождающей код порядка, столбцы могут быть сгруппированы в множеств по столбцов в каждом таким способом, что сумма столбцов каждого множества имеет единицу только в первой строке. (Доказательство Рида очень длинно и здесь приводиться не будет.) Таким образом, транспонированная матрица может быть подразделена на множеств по строк в каждом, так что сумма строк каждого множества имеет единицу только в первом столбце. Если из транспонированной матрицы удалить строку

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

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

Общее число проверок, ортогональных относительно которые построены таким способом, равно

оно на единицу меньше суммы (101), что и требовалось доказать.

Остается показать, что минимальное расстояние вычисляется в точности по формуле (101). Минимальное расстояние и отсюда оно должно быть не меньше, чем сумма (101). Тогда достаточно показать, что существует некоторое кодовое слово с в точности этого веса. Вспомним, что

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

и, следовательно, существует начальное кодовое слово такого веса. Сумма (103) равна сумме (101), что и требовалось доказать.

В табл. IV выписаны сверточные коды для аналогичные кодам Рида — Маллера. М, К код, где совпадает с равномерным кодом (§ 3.7), где

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

Таблица IV (см. скан) Сверточные коды, аналогичные кодам Рида — Маллера

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