Лекция № 17

Тема: Пропускная способность канала связи. Теорема Шеннона

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

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

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

C_бп = max{Hx}/ tx = log₂m / tx (2)

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

С_бп = 1/tx (3).

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

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

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

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

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

Hz/tz = log₂m/tx (5),

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

lср = Hz (6)

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

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