Инфознайка
Главная

Информация вокруг нас

Виды информации
Измерения информации
Алфавитный подход
Содержательный подход
Файловая система
Кодирование графики
Кодирование звука
Скорость передачи
Электронная таблица Excel
Графы
Система счисления
Кодирование информации
Логика
Адресация в Интернете
Поиск в Интернете
Алгоритмы
Кумир
Массивы

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

Коротко о главном

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

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

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

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

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

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

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

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

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

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится

1) 4B16                  2) 41116                3)BACD16             4) 102316  

Решение:

1)      из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный

2)      последовательность БАВГ кодируется так: 01 00 10 11 = 1001011

3)      разобьем  такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем

1001011 = 0100  10112 = 4B16

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

 

Возможные ловушки:

·    расчет на то, что при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)

·    может быть дан неверный ответ, в котором нужные цифры поменяли местами (расчет на невнимательность), например, B416

·    в ответах дана последовательность, напоминающая исходную (неверный ответ BACD16), чтобы сбить случайное угадывание

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

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: 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. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится:

      13216
      D216
      310216
      2D16


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

     А                       Б                    В                        Г

    00                    11                   010                  011

    Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится:

    CDADBC16
    A7C416
    41271016
    4С7А16

  3. Кодирование сообщения происходило с использованием шифра переменной длины: А- 10, В- 11, С- 100, D- 101. После кодирования полученный двоичный шифр перевели в шестнадцатеричную систему счисления и получили: B7216. Определите зашифрованное сообщение.

    ABDBCA
    DABCA
    DDBCA
    ABCDA

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

    0001
    000
    11
    101

      

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

    00
    01
     11
    010