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

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

Для отслеживания и исправления ошибок в машинное слово добавили проверочные биты. Про машинное слово читать здесь.

Машинное слово и проверочные биты образуют кодовое слово.

Существует два типа ошибок в словах:

Одиночные – компьютер исправляет их сам.

Множественные – исправляются с помощью алгоритмов восстановления.

Слова отличаются друг от друга позициями нулей и единиц. Количество отличных позиций, называется интервалом Хэмминга.

Пример: 110100OO и 110100II – интервал Хэмминга равен двум.

Наш интервал равен D, тогда чтобы из слова 11000000 получилось слово 11000110, нужно D одноразрядных ошибок.

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

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

Для этого создается код Хэмминга: к слову длинной N бит добавляется R бит чётности, чтобы общее число битов со значением 1 – было чётным.

Пример:

В секторы AB, ABC, AC, BC запишем число 1100.

Круги A и B имеют четное количество единиц, а круг C – нет.

Добавили биты чётности.
A – 1 + 1 + 0 + 0 = 2.
B – 1 + 1 + 0 + 0 = 2.
C – 0 + 1 + 0 + 1 = 2.

Биты, чьи номера степени двойки – биты чётности, остальные биты для данных.

К 16-разрядному слову 1111000010101110 добавляются пять битов чётности, получается 21-разрядный код Хэмминга 001011100000101101110.

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

Получается:
Бит чётности 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.

Например, если из-за скачка напряжения пятый бит станет равным 0, то биты чётности 1 и 4 станут неправильными.

1. Неправильный бит чётности 1: биты 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 содержат 5 единиц.
2. Правильный бит четности 2: биты 2, 3, 6, 7, 10, 11, 14, 15, 18, 19 содержат 6 единиц.
3. Неправильный бит четности 4: биты 4, 5, 6, 7, 12, 13, 14, 15, 20, 21 содержат 5 единиц.
4. Правильный бит четности 8: биты 8, 9, 10, 11, 12, 13, 14, 15 содержат 2 единицы.
5. Правильный бит четности 16: биты 16, 17, 18, 19, 20, 21 содержат 4 единицы.

Компьютер узнаёт об ошибке и выявляет неправильные биты чётности: 1 и 4.
Из них выбираются общие биты: 5, 7, 13, 15, 21.

Бит 7 проверяется так же битом чётности 2 – он правильный, ошибка не в нём.
Бит 13 и 15 проверяется битом чётности 8 – он правильный, ошибка не в этих битах.
Бит 21 проверяется битом чётности 16 – он правильный, ошибка не в нём.

Из списка всех возможных ошибочных битов: 5, 7, 13, 15, 21 – остался только бит 5, в нём и ошибка.

Чтобы найти неправильный бит: нужно подсчитать все биты чётности, если они правильные, то ошибки нет или она не однократная.

Если биты чётности неправильные – сложить их номера, получится номер позиции неправильного бита.

В следующей статье рассмотрим кэш–память.