- •Теорія інформації та кодування
- •7.1. Теоретичні положення 121
- •Передмова
- •1. Дискретні джерела інформації
- •1.1. Теоретичні положення
- •1.2. Приклади розв’язання задач Задача 1.2.1
- •1.3. Задачі
- •2. Ефективне кодування
- •2.1. Теоретичні положення
- •2.2. Приклади розв’язання задач
- •Розв’язання. Необхідною умовою побудови нерівномірного коду, що однозначно декодується, є виконання нерівності Крафта. Підставивши значення довжин кодових комбінацій у (2.1), отримаємо
- •Задача 2.2.2
- •Задача 2.2.5
- •2.3. Задачі
- •3. Дискретні канали зв’язку
- •3.1. Теоретичні положення
- •3.2. Приклади розв’язання задач Задача 3.2.1
- •Задача 3.2.2
- •Задача 3.2.3
- •Задача 3.2.4
- •Задача 3.2.5
- •Задача 3.2.7
- •Задача 3.2.8
- •Задача 3.2.9
- •Задача 3.2.10
- •3.3. Задачі
- •4. Коди, їх класифікація та основні характеристики
- •4.1. Теоретичні положення
- •4.2. Приклади розв’язання задач Задача 4.2.1
- •Задача 4.2.2
- •4.3. Задачі
- •5. Двійково-десяткові та двійкові рефлексні коди
- •5.1. Теоретичні положення
- •5.2. Приклади розв’язання задач
- •5.3. Задачі
- •6. Штрихові коди
- •6.1. Теоретичні положення
- •6.2. Приклади розв’язання задач Задача 6.2.1
- •Задача 6.2.2
- •6.3. Задачі
- •7. Двійкові коди, що виявляють помилки
- •7.1. Теоретичні положення
- •7.2. Приклади розв’язання задач Задача 7.2.1
- •Задача 7.2.3
- •Задача 7.2.4
- •7.3. Задачі
- •8. Двійкові коди, що виправляють однократні помилки
- •8.1. Теоретичні положення
- •8.2. Приклади розв’язання задач
- •8.3. Задачі
- •9. Двійкові циклічні коди
- •9.1. Теоретичні положення
- •9.2. Приклади розв’язання задач
- •9.3. Задачі
- •10. Недвійкові коди
- •10.1. Теоретичні положення
- •10.2. Приклади розв’язання задач
- •10.3. Задачі
- •11. Стиснення повідомлень при передачі даних
- •11.1. Теоретичні положення
- •11.2. Приклади розв’язання задач
- •11.3. Задачі
- •12. Канальні коди
- •12.1. Теоретичні положення
- •12.2. Приклади розв’язання задач
- •12.3. Задачі
- •Література
- •Додатки Додаток а. Двійкові логарифми цілих чисел
- •Додаток б. Таблиця значень функції – p log 2 p
- •Додаток в. Десяткові коди країн, що використовуються при штриховому кодуванні
3.2. Приклади розв’язання задач Задача 3.2.1
Знайти пропускну здатність трійкового стаціонарного каналу без пам’яті, який має таку матрицю перехідних ймовірностей
.
Швидкість передачі символів по каналу v0 = 100 Бод.
Знайти середню кількість інформації, що переноситься одним символом, та швидкість передачі інформації по такому каналу від дискретного немарковського джерела інформації з алфавітом X = = {x1, x2, x3}, якщо ймовірності виникнення символів
Часові характеристики джерела та каналу узгоджені, тобто тривалість кожного символу на виході джерела
Розв’язання. Аналізуючи матрицю перехідних ймовірностей ка-налу, можна зробити висновок, що канал є симетричним в посиленому значенні, тому для розрахунку пропускної здатності каналу скористуємося виразом (3.14):
Швидкість передачі інформації розрахуємо, користуючись виразом (3.8). Щоб отримати H ( Y ), знайдемо за виразом
-
(3.19)
Маємо p( y1) = 0,556 ; p( y2) = 0,315 ; p( y3) = 0,129 ;
H ( Y ) = 1,377 біт.
Нарешті = 100 ( 1,377 – 0,557 ) = 82 біт / с .
Задача 3.2.2
Для каналу задачі 3.2.1 знайти середню кількість інформації, що переноситься одним символом, та швидкість передачі інформації по каналу, якщо до входу каналу підключене марковське стаціонарне дискретне джерело інформації задачі 1.2.6.
Розв’язання. Оскільки до входу каналу підключене марковське джерело, вихід каналу теж в загальному випадку буде являти собою марковське джерело, при цьому глибина пам’яті може бути більше одиниці. Це ускладнює застосування виразів (3.6) та (3.8), оскільки для розрахунків H (Y ) недостатньо знати тільки безумовні ймовірності p( yk ) виникнення символів на виході каналу; треба знати також умовні ймовірності p( yk /s), де s – стан джерела з алфавітом Y ( виходу каналу ), який визначається попередніми символами на виході каналу.
Для розрахунку середньої кількості інформації, що переноситься одним символом, доцільніше в цьому випадку користуватись виразом (3.5). Щоб знайти умовну ентропію H ( X /Y ), треба знайти умовні ймовірності , для чого скористуємося виразом
Ймовірності p(xi) та p( yk /xi) є відомими. Для розрахунку ймовірностей p(yk) скористуємося виразом (3.19). Маємо
p(x1) = 0,70037; p(x2) = 0,16802; p(x3) = 0,13161.
Тепер знаходимо набір ймовірностей :
.
Умовна ентропія H ( X /Y ) = 0,4 біт.
Кількість інформації, що переноситься одним символом, з урахуванням значення ентропії HП1( X ), отриманого в задачі 1.2.6 :
I (Y, X ) = 1,001 – 0,4 = 0,601 біт.
Швидкість передачі інформації по каналу
= v0 I (Y, X ) = 100 0,601 = 60,1 біт /c .
Задача 3.2.3
Отримати вирази для пропускної здатності симетричного в посиленому значенні каналу без пам’яті для довільної потужності М алфавіту та для біноміального каналу. Проаналізувати залежність пропускної здатності біноміального каналу від ймовірності р помилки в каналі.
Розв’язання. Матриця перехідних ймовірностей для симетричного в посиленому значенні каналу з алфавітом потужності М містить М рядків, М стовпців та має вигляд
-
.
(3.20)
Тут – ймовірність виникнення конкретної помилки при передачі символу по каналу ( наприклад, перехід символу х1 в символ y3 ). Слід відрізняти цю ймовірність від ймовірності рn виникнення будь-якої помилки, яка дорівнює
-
.
Оскільки канал симетричний в посиленому значенні є симетричним і в послабленому значенні, скористуємося виразом (3.14), підставивши в нього ймовірності із першого рядка матриці (3.20):
-
.
(3.21)
Для біноміального каналу M = 2; 1 – q = p, тому отримаємо
-
.
(3.22)
Розраховуючи С при значеннях р в інтервалі від 0 до 1, отримаємо залежність С від р, яку зображено на рис. 3.1. Аналізуючи цю
Рис.3.1. Графік залежності пропускної здатності від ймовірності помилки для біноміального каналу
залежність, бачимо, що при p = 0 пропускна здатність C чисельно до-рівнює швидкості передачі символів. Через це іноді ці дві характеристики ототожнюють, що принципово не вірно. При збільшенні р від 0 до 0,5 пропускна здатність зменшується від до 0. При р = 0,5 пе-редача інформації неможлива. Подальше збільшення р призводить до збільшення пропускної здатності, і при р = 1 маємо С = . Очевидно, що при р = 1 всі символи при передачі в каналі будуть інвертуватися ( і це відомо на приймальній стороні! ), тому для правильного прийому повідомлень всі символи на виході каналу треба піддавати інверсії.