Решение. (a) По алгоритму Хаффмана сначала объединяются p3 и p4

(a) По алгоритму Хаффмана сначала объединяются p ₃ и p ₄. Так как p ₁ = p ₃+ p ₄ ≥ p ₂, далее можнообъединить p ₁ и p ₂, вследствие чего у всех кодовых слов длина 2. Также можно объединить символ, полученный объединением символов 3 и 4, с символом 2, получая при этом кодовые слова длиной 1, 2, 3 и 3.

(b) p ₃ ≤ p ₂ и p ₄ ≤ p _2, следовательно, p ₃ + p ₄ ≤ 2 p ₂. Таким образом, p ₁ = p ₃ + p ₄ ≤ 2 p ₂, что означает p ₁ + p ₃ + p ₄ ≤ 4 p ₂. Так как p ₂ = 1 −p ₁ −p ₃ −p ₄, то 1 −p ₂ ≤ 4 p ₂, или p ₂ ≥ 0. 2. Из этого следует, что p ₁ ≤ 2 p ₂ ≤ 0. 4, => p ₁ ≤ 0. 4. p _max = 0. 4.

(c) В соответствии с частью (b), p ₂ ≤ p ₁ и p ₂ = 1 − p ₁ − p ₃ − p ₄ = 1 − 2 p ₁. Таким образом, 1 − 2 p ₁ ≤ p ₁, => p ₁ ≥ 1 / 3, т.е. p _min = 1 / 3.

(d) Параметр из части (b) остаётся прежним, если предположить, что p ₁ ≤ p ₃+ p ₄, а не p ₁ = p ₃+ p ₄ (p ₁ ≤ p ₃ + p ₄ => p ₁ ≤ p _max). Таким образом, при p ₁ > p _max p ₁ > p ₃ + p ₄. Поэтому символ, полученный объединением символов 3 и 4, будет объединён с символом 2 (или с символом 1, если p ₂ = p ₁). Т.о., кодовое слово для символа 1 (или для символа 2) будет иметь длину 1.

(e) Длина любого оптимального префиксного кода должна быть или (1, 2, 3, 3), или (2, 2, 2, 2). Если p ₁ > p _max, тогда p ₁ > p ₃ + p ₄, => длины (2, 2, 2, 2) не подходят (большая вероятность соответствует меньшей длине).

(f) Параметр из части (c) остаётся тем же, если предположить, что p ₁ ≥ p ₃ + p ₄. В данном случае p ₂ = 1 − p ₁ − p ₃ − p ₃ ≥ 1 − 2 p ₁. Объединяя с выражением p ₁ ≥ p ₂, получается p ₁ ≥ p _min. Т.о., если p ₁ < p _min, то p ₃ + p ₄ > p ₁ ≥ p ₂. Затем, после объединения p ₁ и p ₂ на втором шаге алгоритма Хаффмана каждое кодовое слово будет иметь длину 2.

(g) Если p ₁ = 0.4, p ₂ = p ₃ = 0.2, а у всех остальных символов совокупная вероятность 0.2, то структура кода Хаффмана объединяет символы с наименьшей вероятностью, пока они не будут связаны в один с вероятностью 0.2. Завершение алгоритма приводит или к одному кодовому слову длиной 1, или к трём кодовым словам длиной 2 и остальным большей длины. При p ₁ > 0.4 на каждой стадии алгоритма два символа с совокупной вероятностью, меньшей 0.4, объединяются, причём символ 1 не присоединяется, пока в уменьшенном наборе символов их не остаётся 4. Тогда, согласно полученным результатам в (d), код будет иметь кодовое слово длиной 1. Т.о., p _max=0.4.

2.14

Рассмотрим источник с М равновероятностными символами.

1) Пусть k=[Log M]. Докажите, что для кода Хаффмана, возможные длины кодового слова равны k и k-1.

2) В функции М, найдите сколько кодовых слов имеют длину k=[log M]. Какая ожидаемая длина кодового слова L в битах на символ источника?

3) Определить y = M/2^k. Выразить L – log M как функцию y. Найдите максимальное значение этой функции в диапазоне 1/2 < y ≤1. Показывает ли это, что граница энтропии, L < H[X] +1 независима в этом равновероятностном случае.

Решение:

1) Сначала, докажем что для любого равновероятностного алфавита, длина кодового слова может отличаться не более чем на 1. В дереве равновероятностного алфавита кода Хаффмана, главная ветвь соответствует любому символу j имеющему вероятность хотя бы 2/M, которая больше чем вероятность любого другого символа i. Таким образом, по лемме 2.5.1, l_j-1≤l_i для каждого j,i; таким образом, длины кодовых слов могут отличаться не более чем на 1.

Мы показали, что длинны должны быть k или k-1 для некоторого целого k. Остается показать что k = [log M]. Если M является степенью 2, значит все кодовые слова имеют длину log M. Таким образом, предполагаем, что M не является степенью 2 и пусть n_k будет номером кодового слова длиной k, где 1≤ n_k ≤ M-1. Оставшееся M – n кодовые слова будут иметь длину k – 1. Так как код является оптимальным, код дерева полный, и

N_k2^-k + (M – n_k) 2^-(k-1)=1

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

2M – n_k = 2^k.

Поскольку n_k > 0, то следует что 2M > 2^k и таким образом M > 2^k-1. Так как n_k < M, то значит что M < 2^k. Таким образом, k = [log M].

2) Из (3), n_k = 2M – 2^k. Ожидаемая длина кодового слова

L = ((k-1)(2^k-M)+k(2m-2^k))/M = k+1 = 2^k/M

3) Полагая y = M/2^k_,

L – log M = [k – log M] +1 – 2^k/M = -log y +1 - .

Обращаем внимание что 1/2 ≤ y <1. Задав производную по y нулевым значением, мы найдем что L – log M достигает его максимума в y = ln 2 с полученным значением по 1 – log (e Ln2) или приблизительно 0.08607.

Следовательно, для любого М мы имеем

L – log M ≤ 1 – log (e Ln2)

L ≤ H(X) + 0.08607.

Которая является более жесткой границей чем L < H(X) + 1.

2.15

Допустим, у дискретного источника без памяти M символов с алфавитом { 1, 2 ,...,M} и их вероятностями p ₁ > p ₂ > · · · > p_M > 0. Предположим также, что p ₁ < p_{M− 1} + p_M. l ₁, l ₂ ,..., l_M – длины префиксного кода минимальной длины для данного источника.

(a) Показать, что l ₁ ≤ l ₂ ≤ ·· · ≤ l_M.

(b) Показать, что если для генерации выше указанного кода используется алгоритм Хаффмана, то l_M ≤ l ₁+1. Подсказка: Смотреть только на первую часть алгоритма.

(c) Показать, что l_M ≤ l ₁ + 1 вне зависимости, был ли использован алгоритм Хаффмана для генерации префиксного кода наименьшей ожидаемой длины.

(d) Предположим, что M = 2 ^k для целых k. Определить l ₁ ,..., l_M.

(e) Предположим, что 2 ^k <M < 2 ^{k +1} для целых k. Определить l ₁ ,..., l_M.