4.6. Каскадные коды и коды Юстесена

4.6.1. Каскадные коды

Пусть линейный -код над линейный -код над Каскадным кодом [49] с внешним кодом и внутренним кодом называется линейный -ичный

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

1) Информационные компоненты кода С представляют собой вектор длины который мы также представим в виде матрицы размера (каждую строку этой матрицы можно рассматривать как представление некоторого элемента поля виде вектора над пусть элемент представлением которого является строка).

2) Пусть кодовый вектор кода , информационные компоненты которого совпадают с (по определению существует ровно один такой вектор).

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

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

Используя в качестве внешнего кода код Рида — Соломона и подбирая специальным образом внутренний код, Форни показал, что в двоичном симметричном канале при любых скоростях, меньших пропускной способности, вероятность ошибочного декодирования для каскадного кода с ростом по стремится экспоненциально к нулю [49].

Все строки кодового слова описанного выше каскадного кода являются кодовыми словами одного и того же кода Можно, однако, рассматривать также каскадные коды, в которых для каждой строки используется свой линейный -код . Коды Юстесена являются кодами такого типа [50].

Что касается декодирования каскадных кодов, то сначала проводится декодирование каждой принятой строки этом используются методы декодирования кода Информационные части векторов, полученных в результате этого декодирования (первые k компонент), можно рассматривать как элементы поля Далее, используя методы декодирования кода следует провести декодирование вектора

Пример 4.14 [69]. Пусть положительное нечетное число, минимальное целое число, такое, что — элемент порядка и -двоичный циклический код длины проверочным многочленом которого является минимальный многочлен элемента у. Поскольку корни порождающего многочлена представляют собой элементы множества многочлен соответствующий кодовому вектору кода имеет вид

Согласно теореме 4.4, отображение является взаимно однозначным линейным отображением -мерного линейного пространства над полем . В качестве возьмем -ичный БЧХ-код длины информационными символами из примера 4.5 или утверждения 4.3. Пусть множество всех МС-многочленов кодовых векторов кода — элемент порядка (поскольку то такой элемент существует). Обозначим через С каскадный код с внешним кодом и внутренним кодом (получаемый с помощью отображения Код С является -ичным линейным -кодом. Если фиксировать один из кодовых векторов кода , то, согласно определению кода С, фиксируется кодовый вектор соответствующий Элементу сопоставим вектор . При этом -компонента кодового вектора (для простоты обозначаемого ниже через согласно формуле (4.39), равна

Если использовать вместо то -компонента

будет равна

Так как то вектор может быть получен с помощью однократного циклического сдвига каждой строки Аналогично, рассматривая можно убедиться в том, что является вектором, получающимся однократным циклическим сдвигом каждого столбца Следовательно, код С инвариантен относительно циклических перестановок строк и столбцов. Так как нечетное число и то Если положить то порядок элемента а будет равен Пусть остатки от деления соответственно на Тогда Отображение, сопоставляющее пару чисел переводит двумерные матрицы в одномерные векторы. Если перестановка, представляющая собой последовательность однократных циклических перестановок строк или столбцов, то при этой перестановке и это соответствует циклической перестановке одномерного вектора. Следовательно, при таком расположении компонент код С оказывается циклическим. Так как, примеру 4.5, минимальный вес равен то минимальный вес С равен где минимальный вес Необходимым условием того, что представляет собой корень проверочного многочлена кода, является наличие в С хотя бы одного кодового слова, МС-многочлен которого содержит с ненулевым коэффициентом. Пусть а — элемент, обратный элементу по модулю и пусть элемент, обратный элементу по модулю Так как

Следовательно, из определений имеем

Преобразуя выражение (4.40), получаем, что -компонента равна

Отсюда следует, что совпадает с Если проверочный многочлен кода то, так как имеет вид

получаем

Следовательно, корнями проверочного многочлена кода С являются элементы множества

Выбирая подходящим образом коды Берлекэмп и Юстесен показали существование большого числа кодов, для которых при достаточно больших их длинах отношение минимального расстояния к длине кода больше, чем у БЧХ-кодов, имеющих приблизительно такую же скорость передачи [51].