Энтропия дискретного источника сообщений с учетом статистических взаимосвязей

Энтропия источника, или количество информации по Шеннону, приходящееся в среднем на одно сообщение:

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

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

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

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

Модель третьего приближения учитывает связи между тремя соседними буквами

И т.д.

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

где H₀ - модель источника без учета статистических характеристик H0=log n.

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

Например, если возьмем 33 буквы русского алфавита, то значение энтропии будет убывать в зависимости от номера модели

H₀=log 33=5,04 бит; H₁ =4,04 бит

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

приближение	Nenglish=Ne=27	Nrussian=Nr=33
	I0E=log227=4,755»5 bit	I0R=log233=5,043999»6 bit
Т.е. для кодирования одной буквы английского алфавита требуется 5 бит, а для одной буквы русского – 6 бит. Но на самом деле вероятность появления букв, т.е. частоты появления букв в сообщениях различна. Если не делать различия между буквами е и ё, а также ъ и ь, при этом учесть частоты появления букв, то для русского алфавита получаем: Буква О Е,Ё а и т н с Р Р 0,09 0,072 0,062 0,053 0,053 0,053 0,045 0,040 И т.д.
	I1E= 4,04»5 bit	I1R=4,36»5 bit
Если же учесть корреляции, то есть вероятности появления сразу двух букв, то отбрасывается множество вариантов, как щц,фъ и т.п.
	I2E= 3,32»4 bit	I2R=3,52»4 bit
Если же учесть, что после пр обязательно идет гласная буква, а их 10, а не 33Þр=1/10, то есть корреляции трехбуквенных сочетаний, получаем
	I3E= 3,1»4 bit	I3R=3,03»4 bit
I5E= 2,1»3 bit, I8E= 1,9»2 bit. Получено, что последовательность I0,I1,I2.. является убывающей в любом языке.
¥	I¥E= 4,04»5 bit	I¥R=4,36»5 bit

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

I₀ – наибольшая информация на знак алфавита, которая может содержаться в знаке данного алфавита.

В связи с этим, Шеннон ввел понятие избыточности языка .

R является мерой бесполезно совершаемых альтернативных выборов при чтении текста. R_E»0,68»68%; R_R»60-70%.

+Это означает, что возможно трехкратное сокращение текста без ущерба их содержательной стороны и выразительности.

- Но при этом снижается разборчивость языка и уменьшает вероятность правильной интерпретации сообщений при наличии шума на линии связи;

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

ßИзбыточность языка является своего рода гарантией и страховкой разборчивости.

Сообщения и сигналы

Понятие носителя информации

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

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

Материальным носителем информации может быть:

- бумага;

- воздух;

- дискета;

- электромагнитное поле

- и пр.

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

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

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

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

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

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

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

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

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

Последовательность сигналов называется сообщением.

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

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

Соответствие между сообщением и содержащейся в нем информацией называется правилом интерпретации сообщения.

Это соответствие может быть однозначным и неоднозначным.

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

Неоднозначность соответствия между сообщением и информацией возможна в двух случаях:

1. одна и та же информация может передаваться различными сообщениями (например, прогноз погоды может быть получен по радио, из газеты, по телефону и пр.);

2. одно и то же сообщение может содержать различную информацию для разных приемников (примером может служить передача в 1936 г. по радио фразы «Над всей Испанией безоблачное небо», которое для непосвященных людей имело смысл прогноза погоды, а для знакомых с правилом интерпретации сигналом к началу военных действий).

Информационные процессы

Информационный процесс это изменение с течением времени содержания информации или представляющего его сообщения.

Различных видов информационных процессов оказывается немного:

1. порождение (создание, сбор) новой информации;

2. преобразование информации (т.е. порождение новой информации в результате обработки);

3. передача информации (распространение в пространстве).

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

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

Хранение информации

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

Передача информации

С передачей информации связаны понятия источника и приемника информации.

Источник информации это субъект или объект, порождающий информацию и представляющий ее в виде сообщения.

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

Приемник информации это субъект или объект, принимающий сообщение и способный правильно его интерпретировать.

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

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

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

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

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

Типы сигналов

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

Аналоговый сигнал

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

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

Пример математической записи сигнала: y(t) = 4.8 exp[-(t-4)2/2.8].

Пример графического отображения данного сигнала приведен на рисунке.

Сама функция и ее аргументы могут принимать любые значения в пределах некоторых интервалов y1 £y £ y2, t1 £t £ t2. Если интервалы значений сигнала или его независимых переменных не ограничиваются, то по умолчанию они принимаются равными от -¥ до +¥.

Дискретный сигнал

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

По множеству своих значений он является конечным (счетным) и описывается дискретной последовательностью отсчетов y(n∆t), где y1 £y £ y2, ∆t - интервал между отсчетами (интервал или шаг дискретизации), n = 0, 1, 2,...,N.

Величина, обратная шагу дискретизации: f = 1/∆t, называется частотой дискретизации.

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

Пример дискретизации аналогового сигнала, представлен на рисунке.

При ∆t = const (равномерная дискретизация данных) дискретный сигнал можно описывать сокращенным обозначением y(n).

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

Цифровой сигнал

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

Цифровой сигнал квантован по своим значениям и дискретен по аргументу. Задается цифровой сигнал, как правило, в виде дискретного ряда числовых данных - числового массива по последовательным значениям аргумента при ∆t = const, но в общем случае сигнал может задаваться и в виде таблицы для произвольных значений аргумента.

Цифровой сигнал конечен по множеству своих значений. Процесс преобразования бесконечных по значениям аналоговых отсчетов в конечное число цифровых значений называется квантованием по уровню, а возникающие при квантовании ошибки округления отсчетов (отбрасываемые значения) – шумами (noise) или ошибками (error) квантования (quantization).

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

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

Преобразования сигналов

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

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

Операция дискретизации заключается в определении моментов времени измерения сигнала.

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

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

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

Операция демодуляции выполняет интерполяцию или восстановление непрерывного сигнала по его измерениям.

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

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

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

Преобразование N1® N2

Примерами устройств, в которых осуществляется преобразование типа N1® N2, являются:

- микрофон (звук преобразуется в электрические сигналы);

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

- телекамера (изображение и звук превращаются в электрические сигналы);

- радио и телевизионный приемник (радиоволны преобразуются в электрические сигналы, а затем в звук и изображение);

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

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

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

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

Преобразование N ® D

Рассмотрим преобразование типа N ® D.

С математической точки зрения перевод сигнала из аналоговой формы в дискретную означает замену описывающей его непрерывной функции времени Z(t) на некотором отрезке [t1,t2] конечным множеством (массивом) {Z_i, t_i,} ( , где n количество точек разбиения временного интервала).

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

Операцияразвертки по времени заключается в том, наблюдение за значением величины Z производится в определенные моменты времени с интервалом Dt:

Квантование по величине это отображение значений параметра сигнала в конечное множество чисел, кратных некоторой постоянной величине шагу квантования (DZ).

Совместное выполнение обеих операций эквивалентно нанесению масштабной сетки на график Z(t), как показано на рисунке.

Рисунок - Дискретизация аналогового сигнала за счет операций развертки по времени и квантования по величине

Далее, в качестве пар значений {Z_i, t_i,} выбираются узлы сетки, расположенные наиболее близко к Z(t_i).

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

При такой замене довольно очевидно, что чем меньше n (больше D t), тем меньше число узлов, но и точность замены Z(t) значениями Z_i, будет меньшей.

Другими словами, при дискретизации может происходить потеря части информации, связанной с особенностями функции Z(t). На первый взгляд кажется, что увеличением количества точек n можно улучшить соответствие между получаемым массивом и исходной функцией, однако полностью избежать потерь информации все равно не удастся, поскольку n величина конечная. Ответом на эти сомнения служит теорема отсчетов, доказанная в 1933 г. В. А. Котельниковым:

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

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

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

Dt<=1/2*n_m (1.1)

Можно перефразировать теорему отсчетов:

Например, для точной передачи речевого сигнала с частотой до n_m = 4000 Гц при дискретной записи должно производиться не менее 8000 отсчетов в секунду; в телевизионном сигнале n_m = 4 МГц, следовательно, для его точной передачи потребуется около 8000000 отсчетов в секунду.

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

Например, человеческий глаз в состоянии различить около 16 миллионов цветовых оттенков; это означает, что при квантовании цвета нет смысла делать большее число градаций. При передаче речи достаточной оказывается гораздо меньшая точность около 1%; следовательно, для амплитуды звуковых колебаний DZ= 0,01*-Z^max, а алфавит для обозначения всех градаций громкости должен содержать 100 знаков.

Указанные соображения по выбору шага развертки по времени и квантования по величине сигнала лежат в основе оцифровки звука и изображения.

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

Преобразование D1®D2

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

Достоинства дискретной информации:

Преобразование сигналов N1®N2 происходит с потерями информации, а преобразование сигналов типа N®D, D®N, D1®D2может осуществляться без потери содержащейся в них информации. Другими словами, преобразование сообщений без потерь информации возможно только в том случае, если хотя бы одно из них является дискретным.

Достоинства дискретной информации:

- высокая помехоустойчивость;

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

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

- универсальность устройств.

Кодирование сигналов

Теория кодирования информации является одним из разделов теоретической информатики.

К основным задачам, решаемым в данном разделе, необходимо отнести следующие:

- разработка принципов наиболее экономичного кодирования информации;

- согласование параметров передаваемой информации с особенностями канала связи;

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

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