ПРАКТИЧЕСКАЯ РАБОТА 4 Декодирование, задачи на Фано. Кодирование и декодирование информации краткие теоретические сведения
 Скачать 66.49 Kb.
|
|
ПРАКТИЧЕСКАЯ РАБОТА КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ Краткие теоретические сведения В чем смысл прямого условия Фано? Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным. Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова». С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде». В чем смысл обратного условия Фано? Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова». С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде». Разбор задач на условие Фано Условие задачи: дана последовательность, которая состоит из букв «A», «B», «C», «D» и «E». Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.
Вопрос: есть ли возможность для одного из символов сократить длину кодового слова таким образом, чтобы сохранить возможность однозначного декодирования? При этом коды остальных символов должны остаться неизменными.
Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов 1, 3 и 4. В случае если ни один из вариантов не подойдет, правильным ответом будет вариант 2 (не представляется возможным). Вариант 1. Код: A - 00, B - 01, C - 011, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «B» совпадает с началом кода символа «C». Обратное правило Фано не выполняется: код символа «B» совпадает с окончанием кода символа «D». Вариант не является подходящим. Вариант 3. Код: A - 00, B - 010, C - 01, D - 101, и E - 111. Прямое условие Фано не выполняется: код символа «C» совпадает с началом кода символа «B». Обратное условие также не выполняется: код символа «C» совпадает с окончанием кода символа «D». Вариант не является подходящим. Вариант 4. Код: A - 00, B - 010, C - 011, D - 01, и E - 111. Прямое условие Фано не выполняется: код символа «D» совпадает с началом кода символов «B» и «C». Однако наблюдается выполнение обратного правила Фано: код символа «D» не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим. После проверки вариантов решения задачи на соответствие прямому и обратному условию Фано, было установлено, что правильным является вариант 4. Ответ: 4 Задания для самостоятельной работы Декодируйте сообщение под таблицей. Для кодирования сообщения используется таблица1 1 Выберите вариант по указанию учителя. Вариант 1:  Сообщение: 0101110010110 Вариант 2:  Сообщение: 01011100101101 Вариант 3:  Сообщение: 0010001001001 Вариант 4:  Сообщение: 0100001101000010 Вариант 5:  Сообщение: 1010000011011000 Используя средства текстового процессора, изобразите двоичное дерево (дерево кодирования), соответствующее этому коду. 2. Выполняется ли для этой кодовой таблицы условие Фано? Обратное условие Фано? Почему? Ответ:  3. Найдите все способы декодирования сообщения, записанное под таблицей: Ответ: 4. Замените код одного символа так, чтобы выполнилось условие Фано (или обратное условие Фано). Выделите зеленым фоном ячейку таблицы с измененным кодом символа.  5. Сократите код одного символа в таблице, полученной в п. 4 так, чтобы условие Фано (или обратное условие Фано) по-прежнему выполнялось. Выделите фиолетовым фоном ячейку таблицы с измененным кодом символа. |