Назад (Информатика).

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

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

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

Код с контролем четности

Существует достаточно простой способ определения ошибок, построенный на том принципе, что если каждая обрабатываемая битовая комбинация будет состоять из четного количества единиц, то обнаружение комбинации с нечетным количеством единиц будет свидетельствовать о возникновении ошибки.

Чтобы использовать этот принцип, необходимо создать систему, в которой любая битовая комбинация будет содержать четное количество единиц. Обычно это достигается путем добавления к уже существующему коду дополнительного бита [который называется битом четности или контрольным битом], чаще всего помещаемого в старший конец комбинации. В результате восьмиразрядный код ASCII превращается в девятиразрядный, а шестнадцатиразрядная битовая комбинация в двоичном дополнительном коде становится семнадцатиразрядной. В каждом случае значение бита четности устанавливается равным 0 или 1, исходя из требования, чтобы вся битовая комбинация в целом содержала нечетное количество единиц. Напрмер, символ А в коде ASCII будет представлен как 101000000 [бит четности равен 0], тогда как символ F в этом же коде будет иметь вид 001000111 [бит четности равен 1]. Хотя исходная восьмиразрядная комбинация, представляющая букву А, содержит четное количество единиц, а аналогичная комбинация, представляющая букву F, - нечетное количество единиц, оба девятиразрядных кода имеют четное количество единиц. Если система будет построена указанным образом, то появление битовой комбинации с нечетным количеством единиц будет свидетельствовать об ошибке и сигнализировать, что обрабатываемые данные являются неверными.

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

Длинные битовые комбинации часто дополняются группой контрольных битов, образующих контрольный байт. Каждый бит в этом байте является контрольным и относится к определенной группе битов, разбросанных по основной битовой комбинации. Например, один контрольный бит может относиться к каждому восьмому биту, начиная с первого, тогда как другой - к каждому восьмому биту, начиная со второго, и т.д. В данном случае легче выявить ошибки, сконцентрированные в одной области исходной комбинации, поскольку их наличие будет контролироваться группой контрольных битов. Различные варианты данного подхода к созданию схем контроля называются методом контрольных сумм и методом использования кода циклического контроля избыточности [CRC].

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

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

Для того чтобы понять принцип действия этого кода, сначала необходимо определить дистанцию Хемминга между двумя кодовыми комбинациями, которая будет равна количеству битов, отличающихся в этих комбинациях. Понятие дистанция Хемминга получило свое название в честь Р.В. Хемминга [R.W. Hamming], который провел первые исследования в области разработки кодов с исправлением ошибок. Он обратился к этой проблеме в 1940-х годах по причине крайней ненадежности существовавших в то время релейных вычислительных машин. Рассмотрим следующий код:

A 000000
B 001111
C 010011
D 011100
E 100110
F 101001
G 110101
H 111010

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

Если в любой комбинации возникла одиночная ошибка, то легко можно вычислить ее исходное значение. Дело в том, что дистанция Хемминга для измененной комбинации по отношению к исходной форме будет равна единице, тогда как по отношению к другим разрешенным комбинациям она будет равна не менее чем двум. При декодировании некоторого сообщения достаточно просто сравнивать каждую полученную битовую комбинацию с допустимыми комбинациями кода, пока не будет найдена комбинация, находящаяся на дистанции, равной единице, от полученной комбинации. Найденная допустимая кодовая комбинация принимается за правильный символ, полученный в результате декодирования. Предположим, что получена битовая комбинация 010100. Если сравнить ее с допустимыми битовыми комбинациями кода, то будет получена таблица дистанций:

A 2
B 4
C 3
D 1
E 3
F 5
G 2
H 4

По содержанию этой таблицы можно сделать заключение, что поступивший символ - это буква D, так как ее битовая комбинация в наибольшей степени соответствует полученной.