labrab4-5_Kuznetsovoy_Olgi_gr_6231K
.docxГУАП
КАФЕДРА № 43
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
Старший преподаватель __________________________________ Соколовская М.В.
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ
КОДИРОВАНИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ МЕТОДОМ ШЕННОНА-ФАНО И МЕТОДОМ Д.ХАФФМАНА
по дисциплине: ИНФОРМАТИКА
РАБОТУ ВЫПОЛНИЛА СТУДЕНТКА ГР. 6231К _________________________________________ Кузнецова О.Ю.
Санкт-Петербург 2012
Цель работы: освоить метод построения кодов дискретного источника информации, используя конструктивный метод, предложенный К.Шенноном и Н.Фано и методику Д.Хаффмана. На примере показать однозначность раскодирования имеющегося сообщения.
При кодировании дискретных источников информации нужно уменьшить избыточность, то есть количество символов для передачи сообщения по каналу связи. Тогда информация будет передаваться быстрее. Потребуется меньше памяти для хранения этой информации.
In order to code the discrete sources of information it is necessary to reduce redundancy, or the amount of symbols needed for its transmission by the channel. Then the information is transmitted rapidly. Less memory is needed to keep this information.
Любое сообщения можно передать, используя ноль и единицу. Тогда кодовое слово будет состоять из последовательностей нулей и единиц.
Any message can be transmitted by 0 and 1. Then a codeword is a combination of 0 and 1.
Если алфавит A состоит из N символов, то для такого кодирования необходимо слово разрядностью n, которая определяется
If the alphabet A consists of N symbols, a word of n length will be needed.
n = log2 N .
Это справедливо для стандартных кодовых таблиц.
It is true for standard code tables.
В нашей работе было 50 символов. Это меньше, чем 256. Удобнее будет другая таблица кодирования, которая позволит сжать информацию. В ней любой символ будет кодироваться меньшим количеством нулей и единиц. При кодировании не будет передаваться избыточная информация. У более вероятных символов кодовое слово будет короче, чем у менее вероятных символов. Такое кодирование называется эффективным.
We have had 50 symbols in our previous lab. It is less than 256 symbols. A different code table is easier to use, letting compress the information. Any symbol of its would be coded by less amount of 0 and 1. Redundant information is not transmitted. A codeword is shorter for more possible symbols than for less possible ones. Such coding is called effective.
Оно создано на основной теореме Шеннона, которая гласит, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины.
It’s based on the main Shannon theory, which says that the messages which are composed of the letters of some alphabet can be coded so that an average number of binary symbols per a letter will be close to the entropy of the source but no less than this figure.
К.Шеннон и Н.Фано показали, как это можно сделать на практике и то, что получилось, назвали кодом Шеннона-Фано.
C.Shannon and N.Fano showed how to do it and called the result ‘the Shannon-Fano code’.
Сначала копируются символы из лабораторной работы №3 и значения их вероятностей. Они сортируются от самого большого к самому маленькому. Сумма всех вероятностей равна одному. Вероятности делятся на две группы, чтобы суммы вероятностей в каждой были приблизительно равны. Символам верхней группы приписывается единица, символам нижней – ноль. Всё повторяется нужное количество раз, пока в каждой подгруппе не останется по одному символу.
Firstly symbols and probabilities from lab#3 are copied. They are sorted from the biggest to the smallest. The summary probability makes one. The probabilities are divided into two groups so that the sums of probabilities in each group are almost equal. The symbols of upper group are given 1, the symbols of lower group are given 0. These actions are repeated till one symbol rests in each subgroup.
|
Cимвол |
Вероятности символа (pi) |
Кодовые комбинации |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
|
0,121390 |
111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
о |
0,085748 |
110 |
|
|
|
|
|
|
|
|
|
|
|
||
|
е |
0,072757 |
1011 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
и |
0,071939 |
1010 |
|
|
|
|
|
|
|
|
|
|
|||
|
р |
0,071803 |
1001 |
|
|
|
|
|
|
|
|
|
|
|
||
|
а |
0,057335 |
1000 |
|
|
|
|
|
|
|
|
|
|
|||
|
н |
0,056284 |
0111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
т |
0,054408 |
0110 |
|
|
|
|
|
|
|
|
|
|
|||
|
с |
0,046073 |
01011 |
|
|
|
|
|
|
|
|
|
|
|
||
|
в |
0,034922 |
01010 |
|
|
|
|
|
|
|
|
|
||||
|
л |
0,028758 |
01001 |
|
|
|
|
|
|
|
|
|
|
|||
|
д |
0,027480 |
01000 |
|
|
|
|
|
|
|
|
|
||||
|
п |
0,027051 |
00111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
м |
0,026108 |
001101 |
|
|
|
|
|
|
|
|
|
||||
|
к |
0,023965 |
001100 |
|
|
|
|
|
|
|
|
|||||
|
я |
0,019033 |
00101 |
|
|
|
|
|
|
|
|
|
|
|||
|
ы |
0,017067 |
001001 |
|
|
|
|
|
|
|
|
|
||||
|
у |
0,016390 |
001000 |
|
|
|
|
|
|
|
|
|||||
|
з |
0,014701 |
000111 |
|
|
|
|
|
|
|
|
|
|
|
||
|
ь |
0,011817 |
0001101 |
|
|
|
|
|
|
|
|
|||||
|
б |
0,011410 |
0001100 |
|
|
|
|
|
|
|
||||||
|
х |
0,009689 |
000101 |
|
|
|
|
|
|
|
|
|
||||
|
г |
0,009671 |
0001001 |
|
|
|
|
|
|
|
|
|||||
|
, |
0,009646 |
0001000 |
|
|
|
|
|
|
|
||||||
|
. |
0,009383 |
0000111 |
|
|
|
|
|
|
|
|
|
|
|||
|
й |
0,008958 |
00001101 |
|
|
|
|
|
|
|
||||||
|
ц |
0,008418 |
00001100 |
|
|
|
|
|
|
|||||||
|
ч |
0,008415 |
0000101 |
|
|
|
|
|
|
|
|
|||||
|
ж |
0,007014 |
00001001 |
|
|
|
|
|
|
|
||||||
|
ю |
0,006067 |
00001000 |
|
|
|
|
|
|
|||||||
|
ф |
0,004378 |
00000111 |
|
|
|
|
|
|
|
|
|
||||
|
щ |
0,004173 |
00000110 |
|
|
|
|
|
|
|||||||
|
- |
0,002963 |
00000101 |
|
|
|
|
|
|
|
||||||
|
ш |
0,002056 |
00000100 |
|
|
|
|
|
|
|||||||
|
э |
0,001995 |
000000111 |
|
|
|
|
|
|
|
|
|||||
|
( |
0,001944 |
000000110 |
|
|
|
|
|
||||||||
|
; |
0,001455 |
000000101 |
|
|
|
|
|
|
|||||||
|
2 |
0,001397 |
000000100 |
|
|
|
|
|
||||||||
|
1 |
0,000943 |
000000011 |
|
|
|
|
|
|
|
||||||
|
0 |
0,000875 |
0000000101 |
|
|
|
|
|
||||||||
|
: |
0,000807 |
0000000100 |
|
|
|
|
|||||||||
|
4 |
0,000677 |
0000000011 |
|
|
|
|
|
|
|||||||
|
3 |
0,000670 |
00000000101 |
|
|
|
|
|||||||||
|
5 |
0,000515 |
00000000100 |
|
|
|
||||||||||
|
9 |
0,000457 |
00000000011 |
|
|
|
|
|
||||||||
|
ъ |
0,000389 |
00000000010 |
|
|
|
||||||||||
|
6 |
0,000263 |
00000000001 |
|
|
|
|
|||||||||
|
8 |
0,000194 |
000000000001 |
|
|
|
||||||||||
|
7 |
0,000151 |
0000000000001 |
|
|
|||||||||||
|
ё |
0,000000 |
0000000000000 |
|