73fa5d0ba3f715cb7ff1a7673b263ba9

1.

Равномерный и неравномерный коды. Условие
Фано. Измерение количества информации

2.

Основные понятия
Дискретизация – это представление непрерывного объекта в виде
множества отдельных элементов.
непрерывный
объект
дискретный
объект

3.

Основные понятия
Для того чтобы ввести данные в
компьютер, нужно:
✓ Выполнить дискретизацию:
o текст –> набор букв;
o рисунок –> набор пикселей….
✓ Каждому
элементу
(букве,
пикселю)
нужно
присвоить
двоичный код.

4.

Равномерный двоичный код
Перекодируем слово ПОТОП в двоичный алфавит, считая, что в тексте
есть только буквы «П», «Т» и «О» (т.е. в алфавите всего 3 символа).
О
000
П
010
кодовые слова
Т
100
010000100000010
Декодирование – это восстановление
исходного сообщения из кода.
Равномерный код обеспечивает однозначное декодирование, но сообщение
получается более длинным и на его передачу компьютерная система тратит
больше времени.

5.

Неравномерный двоичный код
Сократим длину сообщения, используя кодовые слова разной длины.
Знакам, которые встречаются в сообщении чаще, дадим более
короткие коды, а редко встречающимся – более длинные.
О
0
П
1
Т
10
101001
Сообщения, закодированные с помощью
неравномерного кода не всегда можно
декодировать однозначно.
101001
101001
101001
…

6.

Неравномерный двоичный код
Убедитесь в том, что вторая таблица позволяет однозначно
декодировать сообщение и сравните в чем разница между кодовыми
таблицами.
О
0
П
1
101001
Т
10
О
0
П
10
Т
11
10011010
Неравномерный код декодируется однозначно, если выполняется
условие Фано: ни одно кодовое слово не совпадает с началом другого
кодового слова.

7.

Дерево для двоичного кода
По каналу связи передаются сообщения, содержащие только семь букв: А, Б,
К, О, Т, Р, Я. Для передачи используется двоичный код,
удовлетворяющий
условию Фано. Кодовые слова для некоторых букв известны: А – 101, О – 11,
Я – 011. Какое наименьшее количество двоичных знаков потребуется для
кодирования слова КАТОК?
Условие Фано: для того, чтобы сообщение, записанное с помощью
неравномерного по длине кода, однозначно раскодировалось, достаточно,
чтобы никакой код не был началом другого (более длинного) кода.

8.

Дерево для двоичного кода
Буквы: А, Б, К, О, Т, Р, Я
А – 101, О – 11, Я – 011.
Наименьшее количество двоичных
знаков для кодирования слова
КАТОК
К
00
А
101
Т
100
О
11
Ответ: 12 двоичных знаков.
К
00
0
0
К
0
0
Б
1
Р
1
1
0
1 0
Я
1
Т
О
1
А

9.

Выполните задание
1.
По каналу связи передаются
сообщения,
содержащие
только семь букв: А, Б, Й, Л, М,
Т,
Ю.
Для
передачи
используется двоичный код,
удовлетворяющий
условию
Фано. Кодовые слова для
некоторых букв известны: Л –
010, Б – 011, Ю – 10. Какое
наименьшее
количество
двоичных знаков потребуется
для
кодирования
слова
АЛТАЙ?
2. Для
кодирования растрового
рисунка,
напечатанного
с использованием шести красок,
применили
неравномерный
двоичный код. Для кодирования
цветов используются кодовые
слова. Белый – 0, Зелёный – 11111,
Фиолетовый – 11110, Красный –
1110, Чёрный – 10.
Укажите
кратчайшее кодовое слово для
кодирования синего цвета, при
котором код будет
допускать
однозначное декодирование.

10.

Выполните задание
3. Для кодирования некоторой
последовательности,
состоящей из букв А, Б, В, Г,
решили
использовать
неравномерный
двоичный
код,
удовлетворяющий
условию Фано. Для буквы А
использовали кодовое слово
1, для буквы Б –
кодовое
слово
001.
Какова
наименьшая
возможная
суммарная
длина
всех
четырёх кодовых слов?
4. Для
кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К,
используется неравномерный двоичный код. Вот
этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К
– 11. Можно ли сократить для одной из букв длину
кодового слова? Коды остальных букв меняться
не должны.
Выберите правильный вариант ответа.
✓ кодовое слово для буквы Е можно сократить до 01;
✓ кодовое слово для буквы К можно сократить до 1;
✓ кодовое слово для буквы Н можно сократить до
10.

11.

Выполните задание
5. Для кодирования некоторой последовательности,
состоящей из букв А, Б, В, Г и Д,
используется неравномерный двоичный код, позволяющий однозначно декодировать
полученную двоичную последовательность. Вот этот код: А–11, Б–10, В–011, Г–000, Д–001.
Можно ли сократить для одной из букв длину кодового слова так,
чтобы код попрежнему можно было декодировать однозначно? Коды остальных букв меняться не
должны. Выберите правильный вариант ответа.
1) для буквы Г – 00
2) это невозможно
3) для буквы В – 01
4) для буквы Б – 1
6. По каналу связи передаются сообщения, содержащие только четыре буквы: А,
Б, В, Г;
для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А
и Б используются такие кодовые слова: А – 0; Б – 1011. Укажите сумму длин кратчайших
кодовых слов для букв В и Г,
при котором код будет
допускать однозначное
декодирование.

12.

Измерение количества информации
Двоичное кодирование – это кодирование с помощью двух знаков (0 и 1).
1 бит – это двоичная цифра (один знак сообщения, записанного в двоичном
коде).
Сколько бит информации содержится в сообщении:
L
N=M
10011010
i
N=2
i – количество разрядов двоичного кода,
N – количество различных сообщений.

13.

Выполните задание
7. На хранение целого числа отвели 12 битов.
закодировать таким образом.
Сколько различных чисел можно
8. Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное
количество битов потребуется для кодирования координат одной шахматной
фигуры?
9. Размер поля в международных шашках – 10×10 клеток.
Какое минимальное
количество битов потребуется для кодирования позиции одной шашки?

14.

Выполните задание
10. Ультразвуковой
датчик
измеряет
расстояние
до
препятствия
(в сантиметрах, в диапазоне от 0 до 10 м)
и сохраняет его в памяти
в двоичном коде в виде целого числа. Какова минимальная длина двоичного
кода, необходимая для кодирования результатов одного измерения?
11. Цифровой датчик
меряет температуру процессора (в диапазоне от 200
до 1400С) и сохраняет её в памяти в двоичном коде в виде целого числа.
a) Какова
минимальная
длина
двоичного
кода,
необходимая
для кодирования результатов одного измерения?
b) Сколько байтов потребуется для хранения результатов измерений
в течение часа?

15.

Выполните задание
12. Учёные ежедневно измеряют влажность воздуха в процентах и записывают
её в память компьютера в виде целого числа (от 0 до 100)
при помощи
минимально возможного количества битов. Определите информационный
объём результатов наблюдений за 90 дней в битах.
13. В базу данных каждый час записывается уровень автомобильных пробок в
городе (целое число от 1 до 10). Для хранения каждого значения используется
минимально возможное количество битов.
Сколько битов данных будет
записано:
a) за 2 дня;
b) за месяц.

16.

Выполните задание
14. В некоторой стране автомобильный номер длиной 6 знаков составляется из 26
букв латинского алфавита и десятичных цифр в любом порядке.
Каждый знак
кодируется одинаковым и минимально возможным количеством битов, каждый
номер – одинаковым и минимально возможным количеством байтов. Определите
объём памяти в байтах, необходимый для хранения 50 автомобильных номеров.
15. В базе данных необходимо хранить информацию о датах отгрузки товара.
Каждая такая запись содержит три поля: год (число от 2000 до 2100), номер
месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 31). Каждое поле
записывается отдельно от других полей с помощью минимально возможного
количества битов. Определите минимальное количество битов, необходимое
для кодирования одной записи.

17.

Выполните задание
16. В марафоне участвуют
500 спортсменов. Специальный сканер на финише
считывает номер участника и записывает его с помощью минимально
возможного количества битов. Каков информационный объём сообщения (в
байтах), записанного устройством, после того как финишировали 192
спортсмена?

18.

Е ДИНИЦЫ ИЗМЕРЕНИЯ
1 байт
(байт)
8 бит
23 бит
1 Кбайт
(килобайт)
1024 байт
210 байт
1 Мбайт
(мегабайт)
1024 Кбайт
220 байт
1 Гбайт
(гигабайт)
1024 Мбайт
230 байт
1 Тбайт
(терабайт)
1024 Гбайт
240 байт
1 Пбайт
(петабайт)
1024 Тбайт
250 байт
1 Эбайт
(экзабайт)
1024 Пбайт
260 байт
1 Збайт
(зеттабайт)
1024 Эбайт
270 байт
1 Йбайт
(йоттабайт)
1024 Збайт
280 байт

19.

Справочная информация
:8
бит
→
←
·8
: 1024
байт
→
←
· 1024
: 1024
Кбайт
→
←
· 1024
: 1024
Мбайт
→
←
· 1024
Гбайт

20.

Степени двоек
0
2 =1
6
212=4096
7
2 =64
1
2 =2
2 =128
213=8192
2
2 =4
28=256
214=16384
3
29=512
215=32768
4
210=1024
216=65536
5
211=2048
2 =8
2 =16
2 =32