6.10. Коды, используемые при декодировании с обратной связью
Важнейшей характеристикой сверточных кодов, исправляющих случайные ошибки, точно так же, как в блоковых кодах, является их минимальное расстояние. Однако сверточным кодам не присущи алгебраические свойства, подобные свойствам циклических кодов, и строить сверточные коды с большим минимальным расстоянием методами, подобными методам построения БХЧ-кодов, не удается. Ряд сверточных кодов с большим минимальным расстоянием для скоростей передачи
был построен Бусгангом [21]. Относительно регулярный метод построения таких кодов предложен также Лином [22]. Здесь будет описан метод поиска сверточных кодов с помощью некоторых простых алгоритмов, предложенных Костелло [19], и приведены получающиеся коды. Класс построенных Костелло кодов является наиболее широким из всех известных в настоящее время. При этом Костелло ввел два важных понятия: столбцовое расстояние, используемое при декодировании с обратной связью, и свободное расстояние, используемое при последовательном декодировании.
Порождающая матрица
сверточного кода, введенная в разд. 5.2, при скорости передачи
имеет следующий вид:
Подматрицу матрицы
состоящую из первых и
строк и
столбцов, обозначим через
Пусть
— информационный вектор. Введенное в разд. 6.9.1 минимальное расстояние
сверточного кода определяется равенством
Используемое ниже столбцовое расстояние определяется следующим образом.
Определение 6.1. Столбцовое расстояние порядка и сверточного кода со скоростью передачи
равно
Сравнивая формулы (6.194) и (6.195), можно заметить, что
Введенное столбцовое расстояние обладает следующими свойствами:
где
— первая строка матрицы
Свойство 1 непосредственно следует из определений минимального расстояния кода и минимального веса. Полагая
получаем
отсюда и из свойства 1 следует справедливость свойства 2. Свойство 3 следует из того, что вектор
всегда является префиксом вектора
Как указывалось выше, сверточный код тем лучше, чем большее отношение
он имеет. Одним из критериев, позволяющих судить о том, является ли отношение
плохим или хорошим, является близость этого отношения к границе Гилберта, определяемой формулой (6.187). Так как число сумматоров по модулю 2, содержащихся в показанном на фиг.
-разрядном кодере сверточного кода со скоростью
в точности равно
по, то при заданных параметрах
более предпочтительными оказываются коды, которые имеют меньшее значение
а) Коды со скоростью
Коды с такой скоростью могут быть построены с помощью следующего алгоритма:
Алгоритм
0) Положить
1) Положить
2) Вычислить
Если
то перейти к шагу 4.
3) Положить
4) Если
то построение кода заканчивается; в противном случае положить
и перейти к шагу 1.
Свойство
Доказательство. Из того, что
и из свойства 2 следует, что
. С другой стороны, шаги 2—4 алгоритма таковы, что при
и только в этом случае величина
увеличивается на единицу, но не больше. Следовательно,
а поэтому
В силу свойства 2 столбцового расстояния
но, как следует из свойства 1-1, в данном случае величина
принимает минимальное возможное значение, а это означает в свою очередь, что число сумматоров по модулю 2 в кодере также минимально.
Свойство 1-2. Если то
для всех
Доказательство. Предположим, что
при некотором
. В этом случае информационная последовательность
всегда будет порождать кодовое слово веса
так что
Однако это противоречит тому, что в силу свойства I при сделанных предположениях
Следовательно, если
то для алгоритма I всегда
Из свойства 1-2 следует, что всякий раз, когда коэффициент
и полагается равным 1, следующий коэффициент
должен равняться 0. Это свойство алгоритма I позволяет сократить число операций 1 и 2 при построении кода.
Свойство 1-3. Пусть
порождающий вектор, получающийся при построении кода с помощью алгоритма
Пусть
другой порождающий вектор той же длины, что и
но отличный от последнего и такой, что
при любом целом
а имени о
вектор, любой символ 1 которого увеличивает минимальное расстояние ровно на единицу. Тогда существует такое целое число
что
при
Доказательство. Пусть
начальная точка, в которой начинают различаться порождающие векторы
Допустим, что
Тогда
Это означает, что столбцовое расстояние в точке
увеличивается, а следовательно, согласно алгоритму I, следовало бы положить
но это противоречит предположению о том, что
Следовательно, в точке
где порождающие векторы
впервые начинают различаться,
Коды, которые могут быть построены с помощью других алгоритмов, отличаются от кодов, алгоритм построения которых был описан выше, тем, что их порождающие последовательности могут не содержать символ 1 на позиции, где он мог бы быть введен.
Коды с
полученные с помощью алгоритма I, и их минимальное расстояние, удовлетворяющее границе Гилберта, приведены в табл. 6.1.
Таблица 6.1 (см. скан) Коды со скоростью
б) Коды со скоростью
Коды со скоростью
также можно получить, строя порождающие последовательности, удовлетворяющие условию
путем присоединения к уже построенной последовательности
совокупности из
символов, по крайней мере один из которых равен
при этом не нарушается
Коды, построенные с помощью алгоритма II, а также значения минимального расстояния, найденные из границы Гилберта, приведены в табл. 6.2.
в) Коды со скоростью
этом случае для каждого значения и должны быть определены уже три символа
Кроме того, следует заметить, что здесь при каждом значении и минимальное расстояние может увеличиться не только на 1, но и на 2. Как и все предыдущие алгоритмы, описанный ниже алгоритм позволяет построить класс порождающих последовательностей
удовлетворяющих условию
путем присоединения к построенной последовательности
совокупности трех символов
один из которых равен 1, если при этом нарушается условие
и трех символов 0 в противном случае.
Алгоритм III.
0) Положить
1) Положить
и перейти к шагу 8.
2) Положить
и перейти к шагу 8.
3) Положить
и перейти к шагу 8.
4) Положить
и перейти к шагу 8.
5) Положить
и перейти к шагу 8.
6) Положить
и перейти к шагу 8.
7) Положить
и перейти к шагу 9.
8) Вычислить
Если
то перейти к
9) Если
то построение кода заканчивается; в противном случае положить
и перейти к шагу 1.
Коды, построенные с помощью этого алгоритма, приведены в табл. 6.3.