Насколько часто приходится среднему пользователю выполнять операции пересылки и хранения информации? Пожалуй, десятки раз в день. Цель этих действий - перенести информацию с одного места (например, ваш винчестер) на другое (хост - машина в двадцати километрах от вас) посредством некоторого канала связи (телефонная линия), и перенести без ошибок. А, между тем, именно в каналах связи вероятность искажения данных очень высока. Даже если вы работаете по оптоволокну или выделенной линии, она далеко не нулевая. А уж по телефонному каналу...

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

Рассмотрим, как это происходит, на примере самого распространенного исправляющего кода - CRC, или циклического кода. Этот код, в частности, используется не только при пересылке данных, но и при архивации (операция хранения), например, архиватором RAR.

Для начала вспомним, как работает битовая операция XOR. Если значения битов, над которыми она выполняется, различны (0 и 1), то результат - 1, иначе - 0.

Теперь посмотрим, что происходит с пересылаемой вами информацией, пока вы спокойно похлебываете кофеек в ожидании окончания перекачки. Пусть, например, кодирование происходит словами по n=4 бита, а ширина закодированного слова k=9 бит. Важную роль в процессе кодирования играет так называемое порождающее кодовое слово. В нашем примере это будет g=10011. Заметим, одно из требований к порождающему слову - его длина равна k-n. Вообще, эффективность кодирования сильно зависит от выбора этой константы, но сам процесс выбора - задача сложная, и мы не будем подробно ее рассматривать.

Пусть в данный момент передается слово u=1101. Для начала к u справа приписывается k-n (9-4=5) нулей. Получаем слово t=110100000. Теперь необходимо разделить t на порождающее кодовое слово. Как это делается? Да точно так же, как обычное деление "уголком" (надеюсь, увлечение компьютерами не заставило вас забыть, КАК это делается), только вместо вычитания используется операция XOR (см. рис. 1). Теперь необходимо к t прибавить остаток от деления (см. рис. 2). Получившееся в результате слово f=110101000 и будет передано по каналу связи. Нетрудно определить, что его старшие n бит - это передаваемая нами информация.

Теперь внесем в f ошибку и посмотрим, как она будет исправлена при декодировании. Пусть, например, исказился старший бит. Проделаем деление образовавшегося слова f'=010101000 на g (см. рис. 3). Ошибка определяется по наличию остатка от деления (f делилось на g без остатка). Бит, в котором произошла ошибка, определяется по значению остатка (пытливый читатель может последовательно внести ошибки во все 9 бит и убедиться, что остатки при этом всегда получаются разные).

Этот код может исправлять однократные и обнаруживать двухкратные ошибки. В принципе, можно построить код, который исправляет ошибки любой заранее известной кратности. Но при повышении кратности исправляемой ошибки на 1 закодированные слова также становятся шире, а, значит, падает скорость передачи данных. Так что используемый код в основном определяется, исходя из характеристик конкретного канала (не имеет смысла исправлять 3-х кратные ошибки, если вероятность их возникновения - 10е-10).

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

Денис МАРГОЛИН