Основная теорема Шеннона о эффективном кодировании

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

J(Z; Y) = H_апр(Z) – H_апост(Z) = H_апр(Y),

так как H(Y) = H(Z) и H(Y/Z) = 0, а max{J(Z; Y)} = H_max(Y) – max энтропия источника сигнала, получающаяся при равномерном распределении вероятностей символов алфавита Y.

p( y₁) = p( y₂) = ... = p( y_m) = 1/M_y,

т.е. H_max(Y) = log_aM_y

и, следовательно, пропускная способность дискретного канала без помех в единицах информации за единицу времени равна:

C_y = V_y · max{J(Z; Y)} = V_y · H_max(Y) = V_y · log_aM_y

или C_k = V_k · log_aM_y,

где M_k – должно быть max возможное количество уровней, допустимое для передачи по данному каналу (конечно, M_k = M_y);

V_k – определяется частотными переключательными способностями канала:

Если источник информации создает поток информации

,

а канал связи обладает пропускной способностью С ед. информации в единицу времени, то при H(x) ≤ C:

1. Сообщения, вырабатываемые источником, всегда можно закодировать так, чтобы скорость их передачи была сколь угодно близкой к .
2. Не существует способа кодирования, позволяющего сделать эту скорость большей, чем V_{x max}.

Согласно сформулированной теореме существует метод кодирования, позволяющий при:

H(x) ≤ C – передавать всю информацию, вырабатываемую источником при ограниченном объеме буфера;

H(x) > C – такого метода кодирования не существует, так как требуется буфер, объем которого определяется превышением производительности источника над пропускной способностью канала, умноженной на время передачи.

Из этой теоремы вытекает следующее следствие: если источник информации имеет энтропию H(X), то сообщения всегда можно закодировать так, чтобы средняя длина кода l_ср (количество символов сигнала на одну букву сообщения) была сколь угодно близкой к величине:

,

то есть при а = 2 (бит) и M_y = 2 {0; 1} имеем:

,

где p_i – вероятность встречи данного элемента алфавита;

l_i – количество символов в i-ой кодовой комбинации;

ε – бесконечно малая величина ≥ 0, т.е. lim l_ср = H(x).

Это следует из равенства:

.

Таким образом, l_ср выступает критерием эффективности кодирования. Чем ближе l_ср к H(x), тем лучше мы закодировали. В инженерной практике это различие можно считать допустимым 3÷5% (до 10%). http://peredacha-informacii.ru/ Из этого же критерия следует, что если буквы имеют равномерное распределение вероятностей их употребления, то

H(x) @ log₂ M,

а l_ср тоже равно log₂ M. Пределы эффективного кодирования:

H(x) ≤ l_ср ≤ log₂ M.