Теория информационных систем. Страница 13.

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

Все данные, с которыми могут работать современные вычислительные системы, представляют собой последовательности битов, поэтому все правила, которые мы далее будем рассматривать, распространяются только на такие последовател ьности.

Простейший из применяемых способов кодирования с обнаружением ошибок — это бит четности. Блок данных снабжается дополнительным битом, значение которого выбирается так, чтобы общее количество битов, равных единице, в блоке было четным. Такой код позволяет обнаруживать ошибки в одном бите блока, но не в двух битах (строго говоря — позволяет обнаруживать нечетное количество ошибочных битов). Если вероятность ошибки в двух битах достаточно велика, нам следует либо разбить блок на два блока меньшего размера, каждый со своим битом четности, либо использовать более сложные схемы кодирования.

Самая распространенная из таких более сложных схем — это CRC (Cyclic Redundancy Code, циклический избыточный код). При вычислении CRC разрядности N выбирают число R требуемой разрядности и вычисляют остаток от деления на R блока данных (рассматриваемого как единое двоичное число), сдвинутого влево на N битов. Двоичное число, образованное блоком данных и остатком, делится на R, и этот факт можно использовать для проверки целостности блока (но не для восстановления данных при ошибке!).

Способность контрольной суммы обнаруживать ошибки логичнее измерять не в количестве ошибочных битов, а в вероятности необнаружения ошибки. При использовании CRC будут проходить незамеченными лишь сочетания ошибок, удовлетворяющие весьма специальному условию, а именно такие, вектор ошибок (двоичное число, единичные биты которого соответствуют ошибочным битам принятого блока, а нулевые — правильно принятым) которых делится на R. При случайном распределении ошибок вероятность этого может быть грубо оценена как 1/R, поэтому увеличение разрядности контрольной суммы в сочетании с выбором простых R обеспечивает достаточно быстрый и дешевый способ проверки целостности даже довольно длинных блоков. 32- разрядный CRC обеспечивает практически полную гарантию того, что данные не были повреждены, а 8-разрядный — уверенность, достаточную для многих целей. Однако ни четность, ни CRC не могут нам ничем помочь при восстановлении поврежденных данных.

Простой метод кодирования, позволяющий не только обнаруживать, но и исправлять ошибки, называется блочной или параллельной четностью и состоит в том, что мы записываем блок данных в виде двухмерной матрицы и подсчитываем бит четности для каждой строки и каждого столбца. При одиночной ошибке, таким образом, мы легко можем найти бит, который портит нам жизнь. Двойные ошибки такая схема кодирования может обнаруживать, но не способна восстанавливать (рис. 1.9).