1.1. Источники, энтропия и теорема кодирования без шума

Сообщение: «Сегодня в Лос-Анджелесе солнечная погода, количество смога ограничено» хотя и не является для нас неожиданным, все содержит некоторую информацию, поскольку разрешает неопределенность относительно погоды в Лос-Анджелесе. С другой стороны) новость — «Сегодня в Калифорнии произошло опустошительное землетрясение, разрушившее большую часть делового центра Лос-Анджелеса» - гораздо неожиданнее и содержит больше информации, чем первое сообщение. Но что же такое информация? Что мы понимаем под «информацией», содержащейся в приведенных сообщениях? Если мы намерены ввести формально некую количественную меру информации, содержащейся в подобных сообщениях, то конечно, эта мера должна обладать рядом очевидных свойств.

1. Информацию о событиях следует определять через некоторую меру неопределенности событий.

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

3. Информация о не связанных между собой событиях, рассматриваемых как одно событие, должна равняться сумме информации о каждом из этих событий.

Естественной мерой неопределенности события а может служить его вероятность, обозначаемая через Формальным аналогом понятия «несвязанности» служит независимость; два события а и называются независимыми, если

Коль скоро мы согласились определять информацию о событии а через его вероятность, информацию о событии а, удовлетворяющую свойствам 1 и 2, можно определить следующим образом:

Из этого определения вытекает, что если независимы, то Основание логарифма задает масштаб и, следовательно, единицу количества информации. Введенное выше количество информации естественным образом вытекает из установленных интуитивно свойств, но хорошо ли такое определение? И хотя у нас нет оснований ожидать, что такое простое определение окажется полезным количественным описанием для большинства случаев сложного обмена информацией, мы покажем, что это определение представляет собой центральное понятие цифровой связи.

Главный предмет нашего изучения — передача и обработка информации, причем источники информации и каналы связи задаются вероятностными моделями. Например, источники информации описываются вероятностной моделью, выходом которой служат события или случайные величины. Начнем с простейшего вида источника информации.

Определение. Дискретный источник без памяти характеризуется своим выходом — случайной величиной и, принимающей значения в конечном алфавите с вероятностями

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

Если в некоторый момент времени на выходе ДИБП появится символ (это событие обозначим через то в соответствии с нашим определением информации выходной символа источника содержит

единиц информации. Эти единицы называют натами, если логарифмы натуральные, и битами, если основание логарифмов равно 2. Ясно, что они отличаются всего лишь масштабным множителем Далее мы будем пользоваться обозначением для

логарифма по основанию 2, тогда как означает натуральный логарифм. Среднее количество информации на символ на выходе источника задается тогда выражением

называют энтропией ДИБП. Здесь принято считать, что

Чтобы выяснить смысл энтропии как оперативной характеристики, воспользуемся фундаментальным неравенством

проверить которое можно, учитывая, что функция имеет единственный максимум, равный 0 в точке На рис. 1.2 приведены графики функций Из неравенства (1.1.6) следует, что для любых двух вероятностных распределений на алфавите справедливо неравенство

откуда следует неравенство

которое переходит в равенство тогда и только тогда, когда для всех

Неравенства (1.1.6) и (1.1.8) входят в ряд наиболее часто употребляемых в теории информации. Например, подставив для всех не в (1.1.8), видим, что источник с равновероятными символами обладает наибольшей энтропией. Иначе говоря,

с равенством справа тогда и только тогда, когда для всех

Пример. (Двоичный источник без памяти.) Энтропия ДИБП с алфавитом и вероятностями равна

где функцию называют двоичной энтропией. Здесь переходит в равенство тогда и только тогда, когда В последнем случае мы называем источник двоичным симметричным источником (ДСИ). Каждый символ на выходе ДСИ содержит один бит информации.

Пусть теперь случайная последовательность длины N на выходе ДИБП. Случайные величины независимы и равнораспределены, следовательно, распределение вероятностей и задается соотношением

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

Рис. 1.2. Графики функций

Как и следовало ожидать, для источника без памяти получим

Это показывает, что полная средняя информация в последовательности независимых выходных символов равна сумме средних информаций в каждом выходном символе.

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

где одномерная вероятность выходного символа если только случайные величины не являются независимыми. Тогда из (1.1.8) следует, что

где последнее равенство получается аналогично (1.1.12). Отсюда

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

В целом ряде приложений информация с выхода источника либо передается некоторому получателю, либо хранится в памяти ЭВМ. В любом случае удобно представить выходные символы двоичными символами. При этом необходимо, чтобы по двоичным символам можно было восстановить первоначальные выходные символы источника. Естественно, что на каждый выходной символ хотелось бы употребить как можно меньше двоичных символов. В первой теореме Шеннона, называемой теоремой кодирования без шума для источника, показано, что среднее число двоичных символов, приходящееся на выходной символ источника, можно приблизить к энтропии источника и что нельзя сделать его меньше энтропии. Этот довольно неожиданный результат выявляет значение энтропии источника как оперативной характеристики. Докажем теперь теорему для случая с ДИБП.

Пусть случайная последовательность длины N на выходе ДИБП, а соответствующая двоичная последовательность длины представляющая последовательность и источника. При фиксированном множество всех двоичных последовательностей (кодовых слов),

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

Пример. Пусть Рассмотрим следующие коды для последовательностей длины

Код 1 не является однозначно декодируемым, поскольку двоичная последовательность может соответствовать последовательностям источника однозначно декодируем, поскольку все кодовые слова имеют одинаковую длину и различны. Код 3 также однозначно декодируем, поскольку 1 всегда указывает на начало кодового слова и все кодовые слова различны. Для рассмотрим код

Такой код для последовательностей источника длины 2 из будет однозначно декодируемым, поскольку все его последовательности встречаются только по одному разу и первый их символ указывает на длину кодового слова. Если на первом месте стоит 0, то кодовое слово имеет длину 3, а если 1, то длина кодового слова равна 4. Больше того, этот код обладает тем свойством, что ни одно кодовое слово не является префиксом другого. Иначе говоря, все кодовые слова различны и ни одно кодовое слово длины 3 не встречается в качестве первых трех символов ни в одном кодовом слове длины 4.

Перейдем теперь к формулировке и доказательству теоремы кодирования без шума для источника в ее простейшей форме. Эта

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

Теорема 1.1.1. Теорема кодирования без шума для дискретного источника без памяти. Пусть задан ДИБП с алфавитом и энтропией Для последовательностей источника длины существует однозначно декодируемый двоичный код, состоящий из двоичных последовательностей (кодовых слов) длины при такой, что средняя длина кодового слова ограничена неравенством

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

Прямая теорема — справедливость соотношения (1.1.15) — доказывается построением однозначно декодируемого кода, на котором достигается оценка средней длины. Существует несколько методов такого построения, из которых первый принадлежит Шеннону [1948] (см. задачу 1.6); Хаффману [1952] принадлежит оптимальный метод, тот, при котором получающийся код имеет минимальную среднюю длину при всяком Приведем еще один метод, который, хотя и менее эффективен, чем указанные стандартные методы, позволяет не только доказывать теорему непосредственно, но и иллюстрировать одно интересное свойство ДИБП, присущее гораздо более широкому классу источников и называемое свойством асимптотической равнораспределенности. Его мы установим с помощью следующей леммы.

Лемма 1.1.1. Для любого рассмотрим ДИБП с алфавитом энтропией и введем следующее подмножество множества всех последовательностей источника длины N

Тогда все последовательности источника из можно однозначно представить двоичными кодовыми словами фиксированной длины удовлетворяющей неравенствам

Более того,

где

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

Доказательство. представляет собой подмножество -множества всех последовательностей длины следовательно, справедливо неравенство

Поскольку по определению для любого это неравенство можно записать в следующем виде:

где через обозначено число различных последовательностей в Следовательно, справедлива граница

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

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

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

Из определения (1.1.16) для имеем

Следовательно, дополнение можно представить как

Случайные величины

независимы и равнораспределены со средним

и конечной дисперсией, которую обозначим через

Для суммы N таких случайных величин из хорошо известного не равенства Чебышева (см. задачу 1.4) вытекает, что

Следовательно, для имеем

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

Доказательство теоремы 1.1.1. Воспользуемся результатом леммы 1.1.1 и добавим по одному двоичному символу к двоичным представлениям последовательностей из а именно, допишем 0 перед каждым таким представлением. Это увеличит длину двоичной последовательности с до чем асимптотически можно пренебречь. Из (1.1.17) видно, что все последовательности из однозначно представлены двоичными последовательностями длины бит. Все другие последовательности, входящие в мы можем представить последовательностями длины первый двоичный символ которых всегда равен 1, а оставшиеся символов однозначно представят

все последовательности из Это заведомо возможно при удовлетворяющем неравенствам:

или

поскольку при выполнении последнего неравенства все последовательности из однозначно представимы.

Теперь для каждой из выходных последовательностей длины N есть однозначное двоичное представление или кодовое слово. Это код того же типа, что и код 4 в приведенном примере. Он однозначно декодируем, поскольку первый символ указывает длину кодового слова (0 означает, что длина равна а 1, что тогда как остальные символы однозначно задают последовательность источника длины Когда первый символ равен мы, рассматривая следующие символов, однозначно восстанавливаем последовательность из если же первый символ равен 1, мы по следующим символам однозначно восстанавливаем последовательность источника из Каждое кодовое слово представляет собой однозначно определяемую двоичную последовательность, и никогда не возникает неопределенности по поводу того, где начинается или кончается последовательность кодовых слов. Ни одно кодовое слово не является префиксом другого. Только что описанный кодер приведен на рис. 1.3.

Рис. 1.3. Кодер источника

Мы построили, таким образом, однозначно декодируемый код с двумя возможными длинами кодовых слов: и Поэтому средняя длина кодового слова равна

а из (1.1.17), (1.1.18) и (1.1.30) следует, что

или

Выбрав получим

что и устанавливает прямую теорему.

Прежде чем перейти к обратной теореме, заметим, что благодаря свойству асимптотической равнораспределенности при больших N почти все кодовые слова можно выбрать равной длины, чуть большей причем понадобится всего две длины. При малых N предпочтителен больший набор длин кодовых слов. В действительности при малых N желательно (и почти оптимально) выбирать длины кодовых слов пропорциональными логарифмам вероятностей соответствующих последовательностей источника подобно тому, как при больших N мы выбрали длину примерно равной взятому со знаком минус логарифму (по основанию 2) от почти одинаковых вероятностей выходных последовательностей подмножества Вероятности конкретных последовательностей источника не являются, вообще говоря, близкими друг к другу, поэтому, чтобы достичь малой средней длины, нам потребуется много значений длин кодовых слов. Существует несколько методов их выбора, приводящих к однозначно декодируемым кодам (Шеннон [1948], Хаффман [1952]), и они достаточно подробно описаны в ряде руководств. В книге эти методы нигде не используются и поэтому не включены в материал настоящей вводной главы, имеющей дело с фундаментальными параметрами (см., однако, задачу 1.6).

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

Рассмотрим тождество

где каждая сумма в обеих частях соотношения распространяется на все пространство Обозначив через число

последовательностей из последовательных кодовых слов, имеющих полную длину двоичных символов, можно представить (1.1.34) в

где Из условия однозначной восстановимости последовательности источника по двоичной последовательности имеем

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

Но для всех указанных это неравенство может удовлетворяться тогда и только тогда, когда

поскольку левая часть (1.1.37) экспоненциально зависит от тогда как правая растет лишь линейно с Приведенное неравенство известно как неравенство Крафта-Макмиллана (Крафт [1949], Макмиллан [1956]).

В общем случае для кодера источника с переменной длиной и кодовыми длинами, удовлетворяющими соотношению (1.1.38), средняя длина равна

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

из неравенств (1.1.8) и (1.1.12) получим

Поскольку по неравенству Крафта-Макмиллана (1.1.38) второе слагаемое неположительно, имеем

Эта оценка справедлива для последовательностей любой длины следовательно, для любого кода источника, для которого последовательности источника однозначно восстановимы по двоичным последовательностям (однозначно декодируемы), в среднем необходимо не меньше бит на символ источника. Теорема 1.1.1 доказана

Мы показали, таким образом, что ДИБП можно закодировать при среднем числе двоичных символов на символ источника, сколь угодно близком к энтропии, и что невозможно добиться меньшей средней длины. Это частный случай теоремы кодирования без шума для источника, которая справедлива для произвольного стационарного эргодического источника с дискретным алфавитом и произвольных кодов над конечным алфавитом (см. задачу 1.3). Последняя и выявляет значение энтропии как оперативной характеристики. Если мы ослабим требование восстановимости последовательности источника по двоичной последовательности кода и заменим его некоторым условием на среднее искажение, мы, конечно, сможем обойтись меньшим, чем числом бит на символ источника. Такое обобщение на случай кодирования источника при наличии меры искажения называется теорией скорости как функции погрешности. Этой теории, созданной в 1948 г. Шенноном и развитой им же в 1959 г., мы посвящаем гл. 7 и 8.

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