Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.69

Рис. 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 содержат шесть единиц);