1 Кодирование информации § 5. Язык и алфавит § 6. Кодирование § 7. Дискретность § 8. Алфавитный подход к измерению количества информации
§ 5. Язык и алфавит 2
3 Язык — это система знаков, используемая для хранения, передачи и обработки информации. Египетское письмо Иероглифы (Китай) рука солнце дом луна кобра дождь лев гора вода лошадь Иероглифы:
4 Алфавит — это набор знаков, который используется в языке. Мощность алфавита — это количество знаков в алфавите. АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ 0123456789.,;?!-:… «» () мощность 56 Слово — это последовательность символов алфавита, которая используется как самостоятельная единица и имеет определённое значение.
5 Сообщение — это любая последовательность символов некоторого алфавита. Пример: алфавит @ # $ %. Сообщения длины 1: @ # $ %. Сколько сообщений длины M ? ? Сообщения длины 2 : @ @ @ # @ $ @ % # @ # # # $ # % $ @ $ # $ $ $ % % @ % # % $ % % всего 16 всего 4
6 Если алфавит языка состоит из N символов (имеет мощность N ), количество различных сообщений длиной L знаков равно Q = N L Сколько возможных 5-буквеных слов в русском языке? возможных 3-буквеных слов в английском языке? 33 5 26 3
7 Естественные Формальные русский английский китайский шведский суахили … 1. e2-e4 e7-e5… Формальный язык – это язык, в котором однозначно определяется значение каждого слова, а также правила построения предложений и придания им смысла.
8 результат развития общества для общения в быту значения слов зависят от контекста есть синонимы есть омонимы нет строгих правил образования предложений есть исключения созданы людьми в специальных областях знаний значения слов не зависит от контекста синонимов нет омонимов нет правила образования предложений строго определены нет исключений Естественные Формальные
9 Сколько различных пятизначных чисел можно записать с помощью цифр 4 и 2? В языке разрешены только четырёхбуквенные слова, которые можно образовывать из букв алфавита в любых комбинациях. Словарный запас языка составляет 81 слово. Какова мощность алфавита? Какое наименьшее число символов должно быть в алфавите, чтобы с помощью всевозможных трёхбуквенных слов можно было передать не менее 9 различных сообщений?
§ 6. Кодирование 10
11 Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило такого преобразования называется кодом. Текст : в России: Привет, Вася! передача за рубеж ( транслит ): Privet, Vasya! Windows-1251 : CFF0E8E2E52C20C2E0F1FF21 стенография: шифрование: Рсйгжу-!Гбта ” Числа : для вычислений: 25 прописью: двадцать пять римская система: XXV Как зашифровано? ? Зачем? ?
12 А •— О — — — Э ••—•• Б —••• П •— —• Ю ••— — В •— — Р •—• Я •—•— Г — —• С ••• Д —•• Т — 1 •— — — — Е • У ••— 2 ••— — — Ж •••— Ф ••—• 3 •••— — З — —•• Х •••• 4 ••••— И •• Ц —•—• 5 ••••• Й •— — — Ч — — —• 6 —•••• К —•— Ш — — — — 7 — —••• Л •—•• Щ — —•— 8 — — —•• М — — Ь —•• — 9 — — — —• Н —• Ы —•— — 0 — — — — — Код неравномерный, нужен разделитель! ! •— — •— ••• •—•— ВАСЯ •— —•— ВА, АК, ПТ, ЕМЕТ?
13 Двоичное кодирование — это кодирование с помощью двух знаков. А Б В Г 00 0 1 10 11 АБАВГБ → 00 01 00 10 11 01 Количество сообщений длиной I битов : N = 2 I Пример. Нужно закодировать номер спортсмена от 1 до 200. Сколько битов потребуется? 8 битов 2 7 < 200 ≤ 2 8 = 256 Равномерный код :
14 Сколько существует в коде Морзе различных последовательностей из точек и тире, длина которых от 4 до 6 символов? Вася и Петя передают друг другу сообщения, используя синий, красный и зелёный фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении — 3 или 4, между сообщениями — паузы. Сколько различных сообщений могут передавать мальчики?
15 Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество битов потребуется для кодирования координат одной шахматной фигуры? Для кодирования значений температуры воздуха (целое число в интервале от –50 до 40) используется двоичный код. Какова минимальная длина двоичного кода? Дорожный светофор подаёт шесть видов сигналов (непрерывные красный, жёлтый и зелёный, мигающие жёлтый и зелёный, мигающие красный и жёлтый одновременно). Подряд записано 100 сигналов светофора. Определите информационный объём этого сообщения в битах.
16 Автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством битов, а каждый номер — одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 32 автомобильных номеров.
17 Декодирование — это восстановление сообщения из последовательности кодов. •— — •— ••• •—•— ВАСЯ Когда разделитель не нужен? ? А Б В Г Д 000 10 01 110 001 A 0 корень 1 0 1 0 1 В Б 0 1 Д 0 1 Г Все кодовые слова заканчиваются на листьях дерева!
18 A 0 корень 1 0 1 0 1 В Б 0 1 Д 0 1 Г 1100000100110 110 Г 000 01 001 10 А В Д Б Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова ( условие Фано ). Сообщения декодируются однозначно.
19 Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: A = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование? Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: A = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование?
20 Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с окончанием другого кодового слова. Сообщения декодируются однозначно ( с конца !). А Б В Г Д 000 01 10 011 100 011000110110 10 0 1 0 11 100 01 Б Д Г Б В
21 А Б В Г Д 01 010 011 11 101 АБАГД АБВГА 010100111101 Выполняются ли условия Фано ? ? Декодирование может быть неоднозначным… Может быть, что условия Фано не выполнены, а декодирование однозначно (см. учебник)! !
22 А Б В 0 11 010 *Докажите, что все сообщения, закодированные этим кодом, декодируются однозначно. 01000011001011110000100
§ 7. Дискретность 23
24 Аналоговый сигнал — это сигнал, который в любой момент времени может принимать любые значения в заданном диапазоне. Аналоговые компьютеры невозможно «очистить» сигнал от помех при измерении сигнала вносится ошибка при копировании аналоговая информация искажается
25 1 0 1 1 0 время U 0 U 1 U 0 T 2T 3T 4T Дискретный сигнал — это последовательность значений, каждое из которых принадлежит некоторому конечному множеству. Свойства : сигнал изменяется только в отдельные моменты времени ( дискретность по времени ); принимают только несколько возможных значений ( дискретность по уровню ).
26 Цель – максимально точно передавать сообщения при сильных помехах. Pacta sunt servanda. •— — •— ••• •—•— 01000011001 Компьютеры могут хранить и обрабатывать только дискретную информацию! ! … закодированную с помощью конечного количества знаков некоторого алфавита. Все виды информации нужно перевести в дискретный вид! !
27 Дискретизация — это представление единого объекта в виде множества отдельных элементов. π 3,14 3,1 5 3,13 π
28 дискретизация 36,6 36,4 36,8 9 12 15 18 21 24 время t° 6 аналоговая информация время t° 36,6 36,4 36,8 9 12 15 18 21 24 6 6 ч. 36,7 ° 9 ч. 36,8 ° 12 ч. 36,9 ° 15 ч. 36,7 ° 18 ч. 36,5 ° 21 ч. 36,5 ° 24 ч. 36,6 ° дискретная информация При дискретизации есть потеря информации! ! Как уменьшить потери? ?
29 0 1 2 3 4 5 6 V аналоговые данные дискретные данные V Дискретность — это свойство не информации, а её представления. !
30 При увеличении точности дискретизации свойства аналоговой и дискретной информации практически совпадают! !
§ 8. Алфавитный подход к измерению количества информации 31
32 Количество информации в битах определяется длиной сообщения в двоичном коде. 10101100 8 битов вперёд назад вправо влево Сколько битов? ? 00 01 10 11 00101010010111 14 битов
33 определяем мощность алфавита N ; определяем количество битов информации i, приходящихся на один символ, — информационную ёмкость (объём) символа: количество информации в сообщении : где L – количество символов в сообщении. N, символов 2 4 8 16 32 64 128 256 512 1024 i, битов информации 1 2 3 4 5 6 7 8 9 10 I = L · i
34 каждый символ несёт одинаковое количество информации частота появления разных символов (и сочетаний символов) не учитывается количество информации определяется только длиной сообщения и мощностью алфавита смысл сообщения не учитывается
35 Определить количество информации в 10 страницах текста (на каждой странице 32 строки по 64 символа) при использовании алфавита из 256 символов. информационная ёмкость символа: 256 = 2 8 i = 8 бит = 1 байт количество символов на странице: 32·64 = 2 5 ·2 6 = 2 11 общее количество символов: L = 10·2 11 информационный объём сообщения: I = L · i = 10·2 11 ·1 байтов = 20 Кбайт
