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

А теперь посмотрим, как может использоваться алгоритм Хэмминга при создании кодов исправления ошибок для слов любого размера. В коде Хэмминга к слову, состоящему из m бит, добавляются r бит четности, при этом образуется слово длиной m + r бит. Биты нумеруются с единицы (а не с нуля), причем первым считается крайний левый. Все биты, номера которых — степени двойки, являются битами четности; остальные используются для данных. Например, к 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, 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.

В общем случае бит b проверяется битами b 1, b₂, ..., bj, такими что b 1 + b₂ + + ... + bj = b. Например, бит 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, 11, 13, 15, 17, 19 и 21 должно быть четным, поскольку в данном случае используется проверка на четность. Неправильным должен быть один из битов, проверяемых битом четности 1 (а именно 1, 3, 5, 7, 9, 11, 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. Именно таким образом исправляются ошибки.