Теоретические основы системной теории информации

Системный анализ: книги. «Адаптивное управление сложными системами на основе теории распознавания образов» (В. С. Симанков, Е. В. Луценко)

В. С. Симанков, Е. В. Луценко

Глава 4: Теория информации и ее ключевые понятия

Термин «информация» произошел от латинского слова informatio, которое означает разъяснение, осведомление [351]. Данное понятие является одним из ключевых понятий кибернетики и понимается как совокупность каких-либо сведений или данных.

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

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

Большой вклад в дальнейшее развитие и обобщение теории информации внесли отечественные ученые А.Н. Колмогоров, А.А. Харкевич, Р.Л. Стратанович [373]. Недавно германские исследователи советских архивов сообщили о том, что теория, известная сегодня как теория Шеннона, была создана А.Н.

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

Подход Р. Хартли

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

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

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

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

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

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

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

Таблица 4.1 — К выводу формулы количества информации по Р.Хартли

Количество двоичных разрядов (i) Количество состояний, которое можно пронумеровать i-разрядными двоичными числами (N) Основание системы счисления 10 16 2

1	2	01	01	01
2	4	0123	0123	00011011
3	8	01234567	01234567	000001010011100101110111
4	16	0123456789101112131415	0123456789ABCDEF	0000000100100011010001010110011110001001101010111100110111101111
…	…
i	2i

Очевидно, количество этих чисел (элементов) в множестве равно:

N = 2i.

Рассмотрим процесс выбора чисел из рассмотренного множества. До выбора вероятность выбрать любое число одинакова. Существует объективная неопределенность в вопросе о том, какое число будет выбрано. Эта неопределенность тем больше, чем больше N — количество чисел в множестве, а чисел тем больше — чем больше разрядность i этих чисел.

Примем, что выбор одного числа дает нам следующее количество информации:

i = Log2(N).

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

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

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

N2 = (N1)2,

то

I2 = 2⋅I1,

F(N1⋅N1) = F(N1) + F(N1).

Это невозможно, если количество информации выражается линейной функцией от количества элементов в множестве. Но известна функция, обладающая именно таким свойством: это Log:

Log2(N2) = Log2(N1)2 = 2⋅Log2(N1).

Это второе требование называется требованием аддитивности.

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

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

Подход К. Шеннона

Клод Шеннон основывается на теоретико —вероятностном подходе. Это связано с тем, что исторически шенноновская теория информации выросла из потребностей теории связи, имеющей дело со статистическими характеристиками передаваемых сообщений и каналов связи.

Пусть существует некоторое конечное множество событий (состояний системы): X = {x1, x2, …, xN}, которые могут наступать с вероятностями: p(xi), соответственно, причем множество вероятностей удовлетворяет естественному условию нормировки:

∑p(xi) = 1

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

H(X) = -∑p(xi)⋅Log2(p(xi))

(4.1)

Если измерять количество информации изменением степени неопределенности, то шенноновское количество информации численно совпадает с энтропией исходного множества:

I(X) = -∑p(xi)⋅Log2(p(xi))

(4.2)

Связь формул К. Шеннона И Р. Хартли

Следуя [391], приведем вывод выражения Шеннона (4.2) непосредственно из выражения Хартли для количества информации: I = Log2(N).

Пусть события исходного множества мощности N равновероятны:

p(xi) = 1/N,

тогда учитывая, что

Log(1/N) = Log(1)⋅Log(N) = Log(N),
∑1/N = 1

непосредственно из формулы Хартли получаем

I(X) = -∑1/N⋅Log2(1/N) = -∑p(xi)⋅Log2(p(xi)).

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

Сравнение подходов Р. Хартли и К. Шеннона

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

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

Таким образом, различие между подходами Хартли и Шеннона к построению теории информации соответствует различию между непараметрическими и параметрическими методами в статистике.

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

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

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

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

Источник: http://victor-safronov.ru/systems-analysis/books/simankov-lucenko/17.html

Основы теории информации. Учебное пособие

1. Информационные характеристики сигнала

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

3. Энтропия дискретного источника с зависимыми сообщениями

4. Избыточность источника

5. Производительность источника

6. Совместная энтропия двух источников

7. Взаимная информация источников сообщений

8. Скорость передачи и пропускная способность канал связи

9. Статистическое кодирование дискретных сообщений

10. Энтропия непрерывного источника и её свойства

11. Пропускная способность непрерывного канала связи

12. Эпсилон-энтропия источника непрерывных сообщений

1. Информационные характеристики сигнала

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

В математической теории связи(теории информации) исходят из того, что в некотором сообщении xi количество информации I(xi) зависит не от её конкретного содержания, степени важности и т.д., а от того, каким образом выбирается данное сообщение из общей совокупности возможных сообщений.

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

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

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

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

2. Количество информации о достоверном событии (P(xi)=1) должно равняться нулю, так как такое сообщение не увеличивает наших знаний о данном объекте или явлении.

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

(1)

Чаще всего логарифм берётся с основанием 2, реже – с основанием e:

двоичных систем информации(бит)

натуральных единиц информации(нит)

Одну единицу информации содержит сообщение, вероятность выбора которого равняется 1/2.

В этом случае

двоичных единиц информации (бит)

При применении натуральных логарифмов одну натуральную единицу информации содержит сообщение, вероятность выбора которого равняется 1/e: натуральных единиц информации (нит)

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

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

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

В теории информации чаще всего необходимо знать не количество информации I(xi) содержащееся в отдельном сообщении, а среднее количество информации в одном сообщении, создаваемом источником сообщений.

Если имеется ансамбль(полная группа) из k сообщений x1, x2,… xi,..xk с вероятностями P(x1)…P(xk), то среднее количество информации, приходящееся на одно сообщение и называемое энтропией источника сообщений H(x) определяется формулой

(2) или

(3)

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

Рассмотрим свойства энтропии.

1. Чем больше неопределённость выбора сообщений, тем больше энтропия. Неопределённость максимальна при равенстве вероятностей выбора каждого сообщения:

В этом случае

(4)

т.е. максимальная энтропия равна логарифму от объёма алфавита.

Например, при k=2(двоичный источник)

бит

2. Неопределённость минимальна, если одна из вероятностей равна единице, а остальные – нулю(выбирается всегда только одно, заранее известное сообщение, например – одна буква):

. В этом случае

Эти свойства энтропии иллюстрируются следующим образом.

Пусть имеется двоичный источник сообщений, т.е. осуществляется выбор из двух букв (k=2): x1 и x2 P(x1)+P(x2)=1

Тогда

Зависимость H(x) от вероятностей выбора для двоичного источника приведена на рис.1

Рис. 1

3. Укрупним алфавит. Пусть на выходе двоичного источника имеется устройство, которое группирует буквы в слова из n букв. Тогда k=2n слов(объём алфавита). В этом случае

бит

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

4. Энтропия дискретного источника не может быть отрицательной.

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

3. Энтропия дискретного источника с зависимыми сообщениями

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

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

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

(7)

где c – произвольное положительное число.

Если объём алфавита источника равен K, а число связанных букв, которые необходимо учитывать при определении вероятности очередной буквы, равно порядку источника n, то каждой букве может предшествовать M=Kn различных сочетаний букв(состояний источника), влияющих на вероятность появления очередной буквы xi на выходе источника. А вероятность появления в сообщении любой из K возможных букв определяется условной вероятностью (7) с учётом предшествующих букв, т.е. с учётом M возможных состояний. Эти состояния обозначим как q1, q2,..qm.

Рассмотрим два простых примера.

Пример 1. Пусть имеется двоичный источник(объём алфавита k=2), выдающий только буквы a и b; порядок источника n=1. Тогда число состояний источника M=K1=21=2(назовём эти состояния q1 и q2). В этом случае вероятности появления букв a и b будут определяться следующими условными вероятностями:

P(a/q1=a), P(a/q2=b),

где: q1=a – 1е состояние источника

q2=b – 2е состояние источника

т.е. P(q1)=P(a); P(q2)=P(b)

Пример 2. Пусть по-прежнему K=2(буквы a и b), однако число связанных букв n=2. Тогда M=22=4(четыре возможных состояния): (a,a)=q1, (a,b)=q2, (b,a)=q3, (b,b)=q4

В этом случае имеем дело со следующими условными вероятностями

P(a/a,a); P(a/a,b); P(a/b,a); P(a/b,b); P(b/a,a)… и т.д. Вероятности состояний определяются равенствами P(q1)=P(a,a), P(q2)=P(a,b), P(q3)=P(b,a), P(q4)=P(b,b).

Энтропия эргодического дискретного источника определяется в два этапа:

1) Вычисляется энтропия источника в каждом из M состояний, считая эти состояния известными:

для состояния q1
q2

………..……………………………..….… qm

2) Далее находим H(x) путём усреднения по всем состояниям q;

(8)

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

4. Избыточность источника

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

Чем ближе энтропия источника к максимальной, тем рациональнее работает источник. Чтобы судить о том, насколько хорошо использует источник свой алфавит, вводят понятие избыточности источника сообщений: ячс& (9)

или

&

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

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

5. Производительность источника

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

, [Бит/с] (10)

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

Однако в последней формуле P(τi) можно заменить на P(xi) (вероятность i-того сообщения), т.к. эти вероятности равны. В результате получаем

(11)

а производительность источника будет равна

(12)

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

(13)

Для двоичного источника, имеющего одинаковую длительность элементов сообщения (k=2, =τ) имеем

бит/с (14)

При укрупнении алфавита в слова по n букв, когда k=2n, =nτ, имеем

бит/с, что совпадает с (14)

Таким образом, путём укрупнения алфавита увеличить производительность источника нельзя, так как в этом случае и энтропия, и длительность сообщения одновременно возрастают в одинаковое число раз (n).

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

где m – основание кода

6. Совместная энтропия двух источников

Пусть имеется два дискретных источника с энтропиями H(x) и H(y) и объёмами алфавитов k и l (рис. 2)

Рис. 2

Объединив оба эти источника в один сложный источник и определим совместную энтропию. Элементарное сообщение на выходе системы содержит элементарное сообщение xi и сообщение yi. Алфавит сложной системы будет иметь объём K.L, а энтропия будет равна

(15)

или

(16)

По теореме умножения вероятностей

Подставляя эти соотношения в (15), получим (17)

Аналогично можно получить

(18)

Здесь H(x) и H(y) – собственная энтропия источников x и y

(19)

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

Если источники независимы, то

P(y/x)=P(y) и H(y/x)=H(y). В этом случае H(x,y)=H(x)+H(y).

Если источники частично зависимыми, то H(x,y)

Источник: https://siblec.ru/telekommunikatsii/osnovy-teorii-informatsii

Глава 7. Основы теории информации

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

Задачами теорииинформации являются:

1. Установлениемеры количества информации.

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

3. Определениенаилучших условий кодирования,обеспечивающих скорость передачиблизкой к пропускной способности канала.

7.1.1. Определение количества информации

Модели, используемыев теории информации

Понятие информациятождественнопонятию сведенияили сообщенияи ассоциирует с наличием по крайнеймере двух взаимодейст­вующих системА и В (рис.7.1), одна из которых А являетсяисточникоминформации (передатчиком), а вторая Вявляется наблю­даемой системой(приемником). Вне указанной схемы понятие«информация»те­ряет смысл.

Сообщение— это то,что можно сообщить, а сообщить можнотолько состояние системы. Следовательно, сообщение —это состояние системы.

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

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

Разрешенные уровни как раз и являютсясостояниями источника.

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

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

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

Множества состоянийХи Y,соответственносистем Аи В,в зависимостиот того, в каком отношении онирассматри­ваются, можно интерпретироватькак множества состояний, сообщений исобытий.

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

Сигнал —это материальный переносчик информациив пространстве и во времени.

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

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

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

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

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

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

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

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

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

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

Остановимся нарассмотрении мер информации в первыхдвух теориях.

Комбинаторноеопределение количества информации

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

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

Количественнаямера информации устанавливаетсясле­дующими аксиомами.

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

В качествеколичественной меры информации можновы­брать непосредственно числосостояний системы Nx,которое является единственнойхарактеристикой множества X.

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

Аксиома2. Неопределенностьсостояния сложной системы, состоящейиз двух подсистем, равна сумменеопределен­ностей подсистем.

Кколичественной мере информацииестественно выдвинуть следующиетребования:

1. Количество информации в сообщении о достоверном событии равно нулю.

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

3. Количество информации не должно зависеть от качественного содержания сообщения. То есть от степени важности или полезности для получателя.

В соответствиис требованием 2, если для снятиянеопределенности первой подсистемынеобходимо количество информации,равное ,а для второй подсистемы количествоинформации, равное,то дляснятия неопределенности сложной системынеобходи­мо количество информации,равное

Источник: https://StudFiles.net/preview/3047367/