Задача №3

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

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

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

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

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

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

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

1) 4B₁₆

2) 411₁₆

3)BACD₁₆

4) 1023₁₆

Решение:

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

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

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

1001011 = 0100 1011₂ = 4B₁₆ ;

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

Пример 2.

Решение (вариант 1, декодирование с начала):

7. здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений

8. попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно

9. пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000

• для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 ( начало исходной цепочки – EB?);

• для кода 00011000 первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв;

• поэтому наше предположение о том, что первая буква – E, неверно;

• пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000;

• для кода 10100011000 первой буквой может быть только D с кодом 10, тогда остается 100011000 (можно полагать, что начало исходной цепочки – BD?);

• для кода 100011000 первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?).

Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»;

• для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA;

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

Решение (вариант 2, декодирование с конца):

1. для кода 0110100011000 последней буквой может быть только А (код 000), тогда остается цепочка 0110100011;

2. для 0110100011 последней может быть только буква E (011), тогда остается цепочка 0110100;

3. для 0110100 последней может быть только буква C (100), тогда остается цепочка 0110;

4. для 0110 последней может быть только буква D (10), тогда остается 01 – это код буквы B;

5. таким образом, получилась цепочка BDCEA

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