Основы теории информации и кодирования

Основные понятия и определения

Для анализа различных источников информации, а также каналов се передачи необходимо иметь количественную меру, которая позволила бы оценить объем информации, содержащейся в сообщении и переносимой сигналом. Такую меру в 1946 г. ввел американский ученый К. Шеннон.

Далее источник информации полагаем дискретным, выдающим последовательность элементарных сообщений {я,}, каждое из которых выбирается из дискретного ансамбля (алфавита) а, а₂,…, й_А; к является объемом алфавита источника информации.

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

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

Будем считать, что количество информации /(«,), содержащееся в символе я» выражается через вероятность Р (а), i = 1, 2…к (заме- *.

тим, что ^ Р (а_:) = 1, так как все я, образуют полную группу собы;

1.2.

гий), и выбор этих символов осуществляется с помощью некоторой функциональной зависимости J (a,) = <�р[Р (я,)]. Количество информации ./(я,) удовлетворяет двум условиям: 1) Р{а,) = 1, если выбор источником символа априорно определен, J (a,) = <�р[1] = 0; 2) если последовательно выбраны символы я, и а" a P (a_t, a) — вероятность такого выбора, то количество информации, содержащееся в паре символов, равно сумме количества информации, содержащейся в каждом из символов я, и я, Эго свойство количественной меры информации называют аддитивностью.

Полагаем, что Р (а,) — условная вероятность выбора символа я, после всех предшествующих ему символов, а Р (а,, я,) — условная вероятность выбора символа я_; после я, и всех предшествующих, а, учитывая, что Р (а₁, а₁) = Р (а) Р (я,|я_у), условие аддитивности можно записать.

Введем обозначение Р (а) = Р_п Р (ар) = Q и перепишем условие (5.1):

Считаем, что Р, О * 0. Используя выражение (5.2), определим вид функции (р(Р). Осуществив дифференцирование, умножение на Р* 0 и обозначив РО = R, запишем.

Отметим, что соотношение (5.3) выполняется при любых R ф О и^^О. Однако это требование приводит к постоянству правой и левой частей (5.3): Pq>'(P)= Ар'(/?) — к — const. Тогда приходим к уравнению Рц>'(Р) = К и после интегрирования получаем.

Учтем, что [q>(1) = 0] и перепишем.

Следовательно, при выполнении двух условий о свойствах J (a,) выявилось, что вид функциональной зависимости J (a,) от вероятности выбора символа a_t с точностью до постоянного коэффициента К однозначно определяется.

Коэффициент К влияет только на масштаб и определяет систему единиц измерения количества информации. Так как 1п[Р] Ф 0, то имеет смысл выбрать К < Ос тем, чтобы мера количества информации J (a) была положительной.

Приняв К= -1, запишем.

Отсюда следует, что единица количества информации равна информации о том, что наступило событие, вероятность которого равна Me. Такая единица количества информации называется натуральной единицей. Чаще полагают, что К = —, тогда.

In 2.

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

где логарифм может быть с произвольным основанием.

Свойство аддитивности количественной меры информации позволяет на основе выражения (5.9) определять количество информации в сообщении, состоящем из последовательности символов. Вероятность выбора источником такой последовательности берется с учетом всех ранее имевшихся сообщений.

Количественная мера информации содержащейся в элементарном сообщении а₍, не дает представления о среднем количестве информации J (A), выдаваемом источником при выборе одного элементарного сообщения а_г

Среднее количество информации характеризует источник информации в целом и является одной из важнейших харакгеристик систем связи.

Определим эту характеристику для дискретного источника независимых сообщений с алфавитом К. Обозначим через Н (А) среднее количество информации, приходящееся на один символ и являющееся математическим ожиданием случайной величины Л — количества информации, содержащейся в случайно выбранном символе а

Среднее количество информации, приходящееся на один символ, называют энтропией источника независимых сообщений. Энтропия является показателем средней априорной неопределенности при выборе очередного символа.

Из выражения (5.10) следует, что если одна из вероятностей Р (а) равна единице (следовательно, все остальные равны нулю), го энтропия источника информации будет равна нулю — сообщение полностью определено.

Энтропия будет максимальной в случае равенства априорных вероятностей всех возможных символов К, т. е. Р (а_{) = 1 /К, тогда.

Если источник независимо выбирает двоичные символы с вероятностями Р, = Р (а_х) и Р₂= 1 — Р, то энтропия на один символ будет.

На рис. 16.1 показана зависимость энтропии двоичного источника от априорной вероятности выбора из двух двоичных символов, из этого рисунка также видно, что энтропия максимальна при Я, = Р₂ = 0,5.

1 о 1 ^двед— и в двоичных единицах log₂ 2 = 1;

Рис. 5.1. Зависимость энтропии при К = 2 от вероятности выбора одного из них Энтропия источников с равновероятным выбором символов, но с различными объемами алфавитов К, логарифмически увеличивается с ростом К.

Если вероятность выбора символов различна, то падает энтропия источника И (А) относительно возможного максимума Н (А)_пш = logК.

Чем больше корреляции между символами, тем меньше свободы выбора последующих символов и меньше информации имеет вновь выбираемый символ. Это связано с тем, что неопределенность условного распределения не может превышать энтропии их безусловного распределения. Обозначим энтропию источника с памятью и алфавитом К через Н (АА'), а энтропию источника без памяти, но гем же алфавитом — через Н (А) и докажем неравенство.

Введя обозначение Р (аа') для условной вероятности выбора символа а,(/ = 1, 2, К) при условии, что ранее выбран символ ajij =1,2,К) и опуская преобразования, без доказательства запишем.

что доказывает неравенство (5.13).

Равенство в (5.13) или (5.14) достигается в случае, когда.

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

Интересно, что энтропия текста на русском языке составляет 1,5 двоичных единиц на символ. В то же время при том же алфавите К= 32 с условием независимых и равновероятных символов Н (А)_тп = 5 двоичных единиц на символ. Таким образом, наличие внутренних связей уменьшило энтропию приблизительно в 3,3 раза.

Важной характеристикой дискретного источника является его избыточность р_и:

Избыточность источника информации является безразмерной величиной, находящейся в пределах [0; 1 ]. Естественно, что при отсутствии избыточности р_и = 0.

Для передачи некоторого объема информации от источника, не имеющего корреляционных связей между символами, при равной вероятности всех символов требуется минимально возможное количество передаваемых символов /7_min: /г₀(/7₀Я (Л_тах)). Для передачи того же объема информации от источника с энтропией (символы взаимосвязаны и неравновероятны) потребуется среднее количество символов п = n"H (A)_mJH (A).

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

Если производительность И (А) определять в двоичных единицах, а время в секундах, то Н'(А) — это число двоичных единиц в секунду. Для дискретных источников, выдающих стационарные последовательности символов достаточно большой длины /?, вводят понятия: типичные и нетипичные последовательности символов источника, на которые можно разбить все последовательности длиной п. Все типичные последовательности N_lMl(A) источника при п —"оо имеют примерно одинаковую вероятность появления.

Суммарная вероятность появления всех нетипичных последовательностей при этом стремится к нулю. В соответствии с равенством (5.11), полагая, что вероятность типичных последовательностей /N_rm(A), энтропия источника равна logN_TIin(, 4) и тогда.

Рассмотрим количество и скорость передачи информации по дискретному каналу с шумами. Раньше рассматривалась информация, выдаваемая дискретным источником в виде последовательности символов {я,}.

Теперь предположим, что информация источника кодируется и представляет последовательность кодовых символов {Ь, (/ = 1,2,.т — основание кода), согласовывается с дискретным каналом передачи информации, на выходе которого появляется последовательность сим;

волов.

Предполагаем, что операция кодирования взаимно-однозначная — по последовательности символов {Ь,} можно однозначно восстановить последовательность {я,}, т. е. по кодовым символам можно восстановить информацию источника полностью.

Однако если рассмотреть символы выхода |?. j и символы входа {/>,}, то вследствие наличия в канале передачи информации помех, восстановление невозможно. Энтропия выходной последовательности //(/?).

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

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

Оценим потери информации в канале с шумами и количество информации, переданной по каналу с шумами. Считаем, что символ передан правильно, если при переданном символе 6, принят А.

символ bj с тем же номером (/ = j). Тогда для идеального канала без шумов запишем:

По символу bj-на выходе канала вследствие неравенств (5.21).

неопределенность неизбежна. Можно считать, что информация в символе b_i не передана полностью и часть ее потеряна в канале из-за воздействия помех. Основываясь на понятии количественной меры информации, будем считать, что численное выражение неопределенности, возникающей на выходе канала после приема символа ft_;:

и оно определяет количество потерянной информации в канале в процессе передачи.

Зафиксировав ft. и усреднив (5.22) по всем возможным символам, получаем сумму.

определяющую количество теряемой в канале информации при передаче по каналу без памяти элементарного символа при приеме символа bj (t).

л.

При усреднении суммы (5.23) по всем ft получаем величину Z?), которую обозначаем через н (в/В- Она определяет количество информации, теряемой при передаче одного символа по каналу без памяти:

где P^bjbjj — совместная вероятность события, что при передаче л.

символа Ь. он примет символ b_t.

Н [в/зависит от характеристик источника информации на.

/ч входе канала В и от вероятностных характеристик канала связи. По Шеннону в статистической теории связи н (в/в называют ненадежностью канала.

Условная энтропия НВ/ В, энтропия дискретного источника на входе канала Н (В) и энтропия И ^В) на его выходе не могут быть отрицательными. В канале без помех ненадежность канала.

н (в/в = 0. В соответствии с (5.20) отметим, что Н^в/В^< Н (В),

а равенство имеет место только при статистической независимости входа и выхода канала:

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

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

сать, что при отсутствии помех его ненадежность и.

Под переданной в среднем по каналу информацией J[ b/на один символ понимаем разность между количеством информации на входе канала J (B) и информацией, потерянной в канале /?).

Если источник информации и канал без памяти, то.

Выражение (5.27) определяет энтропию выходных символов канала. Часть информации на выходе канала полезная, а остальная ложная, гак как она порождена помехами в канале. Обратим внимание, что н[в/2?) выражает информацию о помехах в канале, а разность я (й)-Я (й/й) — полезную информацию, прошедшую через канал.

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

Как правило, учитывается наиболее распространенный вид помех — аддитивные шумы N (t); сигнал на выходе канала имеет вид:

Для дискретных сигналов эквивалентный шум, следуя из (5.28), имеет дискретную структуру. Шум представляет собой дискретную случайную последовательность, похожую на последовательности входящего и выходящего сигналов. Обозначим символы алфавита аддитивного шума в дискретном канале через Ц1 = 0, 1,2, т — 1). Условные вероятности перехода в таком канале.

Так как И {^В/?) < И (В) то, следовательно, информация выходной последовательности дискретного канала #(/) относительно входной B (t) или наоборот И (В) — Н^в/в}< И (5).

Иными словами, информация, передаваемая по каналу, не может превышать информации на его входе.

Если на вход канала поступает в среднем х_к символов за одну секунду, то можно определить среднюю скорость передачи информации по каналу с шумами:

где Н (В) = V_kJ (B, B^ - производительность источника на входе канала; н (в/в) = У_кн (в, в) ~ ненадежность канала в единицу времени; Н (B) = V_kH^B^ — производительность источника, образованного выходом канала (выдающего часть полезной и часть ложной информации); Н^в/В^ = У_к1/(в/в) — количество ложной информации, создаваемой помехой в канале в единицу времени.

Понятия количества и скорости передачи информации по каналу можно применять к различным участка канала связи. Это может быть участок «вход кодера — выход декодера».

Отметим, что, расширяя рассматриваемый участок канала, нельзя превысить скорость ни на одной его составной части. Любое необратимое преобразование ведет к потере информации. К необратимым преобразованиям относится не только воздействие помех, но и детектирование, декодирование при кодах с избыточностью. Имеются способы снижения потерь при приеме. Это «прием в целом».

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

где максимум берегся по возможным источникам входа В при заданном V_k и объеме алфавита символов входа т.

Исходя из определения пропускной способности дискретного канала запишем.

Заметим, что С = 0 при независимом входе и выходе (высок уровень помех в канале) и соответственно.

при полном отсутствии воздействия помех на сигнал.

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

Рис. 5.2. Пропускная способность канала.

График зависимости пропускной способности двоичного канала от параметра р представлен на рис. 5.2. При р = ½ пропускная способность канала С = 0, условная энтропия.

//(/?//?) = 1. Практический интерес график представляет при 0 < /; < ½.

Основная теорема Шеннона по оптимальному кодированию связана с понятием пропускной способности. Ее формулировка для дискретного канала следующая: если производительность источника сообщений Н[А) меньше пропускной способности канала С:

го существует способ оптимального кодирования и декодирования, при кагором вероятность ошибки или ненадежность канала н[а!A j может быть сколь угодно мала. Если.

го таких способов не существует.

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

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

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