Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
P(U) = -. (3.13)
Il
вероятность того, что наугад взятая пара "входной-выходной символы" окажется типа "нуль - единица", -
р(0,1) = —, (3.14)
п
вероятность того, что наугад взятая пара "входной-выходной символы" окажется типа "единица - нуль", -
р( 1.0) = -, (3.15)
и
вероятность того, что наугад взятая пара входной-выходной символы" окажется типа "нуль - нуль", -
/>(0,0) = -. (3.16)
и
В дальнейшем изложении приведенные соотношения будем принимать за значения соответствующих вероятностей, не оговаривая каждый раз, что речь идет лишь о статистических их оценках. Примем также, что появление каждого символа как входной, так и выходной последовательностей не зависит от того, какие символы ему предшествовали.
С целью упрощения последующего изложения в некоторых из формул (3.1)-^(3.16) наряду с обозначениями типа р( ) будем использова ть также обозначения to, to,, to2, X, Xx и X2-
59
ГЛАВА 1При вычислении значений вероятностей (3.1)+(3.16) исходными являются четыре независимые переменные: а, Ь, с и d. Если ввести в
рассмотрение набор новых переменных ci = a / п b = b / п, с = с / п и d = d / п, то. очевидно, будет иметь место
a + b+c+d = (3.17)
т.е. из четырех вновь введенных переменных а, Ь, с и d только три окажутся независимыми. С другой стороны, поскольку все значения вероятностей (3.1)+(3.16) можно выразить через эти вновь введенные переменные, то можно утверждать, что лишь три из всех значений вероятностей (3.1)+(3.16) являются независимыми. Например, при заданных значениях со, A11 и X2 можно определить все остальные значения вероятностей. Так,
X = 1 - X2 + ш(Х, +X2- 1), (3.18)
Wj =--Г-. . (3.19)
1 -X2 +X2-I)
CO2= V^2 n (3-20)
X2 -(0(/.] + A2 -1)
Легко заметить, что пара значений X1 и X2 является вероятностной характеристикой собственно "черного ящика" - канала связи, тогда как значение оо характеризует входную последовательность двоичных символов. Естественно, что задание тройки значений X1, X2 и оо полностью предопределяет дальнейший ход событий, т.е. значения всех остальных вероятностей.
о р ЭНТРОПИИНАЯ ТЕОРИЯ ПЕРЕДАЧИ
ИНФОРМАЦИИ. ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА СВЯЗИ
На основе значений вероятностей (3.1)+(3.16) можно определить значения следующих энтроиий:
энтропия ансамбля (х, у) случайных величин х и у -
Н[х,у] = ~(p(lDlog2 р(1, 1) + р(0, Dlog2 р(0,1) +
+p(l,0)log2p(l,0) + p(0,0)log2p(0,0)), (3.21)
энтропия случайной величины х -
Н[х] = -(ш Iog2 00 + (1 - (O)Iog2 (1 - (О)), (3.22)
энтропия случайной величины у -
Н[у] = -(X Iog2 X + (1 - X)log2 (1 - X)), (3.23)
60условная (остаточная) энтропия случайной величины х при известном значении у -
Н[х I у] = IOg2COl +(I-COl)Iog2(I-COl))-
-(I-^Xco2Iog2 CO2 +(I-CO2)Iog2(I-CO2)), (3.24)
условная (остаточная) энтропия случайной величины у при известном значении X -
Н[у / X] = -со(Х, Iog2 X1 + (I - X1) log2(l - X1)) -
-(1 - со)(Х2 Iog2 X2 +(I - X2)Iog2(I-X2)). (3.25)
Из приведенных в (3.21)+(3.25) определений легко убедиться, что
Н[х, у] = Н[х] + Н[у/х] = H[у] + Н[х/у]. (3.26)
Величина
1\х,у)=Н[х}-Н[х/у] (3.27)
равна среднему количеству информации о случайной величине Jt, содержащемуся в одном сообщении о том, какое именно конкретное значение получила случайная величина у. Аналогично, величина
1[у, х]=Н[у]-Н[уМ (3.28)
равна среднему количеству информации о случайной величине у, содержащемуся в одном сообщении о том, какое именно конкретное значение получила случайная величина х. Из (3.26) и (3.27) с учетом (3.21) легко заметить, что имеет место
Их, у] = l[y, X] = Н[х] + Hly] - Hlx, у]. (3.29)
Информационная сущность канала передачи заключается в том, чтобы, заполучив конкретные значения случайной величины у, можно было бы судить о том, какое конкретное значение при этом имела случайная величина X. Степень "проблематичности" угадывания входного символа, когда известен выходной символ, характеризуется остаточной энтропией Hlxly].
С помощью (3.19)+(3.20) легко установить, что когда канал связи является идеальным, т.е. при условии
X1 = X2 = 1, (3.30)
имеет место
со і = CO2 = 1,
т.е. Hlxly] = 0.
К такому же результату мы приходим в случае идеального инвертора, когда имеют место
Xi=X2=O, (3.31)
61
ГЛАВА 1С помощью тех же (3.19)+(3.20) отсюда получим:
со і =CO2 = О,
т.е. Н[х/у] = 0. В обоих этих случаях значение выходного символа оказывается достаточным, чтобы точно знать, каким является входной символ. Это и естественно, гак как при этом количество информации о входном символе, содержащееся в каждом сообщении о том, какое именно конкретное значение получил выходной символ, равно
/[х, у] = tff.vl - Н[х/у] = Н[х], (3.32)
т.е. ровно столько, чтобы полностью ликвидировать равную Н[х] исходную неопределенность по угадыванию входного символа.
При работе с реальными каналами связи значение H[х/у] оказывается большим нуля, вследствие чего количество информации
/La , > j = //La J - //[.v/ v]