Неравенство - крафт
Cтраница 2
Суммирование (3.3.8) по k превращает левое неравенство в неравенство Крафта (3.2.3), и существует префиксный код с этими, длинами. [16]
Покажем теперь, почему коды с запятой удовлетворяют неравенству Крафта. Код с запятой, алфавит которого состоит из г символов ( г - основание), имеет один фиксированный символ, называемый запятой; он используется для обозначения конца всех кодовых слов, за исключением самых длинных; конец слов максимальной длины декодер узнает непосредственно по их длине. [17]
Обратно, при заданном бесконечном множестве длин, которые удовлетворяют неравенству Крафта, можно использовать построение, выполненное в теореме 3.2.1, чтобы построить код, обладающий свойством префикса. Здесь необходимо сделать два замечания. Первое состоит в том, что так как неравенство Крафта удовлетворяется, то существует конечное множество слов каждой длины щ и поэтому длины могут быть упорядочены; второе состоит в том, что следует начинать ( методически) с полного бесконечного дерева. [18]
Но если pk 2l просуммированы по 1 k L, получаем неравенство Крафта, для которого демонстрировали, что там существует код, удовлетворяющий префиксному условию. [19]
Если Р ( а /) 3 - й для всех k, то неравенство Крафта удовлетворяется с равенством. Вместе с тем, если число сообщений является четным, то кодовое дерево не является полным и при этом еще одно кодовое слово могло бы быть добавлено без нарушения неравенства Крафта. [20]
Поскольку это последнее неравенство справедливо для любых п0, величина х не может превосходить 1, что и доказывает неравенство Крафта. [21]
Покажите, что если отображение /: X - Y является разделимым кодом с синхронизацией, то ( i) длины кодовых слов п ( х) Д / ( / ( х)) удовлетворяют неравенству Крафта, причем неравенство обращается в равенство ( ср. [22]
 |
Дерево декодирования вание 3 численные эквиваленты кодов систематически увеличивались с. [23] |
Применим теорему еще к одному примеру. Левая часть неравенства Крафта равна 1 / 3 5 ( 1 / 9) 4 ( 1 / 27) 28 / 27, так что найти мгновенный код с такими параметрами невозможно. Если удалить последнее кодовое слово длины 3, то сумма будет в точности равна 1, и такой код можно найти. [24]
Определим полное кодовое дерево как конечное кодовое дерево, в котором из каждого промежуточного узла исходят D узлов следующего более высокого порядка. Как можно заметить из доказательства неравенства Крафта, для полного кодового дерева неравенство Крафта удовлетворяется с равенством. [25]
Заметим еще раз, что теорема утверждает существование такого кода и ничего не говорит о конкретных кодах. Может существовать код, который удовлетворяет неравенству Крафта и тем не менее не является мгновенным, однако в этом случае существуют коды с теми же / -, являющимися мгновенными. [26]
Определим полное кодовое дерево как конечное кодовое дерево, в котором из каждого промежуточного узла исходят D узлов следующего более высокого порядка. Как можно заметить из доказательства неравенства Крафта, для полного кодового дерева неравенство Крафта удовлетворяется с равенством. [27]
Первое строгое доказательство (4.2), по-видимому, было получено Макмиллаиом ( Me Millan ( 1956)), который опирался на свое обобщение неравенства Крафта ( ср. Неравенство (4.11) было доказано аналогично Краузе ( Krause ( 1962)), отправлявшимся от следствия 4.5. Мы сформулировали утверждения о нижних границах при несколько более слабых условиях, чем обычно. Доказательства представляют собой обработку оригинальных эвристических рассуждений Шеннона н следуют работам Csiszar-Katona-Tusnady ( 1969) и Csiszar ( 1969); мы предпочли этот теоретико-информационный подход несколько искусственным доказательствам, упомянутым выше. В теореме 4.6 используется построение последнего автора, обобщенное на случай символов неравной стоимости. [28]
Если Р ( а /) 3 - й для всех k, то неравенство Крафта удовлетворяется с равенством. Вместе с тем, если число сообщений является четным, то кодовое дерево не является полным и при этом еще одно кодовое слово могло бы быть добавлено без нарушения неравенства Крафта. [29]
Обратно, при заданном бесконечном множестве длин, которые удовлетворяют неравенству Крафта, можно использовать построение, выполненное в теореме 3.2.1, чтобы построить код, обладающий свойством префикса. Здесь необходимо сделать два замечания. Первое состоит в том, что так как неравенство Крафта удовлетворяется, то существует конечное множество слов каждой длины щ и поэтому длины могут быть упорядочены; второе состоит в том, что следует начинать ( методически) с полного бесконечного дерева. [30]
Страницы: 1 2 3