Вопросы (стр. 6 )

Сначала определим требуемую длину корректирующего кода. В соответствии с рис., на вход схемы сравнения поступают два К-разрядных значения. Срав­нение производится путем поразрядной операции «исключающее ИЛИ» (сложе­ние по модулю 2) над входными кодами. Результатом является так называемое слово синдрома. В зависимости от того, было ли совпадение входных кодов или нет, соответствующий бит синдрома будет равен 0 или 1.

Слово синдрома состоит из К разрядов, то есть его возможные значения лежат в диапазоне от 0 до 2К - 1. Значение 0 соответствует случаю, когда ошибки не об­наружено, остальные 2К — 1 случая свидетельствуют о наличии ошибки и указывают на ее местоположение.

Поскольку ошибка может возникнуть в любом из М битов данных или К контрольных битов, мы должны иметь 2к - 1 > М + К. Это выраже­ние позволяет определить число битов, необходимое для исправления одиночной ошибки в М-разрядных данных. В нашем примере, для 8-разрядных слов требуется четыре корректирующих разряда.

Для удобства будем формировать четырехразрядный синдром со следующими характеристиками:

- Если синдром содержит все нули, значит, не обнаружено ни одной ошибки.

- Если синдром содержит единственную единицу в одном из разрядов, это озна­чает, что выявлена ошибка в одном из четырех корректирующих разрядов и ни­какой коррекции не требуется.

- Если в синдроме в единичное состояние установлены несколько битов, то чис­ленное значение синдрома соответствует позиции ошибки в данных, для исправ­ления которой необходимо инвертировать бит в этой позиции (нумерация с единицы!).

Для поддержания этих свойств под контрольные разряды отводятся те биты, чьи позиционные номера пред­ставляют собой степень числа 2 (табл. 2). Отдельный контрольный разряд от­вечает за определенные биты данных. Так, разрядная позиция п контролируется теми битами Рi, которые делают справедливым соотношение = п. Например, раз­ряд данных с позиционным номером контролируется битами 4, 2 и 1 (7 = 4 + 2 + 1), а разряд с номером 1битами 8 и 2 (10 = 8 + 2).

Таблица 2. Распределение разрядов 12-разрядного слова между данными и контрольным кодом

Десятичный номер позиции	12	11	10	9	8	7	6	5	4	3	2	1
Двоичный код номера позиции	1100	1011	1010	1001	1000	0111	0110	0101	0100	0011	0010	0001
Биты данных	D8	D7	D6	D5		D4	D3	D2		D1
Контрольные биты					Р8				Р4		Р2	Р1

Таким образом, для рассматриваемого случая значения контрольных разрядов вычисляются по следующим правилам:

Проверим корректность такой схемы на примере. Пусть входной код равен . Контрольные разряды вы­числяются следующим образом:

Предположим, что данные в бите 3 содержат ошибку и там вместо 0 находит­ся 1. После пересчета контрольных разрядов имеем

Путем сложения по модулю двух результатов старой и новой проверок полу­чим слово синдрома (S8S4S2S1) =0110.

Результат 01означает, что в разряде 6, содержащем третий бит данных, присутствует ошибка.

Описанный код называется кодом с исправлением одиночной ошибки (SEC — Single Error Correcting). В большинстве микросхем памяти используется код с ис­правлением одиночной и обнаружением двойной ошибки (SECDED — Single Error Correcting, Double Error Detecting). Такой код требует одного дополнительного контрольного разряда, который вычисляется путём суммирования по модулю 2 всех остальных контролирующих разрядов (формируемых по принципам, изложенным выше) и разрядов данных. Анализ ошибки ведётся по табл. 3:

Таблица 3. Обнаружение ошибок с использованием кода SECDED

Синдром	Доп. контр. разряд	Тип ошибки	Примечания
0	0	Ошибки нет
≠0	1	Одиночная ошибка	Корректируемая: синдром указывает на позицию искаженного разряда
≠0	0	Двойная ошибка	Неисправимая
0	1	Ошибка в доп. контрольном разряде	Искажен доп. контрольный разряд, и он может быть откорректирован

33)Аппаратные методы контроля арифметических и логических операций.

При аппаратном контроле вводится избыточность – дополнительные разряды, используемые для контроля. Аппаратный контроль может осуществляться следующим образом (ОР – основные разряды, КР – контрольные разряды):

Классическая схема свертки:

F = G. 2) сопоставление – на равенство.

Можно вместо КР использовать ОР – то есть, получаем дублирование (по крайней мере, это один из возможных режимов). Если идет речь об обнаружении и исправлении ошибок, то дублирование не спасет.

В основе корректирующих кодов лежит следующая идея. Для кон­троля двоичного информационного кода длиной М бит добавим к ней К дополни­тельных контрольных разрядов. В этом случае из возможных N = 2М"К комбинаций интерес представляют только L = 2м последовательностей, которые называют: разрешенными. Оставшиеся N - L последовательностей назовем запрещенными. Если при обработке (записи в память, считывании или передаче) разрешенной кодовой последовательности произойдут ошибки и возникнет одна из запрещенных после­довательностей, то тем самым эти ошибки обнаруживаются. Если же ошибки пре­вратят одну разрешенную последовательность в другую, то такие ошибки не могут быть обнаружены. Благодаря свойствам контрольных разрядов, характерным для конкретных методов контроля, в некоторых случаях возможно определить не только наличие, но и местоположение ошибки, а также произвести её коррекцию.

Простейший вид корректирующего кода основан на добавлении к каждому байту инфор­мации одного бита паритета. Бит паритета — это дополнительный бит, значение которого устанавливается таким, чтобы суммарное число единиц в данных, с уче­том этого дополнительного разряда, было четным (или нечетным). При чтении из памяти вычисляется бит паритета для считанных информационных битов, результат сравнивается с битом па­ритета, вычисленным при записи и хранившимся в памяти. Метод позволяет об­наружить ошибку, если исказилось нечетное количество битов, при четном числе ошибок метод неработоспособен. Данный метод позволяет только обнаруживать ошибки, причём местоположение ошибки остаётся неизвестным.

Более эффективным представляется код, предложенный Ричардом Хэммингом и носящий его имя (код Хэмминга).

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

Сначала определим требуемую длину корректирующего кода. В соответствии с рис., на вход схемы сравнения поступают два К-разрядных значения. Срав­нение производится путем поразрядной операции «исключающее ИЛИ» (сложе­ние по модулю 2) над входными кодами. Результатом является так называемое слово синдрома. В зависимости от того, было ли совпадение входных кодов или нет, соответствующий бит синдрома будет равен 0 или 1.

Слово синдрома состоит из К разрядов, то есть его возможные значения лежат в диапазоне от 0 до 2К - 1. Значение 0 соответствует случаю, когда ошибки не об­наружено, остальные 2К — 1 случая свидетельствуют о наличии ошибки и указывают на ее местоположение.

Поскольку ошибка может возникнуть в любом из М битов данных или К контрольных битов, мы должны иметь 2к - 1 > М + К. Это выраже­ние позволяет определить число битов, необходимое для исправления одиночной ошибки в М-разрядных данных. В нашем примере, для 8-разрядных слов требуется четыре корректирующих разряда.

Для удобства будем формировать четырехразрядный синдром со следующими характеристиками:

- Если синдром содержит все нули, значит, не обнаружено ни одной ошибки.

- Если синдром содержит единственную единицу в одном из разрядов, это озна­чает, что выявлена ошибка в одном из четырех корректирующих разрядов и ни­какой коррекции не требуется.

- Если в синдроме в единичное состояние установлены несколько битов, то чис­ленное значение синдрома соответствует позиции ошибки в данных, для исправ­ления которой необходимо инвертировать бит в этой позиции (нумерация с единицы!).

Для поддержания этих свойств под контрольные разряды отводятся те биты, чьи позиционные номера пред­ставляют собой степень числа 2 (табл. 2). Отдельный контрольный разряд от­вечает за определенные биты данных. Так, разрядная позиция п контролируется теми битами Рi, которые делают справедливым соотношение = п. Например, раз­ряд данных с позиционным номером контролируется битами 4, 2 и 1 (7 = 4 + 2 + 1), а разряд с номером 1битами 8 и 2 (10 = 8 + 2).

Таблица 2. Распределение разрядов 12-разрядного слова между данными и контрольным кодом

Десятичный номер позиции	12	11	10	9	8	7	6	5	4	3	2	1
Двоичный код номера позиции	1100	1011	1010	1001	1000	0111	0110	0101	0100	0011	0010	0001
Биты данных	D8	D7	D6	D5		D4	D3	D2		D1

Таким образом, для рассматриваемого случая значения контрольных разрядов вычисляются по следующим правилам:

P_1=D_1⊕D_2⊕D_4⊕D_5⊕D_7

P_2=D_1⊕D_3⊕D_4⊕D_6⊕D_7

P_4=D_2⊕D_3⊕D_4⊕D_8

P_8=D_5⊕D_6⊕D_7⊕D_8

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

P_1=D_1⊕D_2⊕D_4⊕D_5⊕D_7=1⊕1⊕1⊕0⊕0=1

P_2=D_1⊕D_3⊕D_4⊕D_6⊕D_7=1⊕0⊕1⊕1⊕0=1

P_4=D_2⊕D_3⊕D_4⊕D_8=1⊕0⊕1⊕0=0

P_8=D_5⊕D_6⊕D_7⊕D_8=0⊕1⊕0⊕0=1

Предположим, что данные в бите 3 содержат ошибку и там вместо 0 находиnся 1. После пересчета контрольных разрядов имеем

P_1=D_1⊕D_2⊕D_4⊕D_5⊕D_7=1⊕1⊕1⊕0⊕0=1

P_2=D_1⊕D_3⊕D_4⊕D_6⊕D_7=1⊕1⊕1⊕1⊕0=0

P_4=D_2⊕D_3⊕D_4⊕D_8=1⊕1⊕1⊕0=1

P_8=D_5⊕D_6⊕D_7⊕D_8=0⊕1⊕0⊕0=1

Путем сложения по модулю двух результатов старой и новой проверок полу­чим слово синдрома (S8S4S2S1) =0110.

Результат 01означает, что в разряде 6, содержащем третий бит данных, присутствует ошибка.

Описанный код называется кодом с исправлением одиночной ошибки (SEC — Single Error Correcting). В большинстве микросхем памяти используется код с ис­правлением одиночной и обнаружением двойной ошибки (SECDED — Single Error Correcting, Double Error Detecting). Такой код требует одного дополнительного контрольного разряда, который вычисляется путём суммирования по модулю 2 всех остальных контролирующих разрядов (формируемых по принципам, изложенным выше) и разрядов данных. Анализ ошибки ведётся по табл. 3: