2.4.3. КОДИРОВАНИЕ ИСТОЧНИКА

Кодирование источника сводится, как уже было указа1Но в разд. 2.4.2, к представлению символов алфавита источника с помощью двоичных кодовых комбинаций. Для передачи данных кодирование источника кодовыми комбинациями одинаковой длины имеет первостепенное значение, в то время как экономное кодирование источника представляет скорее принципиальный интерес.

2.4.3.1. ЭКОНОМНЫЕ КОДЫ

Известный пример экономного кода - код Шеннона-Фано, представленный в табл. 2.2 для случая немецкого языка [2.20],

л «

содержит 26 букв лативокого алфавита, буквы А, О, U и знак пробела, т. е. объем его составляет 30 знаков {Хг}. Во втором столбце

Таблица 2.2

Экономное кодирование источника: код Шеннона-Фано (ШФ)

КодШФ

Pi logj(l/Pj)

Код ШФ

Пробел Е N R I S

D Н А

С G М

0,15149 0,14701 0,08835 0,06858 0,06377 0,05388 0,04731 0,04385 0,04355 0,04331 0,03188 0,02931 0,02673 0,02667 0,02134

0,41251 0,40661 0,30927 0,26512 0,25323 0,22705 0,20824 0,19783 0,19691 0,19616 0,15847 0,14927 0,13968 0.13945 0,11842

0111

1000

1001

1010

10110

101II

11000

11001

11010

11011

111000

о р д о

,! Y

0,01772 0,01597 0,01423 0,01420 0,01360 0,00956 0,00735 0,00580 0.00499 0,00491 0,00255 0,00165 0,00017 0,00014 0,00013

0,10389 0,09585 0,08727 0,08716 0,08431 0,06412 0,05209 0,04309 0,03817 0,03764 0,02194 0,01521 0,00217 0,00181 0,00167

111001

111010

111011

111100

ИНОЮ

1111011

1111100

1111101

1111110

11111110

111111110

1111111110

11111111110

111111111110

111111111111

приведены вероятности р(хг) их появления, соответствующие относительной частоте в длинных текстах на немецком языке. Знаки располагаются в списке по убывающей вероятности. Сумма всех вероятностей, разумеется, равна единице. Б третьем столбце помещены соответствующие составляющие P{log2(l/Pi) энтропии Н(Х). Четвертый столбец содержит двоичные кодовые комбинации кода Шеннона-Фано. Он начинается с трехразрядных комбинаций для знаков с высокой вероятностью и закамчивается 12-разрядными комбинациялш для знаков с малой вероятностью. Кро-44

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

Сокращение избыточности вытекает из следующего; алфавит из 30 знаков согласно (2.8) имеет максимальную энтропию Но= = log230= 4,907 бит. Энтропия но (2.7) - является суммой компо--нент из столбца 3. Она составляет Н(Х)-А,\\Ъ бит и выражает минимальное значение средней длины комбинации при двоичном кодировании. Отсюда избыточность алфавита по (2.17) R = =4,907-4,115=0,702 бит на знак. В коде Шеннона-Фано средняя длина комбинаций, перечисленных в столбце 4 табл. 2.2, получается следующим образом. Для каждой комбинации число ее разрядов, т. е. степень неопределенности в битах, умножается на соответствующую ей вероятность pi ее появления, и эти произведения суммируются по всем комбинациям. В результате средняя длина комбинации получается равной 4,151 бит на знак, что лишь немного превышает энтропию заданного алфавита. Все еще содержащаяся в коде Шеннона-Фано избыточность равна 4,151- -4,115=0,036 бит на знак, т. е. существенно меньше, чем первоначальная избыточность алфавита.

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

2.4.3.2. КОДИРОВАНИЕ ИСТОЧНИКА ДЛЯ ПЕРЕДАЧИ ДАННЫХ КОДОВЫМИ КОМБИНАЦИЯМИ ОДИНАКОВОЙ ДЛИНЫ

Равномерные коды, у которых все кодовые комбинации имеют одинаковую длину п (п-разрядные двоичные коды), обеспечивают существенное упрощение аппаратуры для сбора, передачи и обработки данных. Объем такого кода, т. е. количество возможных двоичных комбинаций длины п, ограничен числом Л=2". В аппаратуре телеобработки данных нашли применение равномерные коды, которые различаются числом разрядов и упорядочением символов в комбинациях - отчасти разным в аппаратуре, выпускаемой разными фирмами. Коды также -изменяются в связи с развитием техники телеобработки данных. Обзор различных видов этих кодов дан Г. Берндтом [2.21].

У(помянем прежде всего следующие два кода, предусмотренные международными нормами для передачи данных: пятиэле-м-ентный телеграфный код (алфавит № 2 МККТТ) [2.22] и новый, семиэлементный код (алфавит № 5 МККТТ) [2.23], который, как правило, дополняется до восьми элементов еще одним контрольным двоичным разрядом (см. разд. 2.4.4.2), присоединенным к ко довой комбинации [2.24]. б обоих случаях кодовые комбинаций

могут быть переданы как стартстопные знаки. Кодовым комбинациям тогда предшествует стартовый элемент, а в конце их присоединяется стоП-элемент. У телеграфного кода он имеет как Минимум полуторную длительность по сравнению с элементом сигнала. У алфавита № 5 стоп-элемент при скоростях до 200 бит/с имеет по сравнению с длительностью элемента сигнала ту же или двукратную длительность, а лри более высоких скоростях - длительность сигнала [2.24]. Соответствие между двоичными символами и значащими позициями указано в табл. 2.3 [2.25].

Таблица 2.3

Формы представления и обозначения двоичных символов

Пятиэлементный телеграфный код (алфавит № 2 МККТТ) иредставлен в табл. 2.4. Так как каждая кодовая комбинация состоит из пяти двоичных знаков, от bi до Ьв, то объем кода 2=32. В соответствии с этим в табл. 2.4 комбинации имеют номера от 1 до 32. Общее требуемое число букв, цифр, знаков препинания и управления, однако, больше чем 32. Поэтому комбинации с 1-ю гю 26-ю используются дважды. В буквенном ряду они охватывают латинские буквы, в цифровом ряду - цифры от О до 9, знаки препинания и некоторые знаки управления;.к последним принадлежит знак «Кто там?», с помощью которого автоматически запрашивается устройство выдачи опознавательных знаков противоположной оконечной установки. Далее имеется комбинация № 32, занятая только нулем, а в цифровоМ ряду некоторые места оставлены

свободными для национальных, особых знаков (например, А, О,

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

Семиэлементный код МОС (табл. 2.5) с 1968 г. предусмотрен нормами МККТТ как алфавит № 5 [2.23]. Большой объем, 2= = 128, кодовых комбинаций обеспечивает представление в алфавите знаков управления и препинания, цифр, больших и малых букв. Столбцы таблицы показывают его подразделение на категории. Столбцы О и 1 содержат знаки управления, значение которых

• 46 . .