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

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

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

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

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

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

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

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

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

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

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

Размер исходного	Количество	Общий размер	Процент
слова	контрольных разрядов	слова	увеличения слова
8	4	12	50
16	5	21	31
32	6	38	19
64	7	71	11
128	8	136	6
256	9	265	4
512	10	522	2

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

В общем случае бит Ъ проверяется битами Ь_ь Ь₂,fy, такими, что b_t + 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, И, 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. Именно та­ким образом исправляются ошибки.

Слово 1111000010101110 в памяти

1    2   3   4   5   6   7   8   9   10 11  12 13 14 15 16 17 18 19 20 21

                                       Биты четности

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

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

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

 

Источник: Таненбаум Э. Архитектура компьютера. 5-е изд. (+CD). — СПб.: Питер, 2007. — 844 с: ил.

Предлагаю ознакомиться с аналогичными статьями: