§ 5. Равномерное и неравномерное кодирование 1
2 Алфавит — это набор знаков, который используется в языке. Мощность алфавита — это количество знаков в алфавите. Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину. Неравномерный код — это код, в котором кодовые слова имеют различную длину. Двоичное кодировани е — это кодирование с помощью двух знаков. 1 бит — это одна двоичная цифра (один знак сообщения, записанного в двоичном коде).
3 Если алфавит языка состоит из M символов (имеет мощность M ), количество различных сообщений длиной L знаков равно N = M L Сколько возможных 7 -битовых двоичных кодов? возможных 5-буквеных слов в русском языке? возможных 3-буквеных слов в английском языке? 33 5 26 3 Для двоичного кода: N = 2 L 2 7
4 Сколько различных чисел можно закодировать в 8-битовой ячейке? различных чисел можно закодировать в 8-разрядной ячейке троичного компьютера (-1, 0, 1)? сколько битов нужно выделить для хранения номера спортсмена от 1 до 1000? 512 = 2 9 < 1000 2 10 = 1024 сколько битов нужно выделить для хранения температуры от –50 до 80 ? 128 = 2 7 < 131 2 8 = 256 10 8 2 8 3 8
5 Если в сообщении длиной L на позиции i может стоять один из M i символов, количество различных сообщений равно N = M 1 M 2 … M L Задача 1. Сколько существует различных сообщений длины 5 в алфавите {A, B, C, Х}, если буква «Х» может появляться только на первом или на последнем месте? 4 4 3 3 3 M 1 M 5 M 2 M 3 M 4 4 ∙ 3 ∙ 3 ∙ 3 ∙ 4 = 432
6 Задача 2. Сколько существует 5-значных десятичных чисел, все цифры в которых различны ? 9 6 9 8 7 M 1 M 5 M 2 M 3 M 4 9 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = 27216 Не может быть 0!
7 можно уменьшить длину закодированного сообщения не всегда однозначно декодируется А Г Р 00 0 1 10 ГАГАРА → 01 00 01 00 10 00 Равномерный код : А Г Р 0 01 1 0 ГАГАРА → 01 0 01 0 10 0 Неравномерный код : 12 бит 9 бит 010010100 → 01 0 01 0 10 0 → 0 10 0 10 10 0 ГАГАРА АРАРРА
8 Задача 3. Сколько существует двоичных кодов длиной от 2 до 5 битов? L = 2: N 2 = 2 2 = 4 Правило сложения! ! L = 3 : N 3 = 2 3 = 8 L = 4: N 4 = 2 4 = 16 L = 5 : N 5 = 2 5 = 32 N = N 2 + N 3 + N 4 + N 5 N = 4 + 8 + 16 + 32 = 60
9 Задача 4. Сколько существует различных 3-буквенных слов в алфавите { К, Р, О, Т }, в которых буква К встречается ровно 1 раз? К * * 1 ∙ 3 ∙ 3 = 9 1 3 3 К * * 3 ∙ 1 ∙ 3 = 9 К * * 3 ∙ 3 ∙ 1 = 9 9 + 9 + 9 = 27
10 Сколько существует в коде Морзе различных последовательностей из точек и тире, длина которых от 4 до 6 символов? Вася и Петя передают друг другу сообщения, используя синий, красный и зелёный фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении — 3 или 4, между сообщениями — паузы. Сколько различных сообщений могут передавать мальчики?
11 Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество битов потребуется для кодирования координат одной шахматной фигуры? Для кодирования значений температуры воздуха (целое число в интервале от –50 до 40) используется двоичный код. Какова минимальная длина двоичного кода? Дорожный светофор подаёт шесть видов сигналов (непрерывные красный, жёлтый и зелёный, мигающие жёлтый и зелёный, мигающие красный и жёлтый одновременно). Подряд записано 100 сигналов светофора. Определите информационный объём этого сообщения в битах.
12 Автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством битов, а каждый номер — одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 32 автомобильных номеров.
