Методическое пособие 640

1)с коммутацией каналов;

2)с коммутацией сообщений;

3)с комбинированной коммутацией.

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

Метод коммутации сообщений осуществляется без орга-

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

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

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

21

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

ным способом коммутации.

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

делить на радиальные, кустовые, цепочечные и смешанные.

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

22

2. Энтропия как мера неопределенности информации

2.1. Вероятностное описание дискретных ансамблей

Пусть Х = { х1, х2, х3, ... , хN } – множество, состоящее из N элементов. Говорят, что на множестве Х задано распределение вероятностей p(х), если каждому х поставлено в соответствие число p(х) такое, что для всех i = 1, N; p(хi) ≥ 0, ∑ p(хi) = 1.

Множество Х вместе с заданным на нём распределением веро-

ятностей называется дискретным вероятностным ансамблем

или просто дискретным ансамблем и обозначается {Х, p (х )}.

Пусть Х = { х1, х2, х3, ... , хN } и Y = {y1, y2, y3, ... , yK } – два конечных множества. Произведением множеств {XY} называется множество, элементы которого представляют собой все

возможные упорядоченные пары произведений xi yj , i = 1, N; j = 1, K. Если каждой паре xi yj поставлена в соответствие вероятность p(xi yj), то имеем произведение ансамблей

{XY, p(xy)}. Для элементов объединенного ансамбля имеют ме-

сто обычные свойства вероятностей:

Из указанных свойств, в частности, следует, что если задано произведение ансамблей, то всегда могут быть найдены исходные ансамбли {X, p(x)} и {Y, p(y)}. Обратное возможно лишь в случае, когда элементы исходных ансамблей независимы, при этом p(xi yj) = p(xi )· p(yj ). В общем случае для зави-

симых ансамблей p(xi yj) = p(xi) · p(yj / xi) = p(yj) · p(xi / yj), т.е.

для определения вероятности элемента объединенного ансамбля необходимо задание условной вероятности появления элемента одного из ансамблей, при условии, что реализовался элемент другого ансамбля:

2.2. Энтропия, как мера неопределенности выбора

Для сравнения между собой различных источников сообщений необходимо ввести некоторую количественную меру, которая дала бы возможность объективно оценить информацию, содержащуюся в сообщении. Такая мера впервые была введена K. Шенноном в 1948 г., а затем более строго определена А.Я. Хинчиным. Рассмотрим основы информационного подхода Шеннона [1].

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

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

Пусть задан дискретный ансамбль с N возможными состояниями:

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

24

сти:

Мера предложена Р. Хартли в 1928 г. Свойства меры Хартли:

1)она является монотонной функцией числа элементов;

2)при N = 1 – H(X) = 0, т.е. мера равна нулю, когда неопределенность отсутствует;

3)мера аддитивна, т.е. объединение, например, двух множеств X и Y с числом элементов N и M, можно рассматривать как одно множество, включающее N х M различных комбинаций xi yj, i = 1, N; j = 1,M , при этом

H(XY) = log a (NM ) = log a N + log a M .

К сожалению, мера Р. Хартли не учитывает того факта, что вероятности pi , i = 1, N в (2.3) могут быть различны. Поэтому она используется лишь в случае равновероятных элементов множества. При неравновероятных элементах неопределенность меньше. Например, неопределенность выбора в случае двух элементов с априорными вероятностями 0,9 и 0,1 меньше, чем в случае равновероятных элементов (0,5; 0,5). Поэтому естественным является требование, чтобы мера неопределенности была непрерывной функцией вероятностей pi , i = 1,N элементов. Удовлетворяющая этому требованию мера предложена К. Шенноном и называется энтропией:

Основание а логарифма, вообще говоря, не имеет принципиального значения. Если логарифм десятичный (lg), энтропия и количество информации определяются в десятичных единицах дитах, если логарифм натуральный (ln), единицей измерения является нат. Наиболее широко используется двоичная единица информации – bit (сокращение от английского binary digit), соответствующая логарифму по основанию два (log2), которая и будет использоваться далее.

25

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

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

Покажем связь меры К. Шеннона с мерой Р. Хартли. Если все элементы множества равновероятны, т.е. pi = 1/N для всех i = 1, N, то

Таким образом, мера Р. Хартли – частный случай меры К. Шеннона для равновероятных элементов. Можно также показать, что мера К. Шеннона является обобщением меры Хартли на случай неравновероятных элементов.

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

2.3. Свойства энтропии

1) Энтропия величина ограниченная, вещественная и неотрицательная. Свойство легко проверяется по формуле (2.5) с учетом того, что 0 < p (xi ) < 1 для всех i = 1, N.

2) H (X) = 0, если вероятность одного из элементов множества равна 1.

26

3) Энтропия максимальна, когда все элементы множества равновероятны и

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

4) Энтропия системы двух альтернативных событий может изменяться в пределах от нуля до единицы.

Рис. 2.1 Изменение энтропии в случае двух элементов

Для множества с двумя элементами зависимость энтропии от вероятности одного из элементов имеет вид, показанный на рисунке 2.1. В этом можно убедиться, подставляя конкретные значения в соотношение (2.5), которое в данном случае принимает вид

Проверкой (подставляя конкретные значения вероятности в (2.9)) легко убедиться, что при значениях pi = p1 = p2 энтропия H (Z) достигает максимума.

2.4. Энтропия сложных сообщений

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

27

Пусть объединенный ансамбль {XY} задан матрицей вероятностей всех его возможных элементов xi yj, i = 1, N, j = 1, M :

Суммируя вероятности по строкам и столбцам (2.10) в соответствии с (2.1) можно определить также ансамбли {X, p (x)}

и {Y, p (y)}:

пией Н(X) ансамбля {X, p(x)}. Вторая сумма (по j) во втором слагаемом характеризует частную неопределенность, приходящуюся на одно состояние ансамбля Y при условии, что реализовалось состояние – ансамбля X. Ее называют частной

28

условной энтропией и обозначают H (Y/xi ):

называется полной условной энтропией или просто условной энтропией. Таким образом, (2.12) с учетом (2.13), (2.14) можно записать в виде

Используя второе равенство в (2.11), по аналогии можно записать:

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

Можно также показать, что в случае объединения любого числа множеств {XYZ...} с зависимыми элементами имеет место равенство

H(XYZ…) = H(X) + H(Y/X) +H(Z/XY)+ … .

2.5. Основные свойства энтропии сложных сообщений

1) Энтропия объединения статистически независимых множеств равна сумме энтропий исходных множеств [7]. При установлении этого свойства используется свойство вероятностей независимых элементов: p(xi yj) = p(xi )· p(yj ).

Поскольку при этом

29

имеем

2)При полной статистической зависимости сообщений X

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

H (XY) = H (X) = H (Y).

3) Условная энтропия всегда меньше или равна безуслов-

ной:

0 ≤ H (Y /X ) ≤ H (Y);

0 ≤ H (X /Y ) ≤ H (X).

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

Аналогично, для систем более высокого порядка:

H(X/YZ) ≤ H(X/Y).

4) Для совместной энтропии всегда справедливо соотношение

30