Глава 2. транспортировка данных

Постановка задачи

Процедура транспортировки информации [1] имеет два вида: традиционная связь; вычислительные сети. В параграфах 2.1 – 2.4 рассмотрим традиционную связь [2 – 6, 9], а в параграфе 2.5 – специфику компьютерной связи [7, 8].

глава 2. транспортировка данных - student2.ru Общая схема процедуры транспортировки данных представлена на рис. 2.1.

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

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

Сигнал [3] – форма передачи информации.

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

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

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

Кодирование – преобразование дискретной информации (шифрование, сжатие, защита).

Развернем рис. 2.1 с учетом кодирования (рис. 2.2).

глава 2. транспортировка данных - student2.ru

Эта схема определяет последующие параграфы данной главы.

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

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

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

I(X; Y) = Spij log2(pij/(piqj)).

i;j

Очевидно выражение для собственной информации

I(X; X) = - Spi log2(pi).

i

Энтропия дсв определяется так

H(X) = HX = I(X;X).

Энтропия представляет собой среднее значение количества собственной информации в сообщениях ансамбля X.

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

1. I(X; Y) > 0, из I(X; Y) = 0 следует, что X и Y независимы.

Из неравенства ex-1 ³ x логарифмированием получаем x – 1 ³ lnx или (x - 1)/ln2 ³ lg2x.

Тогда при pij = pipj, т.е. при независимых дсв

- I(X; Y) = Spij log2((piqj)/pij) = Spij (((piqj)/pij) -1)/ln2 = S(piqj - pij)/ln2 =

i;j i;j i;j

SpiSqj - Spij)/ln2 = (1 - 1)/ln2 = 0

i j i;j

2. I(X; Y) = I(Y; X) следует из симметричности аргументов.

3. HX = 0, X – константа. Все члены суммы – нули, что возможно лишь при X – константе.

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

i;j

Очевидно, что

Spij = pi, Spij = pj,

i j

HX = - Spi log2(pi) = - Spij log2(pi), HY = -Spj log2(pj) = - Spij log2(pj)

i i,j j i,j

следует

HX + HY - H(X; Y) = Spij(- log2(pi) - log2(qj) + log2(pij)) = I(X; Y).

i,j

5. I(X; Y ) ≤ I(X;X). Если I(X; Y) = I(X;X), TO X – функция от Y.

HY - H(X; Y) = Spij(-log2(qj) + log2(pij)) = Spij log2(pij/qj).

i,j i,j

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

Приведем несколько числовых примеров.

Пример 2.1.В заезде участвуют 4 лошади с равными вероятностями на победу, составляющими ¼. Найти энтропию.

HX = - Spi log2(pi) = - 4 ¼ log2 ¼ = 2

i

Пример 2.2.Пусть имеется переменная X для примера 2.1 с таким распределением:

P(X = 1) = ¾; P(X = 2) = 1/8; P(X = 3) = P(X = 4) = 1/16.

Фаворит – лошадь с номером 1.

HX = ¾ log24/3 + 1/8 log28 +1/8 log216 = 19/8 – ¾ log23 = 1.186 бит/симв.

Пример 2.3.Найти энтропию для X

X 1 2 3 4 5 6 7 8

p 0.1 0.2 0.1 0.05 0.1 0.05 0.3 0.1.

Тогда

HX = 4 0.1 log210 + 0.2 log25 + 0,3 log210/3 + 2 0,05 log220 =

0:9 + log25 - 0:3 log23 = 2.75 бит/симв.

Пример 2.4.Пусть дсв X есть количество очков, выпадающей на игральной кости, а дсв Y является нулем, выпадает нечетное количество очков, и единица, если количество очков четно. Найти I(X; Y) I I(Y; Y).

Тогда pi = P(X = i) = 1/6 при i = 1, 6 и qj = P(Y = j) при j= 0, 1.

Пусть совместное распределение

X 1 3 5 2 4 6 |1 3 5 2 4 6

Y 0 0 0 1 1 1 |1 1 1 0 0 0

p 1/6 | 0

Тогда

I(X; Y) = Spij log2(pij/(piqj)) = 6 1/6 log22 = 1 бит/симв.

i;j

I(Y; Y) = Sqj log2(qj)) = 2 1/2 log22 = 1 бит/симв.

j

I(X; X) = Spi log2(pi)) = 6 1/6 log26 = 1 + log23 = 2.58 бит/симв.

i

Из I(X; Y) = I(Y; Y) и пятого свойства информации следует, что информация об X полностью определяет Y, поскольку I(X; Y) ¹ I(X; X). Y функционально зависит от X, а X от Y функционально не зависит.

Можно определить I(X; Y) через энтропию.

H(X; Y ) = - S pij log2 pij = log2 6 = 1 + log2 3 = HX,

i;j

I(X; Y ) = HX + HY - HX = HY = 1 бит/симв.

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

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

in f(s) = - log2 p(s)

где s – предложение (естественного языка), смысл которого измеряется, p(s) – вероятность истинности s.

Эта мера обладает следующими свойствами.

1. Если (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» следует, что inf(s2) > inf(s1) или что s2 исключает больше возможностей, чем s1.

Возможно использовать меру cont(s) = 1 - p(s). Иначе говоря cont(s) = 1 – 2-inf(s) или in f(s) = - log2(1 - cont(s)).

Наши рекомендации