5.10. Равномерные сверточные коды

Другим классом кодов, допускающих пороговое декодирование, является класс равномерных сверточных кодов. Эти коды имеют низкую скорость передачи, но их минимальное расстояние совпадает со средним расстоянием. Обладая приблизительно такой же корректирующей способностью, как и блоковые коды максимальной длины, они тем не менее имеют небольшую глубину распространения ошибок. Однако этот класс кодов является небольшим, поскольку строится лишь для скоростей вида Эти коды, впервые построенные Месси [2] для в дальнейшем были обобщены Робинсоном [36] и на случай Однако здесь в целях упрощения мы ограничимся рассмотрением только кодов над

5.10.1. Определение равномерного кода

Определение 5.6. Двоичным равномерным кодом называется код со скоростью порождающими многочленами которого являются все

различных ненулевых многочленов вида над степени и менее.

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

5.10.2. Правило ортогонализации

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

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

Величины в (5.89) будучи суммами предшествующих шумовых информационных символов и оценок последних, равны 0, если т. е. если символ был декодирован верно, равны 1 в противном случае и отражают воздействие на символы синдрома ошибок декодирования.

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

1. В качестве первых составных проверок выбираются

2. Пусть — символ синдрома, которому соответствует строка матрицы последовательность из символов 0 и 1, оканчивающаяся символом 1). Тогда найдется по крайней мере один символ которому в матрице соответствует строка Все суммы относятся к числу искомых составных проверок.

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

Пример 5.11. Проверочный параллелограмм равномерного кода со скоростью задается формулой (5.91):

(см. скан)

Метод ортогонализации Месси дает следующую систему ортогональных проверок:

5.10.3. Метод ортогонализации, обеспечивающий небольшую глубину распространения ошибок

Одной из характеристик равномерных кодов является глубина распространения ошибок. Анализируя явление распространения ошибок, Салливан [35] разработал следующий алгоритм ортогонализации, позволяющий минимизировать глубину распространения ошибок:

1) В качестве первых составных проверок берутся символы синдрома

2) Пусть символ синдрома, которому соответствует строка матрицы содержащая не менее трех символов 1 (здесь последовательность из символов 0 и 1). Тогда среди строк матрицы всегда можно найти строку вида соответствующую некоторому символу синдрома Действительно, это всегда можно сделать, поскольку все заканчивающиеся символом 1 строки с номером проверочных параллелограммов образуют совокупность, в которую каждая двоичная последовательность длины содержащая не менее двух единиц, входит ровно один раз. Суммы образуют составные проверки, которые содержат только символ

3) В качестве остальных составных проверок берутся символы синдрома, которым в матрице соответствуют строки вида

Пример 5.12. Если применить метод Салливана для ортогонализации кода из примера 5.11, то получим следующую систему составных проверок:

Метод ортогонализации Салливана является частным случаем метода ортогонализации Месси, но он выгодно

отличается от последнего следующим. Использование метода ортогонализации Месси в примере 5.11 приводит, например, к тому, что от оказываются зависящими восемь составных проверок. Но в этом случае возникновение ошибки декодирования, когда эквивалентно появлению пачки ошибок длины 8, что резко ухудшает корректирующую способность кода по отношению к символу . В то же время при использовании метода ортогонализации Салливана ни одна из составных проверок, полученных на втором и третьем шагах, не содержит ни один из символов Поэтому с точки зрения уменьшения глубины распространения ошибок метод Салливана является оптимальным методом ортогонализации.

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

где матрица размера строками которой являются всевозможные ненулевые последовательности длины

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

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

Тогда декодер к моменту времени перейдет в нормальное рабочее состояние.

Доказательство. Сначала предположим, что и ни один из элементов не равен 1. В этом случае в правой части (5.92) ненулевым является только первый вектор, а следовательно, ровно символов множеств будут равны единице. Допустим, что в равны 1 не более символов Тогда изменить свое значение с 0 на 1 могут самое большее составных проверок. Следовательно, общее число составных проверок, принимающих значение 1, не больше, чем целая часть и решение о принимается правильно.

Далее предположим, что и все элементы за исключением равны нулю. Тогда среди элементов множества будут равны 0 самое большее элементов. Если допустить, что среди символов равны 1 не больше чем то число символов равных 1 и отличных от строго меньше чем а следовательно, строго меньше чем составных проверок изменяют свое значение с 1 на 0. В этом случае не менее составных проверок по-прежнему будут оставаться равными единице и решение о опять будет принято правильно.

Из доказанной теоремы следует, в частности, что декодер кода из примера 5.11 принимает правильное решение о при наличии в не более девяти символов 1, если ошибок декодирования раньше не было, и при наличии в не более пяти символов 1, если перед этим произошла ошибка декодирования.