Презентация_по_информатике_Кодирование_и_декодирование_информации

1. Условие ФАНО

информации
Кодирование
и декодирование
Условие Фано

2.

Неравномерные коды. Прямое условие Фано
Прямое условие Фано. Неравномерный код может быть однозначно декодирован,
если никакой из кодов не совпадает с началом какого-либо другого, более
длинного кода. Такой код называют «префиксным».
Основные принципы построения дерева Фано:
1. Каждый узел дерева Фано имеет ровно две ветви, при этом одной ветви (например,
левой) сопоставляется 0, а другой ветви (правой) –1.
2. От каждого направления можно также рисовать только два направления: 0 (ноль) и 1
(единицу) и т.д. Получается структура похожая на дерево!
3. В конце каждой ветки ( т.е. на «листьях») располагаются буквы.
4. Если мы расположили на «листе» букву, то от этой ветки нельзя делать новые
ответвления.
5. Чем чаще встречается какой-либо символ, тем короче должен быть его код и тем
раньше этот символ надо поместить в дерево.
6. Для каждого символа код Фано получается последовательной записью всех нулей и
единиц по кратчайшему пути от вершины дерева к соответствующему символу.

3.

Задания: 1
2
3
4
5
6
7
8
ТЕОРИЯ
Задание 1. Для кодирования последовательности, состоящей из букв Л, М, Н, П, Р, решили
использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое
слово не является началом другого кодового слова. Использовали кодовые слова Л – 0, М – 100, Н –
101, П – 110, Р – 111. Постройте дерево Фано.
Ответ
0
Л
1
0
1
0
1
0
1
М
Н
П
Р

4.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 2. Для кодирования последовательности, состоящей из букв А, Б, В, Г, Д, решили
использовать неравномерный двоичный код, что никакое кодовое слово не является началом
другого кодового слова. На рисунке представлено дерево Фано. Запишите кодовые слова для букв
А, Б, В, Г, Д.
0
1
0
А
Ответ
1
0
0
1
Г
Д
Б
1
В
А
00
Б
10
В
Г
Д
11 010 011

5.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 3. Для кодирования последовательности, состоящей из букв В, Д, О, П, Р решили
использовать неравномерный двоичный код, что никакое кодовое слово не является началом
другого кодового слова. Известны кодовые слова: В — 01, Д — 11, О — 00, П — 100, Р — 101.
А) Запишите сумму длин всех пяти кодовых слов.
Ответ
12
Решение
Сумма длин всех пяти кодовых слов:
2+2+2+3+3=12
Б) Какую длину имеет код слова ВОДОПРОВОД?
Ответ
22
Решение
Буква В встречается 2 раза, О – 4 раза, Д - 2 раза,
Р – 1 раз, П – 1 раз. Сумма длин всех кодовых
слов слова ВОДОПРОВОД : 2*2+2*4+2*2+3+3=22
В
О
П
Р
Д
код
01
00
100
101
11
длина
2
2
3
3
2

6.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 4. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г;
для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В
используются такие кодовые слова: А – 0; Б – 111; В – 100.
Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное
декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Ответ
110 Решение
Дерево Фано имеет две свободные ветви. Кодовое слово
для буквы Г может быть 101 или 110. Наибольшее
числовое значение имеет код 110
(1102=610, 1012=510)
0
А
0
В
1
0
1
1
0
1
Б

7.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 5. По каналу связи передаются сообщения, содержащие только пять букв: П, И, Л, О, Т. Для
передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы И используется
кодовое слово 1; для буквы О используется кодовое слово 01.
Какова минимальная общая длина кодовых слов для всех пяти букв?
Надо построить дерево Фано с пятью ветками. Буквы
Ответ
Решение
И и О имеют заданные условием задачи кодовые
слова. Буквам П, Л, Т установим кодовые слова с
наименьшей длиной. Все ветви должны быть
0
1
закрыты. Тогда общая длина кодовых слов для всех
И пяти букв равна 4 + 1 + 3 + 2 + 4 = 14.
14
1
0
О
1
0
0
1
Т
П
Л
П
И
Л
О
Т
код
0001
1
001
01
0000
длина
4
1
3
2
4

8.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 6. По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, К, Р,
Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для
некоторых букв известны: К — 01, Р — 001. Для трёх оставшихся букв Б, Н и А кодовые слова
неизвестны. Какое количество двоичных знаков потребуется для кодирования слова БАРАБАН, если
известно, что оно закодировано минимально возможным количеством двоичных знаков?
16
Ответ
0
1
1
0
К
А
0
0
1
Н
Р
Решение
Буквы А и Б закодируем кодовыми словами 10 и 11
соответственно, поскольку они повторяются в слове
БАРАБАН чаще всего. Букву Н закодируем оставшимся
кодовым словом 000. Таким образом, всего
потребуется 2 · 5 + 3 · 2 = 16 двоичных знаков.
1
Б
А
Б
К
Р
Н
код
10
11
01
001
000
длина
2
2
2
3
3

9.

Задания: 1
2
3
4
5
6
7
8
ТЕОРИЯ
Задание 7. По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н,
Ч. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано. Кодовые
слова для некоторых букв известны: Н — 1111, З — 110. Для трёх оставшихся букв А, К и Ч кодовые
слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАЗАЧКА,
если известно, что оно закодировано минимально возможным количеством двоичных знаков?
14
Ответ
0
1
А
0
Решение
1
К 0
1
З 0 1
Ч
Н
Надо подобрать для оставшихся трёх букв А, К и Ч такие
кодовые слова, которые будут являться кратчайшими и
удовлетворять условию Фано.
Буква А встречается в слове КАЗАЧКА три раза, поэтому
закодируем её кодовым словом 0. Буква К встречается в
слове два раза, поэтому закодируем её кодовым словом 10.
Букву Ч закодируем кодовым словом 1110. Тогда для
кодирования слова КАЗАЧКА понадобится
2 · 2 + 1 · 3 + 3 + 4 = 14 двоичных знаков.

10.

Задания: 1
2
3
4
5
6
7
ТЕОРИЯ
8
Задание 8. Все заглавные буквы русского алфавита закодированы неравномерным двоичным
кодом, в котором никакое кодовое слово не является началом другого кодового слова. Кодовые
слова для некоторых букв известны: П — 00, Е — 01, Н — 110. Какое наименьшее количество
двоичных знаков может содержать код слова ПАНАМА?
15 Решение
Ответ
0
1
0
1
0
П
Е
А 0
1
1
Н 0 1
М
Кодовые слова для известных букв П — 00, Е — 01, Н — 110
разместим на ветвях дерева Фано.
Поскольку буква А повторяется в слове ПАНАМА три раза,
закодируем её кодовым словом 10. Букву М закодировать
кодовым словом длины 3 нельзя, поскольку не останется
кодовых слов для остальных букв алфавита, тогда
закодируем её кодовым словом 1110. Тогда наименьшее
количество двоичных знаков, которое может содержать код
слова ПАНАМА, равно 2 · 4 + 3 + 4 = 15.
П
А
Н
А
М
А
код
00
10
110
10
1110
10
длина
2
2
3
2
4
2