Кодування інформації і надмірність коду, рубрика статті

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

У більшості випадків використовуються системи кодування мають надмірністю, тобто вимагають для запису більшу кількість інформації, ніж воно міститься в кодованому повідомленні. Надмірність визначається формулою # 92; [E = 1 - # 92; frac # 92;] де # 92; (H # 92;) - ентропія повідомлення, # 92; (Q # 92;) - середня кількість інформації, що припадає на один символ кодованого повідомлення.

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

величина # 92; (H / Q # 92;) називається економічністю коду. Для оптимального коду # 92; (H / Q = 1 # 92;) а надмірність відсутня, тобто # 92; (E = 0 # 92;).

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

Приклад: визначити ентропію інформації, що міститься в повідомленні «навчання - світло, а не навчання - тьма» і надмірність коду. Кожен символ в повідомленні кодується 1 байтом (8 біт).
Рішення: Підрахуємо кількість символів в повідомленні, для простоти ігноруючи пропуски: N = 26. Знайдемо частоту повторення кожного символу (ймовірність в повідомленні), склавши наступну таблицю, наведену на скрині зліва.

Питома ентропія (ентропія одного символу в повідомленні) в бітах на символ, дорівнює # 92; [# 92; tilde H = 5 # 92; cdot # 92; frac> 13 + # 92; frac> # 92; frac> + 2 # 92; cdot # 92; frac> # 92; frac> + 4 # 92; cdot # 92; frac> 26 # 92; approx # 92;] # 92; [ # 92; approx # 92; frac> # 92; cdot 3.7004 + # 92; frac> # 92; cdot 2.1155 + # 92; frac> # 92; cdot 3.1155 + # 92; frac> # 92; cdot 4.7004 # 92; approx 3.3535 # 92;] Повна ентропія повідомлення # 92; (H = 3.3535 # 92; cdot 26 = 87.19 # 92;) біт. Кількість біт, необхідне для кодування кожного символу одним байтом, становить # 92; (Q = 208 # 92 ;; # 92;) біт.
надмірність коду # 92; (E = 1-87.19 / 208 = 0.58 = 58% # 92;).