Теория информации лабы Бурькова. Теория информации
 Скачать 0.93 Mb.
|
|
1.4 Контрольные вопросы 1 Дать определение понятия «информация», «информационные процессы». Назвать и дать определение видов информационных процессов. 2 Дать определение события с точки зрения теории информации. Какие со- бытия называются противоположными, достоверными, невозможными? 3 Дать определение полной группы событий. Какие события называются элементарными? 4 Дать определение вероятности, условной вероятности. Сформулировать теорему умножения вероятностей. 5 Пояснить смысл теоремы сложения вероятностей для несовместных со- бытий, для совместимых событий, пояснить следствия теоремы. 6 Привести теорему о полной вероятности. Пояснить применение данной теоремы в задачах. 7 Привести теорему умножения вероятностей. Пояснить формулу Байеса. 8 Что такое случайные дискретными величины, случайные непрерывные величины? 9 Дать определение понятия «закон распределения случайной величины»? Привести способы задания закона распределения. 10 Привести основные законы распределения. 11 Пояснить понятие «функция распределения случайной величины». На- зовите свойства функции распределения случайной величины. 12 Что такое математическое ожидание? Назовите свойства математическо- го ожидания. 13 Дать определение информационной системы. Назвать основные классы информационных систем. 13 2 Лабораторная работа № 2. Количественная оценка информации 2.1 Цель работы − Освоение навыков определения количества информации; − Определение энтропии непрерывных сообщений. 2.2 Теоретические сведения Важной задачей теории информации является количественная оценка пере- даваемых сообщений, которая называется количеством информации. Количество информации не отображает качественное содержание сообщения, а определяет меру его неопределенности. Если алфавит некоторого источника сообщений состоит из m знаков, каж- дый из которых может служить элементом сообщения, то количество N возмож- ных сообщений длины n равно числу перестановок с неограниченными повторе- ниями: N = m n (2.1) В том случае, если все N сообщений от источника будут равновероятными, получение определенного сообщения равносильно для него случайному выбору одного из N сообщений с вероятностью Р = 1/N. Чем больше N, тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение. Поэтому число N может служить мерой информации. С точки зрения тео- рии информации, мера информации должна быть пропорциональна длине сооб- щения. В качестве меры неопределенности выбора состояния источника с равно- вероятными состояниями принимают логарифм числа состояний: I = log 2 N = log 2 m n = n log 2 m (2.2) Эта логарифмическая функция характеризует количество информации. 14 Количество информации, приходящееся на один элемент сообщения (знак, букву), называется энтропией: Вычислительные системы основаны на элементах, имеющих два устойчи- вых состояния «0» и «1», поэтому выбирают основание логарифма равным двум. При этом единицей измерения количества информации, приходящейся на один элемент сообщения, является двоичная единица - бит. Двоичная единица (бит) является неопределенностью выбора из двух равновероятных событий. Так как из log 2 m = 1 следует m = 2, то ясно, что 1 бит - это количество ин- формации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1. Представленная оценка количества информации базируется на предположе- нии о том, что все знаки алфавита сообщения равновероятны. Для общего случая каждый из знаков появляется в сообщении с различной вероятностью. На основа- нии статистического анализа известно, что в сообщении длины n знак xi появля- ется ni раз, т.е. вероятность появления знака: Все знаки алфавита составляют полную систему случайных событий, поэтому: Формулы Шеннона для количества информации и энтропии: Свойства энтропии. 1) Энтропия Н - величина вещественная, неотрицательная и ограниченная, т.е. Н ≥ 0. 15 2) Энтропия равна нулю, если вероятность одного из элементов множества равно единице. 3) Энтропия максимальна, если все знаки алфавита равновероятны, т.е. Нmax = log m. (2.7) Избыточностью называется где - это случайная величина, N- число сообщений. Пример1. Вычислить количество информации, содержащееся в телевизи- онном сигнале, соответствующем одному кадру развертки. В кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В. Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней: n = 600. Количество элементов сообщения (знаков) в одной строке равно числу зна- чений, которое может принять амплитуда импульсов в строке m = 8. Количество информации в одной строке I = n log 8, а количество информации в кадре Iк =625*I = 625*600*log 8= 1,125*10 6 бит. Пример 2. Даны 27монет равного достоинства, среди которых есть одна фальшивая с меньшим весом. Вычислить сколько раз надо произвести взвешива- ние на равноплечих весах, чтобы найти фальшивую монету. Решение. Так как монеты внешне одинаковы, они представляют собой ис- точник с равновероятными состояниями, а общая неопределенность ансамбля, ха- рактеризующая его энтропию 16 H1 = log 2 27. Одно взвешивание способно прояснить неопределенность ансамбля насчи- тывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии). Все исходы являются равновероятными (нельзя заранее отдать предпочтение одному из них), поэтому результат одного взвешивания представляет источник с равновероятными состояниями, а его эн- тропия H2 = log 2 3 бит. Так как энтропия отвечает требованию аддитивности и при этом H1 = 3*H2 = 3* log 2 3, то для определения фальшивой монеты достаточно произвести три взвешивания. Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие. Аналогично, после второго взвеши- вания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальши- вую монету. 2.3 Задание Задача 1. Известно, что одно из k возможных сообщений, передаваемых равномерным двоичнымкодом, содержит 3 бита информации. Определить чему равно k. Задача 2. Сообщения передаются в восьмеричном алфавите m = 8, по 4 символа в каждом сообщении. Всего передано 10 сообщений. Найти количество информации в 10 сообщениях. Задача 3. Символы алфавита обладают двумя качественными признаками. а) Какое количество сообщений можно получить, комбинируя по 3, 4, 5 и 6 эле- 17 ментов в сообщении? б) Найти количество информации, приходящееся на один элемент указанных сообщений. Задача 4. Некий алфавит состоит из трех буквX, Y, Z. Задание: а) составить максимальное количество сообщений, комбинируя по три буквы; б) какое количество информации приходится на одно такое сообще- ние; в) определить количество информации на символ первичного алфавита. Задача 5. Устройство генерируетчетыре частоты f1, f2, f3, f4. В шифраторе частоты комбинируются по три частоты в кодовой комбинации. а) Определить максимальное количество комбинаций, составленных их этих частот? б) Опреде- лить количество информации на одну кодовую посылку? Задача 6. Дать описаниевсех возможныхспособов определения располо- жения шахматных фигур на доске. Определить количество информации для каж- дого способа. Задача 7. Какое количество информации приходится на одну букву алфави- та, состоящего из 16, 25, 32 букв? Задача 8. Алфавит состоит из букв А, В, С, D. Заданы вероятности встре- чаемости букв, они равны соответственно РА=РВ=0,25; РС=0,34; PD= 0,16. Най- ти количество информации, приходящееся на один символ сообщения, состав- ленного из такого алфавита. Задача 9. Задан алфавит,количество символов которого равно 5. Найти ко- личество информации, приходящееся на один символ сообщения, составленного из этого алфавита при условии: а) символы алфавита равновероятны; б) символы алфавита встречаются с вероятностями Р1=0,8; Р2=0,15; Р3= 0,03; Р4=0,015; Р5=0,005. Определить недогрузку символов во втором случае? Задача 10. Определить количество информации в каждом сообщении (ал- фавит русский). а) Ра, ра, ра, ра, ра, ра, ра. б) Соблюдай правила техники безо- пасности! Не стой под краном! в) Черемуха душистая весною расцвела и ветки золотистые, что кудри завила. 18 Задача 11. Чему равна вероятность появления комбинации 10110 при пере- даче пятизначных двоичных кодов? Чему равно среднее количество информации, приходящейся на одну комбинацию? (Р=1/32=0, 0312; I=5 бит). Задача 12. Сообщения составлены из равновероятного алфавита, содержа- щего m=128 качественных признаков. Чему равно количество символов в приня- том сообщении, если известно, что оно содержит 42 бита информации? Чему рав- на энтропия этого сообщения? (n=6; Н=7 бит/символ) 2.4 Контрольные вопросы 1 Дать определение понятия «количество информации», привести форму- лу и пояснить все составляющие этой формулы. 2 В чем отличие формулы количества информации для равновероятных событий и разновероятных? Пояснить на примере, привести формулы. 3 Дать определение энтропии. Записать и пояснить формулу Шеннона. 4 Перечислить и доказать основные свойства энтропии. 5 Записать и пояснить формулу Хартли. 6 Что является единицей измерения количества информации, энтропии? Назвать и пояснить все единицы измерения количества информации. 7 Приведите примеры, в которых энтропия сообщения равна нулю, при- нимает максимальное значение? 8 Дать определение и пояснить правило сложения энтропий для независи- мых источников? 9 Пояснить как определяется количество информации непрерывных со- общений. 10 Записать и пояснить формулу избыточности кода. 19 3 Лабораторная работа № 3. Условная энтропия и энтропия объединения 3.1 Цель работы − Вычисление условной энтропии; − Вычисление энтропии объединения. 3.2 Теоретические сведения Условная энтропия в теории информации применяется для определения взаимозависимости между символами кодируемого алфавита. Это необходимо с целью определения потерь информации при передаче данных по каналам связи. Для того, чтобы определить условную энтропию используются условные вероятности. Пусть при передаче n сообщений символ А появился m раз, символ В поя- вился l раз, а символ А совместно с символом В появился k раз, то вероятность появления символа А будет Р(А) = m/n, вероятность появления символа В будет Р(В) = l/n, вероятность совместного появления символов А и В будет Р(АВ) = k/n. Условная вероятность появления символа А относительно В и наоборот будет Р(А/В) = Р(АВ)/Р(В) = k/l, Р(B/A) = Р(АВ)/Р(A) = k/m.(3.1) Вероятность совместного появления символов А и В Р(АВ) = Р(В)*Р(А/В) = Р(А)*Р(В/А). (3.2) Условная энтропия символов А и В определяется выражением Индексы i и j выбраны для характеристики произвольного состояния источ- ника сообщений А и адресата В. 20 Различают общую условную энтропию и частную. Общая условная энтро- пия сообщения В относительно сообщения А характеризует количество инфор- мации, содержащееся в любом символе алфавита, и определяется усреднением по всем символам, т.е. по всем состояниям с учетом вероятности появления каждого из состояний, и равна сумме вероятностей появления символов алфавита, умно- женной на неопределенность, которая остается после того как адресат принял сигнал. Если передавать m сигналов А и ожидать получить m сигналов В, влияние помех в канале связи описывается канальной матрицей Вероятности, расположенные по диагонали, определяют правильный прием сообщений, а остальные – ложный. Если описывать канал связи со стороны ис- точника сообщений, то прохождение данного сигнала описывается распределени- ем условных вероятностей вида P(bj / ai). Для сигнала а1 это будет распределение вида P(b1/a1) + P(b2/a1) + … + P(bj /a1) +… + P(bm /a1). (3.5) Сумма вероятностей распределения всегда должна равняться единице. По- тери информации, которые приходятся на долю сигнала а1, описываются с помо- щью частной условной энтропии вида 21 Суммирование производится по j, так как i-тое состояние (в данном случае) остается постоянным. Чтобы учесть потери при передаче всех сигналов по данному каналу связи, надо просуммировать все частные условные энтропии. Для случая равновероят- ных появлений сигналов на выходе источника Для случая неравновероятного появления следует учесть вероятность появ- ления каждого символа. Тогда общая условная энтропия будет Если мы исследуем канал связи со стороны приемника сообщений, то с по- лучением сигнала bjпредполагаем, что был послан какой-то из сигналов a1, a2, … ai, … am. При этом канальная матрица будет иметь вид В этом случае единице должны равняться суммы условных вероятностей по столбцам канальной матрицы P(a1/bj) + P(a2/bj) + … + P(ai /bj) +… + P(am /bj) = 1 (3.9) Частная условная энтропия Общая условная энтропия 22 Наравне с выражением (3.8) для вычисления общей условной энтропии мо- жет быть использовано выражение Если заданы безусловные вероятности источника и канальная матрица, то можно вычислить энтропию приемника Если взаимозависимость связывает 3 элемента ai, aj, ak, то условная энтро- пия вычисляется по формуле Энтропия объединения используется для вычисления энтропии совместного появления статистически зависимых сообщений. Например, передав сто раз циф- ру 5 по каналу связи с помехами, эта цифра была принята 90 раз, цифра 6 была принята 8 раз, цифра 4 – 2 раза. Неопределенность возникновения комбинаций может быть описана с помощью энтропии объединения. Н(А, В) - неопределен- ность того, что будет послано А, а принято В. Для ансамблей переданных сооб- щений А и принятых сообщений В энтропия объединения представляет собой сумму вида Энтропия объединения и условная энтропия связаны соотношениями H(A,B) = H(A) + H(B/A) = H(B) + H(A/B) H(B/A) = H(A,B) - H(A); H(A/B) = H(А,B) - H(B) (3.15) Количество информации на символ сообщения, переданного по каналу свя- зи, в котором влияние помех описывается при помощи энтропии объединения, вычисляется так I(A,B) = H(A) + H(B) – H(B/A). (3.16) 23 3.3 Задание Задача 1. При передаче каждых 100 сообщений длиной по 5 символов в со- общении символ К встречается 50 раз, символ Т – 30 раз. Совместно К и Т встре- чаются 10 раз. Определить условные энтропии Н(К/Т) и Н(Т/К). Задача 2. При передаче текстовых сообщений наблюдения показали, что для слов со средней длиной в 6 букв на каждые 100 сообщений буква А встреча- ется 80 раз, буква В встречается 50 раз, буквы А и В вместе встречаются 10 раз. Определить условную энтропию появления А, если в слове присутствует В, и ус- ловную энтропию появления В, если в слове присутствует А. Задача 3. Определить общую условную энтропию сообщений, составлен- ных из алфавита А, В, если вероятности появления символов в сообщении равны РА=0,6; РВ=0,4. Условные вероятности переходов одного символа в другой равны Р(В/А)=0,15; Р(А/В)= 0,1. Задача 4. В одной корзине два яблока и одна груша, в другой три яблока и одна груша, в третьей – два яблока и две груши. Определить полную условную энтропию возможности вытащить яблоко из любой корзины. Задача 5. Влияние помех в канале связи описывается следующим распреде- лением условных вероятностей Вычислить полную условную энтропию сообщений, передаваемых по дан- ному каналу связи: а) при равновероятном появлении символов в сообщении; б) при вероятностях Р(а1) = 0,7; Р(а2) = 0,2; Р(а3) = 0,1. Задача 6. а)Определить частные условные энтропии для каждого символа алфавита а1, а2, а3, а4, если канал связи для передачи сообщений описывается следующей канальной матрицей 24 б) Найти общую условную энтропию для сообщений, передаваемых по ка- налу связи, описанному приведенной выше канальной матрицей, если символы источника равновероятны; в) Найти общую условную энтропию для сообщений, передаваемых по ка- налу связи, если распределение вероятностей появления символов на выходе ис- точника сообщений имеет вид Р(а1) = 0,15; Р(а2) = 0,32; Р(а3) = 0,25; Р(а4) = 0,28. Задача 7. Определить общую условную энтропию сообщений, передавае- мых по каналу связи, описанному канальной матрицей Символы алфавита равновероятны. Задача 8. Определить энтропию приемника сообщений, если вероятности появления символов на выходе источника сообщений равны Р(а1) = 0,5; Р(а2) = 0,3; Р(а3) = 0,2 и канальная матрица имеет вид Задача 9. Определить энтропию источника сообщений, если вероятности появления символов на входе приемника сообщений равны Р(b1) = 0,1; Р(b2) = 0,3; Р(b3) = 0,4; Р(b4) = 0,2 и канальная матрица имеет вид 25 Задача 10. Задана матрица вероятностей системы, объединенной в одну систему из двух взаимозависимых систем А и В Определить полные условные энтропии Н(В/А) и Н(А/В). 3.4 Контрольные вопросы 1 Дать определение условной энтропии. Пояснить для чего она применяет- ся в теории информации. 2 Что такое общая и частная условная энтропия? 3 Какие формулы используются для расчета условной энтропии? 4 Что такое канальная матрица и как она используется при решении задач в теории информации? 5 Пояснить, что такое энтропия объединения и для чего она используется. 6 Привести определение понятия «полной средней взаимной информация». 7 Пояснить, что подразумевают под дискретными системами передачи ин- формации. 8 Дать определение непрерывных систем передачи информации. Привести их характеристику. 9 Пояснить способ определения условной энтропии для непрерывной сис- темы передачи сообщений. 10 Какие отличия есть при вычислении условной энтропии при равноверо- ятном и неравновероятном появлении сигналов сообщения? |