Читать «Архитектура компьютера» онлайн - страница 77

Для любых двух кодовых слов, например 10001001 и 10110001, можно определить, сколько соответствующих битов в них отличаются. В данном примере таких бита три. Чтобы определить количество отличающихся битов, нужно над двумя кодовыми словами произвести логическую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ и сосчитать число битов со значением 1 в полученном результате. Число битовых позиций, по которым отличаются два слова, называется интервалом Хэмминга [Hamming, 1950]. Если интервал Хэмминга для двух слов равен d, значит, достаточно d одноразрядных ошибок, чтобы превратить одно слово в другое. Например, интервал Хэмминга для кодовых слов 11110001 и 00110000 равен 3, поскольку для превращения первого слова во второе достаточно трех одноразрядных ошибок.

Память состоит из m-разрядных слов, следовательно, существуют 2^m вариантов сочетания битов. Кодовые слова состоят из n бит, но из-за способа подсчета контрольных разрядов допустимы только 2^m из 2ⁿ кодовых слов. Если в памяти обнаруживается недопустимое кодовое слово, компьютер знает, что произошла ошибка. При наличии алгоритма подсчета контрольных разрядов можно составить полный список допустимых кодовых слов и из этого списка найти два слова, для которых интервал Хэмминга будет минимальным. Это интервал Хэмминга для полного кода.

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

В качестве простого примера кода с обнаружением ошибок рассмотрим код, в котором к данным присоединяется один бит четности. Бит четности выбирается таким образом, чтобы число битов со значением 1 в кодовом слове было четным (или нечетным). Интервал Хэмминга для этого кода равен 2, поскольку любая одноразрядная ошибка приводит к кодовому слову с неправильной четностью. Другими словами, достаточно двух одноразрядных ошибок для перехода от одного допустимого кодового слова к другому допустимому слову. Такой код может использоваться для обнаружения одиночных ошибок. Если из памяти считывается слово с неверной четностью, поступает сигнал об ошибке. Программа выполняться не сможет, но зато не выдаст неверных результатов.

В качестве простого примера кода исправления ошибок рассмотрим код с четырьмя допустимыми кодовыми словами: 0000000000, 0000011111, 1111100000 и 1111111111.

Интервал Хэмминга для этого кода равен 5. Это значит, что он может исправлять двойные ошибки. Если появляется кодовое слово 0000000111, компьютер знает, что изначально это слово выглядело как 0000011111 (если произошло не более двух ошибок). При появлении трех ошибок (например, слово 0000000000 меняется на 0000000111) этот метод не подходит.