Контрольные суммы
Способность контрольной суммы обнаруживать ошибки логичнее измерять не в количестве ошибочных битов, а в вероятности необнаружения ошибки. При использовании CRC будут проходить незамеченными лишь сочетания ошибок, удовлетворяющие весьма специальному условию, а именно такие, вектор ошибок (двоичное число, единичные биты которого соответствуют ошибочным битам принятого блока, а нулевые – правильно принятым) которых делится на R.
При случайном распределении ошибок вероятность этого может быть грубо оценена как 1/R, поэтому увеличение разрядности контрольной суммы в сочетании с выбором простых R обеспечивает достаточно быстрый и дешевый способ проверки целостности даже довольно длинных блоков. 32 – разрядный CRC обеспечивает практически полную гарантию того, что данные не были повреждены, а 8-разрядный – уверенность, достаточную для многих целей. Однако ни четность, ни CRC не могут нам ничем помочь при восстановлении поврежденных данных.
Простой метод кодирования, позволяющий не только обнаруживать, но и исправлять ошибки, называется блочной или параллельной четностью и состоит в том, что мы записываем блок данных в виде двухмерной матрицы и подсчитываем бит четности для каждой строки и каждого столбца. При одиночной ошибке, таким образом, мы легко можем найти бит, который портит нам жизнь. Двойные ошибки такая схема кодирования может обнаруживать, но не способна восстанавливать (рис. 1.9).
Рис. 1.9. Параллельная четность
Широко известный и применяемый код Хэмминга (Hamming code) находится в близком родстве с параллельной четностью. Его теоретическое обоснование несколько менее очевидно, чем у предыдущего алгоритма, но в реализации он, пожалуй, даже проще [Берлекэмп 1971]. Идея алгоритма состоит в том, чтобы снабдить блок данных несколькими битами четности, подсчитанными по различным совокупностям битов данных.
При выполнении неравенства Хэмминга (1.1) сформированный таким образом код обеспечивает обнаружение и исправление одиночных ошибок либо гарантированное обнаружение (но не исправление!) двойных ошибок. Важно подчеркнуть гарантию обнаружения, в отличие от всего лишь высокой вероятности обнаружения при использовании CRC.
d + р+1<= 2^р, (1.1)
Где d – количество битов данных, р – разрядность контрольного кода.
Код, использующий d и р, при которых выражение (1.1) превращается в равенство, называют оптимальным кодом Хэмминга.
Часто оказывается целесообразно сочетать упаковку данных с их избыточным кодированием. Наиболее удачным примером такой целесообразности опять-таки являются тексты на естественных языках: статистический анализ такого текста показывает очень высокий, более чем двукратный, уровень избыточности. С одной стороны, это слишком "много для большинства практически применяемых способов цифровой передачи и кодирования данных, а с другой – правила формирования этой избыточности слишком сложны и плохо формализованы для использования в современных программно-аппаратных комплексах. Поэтому для длительного хранения или передачи по низкоскоростным линиям целесообразно упаковывать текстовые данные и снабжать их простыми средствами избыточности, например CRC.