Решение. Любая конкретная xn строка, которая имеет i-a’s и n-b’s вероятно имеет (2/3)I (1/3)n-i

Любая конкретная xⁿ строка, которая имеет i-a’s и n-b’s вероятно имеет (2/3)^I (1/3)^n-i

Это максимальное, когда i = 105, а соответствующие вероятности 10^-17,600. Cтрокa b больше с вероятностью 1/2, и 2 b ’s имеют вероятность 1/4, как большой. Поскольку c (ⁿ_i) существует различные последовательности, которые имеют i a’ s и n − i b ’s.

Pr {Na = i} =(ⁿ_i)(²₃)(¹₃)^n-i

Оценка i = n, n− 1, and n− 2 for n = 10⁵:

Pr {Na = N} =(²₃)ⁿ ≈ 10^-17,609

Pr {Na = N-1} =10⁵(²₃)^n-1(1/3)≈ 10^-17604

Pr {Na = N-2} =(10⁵/2)(2/3)^n-2(1/3)²≈ 10^-17600

Это говорит о том, что вероятность любой из строк с na уменьшается по мере уменьшения,в то время как совокупная вероятных строк увеличивается с na a ’s, na. Мы видели в предыдущем упражнении, что типичный набор множеств, где na близка к Na и теперь мы видим, что наиболее вероятные отдельные строки имеют фантастическую малую вероятность,как индивидуально, так и в совокупности, и, следовательно, могут быть проигнорированы.

2.27

Пусть X₁, X₂, ……, будет последовательностью IDD символов из ограниченного алфавита. Для каждого блока длинной n и для любого малого числа ɛ>0 определен хороший набор n-кортежей Xⁿ как набор:

a) Объяснить как отличается от

b) Показать что где W -Log pmf rv для X

c) Получить верхнюю границу числа элементов вида и определить значение α (Вы должны найти наименьшее значение α какое сможете, но не доказывая, что меньшее значение может быть использовано в верхней границе)

d) Пусть будет набором n-кортежей X_n, которые лежат в , но не в . Найти верхнюю границу для в форме . Найти наименьшую β.

e) Найти предел при

Решение.

a) Хороший набор отличается от типичного тем, что включает только нетипичные, невероятные последовательности. Остальные остаются нетипичными вероятными. В предыдущем упражнении, последовательности с N_a = 0, 1 или 2 являются нетипичными, вероятными.

b) В последствии это подмножество

c) Каждый элемент имеет вероятность превышающую , число таких элементов может достигать не более . Следовательно:

где

Каждый элемент , который не находится в имеет вероятность не меньше . Следовательно: - где

d) Нам нужна нижняя граница на , но этого не достаточно. Другая возможность - содержит Используя это:

Из этого видно, что = 0, сходится как . Другими словами, большинство элементов типичны для множеста n.

2.28

Типичный набор определенный в тексте обычно называется простым(обычным, слабым) типичным набором, в отличии от другого вида типичного набора, называемого сложным (надежным, сильным). Возьмём дискретный источник без памяти (?гистерзисный?) и примем ( за число символов в n-последовательности «формула», принимающей значение j. Тогда сложный набор определяется как:

= { : (1-ℰ) < < (1+ℰ); for all j ∈ }

a) Доказать, что (

b) Доказать, что каждый в обладает таким свойством, что:

H[X](1 − ε) < < H[X](1 + ε)

c) Доказать, что если ∈ , тогда ∈ и ε’ = H[X]ε, то есть, что ⊆ .

d) Доказать, что для каждого δ > 0 и достаточно больших n,

Pr ( ∈ ) ≤ δ

Подсказка: Беря каждое j по отдельности, 1 ≤ j ≤ M, покажите, что для каждого достаточно большого n:

Pr ≤

e) Доказать, что для каждого δ > 0 и всех достаточно больших n:

(1 − δ) < | <

Обратите внимание, что части c и e представляют собой ту же теорему, что и для сложного набора, как Теорема 2.7.1 для простого набора.

Решение.

a) Вероятность n-кортежа выражается, как (. Это множество включает условия x _k для которых x _k обозначается j, и это верно для каждого j в алфавите.

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

( (5)

b) Взяв логарифм (из 5),

= (6)

Используя определение для , все ∈ должны удовлетворять

(1 − ) < < (1 + )

H(X)(1 − ) < < H(X)(1 + )

Сопоставляя это с (6, каждый ∈ удовлетворяет неравенству

H[X](1 − ε) < < H[X](1 + ε) (7)

c) Взяв ε’= H(X) , (7) показывает, что для всех ∈ ,

H[X](1 − ε’) < < H[X](1 + ε’)

По (2.25) в тексте, это определяющее уравнение для , так, что все , входящие в , так же принадлежат .

d) Для каждого j в алфавите Обычный Закон Простых Чисел говорит, что для любого ε > 0 и δ > 0, и для всех достаточно больших n,

Pr ≤ (8)

Для всех достаточно больших n, (8) выполняется для всех j, 1 ≤ j ≤ M. Для всех таких достаточно больших n, каждый или принадлежит , или является членом события, такого, что для некоторого j, ограниченного сверху δ, так что Pr(,) ≥ 1 − δ.

e) Доказательство, точно такое же, как и у теоремы 2.7.1. Часть (b) даёт верхнюю и нижнюю границу на Pr( для ∈ , и (d) показывает, что 1 − δ ≤ Pr( ≤ 1), которые вместе дают желаемую оценку числа элементов .

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

(а) Случайная величина D_n в п. 2.7.4 была определена как начальная длина строки закодированных битов, необходимых для декодирования первых n символов источника входного сигнала. Для примера кодирования с переменной длиной в упражнении 2.23, список входных строк и соответствующих кодированных выходных строк, которые должны быть проверены, чтобы декодировать первые буквы источников и из этого найти PMF функции D₁. Подсказка: Целых 8 букв источника должно быть закодировано перед тем, как X₁ может быть расшифрован.

(б) Найти PMF D₂. Один пункт этого упражнения состоит в том, чтобы убедить вас, что D_n является полезной RV для доказательства теорем, но не RV, полезной для подробного расчета. Он также ясно показывает, что D_n может зависеть от более чем первых n букв источника.

РЕШЕНИЕ

--------------------------

2.30

Цепь Маркова S0, S1,... ниже начинается в устойчивом состоянии в момент времени 0 и имеет 4 состояния, S = {1, 2, 3, 4}. Соответствующий источник Маркова X1, X2,... имеет исходный алфавит X = {A, B, C} размером 3.

(а) Найти стационарные вероятности {Q (S)} цепи Маркова.

(б) Найти H [X1].

(в) Найти H [X1 | S0].

(г) Описать однозначно-декодируемый датчик, для которого L = H [X1 | S0). Предположим, что начальное состояние известно для декодера. Объясните, почему декодер может отслеживать состояние после времени 0.

(д) Предположим, вы наблюдаете выходе источника, не зная состояния. Каково максимальное количество исходных символов, которые вы должны заметить до того, как узнаете состояние?

РЕШЕНИЕ

(а) Прежде всего заметим, что цепь является эргодической (т. е. она апериодическая и все состояния могут быть получены из всех других состояний). Таким образом, устойчивое состояние вероятности Q (S) существует и удовлетворяет уравнениям

и .

Для данной цепи, вот последние уравнения

q(1) = q(1)(1/2) + q(2)(1/2) + q(4)(1)

q(2) = q(1)(1/2)

q(3) = q(2)(1/2)

q(4) = q(3)(1).

Решение с проверкой, q(1) = 1/2, q(2) = 1/4, и q(3) = q(4) = 1/8.

(б) Для расчета H (X₁) мы сначала рассчитываем PMF PX₁ (х) для каждого х ∈ X. Используя стационарное состояние вероятности Q(S) для S₀, у нас есть

. Так как X₁ = a происходит с вероятностью 1/2 для обоих S₀ = 0 и S₀ = 2 и происходит с вероятностью 1 из S₀ = 4, .

Точно так же, . Поэтому PMF от X₁ – и H(X₁)=3/2.

(в) PMF из X1 при условии, что S₀ = 1 – . Следовательно, . Аналогично, . Нет никакой неопределенности состояний 3 и 4, поэтому H (X1 | S0 = 3) = H (X1 | S0 = 4) = 0. Так как H (X1 | S0) определяется как , мы имеем

, что меньше, чем H (X1), как ожидалось.

(г) Мы можем добиться L = H (X1 | S0) по достижении L (S) = H (X1 | ов) для ∈ каждого состояния . Чтобы сделать это, мы используем оптимальный беспрефиксный код для каждого состояния. Для S₀ = 1, код {a → 0, b → 1} является оптимальным с L (S0 = 1) = 1 = H (X1 | S0 = 1). Аналогично, для S0 = 2 {a → 0, c → 1} является оптимальным с L (S0 = 2) = 1 = H (X1 | S0 = 2). Так как H (X1 | S0 = 3) = H (X1 | S0 = 4) = 0, мы не используем никакой код для состояний 3 и 4. Другими словами, наш датчик не передает биты для символов, которые являются результатом переходов из этих состояний.

Сейчас мы объясним, почему декодер может отслеживать состояние после времени 0. Декодеру предполагается знать начальное состояние. Когда находимся в состояниях 1 или 2, следующее кодовое слово из соответствующего беспрефиксного кода однозначно определяет следующее состояние. Когда состояние 3 введено, следующее состояние должно быть 4, так как есть один детерминированный переход из состояния 3, который переходит в состояние 4 (а это, как известно, не получив следующего кодового слова). Аналогичным образом, когда состояние 4 введено, следующего состояние должно быть 1. Когда состояния 3 или 4 вводятся, следующее полученное кодовое слово соответствует последующему переходу из состояния 1. Таким образом, декодер может отслеживать состояние.

(д) Вопрос немного неоднозначный. Значение слова, сколько исходных символов x1, x2,..., Хк должны быть замечены пока новое S_K состояние не известно, но можно было возможно интерпретировать это как определение начального s₀ состояния.

Для того чтобы определить новое состояние, обратите внимание, что символ всегда приводит цепь в состояние 0 и символ b всегда гонит его в состояние 2. Символ C, однако, может привести к состоянию 3 или 4. В этом случае последующий символ может быть C, приводя к состоянию 4, или может быть a, что приведет в состояние 1. Таким образом, более 2 символов необходимо для определения нового состояния.

Определение исходного состояния, с другой стороны, не всегда возможно. Символ a может исходить от состояний 1, 2 или 4, и никакие последующие символы не могут разрешить эту неопределенность.

Более интересная проблема заключается в определении состояния, и затем начать декодирование правильно, когда начальное состояние неизвестно для декодера. Для кода выше, это легко, так как всякий раз, когда появляется 0 в закодированном потоке, соответствующий символ будет a и следующее состояние - 0, что позволяет правильно декодировать далее. Эта проблема известна как проблема синхронизации, довольно сложно даже для источников без памяти.

2.31

Пусть X₁,X₂,...,X_n будут дискретными случайными числами. Выведите следующее правило

Подсказка: используйте правило для n =2 из (2.37) и спросите себя, является ли k-последовательность случайных чисел сама по себе случайной величиной.

Решение.

Мы знаем из (2.37), что H(XY)= H(Y)+ H(X | Y) для любых случайных чисел X и Y. Для любой последовательности из k случайных чисел X₁,…,X_k мы можем X_k взять в качестве X, а из k -1-последовательности X_k-1,X_k-2,…X₁, взять Y, получая следующее

H(X_k,X_k−1 ...,X₁) = H(X_k | X_k−1,...,X₁) + H(X_k−1,...,X₁).

Так как это равенство выражает энтропию каждого k -го члена с точки зрения k -1-члена, мы можем повторять это, получая

2.32

Рассмотрим дискретную эргодическую цепь Маркова S0, S1,... со случайным начальным распределением.

(a) Показать, что H[S2|S1S0] = H[S2|S1] (использовать основное значение условной энтропии).

(b)С помощью Упражнения 2.31 показать, что для любого n ≥ 2,

H[S1S2 · · · Sn|S0] =n

k=1

H[Sk|Sk−1].

(c) Упростить для случая, когда S0 постоянна.

(d) Для цепи Маркова с выходами X1X2 · · ·, объяснить почему H[X1 · · · Xn|S0] =

H[S1 · · · Sn|S0]. По желанию можно ограничить n = 2.

(e) Проверить (2.40)

Решение:

(a) Мы должны показать, что . Сделаем это с помощью случайных символов S1S0, определение условной вероятности:

,где мы будем использовать для исности сокращения, использовавшиеся выше. По последовательности Маркова, для всех s0, s1, s2.Таким образом,

Заменяем это в (9), получаем

(b) Используя результат упражнения 2.31,

Оценивая S0 как один символ и n-кратный S1,..., Sn как другой,

Комбинируя эти два уравнения,

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

Заменяем это в (11),

(c) Если цепь начинается с установленного значения, каждое последующие значение имеет установленное значение pmf, поэтому каждое из условий выше одинаковые и

20(d) По значениям цепи Маркова, значение S0 и следующие значение символа X1 однозначно определим следующее значение S1 (и vice-versa). Так же, давая значение S1, следующий символ X2 однозначно определяет следующее значение S2. Таким образом, , где x1x2 те же значения, что X1X2 в связи один к одному со значениями выборки s1s2 из S1S2, все значения S0 = s0.

Поэтому совместное pmf X1X2 обусловлено S0=s0 так же, как pmf для S1S2 обусловлен S0=s0. Из этого следует результат.

(e) Комбинируя результаты (c) и (d) подтверждения (2.40) в тексте.

2.33

Выполнить LZ77 последовательность строки 000111010010101100. Предположим, что длина окна W = 8; начало окно указано выше. Вы должны разобрать остальный строки Lempel-Ziv алгоритм.

Решение:

Lempel-Ziv разбор данной строки можно сделать следующим образом:

Строка анализируется в 3 этапа. На каждом шаге,окна подчеркиваются и разобранный блок объединяются скорбой. (n, u) пары результатоы из этих шагов соответственно (3,7), (4,2) и (3,8).

Используя бинарный код для n, чье отображение 3 → 011 и 4 → 00100, и стандартное 3-битовое изображение для u, 1 ≤ u ≤ 8, закодированные последовательности - 011, 111, 00100, 010, 011, 000 (передается без запятых).

Обратите внимание, что на небольших примерах, такой как в этом случае, LZ77 может быть не очень эффективным. Обычно, алгоритм требует большего размера окна для эффективного сжатия.

2.34

Пусть алгоритм LZ77 используется для бинарной строки x₁^10,000= 0⁵⁰⁰⁰1⁴⁰⁰⁰0¹⁰⁰⁰.

Эта запись означает, что строка состоит из 5000 нулей в начале, затем 4000 единиц и в конце 1000 нулей. Возьмем размер окна w = 1024.

(a) Опишите, как эта строка будет закодирована. Представьте зашифрованную строку и опишите её подстроки.

(b) Какой длины будет зашифрованная строка?

(c) Пусть мы уменьшили размер экрана до w = 8. Какой длины будет зашифрованная строка в этом случае? (Обратите внимание, что такой маленький размер экрана будет пригоден только для простых примеров, подобных этому.)

(d) Создайте модель Маркова с двумя состояниями, которая будет вполне хорошо отражать исходную строку. Не вдавайтесь в подробности; используйте общий смысл.

(e) Вычислите энтропию в битах на символ исходной строки для Вашей модели.

Решение

(a) Начальная подстрока будет представлять собой первые w = 1024 символа, которая кодируется как 0¹⁰²⁴. Окно тогда будет содержать строку вида 0¹⁰²⁴.

Вторая подстрока состоит из оставшихся 5000 − 1024 = 3976 нулей, тогда n = 3976, u = 1.

(Фактически мы видим здесь некоторую неоднозначность; наибольшее совпадение наблюдается для n = 3976, причем это совпадение справедливо для любого u, 1 ≤ u ≤ 1024.) n=3976 кодируется в [log3976] = 11 нулей, за которыми следует последовательность 1⁵0³10³. u=1 кодируется в 0⁹1. Тогда окно будет содержать строку 0¹⁰²⁴.

Третья подстрока состоит из единственного символа 1 (поскольку нет совпадений), соответствующего n = 1. Мы определяем символ ‘1’, за которым следует‘1’, чтобы закодировать n = 1. Таким образом, окно содержит строку 0¹⁰²³1.

Четвертая подстрока состоит из оставшихся 3999 символов, тогда n = 3999, u = 1. n=3999 кодируется в [log3999] = 11 нулей, за которыми следует строка 1⁵0²1⁵. u=1 кодируется в 0⁹1. Следовательно, окно будет содержать строку 1¹⁰²⁴.

Пятая подстрока содержит единственный символ 0 (поскольку больше совпадений нет), что соответствует n = 1. Мы определяем символ ‘0’, за которым следует ‘1’, чтобы закодировать n = 1. Таким образом, окно содержит строку 1¹⁰²³0.

Шестая (и последняя) строка состоит из оставшихся 999 нулей, тогда n = 999, u = 1. n=999

кодируется как [log999] = 9 нулей, за которыми следует 1⁵0²1³. u=1 кодируется как 0⁹1.

Объединяя всё описанное выше, конечная закодированная строка будет иметь вид 0¹⁰³⁵1⁵0³10¹²1³0¹¹1⁵0²1⁵0⁹1010⁹1⁵0²1³0⁹1.

(b) Сложив длины описанных строк, получаем конечную длину: 1024+23+10+2+23+10+2+19+10 = 1123 бита для кодирования полученной строки, из которых 1024 используются для заполнения окна исходной некодированной строкой.

(c) Рассмотрим три отличия между случаем с w = 8 и случаем, где w = 1024. Во-первых, исходное окно требует w = 8 бит вместо 1024. Во-вторых, нам требуется только 3 бита для кодирования u вместо 10 бит. В-третьих, первая (n, u)-пара имеет вид (4992, 1) вместо (3976, 1), для чего необходимо 25-битное кодовое слово, чтобы закодировать n. Оставшиеся (n, u)-пары идентичны в обоих случаях. В итоге получаем

8 + 25 + 3 + 1 + 1 + 23 + 3 + 1 + 1 + 19 + 3 = 88 бит для кодирования строки.

Обратите внимание, что размер окна w = 1 будет оптимальным для данной исходной последовательности.

(d) За каждым из 5000 + 999 нулей (исключая последний символ в последовательности) стоит ‘0’ (кроме нуля, за которым следует ‘1’). Аналогично за каждой из 4000 единиц за исключением одной следует единица. Простая модель Маркова для этого случая представлена ниже. Символы, которыми отмечены изменения состояний,

указывают на выходные данные источника во время изменения состояния. Вероятности изменения состояний написаны над стрелками.

(e) Сперва мы находим вероятности устойчивых состояний данной цепочки Маркова, решив три линейных уравнения:

Решение следующее:

2.35

(a) Докажите, что если выбран оптимальный (под «минимумом» понимается длина) беспрефиксный код (в зависимости от условий pi > pj для i < j), длина кодового слова удовлетворяет условию li ≤ lj для всех i < j. Используя это, докажите, что для всех j ≥ 1 выполняется условие l_j ≥ [log j] + 1.

(b) Асимптотическая эффективность беспрефиксного кода для всех положительных целых чисел определена выражением lim_j→∞ (l_j / log j). Какова асимптотическая эффективность унарно-бинарного кода?

(c) Объясните, как построить беспрефиксный код для положительных целых чисел, если асимптотическая эффективность равна 1. Подсказка: замените унарную часть унарно-бинарного кода для целых n =[log j] + 1 кодом, длина которого растет медленнее с увеличением n.

Решение

(a) При условии, что l1 ≤ l2 ≤ · · · ≤ lj, имеем j кодовых слов, длины которых не превышают l_j, и не более 2^lj беспрефиксных кодов длины l_j и менее. Таким образом l_j ≥ logj. Если j меньше размера алфавита M, то должен быть как минимум один промежуточный код длины l_j для оставшихся кодовых слов. Значит

l_j ≥ [log l_j] + 1. Есть одно исключение, на которое стоит обратить внимание: если j = M

и j является степенью 2, возможно для всех кодовых слов получить одинаковую длину: log j = [log j].

(b) В унарно-бинарном коде l_j = 2[log j] + 1, таким образом асимптотическая эффективность равна 2.

(c) Как предложено в подсказке, мы можем использовать унарно-бинарный код для кодирования целых чисел n = [log j]+1, которые используются в унарной части унарно-бинарного кода. Такой код иногда называют унарно-бинарно-бинарным. Таким образом, длина кодового слова j равна [ log j] + 2 [log n] + 1, где n = [log j] + 1. По существу это log j + log log j, таким образом асимптотическая эффективность в этом случае равна 1.