3.4 Основные теоремы Шеннона

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

Если поток информации, вырабатываемый источником, равен

, (3.46)

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

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

Основная теорема Шеннона для дискретного канала с шумами

Если поток информации, вырабатываемый источником, равен

, (3.46а)

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

, (3.47)

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

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

В общем случае выполнение (3.46а) может быть достигнуто с помощью кодирования достаточно длинных последовательностей сообщений. Если М_Х – число сообщений в одной кодируемой последовательности, то чем меньше ε в (3.46а) и η в (3.47), теми большим должно быть число М_Х, т.е. тем длиннее должна быть кодируемая последовательность.

Основная теорема Шеннона для непрерывных каналов

Если ε-энтропия источника непрерывных сообщений, определяющая количество информации, вырабатываемое источником в единицу времени (поток информации непрерывного источника) при заданной оценке g верности воспроизведения равна

, (3.48)

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

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

.

ε-энтропия определяется как наименьшее значение количества информации в принятой случайной величине Y относительно переданной случайной величине Х при заданной верности произведения g:

, (3.49)

где ε – приемлемо малая величина.

3.5 Энтропия источника при наличии коррелятивных связей между двумя соседними символами

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

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

Для описания такого источника необходимо задать распределение вероятностей p(x_i) и вероятности переходов (условная вероятность) p(x_i|x_k) или вероятности всех возможных пар символов p(x_i, x_k).

Нижеприведенное выражение описывает связь между этими вероятностями

. (3.50)

Если коррелятивные связи имеются между двумя соседними символами, то энтропия источника равна

(3.51)

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

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

p(x₁)=1/2, p(x₂)=1/4, p(x₃)= p(x₄)=1/8.

Для независимых событий

.

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

xixj	p(xi, xj)	p(xi | xj)	xixj	p(xi, xj)	p(xi | xj)
x1x1	13/32	13/16	x3x1	0	0
x1x2	3/32	3/16	x3x2	0	0
x1x3	0	0	x3x3	0	0
x1x4	0	0	x3x4	1/8	1
x2x1	1/32	1/8	x4x1	1/16	1/2
x2x2	1/8	1/2	x4x2	1/32	1/4
x2x3	3/32	3/8	x4x3	1/32	1/4
x2x4	0	0	x4x4	0	0

По заданным вероятностям появления символов p(x_i) и вероятностям пар импульсов p(x_i, x_j) из (3.50) определяются условные вероятности

, представленные в третьем и шестом столбцах таблицы.

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