Решение. а) Так как X1 и X2 независимые и одинаково распределенные величины, симметрия подразумевает, что Pr (X1> X2) = Pr (X2> X1)

а) Так как X₁ и X₂ независимые и одинаково распределенные величины, симметрия подразумевает, что Pr (X₁> X₂) = Pr (X₂> X₁). Эти два события являются взаимоисключающими и событие X₁ = X₂ невозможно. Таким образом, Pr (X₁> X₂) и Pr (X₁ <X₂) имеет стопроцентную вероятность =1, значит вероятность каждого из событий должна быть равна 1/2. Таким образом, Pr (X₁ ≥ X₂) = Pr (X₂ ≥ X₁) = 1/2.

б) Применяя симметрию между X₁, X₂ и X₃, мы видим, что каждое из них имеет равную вероятность быть наименьшим (вероятность их равнозначности равна 0). Эти три события являются взаимоисключающими, и сумма их вероятностей должна равняться 1. Поэтому каждое событие происходит с вероятностью 1/3.

в) событие {N> п} так же, как события {X₁ является минимальным среди n независимых случайных величин X₁, X₂, · · ·, X_n}. Расширяя аргумент в части (б), мы видим, что Pr (X₁ является самым маленьким из X₁,..., X_n) = 1 / n. Наконец, Pr {N ≥ n} = Pr {N> n - 1}=1∕(n-1) для n ≥ 2.

г) Так как N неотрицательная целочисленная случайная переменная (со значением от 2 до ∞), мы можем использовать упражнение №2.3 (а) следующим образом:

Так как ряд расходится, мы заключаем, что E [N] = ∞.

(е) Так как алфавит состоит из конечного числа букв, Pr (X₁ = X₂) уже не 0 и зависит

от конкретного распределения вероятностей. Таким образом, несмотря на то, что, Pr (X₁ ≥ X₂) = Pr (X₂ ≥ X₁) симметрично, ни одно из выражений не может быть найдено, без распределения.

Из букв алфавита с ненулевой вероятностью, пусть a_min - буква минимального числового значения. Если X₁ = a_min, то никакие последующие случайные величины X₂, X₃,... не могут иметь меньшее значение, поэтому N = ∞ в этом случае. Поскольку событие X₁ = a_min происходит с положительной вероятностью, E [N] = ∞.

2.5

Пусть X1, X2,..., Xn последовательность n двоичных iid rv’s. Предположим, что Pr{Xm=1} = Pr{Xm=0} = 1/2

Пусть Z четности на X1,..., Xn, т. е. Z = X1 ⊕ X2 ⊕ · · · ⊕ Xn

(где 0 ⊕ 0 = 1 ⊕ 1 = 0 и 0 ⊕ 1 = 1 ⊕ 0 = 1).

(а) является Z зависит от X1? (Предположим, п> 1).

(б) Z, X1,..., Xn-1 независимы?

(с) Z, X1,..., Xn независимы?

(д) Z не зависит от X1, если Pr {Xi = 1} = ½ здесь вы можете взять n=2

Заметим сначала, что для любого n ≥ 1, число двоичных кортежей с четными номерами единиц, равна числу двоичных кортежей с нечетными номерами единиц. Чтобы убедиться в этом, заметим, что для каждой последовательности (x1, x2, · · ·, xn−1, 0)

соответствует единственная последовательность (x1, x2, · · ·, xn−1, 1).

Одна из этих двух последовательностей имеет нечетные номера единиц в то время как другой имеет четный номер единиц.

Так как все 2^n n-последовательности равновероятны, то вероятность четных номеров единиц равна вероятности нечетному числу, т.е.

Pr(X1 ⊕ X2 ⊕ · · · ⊕ Xn = 0) = Pr(X1 ⊕ X2 ⊕ · · · ⊕ Xn = 1) = 1 / 2

(а) Так как Z = X1 ⊕ · · · ⊕ Xn, это показывает, что двоичная случайная переменная Z принимает значения 0 и 1 с равной вероятностью. Теперь, при условии X1 = 0, Z будет 0, если X2 ⊕ · · · ⊕ Xn = 0, что, сверху (с помощью X2,..., Xn вместо X1,..., Xn) имеет вероятность 1 / 2. Точно так же, при условии X1 = 1, Z снова принимает значения 0 и 1 с вероятностью 1/2 каждое. Таким образом, Z не зависит от X1.

(б) Учитывая, что X1 = x1, x2 = x2, · · ·, Xn-1 = х-1, Z равна 0,

если Х = x1 ⊕ x2 ⊕ · · · ⊕ хп-1.

Так как Хn не зависит от X1,..., Xn-1, и равновероятно 0 или 1, следует, что Z = 0

при этом кондиционирования с вероятностью 1/2 и Z = 1 с вероятностью 1/2. Так как это верно для всех выборов x1,..., Хп-1 следует, что Z не зависит от X1,..., Xn-1.

(с) Z, X1, X2, · · ·, Xn не являются статистически независимыми, а на самом деле, Z однозначно определяется по X1,..., Xn.

(г) Z не является статистически независимым от X1, если Pr (Xi = 1) = р ≠ 1 / 2. Покажем это для n = 2. Условная PMF рz | x1 (z | x1) для x1 = 0 и 1 является

pZ|X1 (0|0) = Pr(X2 = 0) = 1 − p,

pZ|X1 (0|1) = Pr(X2 = 1) = p.

Так как условные PMF для Z зависит от X1, Z и X1 являются статистически зависимы.

Цель этого вопроса, чтобы показать, что в группе n +1 случайных величин, попарно статистической независимости (части) не следует статистическая независимость всех случайных величин (часть С) (даже с учетом статистической независимости групп п случайных величин в части (б).

2.6

Определить бесконечный код в качестве кода, в котором ни одно кодовое слово не является окончанием любого другого кодового слова.

(а) Показать, что бесконечные коды являются однозначно декодируемыми. Используйте определение уникальной декодируемости из раздела 2.3.1, а не интуитивное, но расплывчатое представление о декодируемости с начальной синхронизацией.

(б) Найдите пример бесконечного кода с длиной кодового слова (1, 2, 2), который не является беспрефиксным кодом. Может быть кодовое слово декодироваться, как только его последний бит поступает на декодер?

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

(C) Существует ли код с длиной кодового слова (1, 2, 2), который является одновременно беспрефиксным и бесконечным?

Объясните.

(А) Предположим противное, т. е. имеется бесконечный код, который не является однозначно декодируемым. Значит этот код должен содержать две различных последовательностей исходных букв, скажем, x1, x2,..., Хn и x’1, х’2,..., Х’m

такие, что

C (x1) C (x2)... С (хn) = C (x’1) C (x’2)... C (x’m).

Тогда одно из перечисленного должно быть верным:

• C (хn) = C (x’m)

• C (хn) является окончанием С (x’m)

• С (x’m) является окончанием C (хn).

В последних двух случаях мы приходим к противоречию, так как предполагается, что код - бесконечный.
В первом случае, хn должен быть равны х’m в связи со свободным окончанием. Просто удалите этот последний символ из каждой последовательности и повторите параметр. Так как последовательности различны, последняя буква должна стать другой после некоторого числа повторений приведенных выше рассуждений, и в этот момент один из двух последних пунктов имеет место и противоречие достигнуто.

Таким образом, бесконечные коды являются однозначно-декодируемыми.

(Б) Любой беспрефиксный код становится бесконечным, если порядок символов в каждом кодовом слове - обратный. Простейший такой пример {0,01,11}, бесконечный код (с длиной кодового слова {1, 2, 2}), но не беспрефиксный.

Кодовое слово в приведенном выше коде не может быть расшифровано, пока его последний бит не поступит на декодер.

Для иллюстрации крайнего случая, рассмотрим следующий результат, выданный декодером,
0111111111...

Полагая, что исходные символы {A, B, C}, {0,01,11}, мы не можем различить две возможных последовательностей исходника,

acccccccc...

и

bcccccccc...,

пока конец строки не будет достигнут. Следовательно, в этом случае декодеру, возможно, придется ждать сколь угодно долго до их раскодирования.

(С) Не может быть никакого кода с длиной кодового слова (1, 2, 2), который является одновременно песпрефиксным и бесконечным. Без изменения порядка, установим C1 = 0. Затем беспрефиксный код не может использовать кодовые слова 00 и 01 для C2 или C3, и, следовательно, должен использовать 10 и 11, которые не являются бесконечными.

2.7

Алгоритм, данный в сущности (2.2) для создания префиксных кодов из набора длин кодирующих слов предполагает, что длины изначально были отсортированы. Приведите пример, в котором алгоритм не будет работать, если длины не будут отсортированы.

Решение

Возьмём набор длин кодирующих слов (1,2,2) и расположим их как (2,1,2). Тогда, представлено как . Далее, должно быть представлено используя 1 бит после бинарной точки, что невозможно. Следовательно, алгоритм не работает.

2.8

Предположим, что по некоторым причинам, Вы хотите закодировать код-источник символами из D-ичного алфавита(где D — некоторое целое число больше 2), а не двоичным алфавитом.

Описанное в Параграфе 2.3, может быть легко расширено до D-ичного случая, используя D-ичные деревья, а не бинарные деревья для представления префикс-свободных(prefix-free) кодов. Обобщите неравенство Крафта, (2.1), для D-ичного случая и обрисуйте в общих чертах, почему оно остается действующим(валидным).

Решение:

Неравенство Крафта для D-ичного алфавита можно сформулировать так: Каждый префикс-свободный (prefix-free) код для алфавита X с кодовым словом длиной {l(x), x ∈ X } удовлетворяет,

С другой стороны, если неравенство выполняется, тогда перфикс-свободный(prefix-free) код с длинами {l(x)} существует.

Фишка в том, чтобы определить необходимые шаги, которые могут доказать работу в бинарном случае и прийти к заключению, что они всегда могут быть распространены на D-ичный случай:

Если мы сопоставим число с кодовым словом y1y2... yn,
тогда все кодовые слова, которые начинаются с y1, y2,..., yn лежат в интервале [0.y1y2... yn, 0.y1y2... yn +D−n).

Поскольку код префикс-свободный(prefix-free), никакие два интервала не могут перекрываться(наложиться друг на друга).

Так как интервалы не пересекаются и все содержатся в промежутке [0, 1), то сумма всех длин интервала меньше или равна единице.

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

2.9

Пусть префикс без кода имеет символ вероятностей p1, p2, … pm и длин li, …, lm. Предположим также, что ожидается длины L удовлетворяет L = H[ X ].
a) Объяснить почему pi = 2^l для каждого i.

b) Объясните, почему последовательность закодированных двоичных разрядов представляет собой последовательность независимых одинаково равновероятных двоичных цифр. Подсказка: используйте рисунок 2.4 для иллюстрации этого явления, и объяснить словами, почему результат справедлив в целом.

(a)Предположим что pj > 0 для любой j. Из заданий 2.8 и 2.9

Как видно из рисунка 2.7, неравенство будет строгим, если 2-LJ = р для каждого J. Таким образом, если

H [X] = L, следует, что 2-LJ = pj для любой j.

(b) Сначала рассмотрим рисунок 2.4, предположим, что PR (A) = 1/2 и Pr (B) = Pr (с) = 1/4. Первый узел порядка 0 соответствует букве «a» и имеет вероятность 1/2. Первый порядок узла 1 соответствует входу либо буквой В или С и следовательно, имеет вероятность 1/2.

Аналогично, второй порядок нулевых узлов соответствует AA, который имеет вероятность 1/4, а второй, чтобы узел 01 соответствовал либо AB, либо переменному току, у которых совокупная вероятность 1/4. Таким же образом, 10 adm 11 соответствуют В и С, с вероятностью 1/4 каждый. В общем, когда бесконечное двоичное дерево используется для представления бесконечной последовательности букв от iid источника, где каждая буква J имеет вероятность р и длину J = 2-й, мы видим, что каждый узел, соответствующий исходной последовательности букв sx1,..., Хп имеет вероятность i2-си равных произведений вероятностей отдельных слов и порядков, равных ixi.

2.10

Условие

(а) Показать, что в коде из M кодовых слов, удовлетворяющем неравенству Крафта с равенством, максимальная длина может быть не больше М-1. Объяснить, почему это обеспечивает конечность числа подобных различных кодов.

(б) Рассмотрите число различных полных кодовых деревьев с конечными узлами. Считайте два дерева различными, если соответствующие им множества кодовых слов отличаются друг от друга; иными словами, не рассматривайте исходный набор символов и пропустите сопоставление исходных символов и кодовых слов. Покажите, что S(2)=1, а также что для M>2

, при этом принято считать, что S(1)=1.

Решение:

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

a

e

d

c

b

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

(б) Очевидно, что существует только одно полное дерево с двумя листовыми узлами. То есть S(2)=1. Далее мы используем индукцию для подсчета количества полных деревьев двоичного кода с М>2. Для данного М, сначала рассмотрим количество деревьев, в которых j кодовых слов начинается с 0, а M-j начинается с 1 (). Так как набор кодовых слов, начинающийся с нуля, должны образовывать полное кодовое дерево с пропущенным начальным нулем, существует S(j) таких деревьев. Как видно выше, S(2)=1, и заведомо S(1)=1. Аналогично получим S(M-j) различных деревьев, начинающихся с 1.таким образом, для данного j существует S(j)S(M-j) кодовых деревьев с М кодовыми словами, для которых j кодовых слов стартуют с 0. Это значит, что

Можно проверить формулу для малых значений М, взяв S(3)=2, S(4)=5 и т.д.

2.11

(Доказательство неравенства Крафта для однозначно декодируемых кодов)

(а) Предположим, что однозначно декодируемый код имеет длину . Для того, чтобы показать, что , нужно рассмотреть следующее тождество для каждого целого :

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

(в) Пусть – число последовательностей, имеющих суммарную длину i. Тогда

(г) Используя однозначную декодируемость кода и максимальное значение каждого , покажите что:

(д) Извлекаем корень n-ной степени и предполагаем , получаем неравенство Крафта.

Решение:

(а) Для n=2,

Аналогично для других n.

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

(в) Перепишем предыдущее выражение относительно числа последовательностей n кодовых слов суммарной длиной i,

Это следует из того, что каждое кодовое слово имеет длину не более , а значит каждая последовательность имеет длину не более .

(г) Из однозначной декодируемости кода следует, что все эти последовательности должны быть различны, значит существует не более 2i последовательностей общей длиной i, т.е. . Таким образом, вышеупомянутая сумма содержит не более , то есть

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

при . Поскольку неравенство из пункта (г) выполняется при всех n, неравенство Крафта верно.

2.12

Сообщение с размером алфавита имеет вероятности появления символа { }.

(а) Используя алгоритм Хаффмана найдите оптимальный префиксный код для сообщения.

(б) Используя алгоритм Хаффмана найдите еще один префиксный код с другим набором длин.

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

Решение

(а) и (б) Один код Хаффмана – это , где c и d менее возможные буквы, другой - .

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

2.13

Алфавит из M = 4 символов имеет вероятности p ₁ ≥ p ₂ ≥ p ₃ ≥ p ₄ > 0.

(a) Показать, что при p ₁ = p ₃+ p ₄ существует код Хаффмана, где все длины равны, а также ещё один с длиной одного кодового слова – 1, другого – 2, и оставшихся двух – 3.

(b) Найти наибольшее значение p ₁ (p _max), для которого возможно равенство p ₁ = p ₃ + p ₄.

(c) Найти наименьшее значение p ₁ (p _min), для которого возможно равенство p ₁ = p ₃ + p ₄.

(d) Показать, что при p ₁ > p _max в каждом коде Хаффмана будет кодовое слово длиной 1.

(e) Показать, что при p ₁ > p _max в каждом оптимальном префиксном коде будет кодовое слово длиной 1.

(f) Показать, что при p ₁ < p _min все кодовые слова будут иметь длину 2 во всех кодах Хаффмана.

(g) Предположим, что M > 4. Найти такоенаименьшее значение p’ _max, что неравенство p ₁ > p’ _max обеспечивает наличие у кода Хаффмана кодового слова длиной 1.