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.

0) Положить

1) Положить

2) Вычислить Если то перейти к шагу 6.

3) Положить

4) Вычислить Если то перейти к шагу 6.

5) Положить

6) Если то построение кода заканчивается; в противном случае положить и перейти к шагу 1.

Заметим, что описанный алгоритм исключает возможность удлинения порождающей последовательности путем присоединения символов Как показали Лин и Лайн [22], для данного алгоритма всегда

Таблица 6.2 (см. скан) Коды со скоростью

Коды, построенные с помощью алгоритма 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.