Пропускная способность дискретного канала без помех
Определим пропускную способность канала как максимальное количество информации, которое можно передавать по нему в единицу времени:
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.
Для общего описания канала связи и построения теории информации используется одна и та же модель. Канал называется д и с к р е т н ы м (непрерывным), если множества Х и 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) всегда можно определить с вероятностью, равной единице, переданную букву. К сожалению, это возможно только тогда, когда априори (до приема) известно значение вероятности р е (нуль или единица).
2.1 Дискретный канал связи без помех
Если помехи в канале связи отсутствуют, то входные и выходные сигналы канала связаны однозначной, функциональной зависимостью.
При этом условная энтропия равна нулю, а безусловные энтропии источника и приемника равны, т.е. среднее количество информации в принятом символе относительно переданного равно
I (X, Y) = H(X) = H(Y); H (X/Y) = 0.
Если Х Т – количество символов за время T, то скорость передачи информации для дискретного канала связи без помех равна
где V = 1/ – средняя скорость передачи одного символа.
Пропускная способность для дискретного канала связи без помех
(7)
Т.к. максимальная энтропия соответствует для равновероятных символов, то пропускная способность для равномерного распределения и статистической независимости передаваемых символов равна:
. (8)
Первая теорема Шеннона для канала: Если поток информации, вырабатываемый источником, достаточно близок к пропускной способности канала связи, т.е.
, где - сколь угодно малая величина,
то всегда можно найти такой способ кодирования, который обеспечит передачу всех сообщений источника, причем скорость передачи информации будет весьма близкой к пропускной способности канала.
Теорема не отвечает на вопрос, каким образом осуществлять кодирование.
Пример 1. Источник вырабатывает 3 сообщения с вероятностями:
p 1 = 0,1; p 2 = 0,2 и p 3 = 0,7.
Сообщения независимы и передаются равномерным двоичным кодом (m = 2) с длительностью символов, равной 1 мс. Определить скорость передачи информации по каналу связи без помех.
Решение: Энтропия источника равна
Для передачи 3 сообщений равномерным кодом необходимо два разряда, при этом длительность кодовой комбинации равна 2t.
Средняя скорость передачи сигнала
V =1/2t = 500 .
Скорость передачи информации
C = vH = 500×1,16 = 580 [бит/с].
2.2 Дискретный канал связи с помехами
Мы будем рассматривать дискретные каналы связи без памяти.
Каналом без памяти называется канал, в котором на каждый передаваемый символ сигнала, помехи воздействуют, не зависимо от того, какие сигналы передавались ранее. То есть помехи не создают дополнительные коррелятивные связи между символами. Название «без памяти» означает, что при очередной передаче канал как бы не помнит результатов предыдущих передач.
При наличии помехи среднее количество информации в принятом символе сообщении – Y, относительно переданного – X равно:
Для символа сообщения X T длительностиT, состоящего из n элементарных символов среднее количество информации в принятом символе сообщении – Y T относительно переданного – X T равно:
I(Y T , X T) = H(X T) – H(X T /Y T) = H(Y T) – H(Y T /X T) = n }
