Теоремы кодирования неравнозначными символами для дискретных каналов без шума

Федеральное агентство связи 
 
Федеральное государственное бюджетное образовательное 
 учреждение высшего образования  
«Сибирский государственный университет телекоммуникаций и информатики»  
(СибГУТИ) 
 
 
 
В. К. Трофимов  
Т. В. Храмова  
 
 
ТЕОРЕМЫ КОДИРОВАНИЯ  
НЕРАВНОЗНАЧНЫМИ СИМВОЛАМИ 
ДЛЯ ДИСКРЕТНЫХ КАНАЛОВ БЕЗ ШУМА 
 
 
 
МОНОГРАФИЯ 
 
 
 
 
 
 
 
Новосибирск 
2016 

 
УДК 621.391 
 
Трофимов В. К., Храмова Т. В. 
Теоремы кодирования неравнозначными символами для дискретных каналов 
без шума. Монография.  – Изд-во СибГУТИ, Новосибирск, 2016. – 80с., илл. 
 
 
 
Рецензенты: д.т.н. А.Л. Резник, д.ф.м.н. Г.Г. Черных. 
 
 
 
 
Утверждено редакционно-издательским советом СибГУТИ  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
© «Сибирский государственный университет  
    телекоммуникаций и информатики» 
© Трофимов В.К., Храмова Т.В., 2016 г. 
 

 
Оглавление 
Предисловие 
Введение 
6 
Предварительные сведения 
8 
1. 
Канал передачи информации 
10 
1.1. Общая схема канала без шума 
10 
1.2. Понятие источника информации 
11 
1.3. Энтропия источника информации 
13 
1.4. Кодирование источника сообщений 
16 
1.5. Пропускная способность канала и избыточность кодирования  
информации 
18 
2. 
Некоторые методы кодирования известного источника равнозначными 
символами 
19 
2.1. Код Хаффмана 
19 
2.2. Арифметическое кодирование 
23 
2.3. Код Лемпела-Зива 
26 
3. 
Кодирование известного источника неравнозначными символами 
29 
3.1. Предварительные построения 
29 
3.2. Схема кодирования неравнозначными символами 
34 
3.3. Оценка стоимости кодирования известного источника неравнозначными 
символами 
41 
4. 
Универсальное кодирование бернуллиевских источников буквами 
кодового алфавита с неравными длительностями 
42 
4.1. Схема кодирования множества бернуллиевских источников буквами 
кодового алфавита с неравными длительностями 
43 
4.2. Верхняя оценка избыточности универсального кодирования множества 
бернуллиевских источников 
49 
4.3. Нижняя оценка избыточности универсального кодирования множества 
бернуллиевских источников 
50 

 
4.4. Асимптотика избыточности универсального кодирования множества 
бернуллиевских источников 
5. 
Универсальное кодирование марковских источников буквами кодового 
алфавита с неравными длительностями 
58 
5.1. Кодирование неравнозначными символами информации, порожденной 
неизвестным марковским источником 
58 
5.2. Верхняя оценка избыточности универсального кодирования марковских 
источников символами неравнозначных длительностей 
64 
5.3. Нижняя оценка избыточности универсального кодирования марковских 
источников неравнозначными символами 
65 
5.4. Асимптотика избыточности универсального кодирования марковских 
источников неравнозначными символам 
66 
6. 
Слабо универсальное кодирование стационарных источников  
символами с неравнозначными длительностями 
68 
7. 
Оптимальное универсальное кодирование объединения различных 
множеств источников символами неравной длительности 
69 
7.1. Адаптивное кодирование объединения различных множеств  
источников 
69 
7.2. Универсальное кодирование для объединения множеств марковских 
источников 
71 
 
Литература 
74 
 

 
Предисловие  
Вопросы сжатия информации возникают при решении многих задач. 
Например, сжатие информации позволяет в несколько раз уменьшить ее объем 
при передаче. Так, хорошо известные факсимильные аппараты при работе примерно в 3,5 – 4 раза уменьшают объем передаваемой информации. При факсимильной передаче больших текстов (таких, например, как газетные) удается 
уменьшить объем передаваемых данных до 10 раз. Отметим также широкое использование методов сжатия информации в криптографии. Можно считать, что 
первым алгоритмом, позволяющим сжать сообщение, явился известный код 
Морзе. В дальнейшем появились новые возможности передачи сообщений, такие как телефон, радио, телевидение, интернет. С их помощью передаются 
ограниченные потоки информации. Задача сжатия приобрела огромное значение, и для её решения  в различных случаях была создана наука, названная теорией информации.  
Теория информации излагается во многих книгах. В них нашли отражение универсальные коды, которые позволяют сжимать тексты различной природы, не требуя знания их точной закономерности. 
Проведем анализ между степенью сжатия и сложностью реализации этих 
алгоритмов. Все методы сжатия информации, описанные в литературе, как правило излагаются для случая, когда символы, используемые при передаче по каналам связи равнозначны. Если же эти символы не равнозначны, то в монографиях описаны методы сжатия информации, когда структура этой информации 
известна. К последним относятся работы К. Шеннона, И. Чиссара, Г. Катоны 
(G.  Katona).  
Изучению вопросов сжатия информации символами различной стоимости 
и посвящена настоящая монография. Книга может быть полезна для специалистов по теории информации, информатике, программированию, базам данных. 

 
Введение 
 
В условиях современной реальности мы постоянно сталкиваемся с лавинообразным потоком информации, которую необходимо обрабатывать, хранить 
и передавать. Передача информации по каналам связи  сопровождается ее 
предварительной обработкой с целью уменьшения объема информации, подлежащей передаче, защиты ее от искажения в процессе передачи, и т.д. Уменьшение объема передаваемой информации напрямую связано с увеличением скорости передачи, а также экономией процессорного времени, затрачиваемого на 
дальнейшую обработку. Задача уменьшения объема памяти, занимаемого информацией, частично решается за счет использования методов сжатия данных и 
кодирования дискретных источников. Следует отметить, что решение задач кодирования источников используется также в теории управления, при выявлении 
скрытой информации, при создании большемасштабных вычислительных систем, в криптографии.  
Теория информации, основанная в 1948 г. К. Шенноном,  служит для получения различных методов сжатия данных. Разработанные  К. Шенноном 
[61, 28], Р. Фано [22], Д. А. Хаффманом [27], И. Чисаром [25], Г. Катоной [46] 
алгоритмы кодирования дискретных источников существенно использовали 
статистику сообщений, что частично препятствовало их практическому применению.  
Вопросы кодирования источников с неизвестной статистикой впервые 
рассматривались в работах А.Н. Колмогорова [2] и Б.М. Фитингофа [23]. В случае неизвестной статистики источника кодирование называется  универсальным. Точная постановка задачи универсального кодирования принадлежит 
Р.Е. Кричевскому [3].  
Исследованию свойств универсального кодирования также посвящены 
работы Л.Д. Дэвиссона [37, 38], Т.Д. Линча [51, 52], Т. Ковера [36], Н. Фаллера 
[41], Р.Г. Галлагера [45], Д. Кнута [47],  Й.С. Виттера [64], Б.Я. Рябко, 
А. Н. Фионова [13-17, 58, 59], М. Борроуза и Д. Виллера [35], А. Лемпела, 

 
Я. Зива [67, 68], Й. Риссайнена [55-57], Ф. Уиллемса, Ю.М. Штарькова и 
Ч. Чокенса [31, 32, 65], В. Ф. Бабкина [62], В. К. Трофимова [19-21, 49, 50], 
С. Савари [60], С. Верду [63], В.Н. Потапова [9-12]. Последним двум авторам 
принадлежат подробные обзорные работы.  
  

 
Предварительные сведения  
 
Ниже приведены основные понятия, используемые в данной работе. 
Рассмотрим источник сообщений , генерирующий последовательность 
из букв некоторого конечного алфавита 
1
2
{ ,
,...,
}
k
X
x x
x

. Последовательность 
должна быть закодирована и передана по каналу связи.  Для решения нашей задачи оптимального кодирования разобьем исходящую последовательность букв 
источника на блоки (слова) фиксированной длины N .  
Процедура кодирования источника заключается в том, что каждому блоку 
N
w
X

 ставится в соответствие некоторое кодовое слово ( )
w
Y



 из букв кодового алфавита 
1
2
{ ,
,...,
}
m
Y
y y
y

 (здесь Y  обозначает множество всевозможных последовательностей из элементов множества Y ). Кодирование, при котором блокам источника ставится в соответствие кодовое слов нефиксированной 
длины, называется равномерным по входу.  
Разные буквы кодового алфавита имеют разную длительность или, другими словами, стоимость передачи: 
)
(
j
j
y
t
t 
, 
m
j
,1

. Таким образом, каждому 
кодовому алфавиту можно поставить в соответствие вектор длительностей 
букв 


1
2
, ,
, m
t
t t
t

, (
(
)
j
j
t
t y

, 
1,
j
m

). В частности, длительности кодовых 
символов могут быть одинаковы, в этом случае соответствующий алфавиту 
вектор обозначим через 


1
1,1,
,1
m
t 
. 
Самым популярным примером кода с неравными длительностями является код Морзе, актуальность которого не теряется и в наше время:  на основе кода Морзе созданы широко используемые штрихкоды. 
  
Длительностью кодового слова будем считать величину, равную сумме 
длительностей входящих в слово букв:  





,
y
w
l
w t
t y



