Передачи информации
Сигнал
Принято считать, что передача информации происходит тогда, когда некоторый объект (получатель информации) приобретает знания, сведения, данные о состоянии другого объекта (источника информации).
Сигналами называются состояния объектов в цепи, связывающей источник с получателем, при условии, что изменения состояния источника приводит к изменению состояний остальных объектов в этой цепи по правилам, хотя бы частично известным получателю. Такие правила называются кодом.
Следует подчеркнуть, что всегда можно указать пару крайних элементов в этой цепи сигналов: переданный сигнал (сообщение), то есть состояние источника информации, и принятый сигнал, то есть состояние объекта, доступного для непосредственного наблюдения получателем.
Состояние любого объекта можно математически описать при помощи набора чисел (параметров). Поскольку значения этих параметров обычно изменяются со временем, то математической моделью сигнала служит функция времени (и, возможно, других аргументов, например, пространственных координат). Интересоваться значением передаваемого сигнала X(t) и наблюдать с этой целью принимаемый сигнал Y(t) имеет смысл только в том случае, когда значения этих функций заранее не известны получателю.
Наиболее распространенной математической моделью сигнала, удовлетворяющей этому требованию и допускающей строгое количественное описание, является случайная функция. При этом конкретной реализации сигнала, возникшей в результате опыта, ставится в соответствие конкретная реализация этой случайной функции. Множество всех возможных реализаций сигнала с указанием вероятностной меры, соответствующей каждой из реализаций, называется ансамблем.
Случайная функция называется дискретной по данному параметру, если множество возможных значений этого параметра конечно. В противном случае, когда параметр может принимать любое значение из непрерывной области, функция называется непрерывной по данному параметру. Переход от непрерывного сигнала к дискретному называется квантованием (дискретизацией), а обратный переход - интерполяцией (восстановлением). Случайная функция, дискретная по времени, называется случайной последовательностью.
Типичная процедура квантования по времени заключается в том, что берут отчеты исходной непрерывной функции X(t) (рис.1.1,а) в моменты времени t1, t2 ..., tn отстоящие один от другого на величину, называемую шагом квантования по времени (рис.1.1, б).
Рис.1.1
Полученная в результате квантования случайная последовательность - система случайных непрерывных величин X(1), X(2), ..., X(n) в соответствии с теоремой В.А. Котельникова полностью определяет случайную исходную функцию X(t), если n®¥, а шаг квантования выбран из условия Dt£(1/2) FВ, где FВ - верхняя граничная частота в спектре сигнала X(t).
Квантование по уровню, т.е. переход от непрерывных величин X(k) к дискретным Xj(k), иллюстрируется на рис.1.1, в.
В дальнейшем будем рассматривать сведущие модели сообщений и сигналов:
а) непрерывная или дискретная случайная величина;
б) непрерывная или дискретная случайная последовательность, т.е. система n непрерывных или дискретных случайных величин;
в) непрерывная случайная функция, т.е. непрерывная функция времени, значение которой в любые моменты времени являются непрерывными случайными величинами.
Модель сигнала - случайная величина
Простейшая модель сигнала - случайная величина X.
Полное математическое описание дискретной случайной величины X содержит ее закон распределения, т.е. таблица, в которой перечислены все возможные значения этой случайной величины x1, x2, ... и соответствующие им вероятности p(x1), p(x2),... . Дискретная случайная величина X называется m-ичным символом (буквой, цифрой), если множество ее возможных значений x1, x2, ..., xm конечно. Это множество называется алфавитом, а число m - основанием кода. Термин "символ xj" применяется для указания конкретного j-го элемента алфавита.
Рис. 1.2
Полное математическое описание непрерывной случайной величины X содержит ее функция распределения F(x) либо плотность вероятности W(x), если последняя существует.
Типичная процедура квантования непрерывной величины X, т.е. переход к дискретной величине X', заключается в следующем. Область возможных значений случайной величины X делят на m интервалов с длинами Dx1, Dx2, …, Dxm и задают множество x1, x2, …, xm возможных значений дискретной случайной величины X'. Обычно, хотя это не обязательно, в качестве xj выбирают середину j-го интервала. Далее считают, что дискретная величина X' приняла значение xj, если реализация непрерывной случайной величины X попала внутрь j-го интервала (рис.1.2). Вероятность этого события равна
. (1.1a)
Если длины интервалов настолько малы, что относительное изменение плотности W(x) внутри интервала незначительно, то приближенно имеем
(1.1 б)
Квантование называется равномерным, если длины всех интервалов равны между собой, тогда величина Dx=Dxj называется шагом квантования по уровню.
Кроме закона распределения для описания случайной величины нередко используют числовые характеристики, являющиеся средними значениями некоторых функций j (x) от случайной величины X. Такие характеристики вычисляют по формуле
(1.2)
Простейшей моделью пары "сообщение - сигнал" является система двух случайных величин XY.
Если эти случайные величины дискретны, то их полной характеристикой служит набор ms совместных вероятностей p(xj, yk), где m - основание кода сообщения, s - основание кода сигнала.
Сигнала непрерывных случайных величин XY полностью характеризуется функцией распределения F(x,y) или совместной плотностью вероятности W(x,y) при условии существования последней.
Для каждой из случайной величин, входящих в систему, можно вычислить безусловные и условные вероятности (плотности вероятности):
, (1.3)
, (1.4)
причем по формулам умножения вероятностей:
(1.5)
Случайные величины X и Y статистически независимы, если для всех значений x и y выполняется условие
(1.6)
Числовые характеристики системы вычисляются по формуле
(1.7)
Условные числовые характеристики, например, среднее значение j(x,y) при условии, что случайная величина Y приняла конкретное значение yk, вычисляется по формуле
(1.8)
Модель сигнала - случайная последовательность
Более сложной моделью сообщения и сигнала являются случайные последовательности.
Дискретная по времени и по уровню случайная функция X(t) полностью определяется последовательностью n случайных чисел - отчетов, X(1),…,X(n) взятых в моменты времени t1, t2, …, tn. Совокупность символов X(1),…,X(n) образует кодовое слово, а число n символов в слове называется его длиной.
Аналогично для сигнала Y(t) имеем последовательность отсчетов Y(1),…,Y(n) образующую кодовое слово длины z. Основание кода сигнала s также может отличаться от основания кода сообщения m.
Последовательность X=(X(1), …, X(n)) имеет NX = mn возможных значений, а для последовательности Y = (Y(1), …, Y(n)) это число равно Ny=sz. Поэтому для полного описания системы XY необходимо перечислить N=NXNy=mnsz возможных реализаций этой системы и указать их вероятности
Из них могут быть получены безусловные и условные характеристики X(t) и Y(t) по формулам, аналогичным (1.3) - (1.8),
например:
и так далее.
Две последовательности бесконечной длины
называются стационарными и стационарно связанными, если для любых n и i
т.е. все характеристики таких последовательностей не зависят от начала отсчета.
Модель сигнала - непрерывная случайная величина
Осуществляя квантование по времени, переходим от непрерывной случайной функции X(t) к системе непрерывных случайных величин X(1), X(2), …, X(n) а от непрерывной случайной функции Y(t) - к системе Y(1), Y(2)…, Y(n) .Полной статистической характеристикой сообщения и сигнала является 2n-мерная совместная плотность вероятности W(x(1), …, x(n), y(1), …, y(n)). Для вычисления других характеристик необходимо использовать обобщение формул (1.3) - (1.8).
Помехи
Помехой называется всякое стороннее воздействие, мешающее правильному приему сигнала, Если принимаемый сигнал Y(t) связан с передаваемым сигналом X(t) соотношением
Y(t)=X(t)+Q(t), (1.9)
то помеха Q(t) называется аддитивной, а в случае
Y(t)=X(t)×Q), (1.10)
мультипликативной.
В качестве помехи имеет смысл рассматривать только такую функцию Q(t), значение которой заранее не известно получателю, так как в противном случае помеха может быть скомпенсирована в месте приема. Поэтому для описания помехи используют те же модели, что и для описания сигнала. Принципиальное отличие сигналов от помехи сводится к тому, что помеха не имеет информативных параметров.
Решение типовых примеров
Пример 1.1.Случайная величина X - число бросания монеты до первого выпадения герба. Найти:
а) ряд распределения случайной величины Х,
б) среднее значение Х,
в) среднее значение двоичного логарифма вероятности Х.
Решение. Возможные значения случайной величины Х равны 1,2,3,.... Для осуществления события x=n необходимо, чтобы, во-первых, n-1 бросания выпадали решки, а в n-м бросании выпал орел, поэтому p(x=n)=(1/2)n по формуле умножения вероятностей независимых событий. Ряд распределения дан в таблице
| xj | … | ||||
| p(xj) | 1/2 | 1/4 | 1/8 | 1/16 | … |
Среднее число бросания вычислим по формуле (1.2), положив j(x,y)=x, m = ¥,
Среднее значение двоичного логарифма вероятности X также вычислим по формуле (1.2), положив j (x)=log2 p(x), т.е.
Пример 1.2. По двоичному каналу связи с помехами (рис.1.3)
Рис.1.3
передаются сообщения x1 и х2 с априорными вероятностями p(x1)=0.4, p(x2)=0.6. Влияние помех описывается переходными вероятностями:
p(y1/x1) = 0.75, p(y2/x1) = 0.25,
p(y1/x2) = 0.5, p(y2/x2) = 0.5.
Найти:
а) безусловные вероятности сигналов на выходе канала;
б) наиболее вероятное значение X, если y = y1;
в) наиболее вероятное значение X, если y = y2.
Решение. Совместные вероятности сообщения X и сигнала Y вычисляем по формуле умножения вероятностей (1.5):
p(x1, y1) = p(x1) × p(y1/x1) = 0,4 × 0,75 = 0,3;
p(x1, y2) = 0,4 × 0,25 = 0,1;
p(x2, y1) = 0,6 × 0,5 = 0,3;
p(x2, y2) = 0,6 × 0,5 = 0,3.
Безусловные вероятности сигналов на выходе канала вычислим по формуле полной вероятности (1.3):
p(y1) = p(x1, y1) + p(x2, y1) = 0,3 + 0,3 = 0,6;
p(y2) = p(x1, y2) + p(x2, y2) = 0,1 + 0,3 = 0,4 = 1- p(y1).
Условные вероятности сообщений на входе находим по формуле Байеса (1.4):
Сравнив p(x1/y2) и p(x2/y2), видим, что если принят сигнал y2 то более вероятно, что было передано сообщение x2. Сигнал y1 мог быть с одинаковой вероятностью вызван сообщением х1 и х2.
Пример 1.3.Сигнал Y(t) на выходе непрерывного канала связи выражается через входной сигнал X(t) соотношением Y(t) = X(t) + Z(t), где Z(t) - нормальный аддитивный стационарный белый шум со спектральной плотностью N0 = 10-18 В2/Гц, ограниченный полосой от 0 до Fв = 10 МГц. Суммарная мощность составляющих в спектре сигнала X(t), лежащих вне указанной полосы, пренебрежимо мала.
Осуществить квантование по времени сигнала Y(t) на интервале то 0 до Т = 10-4 сек. и найти при конкретной реализации входного сигнала
а) вектор условных средних значений,
б) условную корреляционную матрицу,
в) условную плотность вероятности квантованного сигнала на выходе.
Решение. Чтобы осуществить квантование непрерывного по времени сигнала Y(t), необходимо взять его Y(1), Y(2)…, Y(n) отсчеты в моменты времени tk=kDt, k = 1, 2, ... , n, где
Верхняя граничная частота суммы сигнала с шумом равно Fв, поэтому шаг квантования определяется в соответствии с теоремой Котельникова.
Требуемое число отсчетов равно
Каждый отсчет сигнала Y(k) = Y(tk) является суммой двух величин:
Y(k) = X(k) + Z(k),
где X(k) = X(tk) - отсчет сообщения,
Z(k) = Z(tk) – отсчет шума.
Вектор условных средних значений сигнала состоит из следующих элементов:
и определяется только передаваемым сообщением, так как среднее значение белого шума Z(t) равно нулю.
Условная корреляционная матрица сигнала Y(t) при фиксированном X(t) состоит из следующих элементов:
и равна корреляционной матрице отсчетов шума. Элементы этой матрицы есть отсчеты корреляционной функции шума
Шум стационарен, поэтому его корреляционная функция зависит от разности аргументов t = t1- t2 и может быть найдена по теореме Винера - Хинчина
где G(F) - энергетический спектр шума.
По условию задачи, он равномерен в полосе 0 - Fв,
Находим выражение для корреляционной функции
Поскольку:
,
то
Отсюда видно, что
B(t) = 0 при t=Dt, 2Dt, 3Dt, ... ,
т.е. отсчеты Z(1), …, Z(n) взятые с шагом квантования Dt, некоррелированы. Таким образом, не равны нулю в корреляционной матрице отсчетов сигнала будут только элементы, стоящие на главной диагонали
и численно равны дисперсии этих отсчетов.
Условная плотность вероятности квантованного сигнала есть совместная плотность вероятности системы n некоррелированных (а, следовательно, и не зависимых) нормальных случайных величин:
Пример 1.4.Доказать, что для любой положительной случайной величины X (т.е. имеющей только положительные возможные значения) при а >1 справедливо неравенство Иенсена
M[loga X]£ loga M[X].
Доказать, что для любой системы случайных величин Q, L, ..., Z и любой функции j, таких что j (Q, L, ..., Z)>0 при всех возможных значениях системы, справедливо аналогичное неравенство
.
Найти необходимые и достаточные условия, при которых неравенства обращаются в равенства.
Решение. Сначала убедимся, что непрерывная функция y = loga x является строго выпуклой вверх, т.е. ее вторая производная отрицательна при любых х >0. Действительно,
Следовательно, график функции y = loga x лежит ниже касательной, проведенной в любой точке x >0 (рис.1.4):
Рис.1.4
причем знак равенства выполняется только в точке касания x = x0.
Предположим, что X - положительная случайная величина, тогда полученное неравенство справедливо для любого из ее возможных значений и, следовательно, при усреднении обеих частей знак неравенства сохранится:
Выбрав абсциссу точки касания x0 = М[X], получим окончательно
Это неравенство обращается в равенство тогда и только тогда, когда все возможные значения случайной величины X = х0 = М[X], т.е. если величина X не случайна.
Пусть случайная величина X получена в результате функционального преобразования системы случайных величин X = j (Q, L, ..., Z) > 0, тогда в силу доказанного неравенства имеем
.
Это неравенство обращается в равенство тогда и только тогда, когда величина X = j (Q, L, ..., Z) не случайна.
Задачи
1.1.В городе Н в 50 % случаев бывает ясная погода, в 30 % - переменная и в 20 % - дождливая. Сообщения о погоде передаются при помощи кодовых слов "ясно", "переменно", "дождь". Найти среднее количество букв в одном кодовом слове (среднюю длину кодового слова).
1.2.В условиях задачи 1.1 сообщения о погоде передаются по линиям связи при помощи импульсов амплитуды 5, 3 и 1 В соответственно. Определить среднюю мощность в импульсе, если входное сопротивление линии равно 100 Ом.
1.3.В условиях задачи 1.2 на выходе линии связи установлен идеальный ограничитель сверху с порогом 0,5 В. Имеется ли статистическая зависимость сигналов на входе линии и выходе ограничителя?
1.4.Сообщение на выходе линии связи может с одинаковой вероятностью принимать одно из двух значений: х1= -1 В или х2= +1 В. На выходе линии установлен вольтметр. Ошибка измерения, которого распределена нормально с математическим ожиданием, равным нулю, и среднеквадратичным отклонением 0,5 В. Показание вольтметра в некоторый момент времени равно 0,75 В. Найти условные вероятности сообщений х1 и х2.
1.5.Температура в камере может принять с одинаковой вероятностью любое значение в интервале от 0 до 40 градусов. Как выбрать шаг квантования этой величины, чтобы ошибка квантования никогда не превышала 2 градуса ? Построить ряд распределения для квантовых значений температуры.
1.6.В условиях задачи 1.5 найти средний квадрат ошибки квантования.
1.7.Напряжение в сети в момент измерения - случайная величина, имеющая нормальное распределение с параметрами m = 220 В, s= 5 В. На интервале 190 - 240 В осуществить квантование этой величины с шагом Du = 5 В и построить ряд распределения.
1.8.Сколько отсчетов по теореме Котельникова необходимо для передачи сигнала длительностью 10 мин с выхода микрофона, если спектр звуковых частот полностью заключен в полосе 20 - 20000 Гц ?
1.9.Можно ли без искажений восстановить телевизионный видеосигнал, если по линии связи передавались его отсчеты с шагом Dt = 0,2 мкс ?
1.10.Система случайных величин XY имеет совместную плотность вероятности
,
а) вычислить четвертый центральный момент величины Х;
б) являются ли эти случайные величины независимые ?
1.11.Билеты лотереи, среди которых только один выигрышный, занумерованы числами от 0 до 999. Указать среднее количество цифр, необходимых для передачи номера выигравшего билета.
1.12.По каналу связи передаются сообщения х1 и х2 с вероятностями p(х1) = 0,7, p(х2) = 0,3. Вследствие влияния помех сигнал на выходе может принимать одно из трех значений y1, y2, y3 с вероятностями:
p(y1/ х1) = 0,4, p(y2/ х2) = 0,2, p(y3/ х1) = 0,2,
p(y3/ х2) = 0,6, p(y1/ х2) = 0,2, p(y2/ х1) = 0,4.
Найти вероятность ошибочных решений, если выходным сигналам ставить в соответствие следующие решения:
y1 ® х1, y2 ® х1, y3 ®х2.
1.13.Даны математические ожидания двух нормальных случайных величин: mx = 26, my = -12 их корреляционная матрица
Определить плотность вероятности системы XY, считая совместное распределение также нормальным.
1.14. Плотность вероятности системы трех случайных величин равна
Найти совместную плотность вероятности величин X и Y.
1.15. Система случайных величин имеет нормальное распределение
Определить:
а) условную плотность вероятности W(x/y),
б) условное математическое ожидание M[x/y],
в) условную дисперсию D[x/y].
1.16.Сообщение X на входе линии связи есть случайная величина, имеющая нормальное распределение с mx = 0 B, sx= 10 В. Сигнал на выходе линии Y = X + Z, где помеха Z - случайная величина, не зависящая от X и имеющая нормальное распределение с параметрами mz = 0 B, sz=1 В. Указать наиболее вероятное значение переданного сообщения x*, если сигнал на выходе линии равен 7 В ?
1.17.Случайная величина X может принять одно из m значений x1, х2,...,xm. Какими должны быть вероятности p(xj), чтобы величина M[ln(1/p(X))] приняла наибольшее значение ? Чему равно это значение ?
2.Дискретные каналы
2.1. Собственная информация. взаимная Информация
Описание дискретного канала
Дискретным называется канал, сигналы на входе и выходе которого являются последовательностями случайных дискретных величин (символов).
Для полного описания канала на интервале времени, соответствующем передаче одного символа, необходимо задать ансамбли символов на входе X и выходе Y и условные вероятности переходов p(yk/xj).
Будем обозначать
X={x1,x2,…,xj,…,xn; p(x1),p(x2),…,p(xj),…,p(xn)} - ансамбль сообщений на входе,
Y={y1,y2,…,yk,…,yn; p(y1),p(y2),…,p(yk),…,p(yn)} - ансамбль сообщений на выходе.
Собственная информация
Поскольку появление символа сообщения xj на входе дискретного канала есть событие случайное, то говорят, что имеет место неопределенность исхода. В результате опыта неопределенность уменьшается, и при этом получается некоторое количество информации.
Тогда собственная информация символа xj (количество информации, доставляемое самим символом xj или любым другим, однозначно с ним связанным) определяется как
I(xj) = log 1/p(xj) = - log p(xj), (2.1.1)
т.е. информация в каком-либо событии измеряется логарифмом величины, обратной вероятности его появления.
Выбор основания логарифма loga p(xj) определяет единицу количества информации. Если а = 2, то единица информации называется двоичной (бит), при а = е - натуральной (нат), а при а = 10 - десятичной (дит, хартли). Двоичная единица количества информации, например, есть собственная информация символа, обладающего двумя равновозможными состояниями. Переход от одной системы логарифмов к другой равносилен простому изменению единицы измерения информации. Этот переход осуществляется по формуле
logb k = logb a× loga k .
Отсюда 1 нат = log2 e бит= 1,443 бит,
1 дит = log2 10 бит = 3,32 бит.
Условная собственная информация
В общем случае символы X и Y на входе и выходе дискретного канала зависимы. Пусть p(xj / yk) - условная вероятность того, что реализовалось состояние xj ансамбля X при условии, что ансамбль Y принял состояние yk. Тогда, по аналогии с собственной, информация, содержащаяся в символе xj при условии, что сигнал принял значение yk, определяется как
I(xj / yk) = - log p(xj / yk), (2.1.2)
и называется условной собственной информацией.
Взаимная информация
Рассмотрим снова ансамбли X и Y. Пусть ансамбли зависимы. В результате опыта (приема символа yk) апостериорная вероятность появления символа xj изменяется по сравнению с априорной. Тогда количество информации относительно символа сообщения xj, доставляемое символом yk, можно определить как логарифм отношения апостериорной вероятности к априорной
I(xj ; yk) = log (p(xj / yk))/ p(xj). (2.1.3)
Таким образом и определяется взаимная информация.
Основные свойства взаимной информации
1.Взаимная информация может быть отрицательной, положительной или равной нулю, в зависимости от соотношения между априорной и апостериорной вероятностями
-µ < I(xj ; yk) < µ (2.1.4)
2.Взаимная информация не превышает собственную
I(xj ; yk) £ I(xj)
I(xj ; yk) £ I(yk). (2.1.5)
При данной вероятности p(xj) взаимная информация I(xj ; yk) достигает максимума, когда принятый символ yk однозначно определяет переданный символ xj , при этом
и это максимальное значение взаимной информации
I(xj ; yk) = - log p(xj) ,
равно собственной информации, определяемой только априорной вероятностью символа xj .
3.Свойство симметрии
I(xj ; yk) = I( yk ; xj) , (2.1.6)
т.е. информация, содержащаяся в yk относительно xj , равна информации, содержащаяся в xj относительно yk . В силу этого свойства информацию I(xj ; yk) называют взаимной информацией между xj и yk .
4.Свойство аддидивности количества информации
I(xj , zi; yk, ql) = I(xj ; yk) + I( zi ; ql) . (2.1.7)
Если пара X,Y независима от пары Z,Q , то информация, содержащаяся в паре yk, ql относительно пары xj , zi, равна сумме информации, содержащейся в yk относительно xj , и информации, содержащейся в ql относительно zi .
Решение типовых примеров
Пример 2.1.1. Определить собственную информацию, содержащуюся в изображении, при условии, что оно разлагается на 500 строк по 500 элементов в каждой строке. Яркость каждого элемента передается 8 квантованными уровнями. Различия градации яркости равновероятны, а яркости разных элементов статистически независимы.
Решение. Обозначим случайной величиной Х яркость одного элемента изображения. По условию задачи все градации яркости одинаково вероятны, т.е. p(xj) = 1/n, где n = 8 и, следовательно, собственная информация одного элемента по формуле (2.1.2)
I(xj) = log2 n .
Изображение содержит
N = 500×500 = 2.5×105 элементов.
Так как яркости элементов независимы, то по свойству аддитивности информации
I(изображения) = N I(xj) = N log2 n = 2.5×105×3 = 7.5×105 бит.
Пример 2.1.2. На экране индикатора РЛС, представляющего поле с 10 вертикальными и 10 горизонтальными полосами, появляется изображение объекта в виде яркостной отметки. Все положения объекта равновероятны.
Определить количество информации, содержащееся в сообщениях:
а)объект находится в 46-м квадрате экрана;
б)объект находится в 5-й горизонтальной строке экрана.
Решение. а) Пусть х46 – сообщение о том, что объект находится в 46-м квадрате экрана.
Собственная информация в этом сообщении по формуле (2.1.1) I(x46)=-log2 x46. Безусловная вероятность сообщения - объект находится в 46-м квадрате экрана – равна
p(x46) = m / n,
где n – общее число возможных исходов (квадратов поля),
m – число исходов, благоприятствующих событию x46 .
По условию задачи n=100 (квадратов), а m =1. Тогда
p(x46) = 1 / 100 и I(x46)=-log2 1/100= log2 100=6.64 бит.
б) Вероятность события y5 - объект находится в 5-й горизонтальной строке экрана, по аналогии с рассмотренным случаем а), определяется так:
p(y5) = m / n где n=100, m =10 и p(y5) = 10 / 100 =1/10.
Собственная информация
I(y5) =)= -log2 1 / 10 = log2 10 = 3.32 бит.
Пример 2.1.3..Рассматривается ансамбль сообщений, приведенный в таблице
| xi | x0 | x1 | x2 | x3 | x4 | x5 | x6 |
| p(xj) | 1/2 | 1/4 | 1/8 | 1/32 | 1/32 | 1/32 | 1/32 |
| Код |
Сообщение x4 поступает в кодер. Вычислить дополнительную информацию об этом сообщении, доставляемую каждым последующим символом на выходе кодера.
Решение. На вход кодера поступают сообщения x0,x1,…, x6 и кодер порождает соответствующие таблице двоичные символы. Так, сообщению x4 . соответствует кодовое слово 101. Символы на выходе кодера появляются последовательно, т.е. первый символ 1, второй 0 и третий 1. Первый символ кодового слова содержит некоторую информацию относительно того, какое сообщение поступает на вход кодера. Так, первый символ 1 показывает, что на выходе могут быть сообщения x2, x4, x5 или x6 . Второй символ 0 сужает выбор – теперь на входе возможно обно из двух сообщений: x2 или x4 . И, наконец, последний, третий символ 1 однозначно определяет переданное сообщение.
Как известно, взаимная информация есть некоторая (логарифмическая) функция изменения вероятностей. Тогда по формуле (2.1.3) взаимная информация, содержащаяся в первом кодовом символе 1 относительно сообщения x4 ,
I(x4 ; 1) = log (p(x4 / 1))/ p(x4).
Вероятность p(x4 / 1) может быть найдена по формуле Байеса. Условная вероятность гипотезы
В нашем случае гипотезы x0,x1,…, x6 (Hi) , а случайное событие А, имеющее место при некоторой гипотезе, есть появление кодового символа 1 на выходе кодера. Тогда формула Байеса примет такой вид:
где
т.е. условная вероятность p(1/ x4)=0 для гипотез, у которых первый кодовый символ 0, и p(1/ x4)=1 для гипотез, у которых первый кодовый символ 1. В формуле Байеса учитываются, таким образом, те гипотезы, при которых возможно появление 1 на первом месте.
Итак
и взаимная информация, содержащаяся в первом кодовом символе относительно сообщения x4,
Информация, содержащаяся во втором кодовом символе 0 при условии, что первый кодовый символ был 1, есть
Информация, содержащаяся в третьем кодовом символе 1 при условии, что ему предшествовали 10, есть
Так как сообщения xj и кодовые слова однозначно связаны, то
I(x4) = I(x4;1) + I(x4;0/1) + I(x4;1/10).
Действительно, I(x4) = - log2 p(x4) = - log2 32 =5 бит и это равно
I(x4) = I(x4;1) + I(x4;0/1) + I(x4;1/10=
=2.2 + 0.48 + 2.32 =5 бит.
Пример 2.1.4.По дискретному каналу передаются сообщения x1 и x2. Вследствие действия шумов на выходе канала появляются сигналы y1, y2 и y3. Вероятности совместного появления заданы в таблице
| xj | yk | ||
| y1 | y2 | y3 | |
| x1 | 1/4 | 1/16 | 1/8 |
| x2 | 1/8 | 3/16 | 1/4 |
Вычислить взаимные информации I(x2 ; y2), I(x1 ; y3).
Решение. Дискретный канал с шумом удобно изображать в виде графа
Определим взаимную информацию по формуле (2.1.3)
I(x1 ; y3) = log (p(x1 / y3))/ p(x1)
или в силу свойства симметрии
I(x1 ; y3) = I(y3 ; x1 ) = log (p( y3 / x1))/ p(y3).
Условные и безусловные вероятности найдем, воспользовавшись таблицей. По формуле (1.3)
p(x1)= p(x1, y1)+ p(x1, y2)+ p(x1, y3)=
=1/4+1/16+1/8=7/16;
p(x2)= 1/8+3/16+1/4=9/16; p(y1)=1/4+1/8=3/8;
p(y2)=1/16+3/16=1/4; p(y3)=1/8+1/4=3/8.
Найдем условные вероятности
p( y2 / x2) = p(x2 , y2))/ p(x2)=(3/16)/(9/16)=1/3;
p(x1 / y3) = p(x1 ; y3))/ p(y3)=(1/8)/(3/8)=1/3.
Тогда количество взаимной информации по формуле (2.3.1)
I(x2 ; y2) = log2 p( y2 / x2 ))/ p(y2)= log2 (1/3)/(1/4)=
=2 – 1.585 =0.415 бит .
I(x1 ; y3) = log2 p( x1 / y3 ))/ p(x1)= log2 (1/3)/(7/16)=
= log2 16/21= 4 – 4.39 = -0.39 бит .
Мы получили I(x1 ; y3) < 0 , так как p(x1 / y3)< p(x1).
Задачи
2.1.1.На шахматной доске произвольным образом расставлены фигуры. Априори все положения фигур на доске одинаково вероятны. Определить собственную информацию, получаемую от сообщения, что фигура находится в одной из угловых клеток доски.
2.1.2.Сколько информации содержится в сообщении о том, что сумма очков на двух подброшенных игральных костях есть четное число ?
2.1.3.Сколько информации содержится в сообщении о том, что сумма очков на двух подброшенных игральных костях равна 7 ?
2.1.4.Бросаются одновременно две игральные кости. Определить количество информации, содержащееся в сообщении о том, что произведение чисел выпавших очков четно.
2.1.5.В цехе работают 7 мужчин и три женщины. По табельным номерам наудачу отобраны 3 человека. Найти количество информации, содержащееся в сообщении "все отобранные люди - мужчины".
2.1.6.Из шести букв разрезной азбуки составлено слово "машина". Ребенок, не умеющий читать, рассыпал эти буквы и затем собрал в произвольном порядке. Какое количество информации будет содержаться в утверждении, что у него снова получилось слово "машина" ?
2.1.7.Два стрелка, для которых вероятности попадания в мишень равны соответственно 0.6 и 0.7, производят по одному выстрелу. В результате оказалось, что мишень поражена. Какое количество информации содержится в сообщении ?
2.1.8.Урна содержит 5 черных и 10 белых шаров. Случайно, без возвращения, из урны вынимают 3 шара и результат опыта передается по системе связи. Пусть шары выбраны в следующей последовательности: черный, черный, белый.
Какое количество информации надо передать, если:
а) интересоваться только числом шаров ?
б) представляет интерес также и порядок, в котором выбраны шары ?
2.1.9.В некотором городе четверть женщин - блондинки, половина - брюнетки и четверть шатенки. Блондинки всегда приходят на свидание вовремя, брюнетки - кидают монету и в зависимости от результата приходят вовремя или опаздывают, а шатенки всегда опаздывают.
1.Определить взаимную информацию между высказыванием "женщина пришла на свидание вовремя" относительно каждого из следующих предложений:
а) она блондинка;
б) она брюнетка;
в) она шатенка.
2.Сколько информации содержится в высказывании "женщина пришла вовремя на 3 свидание подряд" относительно предложения, что она брюнетка ?
2.1.10.При фототелеграфной передаче изображения кадр состоит из 2,5×106 элементов. Для хорошего воспроизведения необходимы 12 градаций (уровней) яркости. Предполагается, что все уровни яркости встречаются с одинаковой вероятностью. Элементы изображения независимы. Какое количество информации надо передать по каналу связи, если передача продолжается 5 минут ?
2.1.11.По дискретному каналу передаются сообщения x1,x2,,x3. Вследствие действия шумов на выходе канала появляются сигналы y1 и y2. Вероятности совместного появления заданы в таблице
| xj | yk | |
| y1 | y2 | |
| x1 | 0,4 | 0,1 |
| x2 | 0,2 | 0,15 |
| x2 | 0,1 | 0,05 |
Вычислить взаимные информации I(x1 ; y2), I(x3 ; y1), I(x2 ; y2).
2.1.12.По двоичному каналу с шумом передается сообщения x1,x2,,x3 с вероятностями 0.2, 0.3 и 0.5. На выходе канала появляются сигналы y1, y2,y3. Вероятности искажения в канале (условные вероятности переходов):
p(y1 / x1) = 3/4 ; p(y1 / x2) = 1/8 ; p(y1 / x3) = 1/8 ,
p(y2 / x1) = 1/8 ; p(y2 / x2) = 3/4 ; p(y2 / x3) = 1/8 ,
p(y3 / x1) = 1/8 ; p(y3 / x2) = 1/8 ; p(y3 / x3) = 3/4 .
Вычислить взаимные информации I(x1 ; y3) и I(x3 ; y1).
2.1.13.По двоичному каналу с помехами передаются равновероятные и статистически независимые сообщения x1 и x2. В результате действия помех они преобразуются в сигналы y1, y2, y3 . Условные вероятности переходов p(yk / xj) заданы в таблице:
| xj | yk | ||
| y1 | y2 | y3 | |
| x1 | 5/8 | 2/8 | 1/8 |
| x2 | 1/8 | 5/8 | 2/8 |
Вычислить взаимные информации I(x1 ; y3) и I(x2 ; y2).
2.1.14.Рассматривается ансамбль сообщений, приведенный в таблице
| xi | x0 | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| p(xj) | 1/4 | 1/4 | 1/8 | 1/8 | 1/16 | 1/16 | 1/16 | 1/16 |
| Код |
Сообщение x2 поступает в кодер. Вычислить дополнительную информацию об этом сообщении, доставляемую каждым последующим символом на выходе кодера.
2.1.15.Сообщения источника x1, x2, x3, x4 для согласования с каналом кодируются в соответствии с таблицей
| Сообщения xi | x1 | x2 | x3 | x4 |
| p(xj) | 1/2 | 1/4 | 1/8 | 1/8 |
| Код |
Пусть на вход кодера поступает сообщение x3. Вычислить дополнительную информацию об этом сообщении, которую содержит каждый последующий символ на выходе кодера.
2.1.16.Среди студенток некоторого института 25 % всех девушек - блондинки, а 75 % всех блондинок имеют голубые глаза; всего же голубые глаза имееют половина всех девушек. Пусть мы знаем, что некоторая студентка имеет голубые глаза. Сколько дополнительной информации будет содержаться в сообщении о том, что эта девушка – блондинка ?
2.2.Средняя собственная информация (энтропия)
Энтропия
Дискретный источник удобнее характеризовать количеством собственной информации, содержащимся в среднем в одном символе ансамбля X .
Это среднее количество собственной информации
(2.2.1)
и названо энтропией (по аналогии с понятием энтропии в термодинамике).
Основные свойства энтропии
1.Энтропия не отрицательна
H(X) ³ 0. (2.2.2)
Знак равенства имеет место, когда X - не случайна, т.е. p(xj) = 1, а p(xi) = 0 для i ¹ j. При этом неопределенность относительно ансамбля X отсутствует. Таким образом, энтропия есть мера неопределенности случайного ансамбля.
2.Величина энтропии удовлетворяет неравенству
H(X) £ log n. (2.2.3)
Знак равенства имеет место при равномерности символов ансамбля X, т.е. при p(xj) = 1/n .
3.Свойство аддитивности энтропии.
В последовательности n независимых символов энтропия равна сумме энтропий, содержащихся в отдельных символах
H[X1,…,Xn] = H(X1)+…+ H(Xn) . (2.2.4)
Вычисление энтропии по формуле (2.2.1) можно упростить, введя функцию h(p)=-p log p, тогда формула примет вид
(2.2.5)
Условная энтропия
Пусть имеются два статистически зависимых конечных ансамбля символов X и Y. Пары символов xj yk с вероятностями p(xj,yk) можно рассматривать как элементарные символы объединенного ансамбля XY с энтропией
(2.2.6)
Появление символа xj Î X вызывает появление символа yk Î Y с условной вероятностью
При этом условная энтропия ансамбля Y в предположении, что выбран символ xj, будет
(2.2.7)
Здесь каждому xj соответствует свое значение энтропии H(Y/xj), т.е. H(Y/xj) - случайная величина.
Тогда средняя условная энтропия случайной величины Y, вычисленная при условии, что известно значение другой случайной величины X, равна
(2.2.8)
Энтропия объединенного ансамбля H(XY) удовлетворяет следующим соотношениям
а) H(XY)= H(X)+ H(Y/X)= H(Y)+ H(X/Y) , (2.2.9)
если X и Y зависимы;
б) H(XY)= H(X)+ H(Y), (2.2.10)
если X и Y независимы.
Для объединенного ансамбля XY условная энтропия удовлетворяет неравенствам
H(Y/X) £ H(Y),
H(X/Y) £ H(X). (2.2.11)
Избыточность
Считают, что имеется избыточность, если количество информации, содержащейся в сигнале (энтропия сигнала), меньше того количества, которое этот сигнал мог бы содержать по своей физической природе. Пусть сигнал длиной в n символов (отсчетов) содержит количество информации H. Пусть далее наибольшее количество информации, которое в принципе может содержаться в данном сигнале с учетом наложенных на него ограничений (заданное основание кода, заданная средняя мощность сигнала и т.п.), равно Hmax. Тогда количественной мерой избыточности является величина
k = 1 - H/ Hmax . (2.2.12)
Причина появления избыточности - это статистическая связь между символами (отсчетами) сигнала и неэкстремальность распределения вероятностей отдельных символов (отсчетов). Введение избыточности приводит к удлинению сигнала, но зато повышает его информационную устойчивость при воздействии помех.
Решение типовых примеров
Пример 2.2.1.На измерительной станции имеются два прибора. Первый имеет шкалу, содержащую 100 делений, его показания могут меняться через каждые 0.05 с. Шкала второго прибора имеет 10 делений, и его показания могут меняться каждые 0.01 с.
Какова наибольшая средняя информация, поставляемая двумя приборами в 1 с. ?
Решение. 1-й прибор. Энтропия одного значения (отсчета) по формуле (2.2.3)
H1(X) = log2 m1 = log2100.
Число отсчетов в 1 с. n1=1/0.05=20.
2-й прибор. Энтропия одного значения
H2(X) = log2 m2 = log210.
Число отсчетов в 1 с. n2=1/0.01=100.
Энтропия двух приборов в 1 с. по формуле (2.2.4)
HS(X)=n1H1(X)+n2H2(X)=20 log2 100+100 log210=
=20×6.64+100×3.32=464 бит/с.
Пример 2.2.2.Призводится стрельба по двум мишеням, по одной сделано 2 выстрела, по второй – 3. Вероятность попадания при одном выстреле соответственно равны 1/2 и 1/3. Исход стрельбы (число попаданий) по какой мишени является более определенным ?
Решение. Исход стрельбы определяется числом попаданий в мишень, которое подчинено биномиальному закону распределения:
p(X=m)=Cnmpm(1-p)n-m, где Cnm = n!/m!(n-m)!.
Составляем ряд распределения для числа попаданий в первую мишень при n=2 и p=1/2
| m | |||
| p(x=m) | 1/4 | 1/2 | 1/4 |
и во вторую мишень при n=3 и p=1/3
| m | ||||
| p(x=m) | 8/27 | 4/9 | 2.9 | 1/27 |
Мерой неопределенности исхода стрельбы служит энтропия числа попаданий. Энтропия числа попаданий при стрельбе по первой мишени
По второй мишени
т.е. исход стрельбы по второй мишени обладает большей неопределенностью.
Пример 2.2.3.Источник сообщений вырабатывает ансамбль символов
Символы в последовательности статистически независимы. Вычислить энтропию источника и определить избыточность.
Решение. Энтропия источника для случая неравномерных и независимых сообщений определяется формулой (2.2.1)
Избыточность за счет неоптимальности (неравновероятности) распределения сообщений в источнике определяется формулой (2.2.12)
k = 1 - H/ Hmax, где Hmax=log2m по формуле (2.2.3).
Отсюда
k = 1 - H/ Hmax=1-2,27/ log26=1-0,87=0,13.
Пример 2.2.4.Алфавит источника состоит из трех букв x1 , x2 и x3 .
Определить энтропию на 1 букву текста Х(1), Х(2) для следующих случаев:
а)буквы неравновероятны: p(x1)=0,5, p(x2)= p(x3)=0,25, а символы в последовательности на выходе источника статистически зависимы. Условные вероятности переходов p(xj(2)/xi(1)) заданы таблицей
| i - индекс предыдущей буквы | j - индекс последующей буквы | ||
| 0,4 | 0,2 | 0,4 | |
| 0,0 | 0,6 | 0,4 | |
| 0,3 | 0,0 | 0,7 |
б)вероятности букв те же, что и в п. а), но символы независимы;
в)символы в последовательности независимы, а вероятности букв одинаковы.
Вычислить избыточность источника для случаев а) и б).
Решение.а)В случае неравновероятных и зависимых сообщений энтропия текста по формуле (2.2.9)
где
а условная энтропия по формуле (2.2.8)
Энтропия на один символ
б)При неравновероятных, но независимых сообщениях энтропия по
формуле (2.2.1)
Избыточность, обусловленная статистической зависимостью
k1= 1 – H1(X)/ H(X)=1-1,36/1,5=1-0,9=0,1.
в)В случае равновероятных и независимых сообщениях энтропия по формуле (2.2.3)
Hmax(X)=log2m = log23=1,585 бит.
Избыточность, обусловленная неоптимальностью распределения
k2= 1 – H(X)/ Hmax(X)=1-1,5/1,585=1-0,95=0,05.
Полная избыточность (за счет неоптимальности распределения и наличия статистических зависимостей)
k= 1 – H1(X)/ Hmax(X)=1-1,36/1,585=1-0,86=0,14.
Задачи
2.2.1.Алфавит русского языка состоит из 32 букв (если не различать е и ё, ь и ъ), включая промежуток между буквами. Вычислить энтропию однобуквенного текста, считая вероятности появления любой из букв в заданном тексте одинаковыми.
2.2.2.Источник вырабатывает ансамбль сообщений
Символы в последовательности независимы. Вычислить энтропию источника и определить избыточность.
2.2.3.Найти число значений m равномерно распределенной случайной величины Y, при котором ее энтропия будет равна энтропии случайной величины X, заданной в таблице
| xj | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x9 |
| p(xj) | 1/2 | 1/4 | 1/8 | 1/16 | 1/32 | 1/64 | 1/128 | 1/128 |
2.2.4.Призводится стрельба по мишени. Сделано 2 выстрела. Вероятность попадания при одном выстреле 1/2. Найти неопределенность исхода стрельбы (числа попаданий) по мишени.
2.2.5.Определить энтропию случайной величины X, распределенной по биномиальному закону:
а) в общем случае,
б) при p = q = 1/2 и m = 3.
2.2.6.В двух урнах имеется по 15 шаров: в первой урне 5 красных, 7 белых и 3 черных; во второй соответственно 4, 4, 7. Из каждой урны вынимается по одному шару. Сравнить неопределенности исхода опытов для двух урн.
2.2.7.Алфавит источника сообщений состоит из двух букв x1 и x2 с вероятностями 0,6 и 0,4. В последовательности на выходе источника символы статистически зависимы. Условные вероятности переходов p(xj(2)/xi(1)) заданы таблицей
| i - индекс предыдущей буквы | j - индекс последующей буквы | |
| 0,2 | 0,8 | |
| 0,7 | 0,3 |
Определить энтропию на один символ текста X(1)X(2). Вычислить избыточность источника.
2.2.8.Выполнить задачу 2.7, если условные вероятности переходов p(xj(2)/xi(1)) заданы таблицей
| i - индекс предыдущей буквы | j - индекс последующей буквы | |||
| 0,0 | 0,2 | 0,4 | 0,4 | |
| 0,2 | 0,2 | 0,3 | 0,3 | |
| 0,25 | 0,0 | 0,25 | 0,5 | |
| 0,2 | 0,4 | 0,4 | 0,0 |
Безусловные вероятности букв x1 … x4 равны соответственно 0.5; 0.25; 0.125; 0.125.
2.2.9.Символы азбуки Морзе могут появиться в сообщении с вероятностями: для точки - 0.51, для тире - 0.31, для промежутка между буквами - 0.12, между словами - 0.06. Определить среднее количество информации в сообщении из 500 символов данного алфавита, считая, что связь между последовательными символами отсутствуют.
2.2.10.Система радиозонда измеряет давление. Барометр имеет 10 отметок шкалы, и его отсчеты могут изменяться до любого допус