Кодирование

Равномерные и неравномерные двоичные коды - Информация. Измерение информации. Кодирование информации

Кодирование символов обычно предполагает, что каждому символу всегда сопоставляется одинаковое количество битов (например, в кодовой таблице ASCII каждому символу сопоставляется один байт, хранящий порядковый номер того или иного символа в этой таблице). Такой способ кодирования прост и удобен, однако очевидно, что он является не самым оптимальным. Для значительной части символов используются не все биты отведенных под них байтов (часть старших битов — нулевые), а при наличии в тексте только части символов, предусмотренных в таблице ASCII (например, если текст содержит только прописные русские буквы), приходится все равно использовать 8-битный код.

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

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

Обратное условие Фано. Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с окончанием (постфиксом) какого-либо другого, более длинного кода.

Для однозначности декодирования последовательности кодов достаточно выполнения хотя бы одного из двух вышеуказанных условий Фано:

— при выполнении прямого условия Фано последовательность кодов однозначно декодируется с начала;

— при выполнении обратного условия Фано последовательность кодов однозначно декодируется с конца.

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

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

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

Если для заданной последовательности кодов выполняется прямое правило Фано, то её декодирование необходимо вести с начала (слева направо).

Если для заданной последовательности кодов выполняется обратное правило Фано, то её декодирование необходимо вести с конца (справа налево).

При сравнении пары кодов удобно подписывать более короткий код под более длинным, выравнивая эти записи по левому краю — для прямого правила Фано либо по правому краю — для обратного правила Фано.

Задача.

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

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

Для кодирования букв “И”, “Н”, “О” используются следующие 5-битовые кодовые слова:

“И”: 11110, “Н”: 10000, “О”: 01001. Про 5-битовый код для буквы “Ф” известно, что оно начинается с 0 и заканчивается 1.

Укажите кодовое слово для буквы “Ф”.

Решение

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

1. По условию, любые два кодовых слова из используемого набора различаются как минимум в трёх разрядах. Запишем предполагаемый код буквы “Ф”, заменяя неизвестные пока биты звездочками: “Ф”: 0***1.

2. Сравним этот код с известными кодами других букв:

“И”: 11110

“Н”: 10000

“О”: 01001

“Ф”: 0***1

Видим, что начальный и конечный биты кода буквы “Ф” не совпадают с соответствующими битами кодов букв “И” и “Н”, но совпадают (причём оба!) с начальным и конечным битами для буквы “О”.

3. По условию, нужно, чтобы коды “О” и “Ф” различались как минимум в трёх позициях. А такое различие нам могут дать только три внутренних бита.

Тогда для “Ф” вместо звёздочек надо выбрать биты, противоположные соответствующим битам для “О”:

“О”: 01001

“Ф”: 00111

3. Для кодов “Ф” и “О” требуемое условие соблюдено. Проверим его соблюдение для кодов остальных букв:

“И”: 11110 “Н”: 10000

“Ф”: 00111 “Ф”: 00111

3 различия 4 различия

Таким образом, условие соблюдено и для этих кодов.

Ответ: 10110.

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

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

Измерение скорости передачи информации

Скорость передачи информации по каналу связи (обычно рассматривается только передача сообщений¹) вычисляется как количество информации, переданной за одну секунду. Базовой единицей при этом является “бит в секунду” (бит/с, bits per second, bps); может также использоваться размерность “байт в секунду” и производные от нее величины (кб/с, Мб/с и пр.).

Для измерения скорости передачи информации также применяется единица, называемая “бод” (baud). Однако в бодах измеряется не собственно скорость передачи информации, а скорость изменения информационного параметра, являющегося носителем передаваемой информации. В частном случае (при синхронной двоичной передаче) скорость в бодах может быть равна скорости в битах в секунду. Однако, например, в современных модемах при одном изменении уровня несущего сигнала может передаваться больше одного бита информации (например, 4 бита), тогда скорости 2400 бод соответствует скорость передачи информации 9600 бит/с.

Не следует путать эти две величины: бод и бит/с!

Диаграммы процессов (сетевые диаграммы, диаграммы Ганта)

В некоторых задачах, связанных с процессами передачи информации (особенно в случаях, когда один процесс начинается по истечении заданного времени после начала другого) можно существенно облегчить их решение благодаря его наглядному представлению с помощью диаграмм процессов. Такие диаграммы также называют диаграммами Ганта — по имени их изобретателя, американского инженера, механика и специалиста по менеджменту Генри Лоуренса Ганта.

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

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

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

Задача 1.

У Кати есть доступ в Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2²⁰ бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Кати по телефонному каналу со средней скоростью 2¹³ бит в секунду. Сергей договорился с Катей, что она скачает для него данные объёмом 9 Мбайт по высокоскоростному каналу и ретранслирует их Сергею по низкоскоростному каналу.

Компьютер Кати может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Катей данных до полного их получения Сергеем?

Решение

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

Процесс 1: компьютер Кати скачивает файл объёмом в 9 Мб (= 9 ∙ 2²⁰ байт = 9 ∙ 2²³ бит) со скоростью 2²⁰ бит/с.

Длительность процесса 1: 9 ∙ 2²³ / 2²⁰ = 9 ∙ 2³ с.

Процесс 2: компьютер Сергея скачивает файл объёмом в 9 Мб (= 9 ∙ 2²³ бит) со скоростью 2¹³ бит/с.

Длительность процесса 2: 9 ∙ 2²³ / 2¹³ = 9 ∙ 2¹⁰ с.

Начало процесса 2 — через время, равное времени скачивания со скоростью 2²⁰ бит/с информации объёмом 1024 кб (= 1024 ∙ 2¹⁰ байт = 2¹⁰ ∙ 2¹⁰ байт = 2²⁰ байт = 2²³ бит), т.е. через 2²³ / 2²⁰ = 2³ с.

Сетевая диаграмма с надписанными результатами расчётов:

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

Ответ: 9224 с.

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

Задача 2.

Лена скачивает дистрибутив ОС Linux с зарубежного сайта-репозитория, пользуясь односторонним каналом цифровой передачи данных через телевизионное эфирное вещание, обеспечивающим приём информации со скоростью 4 Мбит/с. При этом информация передаётся фрагментами по 10 Мбайт. Для начала передачи каждого фрагмента компьютер Лены должен отправить на сервер сообщение-запрос объёмом 32 кбайт, а после получения фрагмента подтвердить его безошибочный приём отдельным сообщением объёмом 16 кбайт. Для отправки таких сообщений Лена пользуется радиомодемом GPRS, который обеспечивает скорость передачи информации 128 кбит/с. Определить минимально возможное время, за которое Лена сможет скачать файл дистрибутива объёмом 350 Мбайт.

Решение

Принцип решения данной задачи аналогичен предыдущей.

Общий вид сетевой диаграммы:

Процесс 1: передача сообщения-запроса объёмом 32 Кбайт (= 2⁵ ∙ 2¹⁰ байт = 2⁵ ∙ 2¹³ бит) через радиомодем GPRS со скоростью 128 Кбит/с (= 2⁷ ∙ 2¹⁰ бит/с).

Длительность процесса 1: 2⁵ ∙ 2¹³ / 2⁷ ∙ 2¹⁰ = 2¹⁸ / 2¹⁷ = 2 с.

Процесс 2: приём очередного фрагмента файла объёмом 10 Мбайт (= 10 ∙ 2²⁰ байт = 10 ∙ 2²³ бит) через телевизионное эфирное вещание со скоростью 4 Мбит/с (= 2² ∙ 2²⁰ бит/с).

Длительность процесса 2: 10 ∙ 2²³ / 2² ∙ 2²⁰ = 10 ∙ 2²³ / 2²² = 20 с.

Процесс 3: передача сообщения-подтверждения объёмом 16 Кбайт (= 2⁴ ∙ 2¹⁰ байт = 2⁴ ∙ 2¹³ бит) через радиомодем GPRS со скоростью 128 Кбит/с (= 2⁷ ∙ 2¹⁰ бит/с).

Длительность процесса 1: 2⁴ ∙ 2¹³ / 2⁷ ∙ 2¹⁰ = 2¹⁷ / 2¹⁷ = 1 с.

Файл объёмом 350 Мбайт принимается порциями по 10 Мбайт, следовательно, весь процесс приёма информации состоит из 35 элементарных процессов, рассмотренных выше (передача команд + приём очередного фрагмента).

Сетевая диаграмма с надписанными результатами расчётов:

Итого для приёма всего файла потребуется 35 ∙ 23 = 805 с.

Ответ: 805 с.

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

Задача 3.

Данные объёмом 80 Мбайт передаются из пункта А в пункт Б по каналу связи, обеспечивающему скорость передачи данных 2²³ бит в секунду, а затем из пункта Б в пункт В по каналу связи, обеспечивающему скорость передачи данных 2²⁰ бит в секунду. От начала передачи данных из пункта А до их полного получения в пункте В прошло 13 минут.

Через какое время в секундах началась передача данных в пункте Б, т.е. каково время между началом передачи данных из пункта А и началом передачи данных в пункт В? В ответе укажите только число, слово “секунд” или букву “с” добавлять не нужно.

Решение

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

1) Построим диаграмму Ганта для этой задачи:

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

2) Составляем по этой схеме уравнение (t — время задержки между окончанием приема данных из А и началом их передачи в В). Для этого вычисляем время передачи данных из А в Б и из Б в В:

• из А в Б: 80 (Мбайт) / 2²³ (бит в секунду) = 5 ∙ 2²⁷ (бит) / 2²³ (бит в секунду) = 5 ∙ 2⁴ = 80 (с);

• из Б в В: 80 (Мбайт) / 2²⁰ (бит в секунду) = 5 ∙ 2²⁷ (бит) / 2²⁰ (бит в секунду) = 5 ∙ 2⁷ = 640 (с).

Записываем уравнение:

80 + t + 640 = 13 (минут) = 13 ∙ 60 (с), т.е. 720 + t = 780, откуда t = 60.

3) Чтобы найти время от начала передачи данных из Л в Б до начала их передачи из Б в В, нужно к найденному значению t прибавить время передачи данных из А в Б:

80 + 60 = 140 (с).

Ответ: 140.

Задача 4.

Документ объёмом 8 Мбайт можно передать с одного компьютера на другой двумя способами:

А) сжать архиватором, передать архив по каналу связи, распаковать;

Б) передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если:

• средняя скорость передачи данных по каналу связи составляет 2¹⁵ бит в секунду;

• объём сжатого архиватором документа равен 40% от исходного;

• время, требуемое на сжатие документа — 6 секунд, на распаковку — 3 секунды?

В ответе напишите букву А, если способ А быстрее, или Б, если быстрее способ Б. Сразу после буквы напишите, на сколько секунд один способ быстрее другого.

Например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23.

Решение (вариант 1)

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

Вариант А:

Предполагается, что исходный массив информации сначала архивируется (6 секунд). Затем он в уже упакованном виде (40% от исходного объёма) передаётся по каналу связи с заданной средней скоростью, а после этого распаковывается (3 секунды).

Записывается соответствующая цепочка вычислений:

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