Джерело → Канал: Двостадійне кодування
Розділ 10 Хеммінга починається з моделі комунікації Шеннона, яка застосовується до кожної системи, яка передає інформацію: телефонні дзвінки, радіо, жорсткі диски, репродукція ДНК, комп'ютерна пам'ять.
Архітектура двостадійного кодування
Стадія 1: Кодування джерела (стиснення). Перетворіть вихідне повідомлення на компактне представлення. Мета: видалити надмірність, властиву джерелу. Код Морзе робить це: загальні літери отримують короткі коди, рідкісні літери отримують довгі.
Стадія 2: Кодування каналу (захист від помилок). Додайте контрольовану надмірність, адаптовану до характеристик шуму каналу. Шумна телефонна лінія потребує більше надмірності, ніж оптоволоконний кабель. Дві стадії розділяються: оптимізуйте кожну незалежно для її власного завдання.
Загальний інтерфейс між двома стадіями — стандартизований бітовий потік — означає, що будь-яке джерело може спаруватися з будь-яким каналом. Ця модульність є ключною архітектурною ідеєю Шеннона.
Зберігання як комунікація. Хеммінг зазначає, що відправлення повідомлення через простір (передача) та його відправлення через час (зберігання) використовують одну й ту ж модель. Резервна копія на диску — це шумний канал у часі.
Роль шуму
Модель Шеннона робить радикальне припущення: шум невідворотний. Кожен канал, кожне запам'ятовуючий пристрій, кожен комутаційний ланцюг вводить певну ймовірність помилки. Питання не в тому, як ми можемо усунути шум, а в тому, як ми можемо відновити вихідне повідомлення, попри шум.
Це контрастує з класичною фізикою, де шум входить як непередбачувана явище (принцип невизначеності). Шеннон розглядає шум як основну умову — вся теорія будується на ній.
Наразі, Розділ 10 зосереджується на безшумному випадку: кодування джерела без помилок. Проблема кодування каналу (коригування помилок) чекає на пізніші розділи.
Коли ви можете декодувати унікально?
Щоб код змінної довжини був корисним, приймач повинен декодувати потік бітів однозначно. Хеммінг ілюструє код з 4 символів, який не відповідає цьому тесту, потім представляє виправлення: префіксно-вільні коди.
Умова префіксної вільності
Код є префіксно-вільним (або миттєвим), якщо жоден кодовий символ не є префіксом будь-якого іншого кодового символу. Виходячи з отриманого потоку бітів, ви знаєте, що символ закінчився в момент, коли ви досягнете листя в дереві декодування — попередній перегляд не потрібен.
Приклад префіксно-вільного коду для {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Перевірте: 0 не є префіксом 10, 110 або 111. 10 не є префіксом 110 або 111 (10, за якими йдуть більше бітів, дають 100... або 101..., жодне з яких не починається з 110 або 111). Код відповідає умові.
Процедура декодування: дотримуйтесь дерева, розгалуджуйтесь на кожному вхідному біті, видавайте символ коли ви досягнете листя, повернеться до кореня.
Нерівність Крафта
Для будь-якого префіксно-вільного двійкового коду з довжиною кодових символів l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Рівність виконується, коли код є повним (листя кахлюють повне двійкове дерево без зазорів). Це необхідна умова: жоден префіксно-вільний код не може її порушити. Навпаки, для будь-якого набору довжин, що задовольняють нерівність Крафта, існує префіксно-вільний код.
Застосування нерівності Крафта
Виходячи з довжин кодових символів, перевірте Крафта: Σ 2^(−l_i) ≤ 1.
Для {s1=0, s2=10, s3=110, s4=111}: довжини — 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Ентропія Шеннона
Середня довжина коду коду змінної довжини: L = Σ p_i · l_i, де p_i — ймовірність символу s_i та l_i — довжина його коду.
Наскільки коротким може бути L? Відповідь Шеннона: не нижче ентропії джерела.
Ентропія Шеннона: H = −Σ p_i · log₂(p_i) (одиниці: біти/символ)
Ентропія вимірює середню інформацію на символ. Висока ентропія означає, що символи мають приблизно рівну ймовірність (максимальна непередбачуваність). Низька ентропія означає, що деякі символи домінують (висока передбачуваність, більш стисна).
Теорема бездефектного кодування
Для будь-якого префіксно-вільного коду H(джерело) ≤ L ≤ H(джерело) + 1.
Жоден код не може перемогти ентропію. Кодування Хаффмана (наступний розділ) досягає верхньої межі: L < H + 1. Для блокових кодів над n символів межа затягується: H ≤ L/n < H + 1/n.
Ентропія також є теоретичною межею стиснення: ви не можете стискати джерело нижче H бітів на символ без втрати інформації.
Обчислення ентропії
Приклад: 4 символи з ймовірностями p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 бітів/символ
І код Хаффмана {0, 10, 110, 111} досягає L = 1.75 = H точно.
Чому ентропія є нижною межею
Нижня межа теореми бездефектного кодування — це не просто формула — вона відображає щось глибоке про інформацію: ви не можете стискати те, що вже максимально непередбачуване.
Коли всі символи рівноймовірні (рівномірний розподіл), ентропія H = log₂(n) для n символів. Блоковий код довжини log₂(n) бітів досягає точно H. Жоден код не може зробити краще.
Коли один символ домінує (скажімо, p(A) = 0.99, p(B) = 0.01), H є малою — близькою до 0. Код змінної довжини може присвоїти A дуже короткий код, кодуючи потік дуже ефективно.
Практичний висновок: великі коефіцієнти стиснення існують лише коли ймовірності символів суттєво відрізняються. Якщо джерело вже 'рівномірне' (випадково виглядаюче), кодування Хаффмана не дає жодних здобутків.