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

Якщо канал, зображений на Рис. 1.9 є каналом із шумом (тобто в ньому можливі помилки), то інтерес зміщується від завдання представлення інформації максимально компактним методом до задачі її кодування таким чином, щоб досягти максимально можливої надійності зв'язку. Питання, яке природно виникає, звучить наступним чином: наскільки можна зменшити помилки, утворені в каналі?

Приклад 1.8. Двійковий канал з шумом.

Припустимо, що ДСК має ймовірність помилки = 0,01 (тобто 99% всіх символів джерела передаються через канал правильно). Простий спосіб збільшення надійності зв'язку полягає в повторенні кожного повідомлення або кожного двійкового символу кілька разів. Наприклад, припустимо, що замість передачі одного символу 0 або 1, використовується кодове повідомлення 000 або 111. Імовірність того, що під час передачі трьохсимвольного повідомлення не виникне помилки, дорівнює , або Імовірність однієї помилки буде , двох , а ймовірність трьох помилок складе . Оскільки імовірність помилки при передачі одного символу становить менше 50%, то одержуване повідомлення може бути декодовано методом голосування трьох отриманих символів. Вірогідність невірного декодування трьохсимвольного кодового слова дорівнює сумі імовірностей помилок в двох символах і в трьох символах, тобто . Якщо ж у слові немає помилок, або всього одна помилка, то воно буде декодовано вірно. Таким чином, для = 0,01 ймовірність помилки при передачі зменшилася до значення 0,0003.

Розширюючи тільки що описану схему повторення, можна досягти як завгодно малої результуючої помилки передачі. У загальному випадку, це здійснюється кодуванням n -кратного розширення джерела при використанні K -символьної кодової послідовності довжини r, де . Ключовим питанням при такому підході є вибір в якості допустимих кодових слів тільки деякого числа з можливих кодових послідовностей, а також формулювання вирішального правила, оптимізуючого ймовірність правильного декодування. У попередньому прикладі, повторення кожного символу джерела три рази еквівалентно кодуванню нерозширення двійкового джерела, використовуючого лише два з = 8 можливих кодових слів. Два допустимих коду - це 000 і 111. Якщо на декодер надходить якийсь інший (недопустимий) код, то вихід визначається голосуванням по більшості з трьох кодових бітів.

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

Друга теорема Шеннона [Shаппоп, 1948], також називається теоремою кодування для каналу з шумом, підтверджує наступне. Для будь-якого , де C є пропускна здатність каналу без пам'яті, існує код довжини r, де r -ціле, має швидкість R, таку, що ймовірність помилки блокового декодування не перевищує будь-якого наперед заданого з інтервалом . Таким чином, імовірність помилки можна зробити як завгодно малою, за умови, що швидкість кодових повідомлень менше або дорівнює пропускної здатності каналу.

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