1 Кодирование информации § 4. Язык – средство кодирования § 5. Дискретное кодирование § 6. Кодирование с обнаружением ошибок
§ 4. Язык – средство кодирования 2
3 Кодирование — это представление информации в форме, пригодной для её хранения, передачи и автоматической обработки. Код — это правило, по которому сообщение преобразуется в цепочку знаков. Язык — это система знаков и правил, используемая для записи и передачи информации. Естественные языки – сформировались в результате развития общества.
4 Египетское письмо Иероглифы (Китай) рука солнце дом луна кобра дождь лев гора вода лошадь
5 АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ 0123456789.,;?!-:… «» () мощность 56 Алфавит — это набор знаков, который используется в языке. Мощность алфавита — это количество знаков в алфавите. Какова мощность русского алфавита ? латинского? ?
6 Естественные Формальные русский английский китайский шведский суахили … 1. e2-e4 e7-e5… Формальный язык – это язык, в котором однозначно определяется значение каждого слова, а также правила построения предложений и придания им смысла.
7 Пример: алфавит {0, 1}. Сообщения длины 2 : 00 01 10 11 всего 4 Сообщение — это любая последовательность символов некоторого алфавита. Комбинаторика — это наука, изучающая комбинации объектов. Сколько различных сообщений длины L можно построить, используя алфавит мощностью M ? ?
8 Пример: алфавит { @, #, $, % }. Сообщения длины 1: @ # $ %. Сколько сообщений длины L ? ? Сообщения длины 2 : @ @ @ # @ $ @ % # @ # # # $ # % $ @ $ # $ $ $ % % @ % # % $ % % всего 16 всего 4
9 Если алфавит языка состоит из M символов (имеет мощность M ), количество различных сообщений длиной L знаков равно N = M L Сколько возможных 5-буквеных слов в русском языке? возможных 3-буквеных слов в английском языке? возможных сообщений длиной L символов в алфавите {+, –} ? 33 5 26 3 2 L
10 Задача. Сколько различных сообщений длиной 4 знака можно записать с помощью алфавита { А, Б, В, Г, Е } если слова должны начинаться с согласной буквы и заканчиваться на гласную? 3 5 5 2 А, Б, В, Г, Е 5 3 Б, В, Г = 1 50 Правило умножения! ! 2 А, Е
11 Задача. Сколько существует четырёхзначных чисел, составленных из чётных цифр, в которых цифры не повторяются ? 4 4 3 2 0, 2, 4, 6, 8 5 4 2, 4, 6, 8 = 96 одна цифра уже использована!
12 Задача. Сколько сообщений длиной от 2 до 5 символов можно записать с помощью алфавита {0, 1} ? L = 2 : N 2 = 2 2 = 4 Правило сложения! ! L = 3 : N 2 = 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
13 Типы звеньев ( нуклеотиды ) A – аденин ( Adenine ) C – цитозин ( Cytosine ) G – гуанин (Guanine) T – тимин ( Thymine ) Мощность алфавита? ? M = 4 3% – гены (информация о белк á х) Белки 20 типов аминокислот Длина равномерного кода? ? L = 3 4 2 < 20 < 4 3
§ 5. Дискретное кодирование 14
15 Дискретизация — это представление единого объекта в виде множества отдельных элементов. t = 18°C 20 40 0 60 80 100 120 км/ч км/ч 11 0 110,231 км / ч? ?
16 0 0 0 0 1 1 Компьютер — это дискретное устройство. Двоичный код – это код, в котором используются два знака (0 и 1). Все данные в компьютере хранятся в двоичном коде. Бит – это одна двоичная цифра (0 или 1). 010010 Сколько бит? ?
17 Кодовая таблица А Г Р 000 010 100 кодовое слово ГАГАРА: 010 000 010 000 100 000 Равномерный код — это код, в котором все кодовые слова имеют одинаковую длину. Сколько существует кодовых слов длиной N в двоичном коде? ? 2 N
18 Кодовая таблица А Г Р 000 010 100 Р А Г Р А 100000010100000 ? : Декодирование — это восстановление исходного сообщения из кода. Сколько символов было в сообщении? ? 5 100 000 010 100 000 Как разбить на кодовые слова? ? по 3
32 варианта Как выбрать длину кодовых слов? 19 Задача. В сообщении встречаются 25 символов. Выберите минимальную длину кодовых слов, при которой все они могут получить разные коды. 1 бит: 2 варианта 2 бита: 4 варианта 3 бита: 8 вариантов 4 бита: 16 вариантов 5 битов: < 25 < 25 < 25 < 25 Выбор длины кодовых слов L : M L M 0, где M 0 — мощность алфавита исходного сообщения и M — мощность нового алфавита. 2 L 25
20 Недостаток равномерных кодов – длинные закодированные сообщения. Идея : часто встречающиеся символы должны иметь более короткие коды!
21 Кодовая таблица А Г Р 0 1 10 ГАГАРА: 1 0 1 0 10 0 Неравномерный код — это код, в котором кодовые слова имеют разную длину. Декодирование: 010010 Не всегда однозначно! ! АРАР АГААР А P АГА АГААГА Как выделить кодовые слова? ?
22 Условие Фано ? ? НЕТ Нужна пауза! Как декодировать? ? Е А В П
23 Кодовая таблица А Г Р 0 10 11 Декодирование: 01001011 АГАГР Неравномерный код декодируется однозначно, если выполняется условие Фано : ни одно кодовое слово не совпадает с началом другого кодового слова.
24 10101001010 данные (код) Количество информации в битах определяется длиной сообщения в двоичном коде. 10101100 8 битов
25 1 байт = 8 бит 1 Кбайт (килобайт) = 1024 байта 1 Мбайт (мегабайт) = 1024 Кбайт 1 Гбайт (гигабайт) = 1024 Мбайт 1 Тбайт (терабайт) = 1024 Гбайт 2 10 1 байт = 2 3 бит 1 Кбайт = 2 10 байта = 2 1 0 2 3 бит = 2 13 бит 1 Мбайт = 2 10 Кбайт = 2 1 0 2 1 3 бит = 2 2 3 бит
26 2 Кбайт = 2 (1 Кбайт) = 2 1024 байт = 2048 байт = 2048 (1 байт) = 2048 8 бит = 16 384 бита Через степени числа 2 : 2 Кбайт = 2 2 10 байт = 2 11 байт = 2 11 2 3 бит = 2 14 бит.
27 1 байт 1 бит 1 Кбайт 1 Мбайт 1 Гбайт 1 Тбайт : 8 : 1024 : 1024 : 1024 : 1024 1024 1024 1024 1024 8 1 байт = 8 бит 1 Кбайт = 1024 байта число уменьшается число увеличивается
28 Задача 1. Алфавит русского языка содержит 33 символа. Определите наименьшую длину кодовых слов при кодировании сообщений на русском языке с помощью равномерного кода. M = 33 i = ? 2 5 33 2 6 i бит 2 i разных кодов 5 бит на символ не хватает … 6 бит на символ хватает ! Ответ: i = 6 бит Если различать заглавные и строчные буквы? ? i = 7 бит M 2 i
29 Задача 2. Текст длиной 160 символов записан с помощью алфавита из 26 символов. Определите количество информации в сообщении, закодированном с помощью равномерного кода наименьшей длины. L = 160 I = ? M = 3 2 I = L · i бит на символ 2 4 26 2 5 5 бит на символ хватает ! i = 5 I = 160 · 5 = 800 бит В байтах? ? I = 800 : 8 = 100 байт Ответ: I = 800 бит = 100 байт
30 Задача 3. Пароль длиной 8 символов может содержать английские буквы (заглавные и строчные), цифры и специальные знаки: @, #, $, %. Сколько бит памяти нужно выделить для хранения пароля? L = 8 I = ? M = 26 · 2+10 + 4 = 66 I = L · i 2 6 6 6 2 7 7 бит на символ хватает ! i = 7 I = 8 · 7 = 56 бит В байтах? ? I = 56 : 8 = 7 байт Ответ: I = 56 бит = 7 байт
31 Задача 4. Текст длиной 4096 символов занимает в памяти 4 Кбайта. Определите наибольшее возможное количество символов в алфавите. L = 4096 I = 4 Кбайт M = ? M 2 8 = 256 Все ли верно? ? Ответ: M = 256 i бит 2 i разных кодов M 2 i Как найти i ? ? I = L · i i = I : L i = 4 : 4096 i = 4 · 1024 · 8 : 4096 = 8 бит
32 Задача 5. Участники соревнований по бегу получили номера от 1 до 100. На финише автоматическое устройство записывает номер спортсмена. Сколько байт нужно для хранения номеров 80 спортсменов? M = 100 L = 80 I = ? i бит 2 i разных кодов M 2 i I = L · i 2 6 100 2 7 7 бит на символ хватает ! I = 8 0 · 7 = 56 0 бит В байтах? ? I = 56 0 : 8 = 7 0 байт Ответ: I = 7 0 байт
§ 7. Кодирование с обнаружением ошибок 33
34 Бит чётности : 00 01 10 11 00 0 01 1 10 1 11 0 теперь число единиц в каждом блоке чётное Если в принятом блоке нечётное число «1» – ошибка ! принято: 010 110 000 111 000 Можно ли исправить ? ? Для файлов – контрольные суммы (хэш) : CRC = Cyclic Redundancy Code MD5, SHA-1 Верно ли переданы данные ? ? 10010
35 1 11 0 00 0 00 1 11 0 00 – утроение каждого бита принято: 010 111000 101 000 исправлено: 000 111000 111 000 10010 Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку! ! Помехоустойчивый код – это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
36 П О Р Т 11111 11000 00100 00011 Каждое кодовое слово отличается от остальных не менее, чем в 3 битах! ! П = 11 111 11 000 О 3 111 11 000 11 Т 3 Расстояние Хэмминга Как декодировать? ? 10011 11100 00000 0 00 11 Т 11 0 00 О Р 11 1 00 11 1 11 00 1 00 4 Р
37 Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь eremin@pspu.ac.ru
38 http://fpg.unc.edu http://s1.iconbird.com https://sandstorm.deviantart.com http:// compression.ru http://ru.wikipedia.org https://www.kns.ru http://nix.ru http:// www.computer-services.ru http:// www.masterna4as.com http://blendercontest.com http:// geeky-gadgets.com авторские материалы
