Зміст

С.

ПЕРЕДМОВА      3

Частина I  Основи теорії інформації та кодування           4

Розділ 1  ОСНОВНІ ПОЛОЖЕННЯ ТЕОРІЇ ІНФОРМАЦІЇ        4

1.1  Предмет курсу. Види інформації. Теорема дискретизації        4

1.2  Базові поняття теорії інформації 6

1.3  Способи вимірювання інформації               8

1. 4 Ентропія джерела.  Властивості кількості інформації та ентропії            11

Зразки розв'язування задач до розділу 1           14

Задачі до розділу 1               21

Розділ 2  ХАРАКТЕРИСТИКИ ДИСКРЕТНОГО КАНАЛУ ПЕРЕДАЧІ ІНФОРМАЦІЇ       24

2.1  Умовна ентропія           24

2.2  Модель системи передачі інформації          25

2.3  Види умовної ентропії  29

2.4  Ентропія об'єднання двох джерел інформації            32

2.5  Продуктивність дискретного джерела інформації. Швидкість передачі інформації             34

2.6  Інформаційні втрати при передачі інформації по дискретному каналу зв'язку      35

2.7  Пропускна здатність дискретного каналу. Основна теорема про кодування дискретного джерела    38

Зразки розв'язування задач до розділу 2           40

Задачі до розділу 2               47

Контрольні запитання до розділів 1-2               49

Частина II  Економне кодування інформації. Статистичні та словникові методи стиснення даних            51

Розділ 3 ОПТИМАЛЬНІ СТАТИСТИЧНІ МЕТОДИ СТИСНЕННЯ ІНФОРМАЦІЇ               51

3.1  Способи задання кодів. Статистичне кодування       51

3.2  Елементи теорії префіксних множин           56

3.3  Оптимальні методи статистичного стиснення інформації Шеннона-Фано і Хаффмена        57

Зразки розв'язування задач до розділу 3           61

Задачі до розділу 3               64

Розділ 4  ЗАСТОСУВАННЯ СТАТИСТИЧНИХ АЛГОРИТМІВ СТИСНЕННЯ ДО БЛОКІВ ПОВІДОМЛЕННЯ           65

4.1  Теоретичні границі стиснення інформації   65

4.2  Метод блокування повідомлення               67

Зразки розв'язування задач до розділу 4           71

Задачі до розділу 4               74

Розділ 5   АРИФМЕТИЧНЕ КОДУВАННЯ    76

Зразки розв'язування задач до розділу 5           82

Задачі до розділу 5               87

Розділ 6  АДАПТИВНИЙ АЛГОРИТМ ХАФФМЕНА З УПОРЯДКОВАНИМ ДЕРЕВОМ 89

Зразки розв'язування задач до розділу 6           95

Задачі до розділу 6               103

Розділ 7  СЛОВНИКОВІ МЕТОДИ СТИСНЕННЯ ЗІВА-ЛЕМПЕЛА        105

7.1  Алгоритм LZ77             106

7.2  Алгоритм LZSS             109

7.3  Алгоритм LZ78             110

7.4  Алгоритм LZW              112

Зразки розв'язування задач до розділу 7           115

Задачі до розділу 7               121

Розділ 8  СИСТЕМИ СТИСНЕННЯ ІНФОРМАЦІЇ      123

8.1  Огляд типів систем стиснення інформації  123

8.2  Стиснення без втрат інформації   125

8.3  Стиснення із втратами інформації               126

Контрольні запитання до розділів 3-8               127

Частина III  Завадостійке кодування інформації               129

Розділ 9  ОСНОВНІ ПРИНЦИПИ ЗАВАДОСТІЙКОГО КОДУВАННЯ. ЛІНІЙНІ БЛОКОВІ КОДИ                129

9.1  Основні принципи         129

9.2  Елементи двійкової арифметики 130

9.3  Код з перевіркою на парність      131

9.4  Ітеративний код             133

Зразки розв'язування задач до розділу 9           134

Задачі до розділу 9               140

Розділ 10  СПОСОБИ ЗАДАННЯ ЛІНІЙНИХ БЛОКОВИХ КОДІВ. СИНДРОМНЕ ДЕКОДУВАННЯ ЛІНІЙНИХ БЛОКОВИХ КОДІВ  142

10.1  Способи задання лінійних кодів. Твірна матриця лінійного блокового коду      142

10.2  Перевірна матриця лінійного блокового коду         144

10.3  Кодовий синдром і виявлення помилок лінійним блоковим кодом     145

10.4  Синдромне декодування лінійних блокових кодів  146

10.5  Вага і відстань Хеммінга. Можливості лінійних кодів виявляти і виправляти помилки   149

Зразки розв'язування задач до розділу 10         152

Задачі до розділу 10             158

Розділ 11  КОД ХЕММІНГА             161

Зразки розв'язування задач до розділу 11         165

Задачі до розділу 11             169

Розділ 12  ПОЛІНОМІАЛЬНЕ КОДУВАННЯ ІНФОРМАЦІЇ. ЦИКЛІЧНІ КОДИ  170

12.1  Операції над поліномами в полі двійкових символів GF(2)  170

12.2  Поліноміальні коди     171

12.3  Циклічні коди              173

12.4  Синдром і виправлення помилок у циклічних кодах              177

12.5  Твірна і перевірна матриці циклічного коду            179

12.6  Способи декодування циклічного коду    181

Зразки розв'язування задач до розділу 12         182

Задачі до розділу 12             192

Контрольні запитання до розділів 9-12             194

Відповіді до задач 196

Список використаної та рекомендованої літератури        205

Предметний покажчик         206

Зміст       209