Файл: История техники связи.pdf

Ðèñ. 4.10

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

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

Изящный алгоритм последовательного декодирования, в соответствии с которым в декодере просматриваются не все возможные пути по ребрам кодовой решетки сверточного кода, а только наиболее вероятные, был предложен в 1957 г. американским ученым Дж. Возенкрафтом [28]. В соответствии с этим алгоритмом, если декодер выбрал на каком-то шаге неверный путь, то он вскоре обнаруживает, что при последующих выборах ребер происходит быстрое увеличение расстояния между выбранным путем и принимаемой последовательностью. Это является сигналом к тому, чтобы декодер сделал несколько шагов назад и начал исследовать альтернативные, более правдоподобные пути. При последовательном декодировании число вычислений на одно ребро является случайной величиной, и в буферной памяти декодера должны храниться вычисленные расстояния для всех исследованных ветвей. Первые исследования алгоритма последовательного декодирования провели Дж. Возенкрафт и Б. Рейффен [29]. В 1963 г. его усовершенствовал

Р.М. Фано, в 1966 г. эффективную модификацию этого алгоритма разработал отечественный ученый К.Ш. Зигангиров [30], а несколько позднее (1969 г.) аналогичный алгоритм был предложен американским ученым Ф. Джелинеком.

Значительным достижением в области теории кодирования явилась разработка в 1967 г. одним из крупнейших американских ученых А. Витерби эффективного с вы- числительной точки зрения алгоритма декодирования сверточных кодов по максимуму правдоподобия [31]. Этот алгоритм, в отличие от алгоритма последовательного декодирования, исследует все возможные пути по кодовой решетке на длине кодового ограничения K. Поэтому он применим для декодирования сверточных кодов при сравнительно небольших значениях K = 7 – 10.

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

5.4. Коды, корректирующие пакеты ошибок

В реальных каналах связи ошибки при приеме последовательно поступающих символов часто происходят не независимо и возникают пакеты ошибок. Для систем связи в таких каналах построены специальные коды. Для этой цели могут быть использованы блочные коды, построенные в конце 50-х гг. М.А. Эпштейном [32], Н. Абрамсоном [33] и П. Файером [34]. Ими были созданы коды, корректирующие одиночные пакеты ошибок. В 1963 г. Дж. Стоун создал коды, способные корректировать несколько пакетов ошибок в кодовой комбинации [35]. Для коррекции пакетов ошибок были предложены сверточные коды [26, 27].

Следует отметить, что задача коррекции пакетов ошибок может быть сведена к задаче коррекции независимых ошибок путем применения метода перемежения символов. Этот метод состоит в перестановке передаваемых символов таким образом, чтобы соседние символы передаваемой кодовой комбинации оказывались разнесенными в достаточной степени во времени так, чтобы их искажения в канале связи были независимыми. На приеме производится восстановление исходного порядка символов. Эта простая идея, выдвинутая в 1960 г. отечественными учеными — академиком А.А. Харкевичем и профессором Э.Л. Блохом [36], а позднее (1970 г.) американским ученым Дж. Л. Рамсеем [37], сегодня применяется во многих системах радиорелейной и подвижной связи, в которых при приеме цифровых сигналов группируются ошибки.

5.5. Итерированные коды

Â1954 г. П. Элайсом [38] был предложен важный класс итерированных кодов.

Âдвухмерном случае эти коды формируются следующим образом: последователь-

ность информационных символов длиной N1 = N1 × N2 записывается в буферную память в виде таблицы, имеющей N1 – C1 столбцов и N2 – C2 строк, как это показано на рис. 4.11.

Cимволы отдельных строк и столбцов кодируются с помощью корректирующих

кодов, имеющих соответственно C1 è C2 проверочных символов и расстояния между кодовыми комбинациями, равные соответственно d1 è d2.

330ПИОНЕРЫ ИНФОРМАЦИОННОГО ВЕКА. История развития теории связи

Ï.Элайсом было показано, что для такого кода расстояние между кодовыми

комбинациями равно d = d1 × d2. С помощью этих кодов вначале по линии связи передаются N1 символов первой строки. Этот процесс продолжается до тех пор, пока не будут переданы (N2 – C2) строк. Затем определяются последние C2 строки, содержащие проверочные символы, сформированные для каждого столбца табли-

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

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

Ðèñ. 4.11

П. Элайсом были исследованы коды, имеющие k измерений. В этом случае длина

k

кода равна N = ∏ Ni .

i =1

Если же k = 2, то кодирование с помощью итерированных кодов можно пояснить, пользуясь таблицей рис. 4.11.

П. Элайс показал, что при выполнении определенных ограничений на вероятность ошибки в канале связи и длину Ni парциальных кодов в соответствии с теоремой К. Шеннона вероятность ошибочного приема символов на выходе декодера стремится к нулю при k → ∞.

Питер ЭЛАЙС

Питер Элайс родился 23 ноября 1923 г. в Брунсвике (штат Нью-Йорк) в семье инженера, который был сотрудником лаборатории Томаса Эдисона. В 1942 г. он поступил в Бостоне в колледж, на основе которого через два года был создан Массачусетский технологический институт (МТИ). После окончания МТИ в 1944 г. Элайс был призван служить радистом в военно-морской флот США. После увольнения в запас в чине помощника капитана первого класса по электронному оборудованию П. Элайс продолжил свое образование в Гарвардском университете, где позже получил ученую степень доктора наук.

Â1953 г. он начал преподавать в МТИ. В 1956 г. стал доцентом, а в 1960 г. —–—профессором МТИ. Позднее он получил звание почетного профессора и главного лектора. В МТИ он преподавал до 1991 г. и одно время был деканом факультета электротехники и ком-

пьютерных наук. В 1976 г. П. Элайс начал работать в Лаборатории проблем разработки компьютеров. Он также работал в Исследовательской лаборатории электроники, в которой занимался проблемами теории информации и ее применений к системам связи и обработки данных.

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

Â1954 г. им было введено важное понятие сверточного кода. Этот класс кодов интенсивно исследовался многими учеными. Для этих кодов Дж. Возенкрафтом был предложен метод последовательного декодирования, а Э. Витерби –— широко используемый на практике алгоритм декодирования по методу максимального правдоподобия. В 1998 г. за это научное достижение П. Элайс был отмечен золотой юбилейной медалью Секции теории информации IEEE.

Âэтом же году П. Элайс выдвинул идею построения итеративных кодов. В двухмерном

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

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

Â1955 г. Элайсом была доказана теорема кодирования для кодов с проверкой на четность в двоичном симметричном канале и в канале со стиранием отдельных символов. Он установил важный теоретический результат, который показывал, что при скоростях, близких

êпропускной способности, границы случайного кодирования и сферической упаковки экспоненциально совпадают. В этом же году, работая в группе профессора Р. Фано в Исследовательской лаборатории электроники (МТИ), П. Элайс создал первые практически действующие кодер и декодер, позволяющие передать информацию с заданной скоростью и произвольно

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

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

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

Â1963 г. П. Элайс предложил важный класс арифметических кодов, которые в дальнейшем получили применение в коммерческих системах устранения избыточности. Эти коды, усовершенствованные в 1976 г. американскими учеными Дж. Риссаненом и Р. Паско, оказались более простыми в реализации по сравнению с известными оптимальными кодами Хаффмена.

Количество публикаций у П. Элайса невелико. Однако его результаты вошли во все монографии, посвященные теориям информации и кодирования. В 1976 г. была опубликована его книга «Очерки теории информации».»

За новаторские исследования в области теории информации и значительный вклад в подготовку инженеров профессор П. Элайс был избран почетным членом Института инженеров по электротехнике и электронике (IEEE), Американской ассоциации содействия развитию наук, Национальной академии наук и Национальной инженерной академии США, Американской академии искусств и наук, а также многих других научных обществ и ассоциаций.

Он был председателем Секции теории информации IEEE, членом комитетов IEEE по присуждению премий и по стандартизации. Кроме того, он был одним из трех главных редакторов, основавших в 1957 г. международный журнал «Информация и контроль»» (Information and Control), входил в редакционный совет издательства ИМТ и журналов Proceedings of the IEEE и IEEE Spectrum.

Профессор Питер Элайс скончался 10 декабря 2001 г. в Кембридже (США).

5.6. Каскадные коды

В 1964 г. Д. Форни предложил каскадные коды, которые оказались эффективным средством исправления как одиночных, так и пакетированных ошибок [39]. Каскадное кодирование характеризуется тем, что на передаче используются два последовательно включенных кодека, как правило, различного типа. Эти кодеки оптимизированы для исправления ошибок различной конфигурации. Схема каскадного кодирования показана на рис. 4.12. Внутренний кодек и декодер сопряжены соответственно с модулятором, в котором осуществляется формирование сигналов, передаваемых по каналу связи, и с демодулятором, который, обрабатывая принятый сигнал, формирует символы, поступающие на вход декодера.

Элементы, указанные на рис. 4.12 между выходом внешнего кодека и входом внешнего декодера, образуют, по терминологии Д. Форни, суперканал, внешний и внутренний кодек — суперкодер, а внутренний и внешний декодер – супердекодер. Внешний кодер, добавляя проверочные символы, формирует из последовательности k информационных символов на своем выходе блоки из n символов.

Таким образом, он работает с кодовой скоростью r = k/n. Внешний кодек осуществляет кодирование К блоков по n символам, преобразуя их путем добавления проверочных блоков в N блоки. Таким образом, kK информационных символов преобразуются в каскадный код длиной nN символов. Кодовая скорость в данном случае составляет R = kK/nN.

Ðèñ. 4.12

Значимые результаты по исследованию каскадных кодов были получены Д. Форни и отечественными учеными Э.Л. Блохом и В.В. Зябловым [40], исследования которых в 1976 и 1982 гг. показали, что при соответствующем выборе внутреннего и внешнего кодов каскадные коды позволяют эффективно корректировать как независимые, так и пакетные ошибки, возникающие в канале связи. Ими было также показано, что с помощью таких кодов с увеличением их длины можно получить рост сложности алгоритмов кодирования и декодирования по степенному закону. Каскадные коды перспективны для применения в системах связи.

Дэвид ФОРНИ

Выдающийся американский ученый Дэвид Форни, внесший значительный вклад в теорию кодирования сообщений, родился 6 марта 1940 г. в Нью-Йорке. Его отец Дж. С. МакДоннелл был крупным авиационным инженером и возглавлял фирму McDonnell Aircraft. Инженерами были и два его старших брата. Это повлияло на выбор Д. Форни профессии. Он закончил престижную школу и поступил в Принстонский университет, в котором получил глубокое базовое образование. Форни изу- чал философию, архитектуру, социологию, литературу, физику и математику. Университет он окончил в 1961 г. и получил степень бакалавра. Дальнейшее образование