Що Шеннон називав інформацією
Шеннон визначив інформацію вимірюванням несподіванки. Повідомлення з імовірністю p містить:
I = −log₂(p) біти
Певна подія (p = 1) містить 0 біт — немає несподіванки, немає інформації. Рідка подія (p = 1/1024) містить 10 біт.
Хеммінг одразу вказує на проблему: це формула для вимірювання величини, а не визначення поняття. Вона вимірює машиноподібну несподіванку, а не людське значення. Учень, який уже знає відповідь на питання, одержує 0 біт від відповіді — незалежно від того, наскільки важлива відповідь для інших.
Формула добре застосовується до телефонних систем, радіо, комп'ютерів. Вона застосовується погано для людської комунікації, біології чи значення. Віддавана перевага Хеммінга: «Теорія комунікації», а не «Теорія інформації».
Ентропія
Для алфавіту з q символів з імовірностями p₁, p₂, ..., p_q середня інформація на один символ називається ентропією:
H = −Σᵢ pᵢ log₂(pᵢ)
H досягає максимуму, коли всі імовірності рівні: H_max = log₂(q) біт. Будь-який неунітарний розподіл має нижчу ентропію.
Обчислення ентропії
Двійкова ентропія: джерело з двома символами, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 при p = 0 або p = 1 (абсолютно передбачуваний). H(p) = 1 біт при p = 0,5 (абсолютно непередбачуваний).
Нерівність Гіббса та безшумне кодування
Нерівність Гіббса: для будь-яких двох розподілів імовірностей p = {pᵢ} та q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
з рівністю лише коли p = q. Це спирається на елементарний факт, що ln(x) ≤ x − 1 для всіх x > 0, з рівністю при x = 1.
Наслідок: ентропія H(p) максимізується, коли всі символи мають рівну імовірність. Для q символів: H_max = log₂(q).
Теорема про безшумне кодування: для унікально декодованого коду нерівність Крафта вимагає Σ 2^(−lᵢ) ≤ 1, де lᵢ — довжина коду для символу i. За нерівністю Гіббса середня довжина коду L = Σ pᵢ lᵢ задовольняє:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Ви не можете зробити краще за ентропію в середньому. Кодування Гаффмана досягає L < H + 1.
Пропускна спроможність каналу
Двійковий симетричний канал (BSC) незалежно перевертає кожен біт з імовірністю помилки Q = 1 − P. Пропускна спроможність BSC — максимальна надійна швидкість передачі інформації — визначається як:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
де H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) — двійкова ентропія частоти помилок.
При Q = 0 (немає помилок): C = 1 біт/передача (ідеальний канал). При Q = 0,5 (випадкові переверти): C = 0 (канал не передає інформацію). При Q = 1 (усі біти перевертаються): C = 1 (ви знаєте точно, що надіслав відправник, просто переверніть все назад).
C вимірює максимальну швидкість R, при якій ви можете передавати з довільно малою імовірністю помилки. Якщо R < C, такі коди існують. Якщо R > C, вони не існують — жодний код не може перевищити пропускну спроможність.
Обчислення пропускної спроможності каналу
При P = 0,9 (10% частота помилок, Q = 0,1):
C = 1 + 0,9 log₂(0,9) + 0,1 log₂(0,1)
log₂(0,9) ≈ −0,152, log₂(0,1) ≈ −3,322
C ≈ 1 + 0,9×(−0,152) + 0,1×(−3,322) = 1 − 0,137 − 0,332 ≈ 0,531 біт/передача
Що доводить теорема
Фундаментальна теорема Шеннона: для будь-якої швидкості R < C існують коди блокової довжини n (з n → ∞), які досягають імовірності помилки P_E → 0.
Доказ використовує дивовижний аргумент: випадкові коди. Замість конструювання конкретного коду, Шеннон усереднював за всіма можливими випадковими кодовими книгами (кидання монети для кодування). Він показав, що середня помилка над усіма кодовими книгами мала. Якщо середня мала, принаймні один код досягає малої помилки.
Аналіз на основі сфер: відправник вибирає повідомлення aᵢ → сфера радіуса n(Q + ε₂) навколо aᵢ в n-вимірному двійковому просторі. Для великого n одержане слово bⱼ лежить всередині цієї сфери з високою ймовірністю. Одержувач декодує кодове слово, сфера якого містить bⱼ.
Чотири випадки визначають імовірність помилки P_E:
``
aᵢ in sphere other aⱼ in sphere outcome
yes no correct (no error)
yes yes ambiguous → error
no yes wrong decode → error
no no outside all spheres → error
``
Обмеження на P_E працює так: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) для відповідно вибраних d та ε₂. Вибираючи ε₂ так, щоб H(Q+ε₂) < C, робимо показник від'ємним. Для великого n другий член → 0.
Екзистенціальна природа теореми
Хеммінг був точний щодо того, що теорема робить та не робить.
Що вона доводить: надійна комунікація з швидкістю R < C можлива в принципі для досить великого n.
Що вона не надає: явну конструкцію коду. Випадковий код довжини n досить великої для наближення пропускної спроможності має кодову книгу розміром M × n біт, де обидва M та n астрономічно великі. Ви не можете зберігати або обчислювати з нею.
Коди для виправлення помилок проти Шеннона: коди для виправлення помилок (Хеммінг, Рід-Соломон, турбо, LDPC) надають явні, обчислювальні конструкції. Вони жертвують деякою відстанню від пропускної спроможності в обмін на практичні кодери та декодери. Коли n зростає та виправляється більше помилок за блок, практичні коди можуть наближатися до пропускної спроможності близько.
Приклад космічних супутників: Voyager та Pioneer використовували потужні коди для виправлення помилок для спілкування через мільярди миль на потужності 5–20 ватів. Довгі блокові довжини дозволяли виправляти більше помилок за блок, наближуючись до пропускної спроможності попри величезний шум від відстані.
Критична оцінка
Хеммінг закрив Розділ 13 з більш широкою критикою визначень у науці. Формула інформації Шеннона вимірює машиноподібну несподіванку, а не людське значення. Назва «Теорія інформації» обіцяє занадто багато. Аналогія з рибальською сіткою: рибалка, який ловить лише рибу більшу за сітку, робить висновок, що немає меншої риби. Обмеження інструменту стають видимими обмеженнями світу.
Проблема з визначеннями
Хеммінг використав теорію інформації, щоб зробити ширшу методологічну точку: початкові визначення визначають те, що ви знаходите, більше ніж більшість людей усвідомлює.
Шеннон вибрав визначити «інформацію» як несподіванку. Це визначення було продуктивним для інженерії комунікацій. Але воно імпортувало конкретну область — машиноподібні системи — в слово («інформація»), яке припускає універсальність застосування.
Аналогія з рибальською сіткою: сітка з сіткою 6 дюймів ловить лише великих рибин. Рибалка робить висновок: мінімальний розмір риби 6 дюймів. Висновок відображає інструмент, а не світ.
IQ як паралель: тест розроблений для вимірювання «інтелекту», калібрований для виробляння нормального розподілу, потім використаний для визначення інтелекту. Інструмент формує концепцію.
Рекомендація Хеммінга: коли ви зустрічаєте визначення, запитайте (1) наскільки воно узгоджується з вашою попередньою інтуїцією? (2) наскільки воно спотворює? (3) під які умови воно було створено? (4) чи застосовується воно зараз в інших умовах?