Решение. (a) Y является 1 при X = 1 с вероятностью p1 и 0 во всех остальных случаях

(a) Y является 1 при X = 1 с вероятностью p₁ и 0 во всех остальных случаях. Таким образом, H(Y) = −p₁log(p₁)−(1 − p₁)log(1 − p₁) = H_b(p₁).

(b) Если Y = 1, X = 1 с вероятностью 1, следовательно H(X|Y=1) = 0.

(c) Если Y = 0, X = 1 с вероятностью 0, значит X имеет (M–1) возможных значений (т.е. с ненулевой вероятностью). Максимальная энтропия алфавита размером вида (M–1) равна log(M–1), то есть H(X|Y=0) ≤ log(M−1). Эта верхняя граница достигается при Pr(X=j|X≠1)=1/(M–1) при любом j≠1. Поскольку Pr(X=j|X≠1)=p_j/(1−p₁), эта верхняя граница H(X|Y=0) достигается, когда p₂ = p₃ = … = p_M. Отсюда с учётом пункта (b) H(X|Y)=p₁H(X|Y=1) ≤ (1−p₁) log(M−1).

(d) Обратите внимание, что H(XY) = H(Y) + H(X|Y) ≤ H_b(p₁) + (1−p₁) log(M−1), и это неравенство становится равенством при p₂ = … = p_M. Теперь есть два разумных подхода. Один заключается в том, что, т. к. H(XY) также может быть выражена как H(X) + H(Y|X), а значение Y однозначно определяется значением X, то H(Y |X) = 0, и H(X) = H(XY) ≤ H_b(p₁)+(1−p₁)log(M−1) (4), причём эта граница достигается при p₂ = p₃ = … = p_M. Другой подход заключается в следующем: отметим, что H(X) ≤ H(XY), что снова приводит нас к выражению (4), но это ещё не значит, что равенство выполняется для p₂ = … = p_M. Выражение (4) – это граница Фано; оно используется, когда p₁ очень близка к 1 и играет ключевую роль в теореме Шеннона для канала с шумами.

(e) (f) Та же граница сохраняется для каждого символа при замене p₁ на p_j для любого j, 1 ≤ j ≤ M. Таким образом, она также сохраняется для p_max.

2.21

Дискретный источник без последействия испускает независимые одинаково распределённые случайные коды X₁, X₂, …. Каждый случайный код X включает символы {a, b, c} с вероятностями {0.5, 0.4, 0.1} соответственно.

(a) Найдите ожидаемую длину L_min лучшего беспрефиксного кода переменной длины для X.

(b) Найдите ожидаемую длину L_min,2, нормированную к виду бит/символ, лучшего беспрефиксного кода переменной длины для X₂.

(c) Правда ли, что для любого дискретного источника без последействия L_min ≥ L_min,2? Обоснуйте ответ.