Реклама:

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

Чтобы понять, как обращаться с ошибками, необходимо внимательно изучить, что представляют собой эти ошибки. Предположим, что слово состоит из т бит данных, к которым мы дополнительно прибавляем г бит (контрольных разрядов). Пусть общая длина слова составит п бит (то есть п = т + г). Единицу из п бит, содержащую т бит данных и г контрольных разрядов, часто называют кодовым словом.

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

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

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

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

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

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

Представим, что мы хотим разработать код, в котором т бит данных и г контрольных разрядов, позволяющий исправлять все одиночные битовые ошибки. Каждое из 2т допустимых слов имеет п недопустимых кодовых слов, которые отличаются от допустимого одним битом. Они образуются инвертированием каждого из п бит в и-разрядном кодовом слове. Следовательно, каждое из 2т допустимых слов требует п + 1 возможных сочетаний битов, приписываемых этому слову (п возможных ошибочных вариантов и один правильный). Поскольку общее число различных сочетаний битов равно 2", то (п + 1) 2т < 2п. Так как п = т + г, то (т + г + 1) < 2Г. Эта формула дает нижний предел числа контрольных разрядов, необходимых для исправления одиночных ошибок. В табл. 2.2 показано необходимое количество контрольных разрядов для слов разного размера.

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

Размер исходного

Количество

Общий размер

Процент

слова

контрольных разрядов

слова

увеличения слова

Этого теоретического нижнего предела можно достичь, используя метод Ричарда Хэмминга [85]. Но прежде, чем обратиться к указанному алгоритму, давайте рассмотрим простую графическую схему, которая четко иллюстрирует идею кода исправления ошибок для 4-разрядных слов. Диаграмма Венна на рис. 2.11 содержит 3 круга, Л, В и С, которые вместе образуют семь секторов. Давайте закодируем в качестве примера слово из 4 бит 1100 в сектора АВ, АБС, АС и ВС, по одному биту в каждом секторе (в алфавитном порядке). Подобное кодирование иллюстрирует рис. 2.11, а.

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

Рис. 2.11. Кодирование числа 1100 (а); добавляются биты четности (б); ошибка в секторе АС (е)

Далее мы добавим бит четности к каждому из трех пустых секторов, чтобы сумма битов в каждом из трех кругов, Д В, и С, получилась четной, как показано на рис. 2,11, б. В круге А находится 4 числа: 0, 0, 1 и 1, которые в сумме дают четное число 2. В круге В находятся числа 1, 1, 0 и 0, которые также при сложении дают четное число 2. Аналогичная ситуация и для круга С. В данном примере получилось так, что все суммы одинаковы, но вообще возможны случаи с суммами 0 и 4. Рисунок соответствует кодовому слову, состоящему из 4 бит данных и 3 бит четности.

Предположим, что бит в секторе АС изменился с 0 на 1, как показано на рис. 2.11, в. Компьютер обнаруживает, что круги А и С являются нечетными. Единственный способ исправить ошибку, изменив только один бит, - возвращение значения 0 биту в секторе АС. Таким способом компьютер может исправлять одиночные ошибки автоматически.

А теперь посмотрим, как может использоваться алгоритм Хэмминга при создании кодов исправления ошибок для слов любого размера. В коде Хэмминга к слову, состоящему из т бит, добавляются г бит четности, при этом образуется слово длиной т + г бит. Биты нумеруются с единицы (а не с нуля), причем первым считается крайний левый. Все биты, номера которых - степени двойки, являются битами четности; остальные используются для данных. Например, к 16-разрядному слову нужно добавить 5 бит четности. Биты с номерами 1, 2, 4, 8 и 16 - биты четности, все остальные - биты данных. Всего слово содержит 21 бит (16 бит данных и 5 бит четности). В рассматриваемом примере мы будем использовать проверку на четность (выбор произвольный).

Каждый бит четности позволяет проверять определенные битовые позиции. Общее число битов со значением 1 в проверяемых позициях должно быть четным. Ниже указаны позиции проверки для каждого бита четности:

♦ бит 1 проверяет биты 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21;

♦ бит 2 проверяет биты 2, 3, 6, 7, 10, И, 14, 15, 18, 19;

♦ бит 4 проверяет биты 4, 5, 6, 7, 12, 13, 14, 15, 20, 21;

♦ бит 8 проверяет биты 8, 9, 10, 11, 12, 13, 14, 15;

♦ бит 16 проверяет биты 16, 17, 18, 19, 20, 21.

В общем случае бит Ъ проверяется битами Ьь Ь2,Ьр такими, что Ьх + Ь2 + ... + + й; = Ь. Например, бит 5 проверяется битами 1 и 4, поскольку 1+4 = 5. Бит 6 проверяется битами 2 и 4, поскольку 2 + 4 = 6 и т. д.

Рисунок 2.12 иллюстрирует построение кода Хэмминга для 16-разрядного слова 1111000010101110. Соответствующим 21-разрядным кодовым словом является 001011100000101101110. Чтобы понять, как происходит исправление ошибок, рассмотрим, что произойдет, если бит 5 изменит значение (например, из-за резкого скачка напряжения). В результате вместо кодового слова 001011100000101101110 получится 001001100000101101110. Будут проверены 5 бит четности. Вот результаты:

♦ неправильный бит четности 1 (биты 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 содержат пять единиц);

♦ правильный бит четности 2 (биты 2, 3, 6, 7, 10, 11, 14, 15, 18, 19 содержат шесть единиц);

+ неправильный бит четности 4 (биты 4, 5, 6, 7, 12, 13, 14, 15, 20, 21 содержат пять единиц);

♦ правильный бит четности 8 (биты 8, 9, 10, 11, 12, 13, 14, 15 содержат две единицы);

♦ правильный бит четности 16 (биты 16, 17, 18, 19, 20, 21 содержат четыре единицы).

Общее число единиц в битах 1, 3, 5, 7, 9, И, 13, 15, 17, 19 и 21 должно быть четным, поскольку в данном случае используется проверка на четность. Неправильным должен быть один из битов, проверяемых битом четности 1 (а именно 1, 3, 5, 7, 9, И, 13, 15, 17, 19 и 21). Бит четности 4 тоже неправильный. Это значит, что изменил значение один из следующих битов: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21. Ошибка должна быть в бите, который содержится в обоих списках. В данном случае общими являются биты 5, 7, 13, 15 и 21. Поскольку бит четности 2 правильный, биты 7 и 15 исключаются. Правильность бита четности 8 исключает наличие ошибки в бите 13. Наконец, бит 21 также исключается, поскольку бит четности 16 правильный. В итоге остается бит 5, в котором и кроется ошибка. Поскольку этот бит имеет значение 1, он должен принять значение 0. Именно таким образом исправляются ошибки.

Рис. 2.12. Построение кода Хэмминга для слова 1111000010101110 добавлением к битам данных пяти контрольных разрядов

Чтобы найти неправильный бит, сначала нужно подсчитать все биты четности. Если они правильные, ошибки нет (или есть, но ошибка не однократная). Если обнаружились неправильные биты четности, нужно сложить их номера. Сумма, полученная в результате, даст номер позиции неправильного бита. Например, если биты четности 1 и 4 неправильные, а 2, 8 и 16 правильные, то ошибка произошла в бите 5(1 +4).

Упорядочение байтов || Оглавление || Кэш-память