Главная / Задание 5 / Задание 5. Пример

Задание 5. Пример

1. Пример задания

 

По каналу связи передаются сообщения, содержащие только четыре буквы,
А, Б, В, Г. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А: 0,  Б: 100,  В: 110.

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Правильный ответ:           101

Решение: Так как код А – это 0, то код для Г не может начинаться с 0 (нарушается условие Фано для букв А и Г). Поэтому код для Г должен начинаться с 1. Оба слова длины 2, которые начинаются с 1, использовать нельзя: 10 – начало кода буквы Б, а 11 – начало кода буквы В. Из начинающихся с 1 слов длины 3 для использования в качестве кода для Г доступны слова 101 и 111. В обоих случаях условие Фано выполняется. Из них наименьшее кодовое значение имеет слово 101 (см. рис.1).

Замечание. Условие Фано также будет выполнено, если в качестве кода для Г использовать любое слово, которое начинается с 101 или 111.  Условие Фано НЕ будет выполнено, если в качестве кода для Г использовать любое слово, которое начинается со слов  100 и 110 – кодов для Б и В. Вместе со сказанным выше это означает, что в качестве кода для Г использовать любое слово, которое начинается с 101 или 111 и ТОЛЬКО такое слово.

ta

Рис.5-1. Все двоичные слова длины не более 3; каждый узел дерева соответствует одному такому слову. Красным обозначены узлы, соответствующие началам кодовых слов; оранжевым – узлы, соответствующие продолжениям кодовых слов; зеленым – слова, которые могут быть кодовыми словами для Г при соблюдении условия Фано.

2. Еще одна задача

 

По каналу связи передаются сообщения, содержащие только шесть букв,
А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А: 0,  Б: 101,  В: 110.

Какова наименьшая возможная суммарная длина всех кодовых слов?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Правильный ответ:           18

Решение: В соответствии с замечанием после решения задачи 5-1, каждое из кодовых слов для букв Г, Д, Е является продолжением одного из слов 100 и 111 (коды для буквы Б в условиях задач 5-1 и 5-2 – разные). Таким образом, среди слов, которые можно использовать, есть только два слова длины 3 – сами слова 100 и 111. Но если использовать оба эти слова в качестве кодовых слов, скажем, для букв Г и Д, то для буквы Е кодовых слов не останется – любое из возможных для Е слов – продолжение слов, уже выбранных для Г и Д. Поэтому в коде (скажем, для буквы Г) можно использовать только одно из трехбуквенных слов 100 и 111. Для оставшихся двух букв придется использовать 4-буквенные слова. Пример такого кода, удовлетворяющего условию Фано:   А: 0,  Б: 101,  В: 110, Г: 100, Д: 1110, Е: 1111. Суммарная длина кодовых слов: 1+3+3+3+4+4 = 18.

3. И еще одна задача

По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы С, О, Ф, Т. Для кодирования букв С, О, Ф используются 5-битовые кодовые слова:   С – 01111,    О – 00001, Ф – 11000.

Для этого набора кодовых слов выполнено такое свойство:

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

Это свойство важно для расшифровки сообщений при наличии помех.

Какое кодовое слово можно использовать для буквы Т, чтобы указанное свойство выполнялось для всех четырех кодовых слов? В ответе укажите наибольшее (в смысле обозначаемого двоичного числа) из таких кодовых слов.

Правильный ответ:           10110

Решение:

Искомое число не может начинаться с 11. Действительно, единственное такое число, которое отличается от кода буквы Ф не менее, чем в 3 разрядах. – это число 11111. Но это число не подходит, т.к. оно отличается от кода буквы С только в одной позиции. Поэтому наибольшее из возможных кодовых слов (если оно начинается с 1) должно начинаться с 10. Из сравнения с кодом буквы С получаем, что хотя бы одна из трех оставшихся цифр – это 0. Наибольшее из таких чисел – это число 10110. Проверкой убеждаемся, что оно подходит.

 

Еще задачи на кодирование на стр. задачника.

 
 

6 комментариев

  1. Никита:

    Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДВВ).

    Вместо ДВВ должно быть ДГГ..

  2. FED:

    4) 010 – подходит! (не является ничьим началом и никто не является кго началом). Здесь ошибка вместо кго, должно стоять его

  3. Илья:

    У вас ошибка! Код для Д: 001 – вместе с кодами для А, Б, В, Г образует префиксный код. А правильно Код для Д: 101!

    Правильный ответ: 4

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика