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

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

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

0(12)

100 1 ООО 1 ООО 1 010 1 ООО 1 ООО о 001 1 ООО о ООО I

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

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

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

ПорожЭаюцая матрица из многочленов (выражена через коэффициенты многочлена)

(9, 3, 8) (12,4, 10) (15, 5, 12) (18,6, 13) (21,7, 15) (24,8, 16) (27,9, 18) (30, 10, 20) (33, 11,22) (36, 12, 24). (39, 13,24) (42, 14, 26)

101 1101 10101 111001 1101101 10101001 111101101 1111001001 II01011100I 111011111001 110110I0I000I 10100101110001

1011

110101 1010011 10011011 110011011 1010111101 10011101101 110010U1101 1011110110001 10001101110111

111 nil mil

ЮПИ lOlllll

июни

lOOlOOIII IIOIIOOIII lOlllllOOIl 101011010011 lOOOllOlllIll llOIIOIOOIllll

Рис. 12.13. Некатастрофические двоичные сверточные коды с максимальным свободным расстоянием.

12.6. АЛГОРИТМЫ СИНДРОМНОГО ДЕКОДИРОВАНИЯ

Предположим, что принята бесконечная последовательность v, состоящая из слова сверточного кода и шума:

V = с + е.

Точно так же, как и в случае блоковых кодов, можно вычислить синдром:

S = vH = eH

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

Приведем примеры различных синдромных декодеров. Начнем с декодера для (12,9)-кода Вайнера-Эша. Он показан на рис. 12.14. Входящий поток битов поступает на Пр параллельных линий; синдром вычисляется путем нахождения проверочного бита по принятым информационным битам и его сравнения с принятым проверочным битом. Необходимо вычислить лишь столько синдромных битов, сколько их требуется для исправления одиночной ошибки в первом кадре. Возможные конфигурации одиночных ошибок в первых трех кадрах и соответствующие первые три бита синдрома приведены в виде таблицы на рис. 12.15. Заметим, что правый бит равен единице тогда и только тогда, когда в первом кадре имеется ошибка. В этом случае два других бита синдрома точно определяют местонахождение ошибки в первом кадре.

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

Необходимо рассмотреть еще одну задачу. После исправления первого кадра нужно изменить синдром таким образом, чтобы он не вызывал ошибочного исправления в следующем кадре. Это можно сделать несколькими способами, и хотя все они пригодны для данного кода, в случае более мощного кода они ведут себя совершенно по-разному. Возможны два варианта:

1) после каждого исправления ошибки устанавливается нулевое состояние регистра синдрома;