Терема кодування для каналу без шуму

Коли і інформаційний канал, і система зв'язку вільні від помилок, то основна роль останньої повинна зводитися до подання джерела в максимально компактній формі.

Рис. 1.9. Модель системи передачі інформації.

При цих умовах теорема кодування для каналу без шуму, також називають першою теорема Шеннона, визначає мінімально досяжну середню довжину кодового слова на символ джерела.

Джерело інформації з кінцевим ансамблем повідомлень (А,z) і статистично незалежними символами джерела, називається джерелом без пам'яті. Якщо виходом джерела є не один символ, а послідовність з n символів алфавіту, то можна вважати, що вихід джерела приймає одне з можливих значень, позначуваних з повного набору можливих послідовностей в n елементів: . Іншими словами, кожен блок , називається блоковою випадковою змінною, складається з n символів алфавіту A. (Позначення дозволяє відрізняти набір блоків від набору символів алфавіту A.) Імовірність окремого блоку , дорівнює і пов'язана з імовірностями окремих символів наступним співвідношенням:

де індекси використовуються для вказівки n символів алфавіту А, складових блок . Як і раніше, вектор (штрих означає, що використовується блокова випадкова змінна) позначає сукупне розподіл ймовірностей , і ентропія джерела дорівнює

Підставляючи (1.3-14) для і спрощуючи вираз, отримаємо:

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

Оскільки кількість інформації на виході джерела , є перші , розумним представляється кодування , за допомогою кодових слів довжини , де l -ціле число, таке що

Інтуїція підказує, що вихід джерела , повинен бути представлений кодовим словом, довжина якого є найближче ціле, превищує кількість інформації в . Множення (1.3-16) на і підсумовування по всіх , дає

або

де означає середню довжину кодового слова, яке відповідає n -кратному розширенню нерозширення джерела, тобто

Розділивши (1.3-17) на n, і враховуючи, що , отримаємо нерівність:

, (1.3-19)

яке перетворюється в граничному випадку в рівність:

(1.3-20)

Нерівність (1.3-19) встановлює першу теорему Шеннона для джерел без пам'яті, яка стверджує, що, кодуючи джерело безмежного розширення, можна досягти значення скільки завгодно близької до ентропії джерела . Незважаючи на те, що ми грунтувалися на припущенні про статистичну незалежність символів джерела, отриманий результат може бути легко розповсюджений на більш загальний випадок, коли поява символу джерела може залежати від кінцевого числа попередніх символів. Такі типи джерел (називаються марковськими джерелами) звичайно використовуються для моделювання міжелементних зв'язків на зображенні. Оскільки є точною нижньою гранню для вираження (цей вираз, згідно (1.3-20), прагне до при збільшенні ), то ефективність будь-якої стратегії кодування може бути виражена наступною формулою:

Приклад 1.7. Кодування з розширенням.

Джерело інформації без пам'яті з алфавітом має ймовірності символів і . Згідно (1.3-3), ентропія цього джерела дорівнює 0,918 біт/символ. Якщо символи і представлені однобітових кодовими словами 0 і 1, то біт/символ і результуюча ефективність кодування дорівнює , або 0,918.

У Таблиці 1.4 містяться і тільки що розглянутий код, і альтернативний спосіб кодування, заснований на двократному розширення джерела. У нижній частині таблиці наведені чотири блокових символу (), відповідних другому варіанту. Як випливає з (1.3-14), їх ймовірності рівні 4/9, 2/9, 2/9 і 1/9. Відповідно (1.3-18), середня довжина кодового слова при цьому буде дорівнює 17/9 = 1,89 біт/символ. Ентропія при двократному розширенні джерела дорівнює подвоєною ентропії нерозширення джерела, тобто 1,83 біт/символ, так що ефективність при другому варіанті кодування складе = 1,83 / 1,89 = 0,97.

Таблиця 1.4. Приклад кодування з розширенням.

Це дещо краще, ніж ефективність нерозширення джерела, яка дорівнює 0,92. Як легко бачити, кодування дворазового розширення джерела скорочує середнє число бітів кодової послідовності на один символ джерела з 1 біт/символ до 1,89 / 2 = 0,94 біт/символ.

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