менные окна (интервалы), в которых ему разрешается передача. Длинные двоичные сообщения разделяются на пакеты, и один пакет передается в отведенное временное окно. Из-за нарушения синхронизации или дисциплины обслуживания некоторые пакеты могут быть утеряны. Подходящие коды, контролирующие ошибки, защищают от таких потерь, так как утерянные пакеты можно восстановить по известным пакетам.

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

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

1.4. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

Двоичный код мощности М и длины п представляет собой множество из М двоичных слов длины п, называемых кодовыми словами. Обычно М = 2% где k - некоторое целое число; такой код называется двоичным (м, й)-кодом.

Например, можно построить следующий код:

1 О 1 О Г 10 0 10 0 1110

11111.

Это очень бедный (и очень маленький) код с /И = 4 и /г = 5, но он удовлетворяет приведенному выше определению. Данный код можно использовать для представления 2-битовых двоичных чисел, используя следующее (произвольное) соответствие:

00 10101,

01 10010,

10 --01110,

11 11111.

Если получено одно из четырех 5-битовых кодовых слов, то полагаем, что соответствующие ему два бита являются правильной информацией. Если произошла ошибка, то мы получим 5-битовое слово, отличающееся от кодовых слов. Тогда попытаемся найти наиболее вероятно переданное слово и возьмем его в качестве оценки исходных двух битов информации. Например, если мы приняли 01100, то полагаем, что передавалось 01110, и, следовательно, информационное слово равнялось 10.

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

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

По неопытности может показаться, что достаточно-определить требования к хорошему коду и затем предпринять машинный поиск

) Скорость - величина безразмерная или, возможно, измеряемая в единицах бит/бит или символ/символ. Ее следует отличать от другого называемого тем же термином скорость понятия, измеряющего канальную скорость в бит/с. Используется и другое определение скорости: R = {kin) \og(fl, единицей которой, является нат/символ, где один нат равен logs е битов. Принято также определение R = (kin) logg q, в котором скорость измеряется в единицах бит/символ,

ПО множеству всех возможных кодов. Но сколько кодов существует для данных п и Каждое кодовое слово представляет собой последовательность п двоичных символов, и всего имеется 2 таких слов; следовательно, код описывается п•2двоичными символами. Всего существует способов выбора этих двоичных симво-

лов; следовательно, число различных (м, й)-кодов равно 2"-*. Конечно, очень многие из этих кодов не представляют интереса (как в случае, когда два кодовых слова равны), так что надо либо проверять это по ходу поиска, либо развить некоторую теорию, позволяющую исключить такие коды.

Например, выберем (м, k) == (40, 20) - код, весьма умеренный по современным стандартам. Тогда число таких кодов превзойдет величину 10" - невообразимо большое число! Следовательно, неорганизованные процедуры поиска бессильны.

В общем случае блоковые коды определяются над произвольным конечным алфавитом, скажем над алфавитом из q символов 0, 1, 2, q- }. На первый взгляд введение алфавитов, отличных от двбичного, может показаться излишним обобщением. Из соображений эффективности, однако, многие современные каналы являются недвоичными, и коды для этих каналов должны бытьнедвоичными. На самом деле коды для недвоичных каналов часто оказываются достаточно хорошими, и сам этот факт может служить причиной для использования недвоичных каналов. Двоичные данные источника тривиальным образом представляются символами 9-ичного алфавита, особенно если q равно степени двойки, как это обычно и бывает на практике.

Определение 1.4.1. Блоковый код мощности М над алфавитом из q символов определяется как множество из М -ичных последовательностей длины п, называемых кодовыми словами.

Если 7 = 2, то символы называются битами. Обычно М = q для некоторого целого k, и мы будем интересоваться только этим случаем, называя код (п, й)-кодом. Каждой последовательности из k 9-ичных символов можно сопоставить последовательность из п д-ичных символов, являющуюся кодовым словом.

Имеются два основных класса кодов: блоковые коды п древовидные коды; они иллюстрируются рис. 1.2. Блоковый код задает блок из k информационных символов /г-символьным кодовым словом. Скорость R блокового кода ) определяется равенством

R = kin.