Перевод Great Principles of Computing

В 1948 году Шеннон в своей «теории связи» предложил математическую модель связи. Её смысл в следующем.



Есть источник и есть приёмник. Источник отправляет сообщения, а приёмник принимает. Оба участника пользуются одинаковым словарем для кодирования и раскодирования сообщений.
Модель Шеннона применима к любой системе, которая кодирует, раскодирует, передает, хранит и получает сообщения. Так можно рассматривать природу как источник физических законов (сообщений), а процесс открытия этих законов — как канал связи (Dretske 1981).

Шум еще одна составляющая этой модели. Шум — то, что заставляет приёмник неверно истолковывать сообщения. Плохая видимость (туман и сумерки) нарушает семафорное сообщение между судами; вспышки молнии прерывают передачу радиоволн AM-частот; царапины на CD могут сделать его нечитаемым; множество посторонних шумов делают речь неразборчивой.

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

В своей модели Шеннон в качестве «словаря для кодирования» выбрал биты. Он утверждал, что любое сообщение может быть представлено в виде набора бит, т.e. в прямом смысле оцифровано, любая информация превращает в цифры, в набор нулей и единиц.

Любопытно посмотреть на то, как оцифровывать сообщения и что такое шум, на упрощенном примере.
Пусть источник может передавать только сообщения состоящие из 4 букв: A, B, C и D. Используем двухбитовые коды для обозначения этих букв:

A: 11
B: 10
C: 01
D: 00

Например, источник хочет сказать: «CAB». Этому сообщению соответствует код «011110». Источник отправляет этот набор бит в канал, а приёмник их получает и запускает обратный процесс: разбивает код на пары бит и сверяет со словарем.

Возникает вопрос: достаточно ли двух бит для кодирования этих букв? Естественно, что чем меньше бит требуется для этой цели — тем лучше: сообщения занимают меньше места, передаются быстрее. Однако, короткий код намного проще испортить, внеся даже небольшие искажения, которые привносит шум.

Например, если первый бит в букве A по каким-то причинам потеряется, мы получим 010110 — что соответствует CCB, а это полностью меняет смысл сообщения. Как быть?

Добавим дополнительный бит для каждой буквы (бит четности):

A: 110
B: 101
C: 011
D: 000

Теперь, если первый бит в A теряется мы получаем 010 — такой тройки в словаре нет, поэтому приемник легко может понять, что это ошибка. Однако, он не сможет восстановить исходное сообщение.

Если добавить еще несколько лишних битов, то это поможет приемнику не только выяснить где ошибка, но и восстановить исходный код:

A: 11111
B: 10010
C: 01001
D: 00100

Каждый код отличает от другого как минимум на 3 бита. Теперь испорченный бит показывает набор, который по-прежнему отличается от верного на один бит, но теперь он отличается на два или более битов от всех остальных в словаре! Соответственно, приёмник может легко «поправить» испорченное сообщение.

Инжерен связи Ричард Хемминг (Richard Hamming) впервые сформулировал правило, по которому можно определить достаточное «расстояние» между наборами бит. По Хеммингу, расстояние — это количество бит на которые отличаются наборы бит друг от друга. Теперь эта величина называется расстоянием Хемминга.

Хемминг понял, что для того, чтобы поправить k ошибок, достаточно чтобы расстояние Хемминга было равно 2^k — 1. Хемминг так же разработал семейство кодов (коды Хемминга), которые получаются добавлением битов четности к исходным кодам и создал схемы, которые позволяют легко получать исходные сообщения (с учетом исправления ошибок). Коды Хемминга широко используются при передаче сообщений от процессора к памяти компьютера.

Коды Хемминга хорошо работают, когда шум распределен случайным образом. Однако, в некоторых сигналах шум возникает периодически или на относительно длительное время. С этой задачей хорошо справляются другой тип кодов — коды Рида-Соломона (Reed-Solomon). С точки зрения математики, они более хитрые, однако и те и другие легко могут быть выполнены на интегральных схемах компьютера.