Теорема кодування джерела (про взаємозв'язок швидкості і спотворення)

Теореми, розглянуті до справжнього моменту, встановлюють фундаментальні межі безпомилкової зв'язку як по надійним, так і по ненадійним каналам. У даному розділі ми повернемося до випадку каналу без помилок, але в цілому процес передачі інформації може бути не точним. Головним завданням системи зв'язку в такий послідовності є «стиснення інформації», можливо, за рахунок деякого її спотворення. У більшості випадків середня помилка, яку вносить стисненням, обмежується деякими максимально допустимим рівнем D. Ми хочемо знайти найменшу допустиму швидкість як функцію заданого критерію точності, при якій інформація може бути передана від джерела до одержувача. Вирішенням цієї конкретної проблеми займається розділ теорії інформації, називається теорія взаємозв'язку швидкості та спотворення.

Нехай джерело інформації і вихід декодера на Рис. 1.9 визначені кінцевими ансамблями (А, z) і (В, z) відповідно. Припускається, що канал на Рис. 1.9 є каналом без помилок, так що матриця каналу Q, Яка пов'язує z з v згідно (1.3-6), може розглядатися як визначальна тільки сам процес кодування-декодування. Оскільки процес кодування-декодування є детермінованим, описує деякий ідеальний канал без пам'яті, що імітує ефект стиснення і відновлення інформації. Всякий раз, коли джерело породжує вихідний символ , останній представляється деяким кодовою символом, який в результаті декодується у вихідний символ з імовірністю (див. Розділ 1.3.2).

Постановка задачі кодування джерела, при якій середня величина спотворення не повинна перевищувати рівня D вимагає методу кількісної оцінки величини спотворення для будь-якого виходу джерела. Для простого випадку нерозширення джерела може бути використана ненегативна функція вартості , називається мірою спотворення, визначальна величину «штрафу», виникає у випадку, коли вихід джерела відтворюється на виході декодера . Вихід джерела є випадковою величиною, тому спотворення також є випадковою величиною, середнє значення якої дорівнює

Запис підкреслює, що середнє спотворення є функція процедури кодування-декодування, яка (як уже зазначалося раніше) моделюється матрицею каналу . Конкретна процедура кодування-декодування називається D - точною тоді і тільки тоді, коли середнє спотворення менше або дорівнює D. Таким чином, набір D -точних процедур кодування-декодування може бути записаний у вигляді:

Оскільки кожна процедура кодування-декодування визначається матрицею каналу Q, то середня інформація, що отримується при спостереженні одиничного виходу декодера, може бути порахована відповідно (1.3-12). Отже, ми можемо визначити найменшу допустиму швидкість як функцію спотворення виразом

тобто як мінімальне значення (1.3-12) на множині всіх D -точних кодів. Зауважимо, що залежить від значень ймовірностей в векторі z і елементів матриці Q, а мінімум в правій частині (1.3-25) береться по Q. Якщо D = 0, то менше або дорівнює ентропії джерела, тобто .

Рівняння (1.3-25) визначає мінімально можливу швидкість як функцію спотворення, при якій інформація від джерела може бути доставлена ​​одержувачу за умови, що середнє спотворення менше або дорівнює D. Щоб обчислити цю швидкість, тобто , ротрібно мінімізувати значення , що задається (1.3-12), шляхом вибору підходящої матриці Q (або ) за умови виконання наступних обмежень:

,

і

Формули (1.3-26) і (1.3-27) виражають основні властивості матриці каналу : її елементи повинні бути невід'ємними і, оскільки будь-якому вхідному символу повинен відповідати якийсь вихід, сума елементів по будь-якому стовпцю матриці повинна бути рівна 1. Рівняння (1.3-28) показує, що мінімальна швидкість досягається при максимально допустимому спотворенні.

Приклад 1.9. Обчислення швидкості як функції спотворення для двійкового джерела без пам'яті.

Розглянемо двійковий джерело без пам'яті з рівноімовірними символами джерела {0, 1} і простою мірою спотворення

де - одинична дельта-функція. Оскільки якщо і 0 в інших випадках, то кожна помилка кодування-декодування вважається за одну одиницю спотворення. Для знаходження може бути використано варіаційне числення, а саме метод Лагранжа знаходження умовного екстремуму. Розглянемо функцію Лагранжа

яка додатково залежить від множників Лагранжа , ,..., . Прирівняємо її похідні по змінним до нуля (тобто = 0), і вирішимо систему, що складається з отриманих рівнянь разом з рівняннями зв'язків (1.3-27) і (1.3-28), для невідомих і , ,..., . Якщо отримані значення не негативні, тобто задовольняють (1.3-26), це означає, що знайдено вірне рішення. Для певної вище пари джерела і спотворення, отримаємо наступні 7 рівнянь (з 7-ма невідомими):

Послідовність алгебраїчних перетворень приводить до наступних результатів:

так що

Оскільки було задано, що символи джерела рівноймовірно, то максимальне можливе спотворення дорівнює 1/2. Таким чином і елементи матриці Q відповідають (1.3-12) для всіх D.

Взаємна інформація, пов'язана з Q і раніше визначеним двійковим джерелом, обчислюється з використанням (1.3-12). Відповідно помітив схожість матриці Q і матриці двійкового симетричного каналу, можна відразу написати:

.

Це випливає з результату Прикладу 1.6 при підстановці = 1/2 і в вираз . Швидкість як функція спотворення може бути отримана прямо з (1.3-25):

.

Останнє спрощення засноване на тому обставину, що для заданного D різницю приймає єдине значення, за замовчуванням є мінімумом. Результуюча функція показана графічно на Рис. 1.10; ця форма типова для більшості графіків швидкості як функції спотворення. Відзначимо точку максимуму D, позначену , таку, що для всіх . Крім того, завжди позитивна, монотонно убиває, і опукла вниз на відрізку (0, ).

Для простих джерел і заходів спотворення, швидкість як функція спотворення може бути обчислена аналітично, як і в попередньому прикладі. Більше того, коли аналітичні методи не працюють, то можуть використовуватися сходяться ітеративні алгоритми, зручні для чисельної реалізації на комп'ютерах.

Рис. 1.10. Швидкість як функція спотворення для двійкового симетричного джерела.

Після того, як обчислили на , теорема кодування джерела стверджує, що для будь-якого існує такий код довжини r і швидкості , що середнє спотворення на символ задовольняє умові . Важливий практичний наслідок даної теореми і теореми кодування для каналу з шумом полягає в тому, що вихід джерела може бути відновлений декодером з довільно малою ймовірністю помилки, за умови, що канал має пропускну спроможність . Цей останній результат відомий як теорема про передачу інформації.

Поиск по сайту: