Что Шеннон называл информацией
Шеннон определил информацию, измеряя неожиданность. Сообщение с вероятностью p несёт:
I = −log₂(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ᵢ в сфере другой aⱼ в сфере результат
да нет правильно (нет ошибки)
да да неоднозначно → ошибка
нет да неправильное декодирование → ошибка
нет нет вне всех сфер → ошибка
``
Граница на 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) применяется ли оно сейчас при различных условиях?