Частина III Розділ 12

1 0100® 01100010100, 10001101® 110011101111001, 11110® 100011100110;

4 ;

5 010111101011111® 011111101011111;

6 , 10010111011®

® 111110010111011, код виявляє 2 і виправляє 1 помилку;

7 d_min = 4; код виявляє 3 і виправляє 1 помилку; P_пом =7 p ³ q ⁴»6,998×10^-16;

8 1100 ®100011110101100, 0011 ®110101100100011; d_min = 6; код здатний виявляти помилки кратності 5 і виправляти помилки кратності 2, ймовірність невиявлення помилки P_пом = p ⁹ q ⁶+7 p ⁸ q ⁷+3 p ⁷ q ⁸+ p ⁵ q ¹⁰;

9 011101 1 ® 0111010, 10110 1 0 ® 1011000;

10 01110 1 1 ® 0111001, 101110 1 ®1011100;

11 ;

12 1 1 01011 ® 1001011 ® 011, 111001 1 ® 1110010 ®010;

15 011 ®1010011, 110® 1001110, 101 ® 0011101.

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

1. Блейхер Р. Теория и практика кодов, контролирующих ошибки. – М.: Мир, 1986.

2. Жураковський Ю.П., Полторак В.П. Теорія інформації та кодування: Підручник. – К.: Вища школа, 2001. – 255 с.

3. Кузьмин И. В. Основы теории информации и кодирования. – Минск: Вышэйшая школа,1986.

4. Лидовский В.В. Теория информации:Уч. пособие. - М.: Компания Спутник+, 2004. - 111 с.

5. Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. – М.: Мир, 1976.

6. Стратонович Р.Л. Теория информации. – М: Изд-во “Сов. Радио”, 1975.

7. Хемминг Р.В. Теория информации и теория кодирования. – М. Радио и связь, 1983.

8. Цымбал В.П. Теория информации и кодирование. – К. Вища школа, 1992. – 263 с.

9. Чисар И., Кернер Я. Теория информации. – М.: Мир, 1985.

10. Шеннон К.-Э. Работы по теории информации и кибернетике. – М.: Изд-во иностр. Лит., 1963. 830 с.

11. Шульгин В. И. Основы теории передачи информации: Учебное пособие. Ч. I. Экономное кодирование. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. - 100 с.

12. Шульгин В. И. Основы теории передачи информации: Учебное пособие. Ч. II. Помехоустойчивое кодирование. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2002. – 90 с.

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

A

ASCII

таблиця кодування, 4

L

LZ77, 105, 106

LZ78, 106, 110

LZSS, 105, 109

LZW, 106, 112

LZ-методи, 105

А

адаптивний (динамічний) алгоритм Хаффмена, 89

аналогова

інформація, 4

аналогово-цифровий перетворювач, 5

ансамбль повідомлень, 7

арифметичне кодування, 76

архівація, 124

Б

байт, 10

без втрат інформації

системи стиснення, 125

безнадмірні коди, 7

безумовна

ентропія, 24

біт, 10

блокові коди, 67, 68,129

бод (baud), 5

В

вага Хеммінга, 149

вектор помилок, 145

вектор Крафта, 56

величина спотворень, 126

верхня границя Варшамова-Гільберта, 151

взаємна інформація, 13

взаємна кількість інформації, 35

виправлення кодом помилок, 150

високоефективні

системи стиснення, 124

виявлення кодом помилок, 150

відстань Хеммінга, 150

властивості

ентропії, 12

кількості інформації і ентропії, 14

циклічних кодів, 173

взаємної ентропії, 33

умовної ентропії, 30

завадостійких кодів, 129

вторинний алфавіт, 7

Г

границі стиснення інформації, 67

Д

двійкове поле GF(2), 131

двійкові (бінарні) коди, 7

двійковий симетричний канал, 132

декодер, 123

декодування циклічного коду, 181

дискретна

інформація, 4

ділення поліномів, 171

добуток поліномів, 170

додаванням за модулем 2, 131

достатні умови

існування завадостійкого коду, 151

Е

економне кодування, 51

ентропія джерела, 11

ентропія об'єднання двох джерел, 32

З

завадостійке кодування, 129

загальна умовна ентропія, 29

зворотна теорема Фано про кодування за наявності завад, 40

згорткові коди, 130

І

із втратами

системи стиснення, 125

інформаційні втрати, 37

інформація, 6

ітеративний

код, 134

К

канал зв'язку, 7

канал без шуму, 35

каскадні

способи стиснення, 124

квантователь, 126

кількість інформації, 9, 10, 36

кодер джерела, 123

коди

Хеммінга, 161

без пам'яті, 57

з пам'яттю, 67

кодова комбінація, 7

кодовий синдром, 146

циклічного коду, 178

кодове слово (слова), 143,129

кодове дерево, 52

кодовий поліном, 174

код, 7

кодування, 7

коефіцієнт стиснення, 124

комбіновані

способи стиснення, 124

контроль парності

код, 131

компактний

код, 56

контрольні

символи, 129

Л

ланцюги Маркова, 25

лінійний код, 130, 143

лінійні

способи стиснення, 124

М

матричні

способи стиснення, 124

метод блокування повідомлень, 68

мінімальна кодова відстань, 150

модель

системи передачі інформації, 25

модем, 5

Н

надлишкові

символи, 129

наслідок теореми Шеннона, 65

неабсолютний статистичний взаємозв'язок джерел, 36

недвійкові (багатопозиційні, q-коди)

коди, 7

некоригувальні, 7

коди, 7

необхідні умови існування завадостійкого коду, 151

неперервна

інформація, 4

нерівність Крафта, 56

нерівномірний

код, 7

неруйнуюче стиснення, 125

нижня границя Хеммінга, 151

нижня границя Плоткіна, 151

низько-, середньо- і високошвидкісні

системи стиснення, 124

низькоефективні

системи стиснення, 124

О

оптимальний код, 67

оптимальні нерівномірні коди, 32

П

первинний алфавіт, 7

первинні

коди, 7

перевірний поліном, 177

перевірні

символи, 129

перевірна матриця, 144

передачі інформації

системи стиснення, 124

повний статистичний взаємозв'язок джерел, 35

поліном синдрому, 178

поліноміальний

код, 171

префіксні коди, 54

префіксна множина, 56

примітивний рівномірний

код, 53

продуктивність джерела, 34

пропускна здатність, 38

Р

рівномірні

коди, 7

руйнуюче стиснення, 125

ряд Фур’є, 6

С

семантична інформація, 11

семантична надмірність, 13

синдром, 149, 162

система перевірних рівнянь, 142

систематичний

код, 130

системи стиснення без втрат, 125

стиснення із втратами, 126

словникові алгоритми, 105

спектр функції, 6

статистична надмірність, 12, 31

статистична незалежність, 36

статистичне

кодування, 31, 56

стиснення інформації, 51

сума двох поліномів, 170

Т

таблиці кодування, 4

твірна матриця циклічного коду, 179

твірний многочлен, 171

твірний поліном, 174

твірна матриця, 142, 151

теорема кодування

за наявності завад, 39

теорема Шеннона про кодування дискретного джерела

за відсутності завад, 39

теорема дискретизації, 5

теорія інформації, 4

У

умовна ймовірність, 24

умовна

ентропія, 25

упорядковане дерево Хаффмена, 89

Ф

Бернуллі

формула, 132

Х

Хартлі

формула, 12

Хаффмена

алгоритм, 58

адаптивний алгоритм, 89

упорядковане дерево, 89

Хеммінга

вага, 149

відстань, 150

коди, 161

Ц

циклічний

код, 173, 176, 177

цифро аналоговий перетворювач, 5

цифрова

інформація, 4

Ч

часткова умовна ентропія, 29

Ш

швидкість передачі інформації, 35

швидкість стиснення, 124, 126

Шеннона-Фано

алгоритм, 57

шум, 7

Зміст

С.

ПЕРЕДМОВА.......................................................................... 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

[1] Шеннон К. Работы по теории информации и кибернетике. - М., Изд-во иностранной литературы, 1963.

[2] Фано Р. Передача інформації. Статистична теорія зв'язку. –М.:

Мир, 1965.