Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Ига Рг
N(i)
—:— — п 1
> е
= 0.
Аналогично пусть L (г) является числом окончательных кодовых символов, соответствующих первым г промежуточным символам. Имеем
L (О
lim Рг
¦ «г > 8
= 0.
588
Отсюда видно, что для любого е > О
lim Рг
/—> се
НО
>е
_____ >Н_
N(i) щ
-^-=0,4756-.
пг
Средняя длина кода Хаффмана, который кодирует сразу четыре символа, равна 1,9702. Отсюда видно, что код Хаффмана дает оптимальное решение математической задачи при заданном множестве сообщений, однако выбор множества сообщений может быть более важным, чем выбор кодовых слов для данного множества сообщений.
3.18. (а) Оптимальным кодом будет {1, 01, 0000, 001, 0001} среднее время на одну букву источника равно 4,15.
(б) Если вероятность одного из узлов больше, чем вероятность узла, соответствующего более короткому пути, тогда два узла могут быть переставлены (переставляются также части деревьев, исходящих из них) и такая перестановка должна уменьшить среднюю длину.
3.19. Существуют 2М + 1 возможных вариантов для М монет, соответствующих тому, что одна из М монет будет тяжелой или легкой или все монеты будут стандартными. Имеются 3 возможных исхода каждого взвешивания и 3” последовательностей исходов п взвешиваний. Отсюда следует, что2Л4+1 < Зп; М < (3" — 1)/2.
(а) Для любого заданного п > 1 возьмем М = (3" — 1)/2. Поместим (Зп— 1 + 1)/2 пенни' на одной стороне весов и (Зп— 1 — 1)/2 пении и одну стандартную пенни — на другой стороне. Если весы находятся в равновесии, то все, кроме (Зп— 1 —1)/2 оставшихся пенни, имеют стандартный вес и возникает первоначальная задача при п, уменьшенном на 1. Если весы находятся не в равновесии, то у нас будет (Зп—1 +1)/2 потенциально тяжелых монет и (Зп—1 — 1)/2 потенциально легких монет (или, возможно, наоборот). Поместим (3”—2 + 1)/2 потенциально тяжелых монет и столько же потенциально легких монет на одну сторону и по (3”~2 — 1)/2 каждых из них и еще одну стандартную монету на другую сторону. Легко проверить, что после взвешивания (для каждого из трех возможных исходов) будут (3”"~2 + 1)/2 потенциально тяжелых монет и (Зп—2 — 1)/2 потенциально легких монет (или наоборот), и, таким образом, точно такая же стратегия с п, уменьшенным на 1, будет работать при следующем взвешивании.
(б) Секрет успеха (а) состоит в том, что при каждом взвешивании альтернативами были три равных множества, При М — (3” — 1)/2 и в отсутствии стандартной монеты четное число альтернатив будет невозможным, если первое взвешивание будет с нарушением равновесия, и поэтому альтернативы не могут представлять собой равные множества. Покажем теперь, как можно выполнить взвешивания с М = (Зп — 3)/2 монетами. Положим вначале (Зп~1 — 1)/2 монет на каждой стороне весов. Если будет равновесие, то останутся (Зп~1 — 1)/2 монет, которым нужно уделить внимание, и теперь уже имеются в распоряжении стандартные монеты. Если весы будут находиться не в равновесии, то следует продолжить, используя стратегию пункта (а)*>.
3.20. (а) Нць (U) = -j- [Я {U2L | U2L_ i ...t/i) +
+ H(U2L_1\U2L_2...U1) + ...+H(Ul+1\UL:.U1)]> (1)
>H(U2L\U2L_l...U1), (2)
*> He участвующие в первом взвешивании (3n 1 — 1)/2 монет будут стандартными. (Прим- ред.)
589
где было использовано то, что первое слагаемое в правой части (1) является границей снизу для каждого из остальных слагаемых. Аналогично
НL\L (^)= "У [Н (У2L I U2L— 1 ^l) (У2L— 1 UL+ 1 | ••• ^1)] <
HL \l(U)+ ? 1|L—1
где было использовано (2) для первого слагаемого и стационарность и (2.3.13) для второго слагаемого. Преобразуя, получаем Hl\l(U) < (U).
(б) Используя соотношение (2), будем иметь
HL [U) >HL]L{U)>H (U2L I U2L-i Ui)-
Так как эти границы стремятся к Нх (U) при L-* со, то Н Lj L(U) -> Н ^(U).
(в) Используя почти такое же доказательство, как в теореме 3.3.2, получаем
НИ l(U) HLlL(U) ^ i
logD logD
3.21. При условии, что и2п+-^ = и2П для всех п, пары 00 и 11 имеют каждая вероятность V2. Поэтому при условии и2п+г = п2П последовательные пары являются независимыми и число кодовых символов на букву источника стремится с ростом п к 3/4. Подобно этому при условии, что u2n_1 = и2п для всех п, последовательные пары на позициях 2п и 2п + 1 являются статистически зависимыми, но они образуют марковский граф, изображенный ниже.
Стационарные вероятности состояний равны V4 для каждого состояния; средняя по времени длина кодового слова равна 9/4, а число кодовых символов на букву источника стремится к 0/в-
3.22. (a) q (1) = q (3) = V7; q (2) = »/,.
