Теория информации

p i k j   2 - вес j  кода j=1,М , где М - число допустимых кодов, k - уровень дерева. Для построения префиксных кодов используется двоичное дерево: Дерево может иметь и более двух ветвей D>2 . Тогда вес j  кода будет равен j k j D p   , где D - основание системы счисления. 1.3.3. Основные теоремы кодирования. Неравенство Крафта Теорема 1. Неравенство Крафта. Неравенство     M j k j D 1 1 является необходимым и достаточным условием существования кодовых слов, соответствующих концевым узлам дерева с длинами, равными k j . Пример 1.18. Для существования двоичного разделимого кода, содержащего N кодовых слов, состоящих из символов 0 и 1, с длинами n 1 , n 2 , …, n N , необходимо и достаточно, чтобы выполнялось неравенство Крафта: 1 2 1     N i n i .