Как составить равномерный код

Готовлю школьников и студентов гарантированно на 100 баллов из 100 возможных!

Здравствуйте! Меня зовут Александр Георгиевич. Я являюсь профессиональным репетитором в области информационных технологий, математике, баз данных и программирования.

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

Чтобы гарантированно набрать на официальном экзамене ОГЭ или ЕГЭ по информатике высоченный балл берите сотовый телефон, дозванивайтесь до меня и задавайте любые интересующие вопросы.

Несмотря на то, что вы являетесь чрезвычайно занятым человеком, я все-таки настаиваю на том, чтобы вы уделили $2-3$ минуты и ознакомились с отзывами клиентов, которые прошли подготовку под моим началом и добились ошеломительных результатов.

Также своим потенциальным клиентам я предлагаю на выбор $4$ различных территориальных формата, в которых могут проходить наши эффективные занятия:

Рекомендую использовать формат дистанционного обучения! Это выгодно, удобно и эффективно!

Что такое равномерный код и в каких случаях его применяют?

Допустим, вам требуется написать секретное письмо и отправить его своему другу. Вы – человек, проживающий на территории России, следовательно, использующий для написания слов буквы русского алфавита. И, вот, вы решаете закодировать ваше послание двоичным кодом, то есть вместо русских слов ваш друг получит набор цепочек, состоящий из нулей и единиц.

Но ваш соратник без особых проблем сможет провести дешифрацию вашего информационного сообщения, так как вы ему расскажете об алгоритме шифрации/дешифрации.

Чтобы провести кодирование вашего русскоязычного сообщения, необходимо воспользоваться равномерным кодом. В первую очередь нам необходимо вспомнить количество букв в русском алфавите – их $33$. Во вторую – необходимо воспользоваться формулой Хартли, чтобы определить количество бит, необходимых для кодирования одного символа.

Итак, давайте посчитаем, сколько требуется бит информации для кодирования одного символа из русского алфавита: $2^i >= 33$.

Поскольку $i$ – минимальное натуральное число, то $i = 6$. Делаем вывод, что для кодирования нашего сообщения нам требуется равномерный код длиной в $6$ бит. Приведу пример кодирования равномерным кодом первых и последних двух символов русскоязычного алфавита:

Символ	‘А’	‘Б’	…	‘Ю’	‘Я’
Равномерный код	000000	000001	…	011111	100000
Десятичное представление	0	1	…	31	32

В примере выше, мы рассмотрели алфавит русского языка и закодировали абсолютно каждый его символ ровно $6$ битами. Кстати, для кодирования информации мы выбрали минимально возможное количество бит, так как при кодировании нужно стремиться к минимизации используемой памяти.

Что такое неравномерный код и в каких случаях его применяют?

Чтобы глубоко понять смысл неравномерного кодирования давайте представим, что вы работаете на продуктовом складе. Вы хотите оптимизировать свою работу и закодировать название каждого товара минимально возможным количеством бит.

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

Следует понять общий принцип неравномерного кода: суть его в том, чтобы кодировать наиболее часто используемые элементы как можно меньшим количеством бит, так как ими вы оперируете очень часто.

Давайте попробуем закодировать неравномерным кодом часть товаров, находящихся на вашем товарном складе. Предположим, что на вашем складе размещается около $3 000$ различных товаров, но наиболее ходовыми являются хлеб, соль, молоко и сахар.

Данные четыре товара покупают огромными партиями и вы уже устали вести записи в базе данных постоянно вбивая названиях этих продуктов. Давайте применим следующее кодирование:

Хлеб — 00

Соль — 01

Молоко — 10

Сахар — 11

Итого, нам потребовалось два бита информации, чтобы закодировать в бинарном виде наиболее ходовых четыре товара.

А как поступить с наименее популярными товарами, например, муку и перец также достаточно часто покупают. В этом случае данные товары можно запрограммировать так:

То есть мы выделяем на их кодирование уже по $3$ бита информации.

Вы должны уловить общий принцип: чем наименее популярный товар, тем большим количеством бит он будет закодирован.

И все бы хорошо, но есть одна существенная проблема, возникающая при создании неравномерного кода, – проблема с однозначной дешифрацией. Для полного понимания данной проблемы вам следует познакомиться с условием Фано.

Равномерный код vs неравномерный код

Чтобы хорошо понимать в каких ситуациях стоит применять то или иное кодирование, вам нужно очень хорошо разобраться с частотой использования элементов, которые вы планируете закодировать. Если частота применения приблизительно равна у всех элементов, то смело применяйте равномерный код, в других случаях – неравномерный код.

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

Я хочу записаться к вам на индивидуальный урок по информатике и ИКТ

Если у вас остались какие-либо вопросы по рассматриваемой теме, то записывайтесь ко мне на первый пробный урок. Я репетитор-практик, следовательно, на своих уроках я уделяю максимум внимания решению заданий. Из теории лишь записываются самые базовые сведения: определения, тезисы, формулировки теорем и аксиом.

Специально для своих потенциальных клиентов я разработал стабильную многопараметрическую систему, состоящую из 144 вариантов нашего будущего взаимовыгодного сотрудничества. Даже самый взыскательный клиент сумеет выбрать вариант, полностью покрывающий его запросы.

Не откладывайте свое решение в долгий ящик. Я все-таки достаточно востребованный и квалифицированный репетитор, поэтому звоните прямо сейчас – количество ученических мест ограниченно!

1. Предмет и задачи
   информатики. Структура современной
   информатики. Понятие информации.
   Информационные процессы. Непрерывная
   и дискретная информация. Дискретизация.
   Различные подходы к измерению количества
   информации. Формулы Хартли и Шеннона.

Информатика –
наука, изучающая закономерности
получения, хранения, передачи и обработки
информации в природе и человеческом
обществе.

Предмет информатики
составляют следующие понятия:

• аппаратное обеспечение
  средств вычислительной техники;

• программное
  обеспечение средств вычислительной
  техники;

• средства взаимодействия
  аппаратного и программного обеспечения.

Основной задачей
информатики является систематизация
приёмов и методов работы с аппаратными
программными средствами вычислительной
техники.

Задачи информатики состоят
в следующем:

1.      Исследование
информационных процессов любой природы.

2.      Разработка
информационной техники и создание
новейшей технологии переработки
информации на базе полученных результатов
исследования информационных процессов.

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

Структура информатики
:

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

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

Программирование—
деятельность, связанная с разработкой
систем программного обеспечения. Здесь
отметим лишь основные разделы современного
программирования: создание системного
программного обеспечения и создание
прикладного программного обеспечения 

Информационные
системы— раздел
информатики, связанный с решением
вопросов по анализу потоков информации
в различных сложных системах, их
оптимизации, структурировании, принципах
хранения и поиска информации. Известным
примером решения проблемы на глобальном
уровне может служить гипертекстовая
поисковая система WWW. 

Искусственный
интеллект—
область информатики, в которой решаются
сложные проблемы находящиеся на
пересечении с психологией лингвистикой
и другими науками.

Термин информация происходит
от латинского informatio, что означает
разъяснение, изложение. Понятие
«информация» многогранно, и поэтому
строгого общепринятого определения
нет. В широком смысле информация –
это отражение реального мира в виде
сигналов и знаков.

В информатике
понятие  «информация»
означает сведения об объектах и   явлениях
окружающей среды, которые уменьшают
имеющуюся неопределенность, неполноту
знаний о них.

С понятием информации
связаны такие понятия,
как сигнал, сообщение и данные.

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

Сообщение –
информация, представленная в определенной
форме и предназначенная для приема-передачи. 

Данные – информация,
представленная в форме, позволяющей ее
дальнейшую обработку в том числе и
техническими средствами, например,
компьютером.

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

Для  обмена
информацией, ее преобразования и передачи
необходимо наличие источника (носителя)
сообщений, передатчика (кодера), канала
связи, приемника (декодера) и
получателя сообщений

Информация может
поступать как непрерывно во времени,
так и дискретно.

Дискретность (от
лат. discretus — разделённый, прерывистый) —
означает прерывность и противопоставляется
непрерывности. Дискретные величины
принимают не все возможные значения, а
только определённые, и их можно пересчитать.
Дискретное изменение величины происходит
скачками, через определённые промежутки
времени.

Непрерывная величина
может принимать любые значения в
некотором диапазоне, которые могут быть
сколь угодно близки, но всё-таки отличаться
друг от друга. Количество таких значений
бесконечно велико.

В технике непрерывная
информация называется аналоговой,
дискретная — цифровой.

Дискретизация —
это процесс перевода непрерывного аналогового
сигнала в дискретный (обратный процесс
называется восстановлением).
Непрерывный аналоговый сигнал заменяется
последовательностью коротких импульсов
(отсчётов),
величина которых равна значению сигнала
в данный момент времени. Возможность
точного воспроизведения такого
представления зависит от интервала
времени между отсчётами.

Чаще всего применяются
два подхода к измерению информации:

• алфавитный (т.е.
  количество информации зависит от
  последовательности знаков);

• содержательный или вероятностный (т.е.
  количество информации зависит от ее
  содержания).

Алфавитный (объемный)
подход применяется в технике, где
информацией считается любая хранящаяся,
обрабатываемая или передаваемая
последовательность знаков, сигналов.

Этот подход основан
на подсчете числа символов в
сообщении, то есть связан только с
длиной сообщения и не учитывает его
содержания. Но длина сообщения зависит
не только от содержащейся в нем информации.
На нее влияет мощность алфавита
используемого языка.

Множество используемых
в тексте символов называется алфавитом.

Полное количество
символов алфавита  называется
мощностью 
алфавита.

 Чем меньше знаков
в используемом алфавите, тем длиннее
сообщение. Так, например, в алфавите
азбуки Морзе всего три знака (точка,
тире, пауза), поэтому для кодирования
каждой русской или латинской буквы
нужно использовать несколько знаков,
и текст, закодированный по Морзе, будет
намного длиннее, чем при обычной записи.

В вычислительной
технике наименьшей единицей измерения
информации является 1
бит (binary
digit). Один бит соответствует одному знаку
двоичного алфавита, т.е. 0 или 1.

Таким образом, 1бит
= 0 или 1.

Единицы измерения
информации

Для удобства помимо
бита применяются более крупные единицы
измерения информации.

1байт = 8 бит

1Кб (килобайт) = 1024
байт

1Мб (мегабайт) = 1024
Кб

1Гб (гигабайт) = 1024
Мб

1Тб(терабайт)=1024 Гб.

Для того чтобы
подсчитать количество информации в
сообщении необходимо умножить количество
информации, которое несет 1 символ, на
количество символов.

Информационный
объем сообщения (информационная емкость
сообщения) —
количество информации в сообщении,
измеренное в битах, байтах или производных
единицах (Кбайтах, Мбайтах и т.д.).

  Формулы Хартли
и Шеннона.

Американский
инженер Р. Хартли в 1928 г. процесс
получения информации рассматривал как
выбор одного сообщения из конечного
наперёд заданного множества из N
равновероятных сообщений, а количество
информации I, содержащееся в выбранном
сообщении, определял как двоичный
логарифм N.

Формула Хартли:   I = log2N

Допустим, нужно
угадать одно число из набора чисел от
единицы до ста. По формуле Хартли можно
вычислить, какое количество информации
для этого требуется: I = log2100 > 6,644.
Таким образом, сообщение о верно угаданном
числе содержит количество информации,
приблизительно равное 6,644 единицы
информации.

Американский
учёный Клод
Шеннон предложил в 1948 г. другую формулу
определения количества информации,
учитывающую возможную неодинаковую
вероятность сообщений в наборе.

Формула Шеннона: I = — ( p1log2 p1 + p2 log2 p2 + . . . + pN log2 pN), где pi — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений.

Легко заметить, что
если вероятности p1, …, pN равны, то
каждая из них равна 1 / N, и формула
Шеннона превращается в формулу Хартли.

Важно помнить, что
любые теоретические результаты применимы
лишь к определённому кругу случаев,
очерченному первоначальными допущениями.

1. Кодирование информации. Равномерные и неравномерные коды. Условие Фано. Задача построения эффективных кодов. Первая теорема Шеннона. Построение кода Шеннона-Фано. Кодирование Хаффмана.

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

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

Равномерное кодирование

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

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

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

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

Тогда код слова АББА
– это 1221.

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

Неравномерное кодирование

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

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

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

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

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

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

А: 00

М: 01

-: 100

Л: 101

У: 1100

Ы: 1101

Р: 1110

О: 11110

П: 11111

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

На рисунке
изображено бинарное дерево. Его
корень расположен слева. Из каждого
внутреннего узла выходит два ребра.
Верхнее ребро имеет пометку 0, нижнее –
пометку 1. Таким образом, каждому узлу
соответствует слова в двоичном алфавите.
Если слово X является началом (префиксом)
слова Y, то узел, соответствующий слову
X, находится на пути из корня в узел,
соответствующий слову Y. Наши кодовые
слова находятся в листьях дерева.
Поэтому ни одно из них не является
началом другого.

Теорема (условие
Фано). Любой
префиксный код (а не только равномерный)
допускает однозначное декодирование.

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

0100010010001110110100100111000011100

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

0100010010001110110100100111000011100

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

01 00010010001110110100100111000011100

М

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

01
00010010001110110100100111000011100

М  А

И т. д.

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

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

Такое эффективное
кодирование базируется на основной
теореме Шеннона для каналов без шума.

Первая теорема
Шеннона: если
пропускная способность канала без помех
превышает производительность источника
сообщений, т.е. удовлетворяется
условие Ck >Vu, то существует способ
кодирования и декодирования сообщений
источника, обеспечивающий сколь угодно
высокую надежность передачи сообщений.
В противном случае, т.е. если Ck <Vu
Такого способа нет. Таким образом,
идеальное кодирование по Шеннону по
существу представляет собой экономное
кодирование последовательности сообщений
при безграничном укрупнении сообщений.
Такой способ кодирования характеризуется
задержкой сообщений поскольку кодирование
очередной типичной последовательности
может начаться только после получения
последовательности источника
длительностью T, а декодирование —
только когда принята последовательность
из канала той же длительности T. Поскольку
требуется , то идеальное кодирование
требует бесконечной задержки передачи
информации. В этом причина технической
нереализуемости идеального кодирования
по Шеннону. Тем не менее, значение этого
результата, устанавливающего предельные
соотношения информационных характеристик
источника и канала для безошибочной
передачи сообщений, весьма велико.
Исторически именно теорема Шеннона
инициировала и определила развитие
практических методов экономного
кодирования.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #

  12.03.2016138.75 Кб1081.doc

• #
• #

На прошлом уроке мы
узнали:

·     Для
удобства хранения и передачи информации её часто переводят из непрерывной формы
в дискретную. Такой процесс называется дискретизацией.

·     В
процессе дискретизации информация записывается на одном из языков.

·     Алфавитом
языка называются все существующие символы, которые
используются для представления информации на этом языке.

·     Алфавит
характеризуется своей мощностью, это количество символов, которые в него
входят. 

·     Двоичный
алфавит состоит из двух символов. Запись информации с помощью
такого алфавита называется двоичным кодированием.

·     Двоичный
код
– это код информации, получившийся в результате её двоичного кодирования.

·     Любой
алфавит можно привести к двоичному.

Вопросы:

·     Двоичное
кодирование звука.

·     Двоичное
кодирование изображения.

·     Равномерный
и неравномерный коды.

·     Двоичное
кодирование текстовых сообщений методом Хаффмана.

Итак, на прошлом уроке мы
узнали, что любой алфавит можно представить в виде двоичного, для этого каждому
символу исходного алфавита присваивается его двоичный код. Записывая подряд
двоичные коды всех символов, мы можем кодировать текстовые сообщения. Ещё мы
узнали, что двоичный алфавит легко реализовать технически, с помощью наличия
или отсутствия электрического сигнала на некотором участке электрической цепи. Именно
поэтому любая информация на компьютере представлена в виде двоичного кода. Однако
мы знаем, что на компьютере может храниться любая информация, а не только
текстовая или числовая. Как же её представить в виде двоичного кода? Например
звук и изображение. Как мы знаем, они представляются в виде непрерывных
сигналов, разберёмся как же представить эти два вида информации в дискретной
форме.

Начнём с изображения.
Вполне логично, что любое изображение можно разделить на некоторые участки,
каждый из которых имеет свой цвет. Именно так происходит при представлении
изображений на компьютере. Изображение разбивается на маленькие фрагменты,
которые можно назвать точками. Каждое изображение имеет своё разрешение. Оно
состоит из двух цифр, которые разделяются крестиком или двоеточием. Число
слева, означает, на сколько точек делится изображение по горизонтали, а справа
– на сколько по вертикали. Таким образом изображение на компьютере
представляется в виде последовательности точек, каждая из которых имеет свой
цвет. То есть изображение на компьютере можно представить, последовательно
записав цвета всех точек, которые в него входят.

Но как же представить
цвет в виде двоичных кодов? Любой цвет на мониторе компьютера изображается
смешиванием в разных количествах трёх основных цветов: красного, зелёного и
синего. Такое представление цветов называется их RGB-моделью.
По первым буквам названий основных цветов на английском языке, то есть «Rad»,
«Green» и «Blue».
Так, как остальные цвета – это смеси трёх основных цветов в разных количествах,
их можно представить в виде трёх чисел, количеств основных цветов. Эти числа
можно заменить двоичными кодами одинаковой разрядности. Записав эти коды
последовательно, мы получим двоичный код цвета точки. Таким образом изображение
на компьютере представляется в виде списка двоичных кодов одинаковой
разрядности, каждый из которых обозначает цвет одной из точек изображения.

Немного иначе происходит
двоичное кодирование звука. Позже из курса физики вы узнаете, что любой звук
можно представить в виде непрерывной волны. Эту волну можно описать, зависимостью
её амплитуды, то есть громкости звука от времени. Такую зависимость легко
изобразить в виде графика. Чтобы представить звук в виде дискретных сигналов,
время, в течение которого продолжается звук, делится на равные небольшие
промежутки. И на каждом из промежутков заново определяется амплитуда волны, то
есть громкость звука.

Дискретизация
звука

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

Мы знаем, что с помощью
двоичного кодирования в виде последовательности единиц и нулей можно
представить любую информацию на естественном или формальном языке, в том числе
изображение и звук. То есть информацию из любой формы можно представить в виде
двоичного кода, что означает универсальность двоичного кодирования. Это и есть
его главное преимущество. Главный недостаток двоичного кодирования – это
большой размер двоичного кода. Так при кодировании текстового сообщения одному
символу текста может соответствовать несколько символов двоичного кода.

Давайте подумаем, как
можно уменьшить размер двоичного кода, и вообще любого кода. До этого все
двоичные коды, которые мы рассматривали, были равномерными. Равномерным
называется код, который состоит из равных по количеству разрядов кодовых
комбинаций. Так например при кодировании алфавита для каждой буквы мы
использовали двоичные коды с одинаковым количеством разрядов. Однако не все
символы алфавита в текстовом сообщении, встречаются одинаково часто. Поэтому,
для того, чтобы сократить длину двоичного кода мы можем присвоить разным
сигналам коды разной длины. Коды с меньшей разрядностью можно присвоить сигналам,
которые в сообщении встречаются чаще, а коды с большей разрядностью – сигналам,
которые встречаются в сообщении реже. Такой код называется неравномерным, то есть
он состоит из комбинаций различной длины.

Пример неравномерного
кода – азбука Морзе. В ней разным буквам алфавита, соответствует разное
количество сигналов, длинных и коротких. Например буква «А» обозначается всего
двумя сигналами: одним коротким и одним длинным. А твёрдый знак кодируется
пятью сигналами: двумя длинными, одним коротким и двумя длинными.

Рассмотрим один из
методов неравномерного кодирования текстовых сообщений. Он называется методом Хаффмана.
Посмотрим, как работает этот метод, закодировав с его помощью сообщение: «МАМА
МЫЛА РАМУ». Сначала выпишем все символы алфавита, который используется в
сообщении. В данном сообщении используются символы: «М», «А», пробел, «Ы», «Л»,
«Р» и «У». Затем нужно записать, как часто в сообщении встречается каждый из
символов. Буквы «М» и «А» повторяются по четыре раза. Пробел повторяется
дважды. Буквы «Ы», «Л», «Р» и «У» в сообщении встречаются по одному разу. Затем
символы сообщения записываются в порядке убывания частоты появления. У нас они
так и записаны.

Теперь строится дерево частоты
появления символов в сообщении. В начале берутся два символа, которые
встречаются в сообщении реже всех. У нас таких символа четыре, возьмём два
правых, буквы «Р» и «У», соединяем их линией, и складываем их частоту появления
в сообщении. 1 + 1 = 2.

Теперь повторим то же
действие. Реже всех у нас появлялись буквы «Ы» и «Л». Соединим их линиями
сложив частоту появления получим 2.

Теперь снова смотрим где
у нас самая маленькая частота появления. Таких частот у нас три. Пробел
появлялся дважды, двум равны и общие частоты появления символов «Ы» и «Л», и
символов «Р» и «У». Возьмём две правые частоты и объединим их. Их суммарная частота
равна 4.

Снова ищем минимальные
частоты появления. Возьмём две правые частоты и объединим их. Их сумма равна 6.

Теперь объединим две
левые частоты. Их сумма равна 8.

Объединим две оставшиеся
частоты. Их сумма равна 14. Именно четырнадцати равна длина кодируемого
сообщения.

Теперь двигаясь, сверху
вниз присвоим ветвям дерева значения 0 и 1. Ветви, с большей частотой будем
присваивать 1, а ветви с меньшей частотой – 0. Так левой ветви верхнего узла
присвоим 1, а правой – 0.

Затем рассмотрим левый
узел. Там две частоты равны. Поэтому левой ветви присвоим 0, а правой – 1.

Рассмотрим узел, частота
которого равна 6. Частота появления пробела меньше суммарной частоты правой
ветви. Поэтому левой ветви присвоим 0, а правой ветви – 1.

По такому же принципу
пронумеруем оставшиеся ветви дерева.

Теперь, двигаясь по
получившемуся дереву сверху вниз, мы можем записать двоичный код каждого
символа. Так у буквы «М» будет код 10, у буквы «А» – 11, у пробела – 00 и т. д…

Теперь нам остаётся лишь
заменить все символы в сообщении их двоичными кодами. В итоге двоичный код
нашего сообщения будет 101110110010010001011100011011100111. Всего в нём 36
разрядов.

У некоторых из вас может
возникнуть вопрос, а как же расшифровать такое сообщение, ведь в отличии от
равномерного кода мы не знаем точно сколько разрядов занимает каждый символ.
При неравномерном кодировании достаточно, чтобы код никакого из символов не
начинался с кода другого символа. Давайте попробуем расшифровать первые символы
нашего сообщения.

Итак, сообщение
начинается с единицы. С единицы у нас начинаются двоичные коды букв «М» и «А»,
посмотрев на следующий символ 0, мы можем точно определить, что первый символ –
это буква «М». По такому же принципу мы можем определить, что, следующий символ
буква «А» и до конца расшифровать слово «МАМА».

Следующая цифра – 0. С
нуля у нас начинаются коды пяти символов. После него идёт так же 0. С 00 у нас
начинается код пробела. Далее идёт буква «М». Следующая цифра – 0. С нуля у нас
начинаются коды 5 символов. Возьмём следующую цифру. С 01 начинаются коды
четырёх символов. Следующая цифра – 0. С 010 начинаются коды двух символов.
Следующий символ – снова 0. И мы можем однозначно определить, что это буква
«Ы». Так же расшифровывается и остальное сообщение.

Давайте посмотрим,
двоичный код из скольких разрядов получился бы при использовании равномерного
двоичного кодирования. Как мы помним сообщение записано с помощью алфавита
мощностью 7 символов. Определим, разрядность двоичного кода, необходимую для
кодирования одного символа такого алфавита. Как мы помним, для этого необходимо
определить, в какую степень возвести цифру 2, чтобы получить 7. Но цифру семь
мы так получить не можем, поэтому результат необходимо округлить в большую
сторону. Мы можем так получить 8, для этого двойку нужно возвести в 3 степень.
То есть для кодирования одного символа нам потребуется 3-разрядный двоичный
код. Определим, какой код потребуется для кодирования всего сообщения, для
этого нужно разрядность кода одного символа, то есть 3 умножить на длину всего
сообщения, то есть 14. 3 × 14 = 42. То есть при кодировании сообщения нам
потребовался бы 42-разрядный равномерный двоичный код. При использовании
неравномерного кода нам потребовалось всего 36 разрядов, то есть на 6 разрядов
меньше.

Сокращение длины
двоичного кода заметно даже при небольшой длине сообщения. Если длина сообщения
будет больше, например десятки тысяч символов, разница между длинами
равномерного и неравномерного кода тоже увеличится. Когда длина двоичного кода
составляет миллиарды разрядов – разница между равномерным и неравномерным кодом
просто огромна. 

Важно запомнить:

·     Универсальность
двоичного кодирования означает, что его можно применять для кодирования
информации на любом формальном или неформальном языке, а также изображений и
звука.

·     Все
коды можно разделить на равномерные и неравномерные, где равномерный код
состоит из комбинаций равной длины, а неравномерный код состоит из
комбинаций разной длины.

·     Использование
неравномерного кодирования позволяет сократить длину кода.

Введение

В последние годы в заданиях КИМ ЕГЭ по информатике, как в демо-версиях, так и в реальных вариантах, неизменно присутствует задача на кодирование данных следующего типа [1, задание А9]:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д — 11; 2) это невозможно; 3) для буквы Г — 10; 4) для буквы Д — 10

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

Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники [2-5], где соответствующая теория изложена строго и научно, достаточно сложны для понимания. Попробуем разобраться в сути кодирования и декодирования на школьном уровне, то есть так, как можно объяснить ученикам 8-11 классов.

В чём проблема?

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

Пример 1. Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:

М	А	Ы	Л	У	пробел	(1)
00	1	01	0	10	11

Коды букв «сцепляются» в одну битовую строку и передаются, например, по сети:

МАМА МЫЛА ЛАМУ → 0010011100010111010010

Эта цепочка битов приходит в пункт назначения, и тут возникает проблема — как восстановить исходное сообщение (конечно, при условии, что мы знаем код, то есть знаем все пары «символ–кодовое слово», которые использовались при кодировании).

Итак, мы получили 0010011100010111010010. Легко понять, что при использовании кода (1) раскодировать такое сообщение можно самыми разными способами. Например, можно предположить, что оно составлено только из букв А (код 1) и Л (код 0). Тогда получаем

ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ

В общем, ни мамы, ни ламы.

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

Сказанное выше означает, что код (1) НЕ является однозначно декодируемым. Как же определить, является ли заданный код однозначно декодируемым? Этим вопросом мы и займемся.

Равномерные коды

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

Пример 2. Закодируем фразу из примера 1, используя код:

М	А	Ы	Л	У	пробел	(2)
000	001	010	011	100	101

Получаем закодированное сообщение

МАМА МЫЛА ЛАМУ → 000001000001101000010011001101011001000100

Длина этого сообщения — 42 бита вместо 22 в предыдущем варианте, зато его легко разбить на отдельные кодовые слова и раскодировать («_» обозначает пробел):

000 001 000 001 101 000 010 011 001 101 011 001 000 100
 М   А   М   А   _   М   Ы   Л   А   _   Л   А   М   У    

Видим, что равномерные коды неэкономичны (закодированное сообщение в примере 2 почти в два раза длиннее, чем в примере 1), но зато декодируются однозначно.

Неравномерные коды

Для того, чтобы сократить длину сообщения, можно попробовать применить неравномерный код, то есть код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину.

Пример 3. Используем для кодирования фразы из примера 1 следующий код:

М	А	Ы	Л	У	пробел	(3)
01	00	1011	100	1010	11

Получаем

МАМА МЫЛА ЛАМУ → 0100010011011011100001110000011010

Здесь 34 бита. Это, конечно, не 22, но и не 42.

Несложно показать, что эта битовая цепочка декодируется однозначно. Действительно, первая буква — М (код 01), потому что ни одно другое кодовое слово не начинается с 01. Аналогично определяем, что вторая буква — А. Действительно, за 01 следует 00 (код буквы А) и никакое другое кодовое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется не только для кодовых слов 01 и 00, но и кодовых слов всех других букв (проверьте это самостоятельно).

Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.

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

Упражнение. Расшифруйте сообщение, закодированное кодом (3). При расшифровке кода очередной буквы не заглядывайте вперёд!

1000001101011010001001101101110000 

Термины «условие Фано» и «префиксный код» не используются в заданиях ЕГЭ и ГИА, однако для решения этих задача важно, чтобы ученики понимали содержание условия Фано.

Пример 4. Рассмотрим ещё один код

М	А	Ы	Л	У	пробел	(4)
10	00	1101	001	0101	11

Ясно, что он не является префиксным: код буквы А (00) совпадает с началом кода буквы Л (001) и код пробела (11) совпадает с началом кода буквы Ы (11). Закодированное сообщение

МАМА МЫЛА ЛАМУ → 1000100011101101001001100100100101

также имеет длину 34 бита, как и при использовании кода (3). Начнем раскодировать с начала. Ясно, что первой стоит буква М, потому что ни один другой код не начинается с 10. Затем — комбинация 001, которая может быть кодом буквы Л или кодом буквы А (00), за которым следует код буквы Ы или пробела. Получается, что для декодирования сообщения нам нужно «заглядывать вперёд», что очень неудобно.

Попробуем декодировать с конца битовой строки. Последние биты 0101 могут представлять только букву У, следующие 10 — только букву М и т.д. Можно проверить, что теперь сообщение однозначно декодируется с конца! Это происходит потому, что выполняется условие, которое можно назвать «обратным» условием Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование. Таким образом,

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

Обратим внимание на то, что условие Фано (и обратное условие Фано) — это достаточное, но не необходимое условие однозначной декодируемости. Это значит, что

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

Наиболее интересен второй вывод, который сразу вызывает два вопроса: 1) что это за коды? и 2) как в общем случае установить, что код декодируется однозначно? Обсудим это в следующем разделе.

Однозначно декодируемые коды

Пример 5. Рассмотрим код, предназначенный для кодирования сообщений, состоящих только из букв А, Б и В:

А	Б	В	(5)
0	11	010

Так как код буквы А (0) совпадает как с началом, так и с концом кода буквы В (010), для этого кода не выполняются ни прямое, ни обратное условие Фано. Поэтому пока мы не можем с уверенностью сказать, декодируется ли он однозначно.

Закодируем сообщение

АББААВВА → 01111000100100

и попытаемся раскодировать эту строку, используя код (5). В первую очередь, замечаем, что две соседние единицы могут появиться только при использовании буквы Б (код 11), поэтому сразу выделяем две таких группы:

0ББ000100100

Здесь жёлтым фоном выделена уже декодированная часть сообщения. В оставшейся части единица может появиться только в коде буквы В (010), в битовой строке находим две такие группы:

0ББ00ВВ0

Оставшиеся нули — это коды букв А. Анализ алгоритма показывает, что такой код всегда однозначно декодируется.

Полный ответ на вопрос об однозначной декодируемости получил в начале 1960-х годов советский математик Ал.А. Марков, предложивший решение с помощью графов [2]. Продемонстрируем его метод на примере.

Пример 6. Рассмотрим код

А	Б	В	Г	Д	(6)
01	010	011	11	101

Здесь не выполняется ни «прямое», ни «обратное» условие Фано, поэтому возможно, что декодировать сообщение однозначно не удастся. Но утверждать это заранее нельзя.

Следуя методу Ал.А. Маркова, построим граф следующим образом:

1. Определяем все последовательности (строки), которые
      а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
      б) сами не являются кодовыми словами.
   В данном случае это две последовательности:
      0 (начало кода буквы А и конец кода буквы Б) и
      1 (начало кода буквы Г и конец кода буквы Д);
      10 (начало кода буквы Д и конец кода буквы Б);
   последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г;
2. Добавляем к этому множеству {0, 1, 10} пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества {Λ, 0, 1, 10} будут вершинами графа:

   

3. Соединяем вершины дугами (направленными ребрами) по такому правилу: две вершины X и Y соединяются дугой, если последовательная запись кода вершины X, кода некоторой буквы (или нескольких букв) и кода вершины Y дает код ещё одной буквы:

   

   Надпись «W→Z» на дуге, ведущей из X в Y, означает, что если между словами X и Y вставить последовательность букв W (она может состоят из нескольких символов), то полученная цепочка кодов совпадёт с кодом буквы Z. Например, последовательная запись пустой строки (Λ), кода буквы А (01) и цепочки 0 дает цепочку 010 (код буквы Б); поэтому рисуем дугу из вершины «Λ» в вершину «0» и у этой дуги пишем «А→Б», и т.д. Поскольку код буквы Г можно записать как 11 = 1Λ1, у вершины «1» появляется петля «Λ→Г».

Результат Ал.А. Маркова состоит в следующем:

Код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих вершину Λ.

Иначе говоря,

1. если есть сообщение, которое декодируется неоднозначно, то в графе есть цикл, проходящий через вершину Λ;
2. если в графе есть цикл, проходящий через вершину Λ, то можно построить сообщение, которое декодируется неоднозначно; для этого нужно, проходя по циклу, последовательно выписывать коды всех встречающихся вершин и дуг;

С сайта автора можно скачать программу на языке Python 3, которая строит граф Ал.А. Маркова, обнаруживает в нём циклы, проходящие через вершину Λ, и определяет соответствующие им кодовые последовательности, которые декодируются неоднозначно.

В нашем графе есть, по крайней мере, четыре таких цикла:

1. цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
2. цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
3. цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 010101; это сообщение может быть расшифровано как ААА и как БД;
4. цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА;

Кроме того, у вершины «1» есть петля, которая даёт более длинные циклы «из Λ в Λ». Действительно, проходя по стрелкам из вершины Λ, мы приходим в вершину 1, там «вертимся» какое-то количество раз, и возвращаемся обратно в вершину Λ, замыкая цикл. Поэтому неоднозначно декодируется любая последовательность вида 01…101, где многоточие обозначает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА.

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: {Λ, 1}. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

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

Нужно отметить, что на практике применяются, главным образом, префиксные коды, поскольку они позволяют декодировать сообщение по мере его получения, не дожидаясь окончания приёма данных.

Ещё примеры

Пример 7. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код

А — 00, Б — 01, В — 100, Г — 101, Д — 110

выбрав один из вариантов

1) для буквы Д — 11    2) это невозможно
3) для буквы Г — 10    4) для буквы Д — 10

Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соответствующий сообщению ΛГ0Λ1АΛ = 100100; это сообщение может быть расшифровано как ГБА или как ВВ;
2. цикл, соответствующий сообщению ΛГ0Λ1ГΛ = 100110; это сообщение может быть расшифровано как ГБГ или как ВД.

Таким образом, вариант 3 не обеспечивает однозначную декодируемость сообщений.

Построение и анализ графа — дело достаточно трудоемкое и требующее аккуратности. Обычно в таких случаях значительно легче просто подобрать последовательность, которая может быть декодирована двумя разными способами.

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):

1. цикл, соответствующий сообщению ΛД0Λ1АΛ = 100100; это сообщение может быть расшифровано как ДБА или как ВВ;
2. цикл, соответствующий сообщению ΛД0Λ1БΛ = 100101; это сообщение может быть расшифровано как ДББ или как ВГ.

Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.

Пример 8. Оптимизируйте код

А — 11, Б — 10, В — 011, Г — 000, Д — 001,

сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:

1) для буквы Г — 00    2) это невозможно
3) для буквы В — 01    4) для буквы Б — 1

Решение. Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Выводы

В заметке выполнен подробный анализ задачи на кодирование, которая предлагается на ЕГЭ в последние несколько лет. Нужно заметить, что в нём затрагивается вузовский курс дискретной математики. Понятно, что нельзя требовать от школьников знания теорем Ал.А. Маркова об однозначном декодировании, но учителю полезно более глубоко представлять себе эти вопросы, которые можно разбирать на факультативах. В качестве дополнительной литературы по этой теме можно рекомендовать [3-5].

С точки зрения практического подхода, для решения всех известных автору реальных задач подобного типа достаточно найти вариант, при котором выполняется условие Фано или обратное условие Фано (одно из двух!).

Литература

1. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2013 года по информатике и ИКТ (проект).
2. Ал.А. Марков, Введение в теорию кодирования. — М.: Наука, 1982.
3. С.В. Яблонский, Введение в дискретную математику. — М.: Наука, 2000.
4. Л.П. Жильцова. Современные проблемы теории кодирования. Учебно-методические материалы по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». — Нижний Новгород: 2007.
5. Л.П. Жильцова, Т.Г. Смирнова. Основы теории графов и теории кодирования в примерах и задачах: Учебное пособие. — Нижний Новгород: Издательство Нижегородского госуниверситета, 2008.

Автор благодарит М.А. Ройтберга за полезные замечания по материалу статьи и Л.Н. Евич за обсуждении вопросов однозначного декодирования на форуме egekp.unoforum.ru.

Ярлыки: ЕГЭ, информатика, кодирование, Фано