Право на ошибку

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

Любопытный тест устроили журналисты британского издания Digital Camera Shopper такому хрупкому продукту ИТ-индустрии как карта флэш-памяти. Взяв образчики "флэшек" пяти популярных стандартов - CompactFlash, Memory Stick, SecureDigital, SmartMedia и xD - они подвергли их ряду испытаний, назвать которые иначе как изуверскими не поворачивается язык. Карты замачивали в ледяной газировке и кипящем кофе, их проворачивали в стиральной машине, по ним топтались и ездили, наконец, их плющили кувалдой и пробивали гвоздями. Так вот за исключением последних двух тестов, модули выдержали все испытания. Кувалду и гвоздь без потери работоспособности не пережила ни одна карточка, но и после этого специалисты по восстановлению данных сумели считать информацию, хранившуюся на картах xD и Smartmedia. Представьте теперь, что сталось бы с носителями десятилетней давности - магнитными дискетами и лентой! Но благодарить за надёжность следует не только и не столько электронщиков, сколько математиков, последние полвека трудившихся над совершенствованием механизмов коррекции ошибок.

Пользуясь сегодня "флэшками" и оптическими дисками, просматривая великолепные фотоснимки, переданные автоматическими станциями с расстояний в сотни миллионов километров, большинство из нас знает о математической подоплёке всего этого цифрового великолепия меньше, чем о технической стороне. Между тем сама возможность коррекции ошибок при передаче информации была теоретически обоснована лишь немногим более пятидесяти лет назад: в 1948 году Клод Шеннон, заложивший основы теории информации, сформулировал теорему, названную впоследствии в его честь. Теорема Шеннона не оговаривает как именно конструировать механизм коррекции, но демонстрирует возможность осуществления таковой и устанавливает предел эффективности методов коррекции ошибок. Честь практического воплощения идей Шеннона принадлежит нескольким математикам, в числе которых Ричард Хэмминг, Марсель Голэй и некоторые другие.

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

Как уже отмечалось выше, обнаружение ошибок позволяет диагностировать проблему, но не исправить её. Появление накопителей на жёстких магнитных дисках, оснащённых сравнительно более сложной управляющей электроникой, реанимировало интерес к методам коррекции ошибок. Код Хэмминга и более современный метод Рид-Соломона (Reed-Solomon) - классические примеры таких алгоритмов, получившие широкое распространение в ИТ-индустрии в конце XX века. Общий принцип их действия сводится к перекодированию некоторого небольшого объёма данных (обычно от нескольких десятков до 255 байт) с одновременным добавлением в него избыточной информации. Теория информации утверждает, что ошибки проявляются неравномерно, "вспышками", поэтому кодировать информацию блоками, а не - к примеру - побайтно оказывается лучшим решением. Именно метод Рид-Соломона используется в современных винчестерах и на оптических дисках. Когда это возможно, данные разносят по поверхности носителя, что ещё больше повышает устойчивость к повреждениям. Результирующая надёжность столь высока, что, к примеру, большинство ошибок при чтении с CD возникают из-за механического несовершенства аппаратуры, а не по причине царапин на поверхности диска. Старину CD можно пробивать гвоздями поперечником в 2.5 мм и это никак не отразится на сохранности данных.

Впрочем, эволюция методов коррекции ошибок продолжается и к настоящему моменту появилось уже третье их поколение, самым известным представителем которого является турбокодирование (Turbo codes). Упомянутая выше теорема Шеннона определяет одну интересную вещь: т.н. предел Шеннона, который является максимальной скоростью передачи информации через канал с некоторой определённой степенью зашумлённости. Прелесть алгоритмов коррекции ошибок третьего поколения в том, что они требуют чрезвычайно малой избыточности - и при передаче данных позволяют держаться максимально близко к пределу Шеннона. Говоря проще, обработанный турбокодами объём данных увеличится в объёме весьма незначительно. Это крайне ценное свойство, благодаря которому такие алгоритмы коррекции ошибок уже нашли применение в космической технике (передача информации на дальние расстояния потребует меньше времени и энергии), в телекоммуникациях на Земле (высокоскоростная передача данных через сети сотовой связи), несомненно найдут и в персоналках (носители будущего смогут вместить больше полезной информации).

Ну а что же модули флэш-памяти? "Флэшки", с которых начинался сегодняшний рассказ, являют собой едва ли не самый замечательный пример использования алгоритмов коррекции ошибок. Как известно, ресурс работы таких микросхем ограничен - физически они способны выдержать обычно не более сотни тысяч циклов записи. И если в документации на "флэшку" говорится про миллион циклов, знайте, что это стало возможным только благодаря применённому механизму коррекции (обычно второго поколения - кодирование Хэмминга).