СибГУТИ Контрольная работа Теория информации скачать бесплатно
1. Вычислить энтропию Шеннона для символов ФИО.
Л У К А Ш Е В И Ч С Р Г Й Т О Ь
Ч 2 1 1 3 1 3 2 2 2 1 1 1 1 1 1 1
В 0,08 0,04 0,04 0,13 0,04 0,13 0,08 0,08 0,08 0,04 0,04 0,04 0,04 0,04 0,04 0,04
2. Построить код Хаффмана для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
Л У К А Ш Е В И Ч С Р Г Й Т О Ь
Ч 2 1 1 3 1 3 2 2 2 1 1 1 1 1 1 1
В 0,08 0,04 0,04 0,13 0,04 0,13 0,08 0,08 0,08 0,04 0,04 0,04 0,04 0,04 0,04 0,04
Упорядочим по вероятностям:
У К Ш С Р Г Й Т О Ь Л В И Ч А Е
В 0,04 0,04 0,04 0,04 0,04 0,04 0,04 0,04 0,04 0,04 0,08 0,08 0,08 0,08 0,13 0,13
Буква Код
А 011
Е 100
Ч 010
В 1010
И 1011
Л 1101
О 0000
Ь 0001
Й 0010
Т 0011
У 11000
К 11001
Р 11100
Г 11101
Ш 11110
С 11111
Средняя длина кодового слова построенного кода:
3. Построить код Фано для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.
Буква Вероятность Кодовое слово Длина
А 0,13 0 0 0 3
Е 0,13 0 0 1 3
Ч 0,08 0 1 0 3
В 0,08 0 1 1 0 4
И 0,08 0 1 1 1 4
Л 0,08 1 0 0 0 4
О 0,04 1 0 0 1 4
Ь 0,04 1 0 1 0 4
Й 0,04 1 0 1 1 0 5
Т 0,04 1 0 1 1 1 5
У 0,04 1 1 0 0 4
К 0,04 1 1 0 1 0 5
Р 0,04 1 1 0 1 1 5
Г 0,04 1 1 1 0 4
Ш 0,04 1 1 1 1 0 5
С 0,04 1 1 1 1 1 5
Средняя длина кодового слова построенного кода:
4. Построить код Шеннона для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.
Буква Pi Qi-1 Li Кодовое слово
А 1/23≤0,13<1/22 0 3 000
Е 1/23≤0,13<1/22 0,13 3 001
Ч 1/24≤0,08<1/23 0,26 4 0100
В 1/24≤0,08<1/23 0,34 4 0101
И 1/24≤0,08<1/23 0,42 4 0110
Л 1/24≤0,08<1/23 0,50 4 1000
О 1/25≤0,04<1/24 0,58 5 10010
Ь 1/25≤0,04<1/24 0,62 5 10011
Й 1/25≤0,04<1/24 0,66 5 10101
Т 1/25≤0,04<1/24 0,70 5 10110
У 1/25≤0,04<1/24 0,74 5 10111
К 1/25≤0,04<1/24 0,78 5 11000
Р 1/25≤0,04<1/24 0,82 5 11010
Г 1/25≤0,04<1/24 0,86 5 11011
Ш 1/25≤0,04<1/24 0,90 5 11100
С 1/25≤0,04<1/24 0,94 5 11110
Средняя длина кодового слова построенного кода:
5. Построить код Гилберта-Мура для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.
Буква Pi Qi Li Кодовое слово
А 1/23≤0,13<1/22 0,065 4 0001
Е 1/23≤0,13<1/22 0,195 4 0011
Ч 1/24≤0,08<1/23 0,30 5 01001
В 1/24≤0,08<1/23 0,38 5 01100
И 1/24≤0,08<1/23 0,46 5 01110
Л 1/24≤0,08<1/23 0,54 5 10001
О 1/25≤0,04<1/24 0,60 6 100110
Ь 1/25≤0,04<1/24 0,64 6 101000
Й 1/25≤0,04<1/24 0,68 6 101011
Т 1/25≤0,04<1/24 0,72 6 101110
У 1/25≤0,04<1/24 0,76 6 110000
К 1/25≤0,04<1/24 0,80 6 110011
Р 1/25≤0,04<1/24 0,84 6 110101
Г 1/25≤0,04<1/24 0,88 6 111000
Ш 1/25≤0,04<1/24 0,92 6 111010
С 1/25≤0,04<1/24 0,96 6 111101
Средняя длина кодового слова построенного кода:
6. Сравнить между собой энтропию Шеннона, вычисленную в п.1, и величины средних длин кодового слова для построенных кодов.
Энтропия Шеннона равна 3,79.
Средняя длина кодового слова для кода Хаффмана равна 3,82. Это значение немного больше энтропии Шеннона, что соответствует теоретическим оценкам.
Средняя длина кодового слова для кода Фано равна 3,82. Это значение равно средней длине кодового слова для кода Хаффмана. И разность средней длины кодового слова и энтропии Шеннона меньше единицы. Все это соответствует теоретическим оценкам.
Средняя длина кодового слова для кода Шеннона равна 4,06. Это значение больше средней длины кодового слова для кода Фано. И разность средней длины кодового слова и энтропии Шеннона меньше единицы. Все это соответствует теоретическим оценкам.
Средняя длина кодового слова для кода Гилберта-Мура равна 5,04. Это значение больше средней длины кодового слова для кода Шеннона. И разность средней длины кодового слова и энтропии Шеннона меньше двух. Все это соответствует теоретическим оценкам.
