1.Условие Фано. 2.Пример №1 3.Пример №2 4.Пример №3 5.Пример №4
Условие Фано : для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода. Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода. Для возможности однозначного декодирования досточно выполнения одного из условий — или прямого, или обратного. Заметим, что существуют варианты неравномерного кодирования, для которых оба условия нарушены, и тем не менее они однозначно раскодируемые.
А Б 1 0 1 0 В 1 Г 0 1 0 Д Е 1 0 А Б 1 0 1 0 3) оставшиеся 4 кода повесить на 4 ветки одинаковой длины: 4) суммарная длина кодовых слов будет в этом случае меньше, чем в предыдущем случае: 1 + 2 + 4·4 = 19 Ответ: 19. это задание удобнее решать с помощью дерева; условие Фано выполняется тогда, когда все выбранные кодовые слова заканчиваются в листьях дерева построим дерево по известным кодовым словам: А – 0, Б – 10:
А Б 0 0 0 1 1 1 В Г 0 1 согласно условию Фано, код декодируется однозначно, если все используемые кодовые слова соответствуют листьям такого дерева; видим, что для заданных кодовых слов это условие выполняется может показаться, что ответ – 01, поскольку на эту ветвь можно «подвесить» букву Д, однако это не так – тогда будет некуда подвешивать оставшуюся букву – Е поэтому для того, чтобы добавить в это дерево две буквы (Д и Е) и сохранить выполнение условия Фано, нужно в узле 01 сделать развилку, тогда получается два свободных кода, 010 и 011, из них меньший – 010 Ответ: 010.
По условию кодовое слово для буквы W соответствует маске 1***0, где вместо звёздочек можно поставить 0 или 1. Найдем расстояния Хэмминга – количество позиций, в которых отличается это кодовое слово от известных кодовых слов букв X, Y и Z : X: 01111 Y: 00001 Z: 11000 W: 1***0 W: 1***0 W: 1***0 2+? 2+? 0+? Знаки вопроса обозначают неизвестные неотрицательные числа – количество различающихся позиций в тех битах, которые в кодовом слове для буквы W неизвестны. 3) Как видим, наиболее критичная ситуация сложилась для пары Z - W. Для того, чтобы эти кодовые слова различались в трёх позициях, все неизвестные биты кодового слова буквы W должны иметь значения, обратные соответствующим битам кодового слова для буквы Z, то есть, W = 10110 4) Проверяем полученное кодовое слово: находим расстояние Хэмминга в парах X - W и Y - W : X: 01111 Y: 00001 Z: 11000 W: 10110 W: 10110 W: 10110 3 4 3 5) Как видим, для все пар расстояние не меньше трёх, что соответствует условию задачи. 6) Ответ: 10110.
А Б 1 0 1 0 0 В Г условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков; построим дерево для заданных кодовых слов А – 0 и Б – 110: штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов Ответ: 3.
код однозначно декодируется, если выполняется условие Фано или обратное условие Фано ; в данном случае «прямое» условие Фано выполняется: с кода буквы А (0) не начинается ни один другой код, оставшиеся короткие коды (Б, Г и Д) не совпадают с началом длинного кода буквы В; таким образом, при сокращении нужно сохранить выполнение условия Фано вариант 3 не подходит, потому что новый код буквы В начинается с 0 (кода А), поэтому условие Фано нарушено вариант 4 не подходит, потому что код буквы В начинается с 10 (нового кода б), поэтому условие Фано нарушено вариант 1 подходит, условие Фано сохраняется (все трёхбитные коды различны, ни один не начинается с 0) Ответ: 3.
