Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

Таблица 10

Соотношение нулей и единиц в восьми- и шестнадцатибуквенных кодах

т. е. в таком алфавите нули встречаются в два раза чаще, чем единицы. Для N = 10 (код четырехзначный) соотношение нулей и единиц 25 к 15, т. е. нулей в 1,66 раза больше. При N = 16 наступает равенство (так как 16 = 24). При N ~ 17 (код пятизначный) соотношение нулей и единиц 52 к 33, т. е. нулей будет в 1,57 раза больше и т. д. Другими словами с увеличением числа N разница в вероятности появления 0 и I

уменьшается. Выражение log Я /log т тем точнее выражает L, чем боль­ ше N. Как видим из табл. 10, в равномерных кодах нули имеют тенден­ цию встречаться чаще, чем единицы. Разность вероятностей появления нулей и единиц с ростом N будет уменьшаться, а величина L будет при­ ближаться к отношению Я /log т, но никогда не будет ему равна.

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

70

, Рассмотрим теперь случай поблочного кодирования, где каждый из блоков состоит из М независимых букв аъ а2, ...,ам ■Выражение для энтропии сообщения из всех букв блока, согласно правилу сложения энтропий,

Я (а 1,.оа, . . . , ам) = Я Ю + Я (а2) + • • • + Н(ам) = МН(а).

По аналогии с формулой (48) запишем выражение для средней длины такого кодового блока

ния при блочном кодировании равно средней длине блока, деленной на число букв в блоке:

Нетрудно заметить, что L можно получить, разделив все части нера­ венства (51) на М. Тогда общее выражение среднего числа элементар­ ных символов на букву сообщения

затрачиваемых на передачу одной буквы, неограниченно приближает-

Н

ся к величине ------. log т

Выражение (53) является основным выражением фундаментальной теоремы кодирования при отсутствии шумов. Сама теорема может быть сформулирована следующим образом:

при кодировании множества сигналов с энтропией Н в алфавите, насчитывающем т символов, при условии отсутствия шумов средняя длина кодового слова не может быть меньше, чем Н/log т. Если вероят­ ности сигналов не являются отрицательными степенями числа т, то точное достижение указанной границы невозможно; но при кодировании достаточно длинными блоками к этой границе можно сколь угодно приблизиться [47].

Для двоичных кодов при кодировании сообщений, состоящих из М буквенных блоков, можно выбрать такое М, что среднее число двоичных единиц на букву сообщения будет сколь угодно близким к log2 т. Общее число элементарных символов на все сообщение будет равно М log2m. Это позволяет для двоичных кодов основную теорему кодирования сформулировать так: при кодировании сообщений в двоич­ ном алфавите с ростом количества кодовых слов среднее число ■двоич­ ных знаков на букву сообщения приближается к энтропии источника сообщений.

71

Если вероятности появления сигналов являются целочисленными отрицательными степенями двух:

то среднее число двоичных знаков на букву в точности равно энтропии источника сообщений.

Выводы: 1. Чем длиннее первичное кодовое слово, тем точнее ве­

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

3. Из какого бы числа букв ни состоял алфавит, целесообразно коди­ ровать сообщения не побуквенно, а поблочно.

Задачи к теме 8

1. Построить код для 32-буквенного алфавита с минимальной длиной кодовых слов, если в текстах буквы встречаются с равными вероятностями, а число качествен­ ных признаков т = 2. Чему будет равна длина кодовых слов при т = 8; т = 16?

2.Чему равна минимальная средняя длина кодового слова для передачи ук­ раинских текстов без учета взаимозависимости между буквами алфавита? 1

3.Какое минимальное число вопросов необходимо задать собеседнику, чтобы угадать любое число из 240, если собеседник отвечает только «Да» и «Нет»?

4.Определить минимальную среднюю длину коАовых слов при передаче анг­ лийских текстов: равновероятным алфавитом, неравновероятным алфавитом, с уче­ том 2, 3, 5 и 8-буквенных сочетаний 12, если сообщение кодируется 20-буквенными блоками?

5. Требуется передать четыре сообщения двоичным кодом и кодом Морзе.

Вкаком случае длина кодовых слов будет меньше?

6.Чему равна минимальная длина кодовых слов для передачи 16, 128, 57, 10, 432 сообщений в восьмеричном и двоичном кодах?

7.Чему равна средняя длина кодового слова сообщений, составленных из алфа­

вита Л, В, С, D, если РА = 0,1; Рв = 0,2; Рс = 0,3; PD = 0,4?

8. Требуется передать 10 арабских "Цифр в двоичном коде; 5, 17, 31, 32, 33, 127, 128, 129, 1135, 4500. Представить эти цифры в двоичном коде. Для каких цифр вели-

logN

чина | 0~ — будет точнее выражать длину кодового слова?

9. Найти верхнюю и нижнюю границы минимальной средней длины кодовых блоков, если они составлены из восьмибуквенных слов по 2, 3, 4, 5, 8, 31, 32, 33 слова в блоке. Доказать, что верхняя и нижняя границы сближаются с удлинением блока.

Основная теорема кодирования для каналов связи без шумов доказы­ вает лишь принципиальную возможность построения оптимальных

1 Для подсчета энтропии см. табл. 2.

2 См. задачу 4, тема 6.

72

кодов. Однако из нее однозначно вытекает и методика построения, и свойства оптимальных кодов.

Одним из основных положений этой теоремы является то, что при кодировании сообщения, разбитого на /V-буквенные блоки, можно, выбрав N достаточно большим, добиться того, чтобы среднее число двоичных элементарных сигналов, приходящихся на одну букву ис­

мума при равновероятных и взаимонезависимых символах, отсюда вытекают основные свойства оптимальных кодов:

минимальная средняя длина кодового слова оптимального кода обеспечивается в том случае, когда избыточность каждого кодового слова сведена к минимуму (в идеальном случае — к нулю);

кодовые слова (алфавит) оптимального кода должны строиться из равновероятных и взаимонезависимых символов.

Из свойств оптимальных кодов вытекает первый принцип опти­ мального кодирования: выбор каждого кодового слова (независимо от того, означает оно букву или цифру) необходимо производить так, чтобы содержащееся в нем количество информации было' максималь­ ным, т. е. чтобы при любых значениях предыдущих кодовых слов выби­ раемое кодовое слово с одинаковой вероятностью принимало значение О или 1 («Да» или «Нет»). Второй принцип оптимального кодирования заключается в том, что кодовым словам, имеющим большую вероят­ ность, присваиваются более короткие кодовые обозначения.

Принципы оптимального кодирования определяют методику по­ строения оптимальных кодов. Построение оптимального кода ансамбля из М сообщений сводится к следующей процедуре:

1) множество из М сообщений располагают в порядке убывания вероятностей;

2) первоначальный ансамбль кодируемых сигналов разбивают на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны;

3) первой группе присваивают символ 0, второй группе — сим­ вол 1;

4) каждую из групп делят на две подгруппы так, чтобы их сум­ марные вероятности были по возможности равны;

5) первым подгруппам каждой из групп вновь присваивают О, а вторым — 1, в результате чего получают вторые цифры кода. Затем каждую из четырех подгрупп вновь делят на равные (с точки зрения суммарной вероятности) части и т. д. до тех пор, пока в каждой из подгрупп останется по одной букве.

Рассмотрим несколько конкретных примеров построения оптималь­ ных кодов.

73