Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Условие существования префиксного кода, неравенство и теорема Крафта.Содержание книги
Поиск на нашем сайте
Префиксным кодом называется алфавитный код, в котором ни одно из кодовых слов не является префиксом никакого другого кодового слова. Любой префиксный код является разделимым. В теории кодирования, неравенство Крафта — Макмиллана даёт необходимое и достаточное условие существования разделимых и префиксных кодов, обладающих заданным набором длин кодовых слов.
Теорема (необходимые условия). Пусть - префиксный двоичный код с длинами кодовых слов . Тогда выполняется неравенство Крафта
Доказательство. Рассмотрим, сколько слов длины может быть в префиксном коде. Максимальное число таких слов равно . В этом случае все кодовых слова имеют длину . Для каждого кодового слова длины имеется слов длины , для которых данное слово является префиксом и по этой причине не является кодовым. Это следует из структуры словарного дерева (см. рис. 6.3). Множества и слов длины , для которых кодовые слова и являются префиксами, не пересекаются, так как в противном случае более короткое из этих слов было бы префиксом более длинного. Значит, если в префиксном коде имеется слов длины слов длины слов длины 1, то число слов длины удовлетворяет неравенству
Это неравенство верно для любого , в том числе и для , равного максимальной длине кодовых слов. После деления на обеих частей неравенства (6.4) его можно преобразовать к виду
Слагаемое вида , представляющее в неравенстве (6.5) кодовых слов длины , можно записать в виде суммы С учетом такого представления неравенство (6.5) можно переписать следующим образом: где - общее число слов префиксного кода. Теорема доказана. Выполнение неравенства Крафта доказано для префиксного кода. Однако в 1956 году Мак-Милан доказал более общую теорему, согласно которой неравенство Крафта выполняется и для любого однозначно декодируемого кода. Доказательство теоремы изложено в[29], [31]. Можно также доказать, что если префиксный код полный, то в нестрогом неравенстве (6.3) будет выполняться равенство. Теорема (достаточные условия). Если положительные целые числа удовлетворяют неравенству Крафта то существует префиксный код с длинами кодовых слов Доказательство. Если среди чисел имеется ровно чисел, равных , то неравенство Крафта можно записать в виде где - максимальное из данных чисел. Из справедливости этого неравенства следует, что верны неравенства (6.5) для всех , а следовательно, и неравенство (6.4). Для построения нужного префиксного кода должна быть возможность подходящим образом выбрать слов длины 1, слов длины 2, вообще слов длины или, иными словами, вершин кодового дерева на первом, - на втором, - на -м ярусе. Из неравенства (6.4) при получаем , т. е. требуемое число не превосходит общего числа вершин первого яруса. Значит, на этом ярусе можно выбрать какие-то вершин в качестве концевых ( равно 0, 1 или 2). Если это сделано, то из общего числа вершин второго яруса (их ) для построения кода можно использовать лишь . Однако и этого числа вершин хватит, так как из неравенства (6.4) при вытекает Аналогично, при имеем неравенство: Правая часть его вновь совпадает с допустимым для построения префиксного кода числом вершин третьего яруса, если на первых двух ярусах уже выбраны и кодовых вершин. Значит, снова можно выбрать кодовых вершин на третьем ярусе. Продолжая этот процесс вплоть до , мы и получим требуемый код. Теорема доказана. Докажем, что если для длин кодовых слов выполняется равен - равенство ,то код является полным. Предположим противное, то есть, что код не полный. Тогда к нему можно добавить, по крайней мере, одно кодовое слово (длины ) и получить новый префиксный код, для которого, с одной стороны, , а с другой стороны, в силу теоремы Крафта, Полученное противоречие доказывает утверждение. Теоремы Крафта доказаны для случая, когда рассматриваются коды в алфавите . Если кодовый алфавит содержит символов, то аналогичным образом можно доказать, что необходимым и достаточным условием для существования префиксного кода с длинами слов является выполнение неравенства Оказывается, этому неравенству обязаны удовлетворять и длины кодовых слов произвольного однозначно декодируемого кода. Поэтому, если существует однозначно декодируемый код с длинами слов , то существует и префиксный код с теми же длинами слов.
|
||||||||||
Последнее изменение этой страницы: 2016-08-14; просмотров: 947; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.222.110.231 (0.006 с.) |