Кодирование и декодирование информации

Неравномерное и равномерное кодирование с однозначным декодированием

Базовые знания и умения: Понимание необходимости однозначного декодирования (использование префиксного кода, без знания этих терминов). Умение построить неравномерный префиксный код.

Примерные формулировки заданий:

Для кодирования последовательности символов используется следующий код: (далее для нескольких символов приводятся двоичные кодовые слова неодинаковой длины).

Задание (один из вариантов):

          декодируйте двоичное сообщение;

          укажите сообщение, которое было закодировано данным кодом;

      укажите кодовое слово для еще одного символа – кратчайшее кодовое слово, обеспечивающее возможность однозначного декодирования сообщений из указанного класса

Разработка занятия «Кодирование информации при архивации».

Цель: знакомство учащихся с принципами архивации и правилом Фано.

Рассматриваемые понятия: Кодирование текстовой информации. Равномерное и неравномерное кодирование. Правило Фано.

Теоретическая часть.

Вопросы для повторения:

1. Сколько бит информации выделяется на кодирование каждого символа?

2. Какие существуют кодировки текста?

3. Чем отличаются различные кодировки текста?

Объяснение нового материала.

На предыдущих занятиях мы выяснили, что в компьютере каждый символ кодируется равномерным двоичным кодом. Однако, в текстах представлены далеко не все символы. Поэтому при архивации текстов используют следующее допущение: создается дополнительная кодовая таблица, в которой для каждого используемого символа назначается определенный код. Разберем на примере.

Заархивируем фразу:мама мыла раму.

В данной фразе 15 символов (12 букв, 2 пробела и 1 точка). Без архивации текст в памяти компьютера занял 15 Байт (при кодировании в однобайтовой кодировке ASCII) или 30 Байт (при кодировании в двухбайтовой кодировке UNICODE).

Построим дерево. Для этого определим используемые символы и пересчитаем их количество во фразе. Затем разделяем символы на примерно равные части, до тех пор пока в каждой ветке не останется по одному символу. Один из вариантов дерева представлено на рисунке №1.

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

Для примера, приведенного на рисунке, получаем:

Проанализируем построенное дерево:

1. Те символы, которые встречаются чаще, имеют более короткое кодовое слово.

2. Каждое кодовое слово удовлетворяет условию Фано (прямому или обратному). Это позволяет однозначно декодировать сообщение. Условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Условие Фано:

• закодированное сообщение можно однозначно декодировать с начала, если никакое кодовое слово не является началом другого кодового слова;

• закодированное сообщение можно однозначно декодировать с конца, если икакое кодовое слово не является окончанием другого кодового слова.

Если в сообщении появляются новые символы, то дерево перестраивается заново.

Практическая часть.

В качестве практики можно предложить задания, собранные К.Ю. Поляковым¹.

Пример подборки заданий приведен ниже

1. По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:

А-0, И-00, К-10, О-110, Т-111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА2) ИКОТА3) КОТ4) ни одно из сообщений не подходит

1. По каналу связи передаются сообщения, содержащие только 4 буквы – П, О, Р, Т. Для кодирования букв используются 5-битовые кодовые слова: П – 00000, О – 00111, Р – 11011, Т – 11100. Для этого набора кодовых слов выполнено такое свойство:любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех (в предположении, что передаваемые биты могут искажаться, но не пропадают). Закодированное сообщение считается принятым корректно, если его длина кратна 5 и каждая пятёрка отличается от некоторого кодового слова не более чем в одной позиции; при этом считается, что пятёрка кодирует соответствующую букву. Например, если принята пятерка 11111, то считается, что передавалась буква Р. Среди приведённых ниже сообщений найдите то, которое принято корректно, и укажите его расшифровку (пробелы несущественны).

11011 10111 11101 00111 10001

10000 10111 11101 00111 00001

1) ПОТОП 2) РОТОР 3) ТОПОР 4) ни одно из сообщений не принято корректно

1. Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:

А - 10111, Б - 00000, В - 11010.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 00100, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается 'х').

Получено сообщение 10101 10000 11110 10010. Декодируйте это сообщение – выберите правильный вариант.

1) АБВВ2) хххх3) АБхх4) АБхВ

1. По каналу связи передаются сообщения, содержащие только 4 буквы: И, Г, Л, А. Для кодирования букв И, Г, Л используются 6-битовые кодовые слова:

И – 000000, Г – 001110, Л – 110110.

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы А так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.

1) 1111102) 1110003) 0001104) не подходит ни одно из указанных выше слов

1. По каналу связи передаются сообщения, содержащие только 4 буквы: А, Т, О, М; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, М используются такие кодовые слова: Т: 100, О: 00, М: 11.

Укажите такое кодовое слово для буквы А, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите тот, у которого меньшая длина.

1) 1 2) 03) 014) 101

1. Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

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

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

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

4) это невозможно

Задания для выполнения самостоятельной / практической работы:

Практическая работа «Кодирование информации»

1 вариант

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

а b сd е

100110 0110110

Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:

1) cbade2) acdeb3) acbed4) bacde

1. Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код:

О К Л М Б

00 01110100110

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110001001001110

2) 10000011000111010

3) 110001001101001

4) 1000110001100010

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

1) 0001 2) 000 3) 11 4) 101

Практическая работа «Кодирование информации»

2 вариант

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

А В С D Е F

001001001111101

Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.

1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD

1. Для кодирования сообщения, состоящего только из букв A, B,C, D и E, используется неравномерный по длине двоичный код:

A B C D E

000 110100110

Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

1) 110000010011110

2) 110000011011110

3) 110001001001110

4) 110000001011110

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

1) 1 2) 11 3) 01 4) 010

1. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

1) для буквы Г – 11 2) это невозможно

3) для буквы В – 000 4) для буквы Б – 00

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

1) 101 2) 10 3) 11 4) 1001

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/586993-kodirovanie-i-dekodirovanie-informacii