3.4. Неравенство Крафта [2]

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

Теорема. Неравенство

является необходимым и достаточным условием существования кодовых слов, соответствующих концевым узлам дерева с длинами, равными

Доказательство. Покажем сначала, что соотношение (3.4) необходимо, С этой целью заметим, что так как кодовый алфавит состоит из символов, то из каждого узла дерева исходит не более ветвей. Отсюда следует, что может быть не более узлов порядка это максимальное число получается тогда, когда ветвей разветвляются из каждого узла порядка, меньшего чем С другой стороны, наличие концевого

узла порядка (не большего, чем ) исключает возможных узлов порядка Отсюда мы заключаем, что длины кодовых слов, совпадающие с порядками концевых узлов, должны удовлетворять неравенству

для всех целых не меньших наибольшего Деля это неравенство на получаем

и необходимость условия теоремы доказана.

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

Предположим далее, что нам удалось построить дерево, содержащее все заданные концевые узлы порядка, меньшего и что дерево должно содержать концевых узлов порядка Согласно условию [см. выражение (3.4)],

где число концевых узлов порядка, меньшего чем Умножая это неравенство на и перенеся две суммы в правую часть, получаем

С другой стороны, число доступных узлов порядка равно минус число узлов, исключаемых из-за наличия концевых узлов меньшего порядка, т. е.

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

справедливо для всех целых то отсюда следует, что дерево с требуемыми концевыми узлами всегда может быть построено шаг за шагом, если только для порядков узлов выполнено неравенство (3.4). Ч.Т.Д.

Неравенство (3.4) является необходимым и достаточным условием существования кодового дерева, содержащего концевых узлов порядка Дерево с этими концевыми узлами может иметь или не иметь еще добавочные концевые узлы. Заданное множество концевых узлов называется полным, если существует дерево, имеющее эти концевые узлы и не имеющее никаких других концевых узлов, т. е., другими словами, если заданное множество узлов целиком заполняет дерево.

Теорема. Равенство

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

Доказательство. Из рассуждений, проведенных при выводе (3.5), немедленно следует необходимость (3.11). В самом деле, если заданные концевые узлы образуют полное множество, то они должны исключить все узлы порядка В этом случае в (3.5) имеет место знак равенства. Разделив затем это равенство на получаем равенство (3.11).

Достаточность условия (3.11) может быть доказана следующим образом. Поскольку любое множество концевых узлов, удовлетворяющее (3.11), также удовлетворяет и (3.4), то существует по крайней мере одно дерево с заданными концевыми узлами. Предположим, что это дерево имеет, кроме заданных, один или более добавочных концевых узлов. Если бы это было так, то мы могли бы, не нарушая неравенства (3.4), добавить в сумму в левой части (3.11) члены, соответствующие этим добавочным концевым узлам. Очевидно, это невозможно. Отсюда следует, что дерево с концевыми узлами, удовлетворяющими условию (3.11), не может иметь дополнительных узлов. Ч. Т. Д.

Теорема. Равенство

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

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

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

Вообще

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

где наивысший порядок концевого узла из заданного множества. Так как выражение в квадратных скобках в правой части равенства (3.16) есть сумма целых чисел, то число доступных концевых узлов должно удовлетворять равенству (3.12).

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

Так как на не накладываются никакие ограничения, то всегда можно выбрать так чтобы удовлетворить

поставленным требованиям. Как видно, целое число на единицу больше наибольшего для которого . Ч. Т. Д.

Важно заметить, что для равенство (3.12) удовлетворяется при любом целом Другими словами, полные двоичные деревья можно построить для произвольного числа концевых узлов. Это не верно, когда отлично от 2.