1. Введение: Что такое информация?

Слово «информация», которое мы произносим каждый день, очень трудно определить с научной точки зрения. Новости, сообщения от друзей, последовательность оснований ДНК или радиоволны из космоса — все это содержит информацию. Однако, чтобы работать с ними математически в общих рамках, необходим объективный и количественный показатель.

Человек, который взялся за эту грандиозную задачу и заложил основу современного цифрового общества, — математик и инженер Клод Шеннон (Claude Shannon). Не будет преувеличением сказать, что его статья 1948 года «Математическая теория связи» (A Mathematical Theory of Communication) в одиночку создала совершенно новую дисциплину — теорию информации (Information Theory).

В этой статье мы подробно рассмотрим, как Шеннон математически определил «информацию», и какое значение имеет ее центральная концепция, энтропия Шеннона, для технологий сжатия данных и связи.

2. Общая модель коммуникации

Шеннон на время отделил значение (семантику) информации и сосредоточился на самой «передаче» информации. Предложенная им общая модель системы связи представлена на диаграмме Mermaid ниже.

  graph LR
    A["Источник информации<br>Information Source"] --> B["Передатчик<br>Transmitter"]
    B -->|"Передаваемый сигнал"| C(("Канал связи<br>Channel"))
    C -->|"Принимаемый сигнал"| D["Приемник<br>Receiver"]
    D --> E["Адресат<br>Destination"]
    N["Источник шума<br>Noise Source"] -.-> C

В этой модели главная проблема коммуникации сводится к следующему: «Как точно и эффективно передать сообщение через канал связи с наличием шума?»

3. Математическое определение количества информации

Самый фундаментальный вопрос в теории информации: «Когда мы узнаем, что произошло определенное событие, сколько информации мы получаем?»

Шеннон рассматривал количество информации как «степень удивления».

• Когда происходит частое событие (событие с высокой вероятностью), удивление невелико, и получаемое количество информации мало.
• Когда происходит редкое событие (событие с низкой вероятностью), удивление велико, и получаемое количество информации велико.

Пусть вероятность наступления события \( x \) равна \( P(x) \), тогда собственная информация (Self-Information) \( I(x) \), содержащаяся в этом событии, определяется следующим образом:

Если в качестве основания логарифма используется \( 2 \), единицей измерения количества информации является бит (bit). Например, количество информации события выпадения орла при подбрасывании монеты с равной вероятностью выпадения орла и решки (\( P = 0.5 \)) равно:

Это совпадает с интуитивным пониманием «1 бита информации».

4. Энтропия Шеннона

Собственная информация — это количество информации для отдельного события, но как узнать, сколько информации в среднем генерируется всем источником информации?

Здесь появляется энтропия (Entropy). Когда источник информации \( X \) генерирует \( n \) различных символов \( x_1, x_2, \dots, x_n \) с вероятностями \( P(x_1), P(x_2), \dots, P(x_n) \), энтропия \( H(X) \) источника информации \( X \) определяется как математическое ожидание собственной информации.

(Однако, в случае \( P(x_i) = 0 \) считается, что \( 0 \log_2 0 = 0 \))

Интуитивное значение энтропии

Энтропия \( H(X) \) представляет собой степень неопределенности, которой обладает источник информации.

• Когда совершенно невозможно предсказать, какой символ появится (все вероятности равны), энтропия достигает максимума.
• Когда всегда появляется один и тот же символ (вероятность одного равна \( 1 \), а остальных \( 0 \)), неопределенность исчезает, и энтропия равна \( 0 \).

Давайте вычислим изменение энтропии при изменении вероятности выпадения орла \( p \), используя следующий код на Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import numpy as np
import matplotlib.pyplot as plt

def binary_entropy(p):
    if p == 0 or p == 1:
        return 0
    return -p * np.log2(p) - (1 - p) * np.log2(1 - p)

probabilities = np.linspace(0, 1, 100)
entropies = [binary_entropy(p) for p in probabilities]

plt.plot(probabilities, entropies)
plt.title('Binary Entropy Function')
plt.xlabel('Probability of heads (p)')
plt.ylabel('Entropy H(X) in bits')
plt.grid(True)
plt.show()

Построив этот график, мы увидим, что при \( p = 0.5 \) энтропия достигает своего максимального значения \( 1 \), что указывает на состояние полной непредсказуемости.

5. Теорема кодирования источника: пределы сжатия данных

Энтропия — это не просто абстрактная концепция. Шеннон доказал, что эта энтропия определяет абсолютный предел сжатия данных. Это теорема кодирования источника (первая теорема Шеннона).

Утверждение теоремы очень простое: «Какой бы алгоритм сжатия без потерь ни использовался, средняя длина кода данных, генерируемых источником информации, не может быть меньше энтропии \( H(X) \) этого источника.»

( \( L \) — средняя длина кода)

Другими словами, энтропия указывает на «существенный размер самой информации», и это означает, что математически невозможно сжать данные за пределами этого барьера, независимо от того, насколько хороши алгоритмы ZIP или gzip.

Код Хаффмана (Huffman Coding)

В качестве конкретного метода приближения к пределу энтропии Дэвид Хаффман, развивая идеи Фано, коллеги Шеннона, разработал код Хаффмана.

Присваивая короткие битовые последовательности часто встречающимся символам и длинные битовые последовательности редко встречающимся символам, минимизируется общая средняя длина кода. Ниже приведен пример простого построения кода Хаффмана на Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import heapq
from collections import Counter

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    frequency = Counter(text)
    heap = [Node(char, freq) for char, freq in frequency.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0]

def generate_huffman_codes(node, prefix="", codebook={}):
    if node is not None:
        if node.char is not None:
            codebook[node.char] = prefix
        generate_huffman_codes(node.left, prefix + "0", codebook)
        generate_huffman_codes(node.right, prefix + "1", codebook)
    return codebook

# Пример текста
text = "shannon_entropy_and_information_theory"
tree_root = build_huffman_tree(text)
codes = generate_huffman_codes(tree_root)

print("Huffman Codes:")
for char, code in sorted(codes.items()):
    print(f"'{char}': {code}")

6. Теорема кодирования канала: пределы безошибочной связи

Продемонстрировав пределы сжатия данных, Шеннон затем взялся за «канал связи с шумом». При наличии шума некоторые данные инвертируются или теряются. Чтобы справиться с этим, мы добавляем к данным избыточность, чтобы можно было исправлять ошибки (коды с исправлением ошибок).

Однако, чем больше избыточности мы добавляем, тем ниже становится фактическая скорость (rate) передаваемой информации. Так с какой скоростью и насколько точно мы можем передавать информацию в условиях шума?

Ответом на этот вопрос является теорема кодирования канала (вторая теорема Шеннона).

Шеннон доказал, что канал связи имеет свою собственную пропускную способность канала (Channel Capacity) \( C \). И удивительно, он утверждал следующее:

«Если скорость передачи информации \( R \) меньше пропускной способности канала \( C \) ( \( R < C \) ), то при соответствующем кодировании вероятность ошибки можно сделать сколь угодно близкой к нулю.»

Типичной формулой для вычисления пропускной способности канала \( C \) является теорема Шеннона-Хартли для канала с аддитивным белым гауссовым шумом (AWGN).

Где:

• \( C \) : Пропускная способность канала (bits per second)
• \( B \) : Пропускная способность (Hz)
• \( S \) : Мощность сигнала (Watt)
• \( N \) : Мощность шума (Watt)
• \( \frac{S}{N} \) : Отношение сигнал/шум (Signal-to-Noise Ratio)

Эта теорема служит ориентиром, показывающим достижимый теоретический предел (предел Шеннона) в проектировании всех цифровых систем связи, таких как современный Wi-Fi, мобильная связь 5G и спутниковая связь.

7. Заключение

Теория информации, созданная Клодом Шенноном, математически строго определила нематериальную вещь под названием «информация» и открыла дверь в цифровую эпоху. Энтропия Шеннона — это не просто абстрактное понятие, она показывает абсолютный предел алгоритмов сжатия данных, а пропускная способность канала определила направление эволюции Интернета и беспроводной связи, которыми мы пользуемся каждый день.

Мы можем транслировать видео на наших смартфонах и получать четкие изображения космоса от далеких зондов, потому что существует прочная математическая основа, называемая теорией информации. Концепция энтропии продолжает распространяться на более широкие области, например, обсуждается ее связь с термодинамической энтропией в физике и она играет важную роль в машинном обучении (например, потери перекрестной энтропии).

Глубокое понимание природы данных и знание их пределов по-прежнему будут оставаться самым важным подходом при проектировании более совершенных систем информационных коммуникаций будущего.