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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для дискретной случайной величины, заданной законами распределения P(X = X_i) = p_i, P(Y = Y_j) = q_j и совместным распределением P(X = X_i; Y = Y_j) = p_ij , количество информации, содержащееся в X относительно Y,

I(X; Y) = Sp_ij log₂(p_ij/(p_iq_j)).

^i;j

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

I(X; X) = - Sp_i log₂(p_i).

ⁱ

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

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

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

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

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

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

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

- I(X; Y) = Sp_ij log₂((p_iq_j)/p_ij) = Sp_ij (((p_iq_j)/p_ij) -1)/ln2 = S(p_iq_j - p_ij)/ln2 =

^{i;j i;j i;j}

Sp_iSq_j - Sp_ij)/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) = Sp_ij log₂(p_ij).

^i;j

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

Sp_ij = p_i, Sp_ij = p_j,

^{i j}

HX = - Sp_i log₂(p_i) = - Sp_ij log₂(p_i), HY = -Sp_j log₂(p_j) = - Sp_ij log₂(p_j)

^{i i,j j i,j}

следует

HX + HY - H(X; Y) = Sp_ij(- log₂(p_i) - log₂(q_j) + log₂(p_ij)) = 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) = Sp_ij(-log₂(q_j) + log₂(p_ij)) = Sp_ij log₂(p_ij/q_j).

^{i,j i,j}

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

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

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

HX = - Sp_i log₂(p_i) = - 4 ¼ log₂ ¼ = 2

ⁱ

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

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

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

HX = ¾ log₂4/3 + 1/8 log₂8 +1/8 log₂16 = 19/8 – ¾ log₂3 = 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 log₂10 + 0.2 log₂5 + 0,3 log₂10/3 + 2 0,05 log₂20 =

0:9 + log₂5 - 0:3 log₂3 = 2.75 бит/симв.

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

Тогда p_i = P(X = i) = 1/6 при i = 1, 6 и q_j = 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) = Sp_ij log₂(p_ij/(p_iq_j)) = 6 1/6 log₂2 = 1 бит/симв.

^i;j

I(Y; Y) = Sq_j log₂(q_j)) = 2 1/2 log₂2 = 1 бит/симв.

^j

I(X; X) = Sp_i log₂(p_i)) = 6 1/6 log₂6 = 1 + log₂3 = 2.58 бит/симв.

ⁱ

Из 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 p_ij log₂ p_ij = log2 6 = 1 + log₂ 3 = HX,

^i;j

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

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

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

in f(s) = - log₂ 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) = - log₂(1 - cont(s)).