Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 13 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

a
r
– B
r
Если отображение
S(A) → S(B) – взаимно однозначное => декодирование
однозначно. Говорят, что алфавит кодирования является взаимно однозначным.
Вопрос – как по схеме определить, обладает алфавитное кодирование
свойством взаимной однозначности или нет?
Сначала рассмотрим простой достаточный признак взаимной однознач-
ности.
Определение. Пусть слово В=В′B′′ => слово B′ называется началом или
префиксом слова В, В′′ – концом слова В. При этом пустое слово λ и само сло-
во В считаются началом и концами слова В.
Все начала и концы, отличные от него самого, называются собственными.
Определение. Схема ∑ обладает свойством префикса, если для любых i и
j (i≥1, r≥j, i≠j) слово В
i
не является префиксом слова B
j.
Теорема. Если схема ∑ обладает свойством префикса, то алфавитное ко-
дирование будет взаимно однозначным.
Доказательство: т.к. ∑ обладает свойством префикса => все элементарные
коды попарно различны В
i
≠B
j
при i≠j
Пусть некоторое слово В∈S(B) допускает две расшифровки (два разбие-
ния на элементные коды)
В=B
i1
…B
is
В=B
j1
…B
jt
Пусть B
i1
=B
j1
, …, B
in-1
=B
jn-1
, B
i1
≠B
j1
. В таком случае одно из слов B
in
, B
jn
явля-
ется префиксом другого => противоречие.
Пусть В=B
i1
…B
in
– слово из S(B)
Обозначим B
~
= b
i1
…b
iL
∑
~
:а
1
– B
~
1
…
a
r
–B
~
r
∑
~
- обладает свойством префикса => по последней теореме алфавитное коди-
рование, задаваемое ∑
~
будет взаимнооднозначным.
Теорема. Если либо схема ∑, либо схема ∑
~
обладает свойством
префикса, то алфавитное кодирование, задаваемое ∑( ∑
~
), будет взаимно одно-
значным.
Пусть B
i
= ''...'
1
β
β
ω
ii
BB (3.3)
B
i
– элементарный код
ω
ii
BB ...
1
- элементы кода
нетривиальное разложение элементарного кода B
i
, т.е. разложение B
i
= B
i
(β′=β′′=λ), причем β′ β′′ отличны от элементарных кодов.
Соотношение (3.3) означает, что в элементарном коде B
i
можно отобра-
зить некоторое начало
β′ и некий конец β′′ так, что оставшаяся часть разбивает-
ся на элементарные коды.
Для каждого B
i
число разложений вида (3.3) конечно.
16
        ar – Br
        Если отображение S(A) → S(B) – взаимно однозначное => декодирование
однозначно. Говорят, что алфавит кодирования является взаимно однозначным.
        Вопрос – как по схеме определить, обладает алфавитное кодирование
свойством взаимной однозначности или нет?
        Сначала рассмотрим простой достаточный признак взаимной однознач-
ности.
        Определение. Пусть слово В=В′B′′ => слово B′ называется началом или
префиксом слова В, В′′ – концом слова В. При этом пустое слово λ и само сло-
во В считаются началом и концами слова В.
        Все начала и концы, отличные от него самого, называются собственными.
        Определение. Схема ∑ обладает свойством префикса, если для любых i и
j (i≥1, r≥j, i≠j) слово Вi не является префиксом слова Bj.
        Теорема. Если схема ∑ обладает свойством префикса, то алфавитное ко-
дирование будет взаимно однозначным.
        Доказательство: т.к. ∑ обладает свойством префикса => все элементарные
коды попарно различны Вi≠Bj при i≠j
        Пусть некоторое слово В∈S(B) допускает две расшифровки (два разбие-
ния на элементные коды)
        В=Bi1…Bis
        В=Bj1…Bjt
Пусть Bi1=Bj1, …, Bin-1=Bjn-1, Bi1≠Bj1 . В таком случае одно из слов Bin , Bjn явля-
ется префиксом другого => противоречие.
Пусть В=Bi1…Bin – слово из S(B)
                 ~
Обозначим B = bi1…biL
 ~        ~
∑ :а1 – B 1
          …
         ~
    ar – B r
 ~
∑ - обладает свойством префикса => по последней теореме алфавитное коди-
                          ~
рование, задаваемое ∑ будет взаимнооднозначным.
                                                            ~
        Теорема. Если либо схема ∑, либо схема ∑ обладает свойством
                                                           ~
префикса, то алфавитное кодирование, задаваемое ∑( ∑ ), будет взаимно одно-
значным.
        Пусть Bi= β ' Bi1...Biω β ' '                                      (3.3)
       Bi – элементарный код
       Bi1 ...Biω - элементы кода
нетривиальное разложение элементарного кода Bi, т.е. разложение Bi= Bi
(β′=β′′=λ), причем β′ β′′ отличны от элементарных кодов.
        Соотношение (3.3) означает, что в элементарном коде Bi можно отобра-
зить некоторое начало β′ и некий конец β′′ так, что оставшаяся часть разбивает-
ся на элементарные коды.
        Для каждого Bi число разложений вида (3.3) конечно.

16

Страницы