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

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

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

Известный пример экономного кода — код Шеннона-Фано, представленный в табл. 2.2 для случая немецкого языка [2.20], содержит 26 букв латинского алфавита, буквы и знак пробела, т. е. объем его составляет 30 знаков Во втором столбце приведены вероятности их появления, соответствующие относительной частоте в длинных текстах на немецком языке.

Таблица 2.2. Экономное кодирование источника: код Шеннона-Фано (ШФ)

Знаки располагаются в списке по убывающей вероятности. Сумма всех вероятностей, разумеется, равна единице. В третьем столбце помещены соответствующие составляющие энтропии Четвертый столбец содержит двоичные кодовые комбинации кода Шеннона-Фано. Он начинается с трехразрядных комбинаций для знаков с высокой вероятностью и заканчивается -разрядными комбинациями для знаков с малой вероятностью.

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

Сокращение избыточности вытекает из следующего: алфавит из 30 знаков согласно (2.8) имеет максимальную энтропию бит. Энтропия по (2.7) является суммой компонент из столбца 3. Она составляет бит и выражает минимальное значение средней длины комбинации при двоичном кодировании. Отсюда избыточность алфавита по бит на знак. В коде Шеннона-Фано средняя длина комбинаций, перечисленных в столбце 4 табл. 2.2, получается следующим образом. Для каждой комбинации число ее разрядов, т. е. степень неопределенности в битах, умножается на соответствующую ей вероятность ее появления, и эти произведения суммируются по всем комбинациям. В результате средняя длина комбинации получается равной 4,151 бит на знак, что лишь немного превышает энтропию заданного алфавита. Все еще содержащаяся в коде Шеннона-Фано избыточность равна бит на знак, т. е. существенно меньше, чем первоначальная избыточность алфавита.

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

2.4.3.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.4. Так как каждая кодовая комбинация состоит из пяти двоичных знаков, от до то объем кода . В соответствии с этим в табл. 2.4 комбинации имеют номера от 1 до 32. Общее требуемое число букв, цифр, знаков препинания и управления, однако, больше чем 32. Поэтому комбинации с 1-ю по 26-ю используются дважды. В буквенном ряду они охватывают латинские буквы, в цифровом ряду — цифры от 0 до 9, знаки препинания и некоторые знаки управления; к последним принадлежит знак «Кто с помощью которого автоматически запрашивается устройство выдачи опознавательных знаков противоположной оконечной установки. Далее имеется комбинация № 32, занятая только нулем, а в цифровом ряду некоторые места оставлены свободными для национальных, особых знаков (например, и не используются в международной связи. Переключение с букв на цифры осуществляется с помощью комбинации № 30, обратное переключение — с помощью комбинации № 29.

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

Таблица 2.4 (см. скан) Пятиэлементный телеграфный код: алфавит № 2 МККТТ

поясняется ниже; из них десять являются знаками управления передачей данных, которые применяются в процессе передачи. Столбцы 2 и 3 содержат знаки препинания и цифры, в то время как столбцы 4 и 5 в основном Предусмотрены для больших букв, а 6 и 7 — для малых.