Протоколы Internet
Статистическая теория каналов связи
2.10 Статистическая теория каналов связи
Семенов Ю.А. (ГНЦ ИТЭФ)
Данная статья имеет целью познакомить с терминологией и математическими основами статистической теории передачи данных. Именно на этой математической основе зиждятся приведенные выше теоремы Шеннона и Найквиста. Статья является компиляцией из нескольких источников (Ю.В.Прохоров, Ю.А.Розанов "Теория вероятностей. Основные понятия, предельные теоремы, случайные процессы" Наука, М. 1967; Л.Ф. Куликовский, В.В.Мотов, "Теоретические основы информационных процессов", Высшая школа, 1987; Р. Галлагер "Теория информации и надежная связь" Советское радио, 1974 и др.). Материалы, предлагаемые здесь не могут считаться исчерпывающими и призваны быть поводом для более углубленного изучения по существующим монографиям.
Канал связи предназначен для транспортировки сообщений. Математическая модель канала связи описывается некоторой совокупностью Х1 элементов х1 (X1 = {x11, x12,, …x1j}), называемых сигналами на входе канала, совокупностью Х2 элементов х2 (x2 = {x21, x22,, …x2k}), называемых выходными сигналами, и условными распределениями вероятностей p2=p2(a2
|x1) в пространстве x2 выходных сигналов x2. Если посланный сигнал (сигнал на входе) есть х1, то с вероятностью P2=P2(A2|x1) на выходе канала будет принят сигнал х2 из некоторого множества A2 М Х2 (распределения задают вероятности того или иного искажения посланного сигнала х1). Совокупность всех возможных сообщений обозначим символом x0. Предполагается, что каждое из сообщений x0О X0 может поступать с определенной вероятностью. То есть, в пространстве X0
имеется определенное распределение вероятностей P0=P0(A0 ).
Сообщения х0 не могут быть переданы по каналу связи непосредственно, для их пересылки используются сигналы x1О X1. Кодирование сообщений х0 в сигналы х1 описывается при помощи условного распределения вероятностей P1=P1(A1
|x0). Если поступает сообщение х0, то с вероятностью P1=P1(A1|x0)
будет послан один из сигналов х1, входящих в множество A1 М Х1 (условные распределения P1(A1|x0) учитывают возможные искажения при кодировании сообщений). Аналогичным образом описывается декодирование принимаемых сигналов х2 в сообщения x3. Оно задается условным распределением вероятностей P3=P3(A3|x2) на пространстве Х3 сообщений х3, принимаемых на выходе канала связи.
На вход канала связи поступает случайное сообщение x0 с заданным распределением вероятностей P0=P0(A0). При его поступлении передается сигнал x1, распределение вероятностей которого задается правилом кодирования P1=P1(A1|x0):
P{x2 О A2|x0, x1} = P2(A2|x1)
Принятый сигнал x2 декодируется, в результате чего получается сообщение x3:
P{x3 О A3|x0, x1, x2} = P3(A3| x2)
Последовательность x0 ® x1 ® x 2 ® x3 является марковской. При любых правилах кодирования и декодирования описанного типа имеет место неравенство:
I(x0,x3) Ј I(x1, x2),
где I(x0, x3) – количество информации о
x0 в принятом сообщении
x3, I(x1, x2) – количество информации о x1 в принятом сигнале
x2.
Предположим, что распределение вероятности входного сигнала x1 не может быть произвольным и ограничено определенными требованиями, например, оно должно принадлежать классу W. Величина C = sup I(( x1 , x2) , где верхняя грань берется по всем возможным распределениям P1 О W, называется емкостью канала и характеризует максимальное количество информации, которое может быть передано по данному каналу связи (теорема Шеннона).
Предположим далее, что передача сообщений x0 ® x3 должна удовлетворять определенным требованиям точности, например, совместное распределение вероятностей Px0 x1 передаваемого и принимаемого сообщений x0 и x3 должно принадлежать некоторому классу V. Величина H= inf I( x0
x3),
где нижняя грань берется по всем возможным распределениям Px0 x3 О V,
характеризует минимальное количество информации, которое должно заключать в себе принимаемое сообщение x3 о x0, чтобы было выполнено условие точности передачи. Величина H называется энтропией источника сообщений.
Если возможна передача
x0 ® x1 ® x2 ® x3 с соблюдением требований V и W, то есть существуют соответствующие способы кодирования и декодирования (существуют условные распределения P1, P2 и P3), то H Ј С.
Для выполнения этого неравенства передача является возможной, т.е. возможна передача последовательно поступающих сообщений
Предположим, что совокупность Х0 всех возможных сообщений х0 является дискретной (имеется не более чем счетное число различных сообщений x0, поступающих с соответствующими вероятностями P0(x0), x0 О X0) и условие точности передачи v состоит в том, что принимаемое сообщение x3 должно просто совпадать с переданным сообщением x3 = x0 с вероятностью 1. Тогда
Предположим далее, что имеется лишь конечное число N
различных входных сигналов х1 и нет никаких ограничений на вероятности P{ x1 = x1}, x1 О X1. Кроме того, предположим, что передаваемые сигналы принимаются без искажений, то есть с вероятностью 1 x2= x1. Тогда емкость канала выражается формулой C = log2N, т.е. передаваемое количество информации I(x1, x
2 ) будет максимальным в том случае, когда сигналы x1 О X1 равновероятны.
Если сообщения
поступают независимо друг от друга, то количество информации, которое несет группа сообщений
Пусть H<C, положим также d=(1/2)(C-H). Согласно закону больших чисел, примененному к последовательности независимых и одинаково распределенных случайных величин
с математическим ожиданием
для любого e >0 найдется такое n(e), что при всех n і n(e )
P{-H-d Ј (1/n)logP( x 0n) Ј H+d } і 1-e, где
Полученное неравенство говорит о том, что все группы сообщений х0n можно разбить на два класса. К первому классу
и количество которых Mn не больше чем 2n(H+d ):
Mn Ј 2n(H+d )
Ко второму классу
х0n: 
Каждую группу высоковероятных сообщений х0n можно в принципе передать, закодировав ее соответствующей комбинацией сигналов
передавать некоторый один и тот же сигнал 
, то с вероятностью, не меньшей чем 1-e, на выходе канала связи будет приниматься последовательность 
При выполнении неравенства H < C оказывается возможной передача достаточно длинных сообщений
Количество информации I(x0, x3) для абстрактных случайных величин x0 и x3
со значениями в пространствах Х0 и Х3 может быть записано в виде:
I(x0, x
3) = Mi(x0, x3), где
- информационная плотность. Последовательность пар (x0n, x3n) называется информационно устойчивой, если при n ® Ґ
I(x0, x3) ® Ґ и
(по вероятности)
Рассмотренная выше последовательность (x0n, x3n), x3n= x0n
поступающих сообщений x 0n =(
x1n® x 2n, Hn – минимальное количество информации, необходимое для соблюдения требуемой точности передачи x0n
® x 3n, причем
(при n ® Ґ ),
и существуют информационно устойчивые последовательности пар (x0n, x3n) и (x1n, x2n), для которых одновременно
то при весьма широких предположениях для любого наперед заданного e >0 существует такое n(e), что по всем каналам связи с параметром n і n(e) возможна передача с точностью до e.
2.10.2. Канал связи с изменяющимися состояниями
Как было указано выше, канал характеризуется условными распределениями З2, задающими вероятности тех или иных искажений посылаемого сигнала х1. Несколько изменим схему канала связи, считая, что имеется некоторое множество Z возможных состояний z канала связи, причем если канал находится в некотором состоянии z и на входе возникает сигнал x1, то независимо от других предшествующих обстоятельств канал переходит в другое состояние z1. Этот переход подвержен случайностям и описывается условными распределениями P(C|x1, z) (P(C|x1, z) – вероятность того, что новое состояние z1 будет входить в множество C М Z). При этом уже считается, что выходной сигнал х2 однозначно определяется состоянием канала z1, т.е. существует некоторая функция j = j (z) на пространстве z возможных состояний канала такая, что х2= j (z1). Эта более общая схема позволяет учитывать те изменения, которые в принципе могут возникать в канале по мере его работы.
Рассмотрим стационарный режим работы канала связи. Предположим, что последовательно передаваемые сигналы
…., x 1(-1), x 1(0), x 1(1),…, соответствующие состояниям канала …, z (-1), z (0), z (1),…, и определяемые ими сигналы
…, x 2(-1), x 2(0), x 2(1),…, на выходе образуют стационарные и стационарно связанные случайные последовательности. Величина С=supI(x 1,x 2), где I(x 1,x 2), означает скорость передачи информации о стационарной последовательности {x1(n)} последовательностью {x 2(n)} и верхняя грань берется по всем допустимым распределениям вероятностей входной последовательности {x1(n)}, называется пропускной способностью канала связи.
Предположим, что поступающие на вход канала связи сообщения {x 0(n)}, n =…, -1, 0, 1 ,…, образуют случайную последовательность. Будем считать правило кодирования заданным, если при всех k, m и k1,…, km і k определены условные вероятности
P{x 1(k1) О B1,…, x 1
(km)О Bm|x 0(-Ґ ,k)}
Того, что при поступлении последовательности сообщений
x 0(-Ґ ,k) = …, x 0(k-1), x 0(k)
на соответствующих местах будут переданы сигналы x 1(k1),…, x 1(km), входящие в указанные множества B1, …, Bm. Эти вероятности считаются стационарными в том смысле, что они не меняются при одновременной замене индексов k и k1,…,km на k+l и k1+l,…,km+l при любом целом l. Аналогичными вероятностями p{ x 3(k1) О D1,…, x 3(km) О Dm|x 2(-Ґ ,k)}
задается правило декодирования.
Определим величину H
формулой H = inf I( x 0,x 3), где I(x 0, x 3) – скорость передачи информации о стационарной последовательности {x0(n)}
последовательностью {x3(n)}, n = …, -1, 0, 1,…
(эти последовательности предполагаются стационарно связанными), и нижняя грань берется по всем допустимым распределениям вероятностей, удовлетворяющим требованиям точности передачи {x0(n)} ® { x3(n)}.
Неравенство H Ј C является необходимым условием возможности передачи
{x 0(n)} ® {x 1(n)} ® {x 2(n)} ® {x 3(n)}.
Напомним, что каждое сообщение
x0(n) представляет собой некоторый элемент х0 из совокупности Х0. Можно интерпретировать Х0 как некоторый алфавит, состоящий из символов х0. Предположим, что этот алфавит Х0 является конечным и требование точности передачи состоит в безошибочном воспроизведении передаваемых символов:
P{x 3(k) = x 3(k)} =1 для любого целого k.
Предположим также, что имеется лишь конечное число входных сигналов х1 и состояний канала z. Обозначим состояния канала целыми числами 1, 2, …, N, и пусть p(k, x1,j) – соответствующие вероятности перехода из состояния k в состояние j при входном сигнале x1:
p(k,x1,j) = P{z (x+1) = j|z (n)=k, x 1(n+1)=x1}.
Дополнительно предположим, что любые произведения вида
p(k0,x1(1),k1)p(k1,x1(2),k2)… p(kn-1,x1(n),kn)
являются стохастическими матрицами, задающими эргодические цепи Маркова. Это условие будет выполнено, если, например, каждая из переходных матриц {p(k,x1,j)} имеет положительный коэффициент эргодичности. Тогда при выполнении неравенства H<C и соблюдении условия эргодичности стационарной последовательности {x 0(n)} сообщений на входе передача возможна с точностью до любого e >0, т.е. при соответствующих способах кодирования и декодирования принимаемая последовательность сообщений {x 3(n)} будет обладать тем свойством, что p{x3(k) № x 0(k)} < e для любого целого k.
Пусть x 1 = {x (t), t О T1} и x 2= {x (t), t О T2} – два семейства случайных величин, имеющих совместное гауссово распределение вероятностей, и пусть H1 и H2 – замкнутые линейные оболочки величин x (t), t О T1, и x (t), t О T2, в гильбертовом пространстве L2
(W). Обозначим буквами P1 и P2 операторы проектирования на пространства H1 и H2 и положим P(1) = P1P2P1, P(2) = P2P1P2. Количество информации I(x1,x 2) о семействе величин x1, содержащееся в семействе x2, конечно тогда и только тогда, когда один из операторов P(1) или P(2) представляет собой ядерный оператор, т.е. последовательность l 1, l 2,… его собственных значений (все они неотрицательны) удовлетворяет условию
В случае, когда x 1 и x 2 образованы конечным числом гауссовых величин:
x1={x (1),…, x (m)}, x 2 = {x (m+1),…, x (m+n
)}, причем корреляционная матрица B общей совокупности x (1),…, x (m+n) является невырожденной, количество информации I(x 1, x 2) может быть выражено следующей формулой:
где B1 и B2 – корреляционные матрицы соответствующих совокупностей x 1 и x 2.
Гауссовы распределения обладают следующим экстремальным свойством. Для произвольных распределений вероятностей величин
x 1 = {x (1), …, x (m)}
и x 2 = {x (m+1), …, x (m+n)}
с соответствующими корреляционными матрицами B1, B2 и B количество информации I(x 1, x 2) удовлетворяет неравенству
Пусть x = (x 1,…,x n) и h = (h 1,…,hn) – векторные случайные величины в n-мерном евклидовом пространстве X и r(x,y) – некоторая неотрицательная функция, определяющая условие близости величин x и h, которое выражается следующим соотношением:
Mr(x ,h ) Ј e .
Величину H=He, определенную как He = inf I(x, h), обычно называют e–энтропией случайной величины x (нижняя грань берется по всем случайным величинам h, удовлетворяющим указанному условию e–близости случайной величине x).
Пусть r(x,y) = r(|x-y|) и существует производная r’(0), 0< r’(0)<Ґ. Тогда при e ® 0 имеет место асимптотическая формула, в которой логарифмы берутся по основанию e:
где g() – гамма функция и h(x) – дифференциальная энтропия случайной величины x:
(px(x) – плотность распределения вероятностей, удовлетворяющая весьма широким условиям, которые выполняются, например, если плотность px(x) ограничена и h(x ) > -Ґ ).
Пусть
Тогда
В частности, при a =2, b =1 имеет место асимптотическая формула
Пусть пара случайных процессов (x 1(t), x 2(t)) образует стационарный в узком смысле процесс, x [u,v] – совокупность значений x (t), u Ј t Ј v, и пусть
, содержащееся в отрезке 
2. Среднее количество указанной информации представляет собой линейно растущую функцию от t:
Фигурирующая здесь величина I(x1, x2) называется средней скоростью передачи информации стационарным процессом x2 о стационарном процессе x1 или просто – скоростью передачи информации.
Скорость передачи информации I(x1,x2)
обладает рядом свойств, аналогичных свойствам количества информации. Но она имеет и специфические свойства. Так для всякого сингулярного случайного процесса x 2, т.е. такого процесса, все значения x 2(t) которого являются функциями от совокупности величин
I(x 1, x 2)=0.Для всякого регулярного случайного процесса x 2 равенство I(x1,x2)=0 справедливо лишь тогда, когда случайный процесс x 1 не зависит от процесса x2 (это говорит о том, что в некоторых случаях I(x1,x2) № I(x 2,x 1) ).
При дополнительных условиях типа регулярности скорость передачи информации I(x 1,x 2)
совпадает с пределом
где
, заключенное в 
0< c Ј l 2nf(l ) Ј c < Ґ
Пусть стационарный процесс x = x (t) представляет собой последовательность величин, каждая из которых принимает значения из некоторого алфавита x, состоящего из конечного числа символов x1, x2,…,xn. Предположим, что вероятность появления на фиксированном месте определенного символа xi есть pi, а вероятность появиться за ним символу xj не зависит от предшествующих xi значений и есть pij:
P
{x (t) = xi} = pi, P{x(t+1) = xi xi|x(t) = xi, x(t-1),…, } = pij
Другими словами x = x
(t) - стационарная цепь Маркова с переходными вероятностями {pij} и стационарным распределением {pi}. Тогда скорость передачи информации стационарным процессом x(t) будет
I(x,x) = -
В частности, если x = x(t) – последовательность независимых величин (в случае pij = pj), то
I(x,x) = -
Пусть x1 = x1(t) и x2 = x2(t) – стационарные гауссовы процессы со спектральными плотностями f11(l), f22(l) и взаимной спектральной плотностью f12(l) причем процесс x2 = x2(t) является регулярным. Тогда
I(x1, x2) = -
Рассмотрим следующее условие близости гауссовых стационарных процессов x1(t) и x2(t):
M|x1(t) - x2(t)|2 Јd2
Наименьшая скорость передачи информации
H = infI(x1,x2),
совместимая с указанным условием “d-точности”, выражается следующей формулой:
а параметр q2 определяется из равенства
Эта формула показывает, какого типа спектральная плотность f22(l) должна быть у регулярного стационарного процесса x 2(t), который несет минимальную информацию I
(x1,x 2) » H
о процессе x1(t). В случае дискретного времени, когда f11(l ) і q 2 при всех l , -p Ј l Ј p, нижняя грань H скорости передачи достигается для такого процесса x 2
(t) (со спектральной плотностью f22(l), задаваемой приведенной выше формулой), который связан с процессом x 1(t) формулой
x 2(t) = x 1(t) + z(t), где z(t) – стационарный гауссов шум, не зависящий от процесса x 2(t); в общем случае формула f22(l) задает предельный вид соответствующей спектральной плотности регулярного процесса x 2(t).
В случае, когда спектральная плотность f11(l) приближенно выражается формулой
соответствующая минимальная скорость передачи информации H может быть вычислена по приближенной формуле
2.10.3. Симметричный канал без памяти
Рассмотрим симметричный канал передачи данных без памяти c конечным числом входных сигналов х1, когда передаваемый сигнал х1 с вероятностью 1-p правильно принимается на выходе канала связи, а с вероятностью p искажается, причем все возможные искажения равновероятны: вероятность того, что на выходе будет сигнал х2, равна
c = supI( x1,x2) достигается в случае, когда на вход поступает последовательность независимых и равномерно распределенных сигналов …, x 1(-1), x 1(0), x 1(1),…; эта пропускная способность выражается формулой
Рассмотрим канал связи, на входе которого сигналы образуют стационарный процесс x 1 = x1(t), M[x 1(t)]2 < Ґ.
Пусть при прохождении сигнала x 1 = x 1(t) он подвергается линейному преобразованию Aj со спектральной характеристикой j (l) и, кроме того, на него накладывается аддитивный стационарный гауссов шум z =z (t), так что на выходе канала имеется случайный процесс x 2(t) вида x 2(t) = aj x 1(t) + z (t).
Предположим также, что ограничения на входной процесс состоит в том, что M[x 1(t)]2 Ј D 2 (постоянная D2 ограничивает среднюю энергию входного сигнала). Пропускная способность такого канала может быть вычислена по формуле
(в последнем выражении интегрирование ведется в пределах -p Ј l Ј p для дискретного времени t и в пределах -Ґ <l <Ґ для непрерывного t), где fz z (l) – спектральная плотность гауссова процесса z (t), функция f(l) имеет вид
а параметр q2 определяется из равенства
Нужно сказать, что если функция f(l) представляет собой спектральную плотность регулярного стационарного гауссова процесса x 1(t), то этот процесс, рассматриваемый как входной сигнал, обеспечивает максимальную скорость передачи информации: I(x 1,x 2) = C. Однако в наиболее интересных случаях, когда время t меняется непрерывно, функция f(l) обращается в нуль на тех интервалах частот l, где уровень шума сравнительно высок (отличные от нуля значения f(l) сосредоточены в основном на тех интервалах частот l, где уровень шума сравнительно мал), и поэтому не может служить спектральной плотностью регулярного процесса. Более того, если в качестве входного сигнала выбрать процесс x 1(t) с спектральной плотностью f(l), то этот сигнал будет сингулярным и соответствующая скорость передачи информации I(x 1,x2) будет равна нулю, а не максимально возможному значению C, указанному выше.
Тем не менее, приведенные выражения полезны, так как позволяют приблизительно представить вид спектральной плотности f(l) регулярного входного сигнала x 1(t),
обеспечивающей скорость передачи I(x1, x2), близкую к максимальному значению C.
С практической точки зрения наиболее интересен случай, когда канал связи имеет ограниченную полосу w пропускаемых частот, т.е. когда спектральная характеристика выражается формулой
а проходящий через канал шум имеет равномерный спектр:
В этом случае пропускная способность может быть вычислена по приближенной формуле
При этом входной сигнал x1(t), обеспечивающий скорость передачи информации I(x1, x2), близкую к максимальной, является гауссовым стационарным процессом со спектральной плотностью f(l) вида
так что параметры D2 и s2 имеют следующий физический смысл:
