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

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

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

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

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

C_бп = max{Hx}/ tx = log₂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₂m/tx (4.5),

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

lср = Hz (4.6)

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

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

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

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

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

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

Hx/y = Hy/x = -p₀ log₂p₀ - (1 - p₀) log₂(1 - p₀) (4.9)

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

C = [1 - p₀log₂p₀ - (1 - p₀)log₂(1 - p₀)]/tx (4.10)

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

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

Рисунок 2

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

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

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