Двоичное кодирование. Введение в информатику. Раздел 1

1.

Раздел 1. Введение в информатику
§6. Двоичное
кодирование

2.

Двоичное кодирование
Двоичный алфавит – алфавит, содержащий два символа.
Двоичное кодирование – представление информации с
помощью двоичного алфавита (двух знаков).
N: {+, -}, {·, -}, {истина, ложь}, {да, нет}, {0, 1}
N=2
Схема перевода
символа произвольного алфавита в двоичный код:
Символ
Порядковый
номер
Двоичный
код

3.

Двоичное кодирование
Если мощность исходного алфавита больше двух, то
для кодировки символа этого алфавита потребуется
несколько двоичных символов.
0
1
Уровень 1
0
1
1
0
Уровень 2
00
01
Порядковый номер символа
Двузначный двоичный код
10
11
1
2
3
4
00
01
10
11

4.

Двоичное кодирование
0
1
Уровень 1
0
1
1
0
Уровень 2
0
1
1
0
0
1
0
1
Уровень 3
000
001 010
011 100
111
101 110
Порядковый номер символа
1
2
3
4
5
6
7
8
Трехзначный двоичный код
000
001
010
011
100
101
110
111

5.

Двоичное кодирование
Разрядность двоичного кода – количество символов
в двоичном коде (длина двоичной цепочки).
Разрядность
двоичного кода
1
2
3
4
Количество
кодовых комбинаций
2
4
8
16 32 64 128 256 512 1024
N=
2i
5
6
7
8
9
10
N – количество кодовых комбинация (кодов)
i – разрядность двоичного кода
Любая информация может быть
представлена с помощью двоичного кода.

6.

Равномерные и неравномерные коды
Код
Равномерный
одинаковое число
символов в кодовых
комбинациях
однозначное
декодирование
Неравномерный
различное число
символов в кодовых
комбинациях
неоднозначное
декодирование
А
Б
В
Г
А
Б
В
Г
00
01
10
11
01
010
0
11
АБАВГ →
0001001011
0001001011 → АБАВГ
АБАВГ →
0101001011
0101001011 → ААВБГ

7.

Декодирование
Декодирование – это восстановление сообщения
из последовательности кодов.
Префиксный код – это код, в котором ни одно кодовое
слово не совпадает с началом другого кодового слова
(условие Фано). Сообщения декодируются однозначно.
А
Б
В
Г
Д
000
10
01
110
001
0
1
0
1100000100110
Г
А
В
Д
Б
0
А
1
В
1
1
0
Б
Д
Все кодовые слова заканчиваются на листьях дерева!
0
Г

8.

Декодирование
Постфиксный код – это код, в котором ни одно кодовое
слово не совпадает с окончанием другого кодового слова.
Сообщения декодируются однозначно (с конца!).
А
Б
В
Г
Д
000
01
10
001
100
0
1
0
011000110110
Б
Д
Г
Б
В
0
А
Б
В
Г
Д
01
010
001
11
101
0
Б
1
Г
Выполняются ли условия Фано?
А
1
010100111101
0
В
Д
АБАГД
АБВГА

9.

Автор
Подкопаева Мария Викторовна
учитель информатики
г. Санкт-Петербург
Презентации разработаны на основе УМК
Людмилы Леонидовны Босовой и
Константина Юрьевича Полякова