Кодирование и декодирование

1.

Кодирование и декодирование
Условие
Фано
информации
Сергей Глазков
Преподаватель информатики

2.

Основы кодирования
00

3.

Кодирование - это
перевод информации с одного языка на другой
(запись в иной системе символов, в другом в алфавите)
00

4.

Виды кодирования
1
Равномерное
Все символы кодируются кодами
одинаковой длины
2
Неравномерное
Разные символы могут
кодироваться кодами разной
длины
00

5.

Условие Фано
Прямое
Никакое кодовое слово не является
началом другого
Если в задаче написано, что код
допускает
однозначное
декодирование – это значит, что код
соответствует прямому условию Фано
Обратное
Никакое кодовое слово не является
концом другого
00

6.

Пример однозначного декодирования
> Сообщение: 100011010011100110
>
00

7.

Задача 1
По каналу связи передаются шифрованные сообщения, содержащие только
восемь букв: А, Б, В, Г, Д, Е, Ж, З. Для передачи используется неравномерный
двоичный код. Для шести букв используются кодовые слова.
В
00
Г
1000
Д
111
Е
1001
Ж
01
З
110
Какое наименьшее количество двоичных знаков потребуется для кодирования двух
оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А; Б.
00

8.

Решение задачи 1
СТАР
0 Т
1
1
0
0
1
В
Ж
0
1
1
0
З
0
Г
1
Е
Д
1
0
А
Б
00

9.

Задача 2
По каналу связи передаются сообщения, содержащие только буквы из набора: А,
И, К, Л, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию
Фано. Это условие обеспечивает возможность однозначной расшифровки
закодированных сообщений. Кодовые слова для некоторых букв известны: Л – 0, Н –
11. Для четырёх оставшихся букв А, И, К и Т кодовые слова неизвестны. Какое
количество двоичных знаков потребуется для кодирования слова КАЛИТКА, если
известно, что оно закодировано минимально возможным количеством двоичных
знаков?
00

10.

Решение задачи 2
СТАР
1
0 Т
Л
1
Н
0
0
0
А
1
И
1
1
0
К
К
4
А
4
Л
1
И
4
Т
4
К
4
А
4
=
25
СТАР
1
0 Т
Л
1
Н
0
1
0
А
1
0
Т
К
4
А
3
Л
1
И
5
Т
5
К
4
А
3
=
25
К
0
И
1
Т
00

11.

Задача 3
Все заглавные буквы русского алфавита закодированы неравномерным
двоичным кодом, в котором никакое кодовое слово не является началом другого
кодового слова. Это условие обеспечивает возможность однозначной расшифровки
закодированных сообщений. Известно, что все кодовые слова содержат не меньше
двух двоичных знаков, а слову БАРАН соответствует код 10011111011010. Какое
наименьшее количество двоичных знаков может содержать сообщение, кодирующее
слово РОБОТ?
00

12.

Решение задачи 3
Р
3
О
2
Б
2
О
2
Т
4
=
13
10
011
111
011
010
Б
А
Р
А
Н
СТАР
Т
1
0
0
1
Б
О
1
0
0
Н
1
Р
А
Т
АЛФАВИТ
00

13.

Задачи для самостоятельной работы
1)
Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, для
которого выполняется условие Фано: никакое кодовое слово не совпадает с началом другого
кодового слова. Известно, что слову ПАПУАС соответствует код 11101100010010. Какой код
соответствует слову СУП?
2)
По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для
передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А и Б
используются такие кодовые слова: А – 0; Б – 1011. Укажите сумму длин кратчайших кодовых
слов для букв В и Г, при котором код будет допускать однозначное декодирование.
3)
Алфавит передаваемых по каналу связи информационных сообщений содержит только девять
букв: А, Г, Д, И, О, П, Р, Т, У. Для передачи используется двоичный код, удовлетворяющий
условию однозначного декодирования. Кодовые слова некоторых букв известны: Д – 010, И –
10. Какое наименьшее количество двоичных разрядов потребуется для кодирования слова
АУДИОАППАРАТУРА?
00

14.

Спасибо за внимание!
00