Подходит ли код под условие фано. Условие Фано и префиксные коды
Задание 31. Неравномерные коды. Условие Фано
5-54.Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 001, Б - 010, В - 000, Г - 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 00 2) 01 3) 0000 4) 101
5-85. Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У – 000, Ч – 001, Е – 010, Н – 100, И – 011, К – 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Примечание. Префиксный код – это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
4) это невозможно
5-94. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
5-74. По каналу связи передаются сообщения, содержащие только 4 буквы: E, Н, О, Т. В любом сообщении больше всего букв О, следующая по частоте буква – Е, затем – Н. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать?
1) Е – 0, Н – 1, О – 00, Т – 11 2) О – 1, Н – 0, Е – 01, Т – 10
3) Е – 1, Н – 01, О – 001, Т – 000 4) О – 0, Н – 10, Е – 111, Т – 110
5-105. По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:1, Б:01, В:001, Г:111
2) А:1, Б:01, В:10, Г:111
3) А:00, Б:01, В:10, Г:11
4) А:100, Б:101, В:11, Г:0
5-102. В сообщении встречается 10 разных букв. При его передаче использован неравномерный двоичный префиксный код. Известны коды трех букв: 11, 100, 101. Коды остальных семи букв имеют одинаковую длину. Какова минимальная суммарная длина всех 10-ти кодовых слов?
5-104. В сообщении встречается 50 букв А, 30 букв Б, 20 букв В и 5 букв Г. При его передаче использован неравномерный двоичный префиксный код, который позволил получить минимальную длину закодированного сообщения. Какова она в битах?
По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для буквA, B, C используются такие кодовые слова: A – 111, B – 0, C – 100.
Укажите кратчайшее кодовое слово для буквыD, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
9-1-23. После преобразования растрового 256-цветного графического файла в 16-цветный формат его размер уменьшился на 15 Кбайт. Каков был размер исходного файла в Кбайтах?
9-1-25. После преобразования растрового графического файла его объем уменьшился в 1,5 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?
13-37. При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр). Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.
13-38. При регистрации в компьютерной системе, используемой при проведении командной олимпиады, каждому ученику выдается уникальный идентификатор – целое число от 1 до 1000. Для хранения каждого идентификатора используется одинаковое и минимально возможное количество бит. Идентификатор команды состоит из последовательно записанных идентификаторов учеников и 8 дополнительных бит. Для записи каждого идентификатора команды система использует одинаковое и минимально возможное количество байт. Во всех командах равное количество участников. Сколько участников в каждой команде, если для хранения идентификаторов 20 команд-участниц потребовалось 180 байт?
13-50. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
16-165. Значение арифметического выражения: 9 22 + 3 66 – 18 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
3. Коды без разделителя. Условие Фано
Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответ на следующий вопрос: возможно ли такое кодирование без использования разделительных знаков?
Суть этой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из сообщения каждого отдельного знака (то есть декодирование) оказывается однозначным без специальных указателей разделения знаков.
Наиболее простыми и употребимыми кодами без разделителя являются так называемые префиксные коды , которые удовлетворяют следующему условию –условию Фано :Сообщение, закодированное с использованием неравномерного кода может быть однозначно декодировано, если никакой из кодов в данном сообщении не совпадает с префиксом * (началом) какого-либо иного более длинного кода.
Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.
Если условие Фано выполняется, то при прочтении (декодировании, расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Пример 1 . Являются ли коды, представленные втабл. 4,префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».
Пример 2 . Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:
00100010000111010101110000110
Табл. 6. Таблица префиксных кодов
Декодирование производится циклическим повторением следующих действий:
«Отрезать» от текущего сообщения крайний слева символ, присоединить его справа к рабочему (текущему) кодовому слову;
сравнить текущее кодовое слово с кодовой таблицей; если совпадения нет, вернуться к пункту 1.
С помощью кодовой таблицы текущему кодовому слову поставить в соответствие символ первичного алфавита;
Проверить, имеются ли еще знаки в закодированном сообщении; если да, то перейти к пункту 1.
Применение данного алгоритма к предложенному выше закодированному сообщению дает:
00100010000111010101110000110
Таким образом, доведя процедуру декодирования до конца, можно получить сообщение: «мама мыла раму».
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.
Однако условие Фано не устанавливает конкретного способа формирования префиксного кода, оставляя поле для деятельности по разработке наилучшего из возможных префиксных кодов.
4. Префиксный код Шеннона–Фано
Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.
Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере .
Пусть
имеется первичный алфавит
,
состоящий из шести знаков:
,
где
.
Пусть вероятности появления этих знаков
в сообщениях таковы:
,
,
,
,
и
.
Расположим эти знаки в таблице в порядке
убывания вероятностей.
Разделим
знаки на две группы так, чтобы суммы
вероятностей в каждой из этих двух групп
были бы приблизительно равными. При
этом в 1-ю группу попадут
и
,
а остальные – во 2-ю группу. Знакам
первой группы присвоим первый слева
разряд их кодов «0», а первым слева
разрядом кодов символов второй группы
пусть будет «1».
Продолжим
деление каждой из получающихся групп
на подгруппы по той же схеме, то есть
так, чтобы суммы вероятностей на каждом
шаге в обеих подгруппах делимой группы
были бы возможно более близкими. Таким
образом будем получать по одному
следующие разряды кодов символов
.
Эти следующие разряды будем приписывать
справа к уже имеющимся.
Вся эта процедура может быть схематически изображена в табл 7.
Табл. 7. Построение кода Шеннона-Фано
|
Знак |
|
Разряды кода | ||||
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
|
| ||||||
Видно, что построенные коды знаков
удовлетворяют условию Фано, следовательно,
такое кодирование является префиксным.
Найдем среднюю длину полученного кода по формуле
,
где
– число разрядов (символов) в коде,
соответсвующем символу
.
Из таблицы видно, что
,
,
.
Таким образом, получаем:
Таким образом, для кодирования одного
символа
первичного алфавита
потребовалось в среднем 2.45 символов
вторичного (двоичного) алфавита.
Определим среднее количество информации, приходящееся на знак первичного алфавита в первом приближении (с учетом различной вероятности появления этих знаков в сообщениях). Применим формулу Шеннона:
.
Найдем избыточность полученного двоичного кода:
,
то есть избыточность – около 2.5.
Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.
Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и , и вы запутались в алгоритме ее решения? Вам срочно нужно познакомиться с условием Фано , а также записаться ко мне на индивидуальные уроки. На своих уроках я акцентирую внимание на решении тематических простых и сложных упражнений.
В чем смысл прямого условия Фано?
Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.
Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова ».
С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде ».
В чем смысл обратного условия Фано?
Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова ».
С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде ».
Практическое применение условия Фано
Рассмотрим телефонные номера в традиционной телефонии. Если уже существует номер «102», то номер «1029876» попросту не будет выдан. В случае набора первых трех цифр АТС перестает распознавать и принимать все остальные цифры, соединяя с абонентом по номеру 102. Однако это правило не является действительным для операторов мобильной связи. Связано это с тем, что для набора номера необходимо нажатие соответствующей клавиши, которой, в основном, является клавиша с изображением зеленой телефонной трубки. По этой причине, номера «102», «1020» и «1029876» могут существовать и быть закрепленными за разными адресатами.
Условие задачи: дана последовательность, которая состоит из букв «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
А сейчас я вам предлагаю ознакомиться с мультимедийным решением задачи, которая была предложена в демонстрационном варианте ЕГЭ по информатике и ИКТ. Кстати, данная задача относится к типу задач, решаемых с использованием условия Фано .
Остались вопросы?
Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.
Рассмотрим другую кодовую таблицу: А Б В Г Д 000 01 10 011 100 Здесь условие Фано не выполняется, поскольку код буквы Б (01) является началом кода буквы Г (011), а код буквы Д (100) начинается с кода буквы В (10). Тем не менее, можно заметить, что выполнено «обратное» условие Фано: ни один код не является окончанием другого кода (такой код называют постфиксным). Поэтому закодированное сообщение можно однозначно декодировать с конца. Например, рассмотрим цепочку 011000110110. Последней буквой в этом сообщении может быть только В (код 10): В 0110001101 10 Вторая буква с конца – Б (код 01): Б В 01100011 01 10 и так далее: Б Д Г Б В 01 100 011 01 10.
Слайд 26 из презентации «Методы кодирования информации» . Размер архива с презентацией 734 КБ.Методы кодирования
краткое содержание других презентаций«Двоичное кодирование» - Цифры. Двоичное кодирование текстовой информации. Таблица кодировки. Информационный объем текста. Двоичное кодирование в компьютере. Кодирование текстовой информации. Таблица расширенного кода. Символ. Уникальный двоичный код. Буква латинского алфавита. Использование двоичной системы. Компьютеры.
«Кодирование информации в двоичном коде» - Определение. Системы счисления. Двоичная система счисления. Кодирование. Кодирование информации. Приведите примеры кодирования. Десятичная система счисления. Значение цифры. Значение цифры зависит от ее положения. Алфавит. Языки. Римская непозиционная система. Двоичное кодирование. Что здесь зашифровано.
«Способы кодирования» - Номер столбца. Буква исходного текста. Кодирование информации. Способы кодирования информации. Декодируйте информацию. Передаваемая информация. В мире кодов. Автоматическое кодирование. Метод координат. Достоинства и недостатки. Разнообразие кодов. Мальчик. Как можно назвать записную книжку с точки зрения хранения информации. Закодированный текст. Носитель информации. Ключевые слова. Разгадайте ребус.
«Способы кодирования информации» - В памяти компьютера информация представлена в двоичном коде. Кодирование и декодирование. Можно закодировать информацию. Способы кодирования информации. Составим простейшую кодовую таблицу. Чтобы узнать зашифрованное слово, возьмите только первые слоги. Что прочитал Лом на флагах встречной шхуны. Придумайте собственный способ кодирования букв русского алфавита. Задания. Зашифрованная информация. Луи Брайль придумал специальный способ представления информации.
«Методы кодирования информации» - Двоичное кодирование в компьютере. Количество информации. Оптический телеграф Шаппа. Условие Фано. Какой код использовать. Получено сообщение. «Да» или «Нет». Первый телеграф. Способы кодирования информации. Запись информации. Почему двоичное кодирование. Сигнальные флаги. Кодирование. Кодирование и декодирование. Кодирование информации. Выбор способа кодирования. Виды информации. Сколько вариантов.
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Однозначное декодирование Прямое и обратное условие Фано Учитель информатики и ИКТ МБОУ СОШ № 7 г. Оха Сахалинской области Сергиенко Татьяна Геннадьевна
Задача 1 Пусть для кодирования фразы «Доброе утро» выбран такой код: Д О Б Р Е У Т Пробел 111 000 00 1 01 0 10 11
Коды букв «сцепляются» в единую битовую строку и передаются, например, по сети: Доброе утро→ 11100000100001110101000 В пункте назначения возникает проблема – как восстановить исходное сообщение, и возможно ли это.
11100000100001110101000 Раскодировать данное сообщение можно разными способами. В том числе предположим, что оно состоит только из букв Р – 1 и У – 0. Тогда получим РРРУУУУУРУУУУРРРУРУРУУУ, т.е. бессмысленный набор букв.
Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).
Значит, код не является однозначно декодируемым.
Задача 2 Равномерные коды. Для той же фразы используем равномерный код: Д О Б Р Е У Т Пробел 111 000 001 101 011 010 100 110
Равномерные коды неэкономичны – гораздо длиннее неравномерных. Это приводит к усложнению кодирования, но при этом они раскодируются однозначно, что, естественно, облегчает задачу.
Задача 3 Чтобы сократить длину сообщения, можно попробовать применить неравномерный код, т.е. код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину, от одного до нескольких символов.
Используем следующий код: 01Эта битовая цепочка декодируется однозначно. Д О Б Р Е У Т Пробел 01 00 1011 100 1010 1101 1110 1111
Первая буква - Д (код 01), т.к. ни одно другое кодовое слово не начинается с 01. Вторая буква – О (код 00). Никакое другое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется и для кодовых слов других букв.
УСЛОВИЕ ФАНО Никакое кодовое слово не совпадает с началом другого кодового слова. Такие коды называются префиксными (раскодируются с начала сообщения) и декодируются однозначно.
Задача 4 Рассмотрим ещё один код: Он не является префиксным, т.к. код буквы Д (10) совпадает с началом кода буквы Б (1011), У(1000) и код буквы О(00) совпадает с началом кода буквы Р (001). Д О Б Р Е У Т Пробел 10 00 1011 001 0101 1000 0111 1111
Закодируем наше сообщение: ДОБРОЕ УТРО→ 10 00 1011 001 00 0101 1111 1000 0111 001 00 Начнём раскодировать с начала. Первая – Д, или У, а дальше идут вообще разные варианты: Р или Б… Т.е. надо «заглядывать» вперёд, что очень неудобно.
Попробуем раскодировать сообщение с конца – оно однозначно декодируется! Выполняется обратное условие Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова.
Коды, для которых выполняется обратное условие Фано, называются постфиксными.
Сделаем вывод: Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.
Условие Фано - это достаточное, но не необходимое условие однозначной декодируемости Это значит, что: - для однозначной декодируемости достаточно выполнения хотя бы одного из двух условий - прямого или обратного. - могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано, но тем не менее обеспечивается однозначное декодирование, т.к. иначе теряется смысл выражения.
Задача 5 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа: 1) для буквы Д -11 2) это невозможно 3) для буквы Г - 10 4) для буквы Д -10
РЕШЕНИЕ: Исходный код – префиксный. Для него выполняется условие Фано – ни один из трёхбитных кодов не начинается ни с 00 (А), ни с 01 (Б). (При этом обратное условие Фано не выполняется – код А (00) совпадает с окончанием В (100), а код Б (01) совпадает с окончанием Г (101).)
Теперь проверим ответы. Сократим Д до 11. Если полученный код нарушит прямое условие Фано, то свойство однозначного декодирования будет нарушено. Но этого не произошло, нет других кодов, начинающихся с 11. Это и есть верное решение. Проверим остальные варианты.
Вариант 2 сразу не рассматриваем – ответ у нас найден. Вариант 3 нарушает прямое условие Фано – с 10 начинается код буквы В (101). Вариант 4 – так же нарушает прямое условие Фано. Т.е. ответ однозначный, других вариантов нет.
Спасибо за внимание!
