Глава 1. КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ

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

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

§ 1.1. Дискретные ансамбли и источники

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

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

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

Говорят, что на конечном множестве X задано распределение вероятностей если каждому элементу сопоставлено число причем

Пусть А есть подмножество множества Число

представляет собой вероятность того, что при случайном выборе сообщения из множества X в соответствии с распределением будет выбрано сообщение, принадлежащее множеству А. Число называют также вероятностью множества А.

Пример 1.1.1. Пусть X — множество сообщений о результатах бросания правильной игральной кости. Тогда , причем есть сообщение о том, что выпало очков. Если то есть вероятность того, что при бросании кости выпало четное число очков.

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

Определение 1.1.1. Конечное множество X вместе с заданным на нем распределением вероятностей называется дискретным вероятностным ансамблем или коротко — дискретным ансамблем (сообщений) и обозначается символом . В тех случаях, когда из контекста видно, о каком распределении

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

Пусть два конечных множества. Множество, элементы которого представляют собой все возможные упорядоченные , называется роизведением множеств и обозначается через Согласно этому определению и суть различные множества. Если множества совпадают, то произведение обозначается как Аналогичным образом определяются произведения более чем двух множеств. Произведение представляет собой множество всех последовательностей длины таких, что первый элемент принадлежит множеству второй множеству д., элемент принадлежит множеству Если все множества совпадают между собой и с множеством X, то такое произведение обозначается как Таким образом, это множество всех последовательностей длины образованных из элементов множества

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

задают распределения вероятностей на множествах соответственно. Таким образом, при задании ансамбля фактически задаются еще два ансамбля Иногда, имея в виду ансамбль , мы будем говорить, что совместно заданы два ансамбля Это будет означать, что распределения вероятностей на множествах определяются по формулам (1.1.2) и (1.1.3), исходя из распределения вероятностей на множестве

Если распределение вероятностей на произведенйичдвух множеств удовлетворяет условию

то ансамбли называются статистически независимыми. В противном случае говорят, что эти ансамбли статистически зависимы.

Пусть задан ансамбль предположим, что такой элемент множества X, для которого Число

называется условной вероятностью сообщения при условии, что сообщение известно (иногда это число называют условной вероятностью сообщения относительно сообщения Легко увидеть, что множество условных вероятностей относительно фиксированного сообщения которое получается, когда индекс пробегает все возможные значения, удовлетворяет определению распределения вероятностей Такое распределение называется условным распределением на множестве V относительно фиксированного сообщения заметим, что (1.1.3) определяет так называемое безусловное распределение на Понятно, что аналогичные распределения могут быть определены также на множестве Таким образом, задание ансамбля определяет также условные ансамбли

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

называется условной вероятностью сообщения у,- при условии, что сообщение принадлежит множеству условной вероятностью относительно множества А). Легко видеть, что множество условных вероятностей относительно фиксированного множества А, которое получается, когда индекс пробегает все возможные значения, снова удовлетворяет определению распределения вероятностей. Такое распределение называется условным распределением на множестве У относительно фиксированного множества А. Если выбрать то Таким образом, условное распределение относительно множества это просто безусловное распределение на Если А состоит из одного элемента, скажем х, то равно вероятности, определенной в (1.1.5).

Аналогичные условные распределения могут быть определены также для множества Тем самым определены условные ансамбли

Рассмотрим произведение множеств и распределение вероятностей

заданное на этом произведении. Другими словами, рассмотрим вероятностный ансамбль Пусть

Соотношения (1.1.7) задают безусловные распределения вероятностей на множествах соответственно. Если для любых имеет место равенство

то ансамбли называют статистически независимыми.

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

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

Вводя по аналогии с (1.1.5) и (1.1.6) условные распределения на множестве можно получить различные условные ансамбли.

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

Можно представить себе более сложный эксперимент с костью и монетой. Предположим, что вначале бросается кость. Если выпало четное число очков, бросается неправильная монета, у которой вероятность выпадения стороны,

соответствующей равна (а стороны, соответствующей Если же выпало нечетное число очков, то бросается другая неправильная монета, у которой вероятность выпадения стороны, соответствующей равна 3/4 (а стороны, соответствующей При таком эксперименте на множестве имеются два условных распределения: при четных при нечетных Распределение вероятностей на множестве XV указано в следующей таблице:

(см. скан)

Нетрудно видеть, что безусловные распределения в этом случае такие же, как и в случае одной симметричной (правильной) монеты, но ансамбли статистически независимыми не являются.

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

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

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

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

где

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

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

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

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

Замечание. Распределение вероятности на подпоследовательностях может быть получено

с помощью соотношения (1.1.9), причем многими способами. Например,

Условие согласованности обеспечивает совпадение всех этих распределений.

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

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

- при Всюду в этой книге мы используем сокращенную форму записи вместо

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

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

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

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

где через обозначено общее для всех моментов времени одномерное распределение.

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

Пример 1.1.4. Пусть ансамбли примера Рассмотрим источник, выбирающий сообщения в четные моменты времени из множества X, а в нечетные — из У. Такой источник, очевидно, нестационарен. Пусть теперь источник выбирает сообщения из ансамбля примера 1.1.3. Если распределение вероятностей будет такое, как в и. б), то источник будет стационарным, но с памятью. Если же распределение вероятностей такое, как в то источник будет источником без памяти.