ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 9359
Скачиваний: 24
86
●
логико-комбинаторное описание, например, S задано по-
рождающей формальной грамматикой.
8.1
Алфавитное
кодирование
Кодирование F может сопоставлять код всему сообщению
из множества S как единому целому или же строить код сообще-
ния из кодов его частей. Элементарной частью сообщения явля-
ется одна буква алфавита
А
. Этот простейший случай рассматри-
вается в этом и следующих двух разделах.
Префикс и постфикс слова
Пусть задано конечное множество А = {a
1
,…, a
n
}, которое
называется
алфавитом
. Элементы алфавита называются
буквами
.
Последовательность букв называется
словом
(в данном алфави-
те). Множество слов в алфавите
А
обозначается
А
*. Если слово
α = a
1
,…, a
k
∈
А
*, то количество букв в слове называется
длиной
слова: |
α| =|a
1
…a
k
| = k.
Пустое
слово обозначается
Λ: Λ ∈
А
*, |
Λ| = 0, Λ ∉
А
.
Если
α= α
1
α
2
, то
α
1
называется
началом
, или
префиксом
,
слова
α,
а
α
2
–
окончанием
, или
постфиксом
, слова
α. Если при
этом
α
1
≠ Λ (соответственно, α
2
≠ Λ), то α
1
(соответственно,
α
2
)
называется
собственным
началом
(соответственно,
собственным
окончанием
) слова
α.
Таблица кодов
Алфавитное
(или
побуквенное
) кодирование задается
схемой
(или
таблицей
кодов
)
σ
.
σ
:=< a
1
→β
1
, …, a
n
→β
n
>, a
i
∈ A,
β
i
∈ B*.
Множество кодов букв V: ={
β
i
} называется множеством
элементарных
кодов
. Алфавитное кодирование пригодно для лю-
бого множества сообщений S:
F: A*
→B*, a
i1
… a
ik
=a
∈
A*, F(a): =
β
i1 …
β
ik
.
87
Пример
Рассмотрим алфавиты
А
: ={0,1,2,3,4,5,б,7,8,9}, B: ={0,1} и
схему
δ
: =(0
→ 0, 1→ 1, 2 → 10, 3 → 11, 4 → 100, 5 → 101, 6 → 110,
7
→ 111, 8 → 1000, 9 → 1001).
Эта схема однозначна, но кодирование не является взаимно
однозначным:
F
δ
(333) = 111111 = F
δ
(77),
а значит, невозможно декодирование. С другой стороны, схема
δ
: =(0
→ 0000, 1→ 0001, 2 → 0010, 3 → 0011, 4 → 0100, 5 →
0101, 6
→ 0110, 7 → 0111, 8 → 1000, 9 → 1001),
известная под названием «
двоично
-
десятичное
кодирова-
ние», допускает однозначное декодирование.
Разделимые схемы
Рассмотрим схему алфавитного кодирования
σ и различные
слова, составленные из элементарных кодов. Схема
σ называется
разделимой
, если
β
i1
…
β
ik
=
β
i1
…
β
ik
⇒
k = l&
∀
t
∈ 1..k i
t
= j
t
,
то есть любое слово, составленное из элементарных кодов, един-
ственным образом разлагается на элементарные коды. Алфавит-
ное кодирование с разделимой схемой допускает декодирование.
Если таблица кодов содержит одинаковые элементарные ко-
ды, то есть, если
∃ i,j i≠j & β
i
=
β
j
,
где
β
i
,
β
j
∈ V, то схема заведомо не является разделимой. Такие
схемы далее не рассматриваются, то есть
∀ i≠j β
i
,
β
j
∈ V
⇒
β
i
≠β
j
.
Префиксные схемы
Схема
σ называется
префиксной
, если элементарный код
одной буквы не является префиксом элементарного кода другой
буквы:
(
∀ i≠j β
i
,
β
j
∈ V)
⇒
(
∀ β ∈ B* β
i
≠β
j
β).
88
Префиксная
схема
является
разделимой
. Свойство быть
префиксной является достаточным, но не является необходимым
для разделимости схемы.
Пример.
Разделимая, но не префиксная схема:
А
= {a, b},
В
= {0,1},
δ = {а → О, b → 01}.
Неравенство Макмиллана
Чтобы схема алфавитного кодирования была разделимой,
необходимо, чтобы длины элементарных кодов удовлетворяли
определенному соотношению, известному как
неравенство
Мак
-
миллана
.
ТЕОРЕМА. Если
схема
n
i
i
i
a
1
=
→
=
β
σ
разделима
,
то
1
2
1
1
≤
∑
=
n
i
l
i
, где l
i
=|
β
i
|.
Неравенство Макмиллана является не только необходимым,
но и в некотором смысле достаточным условием разделимости
схемы алфавитного кодирования.
ТЕОРЕМА. Если
числа
l
1
, …, l
n
удовлетворяют
неравенству
1
2
1
1
≤
∑
=
n
i
l
i
,
то
существует
разделимая
схема
алфавитного
кодирования
n
i
i
i
a
1
=
→
=
β
σ
,
где
∀
i l
i
= |
β
i
|.
Пример
Азбука
Морзе
– это схема алфавитного кодирования
(
А
→01, B → 1000,
С
→ 1010, D → 100,Е → 0,F → 0010, G →
110, H
→ 0000, I → 00, J → 0111,
К
→ 101, L → 0100, M →ll, N→
10,
О
→ 111, P→ 0110, Q → 1101, R → 010, S → 000, T → 1, U →
001, V
→ 0001, W → 011, X → 1001, Y → 1011, Z → 1100),
где по историческим и техническим причинам 0 называется
точ
-
кой
и обозначается знаком «•», а 1 называется
тире
и обозначает-
ся знаком «–». Имеем:
89
1/4 + 1/16 + 1/16 + 1/8 + 1/2 + 1/16 + 1/8 + 1/16 + 1/4 + 1/16 +
1/8 + 1/16 + 1/4 + 1/4 + 1/8 + 1/16 + 1/16 + 1/8 + 1/8 + 1/2 + 1/8 + 1/16
+ 1/8 + 1/16 + 1/16 + 1/16 = 2/2 + 4/4 + 7/8 + 12/16 = 3 + 5/8 > 1.
Таким образом, неравенство Макмиллана для азбуки Морзе
не выполнено, и эта схема не является разделимой. На самом де-
ле в азбуке Морзе имеются дополнительные элементы – паузы
между буквами (и словами), которые позволяют декодировать
сообщения. Эти дополнительные элементы определены нефор-
мально, поэтому прием и передача сообщений с помощью азбуки
Морзе, особенно с высокой скоростью, является некоторым ис-
кусством, а не простой технической процедурой.
8.2
Кодирование
с
минимальной
избыточностью
Для практики важно, чтобы коды сообщений имели по воз-
можности наименьшую длину. Алфавитное кодирование пригод-
но для любых сообщений, то есть S =
А
*. Если больше про мно-
жество S ничего не известно, то точно сформулировать задачу
оптимизации затруднительно. Однако на практике часто доступ-
на дополнительная информация. Например, для текстов на есте-
ственных языках известно распределение вероятности появления
букв в сообщении. Использование такой информации позволяет
строго поставить и решить задачу построения оптимального ал-
фавитного кодирования.
Минимизация длины кода сообщения
Если задана разделимая схема алфавитного кодирования
n
i
i
i
a
1
=
→
=
β
σ
, то любая схема
n
i
i
i
a
1
'
'
=
→
=
β
σ
, где
n
'
,...,
'
1
β
β
является перестановкой
n
β
β
,...,
1
, также будет разделимой. Если
длины элементарных кодов равны, то перестановка элементар-
ных кодов в схеме не влияет на длину кода сообщения. Но если
длины элементарных кодов различны, то длина кода сообщения
зависит от состава букв в сообщении и от того, какие элементар-
ные коды каким буквам назначены. Если заданы конкретное со-
общение и конкретная схема кодирования, то нетрудно подобрать
90
такую перестановку элементарных кодов, при которой длина ко-
да сообщения будет минимальна.
Пусть k
1
,...,k
n
– количества вхождений букв a
1
,...,a
n
в сооб-
щение S, а l
1
,...,l
n
– длины элементарных кодов
β
1
,...,
β
n
, соответст-
венно. Тогда, если k
i
≤ k
j
и l
i
≥ l
j
, то k
i
l
i
+ k
j
l
j
≤
k
i
l
j
+ k
j
l
j
. Действи-
тельно, пусть k
j
= k + a, k
i
= k и l
j
= l, l
i
= l + b, где a, b
≥
0. Тогда
(k
i
l
j
+ k
j
l
i
) – (k
i
l
i
+ k
j
l
j
) = (kl + (k + a)(l + b)) – (k(l +b) + l(k + a)) =
= (kl + al + bk + ab+ kl) – (kl + al + kl + bk) = ab
≥ 0.
Отсюда вытекает алгоритм назначения элементарных кодов,
при котором длина кода конкретного сообщения S будет мини-
мальна: нужно отсортировать буквы в порядке убывания количе-
ства вхождений, элементарные коды отсортировать в порядке воз-
растания длины и назначить коды буквам в этом порядке. Этот
простой метод решает задачу минимизации длины кода только для
фиксированного сообщения S и фиксированной схемы
σ
.
Цена кодирования
Пусть заданы алфавит
А
= {a
1
,...,a
n
} и вероятности появле-
ния букв в сообщении
Р
= <p
1
,...,
р
п
> (p
i
– вероятность появления
буквы a
i
). He ограничивая общности, можно считать, что p
1
+…
+
р
п
= 1 и p
1
≥ … ≥ p
n
> 0 (то есть можно сразу исключить буквы,
которые не могут появиться в сообщении, и упорядочить буквы
по убыванию вероятности их появления).
Для каждой (разделимой) схемы
n
i
i
i
a
1
=
→
=
β
σ
алфавитно-
го кодирования математическое ожидание коэффициента увели-
чения длины сообщения при кодировании (обозначается 1
σ
) оп-
ределяется следующим образом:
( )
∑
=
=
n
i
i
i
l
p
P
l
1
:
σ
, где 1
i
:= |
β
i
|
и называется средней
ценой
(или
длиной
) кодирования
σ при рас-
пределении вероятностей Р.
Пример
Для разделимой схемы
А
= {
а
, b},
В
= {0,1},
δ = {
а
→ 0, b →
01} при распределении вероятностей <0.5, 0.5> цена кодирования