41678
Исследование источника дискретной информации
Лабораторная работа
Информатика, кибернетика и программирование
А при изпользлвании кода Хаффмена избыточность уменьшилась до 0,51%, из этого следует что избыточность при кодировании этим методом уменьшилась в 16 раз. А при использовании кода Шеннона – Фано избыточность уменьшилась всего в 5,5 раз. Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.
Русский
2013-10-24
165.5 KB
19 чел.
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уральский государственный университет путей сообщения
Кафедра «АТиС»
Лабораторная работа № 1
Исследование источника дискретной информации.
Проверил: Выполнил:
к.т.н., доцент студент ИТ-310
Волынская А.В. Коробицын А.В.
Екатеринбург
2013 г.
Исходное сообщение на выходе источника:
КОРОБИЦЫН_АНАТОЛИЙ_ВАДИМОВИЧ
Определить:
Длину сообщения Lа.
Объем алфавита mа.
Вероятности символов p(ai).
Энтропию источника .
Количество информации, содержащееся в каждом символе I(ai) и во всем сообщении Iсообщ.
Коэффициент избыточности источника информации rист.
Закодировать сообщение эффективными двоичными кодами Шеннона-Фано и Хаффмена.
Определить коэффициент избыточности после кодирования сообщения равномерным кодом rравн. и эффективными кодами rШ-Ф и rХаф.
Сделать выводы.
Определим длину сообщения: КОРОБИЦЫН_АНАТОЛИЙ_ВАДИМОВИЧ
La=28 символов
Определим объем алфавита:
Объем алфавита количество различных символов, из которых состоит сообщение.
ma=17 символов
Определим вероятности символов, количество информации в символе и во всем сообщении:
По следующим формулам
- вероятность символов
где n(ai) количество символов ai в сообщении;
Lа количество всех символов в сообщении;
Количество информации, содержащееся в символе, определяется по формуле Шеннона:
, бит
где p(ai) вероятности символов;
, бит. количество информации во всем сообщении.
Результаты вычислений
ai |
n(ai) |
p(ai), |
I(ai), бит |
К |
1 |
0,04 |
4,644 |
О |
4 |
0,14 |
2,836 |
Р |
1 |
0,04 |
4,644 |
Б |
1 |
0,04 |
4,644 |
И |
4 |
0,14 |
2,836 |
Ц |
1 |
0,04 |
4,644 |
Ы |
1 |
0,04 |
4,644 |
Н |
2 |
0,07 |
3,936 |
_ |
2 |
0,07 |
3,936 |
А |
3 |
0,11 |
3,184 |
Т |
1 |
0,04 |
4,644 |
Л |
1 |
0,04 |
4,644 |
Й |
1 |
0,04 |
4,644 |
В |
2 |
0,07 |
3,936 |
Д |
1 |
0,04 |
4,644 |
М |
1 |
0,04 |
4,644 |
Ч |
1 |
0,04 |
4,644 |
17 |
26 |
1,04 |
Определим энтропию источника:
Энтропией называют среднее количество информации приходящееся на один произвольный символ.
, бит/символ.
H(A)=3,75 бит/символ
Iсообщ=H(A)*La, ,бит
Iсообщ=105 бит
H max (A)=log 2 ma, бит/символ.
H max =4,0875 бит/символ
Коэффициент избыточности:
.
rист = 8,26 %
Закодируем сообщение кодом Шеннона Фано:
ai |
p(ai), |
код |
n(ai) |
n(1) |
n(0) |
|
О |
0,14 |
111 |
4 |
12 |
- |
|
И |
0,14 |
110 |
4 |
8 |
4 |
|
А |
0,11 |
101 |
3 |
6 |
3 |
|
Н |
0,07 |
1001 |
2 |
4 |
4 |
|
- |
0,07 |
1000 |
2 |
2 |
6 |
|
В |
0,07 |
0111 |
2 |
6 |
2 |
|
К |
0,04 |
01101 |
1 |
3 |
2 |
|
Р |
0,04 |
01100 |
1 |
2 |
3 |
|
Б |
0,04 |
0101 |
1 |
2 |
2 |
|
Ц |
0,04 |
01001 |
1 |
2 |
3 |
|
Ы |
0,04 |
01000 |
1 |
1 |
4 |
|
Т |
0,04 |
0011 |
1 |
2 |
2 |
|
Л |
0,04 |
00101 |
1 |
2 |
3 |
|
Й |
0,04 |
00100 |
1 |
1 |
4 |
|
Д |
0,04 |
0001 |
1 |
1 |
3 |
|
М |
0,04 |
00001 |
1 |
1 |
4 |
|
Ч |
0,04 |
00000 |
1 |
- |
5 |
|
55 |
54 |
109 |
L ш-ф = n(0) + n(1)
L ш-ф длина закодированного сообщения.
L ш-ф =109
p(1) = 55/109 = 0,505
p(0) = 54/109 = 0.495
Энтропия:
H ш-ф = 0.985 бит/символ
H ш-ф (K) = log 2 (m k) = = log 2 2 = 1 бит/символ
Избыточность:
r ш-ф = 1,5 %
Закодируем сообщение кодом Хаффмена:
Кодовое дерево приведено на следующей странице.
ai |
код |
n(ai) |
n(1) |
n(0) |
|
О |
100 |
4 |
4 |
8 |
|
И |
011 |
4 |
8 |
4 |
|
А |
001 |
3 |
3 |
6 |
|
Н |
1011 |
2 |
6 |
2 |
|
_ |
1010 |
2 |
4 |
4 |
|
В |
0101 |
2 |
4 |
4 |
|
К |
11111 |
1 |
5 |
- |
|
Р |
11110 |
1 |
4 |
1 |
|
Б |
11101 |
1 |
4 |
1 |
|
Ц |
11100 |
1 |
3 |
2 |
|
Ы |
11011 |
1 |
4 |
1 |
|
Т |
11010 |
1 |
3 |
2 |
|
Л |
11001 |
1 |
3 |
2 |
|
Й |
11000 |
1 |
2 |
3 |
|
Д |
0100 |
1 |
1 |
3 |
|
М |
0001 |
1 |
1 |
3 |
|
Ч |
0000 |
1 |
- |
4 |
|
59 |
50 |
109 |
L х = n(0) + n(1).
L х длина закодированного сообщения.
L х =109
p(1) = 59/109 = 0.5413
p(0) = 50/109 = 0.4587
Энтропия:
H x = 0.9949 бит/символ
H x (K) = log 2 (m k) = = log 2 2 = 1 бит/символ
Избыточность:
r x = 0,52 %
Вывод.
Избыточность источника без шифрования составила rист = 8,26 %.
При кодировании методом Шеннона Фано избыточность уменьшилась до 1,5 %.
А при изпользлвании кода Хаффмена избыточность уменьшилась до 0,51%, из этого следует что избыточность при кодировании этим методом уменьшилась в 16 раз.
А при использовании кода Шеннона Фано избыточность уменьшилась всего в 5,5 раз.
Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.
А также другие работы, которые могут Вас заинтересовать | |||
30329. | Распределение имен по типам склонения в индоевропейском языке | 85 KB | |
Семантический признак основание для выделения типов склонения. По древнейшим суффиксам уже выделялось 5 типов склонения а долгое о и у краткие подтипы: согласные es en et er у долгое = ъв. Изменения древнейшей системы склонения начались с общеславянского языка. | |||