II. К р а т к а я т е о р и я.

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

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

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

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

3. для компрессии или сжатия информации, т.е. для компактного представления данных. В этом случае применяется эффективное (оптимальное) кодирование;

4. для сжатия информации с последующей защитой ее от помех. При этом используется двойное последовательное кодирование.

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

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

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

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

При этом количество информации (по Хартли)определяется в виде

, гдеN - число различных состояний наблюдаемого объекта или размер алфавита сообщений источника;

J- количество информации (в битах).

Если N = 2, тоJ_min = 1 бит.

При такой процедуре (программе) идентификации еще до восприятия сообщений все их множество в памяти приемника должно быть разбито на пары подмножеств (вплоть до отдельных элементов), образуя бинарное дерево. Если двигаться от вершины дерева к месту расположения в памяти искомого элемента, то можно наметитьпуть движения к данному сообщению, в котором повороты направо обозначим²1², а повороты налево -²0². Такой путь - это и естьинформация для поискаданного сообщения в памяти приемника. Таким образом, (по Хартли) информация - это процедура (программа)дихотомического поиска; она представлена последовательностью команд или инструкций вида:²направо²,²налево²или с учетом обозначений -²1²,²0².Заметим, что поиск объектов можно осуществлять различными процедурами в зависимости от наличия априорной (заранее известной) информации о них:

- простым перебором или сканированием;

- случайным выбором;

- оптимальным поиском;

- комбинированным поиском.

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

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

Оптимальная программа поиска объекта

0 1 2 3 4 5 6 7 сообщения²Æ²имеет вид²101².

0 Х § ¨ º Æ ª # Как видно на рисунке - это кратчайший путь поиска.

1

0

1

Где Æ ?

Т.о. можно обозначить все восемь сообщений; программы их поиска окажутся закодированы 3-х разрядными двоичными числами. Количество информации в каждой программе, определенное по формуле Р. Хартли, равно 3-м битам.

J = log₂ 8 = 3 бит.

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

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

Вер-ти. 1/4 1/4 1/8 1/8 1/16 1/16 1/16 1/16

Cообщ. i u ¢ t o U v n l

1

1 0

1

0 1

0 1

Как видно из рисунка, длина инструкции для дихотомического поиска в этом случае различна. Для поиска в памяти приемника самых частых сообщений с вероятностью 1/4требуется всего две команды. Длина программы идентификации самых редких сообщений с вероятностью 1/16 состоит из четырех команд. Средняя длина программ поиска определяется в виде

элемента.

В данном примере с ²идеальным²распределением вероятностей величина средней длины программ идентификации совпадает с количеством информации (2,75 бит), вычисляемым по формуле К. Шеннона в виде

, гдеJ - количество информации,

H- энтропия источника сообщений.

Для случая равновероятных сообщений , когда , эта формула принимает вид формулы Р. ХартлиЕсли неожиданностьпоявленияi-ого сообщения определить в видето. Это позволяет пояснить суть понятия²энтропия².

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

Энтропия имеет следующие свойства:

1. H = Hmax, если вероятности всех сообщений равны;

, еслидля всех .

2. H= 0, если одно из состояний источника достоверно;

если

3. Энтропия нескольких (в количестве к) статистически независимых источников равна сумме их энтропий;

4. Энтропия источника двух разных сообщений определяется в виде

, гдеP и (1-P) - вероятности сообщений.

Как видно это функция одной переменной и может быть изображена графиком

1 бит

H

Р

0 1

где H -энтропия простейшего источника;

H₁ - неожиданность его первого состояния.

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

Целью эффективного кодированияявляется представление массивов сообщений (алфавитом) компактными текстами, которые записаны кодовыми словами, составленными из символов (алфавитаm<M).

Критерием эффективности оптимального кода является средняя длина кодового слова, определяемая в виде , гдеP- вероятность появления данного кодового слова;

l - длина кодового словаi-го сообщения;

M -количество разных кодовых слов (размер алфавита сообщений).

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

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

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

Эффективное кодирование для не равновероятных сообщений основано на теореме Клода Шеннона для дискретного канала без шума. Шеннон доказал, что последовательность сообщений, некоторого алфавита, можно закодировать так, что среднее число двоичных символов на одно сообщение будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины, т.е. (дляm=2 L ³ H)

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

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

При m = 2 такие идеальные вероятности кратны 2, аL = H. Примеры с такими вероятностями сообщений рассмотрены выше.

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

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

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

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

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

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

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

- декорреляция блоками;

- декорреляция L- граммами (более эффективна).

При первом способе не удается учесть статистические связи на границах между блоками. Это устраняется при кодировании L-граммами.

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

Рассмотрим декорреляцию (сегментацию) и кодирование блоками по 4 сообщения следующей фразы:

² Пусть имеется информация... ²®Пусть имеется информация…

К = 4 0110 101 110 011 111 001

Если n -длина исходной последовательности,

к - длина блока, то

число заменяющих ее блоков .

Декорреляция и кодирование L- граммами по 4 сообщения имеет вид:

²Пусть имеется информация...²

⁰¹¹⁰¹₁₀₁₁

^1110111

Число L- грамм (поксообщений), заменяющих исходную последовательность длинойn сообщений определяется в виде= n - (к - 1);

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

n = 8

		1	0	1	0	1	1
				1	0	1	0
						1	0
				1	0	1	1
			1	0	1	1	0
	1	0	0	1	1	0	1

U(t)

t

D t = const

00 1 1 0 11 0 1 00 11 0 0 1 1 00 11 00

уровень²1²

уровень²0²

t

D t₁D t₂D t₃Dt₄Dt₅

При передаче данных по каналу и при заполнении массива данных в памяти нужно установить буферное запоминающее устройство - БЗУ (накопитель) с числом разрядов не меньше удвоенного числа разрядов самого длинного кодового слова. Из этого накопителя в канал связи выдаются не отдельные кодовые слова, а непрерывная последовательность ²1²и²0²с постоянной скоростью и без пробелов. При записи в ячейки памяти на выходе накопителя формируются слова одинаковой длины по числу разрядов в них. Соответственно при считывании данных из массива или для выделения кодовых слов нужен еще один такой же накопитель. Если кодирование осуществляется блоками илиL- граммами, то на стороне источника сигналов необходим формирователь блоков или

L-грамм, а на стороне приемника сообщений - их распознаватель (расформирователь).

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

источник формирователь кодер БЗУ канал связи или ЗУ

дискретных (накопитель)

сообщений блоков, L-гр

приемник распознаватель декодер Б З У

сообщений блоков, L-гр. (накопитель)

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

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

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

Сообщ. Вер-ти. Разбиения. Кодовые слова

U₁ 0,4 I 0

U₂ 0,3 II 10

U₃ 0,1 III 1100

U₄ 0,06 IV 1101

U₅ 0,04 V 11100

U₆ 0,04 11101

U₇ 0,03 11110

U₈ 0,03 11111

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

Процедура Хаффмена осуществляет построение эффективного кода следующим образом:

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

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

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

4. действия (2) и (3) выполняются до тех пор, пока не образуется в последнем столбце псевдосообщение с вероятностью ²1².

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

Ниже приведен пример построения диагональной таблицы.

U_i P_i

U₁ 0,4 0,4 0,4 0,4 0,4 0,4 0,6 1

U₂ 0,16 0,16 0,16 0,18 0,26 0,34 0,4

U₃ 0,12 0,12 0,14 0,16 0,18 0,26

U₄ 0,10 0,10 0,12 0,14 0,16

U₅ 0,08 0,08 0,10 0,12

U₆ 0,08 0,08 0,08

U₇ 0,04 0,06

U₈ 0,02

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

1

1 0 U₁ 0

0,6 0,4 U₂ 110

1 0 U₃ 100

0,34 0,26 U₁ U₄ 1111

1 0 1 0 U₅ 1110

U₆ 1011

0,18 0,16 0,14 0,12 U₇ 10101

U₂ U₃ U₈ 10100

1 0 1 0

0,10 0,08 0,08 0,06

U₄ U₅ U₆ 1 0

0,04 0,02

U₇ U ₈