Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Решение задач
Энтропия
Цель занятия: на конкретных примерах усвоить основные понятия теории информации и энтропии.
Расчетные формулы
Количество информации ,бит (1)
- априорная вероятность, являющаяся мерой неопределенности, знаний о событии до получения сообщения ;
- апостериорная вероятность , являющаяся мерой знаний о событии после получения сообщения
При =1 (безошибочный прием сообщения ) выражение примет вид
(2)
определяет собственное количество информации в сообщении.
Если алфавит дискретного сообщения имеет n – символов, то его можно рассматривать как случайную величину Х, возможными значениями которой являются используемые в алфавите символы х1,х2,х3, хn с известными вероятностями появления их в тексте,Р(х1) = . Среднее количество собственной информации, приходящейся на один символ из множества всех символов данного алфавита, называется энтропией дискретного сообщения (случайной величины Х)
бит /символ.
Энтропия характеризует степень неопределенности случайной величины Х Энтропия на выходе дискретного канала связи определяется как среднее количество информации, прошедшее по каналу связи с одним символом.
Где – вероятность появления символа на выходе канала связи
- вероятность появления на выходе канала связи символа -, при условии появления на выходе - вероятность одновременного появления символов на входе и выходе канала связи, соответственно. - энтропия сообщения на входе ;
и- условные энтропии, характеризующие воздействие помех.
Пропускная способность канала связи С может быть определена по формуле:
F – полоса пропускания канала; - вероятность искажения сообщения.
Решения задач
Задача 1.Самолет противника с равной вероятностью может находится в одной из 250 зон. Какое количество информации будет получено при обнаружении самолета в одной из зон, если вероятность правильного обнаружения равна 0,9846.
Решение
Выбор расчетной формулы
Определение Априорная вероятность появления самолета в одной из зон находится с использованием классического определения вероятности = 0.0004
Определим . при обнаружении самолета в одной из зон, правильность такого решения можно гарантировать с вероятностью 0,9846. Следовательно = 0,9846.
Определение количества информации
Ответ : I = 8 , бит,
Задача 2: Известно, что энтропия русского текста составляет приблизительно 0,5 .Какое количество информации получит читатель, прочтя произвольное слово из 6- ти букв.
Решение
1. Определяем максимальную энтропию одной буквы. Машинописный алфавит русского текста содержит 32 буквы. Энтропия максимальна, если все символы используемого алфавита равновероятны. Следовательно, для алфавита , объема
бит/ симв.
2. Определение количества информации в слове. в случае слова из m- = 6 , букв.
по условию ,бит / симв.
Тогда , бит
Ответ: 15 бит.
Задача: Определить пропускную способность двоичного симметричного канала связи с полосой пропускания и вероятностью ошибочного приема символа из – за помех = 0.3/
Решение:
Выбор исходной формулы
Ответ : 950 бит / сим.
Задача 4. Для передачи сообщения, используется алфавит объема Вероятности появления символов этого алфавита в сообщении = ; = ; = . При передаче по каналу связи символы могут быть искажены с одинаковой вероятностью =0,1. Определить средне количество информации на выходе такого канала связи .
Решение
1.Выбор исходной формулы .
2. Определение безусловной энтропии. =
Бит / симв.
3. Определение условной энтропии
В этой формуле - неправильный прием символа. - правильный прием символа. Подставляя вероятность приходим к выражению вида.
и т.д.
4. Определение
= 1,5 – 08 = 0,7 бит / симв.
Задачи для самостоятельного решения
Ответ: =0,352 бит/ символ.
Продолжение практического занятия
В качестве основной характеристики сообщения теория информации принимает величину, называемую количеством информации. Это понятие не затрагивает смысла и важности передаваемого сообщения, а связано со степенью его неопределенности.
Пусть алфавит источника сообщений состоит из m знаков, каждый из которых может служить элементом сообщения. Количество N возможных сообщений длины n равно числу перестановок с неограниченными повторениями:
LogN = = n log m
Если для получателя все N сообщений от источника являются равновероятными, то получение конкретного сообщения равносильно для него случайному выбору одного из N сообщений с вероятностью 1/N.Ясно, что чем больше N, тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение.
Поэтому число N могло бы служить мерой информации. Однако, с позиции теории информации, естественно наделить эту меру свойствами аддитивности, т.е. определить ее так, чтобы она была пропорциональна длине сообщения (например, при передаче и оплате сообщения - телеграммы, важно не ее содержание, а общее число знаков).
В качестве меры неопределенности выбора состояния источника с равновероятными состояниями принимают логарифм числа состояний :
LogN = = n log m
эта логарифмическая функция характеризует количество информации:
Указанная мера была предложена американским ученым Р.Хартли в 1928 г.
Количество информации, приходящееся на один элемент сообщения (знак, букву), называется энтропией:
В принципе безразлично, какое основание логарифма использовать для определения количества информации и энтропии, т. к. в силу соотношения
переход от одного основания логарифма к другому сводится лишь к изменению единицы измерения. Так как современная информационная техника базируется на элементах, имеющих два устойчивых состояния, то обычно выбирают основание логарифма равным двум, т.е. энтропию выражают как:
Тогда единицу количества информации на один элемент сообщения называют двоичной единицей или битом. При этом единица неопределенности (двоичная единица или бит) представляет собой неопределенность выбора из двух равновероятных событий (bit — сокращение от англ. binary digit — двоичная единица)
Так как из log2 m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.
Двоичное сообщение длины n содержит n бит информации. Единица количества информации, равная 8 битам, называется байтом.
Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения - дитах, причем 1
1дит = 3,32 бит.
Пример1. Определить количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. Пусть в кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайным по амплитуде импульсов,
причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В.
Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней: n = 600.
Количество элементов сообщения (знаков) в одной строке равно числу значений, которое может принять амплитуда импульсов в строке,: m = 8.
Количество информации в одной строке , а количество информации в кадре I
бит
Пример2. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.
Решение. Так как монеты внешне не отличимые, то они представляют источник с равновероятными состояниями, а общая неопределенность ансамбля, характеризующая его энтропию, поэтому составляет: H1= Iog 27
бит.
Одно взвешивание способно прояснить неопределенность ансамбля насчитывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии).Так как все исходы равновероятны (нельзя заранее отдать предпочтение одному из них), то результат одного взвешивания представляет источник с равновероятными состояниями, а его энтропия составляет:
Так как энтропия отвечает требованию аддитивности и при этом
то для определения фальшивой монеты достаточно произвести три взвешивания.
Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие.
Аналогично, после второго взвешивания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальшивую монету.
Рассмотренная выше оценка информации основана на предположении о равновероятности всех знаков алфавита.
В общем случае каждый из знаков появляется в сообщении с различной вероятностью.
Пусть на основании статистического анализа известно, что в сообщении длины n знак xi появляется ni раз, т.е. вероятность появления знака:
Все знаки алфавита составляют полную систему случайных событий, поэтому:
Число всех возможных сообщений длины n, в которых знак входит определяется, где i = 1.2.3. m как число перестановок с повторениями.
РАСЧЕТНЫЕ ФОРМУЛЫ
1) Скорость передачи сигнала в цифровой форме: ,
где fд – частота дискретизации;
, где Fмакс – граничная частота исходного сигнала.
К – число двоичных символов в одном дискретном отсчете.
, где m – число уровней квантования исходного сигнала.
2) При равномерном расположении тактовых импульсов внутри интервала дискретизации минимальная полоса частот цифрового канала, предназначенного для передачи цифровой информации со скоростью С определяется по формуле:
3) Физический объем сигнала: ,
где Tc – длительность сигнала; Fc – ширина спектра;
Dc – динамический диапазон уровней сигнала.
,
где Рмакс и Рмин – максимальное и минимальное значение мощности сигнала;
Рш – значение мощности шумов в канале.
4) Физический объем канала: ,
где Тк – время использования канала; Fк – полоса пропускаемых каналом частот;
Dк – динамический диапазон уровней, пропускаемых каналом с допустимыми искажениями.
5) Количество информации I(ai), содержащееся в символе ai, выбираемом из ансамбля {ai} (i = 1, 2, 3,…, K, K – объем алфавита) с вероятностью Р(аi), определяется как
, причем .
6) Среднее количество информации (энтропия источника), приходящееся на один символ, выдаваемый дискретным источником независимых сообщений с объемом алфавита К:
.
7) Избыточность дискретного источника: .
Если источник без памяти и все символы равновероятны, то и избыточность .
8) Если в единицу времени источник выдает в среднем Vи символов, то среднее количество информации, создаваемое источником в единицу времени (производительность дискретного источника):
, где Тср – средняя длительность одного символа.
9) Средняя вероятность ошибки при оптимальном кодировании: ,
где Т – длительность сигнала, соответствующего последовательности символов источника достаточно большой длины; [C-H’(A)] – определяет запас пропускной способности канала.
10) Максимальный объем информации, который может быть передан по непрерывному каналу с пропускной способностью С:
, где Тк – время использования канала.
11) Если число разрядов во всех кодовых комбинациях n=const, то код называется равномерным. Число кодовых комбинаций равномерного кода:
, где m – основание кода; n – число разрядов в кодовой комбинации.
12) Каждую букву из ансамбля {ai} (i = 1, 2, 3,…, K, K – объем алфавита) можно закодировать при условии:
, где m – основание кода; n – число разрядов в кодовой комбинации.
Код, для которого , называется примитивным (код без избыточности). Для корректирующих кодов справедливо неравенство: .
При этом часть кодовых комбинаций используется для кодирования (эти кодовые комбинации называются разрешенными их число равно К), а другая часть при кодировании не используется. Число неиспользованных при кодировании комбинаций, называемых запрещенными, равно N – K.
13) Избыточность кода можно оценить соотношением: ,
где Ри – избыточность источника;
Vи и Vк – скорость выдачи символов источником и кодером соответственно.
14) Избыточность равномерного m – позиционного n – разрядного кода при Ри = 0:
, где - число символов кода на один символ источника.
15) Средняя длина кодовых комбинаций экономного кода не может быть меньше величины Nмин, которая согласно теореме Шеннона об оптимальном кодировании в каналах без шумов определяется по формуле:
, где m – основание кода.
16) Избыточность оптимального по Шеннону кода определяется соотношением:
, где С – пропускная способность канала.
ЗАДАЧи
1. Верхняя граничная частота ТВ сигнала равна 6 МГц. Число уровней квантования исходного сигнала равно 256. Найти скорость передачи цифрового потока и минимальную полосу частот цифрового канала.
2. При дискретизации цветного изображения был применен стандарт 4:2:2. Найти суммарную скорость передачи цифрового потока и минимальную полосу частот цифрового канала для двух значений числа двоичных символов в кодовой комбинации одного отсчета равных 8 и 10.
3. Во сколько раз отличаются скорости передачи цифрового потока и минимальные полосы частот цифрового канала при использовании стандартов 4:1:1 и 2:1:1. Число двоичных символов К в кодовой комбинации одного отсчета равно 10.
4. Сигнал с полосой 100 кГц передается по каналу связи в течение 30 с. Максимальная мощность сигнала 120 мВт, мощность шума 9,5 мВт. Найти физический объем сигнала.
5. Найти мощность сигнала, который может быть передан по каналу связи с физическим объемом 106 и полосой 10 кГц. Время использования канала 10 с. В канале действует шум с равномерной спектральной плотностью мощности Gш=10-4 мВт/Гц.
6. Определить количество информации, содержащееся в каждом из символов источника при их независимом выборе. Источник без памяти выдает символы из ансамбля А={ai} (i=1, 2, 3, 4) c вероятностями Р(а1)=0,25; Р(а2)=0,16;Р(а3)=0,36; Р(а4)=0,23. Найти энтропию и избыточность источника.
7. Источник без памяти выдает символы из ансамбля А={ai} (i=1, 2, 3, 4, 5) с вероятностями Р(а1)=0,175;Р(а2)=0,045; Р(а3)=0,038; Р(а4)=0,6; Р(а5)=0,142. Средняя длительность одного символа равна 0,3 с. Определить избыточность дискретного источника и среднее количество информации, создаваемое источником в единицу времени.
8. Источник сообщений без памяти и объемом алфавита 12 выдает символы с равной вероятностью. Средняя длительность одного символа равна 0,15 с. Найти среднее количество информации, создаваемое источником в единицу времени и среднее количество символов.
9. За время равное 106 с источник выдал 107 бит информации двоичными посылками длительностью 10 мс. Во сколько раз изменилось время передачи и количество посылок для передачи того же объема информации после устранения избыточности (т.е. каждый символ источника несет 1 бит информации). Определить избыточность источника.
10. Найти запас пропускной способности канала связи при условии, чтобы вероятность ошибки не превысила величину 10-6. Длительность кодовой комбинации равна 0,2 с. Во сколько раз изменится запас пропускной способности канала, если при неизменной вероятности ошибки длительность кодовой комбинации увеличится в 3 раза?
11. Дискретный источник выдает символы из ансамбля А={ai} с объемом 10. Какое минимальное число разрядов должны иметь кодовые комбинации равномерного примитивного двоичного кода, предназначенного для кодирования символов данного ансамбля? Найти скорость передачи и минимальную полосу частот цифрового канала необходимую для передачи ТВ сигнала с граничной частотой 6,5 МГц с таким числом разрядов.
12. Источник сообщений выдает символы из ансамбля А={ai}, объем ансамбля К=64, энтропия источника Н(А)=3 бит/символ. Найти минимальное количество кодовых символов необходимых при кодировании символов источника в канале без шумов равномерным примитивным двоичным кодом и при оптимальном кодировании. Какое избыточное количество символов приходится тратить на один символ источника при использовании равномерного примитивного двоичного кода по сравнению с оптимальным кодом?
13. Производят АЦП первичного непрерывного сигнала. Число уровней квантования К=1024. Каждый уровень кодируется равномерным двоичным кодом. Найти число разрядов в кодовой комбинации, если избыточность кодаРк=0, если отдельные отсчеты сигнала независимы. Определить избыточность кода при увеличении числа разрядов на 4.
14. Источник сообщений выдает символы из ансамбля А={ai} (i=1, 2, 3, 4) с вероятностями Р(а1)=0,25; Р(а2)=0,15;Р(а3)=0,4; Р(а4)=0,2. Средняя длительность одного символа Тср=0,2с. Найти избыточность источника и избыточность равномерного кода, если скорость выдачи символов кодером Vк=15.
15. Источник без памяти с объемом алфавита К=3 выдает символы из ансамбля с вероятностями Р(а1)=0,28;Р(а2)=0,53 и Р(а3)=0,19. Найти избыточность источника и число символов кода на один символ источника n = Vк / Vи, при условии, что избыточность кода Рк=0.
16.Самолет противника с равной вероятностью может находится в одной из 250 зон. Какое количество информации будет получено при обнаружении самолета в одной из зон, если вероятность правильного обнаружения равна 0,9846.
17. Известно, что энтропия русского текста составляет приблизительно 0,5 .Какое количество информации получит читатель, прочтя произвольное слово из 6- ти букв.
18.Оператору РЛС известно, что самолет может с равной вероятностью находиться в одной из 16 зон воздушного пространства. какое количество информации он, получит, достоверно установив равномерное нахождения самолета в одной из 4- х зон. Ответ - 2 бит.
19.Определить полосу пропускания двоичного симметричного канала связи, обладающего пропускной способностью С = 900 бит / секунду, если известно, что в результате воздействия помех каждый из символов может быть равновероятно искажен, а вероятность правильного приема каждого символа равна 0.8.
5.3. РЕШЕНИЕ ЗАДАЧ
ЗАДАЧА 1.
1. Из условия fд2Fмакс fд12 МГц выбираем fд = 13,5 МГц.
2. k = log 2 m = log 2 256 = 8.
3. По формуле (1) вычислим: С = 13,58 = 108 Мбит/с.
4. По формуле (2) находим: fц = 0,5108 = 54 МГц.
ЗАДАЧА 2.
ЗАДАЧА 5.
1. Dc = 10lg(Рмакс / Рш) Рмакс = Рш10Dc / 10.
2. Из формулы (4) получим: .
3. Рш = GшFк = 10-410-3104 = 10-3 Вт или Рш = 1 мВт.
ЗАДАЧА 6.
1. По формуле (5) находим:
I(a1) = - log 2 0,25 = - lg0,25 / lg2 = 2 бит. I(a2) = - log 2 0,16 = 2,64 бит.
I(a3) = - log 2 0,36 = 1,47 бит. I(a4) = - log 2 0,23 = 2,12 бит.
2. По формуле (6) вычислим энтропию источника:
Н(А) = 0,252+0,162,64+0,361,47+0,232,12 = 1,941 бит/символ.
3. Из формулы (7) избыточность дискретного источника равна:
Ри = = 1-0,971 = 0,029.
ЗАДАЧА 7.
1. По формуле (5) находим:
I(a1) = - log 2 0,175 = - lg0,175 / lg2 = 2,51 бит.
Соответственно: I(a2) = 4,47 бит. I(a3) = 4,72 бит. I(a4) = 0,74 бит. I(a5) = 2,82 бит.
2. По формуле (6) вычислим энтропию источника:
Н(А) = 0,44+0,201+0,179+0,442+0,4 = 1,663 бит/символ.
3. Из формулы (7) избыточность дискретного источника равна:
Ри = = 1-0,716 = 0,283.
4. Производительность дискретного источника вычислим по формуле (8):
Н’(А) = Н(А) / Тср = 1,663 / 0,3 = 5,543 бит/с.
ЗАДАЧА 8.
1. Если источник без памяти выдает все символы с равной вероятностью, то избыточность дискретного источника Ри=0 и Н(А) = Нмакс(А) = log 2 К = log 2 12 = 3,585 бит/символ.
2. Производительность дискретного источника вычислим по формуле (8):
Н’(А) = Vи Н(А) = Н(А) / Тср = 3,585 / 0,15 = 23,9 бит/с.
3. Из формулы (8): Vи = = = 6,66 символов.
ЗАДАЧА 9.
1. Первоначальное количество посылок: .
2. Количество информации в одном символе: = 0,1 бит/символ.
3. Количество посылок после устранения избыточности: =107.
4. Время передачи: Т2 = n2 = 1010-3107=105 с.
5. Найдем отношение величин Т и n: и .
6. Избыточность источника: .
ЗАДАЧА 10.
1. Из формулы (9) получим [C - H’(A)] = = = 100.
2. Из условия равенства вероятностей ошибки следует равенство степеней: Т[C - H’(A)]1= = 3Т[C - H’(A)]2. Следовательно, запас пропускной способности канала [C - H’(A)] уменьшится в 3 раза.
ЗАДАЧА 11.
1. Из теоретических сведений (12) для равномерного примитивного двоичного кода выполняется условие 2n = K. Тогдаn = log 2 K / log 2 2 = log 2 10 = 3,32, т.к. n может быть только целым числом, то n = 4.
2. Из условия fд2Fмакс fд13 МГц выбираем fд = 13,5 МГц.
3. По формуле (1) вычислим: С = 13,54 = 54 Мбит/с.
4. По формуле (2) находим: fц = 0,554 = 27 МГц.
ЗАДАЧА 12.
1. Из теоретических сведений (12) при кодировании равномерным примитивным двоичным кодом выполняется условие 2n = K. Тогда n1 = log 2 K / log 2 2 = log 2 64 = 6.
2. По формуле (15) при оптимальном кодировании n2 = H(A) / log 2 2 = 3.
3. Количество избыточных символов при использовании равномерного примитивного двоичного кода: n = n1 – n2 = 6 – 3 = 3.
ЗАДАЧА 13.
1. Т.к. отдельные отсчеты сигнала независимы, то избыточность источника Ри=0, а т.к. и избыточность кода Рк=0, то из формулы (13): , где n = Vк / Vи, получим n = log 2 K / log 2 2 = log 2 1024 = 10.
2. По формуле (14) вычислим избыточность равномерного кода при увеличении числа разрядов на 4: = 1 - 0,714 = 0,285.
ЗАДАЧА 14.
1. По формуле (5) находим количество информации, содержащееся в каждом символе:
I(a1) = - log 2 0,25 = - lg0,25 / lg2 = 2 бит.
Соответственно: I(a2) = 2,73 бит. I(a3) = 1,32 бит. I(a4) = 2,32 бит.
2. По формуле (6) вычислим энтропию источника:
Н(А) = 0,252+0,152,73+0,41,32+0,22,32 = 1,904 бит/символ.
3. Из формулы (7) вычислим избыточность дискретного источника: Ри = = 0,048.
4. Из формулы (8) среднее количество символов, выдаваемое источником в единицу времени равно Vи = 1 / Тср = 1 / 0,2 = 5.
5. Избыточность кода вычислим по формуле (13): Рк = 1 - = 0,365.
ЗАДАЧА 15.
1. По формуле (5) находим количество информации, содержащееся в каждом символе:
I(a1) = - log 2 0,28 = - lg0,28 / lg2 = 1,83 бит.
Соответственно: I(a2) = 0,91 бит. I(a3) = 2,39 бит.
2. По формуле (6) вычислим энтропию источника:
Н(А) = 0,281,83+0,530,91+0,192,39 = 1,455 бит/символ.
3. Из формулы (7) вычислим избыточность дискретного источника: Ри = = 0,272.
4. Т.к. избыточность кода Рк=0, то из формулы (13) получим:
n = = 0,7281,585 = 1,15.
Задача 16
Выбор расчетной формулы
Определение Априорная вероятность появления самолета в одной из зон находится с использованием классического определения вероятности = 0.0004
Определим . при обнаружении самолета в одной из зон, правильность такого решения можно гарантировать с вероятностью 0,9846. Следовательно = 0,9846.
Определение количества информации
Ответ : I = 8 , бит,
Задача 17
Определяем максимальную энтропию одной буквы. Машинописный алфавит русского текста содержит 32 буквы. Энтропия максимальна, если все символы используемого алфавита равновероятны. Следовательно, для алфавита , объема
бит/ симв.
2. Определение количества информации в слове. в случае слова из m- = 6 , букв.
по условию ,бит / симв.
Тогда , бит
Ответ: 15 бит.
Определить пропускную способность двоичного симметричного канала связи с полосой пропускания и вероятностью ошибочного приема символа из – за помех = 0.3/
Решение:
Выбор исходной формулы
Ответ : 950 бит / сим.