вання, с помощью кодів слів Довжина, де 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 біт/символ.
Теорема кодування для каналу з шумом
Если канал, збережений на Рис. 1.9 є каналом Із шумом (тобто в ньом Можливі помилки), то Інтерес зміщується від Завдання представлення информации максимально компактним методом до задачі ее кодування таким чином, щоб досягті максимально можлівої надійності зв'язку. Питання, Пожалуйста природно вінікає, звучить наступна чином: наскількі можна Зменшити помилки, утворені в каналі?
Приклад 1.8. Двійковій канал з шумом.
Припустиме, что ДСК має ймовірність помилки=0,01 (тобто 99% всех сімволів джерела передаються через канал правильно). Простий способ Збільшення надійності зв'язку Полягає в повторенні шкірного ПОВІДОМЛЕННЯ або шкірного двійкового символу кілька разів. Например, Припустиме, что вместо передачі одного символу 0 або 1, вікорістовується кодів ПОВІДОМЛЕННЯ 000 або 111. Імовірність того, что во время передачі трьохсімвольного ПОВІДОМЛЕННЯ НЕ вінікне помилки, дорівнює, або Імовірність однієї помилки буде, двох, а ймовірність трьох помилок складі. Оскількі імовірність помилки при передачі одного символу становіть менше 50%, то одержуване ПОВІДОМЛЕННЯ может буті декодовано методом Голосування трьох отриманий сімволів. Вірогідність невірного декодування трьохсімвольного кодового слова дорівнює сумі імовірностей помилок в двох символах и в трьох символах, тобто. Если ж у слові немає помилок, або Всього один помилка, то воно буде декодовано вірно. Таким чином, для=0,01 ймовірність помилки при передачі зменшіть до значення 0,0003.
Розшірюючі только что опису схеми повторення, можна досягті як завгодно малої результуючої помилки передачі. У загально випадка, це здійснюється кодування n-кратного Розширення джерела при вікорістанні K-сімвольної кодової послідовності довжина r, де. Ключовий харчування при такому підході є вибір в якості допустимих кодів слів только Деяк числа з можливіть кодів послідовностей, а такоже ...
