Однозначное декодирование. Условие фано. Однозначное декодирование обеспечивается
Использование ОЗМС при решении задач связано с определенными трудностями. Поэтому обычно устанавливают дополнительные соотношения между характеристиками движения и сил, которые более удобны для практического применения. Такими соотношениями являются общие теоремы динамики. Они, являясь следствиями ОЗМС, устанавливают зависимости между быстротой изменения некоторых специально введенных мер движения и характеристиками внешних сил.
Теорема об изменении количества движения. Введем понятие вектора количества движения (Р. Декарт) материальной точки (рис. 3.4):
Я і = т V г (3.9)
Рис. 3.4.
Для системы вводим понятие главного вектора количества движения системы как геометрической суммы:
Q = Y, m " V r
В соответствии с ОЗМС: Хю,-^=я) , или X
R (E) .
С учетом, того /w, = const получим: -Ym,!" = R (E) ,
или в окончательном виде
дО/ді = А (Е (3.11)
т.е. первая производная по времени главного вектора количества движения системы равна главному вектору внешних сил.
Теорема о движении центра масс. Центром масс системы называют геометрическую точку, положение которой зависит от т, и т.е. от распределения масс /г/, в системе и определяется выражением радиуса-вектора центра масс (рис. 3.5):
где г с - радиус-вектор центра масс.
Рис. 3.5.
Назовем = т с массой системы. После умножения выраже-
ния (3.12) на знаменатель и дифференцирования обеих частей полу-
ценного равенства будем иметь: г с т с = ^т.У. = 0, или 0 = т с У с.
Таким образом, главный вектор количества движения системы равен произведению массы системы и скорости центра масс. Используя теорему об изменении количества движения (3.11), получим:
т с дУ с /ді = А (Е) , или
Формула (3.13) выражает теорему о движении центра масс: центр масс системы движется как материальная точка, обладающая массой системы, на которую действует главный вектор внешних сил.
Теорема об изменении момента количества движения. Введем понятие момента количества движения материальной точки как векторное произведение ее радиуса-вектора и количества движения:
к о, = бл х т, У , (3.14)
где к ОІ - момент количества движения материальной точки относительно неподвижной точки О (рис. 3.6).
Теперь определим момент количества движения механической системы как геометрическую сумму:
К() = X ко, = ЩУ, ? О-15>
Продифференцировав (3.15), получим:
Ґ сік --- х т і У. + г ю х т і
Учитывая, что = У Г У і х т і У і = 0, и формулу (3.2), получим:
сіК а /с1ї - ї 0 .
На основании второго выражения в (3.6) окончательно будем иметь теорему об изменении момента количества движения системы:
Первая производная по времени от момента количества движения механической системы относительно неподвижного центра О равна главному моменту внешних сил, действующих на эту систему, относительно того же центра.
При выводе соотношения (3.16) предполагалось, что О - неподвижная точка. Однако можно показать, что и в ряде других случаев вид соотношения (3.16) не изменится, в частности, если при плоском движении моментную точку выбрать в центре масс, мгновенном центре скоростей или ускорений. Кроме этого, если точка О совпадает с движущейся материальной точкой, равенство (3.16), записанное для этой точки обратится в тождество 0 = 0.
Теорема об изменении кинетической энергии. При движении механической системы изменяется как «внешняя», так и внутренняя энергия системы. Если характеристики внутренних сил, главный вектор и главный момент, не сказываются на изменении главного вектора и главного момента количества ускорений, то внутренние силы могут входить в оценки процессов энергетического состояния системы. Поэтому при рассмотрении изменений энергии системы приходится рассматривать движения отдельных точек, к которым приложены также и внутренние силы.
Кинетическую энергию материальной точки определяют как величину
Т^туЦг. (3.17)
Кинетическая энергия механической системы равна сумме кинетических энергий материальных точек системы:
Заметим, что Т > 0.
Определим мощность силы, как скалярное произведение вектора силы на вектор скорости:
Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и , и вы запутались в алгоритме ее решения? Вам срочно нужно познакомиться с условием Фано , а также записаться ко мне на индивидуальные уроки. На своих уроках я акцентирую внимание на решении тематических простых и сложных упражнений.
В чем смысл прямого условия Фано?
Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.
Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова ».
С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово 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
А сейчас я вам предлагаю ознакомиться с мультимедийным решением задачи, которая была предложена в демонстрационном варианте ЕГЭ по информатике и ИКТ. Кстати, данная задача относится к типу задач, решаемых с использованием условия Фано .
Остались вопросы?
Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.
Естественно возникает вопрос: существуют ли неравномерные коды, для которых декодирование всегда однозначно? Да, существуют.
Роберт Фано сформулировал следующее достаточное условие того, что код имеет однозначное декодирование: никакое кодовое слово не является началом другого кодового слова. Если это условие выполнено, то никаких проблем с декодированием не будет.
Пусть A 1 , A 2 и A 3 - слова над некоторым алфавитом такие, что A 1 =A 2 A 3 , то есть A 1 получается из A 2 простым приписыванием к нему слова A 3 (слова A 2 или A 3 могут быть односимвольными). Назовем слово A 2 , которое является начальной частью слова A 1 , префиксом слова A 1 . Например, для слова 11101101 префиксами будут слова 1110110 , 111011 , 11101 , 1110 , 111 , 11 , 1 .
Тогда условие Фано для кодов, можно сформулировать так:
Никакое кодовое слово не является префиксом другого кодового слова .
Коды, удовлетворяющие условию Фано, называются префиксными . Итак, если код префиксный, он допускает однозначное декодирование.
Например, код, состоящий из кодовых слов {0, 10, 11} , является префиксным, и следующую кодовую последовательность 01001101110 можно разбить на кодовые слова единственным образом: 0 10 0 11 0 11 10 .
А код, состоящий из кодовых слов {0, 10, 11, 100} , префиксным не является и он не допускает однозначного декодирования. Действительно, ту же самую последовательность можно разбить на кодовые слова разными способами: 0 10 0 11 0 11 10 или 0 100 11 0 11 10 .
Важно отметить, что условие Фано является только достаточным условием однозначного декодирования для кодов, но не является необходимым условием.
Например, простой код, состоящий всего из двух кодовых слов {1, 10} , очевидно не является префиксным, но он дает однозначное декодирование любой кодовой последовательности, полученной при кодировании этим кодом. Действительно, в такой последовательности не может стоять рядом два нуля. А тогда каждый ноль со стоящей перед ней единицей заменяем на прообраз второго кодового слова, а все оставшиеся единицы - на прообраз первого слова, это и будет однозначным декодированием.
Существуют и другие, менее простые коды, обладающие тем же свойством. Например, код {01,10,011} также не является префиксным, но обладает однозначным декодированием (попробуйте доказать это самостоятельно).
Как же все-таки определить является ли код однозначно декодируемым, если для него не выполняется условие Фано? Можно использовать следующий метод.
Пусть слово A 2 является префиксом слова A 1 . Тогда A 1 =A 2 A 3 , где A 3 некоторое слово, конечная часть слова A 1 . Назовем A 3 суффиксом пары слов A 1 и A 2 , одно из которых является префиксом другого, а саму пару A 1 и A 2 назовем префиксной .
Рассмотрим в заданном коде все префиксные пары кодовых слов и построим по ним множество всех суффиксов. Далее рассмотрим все пары префиксных слов, из которых одно является кодовым, а другое – суффиксом, и для них построим суффиксы, расширяя множество суффиксов. Продолжим этот процесс до тех пор пока не перестанут появляться новые суффиксы. Код является однозначно декодируемым тогда и только тогда, когда никакой суффикс не совпадает ни с каким кодовым словом.
Например, для кода {01,10,011} множеством суффиксов будет {1,0,11} . Ни один суффикс здесь не совпадает ни с одним кодовым словом, поэтому, можно утверждать, что этот код является однозначно декодируемым.
Задача 1. Определить обладают ли свойством однозначной декодируемости следующие коды: а) {110, 11, 100, 00, 10} б) {100, 001, 101, 1101, 11011} .
Декодирование последовательностей, полученных кодами, не являющимися префиксными, требует более сложного анализа, чем для префиксных кодов. Префиксные коды иногда называют мгновенными (мгновенно декодируемыми), так как для них при чтении кодовой последовательности конец кодового слова распознается сразу по достижении конечного символа слова. В этом состоит преимущество префиксных кодов.
Демонстрационный вариант ЕГЭ 2019 г. – задание №5
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение:
Ответ:
Демонстрационный вариант ЕГЭ 2018 г. – задание №5
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.
Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение:
Ответ: 1100
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант ЕГЭ 2017 г. – задание №5
Решение:
Для нахождения кодовых слов будем использовать данную таблицу.
Если коды остальных букв будет начинаться на 0, код буквы А=0 будет являться началом их кодов, поэтому этот вариант не подходит. Если код Б=10, коды букв В, Г, Д, Е начинаются на11. Чтобы получить 4 разных кода, нужно использовать коды, состоящие из 4-х символов (1111, 1110, 1101, 1100) .
| 0 | 1 | ||||
| 1 | |||||
| 1 | 0 | ||||
| 1 | 0 | 1 | 0 | ||
А - 0 (1 символ)
Б - 10 (2 символа)
В - 1100 (4 символа)
Г - 1101 (4 символа)
Д - 1110 (4 символа)
Е - 1111 (4 символа)
1+2+4+4+4+4 = 19
Ответ: 19
Демонстрационный вариант ЕГЭ 2016 г. – задание №5
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение:
Для нахождения кодовых слов будем использовать данную схему.
Если коды остальных букв будет начинаться на 0 , код буквы О =0 будет являться началом их кодов, поэтому этот вариант не подходит. Так как код буквы П =100 , а код буквы Т =111 , то буква С не может начинаться и заканчиваться этими цифрами.
Ответ: 101
Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код:
Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится:
1) DACBDC 1 6 2) AD26 16 3) 621310 16 4) 62DA 16
Решение:
ГАВБГВ = 0110001011011010
| 0110 | 0010 | 1101 | 1010 |
| 6 | 2 | D | A |
Ответ: 4
Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.
Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода.
1) 57414 2) 53414 3) 53412 4) 53012
Решение:
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 101 | 011 | 100 | 001 | 010 |
| 5 | 3 | 4 | 1 | 2 |
Ответ: 3
Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01100010100100100110?
1) 6543 2) 62926 3) 62612 4) 3456
Решение:
01100010100100100110
| 01100 | 01010 | 01001 | 00110 |
| 6 | 5 | 4 | 3 |
Ответ: 1
Для кодирования букв О, Л, А, З, К используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ЗАКОЛКА и записать результат в шестнадцатеричном коде, то получится:
1) 4531253 2) 9876 3) E832 4) 238E
Решение:
| О | Л | А | З | К |
| 0=00 | 1=01 | 2=10 | 3=11 | 4=100 |
ЗАКОЛКА = 1110100000110010
| 1110 | 1000 | 0011 | 0010 |
| E | 8 | 3 | 2 |
Ответ: 3
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=00, Б=11, В=100. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 010 2) 0 3) 01 4) 011
Решение:
A=00, Б=11, В=100, Г=?
Ответ: 3
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 111, Б — 110, В — 101, Г — 100.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 1 2) 0 3) 01 4) 10
Решение:
А — 111, Б — 110, В — 101, Г — 100, Д — ?
Ответ: 2
По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г. Для кодирования букв А, Б, В используются 5-битовые кодовые слова: А — 10110, Б — 11000, В — 00101. Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы Г, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?
1) 01110 2) 01011 3) 10001 4) не подходит ни одно из указанных выше слов
Решение:
1) 01 110: А — 10 110 — не отличаются не менее чем в трёх позициях
2) 01011: А — 101 10 , Б — 1 1000 , В — 0010 1 — отличаются не менее чем в трёх позициях
Ответ: 2
Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами:
А — 10001, Б — 01101, В — 10110.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 01111, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘х’).
Получено сообщение 00110 11101 11000 11001. Декодируйте это сообщение – выберите правильный вариант.
1) ВБхх 2) ВБВА 3) хххх 4) ВБхА
Решение:
| 00110 | 11101 | 11000 | 11001 |
| В=1 0110 | Б=0 1101 | x | А=10 001 |
Ответ: 4
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 1; Б – 0100; В – 000; Г – 011; Д – 0101. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы Г – 11 2) для буквы В – 00 3) для буквы Г – 01 4) это невозможно
Решение:
Ответ: 2
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 011. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7 2) 8 3) 9 4) 10
Решение:
А-1, Б-011, В-00, Г-010
Ответ: 9
По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 6 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:1, Б:01, В:001, Г:111
2) А:1, Б:01, В:10, Г:111
3) А:00, Б:01, В:10, Г:11
4) А:100, Б:101, В:11, Г:0
Решение:
Ни одно кодовое слово не является началом другого: А является началом Г в 1-й и 2-й вариантах.
Общая длина закодированного сообщения должна быть как можно меньше.
3) А:00 (15), Б:01 (10), В:10 (6), Г:11 (4)
2.15+2.10+2.6+2.4 = 70
4) А:100 (15), Б:101 (10), В:11 (6), Г:0 (4)
3.15+3.10+2.6_1.4 = 61
Ответ: 3
По каналу связи с помощью равномерного двоичного кода передаются сообщения, содержащие только 4 буквы П, Р, С, Т. Каждой букве соответствует своё кодовое слово, при этом для набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Для кодирования букв П, Р, С используются 5-битовые кодовые слова: П: 01111, Р: 00001, С: 11000. 5-битовый код для буквы Т начинается с 1 и заканчивается на 0. Определите кодовое слово для буквы Т.
Решение:
С: 1 1000
Т: 1 0110 (Т начинается с 1 и заканчивается на 0)
С и Т: 2 буквы одинаковы, то это означает, что остальные 3 буквы должны быть разными.
Ответ: 1 0110
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 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.