Д. Если полученное дерево не обладает минимальной избыточностью, то и порождающее его дерево не обладает минимальной избыточностью. Пришли к противоречию. Ч.Т.Д

Д. Пусть произвольное слово А в алфавите А закодировано словом В с использованием схемы Σ(), для которой не выполняется свойство префикса, а для (Σ) это свойство выполняется. Выделим элементарные коды в соответствии со схемой Σ(), заменим их кодами схемы (Σ). Согласно теореме 4.1 полученное слово имеет единственную расшифровку. Следовательно, единственную расшифровку имеет слово В. Ч.Т.Д.

Т4.3. Алфавитное кодирование со схемой кодирования Σ не обладает свойством однозначности, если и только если граф G(Σ) содержит ориентированный цикл, проходящий через вершину L.

Доказательство приведено в [1]

Т4.7. Для всякого кода с минимальной избыточностью сущ-ет насыщенное дерево, его представляющее.

Д. Преобразования 1, 2 позволяют любое кодовое дерево, в том числе и кодовое дерево, обладающее минимальной избыточностью, привести к насыщенному дереву, не увеличивая при этом избыточности кодового дерева. Ч.Т.Д..

Т4.8. Для кода с минимальной избыточностью существует приведенное насыщенное дерево.

Доказательство следует из определения приведенного насыщенного дерева

Т4.9. Операция редукции порождает новое кодовое дерево с минимальной избыточностью.

Д. Если полученное дерево не обладает минимальной избыточностью, то и порождающее его дерево не обладает минимальной избыточностью. Пришли к противоречию. Ч.Т.Д.

Т5.1. Множество S не выполнимо, если и только если не выполнимы два множества: È и È .

Доказательство следует из того факта, что рассматриваемые множества получаются из S фиксированием значения p (p = и, p = л соответственно).

Т4.4 (неравенство МакМилана). Если кодирование со схемой Σ обладает свойством однозначности, то выполняется соотношение £ 1.

Д. Рассмотрим всевозможные слова в алфавите А, имеющие длину n. Представим их выражением:

( +…+ ) . (1)

Произвольное слово длины n в алфавите А можно представить в виде , ,…, . Здесь принадлежит первой из n скобок, – второй и т.д. Имея это в виду, запишем соотношение

( +…+ ) = . (2)

Сопоставим рассматриваемым словам коды в алфавите В. Коды получаются заменой симв. ,…, элементарными кодами ,…, соответственно. Имеем

( +…+ ) = . (3)

В силу однозначности кодирования, если (,…, ) ¹ (,…, ), то ¹ , то есть разным словам в алфавите А соответствуют разн. слова в алфавите В.

Соотношению (3) соответствует тождество

= .(4)

Слагаемым правой части, имеющим одинаковые знаменатели, сопоставляются слова одинаковой длины t, t = +…+ . Пусть ν(n, t) – число слов из (3), имеющих длину t. Пусть l = . Тогда

= . (5)

Из однозначности кодирования следует ν(n, t) £ . (6)

Действительно, есть число всевозможных слов длины t в алфавите В. Поскольку в (3) все рассматриваемые коды слов длины n в алфавите А различны, то различны и их подмножества – коды одной и той же длины. Следовательно, соотношение (6) выполняется.

Далее £ nl. Тогда £ .

Это неравенство справедливо для любого n, так как его левая часть не зависит от n. Перейдя к пределу при n ®¥, получим неравенство МакМилана

£ 1. Ч.Т.Д.

Теорема 5.2. Пусть , – дизъюнкты КНФ, представленной множеством S, а l – литера. Если l из , а Ø l из , то дизъюнкт r =( / {l}) Ú ( / {Ø l }) есть логическое следствие множества S дизъюнктов. Доказательство следует из введенного ранее определения резольвенты.

С. КНФ, представленные множествами S и S È r, эквивалентны.

Т4.5. Если алфавитное кодирование, заданное схемой Σ, однозначно, Σ:

, … ,

то существует алфавитное кодирование, задаваемое схемой :

, … ,

обладающее свойством префикса, причем для элементар. кодов ,…, выполняются равенства

l () = l (), … l () = l ().

Д. Пусть £…£ . Воспользуемся неравенством МакМилана £ 1.

Разобьем числа ,…, , представляющ. длины элементарных кодов, на классы равной длины. Пусть μ – число классов 1 £ μ £ r; ,…, – длины элементов классов; ,…, – мощности классов. Перепишем неравенство МакМилана с учетом введенных обозначений:

£ 1.

Это неравенство порождает серию вспомогательных неравенств:

£ 1 или £ ,

+ £ 1 или £ – ,

…

+ +…+ £ 1 или £ – – –…– .

Рассмотрим слова в алфавите B, имеющие длину . Так как £ , то можно выбрать из них слов длины . Обозначим выбранные слова через ,…, . Они представляют элементарные коды схемы кодирования . Исключим из рассмотрения в дальнейшем слова, начинающиеся с ,…, . Выберем слова в алфавите В, имеющие длину и не начинающиеся со слов ,…, . Число таких слов в алфавите В определяется выражением

– .Так как £ – , то имеется возможность выбрать нужных нам слов. Обозначим их через ,…, . Они также представл. Элементарн коды схемы кодирования

Исключим в дальнейшем слова, начинающиеся с уже включенных в схему элементарных кодов. В конце концов мы получим все элементарные коды ,…, схемы . Из построения кодов следует:

l () = l (),…, l () = l (). Ч.Т.Д.

Т4.6. Для кода с минимальной избыточностью из условия < следует, что ³ .

Д. Предпол противное: < и < Тогда, если в схеме Σ:

…	…
…	…
…	…

поменять местами коды , , то получим схему :

…	…
…	…
…	…

имеющую меньшую избыточность , чем . В самом деле,

– = ( + ) – ( + ) =

= ( – )( – ) > 0.

Это противоречит условию минимальной избыточности схемы кодирования Σ. Ч.Т.Д.

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

Date: 2015-09-05; view: 565; Нарушение авторских прав