Теория кодирования

Задание 1.

Найти энтропию фамилии студента и определить избыточность р текста фамилии, используя данные, приведенные в таблице 1.

Таблица 1 – Таблица вероятностей появления букв русского алфавита в тексте

[pic 1]

Решение:

Энтропия Н(х) определяется:

[pic 2]

Где pi- вероятности появления букв русского алфавита в тексте.

Значения вероятностей появления букв фамилии студента приведены в таблице 2.

Таблица 2- Таблица вероятностей появления букв фамилии студента

Н(Х)=[pic 3][pic 4]=0.044+0.273+0.224+0.248+0.224+0.248=1.261 бит

Избыточность фамилии р определяется:

Р=1-[pic 5][pic 6],

Где Нmax=5- максимальная энтропия русского алфавита при равномерном кодировании.

Получаем:

Р=1-[pic 7][pic 8]= 1-0,2522=0,74

Ответ: Н(Х)=1,261 бит, p= 0,74

Задание 2. Дано сообщение, составленное из 7 элементов. Вероятности появления шести элементов вычисляются по формуле [pic 9][pic 10] , где ni- i-я цифра шестизначном номере даты рождения студента.

Вероятность появление седьмого элемента должна удовлетворять условию нормировки. [pic 11][pic 12]

 Необходимо найти энтропию и избыточноть данного сообщения, а также произвести оптимальное кодирования элементов сообщения двоичным неравномерным кодом по методике Шеннона-Фано и построить кодовое дерево, оценить эффективность кодирования.

Решение:

Дата рождения: 140196

Соответственно n1=1, n2=4, n3=0, n4=1,n5=9,n6=6.

Вероятности появления элементов равны:

[pic 13][pic 14]0,142           [pic 15][pic 16] [pic 17][pic 18] 

[pic 19][pic 20] [pic 21][pic 22]         [pic 23][pic 24]   

[pic 25][pic 26]              [pic 27][pic 28]   

Вероятности появления седьмого элемента определяется из условия нормировки:

Р1+р2+…….р7=1

Отсюда:

р7=1-0,142-0,1-0,166-0,142-0,006-0,083=0,307

Значения вероятностей проявления цифп даты рождения студента приведены в таблице 3.

Таблица 3- Таблица вероятностей появления цифр даты рождения студента.

Энтропия данного сообщения определяется по фрмуле:

Н(Х)=[pic 29][pic 30]=0,399+0,332+0,430+0,399+0,243+0,298+0,523=2,624 бит.

Избыточность данного сообщения:

Р=1-[pic 31][pic 32],

где Нmax=log27=2.807- максимальная энтропия семи символов.

Р=1-[pic 33][pic 34] 

Оптимальное кодирование элементов сообщения двоичным неравномерным кодом по методике Шеннона-Фано приведено в таблице 4.

Таблица 4. Таблица кодирования элементов сообщения по методике Шеннона-Фано.