Теория информации лабы Бурькова. Теория информации
 Скачать 0.93 Mb.
|
|
4 Лабораторная работа № 4. Вычисление информационных потерь при передаче сообщений по каналам связи с шумами 4.1 Цель работы Освоение метода вычисления информационных потерь при передаче сообщений по каналам связи 4.2 Теоретические сведения Потери информации в каналах связи с шумами описывают с помощью условной энтропии и энтропии объединения. Если помех нет или их уровень низкий настолько, что они не могут уничтожить сигнал или имитировать сигнал в отсутствие передачи, то при передаче ai будет получен сигнал bj, соответствующий переданному сигналу. События А и В жестко связаны, при этом условная вероятность максимальна P(bj/ai) = 1, и условная энтропия Н(А/В) = 0, так как log P(bj/ai) = 0. Для этого случая количество информации в принятом ансамбле сообщений В, равно энтропии передаваемых сообщений ансамбля А I(B,A) = H(A) (4.1) Если уровень помех высок, то любой из принятых сигналов bj может соответствовать любому переданному сигналу ai, статистическая связь между переданными и принятыми сигналами отсутствует. Поэтому вероятности P(аi) и P(bj) являются вероятностями независимых событий и P(bj/ai) = P(bj); P(ai/bj) = P(ai). информации, содержащееся в В, относительно А равно нулю 27 I(A,B) = H(A) – H(A/B) = 0 (4.3) Информационные характеристики реальных каналов связи лежат между этими двумя предельными случаями. При этом потери информации при передаче k символов по данному каналу связи ) / ( B A kH I (4.4) Из-за помех часть информации искажается, однако между переданными и принятыми сообщениями существует статистическая взаимосвязь. Это позволяет описывать информационные характеристики реальных каналов связи с помощью энтропии объединения статистически зависимых событий. Так как H(A,В) = H(A) + H(В/А) = Н(В) + H(A/B), (4.5) то потери в канале связи могут быть учтены с помощью энтропии объединения следующим образом I(В,А) = H(A) + Н(В) - H(В,А). (4.6) Если использовать условную энтропию, то получим I(В,А) = H(A) - H(А/В) = Н(В) - H(В/А). (4.7) Для вычисления среднего количества информации, содержащегося в при- нятом ансамбле сообщений В относительно переданного ансамбля А в условиях действия помех, пользуются следующими выражениями Для вычислений часто применяют выражения 28 Для полного описания канала связи необходимо задать: канальную матрицу вида Р(ai/bj) и безусловные вероятности вида P(bj) или канальную матрицу вида Р(bj/ ai) и безусловные вероятности P(ai), или канальную матрицу вида Р(ai, bj). В последнем случае сумма значений матрицы по столбцам дает безусловные веро- Зная условные и безусловные вероятности, можно найти энтропии H(A), H(B), H(A/B), H(B/A). Если уровень помех настолько высок, что с равной вероят- ностью можно ожидать переход любого символа источника сообщения в произ- вольный символ первичного алфавита, то энтропия канала связи будет равна log m, а количество информации I = H(A) – log m < 0, значение I может отрица- тельной величиной, что означает, что канал связи вносит дезинформацию. Пример. Канал связи задан следующей канальной матрицей Вычислить среднее количество информации, которое переносится одним символом сообщения, если вероятности появления символов источника сообще- ний равны Р(а1) = 0,7; Р(а2) = 0,2; Р(а3) = 0,1. Определить информационные поте- ри при передаче сообщения из 400 символов алфавита а1, а2, а3. Вычислить коли- чество принятой информации. Решение. Энтропия источника сообщений 29 Общая условная энтропия Потери в канале связи ) / ( А В kH I = 400*0,473 = 189,5 бит. Энтропия приемника P(b1) + P(b2) + P(b3) = 1 H(B) = - (0,726 log 0,726 + 0,187 log 0,187 + 0,087 log 0,087) = = 1,094 бит/символ Среднее количество принятой информации I = k [H(B) – H(B/A)] = k H(B) - I = 400* 1,094 – 189,5 = 248,1 бит. 30 4.3 Задание Задача 1. Найти информационные потери в канале связи, заданном каналь- ной матрицей. Задача 2. Определить информационные потери в канале связи. Заданном матрицей, если символы алфавита встречаются в сообщениях с равной вероятно- стью. Задача 3. Определить среднее количество информации, содержащееся в принятом ансамбле сообщений относительно переданного, если сообщения со- ставлены из алфавита А, В, С. Вероятности появления букв алфавита на выходе источника сообщений Р(Ai) = P(Bi) = 0,25; P(Ci) = 0,5. Условные вероятности пар вида bi/ai следующие Р(А/А) = 0,97; Р(А/В) = 0,02; Р(А/С) = 0,01; Р(В/А) = 0,015; Р(В/В) = 0,97; Р(В/С) = 0,01; Р(С/А) = 0,015; Р(С/В) = 0,01; Р(С/С) = 0,98. Проверить правильность результата. Задача 4. Определить информационные потери в канале связи, заданном следующей канальной матрицей 31 Вероятности появления символов А, В, С, D на выходе источника сообще- ний соответственно равны РА = 0,4; РВ = РС =PD =0,2. Определить среднее коли- чество информации в принятых сообщениях относительно переданных. Задача 5. Используя энтропию объединения, определить количество ин- формации при передаче сообщений, построенных из алфавита 1, 2, 3, если апри- орные вероятности появления символов первичного алфавита равны между собой, а в результате действия помех 5% символов передаваемых сообщений могут с равной вероятностью перейти в любой другой символ данного алфавита. Задача 6. Определить количество информации в принятом ансамбле сооб- щений, если заданы условные вероятности перехода одного сигнала в другой и вероятности появления сигналов на выходе источника сообщений Рa = 0,2; Рb = 0,3; Рc = 0,5; Р(а 1 /а) = Р(b 1 /b) = P(c 1 /c) = 0,97; Р(b 1 /а) = Р(c 1 /a) = P(a 1 /b) = Р(c 1 /b) = Р(a 1 /c) = P(b 1 /c) = 0,015. 4.4 Контрольные вопросы 1 Чему равна энтропия объединения при независимости входящих в нее систем? 2 Как вычислить среднее количество информации в условиях помех? 3 Чему равна энтропия объединения при функциональной зависимости входящих в нее систем? 4 Чему равна взаимная информация между независимыми системами? 5 Может ли быть взаимная информация между двумя системами больше, чем наименьшая из энтропий этих систем? 6 Как вычислить информационные потери при передаче ее от одной систе- мы к другой? 7 Что необходимо для полного описания канала связи? 8 Какие характеристики канала связи можно определить из канальной мат- рицы? 32 5 Лабораторная работа № 5. Информационные характеристики каналов связи 5.1 Цель работы Вычисление скорости передачи информации и пропускной способности каналов связи 5.2 Теоретические сведения Основными характеристиками информационных систем являются такие по- нятия, как энтропия, скорость передачи информации, избыточность, пропускная способность канала связи. Для организации передачи информации по канала связи надо учитывать не только количество информации, но и обеспечение пере- дачи его в более короткий срок, не только хранение определенного количества, но и хранение с помощью минимального объема аппаратуры и т.д. Предположим, что по каналу связи передали за время Т количество ин- формации, которое равно Можно вычислить скорость передачи данных Скорость передачи данных представляет собой количество информации, приходящееся на одно сообщение. Если количество сообщений равно n, то ско- рость передачи n сообщений в секунду будет определяться В этом случае максимальная пропускная способность данного канала пред- ставляет собой с 33 Различают техническую скорость передачи и информационную скорость передачи информации. Технической скоростью передачи информации по каналу связи называется число символов, передаваемых в единицу времени Информационной скоростью передачи информации по каналу связи назы- вается среднее количество информации, которое передается в единицу времени Если сообщения являются равновероятными, составленные из равноверо- ятных взаимно независимых символов, то их информационная скорость равна Если символы в сообщении не равновероятны, то скорость определяется В случае, если символы имеют разную длительность Пропускная способность канала передачи информации характеризуется максимальной энтропией Для двоичного кода 1 Теорема Шеннона. Пусть есть источник информации с энтропией H(X ) и канал связи с пропу- скной способностью с, то если c > H(X), то всегда можно закодировать достаточ- 34 но длинное сообщение таким образом, что оно будет передано без задержек. Если c < H(X), то передача информации без задержек невозможна. Для всех практических каналов характерно наличие помех. На есть случаи, когда помехи малы, то вероятность искажения передаваемого сообщения равна нулю и можно считать, что все сигналы передаются верно. В этом случае среднее количество информации, переносимое одним символом Следовательно, пропускная способность канала без помех за единицу времени Реальные каналы характеризуются тем, что в них всегда есть помехи. Пропускная способность дискретного канала с помехами вычисляется 2 Теорема Шеннона. Для дан источник информации Х, энтропия равна H(X ), и пропускная способность равна с. Если H(X) > c , то справедливо, что при любом методе ко- дировании передача сообщений без задержек и искажений невозможна. Если H(X) < c , то любое достаточно длинное сообщение можно всегда закодировать так, что оно будет предано без задержек и искажений с вероятностью сколь угод- но близкой к единице. Пример 1. Дандискретный симметричный канал без памяти, на вход кото- рого поступают двоичные символы x1= 0; x2 = 1 c априорными вероятностями P(x1) = 0,85; P(x2) = 0,15. Переходные вероятности задаются соотношением где Р = 0,05 – это вероятность ошибки. Определить апостериорные вероятности. Решение. Ситуация в канале характеризуется схемой 35 Так как вероятность ошибки Р= 0,05, то вероятность правильного приема q = 1 - 0,05 = 0,95. В таком канале каждый кодовый символ может быть принят с ошибочной вероятностью Правильно переданная информация описывается 5.3 Задание Задача 1. Заданканал передачи информации без шума, по которому переда- ется сообщение из ансамбля: 36 Средняя длительность передачи одного элемента сообщения в канале Найти: пропускную способность канала; скорость передачи информации в канале без шума. Задача 2. Задан источник с вероятностями появления символов источника алфавита p(x1) = 0,5; p(x2) =0,25; p(x3) = 0,125; p(x4) = 0,125. Между соседни- ми символами имеются корреляционные связи, заданные матрицей вероятностей Определить избыточность источника при статистической независимости символов и избыточность при зависимости символов. Задача 3. Задан канал передачи информации, алфавит передаваемых сооб- щений содержит три символа с вероятностями p1 = 0,2; p2 = 0,7; p3 = 0,1. Чтобы передать информации по каналу без помех был применен равномерный двоич- ный код. Задана частота тактовых импульсов генератора 500 Гц. Найти пропуск- ную способность канала и скорость передачи информации. Задача 4. Заданканал связи, по которому передается три символа Матрица безусловных вероятностей источника сигналов 37 Канал связи характеризуется при p1 = 0,01; p2 = 0,02; p3 = 0,97 матрицей условных вероятностей Определить пропускную способность канала. Сравнить производительность источника и пропускную способность канала. Задача 5. По двоичному симметричному каналу связи с помехами переда- ются два символа с вероятностями p(x1) = 0,75 и p(x2) = 0,25. Из-за наличия по- мех вероятность правильного приема каждого из сигналов уменьшается до 0,875. Необходимо определить: производительность и избыточность источника; скорость передачи информации и пропускную способность канала связи. Задача 6. Определить скорость передачи информации для сообщений анг- лийского алфавита, при этом известно, что буквы e, t, o, n передаются за 10 мс каждая, а остальные за 20 мс каждая. При решении применить данные о распре- делении вероятностей букв в английском тексте. 5.4 Контрольные вопросы 1 Дать определения и пояснения технической и информационной скоро- сти передачи. Назвать единицы измерения и области применения этих понятий. 2 Дать определение информационной скорости для равновероятных со- общений. В чем заключается отличие от случая неравновероятных сообщений? 3 Дать определение пропускной способности канала без помех и с поме- хами, назвать единицы измерения, привести области применения этого понятия. 4 Сформулируйте и поясните первую и вторую теоремы Шеннона. В ка- ких задачах нашли применение эти теоремы? 38 6 Лабораторная работа № 6. Избыточность и оптимальное кодирование информации 6.1 Цель работы − Вычисление избыточности кодов. − Освоение приемов кодирования на основе кода Шеннона-Фано. 6.2 Теоретические сведения Преобразование информации из одной формы представления (знаковой системы) в другую называется кодированием. Все виды информации в вычислительных системах кодируются на машинном языке в виде последовательностей логических нуля и единицы. Двоичный код можно представить как два равновероятных состояния: «0» и «1». Количество информации любого двоичного символа равно одному биту. Два символа двоичного кода несут информацию в 2 бита, три цифры – в 3 бита и т.д. Количество информации в битах равно количеству цифр двоичного машинного кода. Восемь последовательных бит равно одному байту. В одном байте можно закодировать значение одного символа из 256 возможных. Используют умножительные приставки: Кодирование - это процесс преобразования информации в форму, удобную для передачи по определённому каналу связи. Декодирование – восстановление принятого сообщения из кодированного вида в вид доступный для потребителя. Одно и тоже сообщение можно закодировать различными способами. 39 Одной из основных проблем кодирования при передаче информации по ка- налам связи является оптимальный способкодирования, когда на передачу со- общения уходит минимальное время. Предположим, что на передачу каждого элементарного символа (0 или 1) затрачивается одно и тоже время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество символов. Например, пусть имеются буквы русского алфавита а, б, в, г,…+ промежу- ток между словами (-). Если не различать ь и ъ (как принято в телеграфии), то по- лучим 32 буквы. Требуется закодировать двоичным кодом буквы так, чтобы каж- дой букве соответствовала определенная комбинация символов 0 и 1 и, чтобы среднее число этих символов на букву текста было минимальным. 1 вариант. Не меняя порядка букв, пронумеровав их от 0 до 31 и перевести их в двоичную систему счисления, получим следующий код: В этом коде на каждую букву тратится ровно пять элементарных символов. Является ли этот код оптимальным? Модно ли составить другой код, при котором на одну букву в среднем приходится меньше элементарных символов? 2 вариант. Так как одни буквы встречаются часто (а, о, е), а другие (щ, э, ф) редко, то часто встречающиеся буквы целесообразно закодировать меньшим чис- лом символов, а реже встречающиеся – большим. Чтобы составить такой код нужно знать частоты букв русского алфавита (таблица 5.1) . Пользуясь такой таб- лицей, можно составить наиболее экономичный код на основе соображений, свя- занных с количеством информации. Код будет самым экономичным, когда каж- дый символ будет передавать максимальную информацию. 40 Рассмотрим элементарный символ, т.е. изображающий его сигнал, как физическую систему с двумя возможными состояниями 0 и 1. Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны. Таблица 5.1 - Статистические данные русского алфавита Метод Шеннона-Фано. Метод Шеннона-Фано является методом оптимального кодирования. Алго- ритм построения кода Шеннона-Фано состоит в том, что кодируемые символы (буквы) разделяются на две равновероятные подгруппы: для символов 1-й под- группы на втором месте ставится 0, а для 2-й подгруппы – 1 и т.д. Возможен дру- гой вариант, когда первая подгруппа соответствует «1», а вторая - «0». Главное, определить правило изначально и следовать ему на протяжении всего процесса кодирования. Необходимо взять первые шесть букв (от – до т). Сумма их вероятностей равна 0,498, на все остальные (от н до ф) приходится 0,502. Первые шесть букв будут иметь на первом месте 0, остальные 1. Далее снова первая группа делится на две приблизительные равновероятные подгруппы: (от – до щ) и (от е до т) и т.д. 41 Для всех букв первой подгруппы на втором месте ставится 0, а второй под- группы – 1. Процесс продолжается до тех пор, пока в каждой группе не останется ровно одна буква, которая и будет закодирована определенным двоичным кодом. Пример. Имеется алфавит символов и их вероятности, с которыми они встречаются в тексте. Построить таблицу кодов символов методом Шеннона- Фано. Закодировать сообщение «вилка» и раскодировать заданную последова- тельность кодов. Решение. Составим таблицу кодов для символов алфавита Сообщению «вилка» соответствует выходная последовательность кодов 01101100111100. Выходной последовательности кодов 100101111000 соответст- вует сообщение «лиса». Избыточность и оптимальное кодирование. Если энтропия источника сообщений не равна максимальной энтропии для алфавита с заданным количеством качественных признаков, то это означает, что сообщения данного источника могли нести большее количество информации. Аб- солютная недогруженность на символ такого источника Для определения количества «лишней» информации, которая заложена в структуре алфавита либо в природе кода, вводится понятие |