6.11. Коды, используемые при последовательном декодировании

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

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

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

Определение 6.2. Свободное расстояние равно т. е. столбцовому расстоянию порядка Свободное расстояние обладает следующими свойствами:

Свойство 1. Для любого и в частности, своб где порождающий вектор кода.

Доказательство. Неравенство следует непосредственно из свойств столбцового расстояния. Неравенство является следствием свойства 2 столбцового расстояния.

Свойство 2. Для всех кодов, которые строятся с помощью алгоритмов I, II и

Доказательство. Справедливость свойства 2 непосредственно следует из того, что для всех кодов, которые строятся с помощью указанных алгоритмов,

Свойство 3. Для систематических кодов со скоростью передачи свободное расстояние равно

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

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

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

Алгоритм IV (предполагается, что

0) Положить

1) Положить

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

3) Положить

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

Коды, построенные с помощью этого алгоритма, обладают следующими свойствами:

Свойство для всех и.

Свойство Если на шаге 2 оказывается, что то

Теорема 6.9. При всех где свободное расстояние <гусеченного» кода с памятью на моментов времени.

Доказательство. Соотношение и следует из свойства и свойства 1 свободного расстояния. Из свойства 1 свободного расстояния также следует, что следовательно, при всех и.

Таблица 6.4 (см. скан) Коды, построенные с помощью алгоритма IV

Коды, построенные с помощью алгоритма IV, приведены в табл. 6.4. Костелло вычислил для сравнения вероятности ошибок при последовательном декодировании в случае для двух кодов: кода с своб и кода с Оказалось, что в первом случае а во втором случае Это показывает, что при последовательном декодировании коды с большими значениями являются более предпочтительными.

Задачи и упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)