2.3. Методы устранения избыточности сообщенияЕсли источник сообщения не имеет избыточности, то его производительность Рассмотрим сначала случай, когда источник выбирает элементарные сообщения с неодинаковыми вероятностями и независимо друг от друга. В этом случае вся избыточность источника является результатом неравных вероятностей элементов. Эта избыточность может быть устранена полностью или частично, если при кодировании представлять наиболее вероятные элементы короткими последовательностями кодовых символов, а менее вероятные — более длинными. Отсюда видно, что такой экономичный код должен быть неравномерным. Если элемент сообщения
Максимальная энтропия
Основное требование, предъявляемое к любому коду, заключается в возможности однозначного декодирования кодовой последовательности, что приводит к условию
Полученное выражение даст оценку снизу для средней длины кодовой комбинации. Задача экономичного кодирования заключается в том, чтобы выбрать код, позволяющий по возможности приблизить
Однако эта избыточность всегда может быть сделана значительно меньшей, чем избыточность сообщения Действительно, применяя примитивное кодирование (§ 2.2) равномерным а-разрядным кодом, можно получить При построении оптимального неравномерного кода, позволяющего предельно сократить избыточность, необходимо учитывать требование однозначного декодирования. Легко видеть, что это требование будет выполнено, если ни одна комбинация данного кода не совпадает с началом другой более длинной комбинации. Такое свойство кода называется «неприводимостью». При декодировании последовательности кодовых символов свойство неприводимости позволяет однозначно разделить эту последовательность на кодовые комбинации и сопоставить с каждой кодовой комбинацией соответствующий элемент сообщения, т. е. произвести декодирование. Так, например, код с основанием 000110101011010100100110010001101.., то ее можно разделить на кодовые комбинации только следующим образом: 00 01 101 01 01 101 01 00 100 110 01 00 01 101... Если бы использовался второй код, не обладающий свойством неприводимости, то разделение той же последовательности на кодовые комбинации можно было бы произвести различными способами, например: 00 01 10 10 10 И 01 01 00 10 01 10 01 00 01 10... или 000 11 010 10 11 010 10 010 01 10 010 001 10..., или 000 11 01 010 11 01 01 001 001 10 01 000 11 01... и т. д. Известны различные способы [1, 3, 4] (алгоритмы) построения неприводимых неравномерных кодов с основанием Все буквы алфавита сообщения в количестве В качестве примера построим неравномерный код с основанием
Энтропия этого источника равна
на знак, а его избыточность В данном случае Объединим четыре последние буквы. Полученный объединенный элемент имеет вероятность 0,035 и должен быть вписан в алфавит в промежутке между Окончательно получим следующую кодовую таблицу: А—0 Д—13 И—120 H—1000 Б—2 Е—101 К—121 С—1001 В—3 Ж—102 Л—122 Я—1002 Г —11 3—103 М—123 Р—1003 Полученный код, как легко видеть, является неприводимым и наиболее короткие кодовые комбинации в нем соответствуют наиболее вероятным знакам. Среднее количество символов на букву равно Избыточность полученного кода согласно (2.18) равна Таблица 2.1. т. е. почти в 10 раз меньше избыточности источника сообщения. Можно показать [4], что полученный с помощью такого алгоритма код является оптимальным в том смысле, что при данном источнике и данном основании кода Заметим, что поскольку избыточность такого неравномерного кода очень мала, то в любой типичной кодовой последовательности все символы должны встречаться почти одинаково часто и вероятностные связи между символами должны быть очень слабы (т. е. условная вероятность появления некоторого символа при известных предшествовавших символах мало отличается от полной вероятности появления этого символа). Перейдем к более общему случаю, когда источник сообщения является марковским и его избыточность определяется не только неравномерным распределением вероятностей букв, но и зависимостью этих вероятностей от того, какие буквы предшествовали данной. Рассмотрим два возможных метода устранения избыточности при кодировании сообщений такого источника. Первый метод состоит в том, что для каждого состояния Такой метод кодирования полностью устраняет избыточность, вызванную вероятностными связями между элементами сообщения, или, как говорят, осуществляет полную декорреляцию. В то же время благодаря применению в каждом состоянии оптимального неравномерного кода полностью или почти полностью устраняется избыточность, вызванная неравномерным распределением вероятностей элементов. Применение этого метода на практике в общем случае затруднено необходимостью использования автоматически перестраивающихся устройств кодирования и декодирования либо комплекта таких устройств на все состояния источника. Однако часто встречаются источники с такими вероятностными связями между элементами, при которых списанный метод декорреляции сводится к экстраполяции последовательности элементов, т. е. предсказанию ожидаемого элемента на основе знания предшествовавших. При этом кодируется «разность» между предсказанным элементом и действительно выбранным. При надлежащем определении понятия «разность» для данного источника эти разности имеют значительно менее сильные вероятностные связи, чем исходные элементы сообщения. Покажем это на простом примере. Пусть система связи служит для передачи сообщения о силе тока, отдаваемого генератором дистанционно управляемой электростанции. Для тою чтобы эти сообщения были дискретными, они должны соответствовать силе тока в определенные моменты времени (например, через 0,1 сек), причем измерения должны производиться с определенной точностью (скажем, с округлением до По существу здесь имеется марковский источник, состояние которого определяется в первом приближении только последним сообщением (силой тока в данный момент) и для каждого состояния задано свое частное распределение вероятностей других элементов сообщения (других значений силы тока). При этом все частные распределения вероятностей отличаются друг от друга только положением наиболее вероятного значения Рис. 2.4. Пример распределения условных вероятностей сообщений марковского источника. (равного значению в последний момент отсчета) и могут быть получены путем перемещения графика вероятностей вдоль оси тока, как видно из рис. 2.4, где показаны распределения условных вероятностей Применим оптимальный неравномерный код для этих разностей. При этом, очевидно, самые короткие кодовые комбинации будут означать, что сила тока не изменилась или изменилась на +1 или -1, а более длинные комбинации будут соответствовать более значительным изменениям силы тока. Легко видеть, что такой метод декорреляции путем передачи разности значений силы тока является одним из вариантов метода частных кодов для каждого состояния источника. Действительно, каждая кодовая комбинация несет фактически сообщение о силе тока в данный момент, но для того чтобы ее декодировать, необходимо знать состояние источника, т. е. (в данном примере) значения силы тока в предыдущем отсчете. Частные коды в этом примере отличаются друг от друга только «начальной точкой отсчета». Отметим, что такой метод устранения избыточности в телеметрических системах имеет практическое значение, так как он позволяет сократить потребную пропускную способность канала и более эффективно использовать имеющуюся многоканальную линию связи для передачи результатов измерения ряда физических величин. Другой метод декорреляции заключается в использовании уже знакомой нам операции укрупнения алфавита. При этом образуется новый алфавит источника, и если число букв исходного алфавита, вошедших в одну «букву» укрупненного алфавита, значительно превышает интервал действия вероятностных связей, то можно связью между элементами укрупненного алфавита пренебречь. Как было показано в гл. 1 [см. (1.14)], общая избыточность при укрупнении алфавита не изменяется. Следовательно, уменьшение избыточности, вызываемой взаимными связями, должно сопровождаться соответствующим возрастанием избыточности, обусловленной неравными вероятностями появления различных элементов. Действительно, укрупненный алфавит источника сообщений всегда характеризуется более неравномерным распределением вероятностей элементов, нежели исходный алфавит. Применив оптимальный неравномерный код для кодирования укрупненного алфавита, можно практически полностью устранить избыточность, содержащуюся в сообщении. Таким образом, процесс устранения избыточности марковского источника сообщений сводится к двум операциям: декорреляции (методом применения частных кодов или методом укрупнения) и кодированию оптимальным неравномерным кодом [5]. Во многих странах применяются специальные коды для служебной телеграфной переписки различных министерств и ведомств. В этих кодах короткие комбинации используются для передачи часто встречающихся фраз и выражений [6] (типичных последовательностей для данного источника сообщений), в то время как редко встречающиеся фразы передаются обычным образом. Это является примером устранения избыточности путем укрупнения алфавита (до целых фраз или частей фраз) и эффективного кодирования. При этом обеспечивается значительная экономия телеграфных расходов. Описанные методы устранения избыточности позволяют эффективно использовать пропускную способность канала связи без шумов. Они полезны также в тех случаях, когда требуется хранить большой объем информации в различных запоминающих устройствах. Отметим, что экономия в пропускной способности канала или в объеме запоминающего устройства в конечном счете приводит к реальной денежной экономии, к уменьшению размеров и веса аппаратуры и т. д. Однако устранение избыточности имеет и существенную отрицательную сторону. Последовательности кодовых символов оптимального неравномерного кода, лишенные или почти лишенные избыточности, оказываются весьма «хрупкими» при действии шумов в реальных каналах или в реальных запоминающих устройствах. Эта хрупкость заключается в том, что достаточно исказить один из символов последовательности, чтобы сделать невозможным правильное декодирование не только той буквы, в которую входит этот символ, но и ряда последующих букв. Поясним сказанное примером. Предположим, что по каналу связи передается телеграмма следующего содержания: «Уборка пшеницы закончена собрано 8000 центнеров». Если эта телеграмма закодирована примитивным равномерным кодом, без устранения избыточности, то ошибочный прием одного или даже нескольких отдельных кодовых символов приведет только к ошибочному декодированию одной или нескольких букв. Пусть эта телеграмма получена в следующем виде: «Уборкр пшеницы законвена собрано 8000 цептнеков». Очевидно, что получатель такой телеграммы легко ее прочитает и восстановит смысл по контексту, несмотря на четыре ошибки. Это обусловлено наличием избыточности алфавита русского языка. Поскольку энтропия, приходящаяся на букву, значительно меньше максимальной энтропии, подавляющее число случайных последовательностей букв образует нетипичные (бессмысленные) сочетания. К их числу относится и то, которое принято вместо переданной телеграммы. Именно поэтому можно без труда определить типичную (осмысленную) последовательность, которая, вероятнее всего, и была передана но каналу связи. Заметим, кстати, что если бы ошибочно было принято число «6000» вместо «8000», то такую ошибку исправить по контексту было бы невозможно. Это вызвано тем, что при изображении чисел Цифрами избыточность резко уменьшается, так как всякая последовательность цифр имеет осмысленное значение. Для повышения верности приема можно было бы числа записывать буквами («восемь тысяч»). Предположим, что та же телеграмма закодирована специальным ведомственным кодом, о котором говорилось выше, так, что избыточность сокращена до минимума. Такая телеграмма, закодированная с помощью буквенного алфавита, может иметь, например, такой вид: «КТШУА 8000», что позволяет ее передать по каналу телеграфной связи значительно быстрее и дешевле, чем при примитивном кодировании. Предположим, что одна буква при передаче исказилась и полученная кодовая последовательность имеет, скажем, следующий вид: «КТМУА 8000». Если код достаточно эффективно устраняет избыточность, то он обладает свойством полноты, т. е. любая последовательность символов является типичной, или, другими словами, имеет осмысленное содержание. В данном случае полученная телеграмма может, например, означать: «В результате стихийных бедствий погиб урожай на площади 8000 га». Обнаружить и исправить ошибку по контексту здесь уже не представляется возможным. Ввиду этого всякое устранение избыточности связано с риском потери верности при передаче сообщений в канале с шумами. Вопрос об использовании избыточности кодовой последовательности для повышения верности принятого сообщения будет рассмотрен ниже.
|