Урок информатики в 10 классе

Двоичное кодирование

10 кл

Кодирование

• Кодирование – преобразование входной информации в форму, воспринимаемую компьютером, т.е. двоичный код.
• Декодирование – преобразование данных из двоичного кода в форму, понятную человеку.
• Двоичное кодирование – это кодирование с помощью двух знаков – 0 и 1.
• Двоичное кодирование информации обеспечивает простоту, надежность и дешевизну.

Для кодирования любых символов можно использовать равномерный или неравномерный код.

Равномерный код

• Равномерный код – код, в котором каждый символ кодируется одинаковым количеством других символов (одинаковой длины).

Равномерный код

• Равномерный код – код, в котором каждый символ кодируется одинаковым количеством других символов (одинаковой длины).

Задача 1а

Неравномерный код

Неравномерный код – код, в котором разные символы кодируются разным количеством других символов (разной длины).

Задача № 1а

Задача № 1б

Неравномерный код декодируется однозначно , если выполняется условие Фано : ни одно кодовое слово не совпадает с началом другого кодового слова.

Роберт Фано  сформулировал правило построения однозначно декодируемого неравномерного кода.

Условие Фано  гласит, что ни одно кодовое слово не совпадает с началом другого кодового слова.

Пример соблюдения условия Фано — телефонные номера. Телефоны экстренных служб обычно короткие. Например, номер 112 — это единый для многих стран телефон вызова экстренных служб. Поэтому ни один другой телефонный номер не может начинаться с цифр 112.

итальяно-американский учёный в области информатики, профессор-эмерит Массачусетского технологического института

Условие ФАНО

Удовлетворяет ли эта кодировка условию ФАНО?

А

О

00 0

С

10

Ф

01

11 0

А

О

000

С

10

Ф

01

110

Начало самых маленьких слов входит или нет в начало длинных слов?

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

Проверять соответствие условию Фано удобно при помощи построения двоичного дерева.

Задание № 4 из ЕГЭ

• Иван кодирует алфавит, состоящий из символов П,Е,Р,М,Ь . Все коды должны удовлетворять условию однозначного декодирования, т.е. ни одно кодовое слово не может быть началом другого кодового слова. Слова символов П,Е,Р,Ь соответственно равны 10, 01, 001, 11. Определите самое короткое слово для буквы М. Если таких несколько, то в качестве ответа запишите наименьшее по значению.

Строим бинарное дерево

П

Е

10

Р

01

001

Ь

11

Задача № 4

Задача № 5

Решение методом перебора: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001 …

0 – начало М, 1 – начало А, 10 – начало Т, 11 = А, 100 = И.

Задача № 6

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Т, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 101, О – 11, Я – 011 . Какое наименьшее количество двоичных знаков потребуется для кодирования слова КАТОК ?

Помимо прямого, существует и обратное условие Фано :   ни одно кодовое слово не может служить концом другого кодового слова .

Задача № 7

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:

Определите, какой набор букв закодирован двоичной строкой 0110100011000

Решение:

Из таблицы видим, что нарушено прямое условие Фано: начало кодов (буквы В и Е, С и D), но при этом выполняется обратное условие Фано. Тогда декодирование строки следует начинать с конца.

Однозначно получаем:

01 10 100 011 000 – В D С Е А

Ответ: ВDСЕА