Система

Как уже говорилось. Преобразование информации из одной формы представления (знаковой системы) в другую называется кодированием.

Процесс обратный кодированию называется декодированием. С этими процессами человек сталкивается ежедневно. В качестве примера можно рассмотреть разговор по телефону. Когда человек произносит слова в трубку телефона, микрофон, установленный внутри телефонной трубки, осуществляет кодирование (преобразование) звука в электрические сигналы, которые передаются по проводам к телефону другого абонента. Громкоговоритель, установленный в трубке второго абонента, декодирует электрический сигнал, преобразуя его снова в звук, и второй человек воспринимает уже звуковые сигналы.

Последовательность символов алфавита какого-либо языка, кодирующая состояние источника и воспринимаемая приемником как сообщение, образует слово на этом языке. На передачу и обработку информации влияет то, сигналами какой природы отображается одна и та же информация, то есть каким кодом задана одна и та же информация. Простейшим алфавитом, достаточным для записи (представления) информации, является алфавит из двух символов.

Закодировать текст – значит сопоставить ему другой текст в иной знаковой системе. Кодирование применяется при передаче данных – для того, чтобы зашифровать текст от посторонних, чтобы сделать передачу данных более надежной, потому что канал передачи данных может передавать только ограниченный набор символов (например, - только два символа, 0 и 1) и по другим причинам.

При кодировании заранее определяют алфавит, в котором записаны исходные тексты (исходный алфавит) и алфавит, в котором записаны закодированные тексты (коды), этот алфавит называется кодовым алфавитом. В качестве кодового алфавита часто используют двоичный алфавит, состоящий из двух символов (битов) 0 и 1. Слова в двоичном алфавите иногда называют битовыми последовательностями.

Наиболее простой способ кодирования – побуквенный. При побуквенном кодировании каждому символу из исходного алфавита сопоставляется кодовое слово – слово в кодовом алфавите. Иногда вместо «кодовое слово буквы» говорят просто «код буквы». При побуквенном кодировании текста коды всех символов записываются подряд, без разделителей.

Пример 1. Исходный алфавит – алфавит русских букв, строчные и прописные буквы не различаются. Размер алфавита – 33 символа.

Кодовый алфавит – алфавит десятичных цифр. Размер алфавита - 10 символов.

Применяется побуквенное кодирование по следующему правилу: буква кодируется ее номером в алфавите: код буквы А – 1; буквы Я – 33 и т.д.

Внимание: Последовательность 1221 может означать не только АББА, но и КУ (К – 12-я буква в алфавите, а У – 21-я буква). Про такой код говорят, что он НЕ допускает однозначного декодирования

Пример 2. Исходный и кодовый алфавиты – те же, что в примере 1. Каждая буква также кодируется своим номером в алфавите, НО номер всегда записывается двумя цифрами: к записи однозначных чисел слева добавляется 0. Например, код А – 01, код Б – 02 и т.д.

В этом случае кодом текста АББА будет 01020201. И расшифровать этот код можно только одним способом. Для расшифровки достаточно разбить кодовый текст 01020201 на двойки: 01 02 02 01 и для каждой двойки определить соответствующую ей букву.

Такой способ кодирования называется равномерным. Равномерное кодирование всегда допускает однозначное декодирование.

Равномерное кодирование удобно для декодирования. Однако часто применяют и неравномерные коды, т.е. коды с различной длиной кодовых слов. Это полезно, когда в исходном тексте разные буквы встречаются с разной частотой. Тогда часто встречающиеся символы стоит кодировать более короткими словами, а редкие – более длинными. Однако не все неравномерные коды допускают однозначное декодирование.

Есть простое условие, при выполнении которого неравномерный код допускает однозначное декодирование.

Код называется префиксным (самотерминирующимся), если в нем нет ни одного кодового слова, которое было бы началом (по-научному, - префиксом) другого кодового слова.

Код из примера 1 – НЕ префиксный, так как, например, код буквы А (т.е. кодовое слово 1) – префикс кода буквы К (т.е. кодового слова 12, префикс выделен жирным шрифтом).

Код из примера 2 (и любой другой равномерный код) – префиксный: никакое слово не может быть началом слова той же длины.

Теорема (условие Фано). Сформулировать данное условие можно следующим образом: «Ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова». Любой префиксный код (а не только равномерный) допускает однозначное декодирование.

Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода.

Пример 3. Пусть исходный алфавит включает 9 символов: А, Л, М, О, П, Р, У, Ы, -. Кодовый алфавит – двоичный. Кодовые слова:

Кодовые слова выписаны в алфавитном порядке. Видно, что ни одно из них не является началом другого.

Рассмотрим закодированный текст, полученный с помощью заданного кода:

Будем его декодировать таким способом. Двигаемся слева направо, пока не обнаружим код какой-то буквы. 0 – не кодовое слово, а 01 – код буквы М.

Значит, исходный текст начинается с буквы М: код никакой другой буквы не начинается с 01! «Отложим» начальные 01 в сторону и продолжим.

Далее таким же образом находим следующее кодовое слово 00 – код буквы А.

Доведите расшифровку текста до конца самостоятельно. Убедитесь, что он расшифровывается (декодируется) однозначно.

Замечание. В расшифрованном тексте 14 букв. Т.к. в алфавите 9 букв, то при равномерном двоичном кодировании пришлось бы использовать кодовые слова длины 4. Таким образом, при равномерном кодировании закодированный текст имел бы длину 56 символов – в полтора раза больше, чем в нашем примере (у нас 37 символов).

Рассмотрим телефонные номера в традиционной телефонии. Если уже существует номер «112», то номер «1123456» попросту не будет выдан. В случае набора первых трех цифр АТС перестает распознавать и принимать все остальные цифры, соединяя с абонентом по номеру 112. Однако это правило не является действительным для операторов мобильной связи. Связано это с тем, что для набора номера необходимо нажатие соответствующей клавиши, которой, в основном, является клавиша с изображением зеленой телефонной трубки. По этой причине, номера «112», «1120» и «1129876» могут существовать и быть закрепленными за разными адресатами.

Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова».

Условие задачи: дана последовательность, которая состоит из букв «A», «B», «C», «D» и «E». Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.

Буква	A	B	C	D	E
Двоичный эквивалент	00	010	011	101	111

Вопрос: есть ли возможность для одного из символов сократить длину кодового слова таким образом, чтобы сохранить возможность однозначного декодирования? При этом коды остальных символов должны остаться неизменными.

Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов 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.