Previous: 2.9.1 Используемые стандарты    UP: 2.6 Методы сжатия информации
Down: 3 Каналы передачи данных
    Next: 3 Каналы передачи данных

Данная статья имеет целью познакомить с терминологией и математическими основами статистической теории передачи данных. Именно на этой математической основе зиждятся приведенные выше теоремы Шеннона и Найквиста. Статья является компиляцией из нескольких источников (Ю.В.Прохоров, Ю.А.Розанов "Теория вероятностей. Основные понятия, предельные теоремы, случайные процессы" Наука, М. 1967; Л.Ф. Куликовский, В.В.Мотов, "Теоретические основы информационных процессов", Высшая школа, 1987; Р. Галлагер "Теория информации и надежная связь" Советское радио, 1974 и др.). Материалы, предлагаемые здесь не могут считаться исчерпывающими и призваны быть поводом для более углубленного изучения по существующим монографиям.

Канал связи предназначен для транспортировки сообщений. Математическая модель канала связи описывается некоторой совокупностью Х₁ элементов х₁ (X₁ = {x₁₁, x₁₂,, …x_1j}), называемых сигналами на входе канала, совокупностью Х₂ элементов х₂ (x₂ = {x₂₁, x₂₂,, …x_2k}), называемых выходными сигналами, и условными распределениями вероятностей p₂=p₂(a₂ |x₁) в пространстве x₂ выходных сигналов x₂. Если посланный сигнал (сигнал на входе) есть х₁, то с вероятностью P₂=P₂(A₂|x₁) на выходе канала будет принят сигнал х₂ из некоторого множества A₂ М Х₂ (распределения задают вероятности того или иного искажения посланного сигнала х₁). Совокупность всех возможных сообщений обозначим символом x₀. Предполагается, что каждое из сообщений x₀О X₀ может поступать с определенной вероятностью. То есть, в пространстве X₀ имеется определенное распределение вероятностей P₀=P₀(A₀ ).

Сообщения х₀ не могут быть переданы по каналу связи непосредственно, для их пересылки используются сигналы x₁О X₁. Кодирование сообщений х₀ в сигналы х₁ описывается при помощи условного распределения вероятностей P₁=P₁(A₁ |x₀). Если поступает сообщение х₀, то с вероятностью P₁=P₁(A₁|x₀) будет послан один из сигналов х₁, входящих в множество A₁ М Х₁ (условные распределения P₁(A₁|x₀) учитывают возможные искажения при кодировании сообщений). Аналогичным образом описывается декодирование принимаемых сигналов х₂ в сообщения x₃. Оно задается условным распределением вероятностей P₃=P₃(A₃|x₂) на пространстве Х₃ сообщений х₃, принимаемых на выходе канала связи.

На вход канала связи поступает случайное сообщение x₀ с заданным распределением вероятностей P₀=P₀(A₀). При его поступлении передается сигнал x₁, распределение вероятностей которого задается правилом кодирования P₁=P₁(A₁|x₀):

P{x₂ О A₂|x₀, x₁} = P₂(A₂|x₁)

Принятый сигнал x₂ декодируется, в результате чего получается сообщение x₃:

P{x₃ О A₃|x₀, x₁, x₂} = P₃(A₃| x₂)

Последовательность x₀ ® x₁ ® x ₂ ® x₃ является марковской. При любых правилах кодирования и декодирования описанного типа имеет место неравенство:

I(x_0,x₃) Ј I(x_1, x₂),

где I(x_0, x₃) – количество информации о x₀ в принятом сообщении x₃, I(x_1, x₂) – количество информации о x₁ в принятом сигнале x₂.

Предположим, что распределение вероятности входного сигнала x₁ не может быть произвольным и ограничено определенными требованиями, например, оно должно принадлежать классу W. Величина C = sup I(( x₁ , x₂) , где верхняя грань берется по всем возможным распределениям P1 О W, называется емкостью канала и характеризует максимальное количество информации, которое может быть передано по данному каналу связи (теорема Шеннона).

Предположим далее, что передача сообщений x₀ ® x₃ должна удовлетворять определенным требованиям точности, например, совместное распределение вероятностей P_{x0 x1} передаваемого и принимаемого сообщений x₀ и x₃ должно принадлежать некоторому классу V. Величина H= inf I( x₀ x₃), где нижняя грань берется по всем возможным распределениям P_x0 x3 О V, характеризует минимальное количество информации, которое должно заключать в себе принимаемое сообщение x₃ о x₀, чтобы было выполнено условие точности передачи. Величина H называется энтропией источника сообщений.

Если возможна передача x₀ ® x₁ ® x₂ ® x₃ с соблюдением требований V и W, то есть существуют соответствующие способы кодирования и декодирования (существуют условные распределения P₁, P₂ и P₃), то H Ј С.

Для выполнения этого неравенства передача является возможной, т.е. возможна передача последовательно поступающих сообщений

Предположим, что совокупность Х₀ всех возможных сообщений х₀ является дискретной (имеется не более чем счетное число различных сообщений x₀, поступающих с соответствующими вероятностями P₀(x₀), x₀ О X₀) и условие точности передачи v состоит в том, что принимаемое сообщение x₃ должно просто совпадать с переданным сообщением x₃ = x₀ с вероятностью 1. Тогда

Предположим далее, что имеется лишь конечное число N различных входных сигналов х₁ и нет никаких ограничений на вероятности P{ x₁ = x₁}, x₁   О  X₁. Кроме того, предположим, что передаваемые сигналы принимаются без искажений, то есть с вероятностью 1 x₂= x₁. Тогда емкость канала выражается формулой C = log₂N, т.е. передаваемое количество информации I(x₁, x ₂ ) будет максимальным в том случае, когда сигналы x₁ О X₁ равновероятны.

Если сообщения поступают независимо друг от друга, то количество информации, которое несет группа сообщений есть

группа сообщений, поступающая на кодирование с вероятностью

Пусть 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 можно разбить на два класса. К первому классу относятся высоковероятные сообщения х_0n, для которых P(x_0n) і 2^{-n(H+d )} и количество которых M_n не больше чем 2^{n(H+d )}:

Ко второму классу относятся все остальные маловероятные сообщения х_0n:
.

Каждую группу высоковероятных сообщений х_0n можно в принципе передать, закодировав ее соответствующей комбинацией сигналов . Число всевозможных комбинаций такого вида есть N_n=2^nC, и видно, что M_n<N_n. Имеется N_n различных сигналов x_1n, с помощью которых можно закодировать и передать безошибочно все M_n высоковероятных сообщений x_0n Если в дополнение к этому при поступлении любого маловероятного сообщения x_0n передавать некоторый один и тот же сигнал (отличный от сигналов, при помощи которых передаются высоковероятные сообщения x_0n , то с вероятностью, не меньшей чем 1-e, на выходе канала связи будет приниматься последовательность :

.

При выполнении неравенства H < C оказывается возможной передача достаточно длинных сообщений с той оговоркой, что с вероятностью e (e - наперед заданное сколь угодно малое положительное число) может быть допущена ошибка. Имеется целое семейство каналов связи и источников сообщений, зависящих от параметра n.

Количество информации I(x₀, x₃) для абстрактных случайных величин x₀ и x₃ со значениями в пространствах Х₀ и Х₃ может быть записано в виде:

I(x₀, x ₃) = Mi(x₀, x₃), где

- информационная плотность. Последовательность пар (x_0n, x_3n) называется информационно устойчивой, если при n ® Ґ

I(x₀, x₃) ® Ґ и

(по вероятности)

Рассмотренная выше последовательность (x_0n, x_3n), x_3n= x_0n поступающих сообщений x _0n =( ) обладает свойством информационной устойчивости, что в конечном счете и определило возможность передачи сообщений x _0n с точностью до e. Этот факт допускает широкое обобщение. Например, если С_n – пропускная способность канала
x_1n® x _2n, H_n – минимальное количество информации, необходимое для соблюдения требуемой точности передачи x_0n ® x _3n, причем

(при n ® Ґ ),

и существуют информационно устойчивые последовательности пар (x_0n, x_3n) и (x_1n, x₂n), для которых одновременно

то при весьма широких предположениях для любого наперед заданного e >0 существует такое n(e), что по всем каналам связи с параметром n і n(e) возможна передача с точностью до e.

Как было указано выше, канал характеризуется условными распределениями З₂, задающими вероятности тех или иных искажений посылаемого сигнала х₁. Несколько изменим схему канала связи, считая, что имеется некоторое множество Z возможных состояний z канала связи, причем если канал находится в некотором состоянии z и на входе возникает сигнал x₁, то независимо от других предшествующих обстоятельств канал переходит в другое состояние z₁. Этот переход подвержен случайностям и описывается условными распределениями P(C|x₁, z) (P(C|x₁, z) – вероятность того, что новое состояние z₁ будет входить в множество C М Z). При этом уже считается, что выходной сигнал х₂ однозначно определяется состоянием канала z₁, т.е. существует некоторая функция j = j (z) на пространстве z возможных состояний канала такая, что х₂= j (z₁). Эта более общая схема позволяет учитывать те изменения, которые в принципе могут возникать в канале по мере его работы.

Рассмотрим стационарный режим работы канала связи. Предположим, что последовательно передаваемые сигналы
…., x ₁(-1), x ₁(0), x ₁(1),…, соответствующие состояниям канала …, z (-1), z (0), z (1),…, и определяемые ими сигналы
…, x ₂(-1), x ₂(0), x ₂(1),…, на выходе образуют стационарные и стационарно связанные случайные последовательности. Величина С=supI(x ₁,x ₂), где I(x ₁,x ₂), означает скорость передачи информации о стационарной последовательности {x₁(n)} последовательностью {x ₂(n)} и верхняя грань берется по всем допустимым распределениям вероятностей входной последовательности {x₁(n)}, называется пропускной способностью канала связи.

Предположим, что поступающие на вход канала связи сообщения {x ₀(n)}, n =…, -1, 0, 1 ,…, образуют случайную последовательность. Будем считать правило кодирования заданным, если при всех k, m и k₁,…, k_m і k определены условные вероятности

P{x ₁(k₁) О B₁,…, x ₁ (k_m)О B_m|x ₀(-Ґ ,k)}

Того, что при поступлении последовательности сообщений

x ₀(-Ґ ,k) = …, x ₀(k-1), x ₀(k)

на соответствующих местах будут переданы сигналы x ₁(k₁),…, x ₁(k_m), входящие в указанные множества B₁, …, B_m. Эти вероятности считаются стационарными в том смысле, что они не меняются при одновременной замене индексов k и k₁,…,k_m на k+l и k₁+l,…,k_m+l при любом целом l. Аналогичными вероятностями p{ x ₃(k₁) О D₁,…, x ₃(k_m) О D_m|x ₂(-Ґ ,k)} задается правило декодирования.

Определим величину H формулой H = inf I( x ₀,x ₃), где I(x ₀, x ₃) – скорость передачи информации о стационарной последовательности {x₀(n)} последовательностью {x₃(n)}, n = …, -1, 0, 1,… (эти последовательности предполагаются стационарно связанными), и нижняя грань берется по всем допустимым распределениям вероятностей, удовлетворяющим требованиям точности передачи {x₀(n)} ® { x₃(n)}.

Неравенство H Ј C является необходимым условием возможности передачи

{x ₀(n)} ® {x ₁(n)} ® {x ₂(n)} ® {x ₃(n)}.

Напомним, что каждое сообщение x₀(n) представляет собой некоторый элемент х₀ из совокупности Х₀. Можно интерпретировать Х₀ как некоторый алфавит, состоящий из символов х₀. Предположим, что этот алфавит Х₀ является конечным и требование точности передачи состоит в безошибочном воспроизведении передаваемых символов:

P{x ₃(k) = x ₃(k)} =1 для любого целого k.

Предположим также, что имеется лишь конечное число входных сигналов х₁ и состояний канала z. Обозначим состояния канала целыми числами 1, 2, …, N, и пусть p(k, x₁,j) – соответствующие вероятности перехода из состояния k в состояние j при входном сигнале x₁:

p(k,x₁,j) = P{z (x+1) = j|z (n)=k, x ₁(n+1)=x₁}.

Дополнительно предположим, что любые произведения вида

p(k₀,x₁(1),k₁)p(k₁,x₁(2),k₂)… p(k_n-1,x₁(n),k_n)

являются стохастическими матрицами, задающими эргодические цепи Маркова. Это условие будет выполнено, если, например, каждая из переходных матриц {p(k,x₁,j)} имеет положительный коэффициент эргодичности. Тогда при выполнении неравенства H<C и соблюдении условия эргодичности стационарной последовательности {x ₀(n)} сообщений на входе передача возможна с точностью до любого e >0, т.е. при соответствующих способах кодирования и декодирования принимаемая последовательность сообщений {x ₃(n)} будет обладать тем свойством, что p{x₃(k) № x ₀(k)} < e для любого целого k.

Пусть x ₁ = {x (t), t О T₁} и x ₂= {x (t), t О T₂} – два семейства случайных величин, имеющих совместное гауссово распределение вероятностей, и пусть H₁ и H₂ – замкнутые линейные оболочки величин x (t), t О T₁, и x (t), t О T₂, в гильбертовом пространстве L² (W). Обозначим буквами P₁ и P₂ операторы проектирования на пространства H₁ и H₂ и положим P⁽¹⁾ = P₁P₂P₁, P⁽²⁾ = P₂P₁P₂. Количество информации I(x₁,x ₂) о семействе величин x₁, содержащееся в семействе x₂, конечно тогда и только тогда, когда один из операторов P⁽¹⁾ или P⁽²⁾ представляет собой ядерный оператор, т.е. последовательность l ₁, l ₂,… его собственных значений (все они неотрицательны) удовлетворяет условию . При этом

.

В случае, когда x ₁ и x ₂ образованы конечным числом гауссовых величин:

x₁={x (1),…, x (m)}, x ₂ = {x (m+1),…, x (m+n)}, причем корреляционная матрица B общей совокупности x (1),…, x (m+n) является невырожденной, количество информации I(x ₁, x ₂) может быть выражено следующей формулой:

,

где B₁ и B₂ – корреляционные матрицы соответствующих совокупностей x ₁ и x ₂.

Гауссовы распределения обладают следующим экстремальным свойством. Для произвольных распределений вероятностей величин

x ₁ = {x (1), …, x (m)} и x ₂ = {x (m+1), …, x (m+n)}

с соответствующими корреляционными матрицами B₁, B₂ и B количество информации I(x ₁, x ₂) удовлетворяет неравенству

Пусть x = (x ₁,…,x _n) и h = (h ₁,…,h_n) – векторные случайные величины в n-мерном евклидовом пространстве X и r(x,y) – некоторая неотрицательная функция, определяющая условие близости величин x и h, которое выражается следующим соотношением:

Mr(x ,h ) Ј e .

Величину H=H_e, определенную как H_e = 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:

(p_x(x) – плотность распределения вероятностей, удовлетворяющая весьма широким условиям, которые выполняются, например, если плотность p_x(x) ограничена и h(x ) > -Ґ ).
Пусть (a, b > 0)

Тогда

В частности, при a =2, b =1 имеет место асимптотическая формула

Пусть пара случайных процессов (x ₁(t), x ₂(t)) образует стационарный в узком смысле процесс, x ^[u,v] – совокупность значений x (t), u Ј t Ј v, и пусть
- условное количество информации о процессе x₁=, содержащееся в отрезке процесса x₂. Среднее количество указанной информации представляет собой линейно растущую функцию от t:

Фигурирующая здесь величина I(x₁, x₂) называется средней скоростью передачи информации стационарным процессом x₂ о стационарном процессе x₁ или просто – скоростью передачи информации.

Скорость передачи информации I(x₁,x₂) обладает рядом свойств, аналогичных свойствам количества информации. Но она имеет и специфические свойства. Так для всякого сингулярного случайного процесса x ₂, т.е. такого процесса, все значения x ₂(t) которого являются функциями от совокупности величин (t₀ может быть выбрано любым), имеет место равенство I(x ₁, x ₂)=0.

Для всякого регулярного случайного процесса x ₂ равенство I(x₁,x₂)=0 справедливо лишь тогда, когда случайный процесс x ₁ не зависит от процесса x₂ (это говорит о том, что в некоторых случаях I(x₁,x₂) № I(x ₂,x ₁) ).

При дополнительных условиях типа регулярности скорость передачи информации I(x ₁,x ₂) совпадает с пределом

,

где - количество информации об отрезке процесса , заключенное в . Так будет, например тогда, когда время меняется дискретно, а отдельные величины x₁(t) и x₂(t) могут принимать лишь конечное число различных значений или когда распределение вероятностей процессов x₁ и x₂ является гауссовым. В случае непрерывного времени t так будет для гауссовых процессов, когда спектральная плотность f(l) процесса x₂(t) удовлетворяет условию

0< c Ј l ²ⁿf(l ) Ј c < Ґ

Пусть стационарный процесс x = x (t) представляет собой последовательность величин, каждая из которых принимает значения из некоторого алфавита x, состоящего из конечного числа символов x₁, x₂,…,x_n. Предположим, что вероятность появления на фиксированном месте определенного символа x_i есть p_i, а вероятность появиться за ним символу x_j не зависит от предшествующих x_i значений и есть p_ij:

P{x (t) = x_i} = p_i, P{x(t+1) = x_i x_i|x(t) = x_i, x(t-1),…, } = p_ij

Другими словами x = x (t) - стационарная цепь Маркова с переходными вероятностями {p_ij} и стационарным распределением {p_i}. Тогда скорость передачи информации стационарным процессом x(t) будет

I(x,x) = -

В частности, если x = x(t) – последовательность независимых величин (в случае p_ij = p_j), то

I(x,x) = -

Пусть x₁ = x₁(t) и x₂ = x₂(t) – стационарные гауссовы процессы со спектральными плотностями f₁₁(l), f₂₂(l) и взаимной спектральной плотностью f₁₂(l) причем процесс x₂ = x₂(t) является регулярным. Тогда

I(x₁, x₂) = -

Рассмотрим следующее условие близости гауссовых стационарных процессов x₁(t) и x₂(t):

M|x₁(t) - x₂(t)|² Јd²

Наименьшая скорость передачи информации
H = infI(x₁,x₂), совместимая с указанным условием “d-точности”, выражается следующей формулой:

где

,

а параметр q² определяется из равенства

.

Эта формула показывает, какого типа спектральная плотность f₂₂(l) должна быть у регулярного стационарного процесса x ₂(t), который несет минимальную информацию I (x₁,x ₂) » H о процессе x₁(t). В случае дискретного времени, когда f₁₁(l ) і q ² при всех l , -p Ј l Ј p, нижняя грань H скорости передачи достигается для такого процесса x ₂ (t) (со спектральной плотностью f₂₂(l), задаваемой приведенной выше формулой), который связан с процессом x ₁(t) формулой
x ₂(t) = x ₁(t) + z(t), где z(t) – стационарный гауссов шум, не зависящий от процесса x ₂(t); в общем случае формула f₂₂(l) задает предельный вид соответствующей спектральной плотности регулярного процесса x ₂(t).

В случае, когда спектральная плотность f₁₁(l) приближенно выражается формулой

соответствующая минимальная скорость передачи информации H может быть вычислена по приближенной формуле , s² = M[x(t)]².

2.10.3. Симметричный канал без памяти

Рассмотрим симметричный канал передачи данных без памяти c конечным числом входных сигналов х₁, когда передаваемый сигнал х₁ с вероятностью 1-p правильно принимается на выходе канала связи, а с вероятностью p искажается, причем все возможные искажения равновероятны: вероятность того, что на выходе будет сигнал х₂, равна для любого х₂ № x₁, где N – общее число сигналов. Для такого канала связи пропускная способность
c = supI( x₁,x₂) достигается в случае, когда на вход поступает последовательность независимых и равномерно распределенных сигналов …, x ₁(-1), x ₁(0), x ₁(1),…; эта пропускная способность выражается формулой

Рассмотрим канал связи, на входе которого сигналы образуют стационарный процесс x ₁ = x₁(t), M[x ₁(t)]² < Ґ.

Пусть при прохождении сигнала x ₁ = x ₁(t) он подвергается линейному преобразованию Aj со спектральной характеристикой j (l) и, кроме того, на него накладывается аддитивный стационарный гауссов шум z =z (t), так что на выходе канала имеется случайный процесс x ₂(t) вида x ₂(t) = aj x ₁(t) + z (t).

Предположим также, что ограничения на входной процесс состоит в том, что M[x ₁(t)]² Ј D ² (постоянная D² ограничивает среднюю энергию входного сигнала). Пропускная способность такого канала может быть вычислена по формуле

(в последнем выражении интегрирование ведется в пределах -p Ј l Ј p для дискретного времени t и в пределах -Ґ <l <Ґ для непрерывного t), где fz z (l) – спектральная плотность гауссова процесса z (t), функция f(l) имеет вид

а параметр q² определяется из равенства

Нужно сказать, что если функция f(l) представляет собой спектральную плотность регулярного стационарного гауссова процесса x ₁(t), то этот процесс, рассматриваемый как входной сигнал, обеспечивает максимальную скорость передачи информации: I(x ₁,x ₂) = C. Однако в наиболее интересных случаях, когда время t меняется непрерывно, функция f(l) обращается в нуль на тех интервалах частот l, где уровень шума сравнительно высок (отличные от нуля значения f(l) сосредоточены в основном на тех интервалах частот l, где уровень шума сравнительно мал), и поэтому не может служить спектральной плотностью регулярного процесса. Более того, если в качестве входного сигнала выбрать процесс x ₁(t) с спектральной плотностью f(l), то этот сигнал будет сингулярным и соответствующая скорость передачи информации I(x ₁,x₂) будет равна нулю, а не максимально возможному значению C, указанному выше.

Тем не менее, приведенные выражения полезны, так как позволяют приблизительно представить вид спектральной плотности f(l) регулярного входного сигнала x ₁(t), обеспечивающей скорость передачи I(x₁, x₂), близкую к максимальному значению C. С практической точки зрения наиболее интересен случай, когда канал связи имеет ограниченную полосу w пропускаемых частот, т.е. когда спектральная характеристика выражается формулой

а проходящий через канал шум имеет равномерный спектр:

В этом случае пропускная способность может быть вычислена по приближенной формуле

.

При этом входной сигнал x₁(t), обеспечивающий скорость передачи информации I(x₁, x₂), близкую к максимальной, является гауссовым стационарным процессом со спектральной плотностью f(l) вида

так что параметры D² и s² имеют следующий физический смысл:

- энергетический уровень входного сигнала,

- энергетический уровень шума.

Previous: 2.9.1 Используемые стандарты    UP: 2.6 Методы сжатия информации
Down: 3 Каналы передачи данных    Next: 3 Каналы передачи данных