Неравенство - крафт
Cтраница 1
 |
Конструирование двоичного дерева, встроенного в полное дерево. [1] |
Неравенство Крафта можно использовать д доказательства следующей теоремы кодирования источника ( без шумов), котор применяется к кодам, удовлетворяющим префиксному условию. [2]
Неравенство Крафта легко доказать с помощью дерева декодирования, существование которого следует из возможности мгновенного декодирования. [3]
 |
Деревья декодирования. [4] |
Неравенство Крафта применимо к мгновенным кодам, которые являются частным случаем однозначно декодируемых кодов. Макмиллан показал, что такое же неравенство справедливо для однозначно декодируемых кодов. Основная идея доказательства необходимости состоит в том, что число, превышающее 1, очень быстро возрастает с увеличением степени, в которую оно возводится. Доказательство достаточности следует из того, что его можно провести для мгновенных кодов, являющихся частными случаями однозначно декодируемых кодов. [5]
Неравенство Крафта, выполненное для кодирования Шеннона - Фано, гарантирует, что кодовых слов хватит для построения мгновенного кода. Такое упорядоченное сопоставление сразу дает дерево декодирования. [6]
Выполнение неравенства Крафта обеспечивает существование нужного набора концевых узлов. [7]
Рассматриваемое ниже неравенство Крафта дает условие существования мгновенных кодов; оно показывает, для каких длин кодовых слов существует мгновенный код, но не показывает, как его строить. [8]
Покажите, что неравенство Крафта выполняется для такого кода. [9]
Из (2.18) и неравенства Крафта вытекает неотрицательность избыточности. [10]
Неравенство (2.2) называется неравенством Крафта и имеет ключевое значение в теории кодирования. Хотя вывод этого неравенства мы осуществили применительно к двоичному префиксному коду, оно верно также для произвольного ( не обязательно двоичного и не обязательно префиксного) кода без запятой. [11]
Для однозначно дешифруемых кодов неравенство Крафта выполняется. [12]
Если код однозначно декодируем, неравенство Крафта (3.2.3) удовлетворяется. [13]
Последнее неравенство в (3.3.6) следует из неравенства Крафта (3.2.3), которое справедливо для любого однозначно декодируемого кода. [14]
Таким образом, новый набор чисел удовлетворяет неравенству Крафта и может служить кодовым. Стоимость кода в результате операции переброски не меняется. Повторяя эту операцию, мы из любого кода получаем новый, у которого длины кодовых слов отличаются разве лишь на единицу. [15]
Страницы: 1 2 3