Простым примером кода с обнаружением одной ошибки является код с битом чётности. Конструкция его такова: к исходному слову добавляется бит чётности. Если в исходном слове число единичек чётно, то значение этого бита 0 (для контроля нечетности - 1), если нечётно — 1 (для контроля нечетности - 0). Таким образом допустимые слова этого кода имеют чётное количество единичек. Если получено слово с нечётным (для контроля нечетности - четным) количеством единичек, то при передаче произошла ошибка.
При этом допускается, что может возникнуть только одна ошибка. В самом деле, для случая четности правильным будет только половина возможных комбинаций. Чтобы одна допустимая комбинация превратилась в другую, должно возникнуть, по крайней мере, два нарушения или четное число нарушений.
Таблица 3.1 Пример реализации метода четности
Число | Контрольный разряд | Проверка |
1-нарушение |
Такое кодирование имеет минимальное кодовое расстояние, равное 2.
Можно представить и несколько видоизмененный способ контроля по методу четности – нечетности. Длинное число разбивается на группы. Контрольные разряды выделяются всем группам по строкам и по столбцам согласно следующей схеме:
Таблица 3.2 - Видоизмененный способ контроля по четности-нечетности
а 1 | а 2 | а 3 | а 4 | а 5 | k1 |
а 6 | a7 | a8 | a9 | а10 | k2 |
а11 | а12 | а13 | а14 | а15 | K3 |
а16 | а17 | а18 | а19 | а20 | k4 |
а21 | а22 | а23 | а24 | а25 | k5 |
k6 | k7 | k8 | k9 | k10 |
Увеличение избыточности информации приводит к тому, что появляется возможность не только обнаружить ошибку, но и исправить её. В самом деле, пусть произошла неисправность в каком-то из разрядов этого числа (представим, что разряд а18 изменил состояние, т.е. а18=1). Это приводит к тому, что при проверке на четность сумма
по соответствующим строкам изменится для значений, которые содержат элемент а18, т.е. это будет четвертая сверху строка и третий слева столбец. Следовательно, нарушение четности по этой строке и столбцу можно зафиксировать, что в конечном счете означает обнаружение не только самой ошибки, но и места, где возникла ошибка. Изменив содержимое отмеченного разряда (в данном случае а18) на противоположное, можно исправить ошибку.
Контроль по методу четности-нечетности широко используют в ЭВМ для контроля записи, считывания информации в запоминающих устройствах на магнитных носителях.
Пример.Определить и исправить ошибку в передаваемой информации вида:
Для контроля использовать метод четности по строкам и столбцам.
Решение. Прежде всего осуществим проверку на четность по каждой строке: k1 = 0; k2 = 1; k3 = 0; k4 = 0; k5 = 1.
Затем проверим на четность информацию по столбцам: k6 = 0; k7 = 1;
k8 = 0; k9 = 1; k10 =0; k11 =1; k12=1.
Проверка показывает, что ошибка возникла в разряде второй строки и второго слева столбца. Следовательно, разряд, содержащий ошибочную информацию, находится на пересечении второй строки и второго столбца.
Ответ: