Сообщение состоит из последовательности букв a b c вероятности которых не зависят
Обновлено: 05.07.2024
2. Пусть алфавит источника содержит шесть элементов , появляющихся с вероятностями Р(А)=0,15, Р(В)=0,1, Р(Б)=0,25, Р(Г)=0,13, Р(Д)=0,25, Р(Е)=0,12. Найти энтропию такого источника, среднее число символов на одну букву при кодировании методом Ш-Ф.
| блок | мы | все | учились | понемногу | чему | нибудь | и | как | - |
| вероятность | 0,37 | 0,13 | 0,125 | 0,08 | 0.06 | 0,052 | 0,023 | 0,11 | 0,05 |
Каково среднее число символов на знак?
6. Построить код Шеннона-Фано для системы из семи букв: A, B, C, D, E, F, G, вероятности появления которых соответственно 0,1, 0,2, 0,05, 0,3, 0,05, 0,15, 0,15. Определить среднее количество разрядов на одну букву. Декодировать этим кодом последовательность:
7. Провести эффективное кодирование ансамбля из восьми знаков (m=8), используя метод Шеннона-Фано.
Провести сравнительный анализ результатов решения двумя способами.
11. Задан алфавит из трех символов с вероятностями 0,75, 0,1, 0,15. Произвести кодирование отдельных букв и двухбуквенных сочетаний по методу Хаффмана. Для полученных кодов найти средние длины и коэффициенты оптимальности.
14. Символы источника
кодируются двоичными последовательностями:
a) 1, 01, 001, 0001; b) 1, 10, 100, 1000.
Являются ли данные коды префиксными, оптимальными? Какова средняя длина кодового слова?
15. Определить среднюю длину кодового слова и избыточность кода при кодировании по методу Фано, Шеннона, Хаффмана знаков ансамбля, приведенного ниже:
16. Источник информации задан вероятностной схемой:
Рассмотрены основные понятия и расчетные соотношения теории информации для практических занятий по темам: оценка энтропийных характеристик, оценка количества информации, оценка информационных характеристик систем и эффективное кодирование. Приводятся примеры решения типовых задач с использованием программного обеспечения Matchad 6.0 Plus. Дается набор типовых задач с ответами. Руководство предназначено для улучшения качества изучения курса "Теоретические основы информационно-измерительной техники" и других дисциплин, содержащих разделы теории информации. Подготовлено на кафедре автоматизированных систем научных исследований и экспериментов ТРТУ.
Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
52 комбинации знаков вероятность символы кода код й й й
0,64 0,16 0,16 0,04 1
1 01 001 000 0
1 0
1 0 Среднее количество символов в коде (или длина)
, Среднее число символов на знак знаменатель означает из скольких знаков состоит одна комбинация, что на 8% больше энтропии. Построим код Шенно-Фано для всевозможных трех знаковых комбинаций. комбинации знаков вероятность символы кода код й й й й й
0,512 0,128 0,128 0,128 0,032 0,032 0,032 0,008 1
1 011 010 001 00011 00010 00001 00000 0
1 1
0 0
1 0
1 1
0 0
1 0 Среднее количество символов в коде (или длина)
, Среднее число символов на знак знаменатель означает из скольких знаков состоит одна комбинация, что на 0,8% больше энтропии. Построим код Хаффмана для всевозможных трех знаковых комбинаций (рис. 2.1). Затем строим кодовое дерево (рис. 2.2) и составляем код комбинаций
1 011 010 001 00011 00010 00001 00000 Коды Шенно-Фано и Хаффмана совпали.
53 0,512 0,512 0,512 0,512 0,512 0,512 0,512 1
0,256 0,488 0.232 0,232 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0,128 0.064 0,104 0.04 0.04 0,032 0,032 0,032 0,032 0,032 0,008 рис Код Хаффмана
1 0 1 0,488 0,512 0 1
[1]
0,232 0,256 0 1 0 1 0,104 0,128 0,128 0,128 0 1
[001]
[010]
[011]
0,04 0,064 0 1 0 1 0,08 0,032 0,032 0,032
[ 00000]
[00001]
[00010]
[00011] Рис. 2.2 Кодовое дерево
54 Среднее количество символов в коде (или длина)
, Среднее число символов на знак
, что на 0,8% больше энтропии. Пример 2. Построить код Хаффмана для следующих данных А В С
D
E
F
G
H
0,25 0,22 0,13 0,11 0,1 0,09 0,07 0,03 Решение.
0,57 1 0,43 0,43 0,32 0,32 А 0,25 0,25 0,25 0,25 0,25 0,25
B 0,22 0,22 0,22 0,22 0,22 0,21 0.21 0,19 0,19
C 0,13 0,13 0,13 0,13
D 0,11 0,11 0,11
E 0,1 0,1 0.1 0,1
F 0,09 0,09
G 0,07
H На основании полученной таблицы можно построить кодовое дерево
(риc.2.3).
62 Пример 2. Построить макет кода Хэмминга и определить значения корректирующих разрядов для кодовой комбинации (
=4) 0101. Решение. По таблице №4 минимальное число контрольных символов
, а общее число символов
=
+
=7. По закону N=
, i=0,1,2…n определяются позиции проверочных символов 1,2 и 4, остальные позиции занимают информационные символы. Кодовая комбинация будет иметь вид С _ _ 0 _ 1 0 1. Для определения значения корректирующих разрядов составляются уравнения знак обозначает сложение по правилу четности) Следовательно, С=0100101.
Тогда избыточность D = 1 - H/Hmax = 1-1,84/2 = 0,08.
4.2. Закодируйте кодами Шеннона-Фано и Хаффмена алфавит, состоящий из пяти букв, - а1, а2, а3, а4, а5, вероятности появления которых Р = 0,4; 0,3; 0,15; 0,1; 0,05.
Построение кода Шеннона-Фано иллюстрируется на рис.У.1.
| Буква | Р | Разряды | Код | |
| а1 | 0,4 | - | - | - |
| а2 | 0,3 | - | - | |
| а3 | 0,15 | - | ||
| а4 | 0,1 | |||
| а5 | 0,05 |
Рис. У.1. Построение кода Шеннона-Фано
Определим, какова эффективность полученного кода. Для этого подсчитаем среднее число символов, приходящихся на букву:
Таким образом, средняя длина получилась достаточно близкой к предельному значению. Длина кода при равномерном кодировании k = 3 бита. Код Шеннона-Фано по сравнению с равномерным кодированием позволил сократить среднюю длину кодовых комбинаций для данного примера на 31,6%. D = 1- 2,05/3 = 0,316.
Рис.У.2. Построение кода Хаффмена.
Средняя длина кода kc = 2,05 бит совпала с длиной, полученной по методике Шеннона-Фано.
4.4. Определите количество элементов в кодовом слове, если известно общее число комбинаций N = 512, а основание кода 2.
4.5. Сколько двоичных чисел может быть представлено 7-разрядным кодом?
4.6. Дана совокупность символов х1, х2, х3, х4 со следующей статистикой соответственно: 0,28; 0,14; 0,48; 0,10. Закодируйте символы по методу Шеннона-Фано и определите эффективность кода.
Произведите кодирование отдельных букв и двухбуквенных сочетаний по методу Шеннона-Фано, сравните коды по их экономичности (количество информации, приходящееся на один символ) и избыточности.
4.9. Дана совокупность символов Х со следующей статистической схемой:
| X | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| P | 0,20 | 0,15 | 0,15 | 0,12 | 0,10 | 0,10 | 0,08 | 0,06 | 0,04 |
Тогда избыточность D = 1 - H/Hmax = 1-1,84/2 = 0,08.
4.2. Закодируйте кодами Шеннона-Фано и Хаффмена алфавит, состоящий из пяти букв, - а1, а2, а3, а4, а5, вероятности появления которых Р = 0,4; 0,3; 0,15; 0,1; 0,05.
Построение кода Шеннона-Фано иллюстрируется на рис.У.1.
| Буква | Р | Разряды | Код | |
| а1 | 0,4 | - | - | - |
| а2 | 0,3 | - | - | |
| а3 | 0,15 | - | ||
| а4 | 0,1 | |||
| а5 | 0,05 |
Рис. У.1. Построение кода Шеннона-Фано
Определим, какова эффективность полученного кода. Для этого подсчитаем среднее число символов, приходящихся на букву:
Таким образом, средняя длина получилась достаточно близкой к предельному значению. Длина кода при равномерном кодировании k = 3 бита. Код Шеннона-Фано по сравнению с равномерным кодированием позволил сократить среднюю длину кодовых комбинаций для данного примера на 31,6%. D = 1- 2,05/3 = 0,316.
Рис.У.2. Построение кода Хаффмена.
Средняя длина кода kc = 2,05 бит совпала с длиной, полученной по методике Шеннона-Фано.
4.4. Определите количество элементов в кодовом слове, если известно общее число комбинаций N = 512, а основание кода 2.
4.5. Сколько двоичных чисел может быть представлено 7-разрядным кодом?
4.6. Дана совокупность символов х1, х2, х3, х4 со следующей статистикой соответственно: 0,28; 0,14; 0,48; 0,10. Закодируйте символы по методу Шеннона-Фано и определите эффективность кода.
Произведите кодирование отдельных букв и двухбуквенных сочетаний по методу Шеннона-Фано, сравните коды по их экономичности (количество информации, приходящееся на один символ) и избыточности.
4.9. Дана совокупность символов Х со следующей статистической схемой:
| X | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 |
| P | 0,20 | 0,15 | 0,15 | 0,12 | 0,10 | 0,10 | 0,08 | 0,06 | 0,04 |
Решение. Предварительно определим единицы измерения количества энтропии и информации как и .
Составим матрицу, в которой вероятности выписываются в первый (основной) столбец в порядке их убывания, т.е.
Две последних вероятности P1 объединяются в одну вспомогательную вероятность Ps1:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P2 объединяются в одну вспомогательную вероятность Ps2:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P3 объединяются в одну вспомогательную вероятность Ps3:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P4 объединяются в одну вспомогательную вероятность Ps4:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P5 объединяются в одну вспомогательную вероятность Ps5:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P6 объединяются в одну вспомогательную вероятность Ps6:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P7 объединяются в одну вспомогательную вероятность Ps7:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
Две последних вероятности P8 объединяются в одну вспомогательную вероятность Ps8:
Вероятности снова располагаются в порядке их убывания в дополнительном столбце
На этом при получении дополнительного столбца с вероятностью, равной единице, процесс заканчивается. Матрица M, на основе которой проводится кодирование, принимает вид:
На основании данной таблицы строим кодовое дерево (рис.4.2.1), ветки которого соответствуют вероятностям, согласно матрице M.
Согласно таблице кодирования 4.1.1, длину кодовых комбинаций можно описать вектор-строкой
Средняя длина кодового слова в битах
На основании (4.2) минимально возможная средняя длина кодового слова равна энтропии источника, т.е.
Определить характеристики кода.
Для обычного двоичного кода: длина кодового слова , скорость передачи по каналу , избыточность и эффективность .
Для обычного двоичного кода характеристики соответственно будут: , , и .
Провести кодирование по алгоритму Шеннона-Фано отдельных букв и двухбуквенных сочетаний. Сравнить коды по их эффективности и избыточности.
Читайте также: