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

Память компьютера из-за всплесков напряжения и по другим причинам время от времени может ошибаться.

Чтобы бороться с ошибками, используются специ­альные коды, умеющие обнаруживать и исправлять ошибки.

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

Предположим, что слово состоит из m бит данных, к которым мы дополнительно прибавляем r бит (контрольных разрядов).

Пусть общая длина слова составит n бит (то есть n = m + r). Совокупность из n бит, содержащую m бит данных и r контрольных разрядов, часто называют кодовым словом.

Для любых двух кодовых слов, например 100 010 01 и 101 100 01, можно опре­делить, сколько соответствующих битов в них различаются. В данном примере таких бита три.

Чтобы определить количество различающихся битов, нужно над двумя кодовыми словами произвести логическую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ и сосчитать количество битов со значением 1 в полученном результате.

Число битовых позиций, по которым различаются два слова, называется интер­валом Хэмминга.

Если интервал Хэмминга для двух слов равен d, это значит, что достаточно d битовых ошибок, чтобы превратить одно слово в другое.

На­пример, интервал Хэмминга для кодовых слов 1111 0001 и 0011 0000 равен 3, по­скольку для превращения первого слова во второе достаточно 3 битовые ошибки.

Память состоит из m-разрядных слов, следовательно, существуют 2^твариан­тов сочетания битов.

Кодовые слова состоят из пбит, но из-за способа подсчета контрольных разрядов допустимы только 2^тиз 2ⁿ кодовых слов.

Если в памяти обнаруживается недопустимое кодовое слово, компьютер знает, что произошла ошибка.

В качестве простого примера кода с обнаружением ошибок рассмотрим код, в котором к данным присоединяется один бит четности.

Бит четности выбира­ется таким образом, чтобы число битов со значением 1 в кодовом слове было четным (или нечетным).

Интервал Хэмминга для этого кода равен 2, поскольку любая одиночная битовая ошибка приводит к кодовому слову с неправильной четностью. То есть, достаточно двух одиночных битовых ошибок для перехода от одного допустимого кодового слова к другому допустимому слову.

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

Кроме обнаружения ошибок, коды Хеминга позволяют исправлять обнаруженные ошибки.

Рассмотрим в качестве примера графическую схему, которая иллюстрирует идею кода исправления ошибок для 4-разрядных слов.

Закодируем в качестве примера слово из 4 бит – 1100, записав по одному биту этого слова в сектора АВ, АВС, АС и ВС в алфавитном порядке.

Далее, добавим бит четности к каждому из трех пустых секторов А, В и С, чтобы сумма битов в каждом из этих кругов получилась четной. Таким образом, кодовое слово, будет состоять из 4 бит данных и 3 бит четности.

В круге А находится 4 числа: 0, 0, 1 и 1, которые в сумме дают чет­ное число 2,

В круге В находятся числа 1. 1, 0 и 0, которые также в сумме дают чет­ное число 2.

Аналогичная ситуация и для круга С.

В данном примере получилось так, что все суммы одинаковы, но вообще случае возможны также суммы 0 (все 0) и 4 (все 1).

Компьютер, после считывания кодового слова и подсчета контрольных сумм, обнаруживает, что контрольные суммы для кругов А и С являются нечетными. То есть сумма всех битов принадлежащих А равна 3 и принадлежащих С также равна 3.

Един­ственный способ исправить ошибку, изменить только один бит — возвратить значения 0 биту в секторе АС.

Таким способом компьютер может обнаруживать и исправлять одиночные ошибки автоматически.

Использование алгоритма Хэмминга при соз­дании кодов обнаружения и исправления одиночных ошибок для слов любою размера.

В коде Хэмминга к слову, состоящему из тбит, добавляются rбит четности, при этом образуется слово длиной n=т+rбит.

Биты нумеруются с единицы (а не с нуля), причем пер­вым считается крайний левый.

Все биты, номера которых равны степени двойки, являются битами четности, остальные используются для данных.

Например, к 16-разрядному слову нужно добавить 5 бит четности.

Биты с номерами 1, 2, 4, 8 и 16 — биты четности, все остальные — биты данных. Таким образом кодовое слово содержит 21 бит (16 бит данных и 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,

В общем случае бит bпроверяется битами b₁, b₂ , ... , b_j такими, что b₁ + b₂ + … + b_j = b, b - это номер бита.