Математики, шпионы и хакеры. Кодирование и криптография | страница 44
При цифровой передаче информации сообщение, сгенерированное отправителем (это может быть как человек, так и компьютер или другое устройство), кодируется в двоичной системе и поступает в канал связи, состоящий из компьютеров отправителя и получателя, плюс самой линии связи, которая может быть или физическим кабелем, или беспроводной (радиоволны, инфракрасное излучение и т. д.). Движение по каналу связи является особенно уязвимым процессом, потому что сообщение подвергается всевозможным воздействиям, в том числе взаимодействиям с другими сигналами, неблагоприятным температурам физической среды и затуханиям (ослаблению) сигнала при прохождении через среду. Эти источники помех называются шумами.
Одним из таких методов является избыточность информации. Он состоит в повторении при определенных критериях некоторых характеристик сообщения. Рассмотрим пример, который поможет пояснить процесс. Возьмем текст, в котором каждое слово состоит из четырех битов, общее количество различных слов — 16 (т. к. 2>4 = 16), каждое слово имеет вид а>1а>2а>3а>4. Перед отправкой сообщения мы добавим к слову еще три бита c>1c>2c>3так что закодированное сообщение при движении по каналу связи будет выглядеть как а>1а>2а>3а>4c>1c>2c>3. Дополнительные символы c>1c>2c>3 обеспечивают надежность сообщения. Они называются контрольными битами, или битами четности, и строятся следующим образом.
Добавим следующие биты четности к сообщению 0111.
Так как сумма 0 + 1 + 1 = 2 четная, с>1 = 0.
Так как сумма 0 + 1 + 1 = 2 четная, с>2 = 0.
Так как сумма 1 + 1 + 1 = 3 нечетная, с>3 = 1.
Следовательно, сообщение 0111 будет передано в виде 0111001. Для «слов» мы, таким образом, получим следующую таблицу:
* * *
ГЕНИЙ БЕЗ НАГРАДЫ
Клод Элвуд Шеннон (1916–2001) был одним из величайших научных деятелей XX в. Получив образование по специальности «электротехника» в Мичиганском университете и Массачусетском технологическом институте, он работал математиком в лаборатории компании «Белл», где занимался исследованиями по криптографии и теории коммуникации. Его научный вклад настолько велик, что он считается одним из основоположников теории информации, но поскольку его работы были на стыке математики и информационных технологий, он так и не получил самой престижной среди ученых Нобелевской премии.
* * *
Допустим, что на другом конце сообщение будет получено в виде 1010110. Заметим, что такая комбинация нулей и единиц не входит в число возможных кодов и, следовательно, является ошибкой при передаче. В попытке исправить ошибку система сравнивает каждую цифру с набором цифр всех возможных кодов, чтобы найти наиболее вероятную альтернативу. Для этого система проверяет, какие из цифр представляют собой ошибку, следующим образом.
