Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 5
Текст из файла (страница 5)
(1.2) Требование аддитивности количества информации при операции укрупнения алфавита приводит к равенству р ]р(х;)]+ рЧ,р(х„] х;)] = р (р(хь хк)] = = — р ]р (хз) р (хв]хс)]. Пусть д(хз) =р н р(ха]хг) =д. Тогда для любых р и д(0<р -,1, 0<4<1) должно соблюдаться уравнение р(Д) + р(4) =ф(дч) (1.3) Случаи р=О или д=О мы исключаем нз рассмотрения, так как вследствие конечного числа букв алфавита эти равенства означают, что выбор источником пары букв хь ха является невозможным событием. Равенство (1.3) является функциональным уравнением, из которого может быть определен вид функции ср. Продифференцируем обе части уравнения (!.3) по йч Умножим обе части полученного уравнения на р и введем обозначение рд=-г, тогда (!.4) )кр'(Р) = пр'(г) . Это уравнение должно быть справедливо при любом р(0<р<1) и любом г(О<г<р).
Последнее ограничение (г<р) не существенно, так как уравнение (!.4) симметрично относительно д и г и, следовательно, должно выполняться для любой пары положительных значений " По сушсству, всс фигурируюшве в этих рассуждениях всроитности ивлиютси условными, так как зависят от букв, предшествовавших хь Вводя обозначснпе р(хь!х;), мы подчеркиваем только, что при вычислении этой вероятности помимо букв, предшествовавших хь нужно учитывать и факт выбора самой буквы х;. 2! аргументов, не превышающих единицы. 1-1о это возможно лишь в том случае, если обе части (!.4) представляют некоторую постоянную величину А, откуда ж'(и =- й ~" (д) = — „-.
Интегрируя полученное уравнение, найдем ~р(р) =А 1и р+С, (1.5) где С вЂ” произвольная постоянная интегрирования. Формула (!.5) определяет класс функций ~р(р), выражающих количество информации при выборе буквы хь имеющей вероятность р(х;) =р, и удовлетворяющих условию аддитивности. Для определения постоянной интегрирования С воспользуемся высказанным выше условием, по которому заранее предопределенный элемент сообщения, т.
е. имеющий вероятность р=!, не содержит информации. Следовательно, ~р(1) =О, откуда сразу с.педует, что С=О. Что касается коэффициента пропорциональности й, то его можно выбрать произвольно, так как он определяет лишь систему единиц, в которых измеряется информация. Однако, поскольку 1пр<О, разумно выбирать й отрицательным, для того чтобы количество информации было положительным. Наиболее простым является выбор й= — !.
Тогда Р (Р) = — — 1 пР === 1 и —. (1.6) Р При этом единица )соличества информации равна той информации, которая содержится в элементарном сооб. шепни, имеюгцем вероятность !/е (е — основание натуральных логарифмов), или, другими словамп, равна информации, содержащеися в сообщении о том, что наступило событие, вероятность которого равнялась !/е. Такую единицу информации называют натуральной единицей. ! Чаще выбирают й= — — „. Тогда с(р) == — Я или Гя2 у (р) = — 1од, р —....- 1о(1,, —. Р' При таком выборе й единица информации называется двоичной. Она равна информации, содержащейся в сооб- шенин о том, что наступило событие, вероятность которого равнялась '/и т. е.
которое могло с равной вероятностью наступить и не наступить. Иногда используют и другие единицы информации, например десятичные. Мы будем применять как двоичные, так и натуральные единицы количества информации. В тех случаях, когда выбор единиц не и~рвет роли, мы будем писать (1.66) ~р(р) = — !пар, считая, что логарифм берется по любому основанию, лишь бы это основание сохранялось на протяжении решаемой задачи. Благодаря свойству аддитивности информации выражения (1.6) позволяют определить количество информа ции не только в букве сообщения, но и в любом сколь угодно длинном сообщении.
Нужно лишь принять за р вероятность выбора этого сообщенця из всех возможных с учетом ранее выбранных сообщений. 1А. Энтропия и производитепьность источника сообщений Для построения теории связи основное значение имеет не количество информации, содержащееся в некотором конкретнол1 сообщении, а средняя величина (математическое ожидание) количества информации, содержащегося в олпом элементарном сообщении источника: //(х) = ~/ (, ( )). (1.7) Здесь, как и всюду в дальнейшем, горизонтальная черта обозначает математическое ожидание. Величина //(х) характеризует источник сообщений и называется энтропией источника, отнесенной к одному элементу сообщения.
В простейшем случае источника независимых сообщений, в котором вероятность выбора того или иного элемента сообщения не зависит от ранее выбранных элементов, //(х)=- — '1 р(хх)!одр(х„), я=1 где ! — объем алфавита источника; р(хх) — вероятность выбора А-го элемента (й-й буквы). 23 Обычно отмечают, что энтропия характеризует заданное распределение вероятностей с точки зрения степени неопределенности исхода испытания, т.
е. неопределенности выбора того или иного сообщения. Действительно, легко убедиться, что энтропия ранна нулю тогда и только тогда, когда одна из вероятностей р(х») равна единице, а все остальные равны нулю; это означает полную определенность выбора. При фиксированном объеме алфавита г энтропия принимает максимальное значение в случае, когда все р(х») одинаковы; тогда р(х») = — и ! г! ч-ч ! ! | )оК г )гг~ ( (!.8) А=г При этом степень неопределенности выбора, понимаемая интуитивно, болыпе, чем при нс равных вероятностях р(х»), Наконец, если рассматривать алфавиты с равновероятными элементами, ио с разными объемами, то энтропия увеличивается с увеличением объема й Это также согласуется с интуитивным представлением о степени неопределенности выбора.
После того как источник произвел выбор некоторого конкретного элемента сообщения, существовавшая неопределенность устраняется. С этой точки зрения количество информации, содержащееся в среднем в элементе, измеряется неопределенностью, которая оказалась устраненной в результате выбора этого эпемента, т. е. энтропией источника. Возможна и другая наглядная интерпретация понятия эитрошги как меры «разнообразия» сообщений, создаваемых источником. Легко убедиться, что приведенные выше свойства энтропии вполне согласуются с интуитивным представлением о мере разнообразия.
Также естественно считать, что количество информации, содержащееся в элементе сообщения, тем больше, чем более разнообразны возможности выбора этого элемента. Определим теперь энтропию для более общего класса источников сообщений, в котором вероятность выбора элемента зависит от того, какие элементы были выбраны ранее. Ограничимся при этом источниками, в которых вероятностные связи выражены только для элементов, $4 не очень далеко отстоящих друг от друга. Именно с такими источниками сообщений чаще всего приходится встречаться в реальной действительности. Так, например, если источник выдаст сообщение в виде текста, написанного па русском (плп каком-либо ином) языке, то вероятность появления некоторой буквы сильно зависит от нескольких предшествующих букв, по почти не зависит от той части текста, которая отстоит от нее, скажем, на несколько десятков слов.
Действительно, если в каком-либо тексте мы найдем сочетание букв «расиределе...», то с большой степенью уверенности можно ожидать, что за ними последу!от буквы «ние». Далее, если текст математический, то вслед за словом «расаредегение» с большой вероятностью последует слово «вероятностей». Однако вероятность того, какие буквы или слова будут па следующей строке, практически не зависит от букв, написанных в начале предыдущей строки.
Несколько более протяженные вероятностные связи можно обнаружить в стихотворном тексте (вследствие ритма и рифмы), по и здесь онп, как правило, ие простираются дальше, чем на одну строфу. Другим примером может служить источник, измеряющий с заданной точностью через определенные промежутки времени атмосферное давление в каком-либо пункте. В этом примере вероятностные связи между результатами наблюдений распространяются на большие промежутки времени, порядка нескольких дней или недель, и, следовательно, охватывают много элементарных сообщений (еслп измерения производятся достаточночасто, например каждый час). Однако и здесь можно указать достаточно большой отрезок времени (несколько месяцев или лет), на который эти связи практически совсем не распространяются.
Математическим представлением сообщений, создаваемых такими источниками, язвляютсн цепи Маркова. Цепью Маркова п-го порядка называется последовательность зависимых испытаний, при которой условная вероятность некоторого исхода х„ в г-м испытании, когда известны исходы в предыдущих и испытаниях, не зависит от более ранних исходов. Другими словами, при г>а,>а,» ...
а,>а„+г р (хгг!) х"', х'"*', ..., х " ) =р(х!'!)хг"', х'", ..., х "+' ). 25 (!.!2) р(кв) =- Ъ Р,р,(кв). т=.! (!.9) ч=! я=! 27 В марковском источнике и-го порядка распределение вероятностей р(ха) букв пе остается постоянным, а за. висит от того, каковы были последние и букв сообщения, Иначе говоря, последние и букв определяют некоторое состояние Б источника (с/=- 1, 2, ..., «), в котором вероятность выбора й-й буквы алфавита равна рв(хх). Число различных возможных последовательностей из и букв при объеме алфавита 1 равно 1в. Следовательно, число «различных состояний марковского источника конечно и не превышает 1'".
Если для каждого состояния 5 заданы вероятности рч(хь) и известно, какое состояние определяется любой последовательностью из и элементов, то могут быть вычислены вероятности Рч каждого из состояний Бч(0=1, ..., «). При некоторых дополнительных условиях, называемых условиями эргодичности, выполняемых для всех источников, представляющих практический интерес, существуют безусловные веРоЯтности Р(хь) выбоРа и-го элементаРного сообще- ния Выражение Нч = — у' рч(ки) 1оп р„(к ), прсдставляю- щее математическое ожидание количества информации в выбираемом элементе, для источника, находящегося в г)-м состоянии, можно назвать энтропией этого состояния. Энтропию источника (рассчитанную на один элемент) Нч в соответствии с (1.7) получим путем усреднения по всем возможным состояниям Н (к) = ~' 5ч Рч р, (кг,) 1ой' рч(кв).
(1.10) Выражение (1.7а) является частным случаем (1.10) при «=1, т. е. при единственном состоянии источника. Если бы мы не учитывали вероятностных связей между элементами сообщения и исходили из безусловных верояг- 26 ностей р(хя), определяемых по (1.9), то за энтропию ис- точника на один элемент следовало бы принять / / г а =-у (уз. ! и ьг17;г,!..!) огп ч==! В теории информапии доказывается, что всегда П~ ~Н", т. е. наличие вероятностных связей уменьшает энтропию источника сообщений.