Данные искажаются из-за слабой радиосвязи, разнообразных электромагнитных помех, да даже чисто физическими повреждениями дисков, USB-накопителей и винчестеров. Благодарить за то, что всё это работает, мы должны инженерный гений человека, который может преодолевать даже такие преграды. Каждое электронное устройство ежесекундно находит и исправляет ошибки. Секретным оружием, позволяющим добиться этого, являются алгоритмы поиска несоответствий и восстановления информации.
Среднестатистический пользователь напрочь игнорирует физическую природу электроники, считая, что она существует в каком-то трансцендентном мире чистой информации. Но инженерам постоянно приходится бороться именно с тем, что окружает нас материально. Так, например, радиоволны, несущие от маршрутизатора очередную серию вашего любимого сериала, с расстоянием слабеют. Шаловливые дети царапают диски с информацией и заляпывают их вареньем. Внутри проводов и микросхем непрерывно гуляют нежелательные электрические токи, порождённые полями других электрошнуров, излучением Солнца, молниями и даже высокоэнергетическими частицами, прилетающими из другого конца Вселенной.
В представлении инженеров всё это выглядит как мощный поток, пытающийся смыть и уничтожить сигнал, который им очень дорог. Но идентифицировать природу каждого источника шума недостаточно, нужно ещё как-то «обойти» его. В целом, выход из ситуации заключается в использовании избыточной информации. Чтобы даже в том случае, если что-то потеряется, резервные данные вовремя восполняли все пробелы. Самый прямолинейный подход, естественно, заключается в простом повторении.
Грубо говоря, если посылать два сигнала вместо одного, то можно надеяться, что как минимум один из них дойдёт до адресата в целости и невредимости. Понятно, что это крайне неэффективно. Поэтому точкой отсчёта для более успешного кодирования является добавление так называемого бита чётности в каждый блок сообщения. Он показывает чётность или нечётность количества единиц в двоичной версии этого блока данных. В первом случае бит четности равен 0, во втором - 1. И если принимающее устройство видит нечетное количество единиц, но бит показывает 0, то это означает ошибку в полученной информации.
Прямая коррекция ошибок
Если есть возможность сразу же запросить и получить ещё одну копию, а ошибки редки, этого приёма вполне достаточно для корректной передачи информации. Но при хранении данных или малой пропускной способности канала нужна так называемая «прямая коррекция ошибок», то есть избыточных данных должно быть столько, чтобы устройство могло исправить ошибки самостоятельно. Эту технологию в 40-х годах прошлого века разработал Ричард Хэмминг, сотрудник компании «Bell Labs», практически от отчаяния.
Он работал с совсем недавно появившейся десятитонной махиной, которая называлась «компьютер». Видимо, с точки зрения начальства его направление исследований было не самым приоритетным, поэтому время учёному выделялось только на выходных, когда обслуживающий персонал, способный помочь в случае возникновения каких-то проблем, спокойно отдыхал дома после напряжённой трудовой недели. Машина же, обнаружив поврежденные данные в программах Хэмминга, просто прерывала работу и переходила к другим задачам. Учёный находил возмутительным тот факт, что компьютер не мог находить и впоследствии устранять ошибки. Поэтому он придумал, как с этим бороться. Он выдвинул идею, получившую известность как «код Хэмминга». Она заключается в том, чтобы пометить все блоки данных несколькими битами четности. Каждый из них отвечает за проверку различных комбинаций битов данных.
То есть один, допустим, проверяет первый, второй и пятый бит данных, второй - первый, третий и четвертый, и так далее. В конечном итоге можно добиться того, чтобы сверялась достоверность всех нулей и единиц, обычно даже по несколько раз. В этом случае каждый бит четности говорит о том, какой должна быть сумма конкретно его комбинации битов. И когда принимающее устройство замечает несоответствия, все эти перекрёстные шаблоны подсказывают, что нужно изменить для восстановления математической гармонии.
Коды Рида-Соломона
Коды Хэмминга просты, быстры и занимают мало места, поэтому они до сих пор популярны в ЕСС-чипах (память с коррекцией ошибок). Но они не способны исправить сразу несколько ошибок одновременно. Эта проблема решается семейством более мощных алгоритмов, именуемых кодами Рида-Соломона. Первое заметное для публики использование этих кодов состоялось в 70-х, в процессе передачи изображений высокого разрешения с космических аппаратов «Вояджер».
Они не делают различия между битами данных и четности, а по существу превращают каждый отправленный кусочек информации в некий маркер, который содержит полезное описание всего сообщения. Результат достигается посредством интерпретации исходных данных не как чисел, а как точек на математической кривой. Чтобы обеспечить избыточность данных, отправитель сообщения размещает несколько дополнительных точек внутри той же кривой.
Таким образом, даже если несколько участков линии повреждены или попросту пропали на пути к получателю, принимающее устройство может легко восстановить правильную форму кривой, а вместе с ней и изначальное сообщение. Коды Рида-Соломона значительно снижают количество неустранимых ошибок. Кроме того, они весьма гибки в использовании - при желании в прорисовываемые кривые можно добавить бессчетное количество избыточных точек. Это, конечно, значительно увеличит объём передающейся информации, но выживаемость ошибок снизится практически до нуля. В этой связи совершенно не удивительно, что эти коды в наше время очень популярны.
Это они помогают считывать информацию с разорванных пополам QR-кодов и повреждённых жестких дисков, принимать слабый сигнал телевизионным ресиверам и делать многое другое. При желании они могут быть дополнены разнообразными «примочками». Например, в таких несопоставимых по сложности областях электроники, как запись компакт-дисков и связь с космическими аппаратами, биты данных чередуются или перемешиваются после применения кодов Рида-Соломона. Это помогает защититься от масштабных системных ошибок, исправление которых перегружало бы код. Если вы, допустим, сильно поцарапаете DVD-диск, все повреждённые данные в этом случае будут распределены на множество независимо корректируемых блоков.
В последние годы и десятилетия появилось много других кодов, которые используются в самом широком спектре - от Интернета и сотовой связи до кабельного телевидения. В основе большинства их лежат аналогичные концепции. Коды обнаружения и исправления ошибок - это невоспетые и незаметные герои мира цифровых технологий. Не забудьте вспомнить о них с благодарностью, когда будете говорить по мобильному телефону, увидите фотографию, сделанную в космосе и присланную оттуда, или когда просто получите долгожданное письмо на электронный ящик. Ну и, кроме того, теперь вы знаете, что происходит, если со всем этим есть какие-то проблемы.
