ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 14.02.2021
Просмотров: 138
Скачиваний: 1
Кодирование
информации
Пусть
объектом
кодирования
являются
тексты
,
записанные
на
некотором
(
естественном
или
искусственном
)
языке
,
причем
число
букв
в
алфавите
этого
языка
,
включая
(
если
есть
такая
необходимость
)
некоторые
знаки
препинания
,
знак
пробела
и
т
.
п
.,
равно
п
.
Пусть
далее
,
l
-
наименьшее
натуральное
число
,
удовлетворяющее
условию
n
l
log
2
≥
.
Тогда
можно
пользоваться
простейшим
из
различных
методов
побуквенного
кодирования
,
сводящимся
к
установлению
взаимно
однозначного
соответствия
между
различными
буквами
исходного
текста
и
различными
кодовыми
наборами
двоичных
символов
фиксированной
длины
,
равной
l
.
Например
,
если
речь
идет
о
текстах
,
записанных
на
русском
языке
,
где
число
букв
алфавита
,
включая
знак
пробела
,
n
= 34,
то
,
поскольку
имеет
место
неравенство
5 <
log
2
34 < 6,
можно
осуществить
побуквенное
кодирование
,
установив
следующее
соответствие
:
Буква
русского
языка
Шестисимвольный
кодовый
набор
Десятичная
запись
(
пробел
)
000000
0
а
000001
1
б
000010
2
.
………
.
л
001101
13
.
……….
.
я
100001
33
.
……….
.
.
111111
63
Декодирование
при
этом
осуществляется
очень
просто
:
последовательность
двоичных
символов
-
закодированный
текст
-
делится
на
блоки
из
шести
символов
и
каждый
блок
заменяется
соответствующей
буквой
алфавита
исходного
текста
.
Невооруженным
глазом
видно
,
что
,
будучи
очень
привлекательным
по
своей
простоте
,
рассмотренный
метод
кодирования
грешит
определенной
"
расточительностью
" (
избыточностью
).
Об
этом
свидетельствует
хотя
бы
то
обстоятельство
,
что
шестью
двоичными
символами
мы
смогли
бы
выразить
не
п
=
34,
а
целых
п
=
2
6
= 64
букв
алфавита
.
Чтобы
улучшить
положение
,
можно
было
,
например
,
пойти
на
некоторую
уступку
,
а
именно
,
согласиться
с
тем
,
чтобы
при
кодировании
и
декодировании
текстов
пары
букв
"
е
"-"
ё
"
и
"
ь
"-"
ъ
"
оказались
"
неразличимыми
".
Ведь
люди
,
владеющие
русским
языком
,
все
равно
смогли
бы
восстановить
это
различие
при
работе
с
уже
декодированным
текстом
.
При
наличии
такого
согласия
число
букв
в
алфавите
русского
языка
(
включая
знак
пробела
)
оказалось
бы
равным
п
=
32,
и
поэтому
можно
было
бы
обойтись
кодовыми
наборами
постоянной
длины
,
равной
l
=
log
2
32 = 5.
Тем
самым
,
из
каждых
шести
двоичных
символов
один
символ
можно
было
сэкономить
.
Из
этого
примера
легко
сделать
вывод
,
что
при
побуквенном
кодировании
букв
исходного
текста
кодовыми
наборами
постоянной
длины
наиболее
компактное
(
экономное
)
кодирование
удается
осуществить
тогда
,
когда
число
букв
в
алфавите
можно
представить
как
целую
степень
двойки
:
n
= 2
l
(
l
=
1,2,
...,).
(2.1)
Нарушение
этого
условия
при
указанном
методе
кодирования
непременно
приводит
к
некоторой
избыточности
.
Возникает
вопрос
,
а
имеются
ли
резервы
для
дальнейшего
сокращения
среднего
числа
двоичных
символов
,
отводимых
под
одну
букву
?
Оказывается
,
что
такие
резервы
имеются
,
и
даже
тогда
,
когда
п
удовлетворяет
условию
(2.1),
возможны
варианты
,
когда
кодирование
можно
осуществить
таким
образом
,
чтобы
среднее
число
двоичных
символов
,
отводимых
под
одну
букву
,
оказалось
меньше
l
=
log
2
п
.
Пусть
алфавит
исходного
текста
состоит
из
восьми
букв
А
,
В
,
С
, D,
Е
, F, G,
Н
.
Поскольку
п
= 8
=
2
3
,
т
.
е
.
l
=
1
о
g
2
n
=
3
,
то
при
рассмотренном
только
что
методе
кодирования
каждой
букве
ставился
бы
в
соответствие
кодовый
набор
постоянной
длины
,
равной
трем
.
Пусть
нам
известны
значения
вероятностей
того
,
что
наугад
взятая
буква
из
текстов
этого
языка
окажется
буквой
А
,
В
,
С
, D,
Е
, F, G
или
Н
:
р
(
А
) = 0,08
р
(
В
) = 0,44
р
(
С
) = 0,08
р
(D) = 0,08
р
(
Е
) = 0,08
р
(F) = 0,08
р
(G) = 0,08
р
(
Н
) = 0,08
С
учетом
неравновероятности
встречаемости
различных
букв
алфавита
представляется
естественным
отказаться
от
постоянства
длины
кодовых
наборов
и
стараться
осуществить
такое
кодирование
,
при
котором
наиболее
часто
встречающиеся
буквы
были
бы
закодированы
возможно
более
короткими
кодовыми
наборами
и
,
наоборот
,
наибольшую
длину
имели
бы
кодовые
наборы
,
соответствующие
наименее
часто
встречающимся
буквам
.
В
русле
этих
соображений
специалистами
были
разработаны
различные
методы
побуквенного
кодирования
.
В
связи
с
переходом
к
переменной
длине
кодовых
наборов
возникает
проблема
установления
границ
между
ними
при
декодировании
.
При
этом
крайне
нежелательно
,
чтобы
для
установления
границ
были
использованы
какие
-
либо
специальные
разделительные
символы
,
так
как
это
привело
бы
к
увеличению
средней
длины
кодовых
наборов
.
Коды
(
схемы
,
алгоритмы
кодирования
),
где
однозначность
декодирования
достигается
без
помощи
каких
-
либо
специальных
разделительных
символов
,
называются
кодами
без
запятой
.
Среди
них
наиболее
простыми
и
в
то
же
время
наиболее
популярными
являются
так
называемые
префиксные
коды
,
обладающие
тем
свойством
,
что
кодовый
набор
никакой
буквы
не
является
началом
(
префиксом
)
кодового
набора
другой
буквы
.
Пусть
п
-
число
букв
в
алфавите
,
n
k
—
число
букв
,
кодовые
наборы
которых
состоят
из
k
двоичных
символов
,
l
i
-
число
двоичных
символов
в
кодовом
наборе
i
-
й
буквы
алфавита
,
L =
max (
l
i
).
Тогда
,
очевидно
,
∑
=
=
L
k
n
n
k
1
,
а
для
произвольного
фиксированного
значения
k
имеет
место
2
k
k
n
≤
.
Если
же
нам
заданы
значения
n
n
n
k
1
2
1
,...,
,
−
,
то
,
очевидно
,
будет
иметь
место
неравенство
n
n
n
k
k
k
k
⋅
⋅
−
−
−
−
−
≤
1
1
1
2
2
2
...
т
.
е
.
2
2
1
k
j
k
j
k
n
j
≤
⋅
=
∑
−
или
,
после
деления
обеих
частей
неравенства
на
2
k
,
1
2
1
≤
⋅
=
∑
−
n
j
j
k
j
Поскольку
выбор
значения
k
произвольный
,
то
примем
k = L.
и
тогда
будем
иметь
:
1
2
1
≤
⋅
=
∑
−
n
j
j
L
j
Отсюда
непосредственно
следует
1
2
1
≤
=
∑
−
n
i
l
i
(2.2)
Неравенство
(2.2)
называется
неравенством
Крафта
и
имеет
ключевое
значение
в
теории
кодирования
.
Хотя
вывод
этого
неравенства
мы
осуществили
применительно
к
двоичному
префиксному
коду
,
оно
верно
также
для
произвольного
(
не
обязательно
двоичного
и
не
обязательно
префиксного
)
кода
без
запятой
.
Неравенство
Крафта
,
собственно
,
и
лимитирует
наше
желание
оперировать
как
можно
меньшими
значениями
l
i
.
Пусть
,
например
,
n
= 10
и
уже
известны
значения
l
1
= 2,
l
2
=
l
3
=...=
l
6
= 3.
Тогда
.
очевидно
,
значения
l
7
÷
l
10
должны
удовлетворить
неравенству
8
1
2
5
2
1
2
3
2
10
7
=
⋅
−
−
≤
−
−
=
−
∑
i
i
l
Пусть
,
например
,
мы
хотим
,
чтобы
имело
место
l
7
=l
8
=l
9
=l
10
=l
.
Тогда
получим
,
что
значение
l
должно
удовлетворить
неравенству
8
/
1
2
4
≤
⋅
−
l
,
т
.
е
.
оно
не
может
быть
меньше
пяти
.
Префиксный
код
называется
полным
,
если
добавление
к
нему
любого
нового
кодового
набора
нарушает
свойство
префиксности
.
Пусть
,
например
,
буквам
А
,
В
и
С
поставлены
в
соответствии
кодовые
наборы
00, 01
и
1.
Тогда
очевидно
,
что
любая
попытка
закодировать
еще
хоть
одну
букву
привела
бы
к
нарушению
свойства
префиксности
.
Значит
,
код
00, 01, 1
является
полным
.
Если
же
буквам
А
.
В
и
С
были
поставлены
в
соответствие
кодовые
наборы
00, 01
и
10,
то
через
ветвь
11...
мы
смогли
бы
,
не
нарушая
свойство
префиксности
,
закодировать
сколько
угодно
новых
букв
.
Мы
также
смогли
бы
без
нарушения
свойства
префиксности
через
ветвь
01...
закодировать
сколько
угодно
новых
букв
,
если
бы
буквам
А
,
В
и
С
были
поставлены
в
соответствие
кодовые
наборы
000, 001
и
1.
Значит
,
коды
00,
01, 10
и
000, 001, 1
являются
неполными
.
Для
полных
префиксных
кодов
и
только
для
них
неравенство
Крафта
превращается
в
равенство
.
Естественно
,
что
на
практике
наибольший
интерес
представляют
полные
коды
,
так
как
при
прочих
равных
условиях
средняя
длина
кодовых
наборов
у
полных
кодов
получается
меньше
,
чем
у
неполных
.
Перейдем
к
рассмотрению
двух
полных
префиксных
кодов
,
представляющих
большой
практический
интерес
.