Пропускная способность дискретного канала без помех

Определим пропускную способность канала как максимальное количество информации, которое можно передавать по нему в единицу времени:

C = max{Ixy}/ tx (бит/с) (4.1)

Для канала без помех справедливо условие I xy = H x , а потому его пропускная способность:

C бп = max{Hx}/ tx = log 2 m / tx (4.2)

В частном случае передачи двоичных разрядов (m = 2) справедливо

С бп = 1/tx (4.3).

Для нас важно, как соотносится величина С бп с потоком информации источника H`z , который определяется по формуле

H`z = Hz/tz (бит/с) (4.4).

Пропускная способность канала используется полностью, когда H`z = C. Между тем, уменьшение энтропии Hz может привести к сокращению информационного потока. Чтобы его увеличить, требуется сократить время tz . Если учесть, что

tz = tx * lср, где lср - средняя длина кода символа, то становится ясно: чтобы полнее использовать пропускную способность канала для любого источника, нужно рационально кодировать сообщения, по возможности сокращая величину lср .

Если записать условие полного использования пропускной способности канала H`z = C в развернутом виде, то для канала без помех оно будет иметь вид:

Hz/tz = log 2 m/tx (4.5),

а с учетом tz = tx * lср и log 2 m = 1 (при m=2) мы получим условие:

lср = Hz (4.6)

По сути, доказательство этой так называемой теоремы Шеннона о кодировании для канала без помех сводится к нахождению процедуры, позволяющей получить требуемый код. Эта процедура, именуемая эффективным кодированием, была предложена самим Шенноном и в дальнейшем усовершенствована (с точки зрения удобства ее практического применения) Хаффменом.

В обоих случаях речь идет о посимвольном кодировании и величина Hz имеет значение безусловной энтропии. В принципе можно пойти дальше и рассматривать кодирование цепочек символов. В этом случае Hz будет иметь смысл условной энтропии порядка l, где l - максимальная длина цепочки. О "цепочечном" кодировании речь впереди, а пока мы рассмотрим классический подход к эффективному кодированию на уровне символов.

Рассмотрим теперь вариант, когда помехи в канале вызывают появление ошибок с вероятностью p 0 . В этом случае из соотношения 3.1 следует:

C = max {Hx - Hx/y}/ tx = (log 2 m - Hx/y) / tx (4.8)

Рассмотрим наиболее распространенный случай так называемого двоичного симметричного канала. При этом m = 2 (log 2 m = 1), а вероятности ошибки “переход "1" в "0” ” “переход "0" в "1" ” одинаковы.

Если теперь рассмотреть в качестве случайного события передачу разряда кода с ошибкой (вероятность p 0), то, используя формулу (2.8) для определения энтропии, получим:

Hx/y = Hy/x = -p 0 log 2 p 0 - (1 - p 0) log 2 (1 - p 0) (4.9)

С учетом этого (4.8) преобразуется к виду:

C = /tx (4.10)

Таким образом, пропускная способность симметричного двоичного канала с помехами определяется только скоростью передачи разрядов кода (Vx = 1/tx) и вероятностью ошибок.

Наглядно зависимость C(p 0) иллюстрирует рисунок 2.

Рисунок 2

Как видно, максимальное значение пропускной способности канала достигается при p 0 = 0 «канал без помех»и при p 0 = 1 (очевидно, что если канал передает все символы с ошибками, то последние легко устраняются инвертированием). Минимальное значение C = 0 имеет место при p 0 = 0.5.

Шеннон показал, что за счет кодирования пропускную способность канала с помехами также можно использовать максимально полно (напомним, что сама она будет ниже, чем у канала без помех).

Способ кодирования, который позволяет этого добиться, основан на использовании избыточных кодов, когда каждый информационный блок защищается контрольными разрядами и чем больше длина блока, тем меньше удельный вес этих избыточных разрядов, позволяющих обнаружить и исправить ошибки. Вопросы применения корректирующих кодов мы рассмотрим в разделе 5.

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

Очевидно, что при этом можно передавать но каналу элементов сообщения в секунду. Но . Таким образом, при этих условиях теорема справедлива даже при . В этом случае иногда (впрочем, без особого основания) считают, что сообщение передается без кодирования.

2. Пусть по-прежнему , но , где - целое число. Построим все возможные последовательности из кодовых символов («кодовые комбинации») длиной . Очевидно, их число равно . Установим взаимно однозначное соответствие каждого элемента сообщения кодовой комбинации. Таким образом, каждая комбинация из символов, переданная по каналу, соответствует одному элементу сообщения и, следовательно, скорость передачи элементов сообщения

. (2.8)

Таким образом, и в этом случае теорема справедлива даже при . Такой код, в котором все кодовые комбинации имеют одинаковую длину , называется равномерным - разрядным кодом.

3. Пусть для того же источника с объем алфавита не является целой степенью числа . Так, например, пусть источник выбирает независимо и с равной вероятностью любую из десяти цифр 0, 1,..., 9, а канал имеет два символа (обозначим их 0 и 1) и позволяет передаватьсимволов в секунду.

Здесь дв. ед. и . Согласно теореме скорость передачи цифр в таком канале может быть сделана сколь угодно близкой к .

Попытаемся достигнуть этого, кодируя каждую цифру равномерным -разрядным кодом. Это сводится, в сущности, к тому, чго каждая из десяти цифр 0, 1,..., 9 изображается двоичным числом: 0000, 0001,..., 1001. Очевидно, что для этого потребуются четырехразрядные двоичные числа. Таким образом, на каждый элемент сообщения (цифру) при таком кодировании потребуется 4 кодовых символа, тогда как теорема утверждает, что можно осуществить более «экономное» кодирование, приближаясь к количеству кодовых символов 3,332 на цифру.

Покажем, что это можно сделать, если до кодирования произвести укрупнение алфавита источника. Будем рассматривать каждую пару цифр, выдаваемых источником, как двухразрядное десятичное число, т. е., перейдем от и сведем по-прежнему «кодирование к изображению этого числа в двоичном счислении. Всякое число меньше 100 можно представить семиразрядным двоичным числом (на том основании, что 27 = 128 > 100, тогда как 26 = 64 и поэтому шестиразрядных двоичных чисел не хватит для представления всех двухразрядных десятичных чисел). При таком кодировании на каждые два знака сообщения потребуется семь кодовых символов, т. е. в среднем 3,5 кодового символа на цифру, а не 4, как было до укрупнения алфавита.

Продолжим укрупнение алфавита, рассматривая каждые три цифры, выдаваемые источником, как трехразрядное десятичное число. Его можно представить в двоичном счислении 10-разрядным числом (так как 210=1024>1000). Следовательно, при таком кодировании на одну цифру потребуется 10/3=3,333 кодового символа, что уже очень близко к теоретической величине 3,332.

Дальнейшие укрупнения алфавита позволят еще больше приблизить скорость передачи цифр по такому двоичному каналу к величине , но, конечно, не превзойти ее. Действительно, если объединить цифр, выдаваемых источником, в -разрядное десятичное число, то его можно изобразить -разрядным двоичным числом при условии, что или , откуда

. (2.9)

В данном случае знак равенства даже невозможен, так как при целых и равенство означает, что является рациональным числом, тогда как в действительности оно иррационально.

Вообще, когда , но не является целой или рациональной степенью , можно для любого числа найти такое число , при котором справедливы неравенства

(2.10)

Будем рассматривать каждые букв сообщения как букву укрупненного алфавита объемом элементов и установим взаимно однозначное соответствие укрупненных букв кодовым комбинациям равномерного -разрядного кода, что всегда можно сделать на основании (2.10) (так как ), причем часть комбинаций останется неиспользованной. Тогда каждая комбинация из символов, переданная по каналу, соответствует буквам первичного алфавита сообщения. Скорость передачи сообщения при этом равна, со скоростью, сколь угодно близкой к - букв в секунду. Такой метод кодирования мы будем называть примитивным. Это утверждение, конечно, более слабое, чем требование теоремы, по которому для любого источника с энтропией скорость передачи может быть сколь угодно близкой к

Соотношения (7.1)–(7.3), определяющие скорость пе­редачи и пропускную способность канала и линии связи, являются общими, и поэтому они при­менимы как для дискретных, так и для непрерывных ка­налов, как для каналов без шумов, так и для каналов с шумами. Разница заключается в способе вычисления ко­личества информации, содержащейся в последовательности выходных сигналов Z T , о входных сигналах Y T , т.е. I (Z T , Y T ).

Для вычисления I (Z T , Y T ) можно использовать соотношения (5.30) или (5.31). Из этих соотношений получаем

I(Z T ,Y T) = H(Z T) – H(Z T ‌ | Y T) = H(Y T) – H(Y T | Z T). (8.9)

Будем полагать, что шумы, действующие в канале связи, имеют эргодический характер. Это значит, что, например, при длительной многократной передаче сигнала у i сигналы z на выходе канала с вероятностью, как угодно близкой к единице, образуют типичную последовательность. То же самое справедливо и при передаче эргодической последовательности различных сигналов у. При таком условии выход канала связи может рассматриваться как эргодический источник.

Для последовательности длительностью Т, содержащей М сигналов такого источника, имеем

H(Z T) = MH(Z), (8.10)

где H(Z) – энтропия выходного сигнала или, точнее, энтропия выхода канала связи, рассматриваемого как эргодический источник.

Величина H(Z) может быть подсчитана по формуле, аналогичной (6.10),

H(Z) = (8.11)

При этом Q l и Q k обозначены характерные состояния выхода канала связи.

Такое же соотношение получим и для вычисления условной энтропии

H(Z T | Y T) = MH(Z | Y), (8.12)

где H(Z |Y) – энтропия выходного сигнала канала связи при известных входных сигналах.

Повторяя рассуждения, приведенные при выводе (6.10), получим

H(Z |Y) = (8.13)

При этом p(Q l | Q k , y j) – условная вероятность перехода выхода канала связи из состояния Q k в состояние Q l при передаче сигнала y j .

Из (8.9), (8.10) и (8.12) следует, что

I(Z T , Y T) = MH(Z) – MH(Z | Y).

При определении скорости передачи информации по (7.3 ’) учтем, что ; при этом, как и ранее, - средняя длительность сигнала одного сообщения. Тогда получим

Повторяя рассуждения, аналогично найдем

В последнем равенстве - поток информации на выходе кодирующего устройства, характеризует потерю информации, обусловленную действием помех.

Из найденных соотношений и (7.3) следует, что пропускная способность канала связи при наличии помех может быть определена из условия

Оба определения равноправны и дают одно и то же значение С с. Использование того или иного определения дикдуется удобством анализа. При отыскании оптимальных статистических характеристик передаваемых сигналов (у ) необходимо иметь в виду следующее:

Характерные состояния выхода канала связи (Q k , Q l ) могут определяться двумя обстоятельствами:

а) наличием фиксированных ограничений, т.е. запретов, накладываемых на допустимую последовательность передачи различных сигналов, и

б) коррелятивными связями между символами, вызываемыми действием шумов.

Каналы, у которых на каждый передаваемый сигнал (символ) шум воздействует независимоот того, какие сигналы передавались ранее, называются каналами без памяти. В этих каналах шумы не вызывают дополнительных коррелятивных связей между сигналами. В настоящее время основные выводы теории информации получены применительно к каналам без памяти.

Проиллюстрируем вычисление пропускной способности канала на следующем примере.

Пусть требуется определить пропускную способность канала связи, по которому передаются двоичные сигналы со скоростью v x , если вероятность превращения в результате действия помех каждого из этих сигналов в противоположный равна р (вероятность правильного приема, следовательно, 1 – р ). Передаваемые сигналы предполагаются независимыми.

Рис. 8.3. Двоичный симметричный канал

В этом случае алфавит Х и алфавит Y состоят из двух символов: Х = (х 1 ,х 2), Y =(у 1 , у 2). Диаграмма рис. 8.3 показывает возможные варианты передачи и соответствующие им вероятности. Такой канал называется симметричным.

Средняя условная энтропия

Но p (x 1) + p (x 2)=1.

H (Y ôX )= -p log p – (1 – p )log (1 – p ).

Отсюда видно, что H (Y ôX )не зависит от характеристик источника, т.е. от р (х 1)и р (х 2),и определятся только помехами в канале передачи.

Максимальное количество информации на один символ получается, следовательно, при таком распределении вероятностей р (х i ),при котором оказывается максимальным член H (Y ). Но H (Y )не может превосходить величины

H m (Y )= log m =log 2

(что достигается при р (х 1)= р (х 2)=1/2.Поэтому имеем:

max{I (Y , X ) = log 2 + p log p + (1 – p )log (1 – p )

и, следовательно, пропускная способность

C = v x max {I (Y , X )} =

= v x . (8.19)

Отсюда следует, в частности, что при p = 0,т.е. при отсутствии шумов в канале, имеем максимальное значение С

С max = v x log 2.

При р =1 также имеем детерминированный случай, когда сигналы х 1 переводятся в сигналы х 2 и наоборот с вероятностью, равной единице. При этом пропускная способность канала также максимальна.

Минимальное значение пропускная способность имеет при p =1/2(C max = 0).

Если на вход канала подаются сигналы от всех возможных источников дискретных сообщений с одинаковым количеством символов в единицу времени u = 1/T и числом элементарных символов т, то выражение для С и, соответственно, для пропускной способности канала в расчете на единицу времени выглядит так:

Отсюда при т = 2 имеем (8.19).

Для общего описания канала связи и построения теории информации используется одна и та же модель. Канал назы­вается д и с к р е т н ы м (непрерывным), если множества Х и Y дискретны (непрерывны), и п о л у н е п р е р ы в н ы м, если одно из множеств дискретно, а другое непрерывно. Ниже рассматриваются только дискретные каналы.

Канал полностью описывается условными вероятностями того, что k-ì принятым символом будет

j k -й символ множества Y (j k = 1, m y ).

Указанную вероятность можно рассматривать как функ­цию , вид которой отражает состояние канала, в частности, характер взаимодействия помехи и сиг­нала. Если

то соответствующий канал называется каналом без памяти. Если вероятность не зависит от k (от времени), то соответствующий канал называется стацио­нарным. Ограничимся рассмотрением только стационар­ных каналов без памяти. Определим скорость передачи информации как предел:

где - средняя взаимная информация между пере­данным и принятым. В случае отсутствия помехH (X /Y )=0, следовательно, R = H (X ). Этот предел в случае канала без памяти равен взаимной информации:

R=I (X,Y )=H (X ) -H (X|Y )=H (Y ) -H (Y|X ) .

Скорость передачи информации R полностью определяется

вероятностями . Поэтому изменять величину R мы можем только за счет изменения вида распре­деления , поскольку - характеристика неуп­равляемого канала. Определим пропускную способность кана­ла С как максимальную по скорость передачи инфор­мации:

.

В случае отсутствия помех

.

Вычисление пропускной способности симметричных каналов

Существует класс каналов, для которых пропускная спо­собность С легко вычисляется. Канал полностью описывается так называемой стохастической матрицей

в которой сумма всех элементов, образующих строку, рвана единице.

Канал называется с и м м е т р и ч н ы м п о в х о д у, если строки матрицы различаются только порядком расстановки некоторого множества чисел

Для симметричных по входу каналов частная условная энтропия

Она не зависит от номера передаваемой буквы и может быть вычислена по любой строке матрицы. Поэтому условная энтропия

Канал называется с и м м е т р и ч н ы м п о в ы х о д у, если столбцы матрицы различаются только порядком расста­новки некоторого множества чисел .

Если распределение источника равномерное

то распределение на выходе симметричного по выходу канала также будет равномерным. При этом энтропииН(Х) и H (Y ) достигают своего максимального значения. В этом легко убедиться, если доказать, что вероятность не за­висит оту j . Представим вероятность в виде

Поскольку

Сумма не зависит от номера столбцаj и в общем

случае не равна единице. Поэтому вероятность также

не зависит от j и равна . При этом

Канал называется симметричным, если он симметричен по входу и выходу. Для симметричного канала H (Y | X ) не зависит от распределения источника сообщений, поэтому пропускная способность

В качестве примера вычислим пропускную способность симметричного канала, который описывается матрицей

где m = m X = m Y . В этом случае

C 1

0,2

0 0,2 0,4 0,6 0,8 1 P e

Рис. 3. Зависимость пропускной

способности ДСК от вероятности ошибки p e

Вероятность 1-p e равна вероятности правильного приема символа. Вероятность ошибки p e равна вероятности приема y j c при условии, что было передано x i . Тогда

Широкое распространение получил двоичный симметрич-ный канал (ДСК) (m =2) , для которого пропускная способность (Рис. 3)

Максимальная скорость передачи информации, равная единице, получается при р е =0 и при р е =1. В этом случае множества Х и Y находятся во взаимно однозначном соответ­ствии, и по принятому у j (j =1, 2) всегда можно определить с вероятностью, равной единице, переданную букву. К сожа­лению, это возможно только тогда, когда априори (до при­ема) известно значение вероятности р е (нуль или единица).