prosdo.ru 1

© К. Поляков, 2009


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

Что нужно знать:

  • кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

  • обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

  • один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

  • кодирование может быть равномерное и неравномерное;
    при равномерном кодировании все символы кодируются кодами равной длины;
    при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

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

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

  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Пример задания:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:

А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.


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

Решение:


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

  2. если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит

  3. если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит

  4. если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит

  5. для четвертого варианта, Д = 010, условие Фано не нарушено;

правильный ответ – 4.

Еще пример задания:

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

1) 1 2) 1110 3) 111 4) 11

Решение (вариант 1, метод подбора):

  1. рассмотрим все варианты в порядке увеличения длины кода буквы Г

  2. начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит

  3. следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит

  4. третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…

  5. … правильный ответ – 3.


Возможные проблемы:


  • при переборе можно ошибиться и «просмотреть» какой-нибудь вариант


Решение (вариант 2, «умный» метод):

  1. для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано

  2. как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит

  3. код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант

  4. третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется

  5. поэтому правильный ответ – 3.




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

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

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

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