|
Посвящается Дню Радио, и в том числе - почетным и
непочетным радистам. 7 мая стал праздником работников
всех отраслей связи в 1945 году, в ознаменование 50-летия
со Дня Радио. В этот день, 25 апреля по старому стилю,
в 1895 году русский ученый Александр Степанович Попов
на заседании физического отделения Русского физико-химического
общества сделал доклад - Об отношении металлических
порошков к электрическим колебаниям - и продемонстрировал
свое изобретение. Он доказал, что электромагнитные
радиоволны могут быть использованы для передачи информации
на коротких расстояниях
Глава 6. Информация при наличии помех. Шенноновское
количество информации В настоящей главе рассматривается
введенное Шенноном количество информации связи двух
случайных величин или двух групп случайных величин.
Это понятие является центральным в теории информации,
самостоятельное развитие которой начато в работах
Шеннона (1948г.). Оно определяется как разность априорной
и апостериорной (условной) энтропией. Явное вычисление
количества информации в сложных случаях, когда в качестве
рассматриваемых случайных величин берутся случайные
процессы, является, вообще говоря, непростой задачей.
В двух последних параграфах главы эта задача решается
для частных случаев: вычисляется удельное количество
информации в случае стационарных гауcсовых и марковских
процессов. При этом используются методы и результаты
гл. 5
6.1. Потеря информации при вырожденных преобразованиях
и при простых помехах Пусть имеется случайная
величина x с конечным числом m состояний (числом реализаций)
и соответствующие ей вероятности P(x).
Рассмотрим некоторое преобразование h
= f(х) этой случайной величины. Функция f, естественно,
определена для всех возможных значений случайной величины.
Если преобразование h является
невырожденным, т.е. существует обратная функция f-1(h)
= x и может быть установлено взаимно однозначное
соответствие между x и h, то энтропия
при преобразовании не меняется:
Hx = Hh.
В самом деле, вследствие взаимно однозначного соответствия
между значениями x и значениями h
выражение типа (1.2.3.) для энтропии
Hx и Hh
будут отличаться лишь порядком следования членов,
нумерации этих членов.
Указанные значения можно нумеровать также числами
1, …, m.
Вследствие этого мы можем, как это делали ранее, заменить
множества значений случайной величины x на множество
1, …, m.
Сложнее обстоит дело, если преобразование h
= f(х) является вырожденным.
Тогда фиксированному значению h
соответствует подмножество Е(h)
элементов x, число W(h)
элементов которого больше единицы.
Зная h, мы не в состоянии сказать,
какое значение x из Е(h) породило
данное значение h.
Чтобы ответить на этот вопрос, требуется помимо h
знать номер x исходного элемента
x в множестве Е(h).
Пара (h,x)
уже в состоянии заменить х.
Между возможными значениями этой пары и множеством
возможных значений х можно осуществить взаимно однозначное
соответствие и, следовательно,
Hx = Hhx.
Случайная величина x является
дополнительной по отношению к h;
Она дополняет h до х.
Пусть, например, на натуральных числах задана функция
h = [x/10], где скобки обозначают
целую часть.
Тогда число h представляет собой
номер десятка, в котором находится натуральное число
х.
Дополнительный величиной x в данном
случае является номер числа в десятке.
Пара (h,x)
есть не что иное, как представление числа х в десятичной
системе и, разумеется, заменяет х.
Применяя формулы из параграфа 1.3. [типа (1.3.4.)],
имеем
Hx = Hh
+ HxЅh.
Отсюда получаем
Hx і Hh (6.1.1)
Так, как HxЅh і
0.
Рассмотрим, когда имеет знак равенства в (6.1.1.).
Поскольку
HxЅh = еP(h)Hx(Ѕh),
То HxЅh = 0 тогда
и только тогда, когда условная энтропия Hx(Ѕh),
исчезает для всех значений h,
имеющих ненулевую вероятность.
Но энтропия
Hx(Ѕh)
= - еxP(xЅh)
ln P(xЅh)
Обращается в нуль, лишь если вероятности P(xЅh)
сосредоточены на одном единственном элементе из Е(h).
Выбирая этот элемент, мы можем осуществить взаимно
однозначное соответствие между значениями h,
имеющими ненулевую вероятность, и значениями (h,x)
= х, имеющими также ненулевую вероятность.
Следовательно, равенство Hx - Hh
= 0, т.е. HxЅh = 0,
означает, что данное преобразование может быть сделано
невырожденным в результате удаления элементов, имеющих
нулевую вероятность, и что оно эквивалентно, невырожденному
преобразованию.
Если же преобразование существенно вырожденное (т.е.
обьединяет хотя бы два каких-то элемента с ненулевыми
вероятностями в один), тогда имеет место строгое неравенство
Hx > Hh(6.1.2)
Итак, мы доказали следующее:
Теорема 6.1. Существенно вырожденное преобразование
случайных чисел х ® h
уменьшает (разрушает) информацию Н, которая может
содержаться в случайной величине.
2. Перейдем теперь к рассмотрению помех Передача
сигналов в канале связи обычно сопровождается помехами
или искажениями. Если х - сигнал на одном конце канала,
то сигнал y на другом (приемном) конце, вообще говоря,
отличается от х вследствие случайных искажений. Если
х обозначает запись, сделанную в запоминающем устройстве
в некоторый момент времени, то через определенное
время запись может исказиться и вместо записи х в
запоминающем устройстве будет содержаться другая запись
y. Такие случайные искажения, описываются вероятностями
перехода P(yЅx). Если через Р(х)
обозначить вероятности первоначального сообщения или
записи, то искаженное сообщение или запись будет,
очевидно, иметь вероятности
P(y) = еxP(x)P(yЅx).
Совместное распределение вероятностей будет
P(x,y) = P(x)P(yЅx).(6.1.3)
В отличие от рассмотренного раньше преобразования
h = f(х) теперь преобразование
х в y, связанное с помехами, является рандомизированным,
т.е. носит случайный характер (y случайно, даже если
х фиксировано).
Покажем, что иногда, несмотря на это кардинальное
отличие, между вырожденным преобразованием и между
случайными искажениями имеется много общего.
Рассмотрим специальный случай простых помех.
Будем называть помехи простыми, если они перемешивают
значения х лишь внутри некоторых классов.
Точнее говоря, пусть область значений х можно разбить
на непересекающиеся подмножества E1, E2,
..., а область значений y - на подмножества
G1, G2, ..., обладающие следующими
свойствами:
а) из области Ek можно попасть лишь в область
Gk:
P (y О Gi Ѕ
x О Ek) = 0, если l
? k; (6.1.4)
б) из всех точек области Ek происходит
переход в y О Gk с
одинаковыми вероятностями
P (y Ѕ x О
Ek) = P (y Ѕk).
(6.1.5)
Легко видеть, что из а) следует
HlЅk = 0 (6.1.6)
или, что эквивалентно,
Hk = Hkl(6.1.7)
(k - номер области Еk, l - номер области
Gl).
Из б) же вытекает
HyЅx = HyЅk
(6.1.8)
Теорема 6.2. Простые помехи с информационной точки
зрения эквивалентны нерандомизированному преобразованию
k = k(x) (где k(x) - номер той области Еk,
которой принадлежит х), т.е. HxЅy
= HxЅk
Для доказательства следует рассмотреть апостериорное
распределение вероятностей P (xЅy).
Подставляя (6.1.5.) в формулу обратной вероятности
(формулу Байеса), приводя ее к виду
P (xЅy) = P(x)P(yЅx)/(еx'
P(x')P(yЅx')) = P(x)P(yЅl)/(еx'
О El P(x')P(yЅl)),
где y О Gl
(l = k) и сокращая на общий множитель Р(yЅl),
получаем
P (xЅy) = P(x)/P(El),
если х О El P
(xЅy) = 0, если Х П
El .
Это выражение зависит от номера l множества Gl,
которому принадлежит y, но не зависит от конкретного
значения y внутри Gl, т.е.
P (xЅy) = p (xЅl)
(y О Gl).
(6.1.9)
Если выполняется подобное равенство, то говорят, что
переменная l является достаточной переменной или достаточной
статистикой, заменяющей y.
Мы получили, следовательно, что номер l множества
служит в данном случае достаточной статистикой.
Из равенства (6.1.9.) вытекает, что Hx(Ѕy)
= Hx(Ѕl) и (после
усреднения этого равенства) что
HxЅy = HxЅl
(6.1.10)
Равенство (6.1.9.), (6.1.10.) означают, что
наблюдение переменной y эквивалентно наблюдению переменной
l=k.
Доказательство закончено.
Из определения простых помех и из теоремы 6.2.
видно, что, понятие простых помех является обратимым:
помехи, соответствующие обратному переходу с вероятностями
P(xЅy), являются простыми, если
простыми являются помехи прямого перехода с вероятностями
P(yЅx).
В самом деле, подставляя (6.1.4.) в (6.1.3.),
легко убедится, что отличны от нуля лишь те вероятности
P(x,y), для которых х и y попадают в области
Еk, Gk с одинаковым номером
k.
Вероятности P(yЅx) равна нулю,
если номера k и l областей Еk '
х, Gl ' y не совпадают.
Следовательно, свойство (6.1.4.) обратимо.
В дополнению к (6.1.6.), (6.1.7.) выполняются
соотношения
HkЅl = 0, Hl
= Hkl = Hk. (6.1.11)
Далее равенство (6.1.9.), очевидно, является
обращением равенства (6.1.5.).
Тем самым указанная обратимость доказана: кроме вырожденного
преобразования k = k(x) можно рассматривать также
нерандомизированное вырожденное преобразование l =
l(y), где l - номер области Gi, содержащую
точку y.
Из теоремы 6.2. следует, что помехи разрушают
информацию, поскольку такое разрушение имеет место
при вырожденном преобразовании l = l (x) по теореме
6.1.
3. Чтобы безошибочно передавать информацию при
вырожденном преобразовании или при простых помехах,
нужно связывать информацию не с переменной х, которая
искажается при преобразовании, а с переменной h
= k, которая остается неизменной, так как l = k.
Количество передаваемой информации, следовательно,
будет равно
I = Hk. (6.1.12)
Преобразуем это соотношение к другому виду, используя
тождество
Hk = Hxk - HxЅk
= Hx + HkЅx
- HxЅk. (6.1.13)
Вытекающее из определения условных энтропий (параграф
1.3.).
При фиксированном х номер k(x) области Еk
' х является полностью определенным,
поэтому
HkЅx = 0. (6.1.14)
И из (6.1.12.), (6.1.13.) получаем
I = Hx - HxЅk.
Согласно (6.1.10.) это соотношение можно записать
I = Hx - HxЅy.
(6.1.15)
Далее, по аналогии с (6.1.14.) имеем HlЅy
= 0 или HkЅy = 0 (что
то же самое, поскольку l = k с вероятностью 1).
Следовательно
Hk = Hk - HxЅk.
(6.1.16)
Учитывая (6.1.12), (6.1.11), (6.1.16), (6.1.15),
будем иметь
I = Hk - HkЅl
= Hk - HkЅy
= Hx - HxЅy.
(6.1.17)
Приведенные результаты относятся к случаю простых
помех однако в менее явной форме (в асимптотическом
смысле) их можно перенести и на случай произвольных
помех, как это видно из последующего (параграф 7.6.).
Там вместо точных соотношений (6.1.17) выведены
приближенные соотношения (7.6.19.).
Для этого нужно рассматривать не отдельные случайные
величины x и y, а последовательности х1,
..., хn и y1, ...,
yn этих величин при n ® Ґ.
Подобно тому как случай произвольных вероятностей
асимптотически сводится к случаю равновероятных возможностей
(см. параграф 1.4., 1.5.), так и случай произвольных
помех асимптотически (при n ® Ґ)
сводится к случаю простых помех.
Поэтому, если информацию связывать с соответствующими
(приближенными) достаточными статистиками k(x) = 1,
..., M (для этого ее должно быть не больше, чем Hk
- HkЅl : ln M Ј
Hk - HkЅl),
то в пределе n ® Ґ можно избежать
ошибок, вызванных искажениями. Этот факт связан с
известной теоремой Шеннона и является одной из возможных
ее интерпретаций (см. гл. 7)
|