Контрольные суммы
Простейший из применяемых способов кодирования с обнаружением ошибок - это бит четности. Блок данных снабжается дополнительным битом, значение которого выбирается так, чтобы общее количество битов, равных единице, в блоке было четным. Такой код позволяет обнаруживать ошибки в одном бите блока, но не в двух битах. Если вероятность ошибки в двух битах достаточно велика, можно разбить блок на два блока меньшего размера, каждый со своим битом четности.
Простой метод кодирования, позволяющий не только обнаруживать, но и исправлять ошибки, называется блочной или параллельной четностью и состоит в том, что мы записываем блок данных в виде двухмерной матрицы и подсчитываем бит четности для каждой строки и каждого столбца. При одиночной ошибке можно найти бит, который портит нам жизнь. Двойные ошибки такая схема кодирования может обнаруживать, но не способна восстанавливать.
Известный и применяемый код Хэмминга (Hamming code) находится в близком родстве с параллельной четностью.
|