WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     || 2 |
-- [ Страница 1 ] --

В. В. Лидовский ТЕОРИЯ ИНФОРМАЦИИ В. В. ЛИДОВСКИЙ ТЕОРИЯ ИНФОРМАЦИИ Допущено учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для

студентов высших учебных заведений, обучающихся по направлению 654600 — Информатика и вычислительная техника, специальности 220200 — Автоматизированные системы обработки информации и управления МОСКВА 2004 Лидовский В. В. Теория информации: Учебное пособие. — М.: Компания Спутник+, 2004. — 111 с. — ISBN 5-93406-661-7.

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

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

Библиогр. 23 назв. Ил. 28.

РЕЦЕНЗЕНТЫ: Кафедра “Управления и моделирова ния систем” Московской государственной академии при боростроения и информатики (зав. кафедрой — д-р. тех.

наук С. Н. Музыкин), доцент Н. Я. Смирнов Для подготовки издания использовались системы plain TEX, AMS-Fonts, PICTEX и TreeTEX ББК 32. Л Введение Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со студентами-третьекурсниками в течении лет на кафедре “Моделирование систем и информационные технологии” «МАТИ» — Российского государственного технологического универси тета им. К. Э. Циолковского.

Настоящее пособие достаточно полно освещает основные положе ния теории информации в соответствии с Государственным образова тельным стандартом РФ от 1995 г. по специальности “Автоматизиро ванные системы обработки информации и управления” (220200). Содер жание некоторых глав (2, 9, 33–36) пособия выходит за рамки стандар та для означенной специальности, но затронутые в них темы актуальны и органично вписываются в материал пособия.

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

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

В главах 10–18 рассматриваются способы сжатия информации.

Рассмотрены как статистические методы (Шеннона-Фэно, Хаффмена, арифметический), так и словарные методы Лемпела-Зива. Для стати стических методов приведены варианты адаптивных алгоритмов коди рования. Приводятся формулы для оценки предельной степени сжатия информации. Обзорно рассматриваются способы сжатия информации с потерями и типы файлов, содержащих сжатые данные.

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

В главах 20–27 рассматриваются способы построения и использо вания избыточных кодов для защиты от помех. Приводятся фундамен тальные характеристики таких кодов. Для понимания материала 23-й главы необходимо знакомство с начальными элементами теории групп.

Главы 28–32 посвящены вопросам теории защиты информации.

Рассматриваются как классические криптографические системы, так и системы, построенные на идеях Диффи и Хеллмана. Кратко матема тический фундамент этих методов излагается в Приложении Д.

В заключительных главах рассмотрены некоторые вопросы ис пользования информации в Internet.

Используемые обозначения, не определенные явно в основном ма териале, приводятся в Приложении Е.

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

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

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

1. Предмет и основные разделы кибернетики Теория информации рассматривается как существенная часть ки бернетики.

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

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

Родоначальниками кибернетики (датой ее рождения считается 1948 год, год соответствующей публикации) считаются американские ученые Норберт Винер (Wiener, он — прежде всего) и Клод Шеннон (Shannon, он же основоположник теории информации).

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

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

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

В СССР значительный вклад в развитие кибернетики внесли ака демики Берг А. И. и Глушков В. М.

В нашей стране в 50-е годы кибернетика была объявлена лженаукой и была практически запрещена, что не мешало, однако, развиваться всем ее важным разделам (в том числе и теории информации) вне связи с обобщающим словом “кибернетика”. Это было связано с тем, что сама по себе кибернетика представляет собой род философии, в кое чем конфликтной с тогдашней официальной доктриной (марксистско ленинской диалектикой).

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

Часто теорию информации вообще рассматривают как одну из ветвей теории вероятностей или как часть теории связи. Таким образом, пред мет “Теория информации” весьма узок, т.к. зажат между “чистой” ма тематикой и прикладными (техническими) аспектами теории связи.

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

2. Формальное представление знаний При формальном представлении знаний каждому описываемому объекту или понятию ставится в соответствие некоторый числовой код.

Связи между кодируемыми сущностями также представляются кодами (адресами и указателями). Для такого перевода неформальных данных в формальный, цифровой вид должны использоваться специальные та блицы, сопоставляющие кодируемым сущностям их коды и называе мые таблицами кодировки. Простейший пример такой таблицы — это ASCII (American Standard Code for Information Interchange), использу емая повсеместно с вычислительной техникой. Она сопоставляет печат ным и управляющим символам (управляющими являются, например, символы, отмечающие конец строки или страницы) числа от 0 до 127.

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

var i: byte;

begin for i := 32 to 126 do write(i:6, chr(i):2);

writeln end.

На практике обычно используют не сам исходный ASCII, а так на зываемый расширенный ASCII (ASCII+), описывающий коды 256 сим волов (от 0 до 255). Первые 128 позиций расширенного ASCII совпадают со стандартом, а дополнительные 128 позиций определяются произво дителем оборудования или системного программного обеспечения. Кро ме того, некоторым управляющим символам ASCII иногда назначают другое значение.

Хотя таблицы кодировки используются для формализации инфор мации, сами они имеют неформальную природу, являясь мостом между реальными и формальными данными. Например, коду 65 в ASCII со ответствует заглавная латинская буква A, но не конкретная, а любая.

Этому коду будет соответствовать буква A, набранная жирным пря мым шрифтом, и буква A, набранная нежирным с наклоном вправо на 9.5 шрифтом, и даже буква A готического шрифта. Задача сопостав ления реальной букве ее кода в выбранной таблице кодировки очень сложна и частично решается программами распознания символов (на пример, Fine Reader).

Упражнение Каков код букв W и w в ASCII?

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

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

При переводе непрерывной информации в дискретную важна так называемая частота дискретизации, определяющая период (T = 1/) между измерениями значений непрерывной величины (см. рис. 1).

Исходный сигнал.................

............

..

....

.........................

.

...............

.........

• •....

.......

.

.

.

.

......

.

......

.

.

.

.

.

.

......

.

.

.....

.

.....

.

.

.

...

...

.

........

.

.

.

.....

.....

.

.

.....

.....

........

.

.

....

....

.

....

• •. • t.

.

.....

.....

.....

.

.

.

.....

.....

......

..

..

..

.

......

.....

......

.

.

.

.

..

..

..

.

......

......

...........................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................

.........

....

...

.

...

...

.

.

.

.

.

.....

.....

.....

.

.....

.

......

......

..

..

..

..

.....

..........

......

..............................

...............................

...

..

..

..

..

..

..

..

.....

..........

.........

.

.

.....

.

.

•....

. •.

....

.

.

.

.

.....

.

.....

.

.

.

.

.....

.

.

.

.

.

.

.

.

.

.

.

.

.

.

......

T...............

...............

......

..........................

..................

...

.

.......

.

•.....................

• Дискретизированный сигнал • • • • • t.

.

.

.

.

.

.

.

.

.

.

.

.

.

...........................................................................................................................................................................................................................................................

.........................................................................................................................................................................................................................................................

...

.

.

..

..

..

....

....

.....

.

.

.

.

.

....

.....

......

.........................

..........................

...

.

.

.

.

.

.

.

....

.....

.....

• • T • • Рис. Чем выше частота дискретизации, тем точнее происходит перевод непрерывной информации в дискретную. Но с ростом этой частоты рас тет и размер дискретных данных, получаемых при таком переводе, и, следовательно, сложность их обработки, передачи и хранения. Однако для повышения точности дискретизации необязательно безграничное увеличение ее частоты. Эту частоту разумно увеличивать только до предела, определяемого теоремой о выборках, называемой также теоре мой Котельникова или законом Найквиста (Nyquist).

Любая непрерывная величина описывается множеством наложен ных друг на друга волновых процессов, называемых гармониками, определяемых функциями вида A sin(t + ), где A — это амплитуда, — частота, t — время и — фаза.

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

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

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

Устройства для преобразования непрерывной информации в дис кретную обобщающе называются АЦП (аналого-цифровой преобразо ватель) или ADC (Analog to Digital Convertor, A/D), а устройства для преобразования дискретной информации в аналоговую — ЦАП (циф ро-аналоговый преобразователь) или DAC (Digital to Analog Convertor, D/A).

Упражнение В цифровых магнитофонах DAT частота дискретизации — 48 КГц.

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

4. Хранение, измерение, обработка и передача информации Для хранения информации используются специальные устройства памяти. Дискретную информацию хранить гораздо проще непрерыв ной, т. к. она описывается последовательностью чисел. Если предста вить каждое число в двоичной системе счисления, то дискретная ин формация предстанет в виде последовательностей нулей и единиц. При сутствие или отсутствие какого-либо признака в некотором устройстве может описывать некоторую цифру в какой-нибудь из этих последо вательностей. Например, позиция на дискете описывает место цифры, а полярность намагниченности — ее значение. Для записи дискрет ной информации можно использовать ряд переключателей, перфокар ты, перфоленты, различные виды магнитных и лазерных дисков, элек тронные триггеры и т. п. Одна позиция для двоичной цифры в описа нии дискретной информации называется битом (bit, binary digit). Бит служит для измерения информации. Информация размером в один бит содержится в ответе на вопрос, требующий ответа “да” или “нет”. Не прерывную информацию тоже измеряют в битах.

Бит — это очень маленькая единица, поэтому часто используется величина в 8 раз большая — байт (byte), состоящая из двух 4-битных полубайт или тетрад. Байт обычно обозначают заглавной буквой B или Б. Как и для прочих стандартных единиц измерения для бита и бай та существуют производные от них единицы, образуемые при помощи приставок кило (K), мега (M), гига (G или Г), тера (T), пета (P или П) и других. Но для битов и байтов они означают не степени 10, а степени двойки: кило — 210 = 1024 103, мега — 220 106, гига — 230 109, тера — 240 1012, пета — 250 1015. Например, 1 KB = 8 Кbit = 1024 B = 8192 bit, 1 МБ = 1024 КБ = 1 048 576 Б = 8192 Кбит.

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

Каждая АВМ предназначена только для узкого класса задач, на пример, интегрирования или дифференцирования. Если на вход такой АВМ подать сигнал, описываемый функцией f(t), то на ее выходе по явится сигнал F (t) или f (t). АВМ работают очень быстро, но их точ ность ограничена и не может быть увеличена без аппаратных пере делок. Программа для АВМ — это электрическая схема из заданного набора электронных компонент, которую нужно физически собрать.

Бывают еще и гибридные вычислительные машины, сочетающие в себе элементы как ЦВМ, так и АВМ.

На рис. 2 изображена схема передачи информации.

Кодированием, например, является шифровка сообщения, декоди рованием — его дешифровка.

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

КОДИРОВАНИЕ КАНАЛ СВЯЗИ ДЕКОДИРОВАНИЕ ИСТОЧНИК-ПЕРЕДАТЧИК-ПРИЕМНИК-ПОЛУЧАТЕЛЬ.

Pис. Скорость передачи информации измеряется в количестве передан ных за одну секунду бит или в бодах (baud): 1 бод = 1 бит/сек (bps).

Производные единицы для бода такие же как и для бита и байта, на пример, 10 Kbaud = 10240 baud.

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

Упражнение Сколько бит в одном килобайте?

5. Базовые понятия теории информации Информация — нематериальная сущность, при помощи которой с любой точностью можно описывать реальные (материальные), вирту альные (возможные) и понятийные сущности. Информация — проти воположность неопределенности.

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

Шум — это помехи в канале связи при передаче информации.

Кодирование — преобразование дискретной информации одним из следующих способов: шифрование, сжатие, защита от шума.

Общая схема передачи информации изображена на рис. 3.

Емкость канала связи без шума можно приблизительно вычислить, зная максимальную частоту волновых процессов, допустимую в этом канале. Можно считать, что скорость передачи данных может быть не меньше, чем эта частота. Например, при предельной частоте, рав ной 1000 Гц, можно обеспечить скорость передачи данных не меньше 1 Кбод.

Примеры каналов связи и связанных с ними предельных частот:

телеграф — 140 Гц, телефон — до 3.1 КГц, короткие волны (10–100 м) — 3–30 МГц, УКВ (1–10 м) — 30–300 МГц, спутник (сантиметровые волны) — до 30 ГГц, оптический (инфракрасный диапазон) — 0.15– 400 ТГц, оптический (видимый свет) — 400–700 ТГц, оптический (уль трафиолетовый диапазон) — 0.7–1.75 ПГц.

исходная шумозащитное шифрование сжатие информация кодирование канал шум связи декодирование полученная шумозащитных - дешифровка - распаковка -.

информация кодов Рис. Типичные современные каналы: телеграфный и телефонный. Пер спективные, внедряемые ныне: оптоволоконный (терабоды) и цифровой телефонный (ISDN, Integrated Services Digital Networks) — 57–128 Кбод.

В реальных оптоволоконных системах скорость гораздо ниже тео ретических пределов (редко превосходит 1–10 Гбод).

Наиболее широко пока используются телефонные линии связи.

Здесь достигнута скорость более 50 Кбод!

6. Способы измерения информации Понятие количества информации естественно возникает, напри мер, в следующих типовых случаях:

1. Равенство вещественных переменных a = b, заключает в себе ин формацию о том, что a равно b. Про равенство a2 = b2 можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следу ет второе, но не наоборот. Равенство a3 = b3 несет в себе информацию по объему такую же, как и первое;

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

3. М.о. некоторой сл.в. содержит в себе информацию о самой сл.в.

Для сл.в., распределенной по нормальному закону, с известной диспер сией знание м.о. дает полную информацию о сл.в.;

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

В 1865 г. немецкий физик Рудольф Клаузиус ввел в статистиче скую физику понятие энтропии или меры уравновешенности системы.

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

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

Термин “энтропия” используется Шенноном по совету патриарха ком пьютерной эры фон Неймана, отметившего, что полученные Шенноном для теории связи формулы для ее расчета совпали с соответствующи ми формулами статистической физики, а также то, что “точно никто не знает” что же такое энтропия.

Упражнение Какое из соотношений несет в себе больше информации x = 5 или x > 3?

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

Для д.с.в. X и Y, заданных законами распределения P (X = Xi) = pi, P (Y = Yj) = qj и совместным распределением P (X = Xi, Y = Yj) = pij, количество информации, содержащейся в X относительно Y, равно pij I(X, Y ) = pij log2.

piqj i,j Для непрерывных сл. в. X и Y, заданных плотностями распреде ления вероятностей pX(t1), pY (t2) и pXY (t1, t2), аналогичная формула имеет вид pXY (t1, t2) I(X, Y ) = pXY (t1, t2) log2 dt1dt2.

pX(t1)pY (t2) R Очевидно, что 0, при i = j P (X = Xi, X = Xj) = P (X = Xi), при i = j и, следовательно, pi I(X, X) = pi log2 = - pi log2 pi.

pipi i i Энтропия д.с.в. X в теории информации определяется формулой H(X) = HX = I(X, X).

Свойства меры информации и энтропии:

1) I(X, Y ) 0, I(X, Y ) = 0 X и Y независимы;

2) I(X, Y ) = I(Y, X);

3) HX = 0 X — константа;

4) I(X, Y ) = HX + HY - H(X, Y ), где H(X, Y ) = - pij log2 pij;

i,j 5) I(X, Y ) I(X, X). Если I(X, Y ) = I(X, X), то X — функция от Y.

1) Логарифмированием из очевидного для всех x неравенства ex-1 x (равенство устанавливается только при x = 1) получается неравенство x- x- ln x или log2 x.

ln piqj - piqj pij -I(X, Y ) = pij log2 pij = pij i,j ln i,j pi qj - pij 1 - piqj - pij i j i,j = = = = 0, ln 2 ln 2 ln i,j т.е. I(X, Y ) = 0 только при pij = piqj для всех i и j, т.е. при независимости X и Y. Если X и Y независимы, то pij = piqj и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X, Y ) = 0;

2) Следует из симметричности формул относительно аргументов;

3) Если HX = 0, то все члены суммы, определяющей HX, должны быть нули, что возможно только тогда и только тогда, когда X — константа;

4) Из четырех очевидных соотношений pij = pi, pij = qj, j i HX = - pi log2 pi = - pij log2 pi, i i,j HY = - qj log2 qj = - pij log2 qj j i,j получается HX + HY - H(X, Y ) = pij(log2 pij - log2 qj - log2 pi) = I(X, Y );

i,j 5) Нужно доказать I(X, Y ) = HX + HY - H(X, Y ) HX или HY - H(X, Y ) 0.

HY - H(X, Y ) = - pij log2 qj + pij log2 pij = pij log2(pij/qj), i,j i,j i,j но pij = P (X = Xi, Y = Yj) qj = P (Y = Yj), а значит аргументы у всех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше 0.

Если HX = I(X, X) = I(X, Y ), то для каждого i pij равно либо qj, либо 0. Но из pij = P (X = Xi, Y = Yj) = P (X = Xi/Y = Yj)P (Y = Yj) {qj, 0} следует P (X = Xi/Y = Yj) {0, 1}, что возможно только в случае, когда X — функция от Y.

При независимости сл. в. X и Y одна из них ничем не описывает другую, что и отражается в том, что для таких сл.в. I(X, Y ) = 0.

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

Пусть заданы д. с. в. X1, X2 и Y. X1 и X2 — количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а Y = X1 +X2.

Найти I(Y, X1), I(X1, X1), I(Y, Y ).

Законы распределения вероятностей для д.с.в. X1 и X2 совпадают, т.к. кости одинаковые и без изъянов.

X1 1 2 3 4 5 p 1/6, т.е. при j = 1...6 qj = P (X1 = j) = 1/6.

Закон распределения вероятностей для д.с.в. Y, P (Y = i) = P (X1 + X2 = i), i = 2...12, вследствие того, что X1, X2 — независимы и поэтому P (X1 = n, X2 = m) = P (X1 = n)P (X2 = m), будет pi = P (X1 + X2 = i) = P (X1 = n)P (X2 = m) = 1/36.

n+m=i n+m=i 1 n,m 6 1 n,m Таблицы, определяющие Y :

\X 1 2 3 4 5 X 1 2 3 4 5 6 2 3 4 5 6 7 3 4 5 6 7 8 4 5 6 7 8 9 5 6 7 8 9 10 6 7 8 9 10 11 12, Y = X1 + X2 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 5 4 3 2 p /36 /36 /36 /36 /36 /36 /36 /36 /36 /36 /36, т.е. при i = 2...12, pi = P (Y = i) = (6 - |7 - i|)/36.

Закон совместного распределения вероятностей д.с.в. X1 и Y будет pij = P (Y = i, X1 = j) = P (Y = i/X1 = j)P (X1 = j), например, P (Y = 2, X1 = 1) = P (Y = 2/X1 = 1)P (X1 = 1) = = P (X2 = 1)P (X1 = 1) = 1/36.

В общем случае получится 1/36, при 1 i - j 6, pij = P (Y = i, X1 = j) = 0, иначе.

\Y 2 3 4 5 6 7 8 9 10 11 X 1 1 1 1 1 1 /36 /36 /36 /36 /36 /36 0 0 0 0 2 0 /36 1/36 1/36 1/36 1/36 1/36 0 0 0 3 0 0 /36 1/36 1/36 1/36 1/36 1/36 0 0 4 0 0 0 /36 1/36 1/36 1/36 1/36 1/36 0 5 0 0 0 0 /36 1/36 1/36 1/36 1/36 1/36 6 0 0 0 0 0 /36 1/36 1/36 1/36 1/36 1/ Тогда pij I(Y, X1) = pij log2 = piqj j=1 1 i-j 1 = log2 = 36 6pi j=1 1 i-j 7 8 11 1 1 1 1 = ( log2 + log2 + · · · + log2 + log2 ) = 36 6pi i=3 6pi 6pi i=7 6pi i=2 i= 1 6 6 6 6 6 = ((log2 +log2 +· · ·+log2 )+· · ·+(log2 +log2 +· · ·+log2 )) = 36 1 2 6 6 5 1 3 = (2 log2 6 + 4 log2 3 + 6 log2 2 + 8 log2 + 10 log2 + 6 log2 1) = 36 2 = (2 + 2 log2 3 + 4 log2 3 + 6 + 8 log2 3 - 8 + 10 log2 3 + 10 - 10 log2 5)/36 = = (10 + 24 log2 3 - 10 log2 5)/36 0.69 бит/символ.

I(X1, X1) = I(X2, X2) = - qj log2 qj = log2 6 = 1 + log2 j= 2.58 бит/сим.

I(Y, Y ) = - pi log2 pi = i= 1 = (2 log2 36 + 4 log2 18 + 6 log2 12 + 8 log2 9 + 10 log2 + 6 log2 6) = 36 = (4+4 log2 3+4+8 log2 3+12+6 log2 3+16 log2 3+20+20 log2 3-10 log2 5+ + 6 + 6 log2 3)/36 = (46 + 60 log2 3 - 10 log2 5)/36 3.27 бит/сим.

Здесь 0 < I(Y, X1) = I(Y, X2) < I(X1, X1) = I(X2, X2) < I(Y, Y ), что соответствует свойствам информации.

Подчекнутый член 2 log2 6 = I(X1, X1)/18 в расчете I(X1, Y ) со ответствует информации о двух случаях из 36, когда Y = 2 и Y = 12, которые однозначно определяют X1. Шесть случаев, когда Y = 7, не несут никакой информации об X1, что соответствует подчеркнутому члену 6 log2 1 = 0.

Расчеты можно проводить, используя 4-е свойство информации, через энтропию.

H(Y, X1) = - pij log2 pij = log2 36 = 2(1 + log2 3) = 2HX i,j 5.17 бит/сим.

I(Y, X1) = HX1 + HY - H(X1, Y ) = HY - HX1 3.27 - 2.58 = 0. бит/сим.

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

Рассмотрим более простой пример. Пусть д. с. в. X равна количе ству очков, выпавших на игральной кости, а д. с. в. Y равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X, Y ) и I(Y, Y ).

Составим законы распределения вероятностей д.с.в. X и Y.

X 1 2 3 4 5 6 Y 0 p 1/6 p 1/ Таким образом, при i = 1...6 pi = P (X = i) = 1/6 и, соответствен но, при j = 0...1 qj = P (Y = j) = 1/2.

Составим также закон совместного распределения вероятностей этих д.с.в.

X 1 3 5 2 4 6 1 3 5 2 4 Y 0 0 0 1 1 1 1 1 1 0 0 p 1/6 0, если i + j — четно, Таким образом, pij = P (X = i, Y = j) = 1/6, иначе.

pij I(X, Y ) = pij log2 piqj = 61 log2 2 = 1 бит/сим.

i,j I(Y, Y ) = - qj log2 qj = 21 log2 2 = 1 бит/сим.

j= Точное количество выпавших очков дает точную информацию о четности, т.е. 1 бит. Из I(X, Y ) = I(Y, Y ) = 1 бит/сим и 3-го свойства информации следует, что информация об X полностью определяет Y, но не наоборот, т.к. I(X, Y ) = I(X, X) = 1+log2 3 2.58 бит/сим. Дей ствительно, Y функционально зависит от X, а X от Y функционально не зависит.

Расчеты через энтропию будут следующими H(X, Y ) = - pij log2 pij = log2 6 = 1 + log2 3 = HX, i,j I(X, Y ) = HX + HY - HX = HY = 1 бит/сим.

Упражнение Найти энтропию д.с.в. X, заданной распределением X 1 2 3 4 5 6 7 p 0.1 0.2 0.1 0.05 0.1 0.05 0.3 0.1.

Упражнение Значения д. с. в. X1 и X2 определяются подбрасыванием двух идеаль ных монет, а д.с.в. Y равна сумме количества “гербов”, выпавших при подбрасывании этих монет. Сколько информации об X1 содержится в Y ?

Упражнение Сколько информации об X1 содержится в д.с.в. Z = (X1 + 1)2 - X2, где независимые д. с. в. X1 и X2 могут с равной вероятностью принимать значение либо 0, либо 1? Найти HX1 и HZ. Каков характер зависимо сти между X1 и Z?

Упражнение Д. с. в. X1, X2 — зависимы и распределены также как и соответству ющие д.с.в. из предыдущей задачи. Найти I(X1, X2), если совместное распределение вероятностей X1 и X2 описывается законом X1 0 0 1 X2 0 1 0 p 1/3 1/6 1/6 1/3.

Упражнение Д. с. в. X1 и X2 определяются подбрасыванием двух идеальных тет раэдров, грани которых помечены числами от 1 до 4. Д. с. в. Y рав на сумме чисел, выпавших при подбрасывании этих тетраэдров, т. е.

Y = X1 + X2. Вычислить I(X1, Y ), HX1 и HY.

Упражнение Подсчитать сколько информации об X1 содержится в д.с.в. Z = X1X2, а также HZ. Д.с.в. X1 и X2 берутся из предыдущего упражнения.

Упражнение Д.с.в. X1 может принимать три значения -1, 0 и 1 с равными вероятно стями. Д.с.в. X2 с равными вероятностями может принимать значения 0, 1 и 2. X1 и X2 — независимы. Y = X1 +X2. Найти I(X1, Y ), I(X2, Y ), HX1, HX2, HY.

Упражнение Найти энтропии д. с. в. X, Y, Z и количество информации, содержа щейся в Z = X + Y относительно Y. X и Y — независимы и задаются распределениями X 0 1 3 4 Y -2 p 1/8 1/8 1/4 1/2 p 3/8 5/8.

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

Рассмотрим пример (скачки). В заезде участвуют 4 лошади с рав ными шансами на победу, т.е. вероятность победы каждой лошади рав на 1/4. Введем д. с. в. X, равную номеру победившей лошади. Здесь HX = 2. После каждого заезда по каналам связи достаточно будет передавать два бита информации о номере победившей лошади. Ко дируем номер лошади следующим образом: 1—00, 2—01, 3—10, 4—11.

Если ввести функцию L(X), которая возвращает длину сообщения, ко дирующего заданное значение X, то м. о. ML(X) — это средняя дли на сообщения, кодирующего X. Можно формально определить L через две функции L(X) = len(code(X)), где code(X) каждому значению X ставит в соответствие некоторый битовый код, причем, взаимно одно значно, а len возвращает длину в битах для любого конкретного кода.

В этом примере ML(X) = HX.

Пусть теперь д.с.в. X имеет следующее распределение 3 1 P (X = 1) =, P (X = 2) =, P (X = 3) = P (X = 4) =, 4 8 т.е. лошадь с номером 1 — это фаворит. Тогда 3 4 1 1 19 HX = log2 + log2 8 + log2 16 = - log2 3 1.186 бит/сим.

4 3 8 8 8 Закодируем номера лошадей: 1—0, 2—10, 3—110, 4—111, — т. е. так, чтобы каждой код не был префиксом другого кода (подобное коди рование называют префиксным). В среднем в 16 заездах 1-я лошадь должна победить в 12 из них, 2-я — в 2-х, 3-я — в 1-м и 4-я — в 1-м. Таким образом, средняя длина сообщения о победителе равна (1 12 + 2 2 + 3 1 + 3 1)/16 = 1.375 бит/сим или м. о. L(X). Дей ствительно, L(X) сейчас задается следующим распределением вероят ностей: P (L(X) = 1) = 3/4, P (L(X) = 2) = 1/8, P (L(X) = 3) = 1/8.

Следовательно, 3 2 3 ML(X) = + + = = 1.375 бит/сим.

4 8 8 Итак, ML(X) > HX.

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

То, что энтропия Шеннона соответствует интуитивному представ лению о мере информации, может быть продемонстрировано в опыте по определению среднего времени психических реакций. Опыт заклю чается в том, что перед испытуемым человеком зажигается одна из N лампочек, которую он должен указать. Проводится большая серия испытаний, в которых каждая лампочка зажигается с определенной ве N роятностью pi ( pi = 1), где i — это номер лампочки. Оказывается, i среднее время, необходимое для правильного ответа испытуемого, про N порционально величине энтропии - pi log2 pi, а не числу лампочек i= N, как можно было бы подумать. В этом опыте предполагается, что чем больше информации будет получено человеком, тем дольше будет время ее обработки и, соответственно, реакции на нее.

Упражнение Найти энтропию д. с. в. X и среднюю длину каждого из приведенных кодов для этой д.с.в.

X 1 3 4 5 p 0.4 0.2 0.1 0.2 0. code1(X) 000 001 010 011 code2(X) 0 100 101 110 code3(X) 00 01 110 10 code4(X) 0 10 1110 110 1111.

Упражнение Д.с.в. X равна количеству “гербов”, выпавших на двух идеальных мо нетках. Найти энтропию X. Придумать минимальный код для X, вы числить его среднюю длину и обосновать его минимальность.

Упражнение Д.с.в. X задана распределением P (X = 2n) = 1/2n, n = 1, 2,... Найти энтропию этой д.с.в. Придумать минимальный код для X, вычислить его среднюю длину и обосновать его минимальность.

Упражнение Про д.с.в. X известно, что ее значениями являются буквы кириллицы.

Произведен ряд последовательных измерений X, результат которых — “ТЕОРИЯИНФОРМАЦИИ”. Составить на основании этого результа та приблизительный закон распределения вероятностей этой д. с. в. и оценить минимальную среднюю длину кодов для X.

9. Семантическая информация В 50-х годах XX века появились первые попытки определения аб солютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, це ликом построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности суще ствования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Приме ром одной из таких мер является функция inf(s) = - log2 p(s), где s — это предложение, смысловое содержание которого измеряется, p(s) — вероятность истинности s. Вот некоторые свойства этой функции меры:

1) если s1 s2 (из s1 следует s2) — истинно, то inf(s1) inf(s2);

2) inf(s) 0;

3) если s — истинно, то inf(s) = 0;

4) inf(s1s2) = inf(s1) + inf(s2) p(s1 · s2) = p(s1)p(s2), т. е.

независимости s1 и s2.

Значение этой функция-меры больше для предложений, исключа ющих большее количество возможностей. Пример: из s1 — “a > 3” и s2 — “a = 7” следует, что s2 s1 или inf(s2) inf(s1);

ясно, что s исключает больше возможностей, чем s1.

Для измерения семантической информации также используется функция-мера cont(s) = 1 - p(s). Ясно, что cont(s) = 1 - 2-inf(s) или inf(s) = - log2(1 - cont(s)).

Упражнение Вычислить inf(s) и cont(s) предложения s1, про которое известно, что оно достоверно на 50%, и предложения s2, достоверность которого 25%.

10. Сжатие информации Цель сжатия — уменьшение количества бит, необходимых для хра нения или передачи заданной информации, что дает возможность пере давать сообщения более быстро и хранить более экономно и оператив но (последнее означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, ес ли скорость распаковки данных выше скорости считывания данных с носителя информации). Сжатие позволяет, например, записать больше информации на дискету, “увеличить” размер жесткого диска, ускорить работу с модемом и т.д. При работе с компьютерами широко использу ются программы-архиваторы данных формата ZIP, GZ, ARJ и других.

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

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

Доказано [20], что среднее количество бит, приходящихся на одно кодируемое значение д. с. в., не может быть меньшим, чем энтропия этой д.с.в., т.е. ML(X) HX для любой д.с.в. X и любого ее кода.

Кроме того, доказано [20] утверждение о том, что существует такое кодирование (Шеннона-Фэно, Fano), что HX ML(X) - 1.

Рассмотрим д.с.в. X1 и X2, независимые и одинаково распределен ные. HX1 = HX2 и I(X1, X2) = 0, следовательно, H(X1, X2) = HX1 + HX2 - I(X1, X2) = 2HX1.

Вместо X1 и X2 можно говорить о двумерной д. с. в. X = (X1, X2).

Аналогичным образом для n-мерной д.с.в. X = (X1, X2,..., Xn) можно получить, что HX = nHX1.

Пусть L1(X) = L(X)/n, где X = (X1, X2,..., Xn), т.е. L1(X) — это количество бит кода на единицу сообщения X. Тогда ML1(X) — это среднее количество бит кода на единицу сообщения при передаче беско нечного множества сообщений X. Из ML(X) - 1 HX ML(X) для кода Шеннона-Фэно для X следует ML1(X) - 1/n HX1 ML1(X) для этого же кода.

Таким образом, доказана основная теорема о кодировании при от сутствии помех, а именно то, что с ростом длины n сообщения, при кодировании методом Шеннона-Фэно всего сообщения целиком среднее количество бит на единицу сообщения будет сколь угодно мало отли чаться от энтропии единицы сообщения. Подобное кодирование практи чески не реализуемо из-за того, что с ростом длины сообщения трудоем кость построения этого кода становится недопустимо большой. Кроме того, такое кодирование делает невозможным отправку сообщения по частям, что необходимо для непрерывных процессов передачи данных.

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

По выбранному значению > 0 можно выбрать такое s, что если разбить все сообщение на блоки длиной s (всего будет n/s блоков), то кодированием Шеннона-Фэно таких блоков, рассматриваемых как еди ницы сообщения, можно сделать среднее количество бит на единицу сообщения б ольшим энтропии менее, чем на. Действительно, пусть Y = (Y1, Y2,..., Yn/s), Y1 = (X1, X2,..., Xs), Y2 = (Xs+1, Xs+2,..., X2s) и т. д., т. е. Yi = (Xs(i-1)+1, Xs(i-1)+2,..., Xsi). Тогда HY1 = sHX1 и sML1(Y1) = ML(Y1) HY1 + 1 = sHX1 + 1, следовательно, ML1(Y1) HX1 + 1/s, т.е. достаточно брать s = 1/. Минимум s по заданному может быть гораздо меньшим 1/.

Пример. Пусть д.с.в. X1, X2,... Xn независимы, одинаково распре делены и могут принимать только два значения P (Xi = 0) = p = 3/4 и P (Xi = 1) = q = 1/4 при i от 1 до n. Тогда 3 4 1 HXi = log2 + log2 4 = 2 - log2 3 0.811 бит/сим.

4 3 4 Минимальное кодирование здесь — это коды 0 и 1 с длиной 1 бит каж дый. При таком кодировании количество бит в среднем на единицу со общения равно 1. Разобьем сообщение на блоки длины 2. Закон распре деления вероятностей и кодирование для 2-мерной д.с.в. X = (X1, X2) — X 00 01 10 p 9/16 3/16 3/16 1/ code(X) 0 10 110 L(X) 1 2 3 3.

Тогда при таком минимальном кодировании количество бит в сред нем на единицу сообщения будет уже 9 3 3 1 ML1(X) = 1 + 2 + 3 + 3 /2 = = 0.84375, 16 16 16 16 т.е. меньше, чем для неблочного кодирования. Для блоков длины 3 ко личество бит в среднем на единицу сообщения можно сделать 0.823, для блоков длины 4 — 0.818 и т.д.

Все изложенное ранее подразумевало, что рассматриваемые д.с.в.

кодируются только двумя значениями (обычно 0 и 1). Пусть д.с.в. ко дируются m значениями. Тогда для д.с.в. X и любого ее кодирования верно, что ML(X) HX/ log2 m и ML1(X) HX1/ log2 m. Кроме того, существует кодирование такое, что ML(X) - 1 HX/ log2 m и ML1(X) - 1/n HX1/ log2 m, где n = dim(X).

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

11. Простейшие алгоритмы сжатия информации Метод Шеннона-Фэно состоит в следующем, значения д.с.в. распо лагают в порядке убывания их вероятностей, а затем последовательно делят на две части с приблизительно равными вероятностями, к коду первой части добавляют 0, а к коду второй — 1.

Для предшествующего примера получим X p code(X) 00 9/16 01 3/16 10 3/16 11 1/16 111, ML1(X) = 27/32 = 0.84375 бит/сим.

Еще один пример. Код составляется после сортировки, т. е. после перестановки значений B и C.

X p code(X) A 0.4 B 0.2 11 ML(X) = ML1(X) = 1.6 бит/сим, C 0.4 10, HX = log2 5 - 0.8 1.523 бит/сим.

Метод Хаффмена (Huffman) разработан в 1952 г. Он более практи чен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно. Код строится при помощи двоичного (бинарного) дерева. Вероятности значений д.с.в. приписыва ются его листьям;

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

в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраня ются. После постройки корня нужно приписать каждой из ветвей, исхо дящих из родительских узлов, значения 0 или 1. Код каждого значения д. с. в. — это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.

Для методов Хаффмена и Шеннона-Фэно каждый раз вместе с соб ственно сообщением нужно передавать и таблицу кодов. Например, для случая из примера 2 нужно сообщить, что коду 10 соответствует сим вол C, коду 0 — A и т.д.

Построим коды Хаффмена для значений д.с.в. из двух предыдущих примеров.

X 00 01 10 9 p /16 3/16 /16 1/ code(X) 0 10 110 ML1(X) = ML(X)/2 = 27/32 = 0.84375 бит/сим.

X A B C p 0.4 0.2 0. 0. code(X) 0 10 ML1(X) = ML(X) = 1.6 бит/сим.

Упражнение Вычислить ML1(X) для блочного кода Хаффмена для X. Длина блока — 2 бита. Д.с.в. X берется из последнего примера.

Упражнение Вычислить HX и ML(X) для кодов Хаффмена и Шеннона-Фэно для X.

Д.с.в. X задается следующим распределением вероятностей:

X 1 2 3 4 p /18 1/6 1/6 1/6 1/9.

12. Арифметическое кодирование Алгоритм кодирования Хаффмена, в лучшем случае, не может пе редавать на каждый символ сообщения менее одного бита информации.

Предположим, известно, что в сообщении, состоящем из нулей и еди ниц, единицы встречаются в 10 раз чаще нулей. При кодировании ме тодом Хаффмена и на 0 и на 1 придется тратить не менее одного бита.

Но энтропия д. с. в., генерирующей такие сообщения 0.469 бит/сим.

Метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит. Хотелось бы иметь такую схе му кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование, разработанное в 70-х годах XX века.

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

объединение этих отрезков должно образовывать отрезок [0,1], а их длины должны быть пропорциональны вероятностям соответству ющих значений д. с. в. Алгоритм кодирования заключается в постро ении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, при надлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все воз можные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и де сятичную точку, но нужен еще один специальный код-маркер, сигна лизирующий о конце сообщения. Отрезки строятся так. Если имеется отрезок для сообщения длины n-1, то для построения отрезка для сооб щения длины n, разбиваем его на столько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно так же как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины n.

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

Эффективность арифметического кодирования растет с ростом длины сжимаемого сообщения (для кодирования Хаффмена или Шеннона-Фэно этого не происходит). Хотя арифметическое кодирование дает обычно лучшее сжатие, чем кодирование Хаффмена, оно пока используется на практике сравнительно редко, т.к. оно появилось гораздо позже и тре бует больших вычислительных ресурсов.

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

Пример арифметического кодирования. Пусть д.с.в. X может при нимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответ ственно. Сопоставим значению 0 отрезок [0,2/3], а 1 — [2/3,1]. Тогда для д.с.в. X, dim(X) = 3, HX = HX/3 = log2 3 - 2/3 0.9183 бит/сим., таблица построения кодов — Интервалы и коды Вероятность Код Хаффмена 26 31 111[, 1] = 0.11111 /27 27 8 26 15 11[8, 1] 110[, ] = 0.1111 /27 9 9 27 22 8 7 101[, ] = 0.111 /27 27 9 2 8 2 22 3 1[, 1] 10[2, ] 100[, ] = 0.11 /27 3 3 9 3 27 16 2 5 011[, ] = 0.101 /27 27 3 2 4 16 1 01[4, ] 010[, ] = 0.1 /27 9 3 9 27 8 4 3 001[, ] = 0.011 /27 27 9 2 4 8 1 0[0, ] 00[0, ] 000[0, ] = 0.01 /27 11.

3 9 27 ML1(X) = 65/81 0.8025 бит/сим. (арифметическое), ML1(X) = 76/81 0.9383 бит/сим. (блочный Хаффмена), ML1(X) = ML(X) = 1 бит/сим. (Хаффмена).

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

Получение исходного сообщения из его арифметического кода про исходит по следующему алгоритму.

Шаг 1. В таблице для кодирования значений д. с. в. определяется ин тервал, содержащий текущий код, — по этому интервалу одно значно определяется один символ исходного сообщения. Если этот символ — это маркер конца сообщения, то конец.

Шаг 2. Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.

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

X1 1 2 3 4 X2 1 2 5 6 p 1/3 1/3 1/6 1/6, p 0.2 0.1 0.3 0.25 0.15, X3 1 4 9 16 25 36 p 0.1 0.1 0.1 0.3 0.1 0.1 0.2, X4 -2 -1 0 1 p 1/3 1/4 1/5 1/6 1/20.

Упражнение Вычислить длины кодов Хаффмена и арифметического для сообщения AAB, полученного от д. с. в. X со следующим распределением вероят ностей P (X = A) = 1/3, P (X = B) = 2/3.

Упражнение Составить арифметический код для сообщения BAABC, полученного от д.с.в. X со следующим распределением вероятностей P (X = A) = 1/4, P (X = B) = 1/2, P (X = C) = 1/4. Каков будет арифметический код для этого же сообщения, если X распределена по закону P (X = A) = 1/3, P (X = B) = 7/15, P (X = C) = 1/5?

Упражнение Д. с. в. X может принимать три различных значения. При построении блочного кода с длиной блока 4 для X необходимо будет рассмотреть д. с. в. X — выборку четырех значений X. Сколько различных значе ний может иметь X? Если считать сложность построения кода про порциональной количеству различных значений кодируемой д. с. в., то во сколько раз сложнее строить блочный код для X по сравнению с неблочным?

Упражнение Составить коды Хаффмена, блочный Хаффмена (для блоков длины 2 и 3) и арифметический для сообщения ABAAAB, вычислить их длины.

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

13. Адаптивные алгоритмы сжатия. Кодирование Хаффмена Является практичным, однопроходным, не требующим передачи таблицы кодов. Его суть в использовании адаптивного алгоритма, т.е.

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

В начале работы алгоритма дерево кодирования содержит толь ко один специальный символ, всегда имеющий частоту 0. Он необхо дим для занесения в дерево новых символов: после него код символа передается непосредственно. Обычно такой символ называют escape символом ( ESC ). Расширенный ASCII кодируют каждый символ 8 битным числом, т.е. числом от 0 до 255. При построении дерева кодиро вания необходимо для возможности правильного декодирования как-то упорядочивать структуру дерева. Расположим листья дерева в порядке возрастания частот и затем в порядке возрастания стандартных кодов символов. Узлы собираются слева направо без пропусков. Левые ветви помечаются 0, а правые — 1.

Рассмотрим процесс построения кодов по адаптивному алгорит му Хаффмена для сообщения ACCBCAAABC, которое соответствует выборке 10-и значений д.с.в. X из 2-го примера на построение неадап тивного кода Хаффмена:

1 входные длина № код 1/A 1 1/C данные кода дерева 0/ ESC A ’A’ 8 1/A C 0’C’ 9 0/ ESC C 1 1 3 B 00’B’ 10 C 1 1 1 2/C A 001 3 2/C A 01 2 1/A A 01 2 0/ ESC 1/B B 001 3 0/ ESC 1/A C 01 5 6 2 3 3/C 3/C 3/C 1 1 1/B 2/A 3/A 0/ ESC 1/A 0/ ESC 1/B 0/ ESC 1/B 8 4 4/A 4/A 1 3/C 3/C 0/ ESC 1/B 0/ ESC 2/B.

Здесь L1(ACCBCAAABC) = 4.1 бит/сим. Если не использовать сжатия, то L1(ACCBCAAABC) = 8 бит/сим. Для рассматриваемой д.с.в. ранее были получены значения ML1(X) = 1.6 бит/сим и HX 1.523 бит/сим. Но с ростом длины сообщения среднее количество бит на символ сообщения при адаптивном алгоритме кодирования будет мало отличаться от значения, полученного при использовании неадап тивного метода Хаффмена или Шеннона-Фэно, т. к. алфавит символов ограничен и полный код каждого символа нужно передавать только один раз.

Теперь рассмотрим процесс декодирования сообщения ’A’0’C’ ’B’1001010100101. Здесь и далее символ в апостофах означает восемь бит, представляющих собой запись двоичного числа, номера символа, в таблице ASCII+. В начале декодирования дерево Хаффмена содержит только escape-символ с частотой 0. С раскодированием каждого нового символа дерево заново перестраивается.

входные № символ данные дерева ’A’ A 0’C’ C 1 C 00’B’ B.........

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

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

На рис. 4 приведен пример упорядоченного дерева Хаффмена.

.

7 E 3 1 2 2 A B C D.

Рис. 9 E 4 2 2 2 D B C A Рис. Если дерево кодирования упорядоченно, то при изменении веса су ществующего узла дерево не нужно целиком перестраивать — в нем достаточно лишь поменять местами два узла: узел, вес которого нару шил упорядоченность, и последний из следующих за ним узлов меньше го веса. После перемены мест узлов, необходимо пересчитать веса всех их узлов-предков.

Например, если в дереве на рис. 4 добавить еще две буквы A, то узлы A и D должны поменяться местами (см. рис. 5).

21 11 11 10 E E 5 4 7 A 2 2 2 2 5 C D B C A 2 D B 10 E 5 A 2 C 2 D B Рис. Если добавить еще две буквы A, то необходимо будет поменять местами сначала узел A и узел, родительский для узлов D и B, а затем узел E и узел-брат E (рис. 6).

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

Процесс работы адаптивного алгоритма Хаффмена с упорядочен ным деревом можно изобразить следующей схемой:

входные длина № метод код данные кода дерева получения A ’A’ 8 1 добавление узла 1/A C 0’C’ 9 2 добавление узла 0/ ESC C 01 2 3 упорядочение B 00’B’ 10 4 добавление узла C 1 1 5 не меняется 1 1/A A 01 2 6 не меняется A 01 2 7 упорядочение 1/C A 11 2 8 упорядочение 0/ ESC B 101 3 9 не меняется C 11 3 4 5 1 2/C 2 2 2/C 3/C 3/C 1/A 1 1 0/ ESC 1/A 1/A 2/A 0/ ESC 1/B 0/ ESC 1/B 0/ ESC 1/B 7 8 4 4 3/C 4/A 4/A 1 1 3/A 3/C 3/C 0/ ESC 1/B 0/ ESC 1/B 0/ ESC 2/B.

Здесь получится L1(ACCBCAAABC) = 4.1 бит/сим.

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

Упражнение Закодировать сообщения “AABCDAACCCCDBB”, “КИБЕРНЕТИКИ” и “СИНЯЯ СИНЕВА СИНИ”, используя адаптивный алгоритм Хафф мена с упорядоченным деревом. Вычислить длины в битах исходного сообщения в коде ASCII+ и его полученного кода.

Упражнение Распаковать сообщение ’A’0’F’00’X’0111110101011011110100101, полу ченное по адаптивному алгоритму Хаффмена с упорядоченным дере вом, рассчитать длину кода сжатого и несжатого сообщения в битах.

14. Адаптивное арифметическое кодирование Для арифметического кодирования, как и для кодирования методом Хаффмена, существуют адаптивные алгоритмы. Реализация одного из них запатентована фирмой IBM.

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

4 5 6 7 8 9 10 11 12 13 1 1 1 1 1 1 1 1 1 4 20 60 420 1120 5040 16800 46200 277200...

...........

...........

...........

...........

...........

..............

...................................

.....

...............

.

...........

...........

...........

...........

...........

...........

...................................

...........

...........

.................

...........

...........

...........

...........

.1...1.....1.....1.1.....1...1...1...1.1..... E...........

...........

...........

...........

.................

.......................

...........

...................

..

...........

...........

...........

............

...........

...........

.................

...

....................

...........

...........

...........

............

...........

...........

...........

....................

.................

...........

...........

............

...........

.1.1.2.3.3.4.4.4.4.4. C...........

....................

...........

...........

.................

............

...........

...........

...

...........

......................

.....

...........

...........

...........

............

...............

...........

...........

........................

...........

...........

...............

............

...........

...........

....

...........

....................

...........

...............

............

..1.1.1.1.2..2..2..2.2.3. B...............

...........

...........

....................

...........

...........

...........

......

................

...........

.............

...............

..............

...........

.................

...........

..............

...........

.................

...........

..............

...............

.............

...........

..................

...........

.............

........

..............

...........

.1.2.......

.2.2. A...............

...........

.................

.......

...........

.......2.3.4.5.............

...........

....

.....................

..................................................

..

A C C B C A A A B C E 1 7 23 19 611 19 3041 4013 [0, ] [40, ] [105, ] [105, ] [22176, ] 4 120 3360 16800 3 1 51 19 913 434747 [20, ] [151, ] [105, ] [2402400, ] 5 840 280 5040 19 2787 9129739 [105, ] [50450400, ] 15400 Рис. Заданное множество символов — это, как правило, ASCII+. Для того, чтобы обеспечить остановку алгоритма распаковки вначале сжи маемого сообщения надо поставить его длину или ввести дополнитель ный символ-маркер конца сообщения. Если знать формат файла для сжатия, то вместо начального равномерного распределения весов мож но выбрать распределение с учетом этих знаний. Например, в тексто вом файле недопустимы ряд управляющих символов и их вес можно занулить.

Пример. Пусть заданное множество — это символы A, B, C. Сжи маемое сообщение — ACCBCAAABC. Введем маркер конца сообщения — E. Кодирование согласно приведенному алгоритму можно провести согласно схеме, приведенной на рис. 7.

Вследствие того, что 759021 9129739 = 0.00101110010100111011012,, 222 = 4194304 50450400 code(ACCBCAAABC) = 0010111001010011101101 и L(ACCBCAAABC) = 22.

Поэтому L1(ACCBCAAABC) = 2.2 бит/сим. Результат, получен ный адаптивным алгоритмом Хаффмена — 4.1 бит/сим, но если ко дировать буквы не 8 битами, а 2, то результат будет 2.3 бит/сим. В первой строчке схемы выписаны суммарные веса символов, а во второй — длины текущих отрезков.

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

Пример. Распакуем код 0010111001010011101101, зная, что множе ство символов сообщения состоит из A, B, C и E, причем последний — это маркер конца сообщения.

0.00101110010100111011012 =.

Веса Длина Число-код и его интервал Символ A B C E интервала 759021 1 1 1 1 1 (0, ) A 4194304 4 759021 3 4 2 1 1 1 (, ) C 1048576 5 5 649377 1 5 2 1 2 1 (, ) C 1048576 2 6 375267 2 3 2 1 3 1 (, ) B 1048576 7 7 529717 1 7 2 2 3 1 (, ) C 1048576 2 8 5429 2 2 2 4 1 (0, ) A 393216 9 3 2 4 1 (0, 0.3) A 0. 27145 4 4 2 4 1 (0, ) A 131072 11 298595 5 7 5 2 4 1 (12, ) B 524288 12 240425 8 12 5 3 4 1 (13, ) C 262144 13 1028373 5 3 5 1 (, 1) E 1048576.

Упражнение Составить адаптивный арифметический код с маркером конца для со общения BAABC.

15. Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива Методы Шеннона-Фэно, Хаффмена и арифметическое кодирование обобщающе называются статистическими методами. Словарные ал горитмы носят менее математически обоснованный, но более практич ный характер.

Алгоритм LZ77 был опубликован в 1977 г. Разработан израильски ми математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel).

Многие программы сжатия информации используют ту или иную моди фикацию LZ77. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

LZ77 использует уже просмотренную часть сообщения как словарь.

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

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

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

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

- смещение в словаре относительно его начала подстроки, совпада ющей с началом содержимого буфера;

- длина этой подстроки;

- первый символ буфера, следующий за подстрокой.

Пример. Размер окна — 20 символ, словаря — 12 символов, а буфе ра — 8. Кодируется сообщение “ПРОГРАММНЫЕ ПРОДУКТЫ ФИР МЫ MICROSOFT”. Пусть словарь уже заполнен. Тогда он содержит строку “ПРОГРАММНЫЕ ”, а буфер — строку “ПРОДУКТЫ”. Про сматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет “ПРО”, в словаре она расположена со смещением 0 и имеет дли ну 3 символа, а следующим символом в буфере является “Д”. Таким образом, выходным кодом будет тройка 0,3,’Д’. После этого алгоритм сдвигает влево все содержимое окна на длину совпадающей подстроки +1 и одновременно считывает столько же символов из входного потока в буфер. Получаем в словаре строку “РАММНЫЕ ПРОД”, в буфере — “УКТЫ ФИР”. В данной ситуации совпадающей подстроки обнару жить не удаться и алгоритм выдаст код 0,0,’У’, после чего сдвинет окно на один символ. Затем словарь будет содержать “АММНЫЕ ПРО ДУ”, а буфер — “КТЫ ФИРМ”. И т.д.

Декодирование кодов LZ77 проще их получения, т.к. не нужно осу ществлять поиск в словаре.

Недостатки LZ77:

1) с ростом размеров словаря скорость работы алгоритма-кодера про порционально замедляется;

2) кодирование одиночных символов очень неэффективно.

Пример. Закодировать по алгоритму LZ77 строку “КРАСНАЯ КРАСКА”.

СЛОВАРЬ(8) БУФЕР(5) КОД "........" "КРАСН" <0,0,’К’> ".......К" "РАСНА" <0,0,’Р’> "......КР" "АСНАЯ" <0,0,’А’> ".....КРА" "СНАЯ " <0,0,’С’> "....КРАС" "НАЯ К" <0,0,’Н’> "...КРАСН" "АЯ КР" <5,1,’Я’> ".КРАСНАЯ" " КРАС" <0,0,’ ’> "КРАСНАЯ " "КРАСК" <0,4,’К’> "АЯ КРАСК" "А...." <0,0,’А’> В последней строчке, буква “А” берется не из словаря, т. к. она последняя.

Длина кода вычисляется следующим образом: длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря -1. Следовательно, длина двоичного кода смещения будет округленным в большую сторону log2(размер словаря), а длина двоичного кода для длины подстроки будет округленным в большую сторону log2(размер буфера+1). А символ кодируется 8 битами (напри мер, ASCII+).

В последнем примере длина полученного кода равна 9(3+3+8) = 126 бит, против 14 8 = 112 бит исходной длины строки.

В 1982 г. Сторером (Storer) и Шиманским (Szimanski) на базе LZ был разработан алгоритм LZSS, который отличается от LZ77 произво димыми кодами.

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

Пример. Закодировать по алгоритму LZSS строку “КРАСНАЯ КРАСКА”.

СЛОВАРЬ(8) БУФЕР(5) КОД ДЛИНА КОДА "........" "КРАСН" 0’К’ ".......К" "РАСНА" 0’Р’ "......КР" "АСНАЯ" 0’А’ ".....КРА" "СНАЯ " 0’С’ "....КРАС" "НАЯ К" 0’Н’ "...КРАСН" "АЯ КР" 1<5,1> "..КРАСНА" "Я КРА" 0’Я’ ".КРАСНАЯ" " КРАС" 0’ ’ "КРАСНАЯ " "КРАСК" 1<0,4> "НАЯ КРАС" "КА..." 1<4,1> "АЯ КРАСК" "А...." 1<0,1> Здесь длина полученного кода равна 7 9 + 4 7 = 91 бит.

LZ77 и LZSS обладают следующими очевидными недостатками:

1) невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря;

2) длина подстроки, которую можно закодировать, ограничена разме ром буфера.

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

Кроме того, резко увеличится время работы алгоритма-кодера.

В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков.

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

Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря +8 (это количество бит в байт коде расширенного ASCII).

Пример. Закодировать по алгоритму LZ78 строку “КРАСНАЯ КРАСКА”, используя словарь длиной 16 фраз.

ВХОДНАЯ ФРАЗА ПОЗИЦИЯ КОД (В СЛОВАРЬ) СЛОВАРЯ "" "К" <0,’К’> "Р" <0,’Р’> "А" <0,’А’> "С" <0,’С’> "Н" <0,’Н’> "АЯ" <3,’Я’> " " <0,’ ’> "КР" <1,’Р’> "АС" <3,’С’> "КА" <1,’А’> Указатель на любую фразу такого словаря — это число от 0 до 15, для его кодирования достаточно четырех бит.

В последнем примере длина полученного кода равна 10 (4 + 8) = 120 битам.

Алгоритмы LZ77, LZ78 и LZSS разработаны математиками и могут использоваться свободно.

В 1984 г. Уэлчем (Welch) был путем модификации LZ78 создан алгоритм LZW.

Пошаговое описание алгоритма-кодера.

Шаг 1. Инициализация словаря всеми возможными односимвольными фразами (обычно 256 символами расширенного ASCII). Ини циализация входной фразы w первым символом сообщения.

Шаг 2. Считать очередной символ K из кодируемого сообщения.

Шаг 3. Если КОНЕЦ СООБЩЕНИЯ Выдать код для w Конец Если фраза wK уже есть в словаре Присвоить входной фразе значение wK Перейти к Шагу Иначе Выдать код w Добавить wK в словарь Присвоить входной фразе значение K Перейти к Шагу 2.

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

Пример. Закодировать по алгоритму LZW строку “КРАСНАЯ КРАСКА”. Размер словаря — 500 фраз.

ВХОДНАЯ ПОЗИЦИЯ ФРАЗА, wK КОД для w СЛОВАРЯ (В СЛОВАРЬ) ASCII+ 0- "КР" 0’К’ "РА" 0’Р’ "АС" 0’А’ "СН" 0’С’ "НА" 0’Н’ "АЯ" 0’А’ "Я " 0’Я’ " К" 0’ ’ "КРА" <256> "АСК" <258> "КА" 0’К’ "А" 0’А’ В этом примере длина полученного кода равна 12 9 = 108 битам.

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

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

Любопытна история патентования LZW. Заявку на LZW подали по чти одновременно две фирмы — сначала IBM и затем Unisys, но первой была рассмотрена заявка Unisys, которая и получила патент. Однако, еще до патентования LZW был использован в широко известной в мире Unix программе сжатия данных compress.

Упражнение Закодировать сообщения “AABCDAACCCCDBB”, “КИБЕРНЕТИКИ” и “СИНЯЯ СИНЕВА СИНИ”, вычислить длины в битах полученных кодов, используя алгоритмы, LZ77 (словарь — 12 байт, буфер — 4 байта), LZ78 (словарь — 16 фраз), LZSS (словарь — 12 байт, буфер — 4 байта), LZW (словарь — ASCII+ и 16 фраз).

Упражнение Может ли для первого символа сообщения код LZ78 быть короче ко да LZW при одинаковых размерах словарей? Обосновать. Для LZW в размер словаря не включать позиции для ASCII+.

16. LZ-алгоритмы распаковки данных. Примеры 1. LZ77, длина словаря — 8 байт (символов). Коды сжатого сооб щения — 0,0,’К’ 0,0,’Р’ 0,0,’А’ 0,0,’С’ 0,0,’Н’ 5,1,’Я’ 0,0,’ ’ 0,4,’К’ 0,0,’А’.

ВХОДНОЙ КОД ПЕЧАТЬ СЛОВАРЬ <0,0,’К’> "К" ".......К" <0,0,’Р’> "Р" "......КР" <0,0,’А’> "А" ".....КРА" <0,0,’С’> "С" "....КРАС" <0,0,’Н’> "Н" "...КРАСН" <5,1,’Я’> "АЯ" ".КРАСНАЯ" <0,0,’ ’> " " "КРАСНАЯ " <0,4,’К’> "КРАСК" "АЯ КРАСК" <0,0,’А’> "А" "Я КРАСКА" 2. LZSS, длина словаря — 8 байт (символов). Коды сжатого со общения — 0’К’ 0’Р’ 0’А’ 0’С’ 0’Н’ 1 5,1 0’Я’ 0’ ’ 1 0,4 1 4,1 1 0,1.

ВХОДНОЙ КОД ПЕЧАТЬ СЛОВАРЬ 0 ’К’ "К" ".......К" 0 ’Р’ "Р" "......КР" 0 ’А’ "А" ".....КРА" 0 ’С’ "С" "....КРАС" 0 ’Н’ "Н" "...КРАСН" 1 <5,1> "А" "..КРАСНА" 0 ’Я’ "Я" ".КРАСНАЯ" 0 ’ ’ " " "КРАСНАЯ " 1 <0,4> "КРАС" "НАЯ КРАС" 1 <4,1> "К" "АЯ КРАСК" 1 <0,1> "А" "Я КРАСКА" 3. LZ78, длина словаря — 16 фраз. Коды сжатого сообщения — 0,’К’ 0,’Р’ 0,’А’ 0,’С’ 0,’Н’ 3,’Я’ 0,’ ’ 1,’Р’ 3,’С’ 1,’А’.

ВХОДНОЙ ПЕЧАТЬ ПОЗИЦИЯ КОД (СЛОВАРЬ) СЛОВАРЯ "" <0,’К’> "К" <0,’Р’> "Р" <0,’А’> "А" <0,’С’> "С" <0,’Н’> "Н" <3,’Я’> "АЯ" <0,’ ’> " " <1,’Р’> "КР" <3,’С’> "АС" <1,’А’> "КА" 4. LZW, длина словаря — 500 фраз. Коды сжатого сообщения — 0’К’ 0’Р’ 0’А’ 0’С’ 0’Н’ 0’А’ 0’Я’ 0’ ’ 256 258 0’К’ 0’А’.

При распаковке нужно придерживаться следующего правила. Сло варь пополняется после считывания первого символа идущего за теку щим кода, т.е. из фразы, соответствующей следующему после раскоди рованного коду, берется первый символ. Это правило позволяет избе жать бесконечного цикла при раскодировании сообщений вида wKwK, где w — фраза, а K — символ. Конкретным примером такого сооб щения является любая последовательность трех одинаковых символов, пары которых ранее не встречались.

ВХОДНОЙ КОД ПЕЧАТЬ СЛОВАРЬ ПОЗИЦИЯ СЛОВАРЯ ASCII+ 0- 0’К’ "К" "КР" 0’Р’ "Р" "РА" 0’А’ "А" "АС" 0’С’ "С" "СН" 0’Н’ "Н" "НА" 0’А’ "А" "АЯ" 0’Я’ "Я" "Я " 0’ ’ " " " К" <256> "КР" "КРА" <258> "АС" "АСК" 0’К’ "К" "КА" 0’А’ "А" Упражнение Распаковать каждое приведенное сообщение и рассчитать длину кода каждого сжатого сообщения в битах. Сообщение, сжатое LZ77 (словарь — 12 байт, буфер — 4 байта), — 0,0,’A’ 0,0,’F’ 0,0,’X’ 9,2,’F’ 8,1,’F’ 6,2,’X’ 4,3,’A’. Сообщение, сжатое LZSS (словарь — 12 байт, буфер — 4 байта), — 0’A’ 0’F’ 0’X’ 1 9,2 1 8,2 1 6,3 1 4,4 1 9,1. Сооб щеие, сжатое LZ78 (словарь — 16 фраз), — 0,’A’ 0,’F’ 0,’X’ 1,’F’ 2,’X’ 5,’A’ 3,’A’ 2,’F’ 0,’A’. Сообщение, сжатое LZW (словарь — ASCII+ и 16 фраз), — 0’A’ 0’F’ 0’X’ 256 257 257 0’A’ 258 0’F’ 0’F’ 0’A’.

17. Особенности программ-архиваторов Если коды алгоритмов типа LZ передать для кодирования (адап тивному) алгоритму Хаффмена или арифметическому, то полученный двухшаговый (конвейерный, а не двухпроходный) алгоритм даст ре зультаты сжатия подобные широко известным программам: GZIP, ARJ, PKZIP,...

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

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

Примером программы, имеющей возможность сжимать файлы в общем потоке, является RAR. Архиваторы ОС Unix (gzip, bzip2,...) сжимают файлы в общем потоке практически всегда.

В 1992 году фирма WEB Technologies объявила о выходе новой про граммы сжатия DataFiles/16, которая якобы может при неоднократном использовании сжать любое количество данных до 1024 байт. Инфор мация об этом прошла из солидного издания, журнала Byte.

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

Но тогда, так как всего разных файлов длиной меньшей 100 байт су ществует не более чем 1 + 28 + 216 + · · · + 2792 = (2800 - 1)/255 < 2800, то неизбежно получится, что два разных файла упакуются в идентич ные файлы. Следовательно, не может существовать программы сжатия данных, которая может сжать любые исходные данные.

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

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

Расширения Программы Тип кодирования Z compress LZW arc arc, pkarc LZW, Хаффмена zip zip, unzip, pkzip, pkunzip LZW, LZ77, Хаффмена, Шеннона-Фэно gz gzip LZ77, Хаффмена bz2 bzip2 Берроуза-Уиллера, Хаффмена arj arj LZ77, Хаффмена ice, lzh lha, lharc LZSS, Хаффмена pak pak LZW Практически все форматы файлов для хранения графической ин формации используют сжатие данных. Формат графического файла также, как правила, идентифицируется расширением имени файла.

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

Расширения Тип кодирования gif LZW jpeg, jpg сжатие с потерями, Хаффмена или арифметическое bmp, pcx RLE tiff, tif CCITT/3 для факсов, LZW или другие Сжатие RLE (Run Length Encoding — кодирование переменной длины) — это простейший метод сжатия, в общем случае очень не эффективный, но дающий неплохие результаты на типичной графиче ской информации. Оно основано в основном на выделении специального кода-маркера, указывающего сколько раз повторить следующий байт.

Сжатие и распаковка в реальном времени используется в програм мах-драйверах для “уплотнения” носителей информации, позволяющих увеличить емкость носителя приблизительно в 2 раза. Наиболее извест ной программой такого рода является DriverSpace для MS-DOS и Mic rosoft Windows.

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

Сжатие с потерями используется в основном для трех видов дан ных: полноцветная графика (224 16 млн. цветов), звук и видеоинфор мация.

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

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

Для сжатия графической информации с потерями в конце 1980-х установлен один стандарт — формат JPEG (Joint Photographic Experts Group — название объединения его разработчиков). В этом формате можно регулировать степень сжатия, задавая степень потери качества.

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

Хотя существует не один стандарт для сжатия видеоданных, наиболее распространенными являются стандарты MPEG (Motion Picture Ex perts Group), первый из которых был опубликован в 1988 году. MPEG — практически единственный стандарт для записи видео и звуковой информации на CD-ROM, DVD-ROM и в цифровом спутниковом теле видении. Видеоинформацию можно сжать необыкновенно плотно, до и более раз, что позволяет, например, на одну видеокассету, записать более ста различных художественных фильмов. Но из-за очень сложных проблем, связанных с правами на интеллектуальную собственность, ре ально возможности сжатия информации таким образом используются сравнительно редко.

Для сжатии звуковой информации с потерями существует несколь ко стандартов. Наиболее широко используемый из них — это MPEG без видеоданных. Стандарт LPC (Linear Predictive Coding) использует ся для сжатия речи. Алгоритм LPC пытается промоделировать рече вой тракт человека и выдает на выходе буквально текущее состояние участвующих в формировании звуков органов.

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

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

Устройства канала — это, как правило, репитеры, просто пере дающие усиленным принятый сигнал (пример, радиорелейные линии).

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

обычно же кодеры/декодеры относят к источникам или при емникам информации.

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

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

Задержка сигнала во времени — это интервал времени от отправ ки сигнала передатчиком до его приема приемником.

Математически канал задается множеством допустимых сообще ний на входе, множеством допустимых сообщений на выходе и набо ром условных вероятностей P (y/x) получения сигнала y на выходе при входном сигнале x. Условные вероятности описывают статистические свойства “шумов” (или помех), искажающих сигнал в процессе пере дачи. В случае, когда P (y/x) = 1 при y = x и P (y/x) = 0 при y = x, канал называется каналом без “шумов”. В соответствии со структурой входных и выходных сигналов выделяют дискретные и непрерывные каналы. В дискретных каналах сигналы на входе и выходе представля ют собой последовательность символов одного или двух (по одному для входа и выхода) алфавитов. В непрерывных каналах входной и выход ной сигналы представляют собой функции от непрерывного параметра времени. Бывают также смешанные или гибридные каналы, но тогда обычно рассматривают их дискретные и непрерывные компоненты раз дельно. Далее рассматриваются только дискретные каналы.

Способность канала передавать информацию характеризуется чис лом — пропускной способностью или емкостью канала (обозначение — C).

Для случая канала без шума формула расчета емкости канала име log2 N(T ) ет вид C = lim, где N(T ) — число всех возможных сигналов T T за время T.

Пример. Пусть алфавит канала без “шумов” состоит из двух симво лов — 0 и 1, длительность секунд каждый. За время T успеет пройти n = T/ сигналов, всего возможны 2n различных сообщений длиной n.

log2 2T / В этом случае C = lim = 1/ бод.

T T На рис. 8 приведена схема, на которой изображен процесс прохо ждения информации по каналу с описанными в примере характеристи ками.

Здесь для кодирования используется уровень сигнала: низкий для 0 и высокий для 1. Недостатки этого способа проявляются в случаях, когда нужно передавать много сплошных нулей или единиц. Малей шее рассогласование синхронизации между приемником и передатчи ком приводит тогда к неисправимым ошибкам. Кроме того, многие но сители информации, в частности, магнитные, не могут поддерживать длительный постоянный уровень сигнала.

t.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.....

.....

.....

0 0 1 0 0 0 0 1 1 0 0 Рис. Для передачи информации используется обычно другой способ, ко гда для представления 0 и 1 используются две разные частоты, от личающиеся друг от друга ровно в два раза (см. рис. 9) — это так называемая частотная модуляция (ЧМ или FM).

t.

.

.

.

.

.

.

.

.

.

.

.

.

....

....

.....

1 0 0 0 1 Рис. Таким образом, при таком кодировании, если сигнал 1 имеет дли тельность, то 0 — 2.

Рассчитаем емкость этого канала. Нужно рассчитать N(T ). Пусть n = T/, тогда получается, что нужно рассчитать сколькими способа ми можно разбить отрезок длины n отрезками длины 2 и 1. Получаем, n-2 n- n что N(T ) = Sn = Cn + Cn-1 + Cn-2 + · · ·, где первое слагаемое — это количество способов, которыми можно разбить отрезок длины n n отрезками длины 1, второе слагаемое — это количество способов, ко торыми можно разбить отрезок длины n (n - 2) отрезками длины 1 и одним отрезком длины 2, третье слагаемое — это количество способов, которыми можно разбить отрезок длины n (n - 4) отрезками длины и двумя отрезками длины 2 и т.д. Таким образом, S1 = 1. Вследствие k+ k k+ того, что Cm + Cm = Cm+1 для любых k < m, получается, что n-1 n-3 n- Sn-1 = Cn-1 + Cn-2 + Cn-3 + · · · n-2 n-4 n- n Sn = Cn + Cn-1 + Cn-2 + Cn-3 + · · ·, n+1 n-3 n- n- Sn+1 = Cn+1 + Cn + Cn-1 + Cn-2 + · · · т. е. Sn+1 = Sn + Sn-1 при n > 1. Если положить, что S0 = 1, то S0, S1,... — это последовательность 1, 1, 2, 3, 5, 8, 13, 21, 34,..., т.е. чис ла Фибоначчи. C XIX века для вычисления n-го члена последователь ности Фибоначчи известна формула n+1 1 - 5 n+ 1 1 + Sn = -.

2 1+ log2 N(T ) log2 Sn log2 Таким образом, C = lim = lim = 0.69/ T n n T бод.

При использовании частотной модуляции на практике нули, как правило, кодируются в два раза плотнее. Это достигается тем, что учитываются не уровни сигнала, а смена уровня (полярности). Если частота соответствует 1, то с частотой 2 производится проверка уровня сигнала. Если он меняется, то это сигнал 1, если нет, то — 0. На практике частота — это частота синхронизации, т. е. частота импульса, который независимо от данных меняет полярность сигнала.

0 не генерирует импульса смены полярности, а 1 генерирует (см. рис.

10).

S D S D S D S D S D S D S D S D S D t.

.

.

.

.

.

.

.

.

.

.

.

.

....

....

.....

1 0 0 0 0 0 0 1 Рис. Для записи информации на первые магнитные диски и ленты ис пользовался метод FM. На гибкие диски 5.25” и 3.5” информация за писывается методом MFM (Modified FM) — модификацией метода FM, позволяющей в 2 раза повысить плотность записи. Это достигается тем, что частота синхронизации увеличивается вдвое. MFM можно ис пользовать с теми же физическими каналами, что и FM, потому что импульсы синхронизации не передаются перед 1 и первым 0 в серии нулей (см. рис. 11).

S D S D S D S D S D S D S D S D S D t.

.

.

.

.

.

.

.

.

.

.

.

.

....

....

.....

1 0 0 0 0 0 0 1 Рис. Метод записи с групповым кодированием, RLL — Run Limited Length, не использует импульсы синхронизации, применяется, в част ности, в жестких дисках “винчестер” и существует в нескольких разно видностях. Одна из них основана на замене тетрад байта на 5-битные группы. Эти группы подбираются таким образом, чтобы при передаче данных нули не встречались подряд более двух раз, что делает код са мосинхронизирующимся. Например, тетрада 0000 заменяется группой бит 11001, тетрада 1000 — 11010, тетрада 0001 — 11011, тетрада — 01111 (см. рис. 12). Существуют разновидности RLL, в которых заме няются последовательности бит различной длины. Кодирование MFM или FM можно представить как частный случай RLL.

t.

.

.

.

.

.

.

.

.

.

.

.

.

....

....

.....

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

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

Теорема Шеннона. Пусть источник характеризуется д.с.в. X. Рас сматривается канал с шумом, т.е. для каждого передаваемого сообще ния задана вероятность его искажения в процессе передачи (вероят ность ошибки). Тогда существует такая скорость передачи u, завися щая только от X, что > 0 u < u сколь угодно близкая к u такая, что существует способ передавать значения X со скоростью u и с веро ятностью ошибки меньшей, причем u = C/HX. Упомянутый способ образует помехоустойчивый код.

Кроме того, Фэно доказана [20] следующая обратная теорема о кодировании при наличии помех. Для u > u можно найти такое поло жительное число, что в случае передачи информации по линии связи со скоростью u вероятность ошибки передачи каждого символа сооб щения при любом методе кодирования и декодирования будет не меньше ( очевидно растет вслед за ростом u ).

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

Упражнение Три передатчика задаются случайными величинами со следующими законами распределениями вероятностей:

1) P (X1 = -1) = 1/4, P (X1 = 0) = 1/2, P (X1 = 1) = 1/4;

2) P (X2 = -1) = 1/3, P (X2 = 0) = 1/3, P (X2 = 1) = 1/3;

3) P (X3 = n) = 2-n, n = 1, 2,...

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

20. Помехозащитное кодирование Простейший код для борьбы с шумом — это контроль четности, он, в частности, широко используется в модемах. Кодирование заключает ся в добавлении к каждому байту девятого бита таким образом, чтобы дополнить количество единиц в байте до заранее выбранного для ко да четного (even) или нечетного (odd) значения. Используя этот код, можно лишь обнаруживать большинство ошибок.

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

Двоичный симметричный канал изображен на p рис. 13, где p — это вероятность безошибочной q передачи бита, а q — вероятность передачи би q та с ошибкой. Предполагается, что в таком канале p ошибки происходят независимо. Далее рассматри Рис. ваются только такие каналы.

Двоичный симметричный канал реализует схему Бернулли, поэто му вероятность передачи n бит по двоичному симметричному каналу с k k ошибками равна Pn(k) = Cnpn-kqk.

Пример. Вероятность передачи одного бита информации с ошибкой равна q = 0.01 и нас интересует вероятность безошибочной передачи 1000 бит (125 байт). Искомую вероятность можно подсчитать по фор муле P1000(0) = C1000p1000q0 = 0.991000 4.32 10-5, т.е. она ничтожно мала.

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

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

Двоичным (m, n)-кодом называется пара, состоящая из схемы ко дирования E: Zm Zn и схемы декодирования D: Zn Zm, где Zn — 2 2 2 2 множество всех двоичных последовательностей длины n, m < n (случай m = n рассматривается в криптографии).

Функции D и E выбираются так, чтобы функция H = D T E, где T — функция ошибок, с вероятностью, близкой к единице, была тож дественной. Функции D и E считаются безошибочными, т. е. функция D E — тождественная (см. рис. 14).

E T D Исходное - Кодированное - Принятое - Декодирован сообщение сообщение Двоичный сообщение ное сообщение симметрич ный канал Рис. Упражнение Пусть двоичный симметричный канал используется для передачи строк из двух бит. Построить таблицу вероятностей приема.

Упражнение По двоичному симметричному каналу передаются строки длины 14.

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

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

Простой код с обнаружением ошибок основан на схеме проверки четности, применимой к сообщениям a1... am любой фиксированной длины m. Схема кодирования определяется следующими формулами:

E(a1... am) = a1... amam+1, m 0, если i=1 ai — четная;

am+1 = m 1, если ai — нечетная.

i= m+ Таким образом, ai должна быть четной.

i= Соответствующая схема декодирования тривиальна:

m+ a1... am, если ai — четна;

D(a1... amam+1) = i= m+ ошибка, если ai — нечетна.

i= m+ Разумеется, что четность ai не гарантирует безошибочной пере i= дачи.

Пример. Проверка четности при m = 2 реализуется следующим кодом (функцией E): 00 000, 01 011, 10 101, 11 110. В двоич ном симметричном канале доля неверно принятых сообщений для этого кода (хотя бы с одной ошибкой) равна q3 + 3pq2 + 3p2q (три, две или одна ошибка соответственно). Из них незамеченными окажутся только ошибки точно в двух битах, не изменяющие четности. Вероятность та ких ошибок 3pq2. Вероятность ошибочной передачи сообщения из двух бит равна 2pq + q2. При малых q верно, что 3pq2 2pq + q2.

Рассмотрим (m, 3m)-код с тройным повторением. Коды с повто рениями очень неэффективны, но полезны в качестве теоретического примера кодов, исправляющих ошибки. Любое сообщение разбивается на блоки длиной m каждое и каждый блок передается трижды — это определяет функцию E. Функция D определяется следующим образом.

Принятая строка разбивается на блоки длиной 3m. Бит с номером i (1 i m) в декодированном блоке получается из анализа битов с но мерами i, i+m, i+2m в полученном блоке: берется тот бит из трех, кото рый встречается не менее двух раз. Вероятность того, что бит в данной позиции будет принят трижды правильно равна p3. Вероятность одной ошибки в тройке равна 3p2q. Поэтому вероятность правильного прие ма одного бита равна p3 + 3p2q. Аналогичным образом получается, что вероятность приема ошибочного бита равна q3 + 3pq2.

Пример. Предположим q = 0.1. Тогда вероятность ошибки при пе редачи одного бита — 0.028, т.е. этот код снижает вероятность ошибки с 10% до 2.8%. Подобным образом организованная передача с пятикрат ным повторением даст вероятность ошибки на бит q5 + 5pq4 + 10p2q3 = 0.00856 = 0.856%, т. е. менее 1%. В результате вероятность правильной передачи стро ки длиной 10 возрастет с 0.910 35% до 0.97210 75% при тройных повторениях и до 0.9914410 92% при пятикратных повторениях.

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

Рассмотрим (2048, 2313)-код, используемый при записи данных на магнитофонную ленту компьютерами Apple II. К каждому байту ис ходных данных прибавляется бит четности и, кроме того, после каж дых таких расширенных битом четности 256 байт добавляется специ альный байт, также расширенный битом четности. Этот специальный байт, который называют контрольной суммой (check sum), есть ре зультат применения поразрядной логической операции “исключающее ИЛИ” (XOR) к 256 предшествующим расширенным байтам. Этот код способен как обнаруживать ошибки нечетной кратности в каждом из отдельных байт, так и исправлять до 8 ошибок в блоке длиной 256 байт.

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

Сбойный бит однозначно определяется пересечением сбойных колонки байта и строки бита контрольной суммы. На рис. 15 изображена схема участка ленты, содержащего ровно 9 ошибок в позициях, обозначенных p1, p2,..., p9. Расширенный байт контрольной суммы обозначен CS, а бит паритета (в данном случае четности) — PB (parity bit). Ошибка в позиции p1 может быть исправлена. Ошибки в позициях p4, p5, p6, p можно обнаружить, но не исправить. Ошибки в позициях p2, p3, p8, p невозможно даже обнаружить.

1 2 3 4 5 6 256 CS p p2 p p p5 p p p8 p PB Рис. Приведенные ранее примеры простейших кодов принадлежат к классу блочных. По определению, блочный код заменяет каждый блок из m символов более длинным блоком из n символов. Следовательно, (m, n)-коды являются блочными. Существуют также древовидные или последовательные коды, в которых значение очередного контрольного символа зависит от всего предшествующего фрагмента сообщения. Ра бота с древовидным шумозащитным кодом имеет сходство с работой с арифметическим кодом для сжатия информации.

Расстоянием (Хэмминга) между двоичными словами длины n на зывается количество позиций, в которых эти слова различаются. Это одно из ключевых понятий теории кодирования. Если обозначить дво ичные слова как a = a1... an и b = b1... bn, то расстояние между ними обозначается d(a, b).

Весом двоичного слова a = a1... an называется количество единиц n в нем. Обозначение w(a). Можно сказать, что w(a) = ai.

i= Пример. Пусть a = 1001 и b = 0011, тогда w(a) = w(b) = 2, d(a, b) = 2.

Далее операция + при применении к двоичным словам будет озна чать поразрядное сложение без переноса, т. е. сложение по модулю или “исключающее ИЛИ” (XOR).

Расстояние между двоичными словами a и b равно весу их пораз рядной суммы, т.е. d(a, b) = w(a + b).

Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.

Следовательно, если a и b — слова длины n, то вероятность того, что слово a будет принято как b, равна pn-d(a,b)qd(a,b).

Наример, вероятность того, что слово 1011 будет принято как 0011, равна p3q.

Для возможности обнаружения ошибки в одной позиции минималь ное расстояние между словами кода должно быть б ольшим 1.

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

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

Достаточность доказывается конструктивно: если условие утверждения выполнено для E, то в качестве декодирующей функции D следует взять функ цию, сообщающую об ошибке, если декодируемое слово отличается от любого из слов из образа E. Необходимость доказывается от противного: если мини мальное расстояние k < k + 1, то ошибка в k позициях сможет превратить одно кодовое слово в другое.

Для такого кода вероятность того, что ошибки в сообщении оста нутся необнаруженными, равна n i k+1 n- Cnpn-iqi = Cn pn-k-1qk+1 + · · · + Cn pqn-1 + qn i=k+ k+ [при малых q и не слишком маленьких k] Cn pn-k-1qk+1.

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

Клод Шеннон Норберт Винер Давид Хаффмен Ричард Хэмминг Авраам Лемпел Рональд Ривест, Эди Шамир, Дональд Кнут Леонард Адлеман Достаточность доказывается конструктивно: если условие утверждения выполнено для E, то в качестве декодирующей функции D следует взять функ цию, возвращающую ближайшее к декодируемому слово из образа E. Необхо димость доказывается от противного. Пусть расстояние между выбранными словами в коде равно 2k. Тогда если при передаче каждого из этих слов слу чится k ошибок, которые изменят биты, в которых различаются эти слова, то приемник получит два идентичных сообщения, что свидетельствует о том, что в данной ситуации исправление k ошибок невозможно. Следовательно, мини мальное расстояние между словами кода должно быть б ольшим 2k.

Пример. Рассмотрим (1, 3)-код, состоящий из E, задающей отобра жение 0 000 и 1 111, и D, задающей отображение 000 0, 0, 010 0, 011 1, 100 0, 101 1, 110 1, 111 1. Этот код (с тройным повторением) исправляет ошибки в одной позиции, т.к. мини мальное расстояние между словами кода равно 3.

Если код исправляет все ошибки кратности k и меньшей, то ве роятность ошибочного приема слова длины n очевидно не превосходит n i Cnpn-iqi. Вероятность правильного приема в этом случае не i=k+ меньше, чем k i 1 k Cnpn-iqi = pn + Cnpn-1q + · · · + Cnpn-kqk.

i= Передачу данных часто удобно рассматривать следующим обра зом. Исходное сообщение a = a1... am кодируется функцией E в ко довое слово b = b1... bn. Канал связи при передаче добавляет к нему функцией T строку ошибок e = e1... en так, что приемник получает сообщение r = r1... rn, где ri = bi + ei (1 i n). Система, исправ ляющая ошибки, переводит r в некоторое (обычно ближайшее) кодовое слово. Система, только обнаруживающая ошибки, лишь проверяет, яв ляется ли принятое слово кодовым, и сигнализирует о наличии ошибки, если это не так.

Пример. Пусть передаваемое слово a = 01 кодируется словом b = 0110, а строка ошибок — e = 0010. Тогда будет принято слово r = 0100. Система, исправляющая ошибки, переведет его в 0110 и затем восстановит переданное слово 01.

Если система только обнаруживает ошибки и расстояние между любыми кодовыми словами k 2, то любая строка ошибок e с един ственной единицей приведет к слову r = b + e, которое не является кодовым.

Пример. Рассмотрим (2, 3)-код с проверкой четности. Множество кодовых слов — {000, 011, 101, 110}. Ни одна из строк ошибок 001, 010, 100, 111 не переводит одно кодовое слово в другое. Поэтому однократная и тройная ошибки могут быть обнаружены.

Пример. Следующий (2, 5)-код обнаруживает две ошибки:

a1 = 00 00000 = b1, a2 = 01 01011 = b2, a3 = 10 10101 = b3, a4 = 11 11110 = b4.

Этот же код способен исправлять однократную ошибку, потому что любые два кодовых слова отличаются по меньшей мере в трех пози циях. Из того, что d(bi, bj) 3 при i = j, следует, что однократная ошибка приведет к приему слова, которое находится на расстоянии от кодового слова, которое было передано. Поэтому схема декодирова ния, состоящая в том, что принятое слово переводится в ближайшее к нему кодовое, будет исправлять однократную ошибку. В двоичном симметричном канале вероятность правильной передачи одного блока будет не меньше чем p5 + 5p4q.

Установлено [20], что в (n - r, n)-коде, минимальное расстояние между кодовыми словами которого 2k + 1, числа n, r (число допол нительных разрядов в кодовых словах) и k должны соответствовать неравенству k k-1 r log2(Cn + Cn + · · · + Cn + 1), называемому неравенством или нижней границей Хэмминга. Кроме того, если числа n, r и k соответствуют неравенству 2k-1 2k-2 r > log2(Cn-1 + Cn-1 + · · · + Cn-1 + 1), называемому неравенством или верхней границей Варшамова-Гиль берта, то существует (n - r, n)-код, исправляющий все ошибки веса k и менее [20].

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

Упражнение Имеется (8, 9)-код с проверкой четности. Вычислить вероятность того, что в случае ошибки этот код ее не обнаружит, если вероятность ошиб ки при передаче каждого бита равна 1%. Вычислить также вероятность ошибочной передачи без использования кода. Сделать аналогичные рас четы для случая, когда вероятность ошибки в десять раз меньше.

Упражнение Вычислить минимальную и максимальную оценки количества допол нительных разрядов r для кодовых слов длины n, если требуется, что бы минимальное расстояние между ними было d. Рассмотреть случаи n = 32, d = 3 и n = 23, d = 7.

22. Матричное кодирование Ранее каждая схема кодирования описывалась таблицами, задаю щими кодовое слово длины n для каждого исходного слова длины m.

Для блоков большой длины этот способ требует большого объема па мяти и поэтому непрактичен. Например, для (16, 33)-кода потребуется 33 216 = 2 162 688 бит.

Гораздо меньшего объема памяти требует матричное кодирова ние. Пусть E матрица размерности m n, состоящая из элементов eij, где i — это номер строки, а j — номер столбца. Каждый из элементов матрицы eij может быть либо 0, либо 1. Кодирование реализуется опе рацией b = aE или bj = a1e1j + a2e2j + · · · + amemj, где кодовые слова рассматриваются как векторы, т.е как матрицы-строки размера 1 n.

Пример. Рассмотрим следующую 3 6-матрицу:

1 0 0 1 1 E = 0 1 0 0 1 1.

0 0 1 1 1 Тогда кодирование задается такими отображениями: 000 000000, 001 001111, 010 010011, 011 011100, 100 100110, 101001, 110 110101, 111 111010.

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

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

Матричные коды называют также линейными кодами. Для линей ных (n-r, n)-кодов с минимальным расстоянием Хэмминга d существу ет нижняя граница Плоткина (Plotkin) [14] для минимального количе ства контрольных разрядов r при n 2d - 1, r 2d - 2 - log2 d.

Упражнение Вычислить минимальную оценку по Плоткину количества дополни тельных разрядов r для кодовых слов матричного кода, если требуется, чтобы минимальное расстояние между ними было d. Рассмотреть слу чаи из предыдущего упражнения.

23. Групповые коды Множество всех двоичных слов a = a1... am длины m образует абе леву (коммутативную) группу относительно поразрядного сложения.

Пусть E — кодирующая m n-матрица, у которой есть m m подматрица с отличным от нуля определителем, например, единичная.

Тогда отображение a aE переводит группу всех двоичных слов дли ны m в группу кодовых слов длины n.

Предположим, что a = a1... am = a +a. Тогда для b = b1 · · · bn = aE, b = a E, b = a E, получаем bj = a1e1j + a2e2j + · · · + amemj = = (a + a )e1j + (a + a )e2j + · · · + (a + a )emj = b + b, 1 2 2 2 m m j j т. е. b = b + b. Следовательно, взаимно-однозначное отображение группы двоичных слов длины m при помощи заданной матрицы E сохраняет свойства групповой операции, что означает, что кодовые слова образуют группу.

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

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

Это следует из соотношения d(bi, bj) = w(bi + bj).

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

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

Такие строки ошибок переводят одно кодовое слово в другое.

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

В рассмотренном примере вероятность ошибки равна 4p3q3 +3p2q4.

Рассмотрим задачу оптимизации декодирования группового кода с двоичной матрицей кодирования E. Требуется минимизировать веро ятность того, что D(T (aE)) = a.

Схема декодирования состоит из группы G всех слов, которые мо гут быть приняты (#G = 2n). Так как кодовые слова B образуют нор мальную (нормальность следует из коммутативности G) подгруппу G, то множеству G можно придать структуру таблицы: будем записывать в одну строку те элементы G, которые являются членами одного смеж ного класса G по B. Первая строка, соответствующая нулевому слову m из G, будет тогда всеми кодовыми словами из B, т. е. b0, b1,..., b2 -1.

В общем случае, если gi G, то строка, содержащая gi (смежный класс m giB) имеет вид b0 + gi, b1 + gi,..., b2 -1 + gi.

Лидером каждого из таких построенных смежных классов называ ется слово минимального веса.

Каждый элемент g из G однозначно представляется в виде суммы gi +bj, где gi G — лидер соответствующего смежного класса и bj B.

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

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

m b0 b1 b2 · · · b2 - m g1 g1 + b1 g1 + b2 · · · g1 + b2 - · · · · · · · · · · · · · · · m g2n-m g2n-m + b1 g2n-m + b2 · · · g2n-m + b2 -1.

-1 -1 -1 - То, что строк будет 2n-m следует из теоремы Лагранжа [1], т.к. 2n-m — это порядок фактор-группы G/B, #(G/B) = #(G)/#(B), #B = 2m.

Декодирование слова g = bj + gi состоит в выборе кодового слова bj в качестве переданного и последующем применении операции, обрат ной умножению на E. Такая схема декодирования сможет исправлять ошибки.

Для (3, 6)-кода из рассматриваемого примера таблица декодирова ния будет следующей:

000000 100110 010011 110101 001111 101001 011100 100000 000110 110011 010101 101111 001001 111100 010000 110110 000011 100101 011111 011001 001100 001000 101110 011011 111101 000111 100001 010100 000100 100010 010111 110001 001011 101101 011000 000010 100100 010001 110111 001101 101011 011110 000001 100111 010010 110100 001110 101000 011101 000101 100011 010110 110000 001010 101100 011001 111111.

Первая строка в ней — это строка кодовых слов, а первый столбец — это лидеры.

Чтобы декодировать слово bj + e, следует отыскать его в таблице и выбрать в качестве переданного слово в том же столбце и в первой строке.

Например, если принято слово 110011 (2-я строка, 3-й столбец та блицы), то считается, что было передано слово 010011;

аналогично, если принято слово 100101 (3-я строка, 4-й столбец таблицы), переданным считается слово 110101, и т.д.

Групповое кодирование со схемой декодирования посредством ли деров исправляет все ошибки, строки которых совпадают с лидерами.

Следовательно, вероятность правильного декодирования переданного по двоичному симметричному каналу кода равна сумме вероятностей всех лидеров, включая нулевой.

В рассмотренной схеме вероятность правильной передачи слова бу дет p6 + 6p5q + p4q2.

Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца.

Пусть переданное слово bi принято как bi + e, d(bi, bi + e) = w(e), т. е.

это расстояние равно весу соответствующего лидера. Расстояние от bi + e до любого другого кодового слова bj равно весу их поразрядной суммы, т.е.

d(bj, bi + e) = w(bj + bi + e) = d(bj + bi, e) = d(bk, e) = w(bk + e) w(e), т. к. e — лидер смежного класса, к которому принадлежат как bk + e, так и bi + e.

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

Упражнение 1 0 0 1 0 1 0 :

Для кодирующих матриц E1 =, E2 = 0 1 0 0 1 1 1 0 0 1 1. Построить соответственно (2, 5)-код и (3, 4)-код.

2. Найти основные характеристики полученных кодов: минимальное расстояние между словами кода;

вероятность необнаружения ошиб ки;

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

3. Построить таблицы декодирования.

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

5. Во что будут декодированы слова: 10001, 01110, 10101, 1001, 0110, 1101?

24. Совершенные и квазисовершенные коды Групповой (m, n)-код, исправляющий все ошибки веса, не большего k, и никаких других, называется совершенным.

Свойства совершенного кода [1]:

1. Для совершенного (m, n)-кода, исправляющего все ошибки веса, k i не большего k, выполняется соотношение Cn = 2n-m. Верно и i= обратное утверждение;

2. Совершенный код, исправляющий все ошибки веса, не большего k, в столбцах таблицы декодирования содержит все слова, отстоящие от кодовых на расстоянии, не большем k. Верно и обратное утверждение;

3. Таблица декодирования совершенного кода, исправляющего все ошибки в не более чем k позициях, имеет в качестве лидеров все строки, содержащие не более k единиц. Верно и обратное утверждение.

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

n- Чисел m, n и k (1 < k < ), удовлетворяющих условию совершенно сти кода очень мало. Но и при подобранных m, n и k совершенный код можно построить только в исключительных случаях.

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

Двоичный блочный (m, n)-код называется оптимальным, если он минимизирует вероятность ошибочного декодирования. Совершенный или квазисовершенный код — оптимален. Общий способ построения оптимальных кодов пока неизвестен.

Для любого целого положительного числа r существует совершен ный (m, n)-код, исправляющий одну ошибку, называемый кодом Хэм минга (Hamming), в котором m = 2r - r - 1 и n = 2r - 1.

1 i Действительно, Cn = 1 + 2r - 1 = 2r = 2n-m.

i= Порядок построения кода Хэмминга следующий:

1. Выбираем целое положительное число r. Сообщения будут сло вами длины m = 2r - r - 1, а кодовые слова — длины n = 2r - 1;

2. В каждом кодовом слове b = b1b2... bn r бит с индексами степенями двойки (20, 21,..., 2r-1) — являются контрольными, осталь ные — в естественном порядке — битами сообщения. Например, если r = 4, то биты b1, b2, b4, b8 — контрольные, а b3, b5, b6, b7, b9, b10, b11, b12, b13, b14, b15 — из исходного сообщения;

3. Строится матрица M из 2r - 1 строк и r столбцов. В i-ой строке стоят цифры двоичного представления числа i. Матрицы для r = 2, и 4 таковы:

001 010 01 011 M32 = 10 M73 = 100 M154 = 1000 ;

11 101 110 111 4. Записывается система уравнений bM = 0, где M — матрица из предыдущего пункта. Система состоит из r уравнений. Например, для r = 3:

b4 + b5 + b6 + b7 = b2 + b3 + b6 + b7 = 0 ;

b1 + b3 + b5 + b7 = 5. Чтобы закодировать сообщение a, берутся в качестве bj, j не равно степени двойки, соответствующие биты сообщения и отыскива ются, используя полученную систему уравнений, те bj, для которых j — степень двойки. В каждое уравнение входит только одно bj, j = 2i.

В выписанной системе b4 входит в 1-е уравнение, b2 — во второе и b1 — в третье. В рассмотренном примере сообщение a = 0111 будет закодировано кодовым словом b = 0001111.

Декодирование кода Хэмминга проходит по следующей схеме.

Пусть принято слово b + e, где b — переданное кодовое слово, а e — строка ошибок. Так как bM = 0, то (b + e)M = bM + eM = eM. Если результат нулевой, как происходит при правильной передаче, считает ся, что ошибок не было. Если строка ошибок имеет единицу в i-й по зиции, то результатом произведения eM будет i-я строка матрицы M или двоичное представление числа i. В этом случае следует изменить символ в i-й позиции слова b + e, считая позиции слева, с единицы.

Пример. (4, 7)-код Хэмминга имеет в качестве одного из кодовых слов b = 0001111. Матрица M73 приведена на шаге 3 хода построения кода Хэмминга. Ясно, что bM = 0. Добавим к b строку ошибок e = 0010000. Тогда b + e = 0011111 и (b + e)M = 011 = 310, т. е. ошибка находится в третьей позиции. Если e = 0000001, то b + e = 0001110 и позиция ошибки — (b+e)M = 111 = 710 и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.

Код Хэмминга — это групповой код.

Это следует из того, что (m, n)-код Хэмминга можно получить матрич ным кодированием, при помощи m n-матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соот ветствуют уравнениям шага 4 построения кода Хэмминга, т. е. 1-му столбцу соответствует уравнение для вычисления 1-го контрольного разряда, 2-му — для 2-го, 4-му — для 4-го и т.д. Такая матрица будет при кодировании копиро вать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга.

Пример. Кодирующая матрица для (4, 7)-кода Хэмминга — E =.

Ее столбцы с номерами 3, 5, 6 и 7 образуют единичную подматрицу.

Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисле ния контрольных бит, например, уравнению b1 = b3 + b5 + b7 соответ ствует столбец 1101, т.е. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3, 5 и 7 кода.

К (m, n)-коду Хэмминга можно добавить проверку четности. По лучится (m, n + 1)-код с наименьшим весом ненулевого кодового слова 4, способный исправлять одну и обнаруживать две ошибки.

Коды Хэмминга накладывают ограничения на длину слов сообще ния: эта длина может быть только числами вида 2r - r - 1: 1, 4, 11, 26, 57,... Но в реальных системах информация передается байтам или машинными словами, т.е. порциями по 8, 16, 32 или 64 бита, что дела ет использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные коды.

Квазисовершенные (m, n)-коды, исправляющие одну ошибку, стро ятся следующим образом. Выбирается минимальное n так, чтобы 2n 2m.

n + Каждое кодовое слово такого кода будет содержать k = n-m контроль ных разрядов. Из предыдущих соотношений следует, что 1 2k = 2n-m n + 1 = Cn + Cn = m + k + 1.

Каждому из n разрядов присваивается слева-направо номер от 1 до n. Для заданного слова сообщения составляются k контрольных сумм S1,..., Sk по модулю 2 значений специально выбранных разрядов ко дового слова, которые помещаются в позиции-степени 2 в нем: для Si (1 i k) выбираются разряды, содержащие биты исходного сообще ния, двоичные числа-номера которых имеют в i-м разряде единицу. Для суммы S1 это будут, например, разряды 3, 5, 7 и т.д., для суммы S2 — 3, 6, 7 и т. д. Таким образом, для слова сообщения a = a1... am будет построено кодовое слово b = S1S2a1S3a2a3a4S4a5... am. Обозначим Si сумму по модулю 2 разрядов полученного слова, соответствующих кон трольной сумме Si и самой этой контрольной суммы. Если Sk... S1 = 0, то считается, что передача прошла без ошибок. В случае одинарной ошибки Sk... S1 будет равно двоичному числу-номеру сбойного бита.

В случае ошибки, кратности большей 1, когда Sk... S1 > n, ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода.

Пример построения кодового слова квазисовершенного (9, n)-кода, исправляющего все однократные ошибки, для сообщения 100011010.

212 4096 213 = < 29 = 512 и = > 512, т.е. n = 13.

13 13 14 1 2 3 4 5 6 7 8 9 10 11 12 Искомое кодовое слово имеет вид. Далее S1S2 1 S3 0 0 0 S4 1 1 0 1 нужно вычислить контрольные суммы.

110 = 210 = 310 = 410 = 510 = S1 = b3 + b5 + b7 + b9 + b11 + b13 = 610 = S2 = b3 + b6 + b7 + b10 + b11 = 710 = S3 = b5 + b6 + b7 + b12 + b13 = 810 = S4 = b9 + b10 + b11 + b12 + b13 = 910 = 1010 = 1110 = 1210 = 1310 = Таким образом, искомый код — 0011000111010. Если в процессе переда чи этого кода будет испорчен его пятый бит, то приемник получит код 0011100111010. Для его декодирования опять вычисляются контроль ные суммы:

S1 = b1 + b3 + b5 + b7 + b9 + b11 + b13 = S2 = b2 + b3 + b6 + b7 + b10 + b11 = S3 = b4 + b5 + b6 + b7 + b12 + b13 = S4 = b8 + b9 + b10 + b11 + b12 + b13 = S4S3S2S1 = 01012 = 510.

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

Совершенный код Хэмминга также можно строить по рассмотрен ной схеме, т.к. для него 2n/(n + 1) = 2m.

Для исправление одинарной ошибки к 8-разрядному коду доста точно приписать 4 разряда (212/13 > 28), к 16-разрядному — 5, к 32 разрядному — 6, к 64-разрядному — 7.

Упражнение Может ли (6, 14)-код, минимальное расстояние между кодовыми слова ми которого 5, быть совершенным?

Pages:     || 2 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.