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

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

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

Класс двоичных сверточных кодов, исправляющих одну ошибку и называемых кодами Вайнера-Эша, аналогичен классу кодов Хэмминга. Для каждого положительного целого т существует ((/п + 1) 2", (m+l) (2" - 1))-код Вайнера~Эша. Такой код определяется проверочной матрицей Н (2*" - 1,2" - 1 - т)-кода Хэмминга. Это проверочная [т X (2" - 1) ]-матрица, в которой все 2*" - 1 столбцов различны и ненулевые. Выберем такую матрицу, используем ее строки для определения множества 11 X X (2" - 1)]-матриц Рь Рт и обозначим через Pj вектор-

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

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

Р1г О

О о р,;

J((m+l)2m)

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

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

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

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

1111 110 0

10 10 о 00 о о 0*0 о

1111

110 0 10 10 0 0 0 0

1111

110 0 10 10

1111

110 0

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

Н(«2) =

1 1 1

1 О О о 1 О

0 0 0 0

1111

110 0

0 0 0 0 0 0 0 0

1111

Серии

информационных Битое

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

Серии "битое

КО0ОВОЕО

слова

этого столбца в первом кадре с тем же столбцом во втором кадре равна (1, О, О, 0) и этот столбец содержится в первом кадре. Следовательно, существуют три столбца, сумма которых равна нулю. □

Например, (12,9)-код Вайнера-Эша соответствует т = 2. Его проверочная матрица равна