2.3. Методы устранения избыточности сообщения

Если источник сообщения не имеет избыточности, то его производительность  и, как было показано в § 2.2, с помощью простой процедуры сообщение может быть закодировано для передачи по каналу без помех с пропускной способностью . В случае источника с избыточностью . Поэтому часто возникает задача о передаче его сообщения по каналу с пропускной способностью , что в принципе возможно, если только . Соответствующее кодирование должно преобразовать последовательность элементов сообщения с избыточностью в последовательность кодовых символов, не имеющую ее либо имеющую значительно меньшую избыточность. Поэтому такую операцию кодирования можно назвать устранением избыточности.

Рассмотрим сначала случай, когда источник выбирает элементарные сообщения с неодинаковыми вероятностями и независимо друг от друга. В этом случае вся избыточность источника является результатом неравных вероятностей элементов. Эта избыточность может быть устранена полностью или частично, если при кодировании представлять наиболее вероятные элементы короткими последовательностями кодовых символов, а менее вероятные — более длинными. Отсюда видно, что такой экономичный код должен быть неравномерным.

Если элемент сообщения  представлен последовательностью кодовых символов, состоящей из  символов, то среднее число символов  в кодовой последовательности, приходящееся на один элемент, равно

                                                             (2.15)

Максимальная энтропия  кодовой последовательности, приходящаяся на один символ, равна , где  — число различных кодовых символов. Следовательно, энтропия кодовой последовательности, приходящаяся в среднем на одну комбинацию (соответствующую элементу сообщения):

                 (2.16)

Основное требование, предъявляемое к любому коду, заключается в возможности однозначного декодирования кодовой последовательности, что приводит к условию , откуда

            (2.17)

Полученное выражение даст оценку снизу для средней длины кодовой комбинации. Задача экономичного кодирования заключается в том, чтобы выбрать код, позволяющий по возможности приблизить  к этой оценке. Если в выражении (2.17) будет достигнуто равенство, то это значит, что  и полученные кодовые последовательности не будут иметь избыточности. В противном случае сохранится остаточная избыточность, равная

                          (2.18)

Однако эта избыточность всегда может быть сделана значительно меньшей, чем избыточность сообщения

Действительно, применяя примитивное кодирование (§ 2.2) равномерным а-разрядным кодом, можно получить , сколь угодно близкое к , что при подстановке в (2.18) даст . Но, применяя неравномерный код, можно всегда сократить среднюю длину кодовой комбинации , используя более короткие комбинации для более вероятных знаков (если только буквы сообщения не равновероятны), в результате чего получить , т. е. устранить по крайней мере часть избыточности. Заметим, что, используя укрупнение алфавита, можно сделать остаточную избыточность сколь угодно малой.

При построении оптимального неравномерного кода, позволяющего предельно сократить избыточность, необходимо учитывать требование однозначного декодирования. Легко видеть, что это требование будет выполнено, если ни одна комбинация данного кода не совпадает с началом другой более длинной комбинации. Такое свойство кода называется «неприводимостью». При декодировании последовательности кодовых символов свойство неприводимости позволяет однозначно разделить эту последовательность на кодовые комбинации и сопоставить с каждой кодовой комбинацией соответствующий элемент сообщения, т. е. произвести декодирование.

Так, например, код с основанием , содержащий кодовые комбинации 00, 01, 100, 101, 110 и 111, является неприводимым, тогда как код, содержащий комбинации 00, 01, 10, 11, 000, 001, 010, не является неприводимым, поскольку комбинация 01 совпадает с началом комбинации 010, а комбинация 00 — с началом комбинаций 000 и 001. Первый из этих кодов позволяет произвести однозначное декодирование. Если принята, например, кодовая последовательность

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] (алгоритмы) построения неприводимых неравномерных кодов с основанием , позволяющих для заданного источника в наибольшей возможной степени устранить избыточность сообщения. Опишем наиболее универсальный способ, предложенный Хафменом [4, 38]

Все буквы алфавита сообщения в количестве  выписываются в порядке убывающей вероятности. Если число  не кратно , то в алфавит добавляются дополнительные «буквы», которым приписываются вероятности, равные нулю, так чтобы для объема полученного алфавита  соблюдалось условие кратности  числу . Затем последние  элементов полученного алфавита объединяются в «укрупненный» элемент, вычисляется его вероятность, которая записывается в соответствующее место алфавита. То же самое проделывается с последними  элементами полученного алфавита (включая укрупненные), и это продолжается до тех пор, пока не останется «алфавит», состоящий из  элементов. Этим элементам приписываются в любом порядке одноразрядные кодовые комбинации  Если в числе оставшихся  элементов есть такие, которые принадлежат исходному алфавиту (т. е. не полученные в результате объединения других элементов), то они оказываются закодированными одноразрядными кодовыми комбинациями. Для тех элементов, которые получены в результате объединения т букв исходного алфавита в кодовые комбинации, дописываются вторые символы , так что эти знаки оказываются закодированными двухразрядными комбинациями. Если среди этих двухразрядных комбинаций имеются такие, которые соответствуют элементам, полученным также в результате объединения, то к этим комбинациям приписываются третьи символы и т. д., пока все элементы исходного алфавита не окажутся закодированными.

В качестве примера построим неравномерный код с основанием , используя кодовые символы 0, 1, 2 и 3 для источника с алфавитом, состоящим из 16 элементов (которые обозначим русскими буквами) со следующими априорными вероятностями:

А	0,3	Д	0,04	И	0,015	Н	0,01
В	0,2	E	0,03	К	0,01	О	0,01
В	0,2	Ж	0,03	Л	0,01	П	0,01
Г	0,1	З	0,02	М	0,01	Р	0,005

Энтропия этого источника равна

  двоичной единицы

на знак, а его избыточность

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

Объединим четыре последние буквы. Полученный объединенный элемент имеет вероятность 0,035 и должен быть вписан в алфавит в промежутке между  и . Проделаем то же с последними четырьмя из оставшихся букв и впишем полученный объединенный элемент, имеющий суммарную вероятность 0,045, в соответствующее место алфавита, между и . Продолжаем поступать таким же образом, пока не останутся 4 буквы (А, Б, В и один объединенный элемент), которым приписываем кодовые символы 0, 1, 2 и 3. Затем составляем комбинации для букв, вошедших в объединения. Весь процесс построения кода ясен из табл. 2.1.

Окончательно получим следующую кодовую таблицу:

А—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 га». Обнаружить и исправить ошибку по контексту здесь уже не представляется возможным.

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