5.6. Ортогонализируемые коды

Ортогонализируемые коды были введены Месси как коды, допускающие пороговое декодирование [2]. По сравнению с самоортогональными кодами эти коды могут иметь при заданном минимальном расстоянии (или числе ортогональных проверок) меньшее кодовое ограничение и в этом смысле обладают более высокими корректирующими способностями. Однако эти коды имеют и ряд недостатков, в частности они строятся методом перебора и, как указывается ниже, могут иметь бесконечную глубину распространения ошибок.

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

5.6.1. Простейшие примеры

Примером ортогонализируемого кода является код, рассмотренный в начале разд. 5.3 и имеющий скорость и кодовое ограничение Рассмотрим этот код более детально. При пороговом декодировании с обратной связью этого кода посредством линейного преобразования символов синдрома формирующихся в моменты времени от 0 до 5, могут быть построены составные проверки:

Заметим, что следующее линейное преобразование синдрома [который определяется в данном случае соотношением (5.34)]:

также позволяет построить систему составных проверок, ортогональных относительно

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

В случае самоортогональных кодов матрица линейного преобразования определяется однозначно построением структуры синдрома. В то же время, как показывает вышеприведенный пример, для других ортогонализируемых кодов матрица линейного преобразования может определяться и неоднозначно. Следовательно, при задании орюгонализируемого кода необходимо указывать не только порождающие многочлены, но и линейное преобразование, с помощью которого по синдрому вычисляются составные проверки. Поскольку последнее преобразование заключается в вычислении некоторых сумм строк проверочной матрицы, то преобразование (5.56) можно задать следующим образом: где основные цифры указывают момент формирования символа синдрома, а верхние индексы — синдром, к которому они принадлежат. Символы синдромов, участвующие в формировании различных проверок, разделены запятыми.

5.6.2. Способ построения кодов

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

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

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

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

5.6.3. Примеры кодов

В табл. 5.2 приведены ортогонализируемые коды, построенные Месси [2] описанным выше способом.

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

5.6.4. Связь с блоковыми кодами

Одним из больших классов блоковых кодов, допускающих пороговое декодирование, является класс обобщенных кодов Рида-Маллера, построенный Уэлдоном [44]. Следует заметить, что если обобщенные коды Рида — Маллера, вообще говоря,

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

Таблица 5.2 (см. скан) Ортогонализируемые коды [22|

В частности, Месси [2] показал, как описано ниже, что если систематический сверточный код со скоростью передачи является кодом, ортогонализируемым за шагов, то он допускает также ортогонализацию и за один шаг.

Действительно, проверочный треугольник сверточного кода со скоростью имеет следующий вид:

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

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

5.6.5. Сопоставление с циклическими кодами, построенными на основе разностных множеств

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

Самоортогональные коды и разностные циклические коды строятся на основе одних и тех же разностных множеств, однако методы их построения совершенно различны. В то же время

Таблица 5.3 (см. скан) Самоортогональные коды в разностные циклические коды (обозначаются соответственно через

самоортогональные коды и квазициклические самоортогональные коды, предложенные Таунсендом и Уэлдоном [40], очень похожи друг на друга. Так, квазициклический самоортогональный код можно построить по самоортогональному коду следующим образом. Входные последовательности ограничим по модулю степени именно будем рассматривать лишь информационных символов. Проверочную последовательность также ограничим по модулю степени полагая Полученный таким образом блоковый код длины информационными символами и скоростью является квазициклическим самоортогональным кодом. Однако в случае квазициклических кодов модуль должен выбираться таким образом, чтобы совокупности разностей разностного множества не пересекались. Поэтому разностные множества, используемые для построения самоортогональных кодов, и разностные множества, используемые для построения квазициклических самоортогональных кодов с той же скоростью передачи и тем же числом ортогональных проверок часто оказываются различными.