Коды с обнаружением и исправлением ошибок

Компьютер при передаче данных между устройствами и при выполнении вычислений может делать ошибки из-за сбоев и отказов аппаратуры. Если компьютер не оснащен средствами для обнаружения и исправления ошибок, то необнаруженные ошибки приводят к сколь угодно серьезным искажениям результатов вычислений, и компьютер становится источником дезинформации пользователей. В связи с этим большинство компьютеров оснащаются средствами, обеспечивающими контроль работоспособности аппаратуры компьютеров за счет увеличения длины байтов, слов и сегментов данных на некоторое число битов, с помощью которых обеспечивается возможность обнаружения и исправления ошибок в передаваемых и обрабатываемых данных, т.е. за счет использования специальным образом представленных данных – кодированных байтов, слов и сегментов.

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

10110011.

Бит четности формируется за счет присоединения к байту одного бита, формируемого следующим образом: если число единиц в байте четно, то бит четности равен 0, если число единиц в байте нечетно, то бит четности равен 1. Таким образом, указанный байт с битом четности имеет следующую структуру:

10110011 1 ,

Байт Бит

четности

где бит имеет значение 1. Ясно, что при указанном правиле вычисления значения бита четности, число битов в кодированном байте всегда четно, в результате чего всякая одиночная ошибка в кодированном байте будет обнаружена. Впрочем, будут обнаружены и 3-, 5-, 7- и 9-кратные ошибки, но не поддаются обнаружению 2-, 4- и 8- кратные ошибки. Бит четности формируется аппаратурой компьютера крайне просто и обеспечивает защиту от многих ошибок.

Для обнаружения и исправления ошибок теория информации предлагает значительное число различных методов. Ясно, что с увеличением длины данных, определяемой длиной битов в данных, должно увеличиваться число контрольных разрядов, присоединяемых к данным для обнаружения и исправления ошибок. Число контрольных разрядов, необходимое для кода, способного обнаруживать и исправлять ошибки по методу Хэмминга, представлено в табл. 3.1.

Таблица 3.1.Число контрольных разрядов кода, способного обнаруживать и исправлять ошибки

Из таблицы видно, что для обнаружения и исправления одиночной ошибки к байту данных необходимо добавить четыре контрольных разряда, в результате чего длина кодирование сегмента данных будет равна 12 разрядам при увеличении длины кодирования сегмента на 50%. Из последующих строк таблицы видно, что при увеличении длины сегмента в 2 раза, количество контрольных разрядов увеличивается только на единицу, в результате чего процент увеличения длины данных уменьшается. При длине данных 1024 битов для исправления одиночных ошибок необходимо всего 11 разрядов, что приводит к увеличению длины контрольного сегмента всего на 1%. Естественно, что затраты оборудования для обнаружения и исправления единственной ошибки по методу Хэмминга значительно больше затрат оборудования при использовании бита четности. Однако при этом достигается существенный эффект – возможность исправления одной ошибки в работе компьютера.

Наряду с кодами Хэмминга, обеспечивающими обнаружение и исправление одной, двух и более ошибок в кодированных словах, широкое применение получили циклические коды, имеющие широкие возможности обнаружения и исправления при сложной картине многократных помех и достаточно простых способах построения систем контроля кодированных слов. Кодированные слова используются и для контроля арифметических и логических операций, выполняемых процессором. Таким образом, существует широкая гамма методов защиты устройств компьютеров от всякого рода искажений обрабатываемых и передаваемых данных, но любые системы защиты не дают 100% гарантии в результативности методов защиты.