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

Первое требование очевидно, так как при одинаковых кодовых обозначениях различных букв алфавитов нельзя будет их однозначно декодировать.

Второе требование может быть удовлетворено следующим образом: введением в код дополнительного разделительного символа — паузы, что значительно удлиняет коды, а следовательно, и время передачи сообщения; созданием кода, в котором конец одной буквы не может быть началом другой; либо кода, в котором все буквы передаются ком­ бинациями равной длины, т. е. равномерного кода. При этом следует отметить, что равномерные коды обладают известными преимущества­ ми: длину каждой буквы можно определить простым подсчетом элемен­ тарных символов, что позволяет автоматизировать процесс декодиро­ вания и строить простые декодирующие устройства (например, рис. 19,6). Однако равномерные коды имеют один существенный недостаток: все кодовые слова алфавитов, представленных ими, имеют равную дли­ ну независимо от вероятности появления отдельных символов кодиру­ емого алфавита. Такой код может быть оптимальным только для слу­ чая равновероятных и взаимонезависимых символов сообщений, что довольно часто встречается в телемеханике и никогда — при передаче текстовых. сообщений.

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

Пусть требуется передать N сообщений при помощи алфавита, который состоит из конечного числа символов т. Обозначим: р{ — вероятность появления г'-го сигнала; pin — условная вероятность по­ явления i-ro сигнала относительно ;'-го; L — средняя длина кодового слова для N сообщений, которая может быть определена как некото­ рое среднее количество элементарных символов для передачи среднего количества информации на кодовое слово данного алфавита и равна отношению количества информации на символ сообщения к максималь­ ному количеству информации на символ данного алфавита. Исполь­

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

L" > U .

Выражение (41) представляет собой предельный случай возможно­ го сокращения количества символов на образование кодового слова.

Выражение (42) позволяет определять минимальное количество сим­ волов на одно сообщение, переданное равномерным кодом, в котором символы алфавита взаимонезависимы. Из этих выражений видно, что длина некоторого среднего кодового слова может быть сокращена за счет увеличения количества качественных признаков т. Например, если каждой букве русского алфавита в виде качественного признака выделить отдельную частоту, то длина любого кодового слова будет равна единице. Однако при этом потребовался бы сравнительно слож­ ный шифратор на 32 команды, необходимо было бы занять в эфире ши­ рокую полосу частот, поставить в приемном устройстве 32 фильтра и т. д. В общем случае увеличение количества качественных признаков часто ведет к усложнению приемно-передающей аппаратуры и не всег­ да себя оправдывает.

Длину среднего кодового слова можно также сократить, исполь­ зовав информационный резерв кода за счет уменьшения избыточности. В этом смысле предельно короткими являются так называемые опти­ мальные кодых — коды с нулевой (или близкой к нулю) избыточностью. Классическим примером кода с нулевой избыточностью может быть, код Шеннона — Фано 1.2 Но прежде чем приступить к рассмотрению прин­ ципов оптимального кодирования на примерах конкретных кодов, вспомним популярную задачу об отгадывании чисел [49], поскольку принцип решения этой задачи подобен принципу построения оптималь­ ного кода Шеннона — Фано. Кроме того, выводы, которые будут полу­ чены в результате рассмотрения этого элементарного примера, послужат основой для нахождения соотношений, которые приведут нас к основ­ ной теореме кодирования.

Итак, сколько вопросов необходимо задать собеседнику, чтобы отгадать задуманное число N, если ответом будет только «Да» и «Нет»? Пусть задуманное число N < 10. Для решения этой задачи используем уже известные нам положения теории информации. Процесс угадыва­ ния путем постановки k вопросов будем рассматривать как некоторый сложный опыт

A - k — а 1> а 2> • • • > a k>

где « г — ответ на первый вопрос; а 2 — ответ на второй вопрос; а к — ответ на последний вопрос.

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

66

Если угадываемое число лежит в пределах 10, то максимальная информация опыта 4*

l Ak = 1 log 10.

Из вышесказанного можно заключить, что

log 10 = IAk< Hak < k log 2 = log 2k,

откуда

2 * > Ю ; й > lo g , 10 = ^ « 3 , 3 2 .

Так как число опытов не может быть дробью, то k — 4. Этот факт легко проверить. Необходимо только ставить вопросы так, чтобы информация в ответе была максимальной. А когда это возможно? Это возможно в том случае, если при каждом опыте иметь дело с рав­ новероятными событиями, т. е. если на вопрос с равной вероятностью может последовать ответ «Да» или «Нет» и энтропия одного опыта дей­ ствительно равняется log 2.

Таким образом, первый вопрос должен звучать так: «Задуманное число больше 5?» Если ответ был «Нет», то следует задать вопрос: «Задуманное число больше 3?» и т. д. Если каждый раз разбивать ос­ тавшееся число на возможно более равные части, то любое число из 10 будет определено максимум за четыре вопроса.

Так как разность k — -°ор ■всегда меньше единицы (округление все­ гда происходит до ближайшего целого числа), то

Н4)

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

а число 100—1100010. Как видим, число элементарных символов равно logN

мерой длины кодового слова. Для случая, когда N является целой сте­ пенью числа 2, k — целое число и представляет собой минимальную длину кодового слова L для представления числа N в двоичном ал­ фавите.

минимальную длину кодового слова для представления данного ансамб­ ля N сообщений в двоичном коде.

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

Для /л-значного алфавита длина кодового слова

lo g N

1 > lo g т

Подводя итоги, можно сказать, что средняя минимальная длина кодового слова L ансамбля ./V сообщений, составленного из алфавита т, не может быть меньше, чем частное от деления среднего количества ин­ формации данного ансамбля сообщений на максимальное количество информации на символ, т. е.

где в общем случае

N

Я'll Pi log Pi, t=i

ав случае равновероятных символов

Я = log N.

С другой стороны,

ТН

lo g m < 1 ,

68

или

Выражения (46) и (47) представляют собой соответственно верх­ нюю и нижнюю границы минимально необходимой средней длины ко­ дового слова. Используя эти выражения, получаем

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

lo g m

Предположим, передаются символы некоторого равномерного кода с числом признаков т = 2, причем появление каждой из букв кода не зависит от появления любой другой буквы этого кода. Для пере­ дачи восьми букв алфавита минимальная длина кодового слова

т. е. минимальная длина не может быть передана меньше, чем тремя

справедливо для кодов с равновероятными и взаимонезависимыми сим­ волами, в противном случае энтропия выражалась бы одной из формул (24) — (27) в соответствии с характером взаимозависимости между сим­ волами сообщения.

Для т = 2 выражение (50) справедливо тогда, когда вероятности появления 0 и 1 одинаковы. Но в действительности это будет только в случае, если N — целая степень числа 2. Например, для N — 4 чис­ ло нулей равно числу единиц и равно 4 (код двузначный). Для N = 8 число нулей равно числу единиц и равно 12 (код трехзначный) и т. д. Однако для N = 5 соотношение нулей и единиц — 10 к 5 (табл'. 10),

69