PDF Печать E-mail

А9 (базовый уровень, время – 2 мин)

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

      Проверяемые элементыУмение кодировать и декодировать информацию

 

Теоретический материал:

 

      Кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите).
     Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.
     Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. 
      Условие Фано – это достаточное, но не необходимое условие однозначного декодирования 
 
    Пример задания:
     Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования.
    1) 00
    2) 01
    3) 11
    4) 010
 
Общий подход:
 Используя условие Фано или логические рассуждения подобрать ответ.
 
Решение:
1) 00 - нарушает условие Фано, так как кодовая цепочка совпадает с началом Б = 000 и В = 001.   Невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ, поэтому первый вариант не подходит
2) 01 - нарушает условие Фано, так как кодовая цепочка совпадает с началом Г = 011. Невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г, поэтому второй вариант тоже не подходит
3) 11 - нарушает условие Фано, так как кодовая цепочка совпадает с началом А = 1. Невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
4) 010 - условие Фано не нарушено.
 
Ответ:  4) 010
 
Задания для тренировки: 
 

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

1) 010

2) 10

3) 01

4) 011

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

1) 00

2) 01

3) 11

4) 010

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

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

2) для буквы Б – 1

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

4) для буквы Д – 01

 

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

1) для буквы Г – 00

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

3) для буквы В – 01

4) для буквы Б – 1

 

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

1) для буквы Г – 11

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

                3) для буквы В – 000
                4) для буквы Б – 00
 
 
 
belovo-lyceum22.ru , Powered by Joomla 1.5 and designed by joomlaworld.ru