3.3. Кодовое дерево для множества кодовых слов
Весьма наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между кодовыми словами, т. е. сообщениями, и концевыми узлами дерева. Дерево, соответствующее множеству двоичных кодовых слов рис. 3.2, изображено на рис. 3.3. Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между нулем и единицей в качестве первого символа кодового слова — левая ветвь соответствует 0, а правая ветвь 1.
Рис. 3.3. Дерево, соответствующее множеству двоичных кодовых слов, изображенному на рис. 3.2.
Две ветви, идущие от каждого из узлов первого порядка, соответствуют второму символу кодовых слов, левая ветвь опять-таки обозначена 0, а правая 1. То же самое правило применяется к узлам более высокого порядка. Ясно, что последовательные символы каждого кодового слова определяют необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.
Так же как и концевым узлам, кодовые слова формально могут быть приписаны промежуточным узлам. Например, двум промежуточным узлам второго порядка на рис. 3.3 можно приписать кодовые слова 10 и 11, т. е. первые два символа кодовых слов, соответствующих концевым узлам, порождаемым этими промежуточными узлами. Однако кодовые слова, соответствующие промежуточным узлам, не могут быть использованы для представления сообщений; сообщения могут быть сопоставлены только концевым узлам. Это объясняется тем, что если рассматривать кодовое слово как совокупность указаний для достижения узла, соответствующего некоторому сообщению, то
эти указания должны были бы содержать еще команду «остановимся здесь», если бы узел был промежуточным. Таким образом, в промежуточном узле были бы возможны три различных указания, а именно «поверни налево» (0), «поверни направо» (1) и «остановись здесь». Другими словами, в такой точке мы должны были бы использовать троичный алфавит, что противоречит сделанным предположениям.
Требование, чтобы только концевые узлы сопоставлялись сообщениям, эквивалентно требованию, чтобы ни одно из кодовых слов не совпало с началом (префиксом) какого-либо более длинного кодового слова. Это условие автоматически удовлетворяется для любого множества кодовых слов, построенных путем последовательного подразбиения ансамбля сообщений, как это сделано в предыдущем разделе. Необходимо также заметить, что если бы это условие не удовлетворялось, то при непрерывной передаче сообщений было бы невозможно, вообще говоря, однозначно разбить последовательность символов на последовательные сообщения.
