Устройство для обнаружения и исправленияОшибОК АРифМЕТичЕСКиХ ОпЕРАций ВСиСТЕМЕ ОСТАТОчНыХ КлАССОВ Советский патент 1981 года по МПК G06F11/08 

(54)

УСТРОЙСТВО для ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Изобретение относится к автоматике и вычислительной технике, в частности может быть использовано для контроля , исправления О1иибки любой кратности при проведении арифметических операций в ЭВМ, работающей в системе остаточных классов. Известно устройство для обнаружения и исправления ошибок в системе остаточных классов, основанное на про цессе нуливизации. Процесс нуливизации за:ключается в последовательном вычитании из представленного числа в системе остаточных классов констант систеыа с целью определения наличия или отсутствия ошибки. Кроме этого, для обнаружения наличия схлибки необходимо в систему оснований ввести одно контрольное основание, а для исправления ошибки необходимо дополнительно ввести еще одно контрольное основание причем каждое из контрольных оснований по величине должно быть больше кажд1ого из рабочих оснований системы {1. Основным недостатком устройства является его низкое быстродействие, так как процесс получения безошибочного числа в устройстве носит последовательный характер и зависит от числа оснований системы счисления. Известно также устройство для обнаружения и исправления ошибок в системе остаточных классов, в котором определение места и величины ошибки производится за счет расширения исходной системы, для чего необходимо вычислить величину неточного ранга 2J. Недостаток этого устройства - его сложность. Наиболее близким по технической сущности к данномуявляется устройство для обнаружения и исправления ошибок арифметических операций в системе остаточных классов, содержащее регистр, вход которого является входом устройства, сумматор, блок памяти, блок определения места ошибки, блок анализа, первый выход которого является первым выходом устройства З. Недостаток его - невозможность обнаруживать и исправлять ошибки, которые могут затронуть больше, чем одно основание. Кроме этого, если такая (Миибка произошла, то устройство, воспринимая эту ошибку как ошибку по одному основанию исправит число, а такое исправление внесет лишь еще одну дополнительную ошибку.

Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения возможности обнаружения исправления любой ошибки.

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

сравнения, четыре группы элементов и,

I

группа элементов ИЛИ, блоки определения места оишбки, логический блок, триггер управления и блок управления, причем первый выход регистра соединен с первым входом логического блока и со входом первого блока модульной свертки, выход которого соединен с первым входом сумматора по контрольному основанию, второй выход регистра соединен со вторым входом логического блока и со вторым входом сумматора по контрольному основанию, выход которого соединен с первым входом схемы срав нения и с первыми входами первой группы элементов И, выход блока управления соединен с первыми входами элементов И второй группы и с первым входом блока памяти, первый выход которо го соединен со входом второго блока модульной свертки и с первыми входами элементов И третьей группы, второй выход блока памяти через вторую группу элементов И соединен со входом каждого блока определения места ошибки, первые выходы которых соединены со входами блока анализа, а вторые - через группу элементов ИЛИ и че.твертую группу элементов И - со вторым входом блока памяти, выход второго блока модульной свертки соединен со вторым входом схемы сравнения, выход которой соединен с третьими входами элементов И второй группы, первый выход блока анализа соединен с третьим входом логического блока, второй выход блока анализа соединен с четвертым входом логического блока и со вторыми входами элементов И третьей, четвертой и первой групп, выход первой группы элементов И соединен с третьим входом блока памяти, управлянвдий вход устройства соединен со входом триггера управления, выход которого соединен с пятым входом логического блока, выходы- логического блока и третьей группы элементов И соединены со входами сумматора, выход которого является вторим выходом устройства.Блок определения места ошибки содержит элементы И, триггеры, сумматор и схему сравнения, причем входь блока соединены с первыми входами элементов И, прямые и инверсные выходы которых соединены со входами соответствующих триггеров, выход кг1ждого из которых соединен со вторым входом соответствукнпего элемента И, со входами сумматора и со входами блока, выход сумматора через схе му сравнения соединен с выходом блока Блок анализа содержит сумматоры, элементы И и два элемента ИЛИ, причем входы блока соединены со входами сумматоров и со входами первого элемента ИЛИ, выход которого соединен с первым выходом блока, выходы сумматоров через элементы И соединены со входами второго элемента ИЛИ, выход которого соединен со вторым выходом блока. Логический блок «содержит три группы элементов И и группу элементов ИЛИ, причем первый и второй входы блока соединены с первыми и вторыми входами первой, второй и третьей групп элементов И, третий вход блока соединен с третьим входом второй группы элементов И, четвертый вход блока соединен с третьим входом третьей группы элементов И, пятый вход блока соединен с третьим входом первой группы элементов И, выходы групп элементов И через группу элементов ИЛИ соединены с выходом блока.

На фиг.1 приведена функциональная схема устройства для обнаружения и исправле ния ошибок арифметических операций в системе остаточных классовj на фиг. 2 - функциональная схема блока определения места ошибки; на фиг.Зфункциональная схема блока анашиза; на фиг.4 - функциональная схема логического блока.

Устройство состоит изрегистра 1, предназначенного для хранения остатков числа по рабочим и контрольному основанию в течение времени обнаружения ошибки, вход 2 которого является входом устройства. Устройство содержит также первый блок 3 модульной свертки, предназначенный для получения остатка числа по контрольному основанию, вход которого соединен с первым входом регистра 1; сумматор 4 по контрольному основанию, предназначенный для вычисления синдрома числа, с помощью которого определяется совокупность возможных ошибок, первый вхо которого соединен с выходом первого блока 3 модульной свертки, а второй со вторым выходом регистра 1; блок 5 управления, предназначенный для выработки сигналов, соответствующих одиночной, двойной, тройной и т.д. ошибке; блок б памяти, предназначенный для хранения констант ошибок, первый вход которого соединен с выходом блока 5 управления} второй блок 7 модульной свертки, предназначенный для вычисления синдрома ошибок, вход которого соединен с первым выходом блока 6 памяти; схему 8 сравнения, предназначенную для сравнения синдромов числа и сяаибок, входы которой соединены соответственно с выходами сумматора по контрольному основанию 4 и второго блока 7 модульной свертки; группу 9 элементов И, входы которой соединены соответственно с выходом схемы 8 сравнения, выходом блока 5 управления и вторым входом блока б памяти: п бло579ков определения места ошибки 10.1,10. 2....,10. п, где п - число рабочих оснований системы счисления, входы которых соединены с выходом группы 9 элементов И: блок 11 анализа, предназначенный для выработки сигналов об отсутствии или. наличии в исходном чис ле ошибки и выработки сигнала на исправление ошибки в числе, входы которого соединены с первыми выходами блоков определения места ошибки 10.1, 10.2,., 10.п. Первый выход блока. 11 анализа является первым выходом 12 устройства. Устройство содержит также группу 13 элементов ИЛИ, входы которой соединены со вторыми выхода.ми блоков определения места ошибки 10.1, 10.2...10.п« группу 14 элементов И, :входы которой соединены соответственно с выходами группы 13 элементов ИЛИ и вторым выходом блока 11 анализа, а выход группы 14 элементов И соединен со входом блока 6 памятиj группу 15 элементов И, входы которой соединены i ,. соответственно с выходами сумматора 4 по контрольному основанию и вторым выходом блока 11 анализа, а выход груп пы 15 элементов И соединен со входом блока 6 памяти; триггер управления 16 вход которого соединен с управляющим Входом 17 устройства: логический блок 18, предназначенный для пропуска исправляемого числа в случае схождения альтернативной совокупности, входы которого соединены соответственно с выходом триггера 16 управления, с выходами регистра 1 и выходами блока 11 анализа группу 19 элементов И, предназначенную для пропуска величины сяйибки из блока 6 памяти, входы которого соединены соответственно с первым выходом блока 6 памяти и вторым выходом блока 11 анализа; сумматор 20, предназначенный-для получения неправленного числа, путем суммирования неправильного числа с величиной ошибки, входы которого соединены соответствен°но с выходом логического блока 18 и выходом группы 19 элементов И, а выход сумматора 20 является вторым выходом 21 устройства. Блок 10 определения места ошибки (см.фиг.2) состоит из элементов И 22.1,22.2,...22.k триггеров 23.1,.23. 2.., 23. k, сумматора 24, схемы оравнения 25. Здесь величина к принимает следующие значения: Сц ,Сц ,..,, С„ С„ .При этом первые входы элементов И 22 j (здесь и далее j l,2,...,k) соединены со входом блока определения .места ошибки, прямой и инверсный вы.хода элементов И 22 j соединены соот; ветственно со входами триггеров 23 j, выходы которых соединены со вторыми .входами элементов И 22 j. Выходы триггеров 23 j соединены с выходом блоков 10 i определе- ния места ошибки и входами сумматора 24. Выход сумматора 24 через схему 66 сравнения 25 соединен с вьаходом блока 40 i определения места ошибки. На второй вход схемы сравнения 25 подается :;игнал, соответствующий представлению единицы. t Блок 11 анализа (см.фиг.3) состоит из сумматоров 26.1, 26.2,. ..26 . п, элементов И 27.1,27.2...27.п, элементов ИЛИ 28 и 29. При этом входы бло--. ка 11 анализа соединены со входом каждого из сумматоров 26 j (здесь и далее j 1,2,..п) и входами 28 элемента ИЛИ, выход которого соединен с первым выходом блока 11 анализа, Первый и второй выходы каходого из сумматоров 26 j через соответствующие элементы И 27 j соединены со входами элемента ИЛИ 29, выход которого подсоединен ко второму выходу блока 11 анализа. Логический блок 18 (см.фиг.4), состоит из первой группы 30 элементов И, второй группы 31 эЗтементов И, третьей группы 32 элементов И и группы 33 элементов ИЛИ. При этом первый и второй входы блока 18 соединены с первыми входами групп элементов И 30,31,32, а третий, четвертый и пятый входы блока 18 соединены соответственно с т:рвтьими входами групп элементов И 31,32 и 30. Работа осуществляется следующим образом. На вход 2 устройства подается контролируемое число (,,.,., ()Ц ,..., t, , Ly. i где d. - остаток числа А по модулю р р . . . Pj. . . Ру, - рабочие основания системы счисления: р .j. контрольное основание системы счисления, которое записывается на регистр 1. На вход первого блока модульной свертки 3 с nepBOi o выхода реистра 1 подается число А o(,/i2,-,,. без остатка оСщ.- по контрольному основанию, с образованием на его выходе сигнала, соответствующего величине j -xj+i -i-XdL.+ .-vXrl wcjdP , f«-n,-i где ) константы системы счисления. Остаток tiy,. контролируемого числа А по контрольному основанию со второго выхода регистра 1 и величидд otu. с выхода первого блока модульной свертки 3 подаются на входы, сумматора по контрольному основанию 4 с образованием на его выходе числа, равного . (. -dl .А ИИ n и- -Одновременно с блока 5 управления вырабатывается первая серия сигналов, в соответствии с которыми из блока 6 памяти на вход второго блока 7 модульной свертки поступают значения ошибок , -.У, c образованием на его выходе сиЛала,

соответствующего величине синдрома ошибки

du .-i -i -- n H ° V Первая серия сигналов с блока 5 управления соответствует одиночным ошибкам по каждому основанию, т.е. с первого выхода блока 6 памяти поступают значения ошибок сначала по первому основанию, затем по второму основанию и т.д. до значений схиибок по основаниюРЦ

Затем с блока 5 управления вырабатывается вторая серия сигналов, которая соответствует двойным ошибкам,т.е сяиибке по двум основаниям. В этом случае с первого выхода блока 6 памяти выдаются ошибки по первому и второму основаниям (д, Да ) по первому и тре.тьему основаниям ( ,) и т.д. (д,Дц). Потом(Л2,Дг.) (2,) ,

С АИ-- )

Затем с блока 5 управления вырабатывается третья серия сигналов, которая соответствует тройным ошибкам,т.е ошибке по трем основаниям. В этом случае с первого выхода блока 6 памяти выдаются oшибки(д,д,),(.Д,(-1

й.(2. (И-а,Д ) Uwy,),

Последней с блока 5 управления вырабатыэается серия сигналов, которая соответствует ошибкам, затрагивакмцим все (п) основания, т.е. (-i, Да,.-. ; Ди )

Значение синдрома ошибки срав нивается со значением синдрома числа на схеме сравнения 8.Если cfА сГ , то в данном числе возможна ошибка, у которой синдром ошибки равен сГд.

В этом случае со второго выхода блока 6 памяти через группу 9 элементов И на один из блоков определения места ошибки 10.1,10.2,... 10.п поступает двоичное слово X - Х, X2,...., ,..., Xу,, причем Может принимат только одно из двух значений 0,1 Величина х 0, если по основан йю Pi ошибка Л невозможна/ и , есЛи по основанию Р-,- св1Шбка возможна. Иными словами, X 1 , если основание Р входит в альтернативную совокупность, которая может привести к синдрому числа, равному Од

Величина X поступает на один из блоков определения места ошибки 10.1, 10.2,... 10. зависимости от количе ства , п):если одно - т на блок определения места ошибки 10.1 если два - то на блок определения места ошибки 10.2 и т.д.

Блок 10 i работает следующим образом.

Перед началом работы все триггеры устанавливаются в состояние единицы

(установочная шина на фиг.2 не показана).

Если , то сигнал, соответствующий единице, с прямого выхода элемента И 22 j поступает на вход установки в единицу триггера 23j, если триггер находился в состоянии единицы, и не

поступает, если триггер 23j находился в состоянии нуля.

Если X J 0, то сигнал, соответству 1ДИЙ нулю, с инверсного выхода элемента И 23 j поступает на вход установки в ноль триггера 23j ,вне зависимости от первоначального состояния триггера 23J.

Сигналы с В1 1ходов триггеров 23J подаются на вход сумматора 24, причем значение суммы, равное единице, фиксируется схемой сравнения 24. Факт сравнения с единицей-сигнализирует о том, что альтернативная совокупность ссхилась, ошибка локализована либо в одном основании, либо в фиксированной группе оснований, а ее место указывается двоичным словом, выдаваемым с выхода блока lOj на блок 11 анализа.

Отсутствие единичных сигналов на входах блока 11 анализа фиксируется элементом ИЛИ 28, выходной сигнал которого, равный нулю, сигнализирует об отсутствии ошибки в числе, а выходной сигнал, равный единице, сигнализирует о наличии хотя бы одной ошибки.

Сигналы со входов блока 11 анализа под: аются также на входы сумматоров 26j ,каждый из которых представляет сумматор на два двоичных разряда накаливающего типа, имеющий выходы из каждого разряда.

Сигналы, поступающие на вход каждого из сумматоров 26j , суммируются в нем, причем факт достижения результата/ равного трем, фиксируется соответствующим элементом И 27J , и с выхода элемента ИЛИ 29 выдается сигнал, соответствующий единице.

Под воздействием этого сигнала через группу 13 элементов ИЛИ и группу

14элементов И на вход блока 6 памяти подается двоичное слово X, указывающее номера оснований, по которым произошла ошибка. CyiJMa единиц в двоично слове X дает кратность ошибки.

Под воздействием этого же сигнала на вход блока 6 памяти через группу

15элементов И подается величина синдрома числа сГд с выхода сумматора 4 по контрольному основанию.

В этом случае величина ошибки

;,(д),(с5д),...,Х(Уд..,д,(и)

с выхода блока 6 памяти через группу 19 элементов И подается на один из входов сумматора 20. На другой вход сумматора 20 через логический блок 18 подается исправляемое число с выходов регистра 1.

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

Исправленное число с выхода сумматора 20 поступает на выход 21 устройства . Если на данном этапе работы устройства в блоке 11 анализа не сущест вует ни одного слова X, в котором имеются (,h), то это означае что в исходном числе ошибок нет. В этом случае с первого выхода блока 1 вырабатывается сигнал, соответствующ О, под воздействием которого число А из регистра 1 через логический блок и сумматор 20 поступает на выход 21 устройства. Если на данном этапе работы устройства в блоке 11 анализа существуют слова X со значениями (,n), то с выхода блока 11 анализа выраиатывается сигнал, равный единице. Описанным образом устройство работает FO время работы контролируемого процессора, получая из него очередное значение числа и сигнал управления, равный единице, который устанавливает триггер 16 управления в единичное состояние. Возможна ситуация, когда процесс вычислений в контролируемом арифметическом устройстве закончен, а ошибка в результате осталась. Это соответствует единичному сигналу на выходе 12 и нулевому состоянию триггера 16 управления (сигнал на его входе со вход ной шиной управления 17 равен нулю). В этом случае результат вычислений из регистра 1 через логический блок переписывается в сумматор 20, где он хранится до тех пор, пока не будет обнаружена и исправлена возможная схиибка, о чем будет сигнализировать нулевой сигнал с выхода 12. Наличие единичного сигнгша на выходе 12 при окончании основных вычислений в контролируемом процессоре при водит к необходимости в проведении некоторой последовательности вспомогательных вычислений, необходимых для схождения альтернативной совокупности. В самом простом случае такой последовательностью может быть последова тельность операций, осуществляемых арифметическим устройством, начиная с последней. Изобретение позволяет осуществить в устройстве обнаружение и исправление произвольной ошибки, которая может затронуть все рабочие основания системы счисления в остаточных классах. Формула изобретения 1. Устройство для обнаружения и исправления ошибок арифметических опе раций в системе остаточных классов, содержащее регистрвход которого является входом устройства, сумматор, бло памяти, блок определения места ошибки блок анализа, первый выход которого является первым выходом устройства, отличающееся тем, что, -с целью расширения функциональных возможностей за счет обеспечения возможности обнаружения и исправления любой ошибки, в устройство введены первый и второй блоки модульной свертки, сумматор по контрольному основанию, схема сравнения, четыре группы элементов И, группа элементов ИЛИ, блоки определения места саиибки, логический блок, триггер управления и блок управления, причем первый выход регистра соединен с первым входом логического блока и со входом первого блока модульной свертки, выход которого соединен с первым входом сумматора по контрольному основанию, второй выход регистра соединен со вторым входом логического блока и со вторым входом сумматора по контрольному основанию, выход которого соединен с первым входом схемы сравнения и с первыми входами первой группы элементов И, первый выход блока управления соединен с первыми входами элементов И второй группы и первым входом блажа памяти, первый выход которого соединен со входом второго блока модульной свертки и с первыми входами элементов И третьей группы, второй выход блока памяти через вторую группу элементов И соединен со входом каждого блока определения места ошибки, первые выходы которых соединены со входами блока анализа, а вторые - через группу элементов или и четвертую группу элементов И соединены со вторым, входом блока , выход второго блока модульной свертки соединен со вторым входом схемы сравнения, выход которой соединен с третьими входами элементов И второй группы, первый выход блока анализа соединен с третьим входом логического блока, второй выход блока анализа соединен с четвертым входом логического блока и со вторыми входами элементов И третьей, четвертой и первой групп, выход первой группы элементов И соединен с третьим входом блока памяти, управляющий вход устройства соединен со входом триггера управления, выход которого соединен с пятым входом логического блока, выходи логического блока и третьей группы элементов И соединены со входами сумматора, соответственно, выхбд которого является вторым выходом устройства. 2. Устройство ПОП.1, отличающееся тем, что блок определения места ошибки содержит элементы И, триггеры, сумматор и схему сравнения, причем входы блока соединены с первыми входами элементов И, прямые и инверсные выходы которых соединены со входами соответствующих триггеров, выход каждого из которых соединен со вторым входом соответствующего элемента И, со входами сумматора и с входами бло сумматора через схему сравнения соединен с выходом блока. 3. Устройство поп.1, отличающееся тем, что блок анализа содержит сумматоры, элементы И и два элемента ИЛИ, причем входы блока соединены со входами сумматоров и со входами первого элемента ИЛИ, выход которого соединен с первым вйходом блока, выходы сумматоров через элементы И соединены со входами второго элемента ИЛИ, выход которого соединен со вторым выходом блока.

17

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

Источники информации, принятые во внимание при экспертизе

06 F 11/08,, 1965

226278, кл. G 15 (прототип).