Реклама

Мезотерапии без мед образования курсы. Косметолог со средним мед образованием и мезотерапия.

Наш канал:

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

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

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

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

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

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

то (т + г + 1) < 2Г. Эта формула дает нижний предел числа контрольных разрядов, необходимых для исправления одиночных ошибок. В табл. 2.2 показано необходимое количество контрольных разрядов для слов разного размера.

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

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