Решение. (a) Кодовые комбинации кода Хаффмана для набора вероятностей {0.5, 0.4, 0.1} имеют длины {1, 2, 2}, и таким образом

(a) Кодовые комбинации кода Хаффмана для набора вероятностей {0.5, 0.4, 0.1} имеют длины {1, 2, 2}, и таким образом, L_min = 1.5.

(b) Набор вероятностей для (X₁,X₂) – это {0.25, 0.2, 0.2 0.16, 0.05, 0.05, 0.04, 0.04, 0.01}. Построение кода Хаффмана приводит нас к длинам {2, 2, 2, 3, 5, 5, 5, 6, 6}. Ожидаемая длина – 2.68, значит ожидаемая длина на символ источника L_min,2=1.34.

(c) Обратите внимание, что в этом примере L_min,2 ≤ L_min. В целом этот результат истинен, т.к. один набор кодовых комбинаций для (X₁,X₂) является объединением таковых для X₁ и для X₂. Так что код минимальной ожидаемой длины для (X₁,X₂) действительно должен быть хотя бы не больше этого результата.

2.22

Для дискретного источника без памяти (ДМС) X с алфавитом Ӽ = {1,2,…,M}, пусть L_min,1, L_min,2, и L_min,3 будут нормализованными средними длинами, в битах на исходный символ, для Кода Хаффмана по Ӽ, Ӽ² и Ӽ³ соответственно. Покажите что L_min,3 ≤ 2/3 L_min,2 + 1/3 L_min,1.

Решение:

Одним из способов генерировать исходный код для (X₁, X₂, X₃) состоит в том, чтобы связать Код Хаффмана для (X₁, X₂) с Кодом Хаффмана X₃. Ожидаемая длина получающегося кода для (X₁, X₂, X₃) есть L_min,2 + L_min. Ожидаемая длина на исходную букву этого кода 2/3 L_min,2 + 1/3 L_min. Ожидаемая длина на исходную букву оптимального кода для (X₁, X₂, X₃) может быть не хуже, таким образом, L_min,3 ≤ 2/3 L_min,2 + 1/3 L_min,1 .

2.23

Кодирование длин серий

Допустим X₁, X₂, …, - последовательность случайных символов a и b, где вероятность появления символа a p_x(a)=0.9, а появления символа b p_x(b)=0.1. Мы кодируем исходную последовательность при помощи кодирования длин серий. Исходная последовательность вначале записывается цифрами путем подсчёта количество букв a между буквами b. Таким образом промежуточный вывод происходит при каждой встрече буквы b в исходной последовательности. Так как мы не хотим чтобы числа могли быть слишком большими, то если промежуточное число=8 что соответствует 8 буквам a подряд – пишем его и начинаем считать с этой точки заново. Таким образом, мы пишем число, если в последовательности встретилась буква b или 8 букв a подряд. После этого начинаем считать заново. Пример:

baaabaaaaaaaaaabbaaaab

0 3 8 20 4

0000 0011 1 0010 0000 0100

На последнем этапе кодировки преобразуем наши цифры следующим образом: цифру восемь записываем как 1. Остальные – как 4х битовые двоичные числа, начинающиеся с 0, за которым следуют 3 значащих разряда.

(a) Показать, что такой код в любом случае возможно однозначно раскодировать

(b) Найти ожидаемое количество выводимых битов соответствующее каждой встрече букв b в исходной последовательности. Количество включает в себя 4х битовое кодирование буквы b и 1-битовое кодирование 8 букв a подряд

(c) Рассматривая строку из 10²⁰ символов показать, что количество буков b относительно всех символов составит число очень близкое к 0,1 с очень высокой вероятностью

(d) Совмещая части (b) и (c) найти предполагаемое количество кодированных битов на один исходный символ.

Решение:

Допустим C и Cˈ - коды соответствующие преобразованию исходные символы в десятичные цифры и десятичные цифры в конечную битовую последовательность соответственно.

Всё успешно и однозначно раскодируется в случае если и C и Cˈ однозначно декодируемы.

Длины заданные для Cˈ удовлетворяют неравенству Крафта — Макмиллана отсюда следует что этот код может быть беспрефиксным и, следовательно, однозначно декодируем

(a) С – код преобразующий строку переменной длины (1-8) на входе {b,a²b,… a⁷b,a⁸} в единственную цифру 0-8 на выходе. Этот набор строк образуют полный беспрефиксный набор и, таким образом, любая входящая строка может быть разобрана на `кодовые слова` и затем преобразована в цифры от 0 до 8. Цифры могут быть декодированы в `кодовые слова` которые затем складываются в исходную последовательность. В общем, код преобразующий данные переменной длины на входе в данные фиксированной длины на выходе однозначно декодируем, если кодировщик сможет разобрать (скорее всего, исходный текст), что гарантировано тем, что набор кодовых слов полный и беспрефиксный

(b) Каждая встреча буквы b в исходной последовательности влечёт вывод 4х бит в конечный код. Плюс к этому встреча подряд 8 букв a влечёт вывод еще 1 бита. Таким образом, на каждую букву b кодировщик выводи 4 бита с вероятность=1 и выводит еще 1 бит с вероятностью (0.9)⁸ (вероятность встретить 8 букв a подряд перед b) и еще один бит с вероятностью (0.9)¹⁶ (если букв a 16 подряд) и.т.д.

Тогда количество выводимых бит на букву b =4+(0.9) ⁸+ (0.9)¹⁶=

(c) Чтобы сосчитать количество букв b в исходной строке положим, что B_i=1 если i-тая буква строки – b и B_i=0 – если нет. Тогда E(B_i)=0.1 и . Пусть будет числом встречающихся букв b на 1 букву 1 в строке из n=10²⁰ символов. примет значение 0.1 и дисперсия будет равна 0.9*10^(-21), т.е. искомое отношение очень близко к 0.1 с очень высокой вероятностью. И чем длиннее строка, тем вероятность выше.

(d) Общее количество символов в конечном коде соответствующее 10¹⁹ буквам b на строку из 10²⁰ символом с высокой вероятностью близко к 4.756*10¹⁹(1+ε) при очень маленьком ε.

Таким образом, количество бит на один исходный символ =

2.24 (РЕШЕНИЕ!!)

(а) Пусть DMS излучает h и t с вероятностью 1/2 каждое. Для ε = 0,01, чему равно T 5?

(б) Найдите T 1 при Pr(h) = 0,1, Pr(t)=0,9 и ε=0,001.

2.25

Представим DMS как двух-символьный алфавит, {a, b} где p_x(a)=2/3 and p_x(b)=1/3. Пусть Xⁿ=X₁,…,X_n будет рядом случайных символов при n=100,000.

a) Пусть W(X_j) будет логарифмом функции распределения случайной величины от j, т.е. W(X_j) = - log 2/3 для X_j=a и –log 1/3 для X_j=b. Найти дисперсию W(X_j).

b) Для ε=0.01 дайте оценку предела вероятности пересечения в (2.24)

c) Пусть N_a это номер а-того элемента в строке Xⁿ=X₁,…,X_n. Случайная величина N_a – сумма независимых одинаково распределенных случайных величин. Покажите что это за случайные величины.

d) Выразите случайную величину W(Xⁿ) как функцию от случайной величины. Выразите зависимость от n.

e) Выразите обычную последовательность в значениях зависимых от N_a (т.е., T_εⁿ = {xⁿ: α < N_a < β} и вычислите α и β).

f) Найдите значение и дисперсию N_a. Рассчитайте Pr{T_εⁿ}используя центральную предельную теорему. Теорема рассчитывает Pr{T_εⁿ}, учитывая, что N_a подчиняется Гауссовом распределению со значением и дисперсией фактического N_a.

С одной стороны упражнение показывает, что неравенство Чебышева необходимо для нахождения Pr{T_εⁿ}, что не сразу заметно в самом тексте (хотя это строгая граница, в то время как Гауссово распределение относительно четкое, но не строгое). С другой стороны, показывается, что n должно быть достаточно большим для обычного ряда, чтобы выглядеть усредненным.

Решение:

a) Предположим, что W принимает значения от –log(2/3) с вероятностью 2/3 -log(1/3) с вероятностью 1/3. Таким образом E(W)=log3-2/3. Положим, что E(W)=H(X). Отклонение W в этой формуле равно -1/3 с вероятностью 2/3 и 2/3 с вероятностью 1/3. Таким образом σ²_W=2/9.

b) Предел вероятности обычного ряда, который был получен используя неравенство Чебышева и указано в (2.2):

c) Чтобы посчитать номер а-того элемента, пусть случайная величина Y_i(X_i) будет 1 для X_i=a и 0 для X_i=b. Y_i(X_i) –одинаково распределенные случайные величины со значением Ỹ=2/3 и σ²_W=2/9. N_a(X_n) задается как

Которое имеет значение 2n/3 и математическое ожидания 2n/9.

d) Т.к. кортеж n-значений Xⁿ – одинаково распределенные случайные величины, тогда типичный результат w(xⁿ)= Σ_iw(x_i). Пусть n_a будет типовым значением N_a соответствующему xⁿ. Т.к. w(a)=-log2/3 и w(b)=-log1/3, мы имеем

Другими словами, Ŵ(Xⁿ), отклонение от W(Xⁿ) – отрицательное значение отклонения N_a(Xⁿ). Типичный пример Ŵ(Xⁿ)= - N_a(Xⁿ).

e) Обычный ряд дан

где использовалось . Таким образом, и .

f) Из части (с) Ň=2/3 и σ²_W=2/9.

Центральная предельная теорема утверждает, что для n большого, сумма n независимых одинаково распределенных случайных величин имеет распределение близкое к Гауссовому кроме среднеквадратического отклонения от значения. При возрастании n диапазон и точность приближения увеличивается. Таким образом, α и β ниже и выше 10³ соответственно. Среднеквадратическое отклонение sqrt(2*10⁵/9), таким образом, α и β имеют значение в 6,7 большего среднеквадратического отклонения. Вероятность, что Гауссовская случайная величина больше чем 6,7 среднеквадратических отклонений около (1,6)*10^-10.

Это не претендует на точное приближение, но показывает слабость предела Чебышева, которое полезно в нахождении предела, а не числового приближения.

2.26

Для случайных величин в предыдущем упражнении, найти Pr {Na =i} для i = 0, 1, 2. Найти вероятность того,что с каждой отдельной строкой xⁿ для значений i. Найти частности xⁿ строка, которая имеет Максимальную вероятность по всем выбранным значения Xⁿ. Какие следующие наиболее вероятные n-строки? Дайте краткое описание того, почему наиболее вероятные n -строки не рассматриваются как типичные строки.