Равномерные и неравномерные двоичные коды; условие Фано

Равномерные и неравномерные двоичные коды. Условие Фано При кодировании символов, которое всегда выполняется при работе с текстовыми данными на компьютере, как правило, предполагается, что любому символу соответствует одно и то же число разрядов. К примеру, кодирование в ASCII сопоставляет любому знаку информационный байт, который хранит номер символьного знака в данной таблице. Эта методика кодировки символов не сложная, но всё же не может считаться пределом оптимальности. Существенная часть символьных знаков задействует далеко не все двоичные разряды из предназначенных им байтов, биты старших разрядов просто нулевые. Если в текстовом файле задействованы не все знаки, имеющиеся табличной кодировке (например, сообщение состоит только из прописных русских символов), тем не менее, применяется то же самое восьми битное кодирование. Однако, существует более гибкий и менее объёмный метод кодирования, который называется неравномерным. В таком коде число битов, которые отводятся для кодировки знаков, зависит от числа применяемых в данном конкретном случае разных знаков, иначе говоря, от алфавитной мощности. При этом кодирование разных знаков, имеет различную длину в двоичном формате. Это кодирование возможно оптимизировать путём учёта частоты повторяемости разных знаков и давать постоянно применяемым символам наиболее маленькие коды. Основное правило при неравномерном кодировании заключается в обеспечении возможности однозначного и правильного декодирования закодированной таким образом информации. Это декодирование должно выполняться путём поочерёдного выделения и распознавания из непрерывной цепи нулей и единиц кодов отдельного символа. Для обеспечения однозначного декодирования текстовой информации, закодированной с применением неравномерного кодирования, такие коды следует присваивать знакам согласно условиям Фано. Принцип Фано Прямое условие Фано формулируется следующим образом: неравномерный код возможно однозначно декодировать, если код любого символа не имеет совпадений с начальными знаками (префиксом) любого другого кода, имеющего больший размер. Подобный код имеет название «префиксный». Обратное условие Фано формулируется так: неравномерный код возможно однозначно декодировать, при условии, что нет кодов, которые имеют совпадения с окончанием (постфиксом) любого другого кода, имеющего большую длину. Этот код носит название «постфиксный». Для однозначного декодирования кодовой последовательности, необходимо и достаточно соблюдение по меньшей мере любого вышеназванного условия Фано. Причём если выполняется прямое условие Фано, то кодовую последовательность возможно однозначно декодировать с начала. Если же выполняется обратное условие Фано, то последовательность кодов возможно однозначно декодировать с конца. Когда необходимо решить проблему с неравномерным кодированием и декодированием, то вначале требуется выполнить анализ кодов, заданных по условию задачи. Если исходные коды соответствуют прямому условию Фано, то его и следует применять при поиске решения. В случае не выполнения прямого условия Фано, необходимо проанализировать коды на соответствие обратному условию Фано и, в случае его выполнения, применять именно его. Затем, учитывая какое условие Фано соблюдено для данного кодового набора, нужно выбрать соответствующее направление декодирования этого кода. А именно, если для данной кодовой последовательности соблюдается прямое условие Фано, тогда процесс декодирования нужно производить с начала (слева направо). Если же для данной кодовой последовательности соблюдается обратное условие Фано, тогда процесс декодирования следует выполнять с конца (справа налево). В случае выполнения обеих условий Фано, процесс декодирования возможно производить в любом направлении. Итог должен быть один и тот же. Проверка условий Фано Для проверки выполнения прямого условия Фано, необходимо поочерёдно выполнять сравнение всех пар кодов, соблюдая такие условия: Когда пара кодов, подлежащих сравнению, имеет одинаковый размер, то хватит проверки на совпадение. Если пара кодов, подлежащих сравнению, имеет разный размер, то следует проверить на совпадение более короткого кода с начальными знаками более длинного кода (так проверяется выполнение прямого условия Фано) или с окончанием более длинного кода (так проверятся выполнение обратного условия Фано). Для последнего случая проверка кодов может выполняться таким образом. Вначале записывается более длинный код. Далее снизу под ним располагается более короткий код так, чтобы было совпадение по расположению знаков. Причём, если проверяется прямое условие Фано, то по левой позиции знаков, а если обратное условие Фано, то по правой позиции знаков. Пример проверки Имеем заданные коды символов: A – 10, B – 11, C – 011. Необходимо проверить выполнение условий Фано для такого кодового набора. Алгоритм решения можно представить в следующем виде: Выполняем сравнение кодов символов A и B. По длине коды одинаковые (у обеих длина два бита), но сами коды разные. Отсюда следует вывод, что выполнено и прямое и обратное условие Фано для пары символов A и B. Выполняем сравнение символов A и C. Они имеют коды различной длины. Выполняем проверку соответствия прямому условию Фано: C: 0 1 1 A: 1 0 Кодирование символа A (оно короче) не совпадает с начальными кодами символа C (который длиннее). Это означает, что для данной пары символов выполнено прямое условие Фано. Выполняем проверку обратного условия Фано: C: 0 1 1 A: 1 0 Кодирование символа A (оно короче) не совпадает с окончанием кода символа (его код длиннее). Делаем вывод о выполнении обратного условия Фано для этих символов. Выполняем сравнение кодов символов B и C. По длине их коды так же отличаются. Выполняем проверку на выполнение прямого условия Фано: C: 0 1 1 B: 1 1 Код символа B (он короче) не совпадает с начальными знаками кода символа C (его код длиннее). Делаем вывод, что прямое условие Фано для этих символов выполнено. Выполняем проверку исполнения обратного условия Фано: C: 0 1 1 B: 1 1 Код символа B (он короче) совпадает с окончанием кода символа C (его код длиннее). То есть обратное условие Фано для этих символов не выполнено. Формирование итогов. Прямое условие Фано исполнено для всех пар символов, обратное условие не исполнено для одной пары, то есть не может применяться и для всего набора символов. Условие Фано Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода. Пример неравномерного кода, выполняющего условие Фано: О Л В 10 11 Тогда слово «ОЛОВО» кодируется как «1100110» и имеет только один вариант дешифровки. Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода. Для возможности однозначного декодирования достаточно выполнения одного из условий — или прямого, или обратного. Заметим, что существуют варианты неравномерного кодирования, для которых оба условия нарушены, и тем не менее они однозначно декодируются. 1. Задание По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: A – 101, B – 010, С – 00, D – 1001, E – 111, F – 0110. Укажите кратчайшее возможное кодовое слово для буквы N. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 2. Задание По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: A – 111, B – 000, С – 01, D – 1101, E – 100, F – 0010. Укажите кратчайшее возможное кодовое слово для буквы L. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 3. Задание По каналу связи передаются сообщения, содержащие только восемь букв: К, Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 001, Н – 100, Р – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКОСОС? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 4. Задание По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 101, В – 010, И – 0. Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 5. Задание Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова , , ,  Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. 6. Задание По каналу связи передаются сообщения, содержащие только восемь букв: А, Е, И, О, П, Р, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 00, И – 1100, Р – 1110. Какое наименьшее количество двоичных знаков потребуется для кодирования слова РЕПЕТИТОР? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 7. Задание Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, К решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово ; для буквы Б – кодовое слово . Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е, К? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений. 8. Задание По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – , Б – , И – . Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 9. Задание По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б – , К – , Л – . Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. 10. Задание По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г – , И – , Т – . Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Передача информации Передача информации — это информационный процесс, при котором производится перемещение информации через пространство и/или через время от одного субъекта (источника информации) к другому субъекту (приемнику информации). При этом информация передается в форме документа (записи на некотором физическом носителе) либо в форме сообщения (последовательности сигналов по каналу связи). В процессе передачи информации возможны помехи: случайные искажения физических характеристик канала связи, которые являются носителем информации, либо повреждения физического носителя. Наличие таких помех вынуждает применять различные способы борьбы с ними, в том числе многократное резервирование документов либо многократную пересылку сообщений, применение специальных методов контроля и коррекции ошибок (контрольная сумма, код Хемминга и пр.). Измерение скорости передачи информации Скорость передачи информации по каналу связи (обычно рассматривается только передача сообщений1) вычисляется как количество информации, переданной за одну секунду. Базовой единицей при этом является “бит в секунду” (бит/с, bits per second, bps); может также использоваться размерность “байт в секунду” и производные от нее величины (кб/с, Мб/с и пр.). Для измерения скорости передачи информации также применяется единица, называемая “бод” (baud). Однако в бодах измеряется не собственно скорость передачи информации, а скорость изменения информационного параметра, являющегося носителем передаваемой информации. В частном случае (при синхронной двоичной передаче) скорость в бодах может быть равна скорости в битах в секунду. Однако, например, в современных модемах при одном изменении уровня несущего сигнала может передаваться больше одного бита информации (например, 4 бита), тогда скорости 2400 бод соответствует скорость передачи информации 9600 бит/с. Не следует путать эти две величины: бод и бит/с! Диаграммы процессов (сетевые диаграммы, диаграммы Ганта) В некоторых задачах, связанных с процессами передачи информации (особенно в случаях, когда один процесс начинается по истечении заданного времени после начала другого) можно существенно облегчить их решение благодаря его наглядному представлению с помощью диаграмм процессов. Такие диаграммы также называют диаграммами Ганта — по имени их изобретателя, американского инженера, механика и специалиста по менеджменту Генри Лоуренса Ганта. Типичная диаграмма Ганта представляет собой отрезки или прямоугольные полоски, размещённые вдоль горизонтальной шкалы времени, где каждый отрезок соответствует отдельной задаче (подзадаче) или процессу. Начало, конец и длина каждого такого отрезка соответствуют началу, концу и длительности соответствующего процесса, а сами такие отрезки обычно располагаются друг за другом со сдвигом по вертикали. В современных диаграммах Ганта, построенных при помощи специальных программ — систем управления проектами, кроме временных зависимостей, также отображаются зависимости (связи) между задачами. Например, самым распространённым типом такой зависимости является связь “Окончание — Начало”, когда очередная задача начинается после окончания предыдущей: Для некоторых задач удобно рисовать подобную диаграмму, изображающую два процесса (или более) и размечая на ней временные отметки их начал и окончаний. Применение диаграммы Ганта для решения задач будет рассмотрено ниже. Разбор типовых задач Задача 1. У Кати есть доступ в Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 220 бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Кати по телефонному каналу со средней скоростью 213 бит в секунду. Сергей договорился с Катей, что она скачает для него данные объёмом 9 Мбайт по высокоскоростному каналу и ретранслирует их Сергею по низкоскоростному каналу. Компьютер Кати может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Катей данных до полного их получения Сергеем? Решение Создаётся набросок сетевой диаграммы, соответствующей условию задачи. Рассматриваются два процесса передачи, осуществляемые с разной скоростью, из которых один процесс начинается спустя заданное время после начала другого. Общий вид диаграммы имеет вид: Процесс 1: компьютер Кати скачивает файл объёмом в 9 Мб (= 9 ∙ 220 байт = 9 ∙ 223 бит) со скоростью 220 бит/с. Длительность процесса 1: 9 ∙ 223 / 220 = 9 ∙ 23 с. Процесс 2: компьютер Сергея скачивает файл объёмом в 9 Мб (= 9 ∙ 223 бит) со скоростью 213 бит/с. Длительность процесса 2: 9 ∙ 223 / 213 = 9 ∙ 210 с. Начало процесса 2 — через время, равное времени скачивания со скоростью 220 бит/с информации объёмом 1024 кб (= 1024 ∙ 210 байт = 210 ∙ 210 байт = 220 байт = 223 бит), т.е. через 223 / 220 = 23 с. Сетевая диаграмма с надписанными результатами расчётов: Благодаря сетевой диаграмме нетрудно определить, какие величины нужно суммировать для вычисления общей длительности процесса (т.е. времени, прошедшего с момента начала скачивания Катей данных до полного их получения Сергеем). Ответ: 9224 с. Следует не забывать приводить все величины, указанные в условии задачи, к одной размерности! Например, если скорость передачи информации задана в битах в секунду, то все значения объёмов информации нужно преобразовать в биты. Задача 2. Лена скачивает дистрибутив ОС Linux с зарубежного сайта-репозитория, пользуясь односторонним каналом цифровой передачи данных через телевизионное эфирное вещание, обеспечивающим приём информации со скоростью 4 Мбит/с. При этом информация передаётся фрагментами по 10 Мбайт. Для начала передачи каждого фрагмента компьютер Лены должен отправить на сервер сообщение-запрос объёмом 32 кбайт, а после получения фрагмента подтвердить его безошибочный приём отдельным сообщением объёмом 16 кбайт. Для отправки таких сообщений Лена пользуется радиомодемом GPRS, который обеспечивает скорость передачи информации 128 кбит/с. Определить минимально возможное время, за которое Лена сможет скачать файл дистрибутива объёмом 350 Мбайт. Решение Принцип решения данной задачи аналогичен предыдущей. Общий вид сетевой диаграммы: Процесс 1: передача сообщения-запроса объёмом 32 Кбайт (= 25 ∙ 210 байт = 25 ∙ 213 бит) через радиомодем GPRS со скоростью 128 Кбит/с (= 27 ∙ 210 бит/с). Длительность процесса 1: 25 ∙ 213 / 27 ∙ 210 = 218 / 217 = 2 с. Процесс 2: приём очередного фрагмента файла объёмом 10 Мбайт (= 10 ∙ 220 байт = 10 ∙ 223 бит) через телевизионное эфирное вещание со скоростью 4 Мбит/с (= 22 ∙ 220 бит/с). Длительность процесса 2: 10 ∙ 223 / 22 ∙ 220 = 10 ∙ 223 / 222 = 20 с. Процесс 3: передача сообщения-подтверждения объёмом 16 Кбайт (= 24 ∙ 210 байт = 24 ∙ 213 бит) через радиомодем GPRS со скоростью 128 Кбит/с (= 27 ∙ 210 бит/с). Длительность процесса 1: 24 ∙ 213 / 27 ∙ 210 = 217 / 217 = 1 с. Файл объёмом 350 Мбайт принимается порциями по 10 Мбайт, следовательно, весь процесс приёма информации состоит из 35 элементарных процессов, рассмотренных выше (передача команд + приём очередного фрагмента). Сетевая диаграмма с надписанными результатами расчётов: Итого для приёма всего файла потребуется 35 ∙ 23 = 805 с. Ответ: 805 с. Лучше разделить описываемый процесс передачи информации на отдельные повторяющиеся этапы, чтобы вначале определить длительность отдельного такого этапа, а затем вычислить общую длительность процесса.