10-2a_Кодирование-I

Кодирование информации
§ 5. Язык и алфавит

Язык
Язык — это система знаков, используемая для хранения, передачи и обработки информации.
Иероглифы:

Алфавитное письмо
Алфавит — это набор знаков, который используется в языке.
Мощность алфавита — это количество знаков в алфавите.
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
0123456789 .,;?!-:…«»()
мощность 56
Слово — это последовательность символов алфавита, которая используется как самостоятельная единица и имеет определённое значение.

Сообщения
Сообщение — это любая последовательность символов некоторого алфавита.
Пример: алфавит @ # $ %.
Сообщения длины 1: @ # $ %.
Сообщения длины 2:
@@ @# @$ @%
#@ ## #$ #%
$@ $# $$ $%
%@ %# %$ %%
всего 16
всего 4

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

Какие бывают языки?
1. e2-e4 e7-e5…
Формальный язык – это язык, в котором однозначно определяется значение каждого слова, а также правила построения предложений и придания им смысла.

Естественные и формальные языки
результат развития общества
для общения в быту
значения слов зависят от контекста
есть синонимы
есть омонимы
нет строгих правил образования предложений
есть исключения
созданы людьми
в специальных областях знаний
значения слов не зависит от контекста
синонимов нет
омонимов нет
правила образования предложений строго определены
нет исключений
Естественные
Формальные

Задачи
Сколько различных пятизначных чисел можно записать с помощью цифр 4 и 2?
В языке разрешены только четырёхбуквенные слова, которые можно образовывать из букв алфавита в любых комбинациях. Словарный запас языка составляет 81 слово. Какова мощность алфавита?
Какое наименьшее число символов должно быть в алфавите, чтобы с помощью всевозможных трёхбуквенных слов можно было передать не менее 9 различных сообщений?

Кодирование информации
§ 6. Кодирование

Что такое кодирование?
Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило такого преобразования называется кодом.
Текст:
в России: Привет, Вася!
передача за рубеж (транслит): Privet, Vasya!
Windows-1251: CFF0E8E2E52C20C2E0F1FF21
стенография:
шифрование: Рсйгжу-!Гбта”
Числа:
для вычислений: 25
прописью: двадцать пять
римская система: XXV

Код Морзе
•— — •— ••• •—•—
ВАСЯ
•— —•—
ВА, АК, ПТ, ЕМЕТ?

Двоичное кодирование
Двоичное кодирование — это кодирование с помощью двух знаков.
АБАВГБ
→ 000100101101
Количество сообщений длиной I битов:
N = 2I
Пример. Нужно закодировать номер спортсмена от 1 до 200. Сколько битов потребуется?
8 битов
27 < 200 ≤ 28 = 256
Равномерный код:

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

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

Задачи
Автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством битов, а каждый номер — одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 32 автомобильных номеров.

Декодирование
Декодирование — это восстановление сообщения из последовательности кодов.
•— — •— ••• •—•—
ВАСЯ
Все кодовые слова заканчиваются на листьях дерева!

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

Задачи
Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код:
A = 0, Б = 10, В = 110.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование?
Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код:
A = 0, Б = 100, В = 101.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование?

Постфиксные коды
Постфиксный код — это код, в котором ни одно кодовое слово не совпадает с окончанием другого кодового слова. Сообщения декодируются однозначно (с конца!).
011000110110
10
01
011
100
01
Б
Д
Г
Б
В

Неоднозначное декодирование
АБАГД
АБВГА
010100111101
Декодирование может быть неоднозначным…

Задача
*Докажите, что все сообщения, закодированные этим кодом, декодируются однозначно.
01000011001011110000100

Кодирование информации
§ 7. Дискретность

Аналоговые сигналы и устройства
Аналоговый сигнал — это сигнал, который в любой момент времени может принимать любые значения в заданном диапазоне.
Аналоговые компьютеры
невозможно «очистить» сигнал от помех
при измерении сигнала вносится ошибка
при копировании аналоговая информация искажается

Дискретные (цифровые) сигналы
Дискретный сигнал — это последовательность значений, каждое из которых принадлежит некоторому конечному множеству.
Свойства:
сигнал изменяется только в отдельные моменты времени (дискретность по времени);
принимают только несколько возможных значений (дискретность по уровню).

Дискретность
Цель – максимально точно передавать сообщения при сильных помехах.
Pacta sunt servanda.
•— — •— ••• •—•—
01000011001
… закодированную с помощью конечного количества знаков некоторого алфавита.

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

Дискретизация
6 ч. 36,7°
9 ч. 36,8°
12 ч. 36,9°
15 ч. 36,7°
18 ч. 36,5°
21 ч. 36,5°
24 ч. 36,6°
дискретная информация

Непрерывность и дискретность
аналоговые
данные
дискретные
данные

Непрерывность и дискретность

Кодирование информации
§ 8. Алфавитный подход к измерению количества информации

Алфавитный подход
Количество информации в битах определяется длиной сообщения в двоичном коде.
10101100
8 битов
вперёд
назад
вправо
влево
00
01
10
11
00101010010111
14 битов

Алфавитный подход
определяем мощность алфавита N;
определяем количество битов информации i, приходящихся на один символ, — информационную ёмкость (объём) символа:
количество информации в сообщении:
где L – количество символов в сообщении.
I = L·i

Алфавитный подход
каждый символ несёт одинаковое количество информации
частота появления разных символов (и сочетаний символов) не учитывается
количество информации определяется только длиной сообщения и мощностью алфавита
смысл сообщения не учитывается

Задача
Определить количество информации в 10 страницах текста (на каждой странице 32 строки по 64 символа) при использовании алфавита из 256 символов.
информационная ёмкость символа:
256 = 28 ⇒ i = 8 бит = 1 байт
количество символов на странице:
32·64 = 25 ·26 = 211
общее количество символов:
L = 10·211
информационный объём сообщения:
I = L·i = 10·211·1 байтов = 20 Кбайт

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]