Ravnomerno-neravnomernoe_kodirovanie

Вспомним известное
Алфавит — это набор знаков, который используется в языке.
Мощность алфавита — это количество знаков в алфавите.
Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину.
Неравномерный код — это код, в котором кодовые слова имеют различную длину.
Двоичное кодирование — это кодирование с помощью двух знаков.
1 бит — это одна двоичная цифра (один знак сообщения, записанного в двоичном коде).

Количество возможных сообщений
Если алфавит языка состоит из M символов (имеет мощность M), количество различных сообщений длиной L знаков равно
N = M L
Сколько
возможных 7-битовых двоичных кодов?
возможных 5-буквеных слов в русском языке?
возможных 3-буквеных слов в английском языке?
335
263
Для двоичного кода: N = 2L
27

Количество возможных сообщений
Сколько
различных чисел можно закодировать в
8-битовой ячейке?
различных чисел можно закодировать в
8-разрядной ячейке троичного компьютера (-1, 0, 1)?
сколько битов нужно выделить для хранения номера спортсмена от 1 до 1000?
512 = 29 < 1000 ≤ 210 = 1024
сколько битов нужно выделить для хранения температуры от –50° до 80°?
128 = 27 < 131 ≤ 28 = 256
10
8
28
38

Правило умножения
Если в сообщении длиной L на позиции i может стоять один из Mi символов, количество различных сообщений равно
N = M1⋅ M2⋅ …⋅ ML
Задача 1. Сколько существует различных сообщений длины 5 в алфавите {A, B, C, Х}, если буква «Х» может появляться только на первом или на последнем месте?
4
4
3
3
3
M1
M5
M2
M3
M4
4 ∙ 3 ∙ 3 ∙ 3 ∙ 4 = 432

Правило умножения
Задача 2. Сколько существует 5-значных десятичных чисел, все цифры в которых различны?
9
6
9
8
7
M1
M5
M2
M3
M4
9 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = 27216
Не может быть 0!

Неравномерные коды
можно уменьшить длину закодированного сообщения
не всегда однозначно декодируется
ГАГАРА
→ 010001001000
Равномерный код:
ГАГАРА
→ 010010100
Неравномерный код:
12 бит
9 бит
010010100
→ 010010100
→ 010010100
ГАГАРА
АРАРРА

Правило сложения
Задача 3. Сколько существует двоичных кодов длиной от 2 до 5 битов?
L = 2: N2 = 22 = 4
L = 3: N3 = 23 = 8
L = 4: N4 = 24 = 16
L = 5: N5 = 25 = 32

Правила умножения и сложения
Задача 4. Сколько существует различных
3-буквенных слов в алфавите {К, Р, О, Т}, в которых буква К встречается ровно 1 раз?
К
*
*
1 ∙ 3 ∙ 3 = 9
1
3
3
К
*
*
3 ∙ 1 ∙ 3 = 9
К
*
*
3 ∙ 3 ∙ 1 = 9
9 + 9 + 9 = 27

Задачи
Сколько существует в коде Морзе различных последовательностей из точек и тире, длина которых от 4 до 6 символов?
Вася и Петя передают друг другу сообщения, используя синий, красный и зелёный фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении — 3 или 4, между сообщениями — паузы. Сколько различных сообщений могут передавать мальчики?

Задачи
Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество битов потребуется для кодирования координат одной шахматной фигуры?
Для кодирования значений температуры воздуха (целое число в интервале от –50 до 40) используется двоичный код. Какова минимальная длина двоичного кода?
Дорожный светофор подаёт шесть видов сигналов (непрерывные красный, жёлтый и зелёный, мигающие жёлтый и зелёный, мигающие красный и жёлтый одновременно). Подряд записано 100 сигналов светофора. Определите информационный объём этого сообщения в битах.