12.5. НЕКОТОРЫЕ ПРОСТЫЕ СВЕРТОЧНЫЕ КОДЫ

Известно всего несколько конструктивных классов сверточных кодов. В настоящее время не известеи ни один такой класс с алгебраической структурой, сравнимой со структурой кодов БЧХ, исправляющих I ошибок; таким образом, не существует конструктивных методов поиска сверточных кодов с большой длиной кодового ограничения. Большинство известных и используемых в настоящее время лучших сверточных кодов было найдено поиском на ЭВМ.

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

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

вектор-строку, элементов которой равны единице. Тогда проверочная матрица кода Вайнера-Эша запишется в виде

и

где 1 — матрица размера состоящая из одной единицы, и 0 — матрица размера состоящая из одного нуля.

Теорема 12.5.1. Минимальное расстояние кода Вайнера—Эша равно 3; таким образом, он является сверточным кодом, исправляющим одну ошибку.

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

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

этого столбца в первом кадре с тем же столбцом во втором кадре равна и этот столбец содержится в первом кадре.

Следовательно, существуют три столбца, сумма которых равна нулю.

Например, -код Вайнера-Эша соответствует Его проверочная матрица равна

При таком усечении кода, чтобы его проверочная матрица соответствовала длине блока 12, получается следующая проверочная матрица:

Рис. 12.12. Кодер для -кода Вайнера-Эша.

Порождающая матрица равна

(см. скан)

а порождающая матрица кода, усеченного до длины блока 12, представляется виде

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

Кодер для -кода Вайнера-Эша представлен на рис. 12.12. Каждому порождающему многочлену на схеме соответствует отдельный КИО-фильтр.

Большинство известных наиболее употребительных сверточных кодов было получено поиском на ЭВМ. На рис. 12.13 приведена таблица таких кодов.

(кликните для просмотра скана)