Решение. (a) Аналогично доказательству леммы 2.5.1

(a) Аналогично доказательству леммы 2.5.1

Предположим, что p ₁ > p ₂ > · · · > p_M и l ₁ > l ₂ > ·· · > l_M (p_i > p_j и l_i ≤ l_j). Учитывая L (переменная, обозначающая длину кодового слова для случайно выбранного символа) для i и j, используем выражения типа p_il_i + p_j l_j . Если два кодовых слова поменять местами (меняя l_i и l_j), то эта сумма уменьшится: (p_il_i + p_j l_j) − (p_il_j + p_j l_i) = (p_i − p_j)(l_i − l_j) > 0. Т.о., L уменьшается, а любой код с таким условием не оптимален.

(b) Так как p ₁ < p_{M− 1} + p_M, видно, что p ₁ < p’_{M− 1}, где p’_{M− 1} – вероятность узла в сокращённом дереве кодов, соответствующая буквам M – 1 и M в изначальном алфавите. Т.о., аналогично части (а), l ₁ ≥ l’_M− 1 = l_M − 1.

(c) Рассмотрим произвольное кодовое дерево с наименьшей ожидаемой длиной. Предположим, что символы k и M являются соседними в этом дереве. Тогда, при k = 1 l ₁ = l_M, и наоборот, p ₁ < p_M + p_k, и l ₁ должна быть как минимум такой же длины, как непосредственный «родитель» (узел верхнего уровня) M, => l ₁ ≥ l_M − 1.

(d) и (e) Наибольшая и наименьшая длины различаются максимум на 1, причём длина некоторых чисел m ≥ 1 равна l ₁, а длины оставшихся M−m равны l ₁+1. Следовательно, 2 ^{l 1+1} = 2 m +(M −m) = M + m. => l ₁ = log₂(M)and m = 2 ^{l 1+1} −M.

2.16

(a) Рассмотреть возможность продления процедуры кодирования Хаффмана для троичных цифр. Используйте термины кодовых комбинаций, как например, листья троичных деревьев. Пусть алфавит M = 4 символа. Помните, что вы не можете нарисовать полное троичное дерево с четырьмя листьями. Начиная с дерева с тремя листьями и расширяя дерево путем преобразования листьев в промежуточные узлы, покажите, при каких значениях M возможно полное троичное дерево.

(b) Объясните, как обобщить процедуру кодирования Хаффмана для троичных цифр, имея в виду ваш результат в части (a).

(c) Используйте ваш алгоритм для множества вероятностей {0.3, 0.2, 0.2, 0.1, 0.1, 0.1}.

Решение

(a) Вырастите полное троичное дерево к полному троичному дереву на каждом шаге. У самого маленького дерева 3 листа. Для следующего, самого большого полного дерева, преобразуйте один из листьев в промежуточный узел и вырастите 3 листа от того узла. Мы теряем 1 лист, но получаем еще 2 при каждом расширении роста. Таким образом, M = 3 + 2n (для n целое число).

(b) Очевидно, что оптимально будет, если все неиспользованные листья дерева будут иметь ту же длину самого длинного кодового слова. Для М даже объединить 2 самые низкие вероятности в узел на первом шаге, а затем объединить 3 узла с самой низкой вероятностью для всех оставшихся шагов, вплоть до корневого узла. Если M нечетно, полное троичное дерево возможно, поэтому объединяем 3 узла с самой низкой вероятностью на каждом шагу.

(c) Если {a, b, c, d, e, f} имеют вероятности символа {0.3 0.2 0.2 0.1 0.1 0.1} соответственно, то троичный Код Хаффмана будет {→ 0, b → 1, c → 20, d → 21, e → 220, f → 221}.

2.17

Пусть X есть M символов, {1, 2,..., M} с упорядоченными вероятностями

p1 ≥ p2 ≥ · · · ≥ PM> 0.

Пусть X’ приведенная источником после первого шага алгоритма Хаффмана.

(а) выразить энтропию H [X] для оригинального источника в терминах энтропии H [X’] Приведенных источников, как

где H (γ) является двоичной функции энтропии, H (γ) =-γ log γ - (1-γ), log (1-γ). Найти

требуемое значение γ, чтобы удовлетворить (2,43).

(б) в дереве кода генерирующемуся по алгоритму Хаффмана, пусть v1 обозначить промежуточный узел, который является родителем конечных узлов для символов М и М-1. Пусть q1 = pm + pm-1 будет вероятность достижения v1 в коде дерева. Аналогично, пусть v2, v3,... Обозначим последующих промежуточных узлов генерируются по алгоритму Хаффмана. Сколько промежуточных узлов есть, в том числе корневого узла всего дерева?

(в) Пусть q1, q2,..., Будь вероятности достижения промежуточных узлов v1, v2,... (Заметим, что вероятность достижения корневого узла - 1).

Показать, что

Подсказка: Обратите внимание, что

(г) Выразить H [X] в виде суммы по промежуточным узлам. i тый член в сумме должен привлечь qi и двоичные энтропии H (γi) для некоторого γi предстоит определить. Вы можете найти его полезным для определения αi как вероятность движения вверх от промежуточного узла vi, при условии достижения vi. (Подсказка: посмотрите на часть а).

(е) Найти условия (в терминах вероятности и выше двоичной энтропии) под

которые L = H [X].

(ф) приведены формулы для L и H [X] выше характерных для кодов Хаффмана в одиночку, или в них не применяются (с модифицированным промежуточных узлов вероятности и энтропии) для произвольных полных свободных от префикса кодов?

Решение:

(а)Заметим что

Таким образом

(б) Каждый шаг алгоритма Хаффмана уменьшает число символов на 1 пока только 1 узел (корень) не останется. Таким образом, есть M - 1 промежуточных узлов, считающих корень.

(с) приведенный код и исходный код одни и те же, за исключением блока увеличивающего длину всякий раз, когда буквы M-1 или M встречаются.

(д) Таким образом как указано. Таким же образом, позволяя быть ожидаемой длины кода после второго шага Хаффмана,

итерации, и пользуясь тем, что длина корневого узла равна 0 мы имеем

(г) Часть (а) показывает, что H (X) = H (X’) + q1H (α1). Позволяя X(2) дальше сокращать группу после второго шага Хаффмана, и использовать часть (а) на X’, мы видим что

Таким образом

Итерация вниз до корня и отметим что

(е) Объединение частей (в) и (г),

H (ai) ≤ 1 с равенством тогда и только тогда, когда ai = 1/2. Кроме того, поскольку каждый рj> 0, следует, что каждая qi> 0. Таким образом, L - H (X) = 0, если и только если каждая ai = 1/2.

(ф) Приведенные выше рассуждения применимы к любому полному древу кода с помощью упорядочения промежуточных узлов, что идет от листьев к корню, т. е. упорядоченность, где vi является префиксом vj только тогда, когда i ≥ j.

2.18

Рассмотрим дискретный случайный символ X с символами M+1, для которых p₁≥p₂≥…≥p_M>0 и p_M+1=0. Предположим, что безпрефиксный код сгенерирован для X и что по некоторым причинам, этот код содержит кодовую комбинацию для M+1 (предположим, например, что p_M+1 фактически положительный, но столь маленький, что приближен как 0).

(а) Найдите L для Кода Хаффмана, включая символ M+1 с точки зрения L для Кода Хаффмана, опуская кодовую комбинацию для символа M+1.

(б) Предположим теперь, что вместо одного символа нулевой вероятности, есть такие n символы. Повторите часть (a) для этого случая.

Решение:

(a) Применяя алгоритм кодирования методом Хаффмана к коду с символом M + 1 где p_M+1=0, мы комбинируем символ M + 1 с символом M, и у уменьшенного кода есть символы M с вероятностями p₁,...,p_M. Код Хаффмана для этого уменьшенного набора символов - просто код для исходного набора символов с устраненным символом M + 1.

Таким образом, код включающий символ M + 1, является уменьшенным кодом, модифицированным увеличением единичной длины кодовой комбинации для символа M. Таким образом, L=L`+p<sub>M</sub>, где L` - ожидаемая длина для кода с символами M.

(б) Все n нулевых вероятностных символов объединены вместе в алгоритме Хафмана, и уменьшенный код от этой комбинации - тогда такой же как код с символами M + 1, в частности (a). Таким образом, снова L=L`+p_M.

2.19

В (2.12) показано, что X и Y независимые дискретные случайные числа и энтропия случайного XY числа выглядит как H[ XY ] = H[ X ]+H[ Y ]. Здесь мы хотим показать, что даже без предположения независимости у нас будет H(XY) ≤ H(X) + H(Y).

(а) Докажите, что

(b) Докажите, что , т.е. H[ XY ] ≤ H[ X ] + H[ Y ].

(c) Пусть X ₁ ,X ₂ ,...,X_n дискретные случайные числа, не обязательно независимые. Используйте (b) чтобы доказать, что

Решение.

(а) Энтропии Н(Х), Н(Y) и H(XY) могут быть представлены как:

Предполагается, что все пары символов х, у с нулевой вероятностью, были удалены из этой суммы, и таким образом удалены все х(у), для которых р х (х) = 0 (р у (у) = 0). Складывая эти уравнения получаем:

(b) Используя стандартное неравенство

Таким образом, H(X,Y) ≤ H(X) + H(Y). Заметим, что это неравенство превращается в равенство тогда и только тогда, когда X и Y являются независимыми.

(c) Для n символов X₁,…X_n. пусть Y будет «супер-символом» X₂…X_n. Затем используем (b)

H(X₁…X_n) = Н(Х₁,Y) ≤ Н(Х₁)+Н(Y) = H(X₁)+H(X₂…X_n).

Итерируя (повторяя) это, получаем желаемый результат.

Альтернативный подход обобщает часть (b) следующим образом:

где мы снова использовали log x ≤ (x-1) log e.

2.20

Рассмотрим случайный символ X из алфавита {1, 2, …, M} и функцией вероятности {p₁, p₂, …, p_M}. Данное упражнение выводит отношение, называемое неравенством Фано, между энтропией H[X] и вероятностью p₁ первого символа. Это отношение используется для доказательства обратной теоремы Шеннона для канала с шумами. Пусть случайный символ Y становится 1 при X = 1 и 0 во всех остальных случаях. В пунктах от (a) до (d) считайте, что значения M и p₁ однозначно определены.

(a) Выразите H[Y] в виде двоичной функции энтропии H_b(α) = −α log(α)−(1−α)log(1−α).

(b) Какова условная энтропия H[X | Y =1]?

(c) Докажите, что H[X | Y =0] ≤ log(M−1), и покажите, при каких p₂, …, p_M достигается эта граница. Затем с помощью результата пункта (b) найдите верхнюю границу H[X|Y]

(d) Найдите отношение между H[X] и H[XY].

(e) С использованием H[Y] и H[X|Y] найдите верхнюю границу H[X] и покажите, при каких p₂, …, p_M она достигается.

(f) Для такого же, как в предыдущих пунктах, M, примем, что p₁, …, p_M произвольны, а max{p₁, …, p_M} обозначим как p_max. Останется ли в силе прежняя верхняя граница, если p₁ заменить на p_max? Обоснуйте ответ.