Теоремы Шеннона

Пусть имеется источник информации Х и приёмник У, связанные каналом К. Известна производительность источника информации Н₁(Х), т.е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источником в единицу времени). Известна пропускная способность канала С₁, т.е. максимальное количество информации, которое способен передать канал в ту же единицу времени. Возникает вопрос: какой должна быть пропускная способность канала, чтобы он справлялся со своей задачей, т.е. чтобы информация от источника к приёмнику поступала без задержки?

Несмотря на то, что ответ и так очевиден, он даётся в первой теореме Шеннона.

1-я теорема Шеннона:

Если пропускная способность канала связи С₁ больше энтропии источника информации в единицу времени

С₁ > Н₁(Х),

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

Если же, напротив,

С₁ < Н₁(Х),

то передача информации без задержек невозможна.

Передача информации с искажениями.

Пропускная способность канала с помехами.

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

Совершенно очевидно, что наличие помех приводит к потере информации. Чтобы в условиях наличия помех получить на приёмнике требуемый объём информации, необходимо принимать специальные меры. Одной из таких мер является введение так называемой «избыточности». Известно, что все живые языки обладают некоторой избыточностью, доходящей до 50% (т.е.50% букв мы могли бы вообще не произносить или перепутывать их местами:-)).

Вот пример: По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бквуы мгоут селдовтаь в плоонм бсепордяке, всё-рвано ткест чтаитсея без побрелм.

Надеюсь, вы поняли, что здесь написано))))

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

Рассмотрим, например, такую задачу. Канал связи К передаёт от источника информации Х к приёмнику У элементарные символы 0 и 1 в количестве k символов в единицу времени. В процессе передачи каждый символ, независимо от других, с вероятностью μ может быть искажён (т.е. заменён противоположным). Требуется найти пропускную способность канала.

Определим сначала максимальную информацию на один символ, которую может передавать канал. Пусть источник производит символы 0 и 1 с вероятностями p и 1-p.

Тогда энтропия источника будет

Н(Х)=-p log p - (1-p) log (1-p).

Если бы передача сообщений не сопровождалась ошибками, то количество информации на один символ было бы равно самой энтропии системы Х. При наличии ошибок оно будет меньше:

I = H(Y) - H(Y/X).

Чтобы найти полную условную энтропию Н(У/Х), найдём сначала частные условные энтропии: Н(У/х₁) и Н(У/х₂).

Вычислим Н(У/х₁); для этого предположим, что передан символ 0. Найдём условные вероятности того, что при этом система У находится в состоянии у₁=0 и в состоянии у₂=1. Первая из них равна вероятности того, что сигнал не перепутан:

Р(у₁/х₁)=1-µ;

вторая - вероятности того, что сигнал перепутан:

Р(у₂/х₁)=µ.

Условная энтропия Н(У/х₁) будет:

Н(У/х₁)=-Σ Р(у_i/x₁) log P(y_i/x₁) = -(1-µ) log (1-µ) - µ log µ.

Найдём теперь условную энтропию системы У при условии, что передан сигнал 1:

Р(у₁/х₂)=µ; Р(у₂/х₂)=1-µ,

откуда

Н(У/х₂)= - µ log µ - (1-µ) log (1-µ).

Таким образом

Н(У/х₁)= Н(У/х₂).

Полная условная энтропия Н(У/Х) получится, если осреднить условные энтропии с учётом вероятностей р и 1-р. Так как частные условные энтропии равны, то

Н(У/Х)= - µ log µ - (1-µ) log (1-µ).

Вывод: условная энтропия Н(У/Х) совсем не зависит от того, с какими вероятностями встречаются символы 0 и 1 в передаваемом сообщении, а зависит только от вероятности ошибки µ.

Теперь вычислить информацию, передаваемую одним символом:

I = H(Y) - H(Y/X) = - r log r - (1-r) log (1-r) - - µ log µ - (1-µ) log (1-µ) =

= [η(r) + η(1-r)] - [η(µ) + η(1-µ)],

Где r - вероятность того, что на выходе появится символ 0.

Мы знаем, что энтропия и количество информации максимально при равновероятных сигналах, т.е. (в нашем случае) при р=1/2. Следовательно, максимальное количество информации, передаваемое одним символом

I _max= 1 - [η(µ) + η(1-µ)],

А пропускная способность канала связи будет равна

С= k(1 - [η(µ) + η(1-µ)]).

Заметьте, что η(µ) + η(1-µ) - это энтропия системы, имеющей 2 возможных состояния с вероятностями µ и 1-µ. Она характеризует потерю информации на один символ, связанную с наличием помех.

Пример 1. Определить пропускную способность канала связи, способного передавать 100 символов 0 или 1 в единицу времени, причем каждый из символов искажается (заменяется противоположным) с вероятностью µ=0,001.

Решение:

η(µ) = η(0,001) = 0,0664

η(1-µ) = 0,0144

η(µ) + η(1-µ) = 0,0808

На один символ теряется информация 0,0808 бит. Пропускная способность канала равна

С = 100(1-0808) = 91,92 ≈ 92 бит в единицу времени.

Зная пропускную способность канала, можно определить верхний предел скорости передачи информации по каналу с помехами. К этому случаю относится вторая теорема Шеннона.

2-я теорема Шеннона:

Пусть имеется источник информации Х, энтропия которого в единицу времени равна Н₂(Х), и канал с пропускной способностью С₂. Тогда, если

Н₂(Х) >С₂,

То при любом кодировании передача сообщений без задержек и искажений невозможна. Если же

Н₂(Х) < С₂,

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

Пример 2. Имеются источник информации с энтропией в единицу времени Н(Х) = 100 бит и 2 канала связи; каждый из них может передавать в единицу времени 70 двоичных знаков (0 или 1); каждый двоичный знак заменяется противоположным с вероятностью µ=0,1. Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником?

Решение: Определяем потерю информации на один символ:

η(µ) + η(1-µ) = 0,332+0,137=0,469 бит

Максимальное количество информации, передаваемое по одному каналу в единицу времени:

С = 70(1-0,469) = 37,2 бит.

Максимальное количество информации, которое может быть передано по двум каналам в единицу времени:

37,2*2 = 74,7 бит,

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

Поиск по сайту: