+)-Ч+)

х+х + \ х +Х + I

<±>

1 =(х+х +1) (х+х-х) + (x+х + I) (Х+Х +х + \) Рис. 12.11. Подробная схема регистра сдвига.

Определение 12.2.3. Сверточный код с матрицей порождающих

многочленов G (х), определители (х), 1=1, .... (Ц), подматриц которой удовлетворяют условию

НОД [Д, (х), 1.....{1:)1 = х-

при некотором а, называется некатастрофическим сверточным кодом. В противном случае он называется катастрофическим сверточным кодом.

Как и в предыдущем случае, некатастрофический код может быть обращен. Иначе говоря, существует (щ X Ло)-матрица многочленов С* {х), такая, что

G(x)G(x) = хЧ,

где I - единичная матрица размера X k, а х°- определяет некоторую фиксированную задержку. Найти G* {х) в общем случае затруднительно, и мы не будем этим заниматься. В случае систематических кодов сформулированные в определении 12.2.3 условия всегда выполняются. Систематические коды всегда являются некатастрофическими.

12.3. ИСПРАВЛЕНИЕ ОШИБОК И ПОНЯТИЯ РАССТОЯНИЯ

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

12.3. ИСПРАВЛЕНИЕ ОШИБОК; ПОНЯТИЯ РАССТОЯНИЯ 413

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

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

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

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

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

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

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

Определение 12.3.1. Минимальное расстояние Хэмминга для любых начальных сегментов длины / кадров всех пар кодовых слов, отличающихся начальным кадром, называется 1-м минимальным расвтоянием сверточного кода и обозначается через d1. Если / равно т -\~ \, то оно называется просто минимальным расстоянием и обозначается через d*. Последовательность d\, dl, dz, ... называется дистанционным профилем сверточного кода.

Так как сверточный код линеен, одно из двух кодовых слов может целиком состоять из нулей. В этом случае /-е минимальное расстояние равно минимальному из всех весов сегментов длины / кадров кодовых слов с ненулевым первым кадром. Оно может быть вычислено по маркированной решетке. Из рис. 12.5 следует, что для сверточного (6, 3)-кода d* = 2, 2 = 3 и d* = 5 при всех i 3.

Предположим, что сверточный код имеет /-е минимальное расстояние dl. Если в первых / кадрах произошло не более t ошибок, причем t удовлетворяет неравенству

2 + 1 < dh

то ошибки, которые появились в первом кадре кодового слова, могут быть исправлены. В частности, выберем / = /п + 1; минимальное расстояние кода d* равно dJn+\- Тогда при t, удовлетворяющем неравенству

2 + 1 < d*,

код исправит первый кадр кодового слова, если на длине первого блока появилось не более t ошибок. Такой код называется сверточным кодом, исправляющим t ошибок. Более точное, хотя и более громоздкое название: сверточный код, исправляющий t ошибок на длине блока.

Определение 12.3.2. Свободным расстоянием сверточного

кода G называется doo = max di.

Очевидно, что

Определение 12.3.3. Свободной длиной п сверточного кода называется длина имеющего наименьший вес ненулевого началь-