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

Урок 10-7. Двоичное кодирование

Данные – сведения, представленные на определённом материальном носителе, в определённом формате, удобном для хранения, передачи, приёма и обработки.

Информация – данные, сопровождающиеся смысловой нагрузкой, помещённой в некоторый контекст.

Знание – зафиксированная и проверенная практикой информация, которая может многократно использоваться людьми для решения тех или иных задач.

Кодирование – преобразование входной информации в форму, воспринимаемую компьютером, т.е. двоичный код.

Декодирование – преобразование данных из двоичного кода в форму, понятную человеку.

Двоичное кодирование – это кодирование с помощью двух знаков – 0 и 1.

Двоичное кодирование информации обеспечивает простоту, надежность и дешевизну.

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

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

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

Задача № 1а

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

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

Задача № 1б

Задача № 1в

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

Задача № 2

Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный код.

Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11.

Можно ли сократить для одной из букв длину кодового слова?

1. кодовое слово для буквы Е можно сократить до 01;

2. кодовое слово для буквы К можно сократить до 1;

3. кодовое слово для буквы Н можно сократить до 10 //3

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

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

Задача № 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СЕА