Устройство для обнаружения и исправленияошибок арифметических операций всистеме остаточных классов

 

Союз Севетскнк Соцналнстнческнк

Республнк

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ о>796846

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено260177 (21) 2439702/18-24 с присоединением заявки Й9 (23) Приоритет

Опубликовано 150181. Бюллетень Н9 2

Дата опубликования описании 170181

{51)М. Кл 3

G 06 F 11/08

Государственный комитет

СССР но делам изобретений и открытий

{53)УДК621.326.7 (088.8) (72) Авторы изобретения

Г. Г. Смолко, И. Я. Акушский и В. М. Бурцев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ

ОШИБОК АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ В СИСТЕМЕ

ОСТАТОЧНЫХ КЛАССОВ

Изобретение относится к автоматике и вычислительной технике, в частности, может быть использовано для контроля ,и исправления снаибки любой кратности при проведении арифметических операций в ЗВМ, работающей в системе остаточных классов.

Известно устройство для обнаружения и Исправления ошибок в системе остаточных классов, основанное на процессе нуливизации. Процесс нуливизации заключается в последовательном вычитании из представленного числа в системе остаточных классов констант системы с целью определения наличия или отсутствия ошибки. Кроме этого, для обнаружения наличия ошибки необходимо в систему оснований ввести одно контрольное основание, а для исправления ошибки необходимо дополнительно 20 ввести еще одно контрольное основание, причем каждое из контрольных оснований по величине должно быть больше каждого из рабочих оснований систе- мы (11. 25

Основным недостатком устройства является его низкое быстродействие, так как процесс получения безошибочного числа в устройстве носит после- 30 довательный характер и зависит от числа оснований системы счисления.

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

Недостаток этого устройства — его сложность.

Наиболее близким по технической сущности к данному является устройство для обнаружения и исправления ошибок арифметических операций в системе остаточных классов, содержащее регистр, вход которого является входом устройства, сумматор, блок памяти, блок определения места ошибки, блок. анализа, первый выход которого является первым выходом устройства (31

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

796846

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

Указанная цель достигается тем, что з устройство введены первый и второй блоки модульной свертки, сумматор по контрольному основанию, схема сравнения, четыре группы элементов И, ! группа элементов ИЛИ, блоки определения места ошибки, логйческий блок, триггер управления и блок управления, причем первый выход регистра соединен с первым входом логического блока и со входом первого блока модульной свертки, выход которого соединен с первым входом сумматора по контрольному основанию, второй выход регистра соединен со вторым входом логического блока и со вторым входом сумматора по контрольному основанию, выход которого соединен с первым входом схемы срав 20 нения и с первыми входами первой группы элементов И, выход блока управления соединен с первыми входами элементов И второй группы и с первым входом блока памяти, первый выход которо- 25 го соединен со входом второго блока модульной свертки и с первыми входами элементов И третьей группы, второй выход блока памяти через вторую группу элементов И соединен со входом каждого блока определения места ошибки, первые выходы которых соединены со входами блока анализа, а вторые — через группу элементов ИЛИ и четвертую группу элементов И вЂ” со вторым входом З блока памяти, выход второго блока модульной свертки соединен со вторым входом схемы сравнения, выход которой соединен с третьими входами элементов

И второй группы, первый выход блока анализа соединен с третьим входом ло- 40 гического блока, второй выход блока анализа соединен с четвертым входом логического блока и со вторыми входами элементов И третьей, четвертой и первой групп, выход пеРвой гРуппы эле- 45 ментов И соединен с третьим входом блока памяти, управляющий вход устройства соединен со входом триггера управления, выход которого соединен с пятым входом логического блока, выхо- gg ды логического блока и третьей группы элементов И соединены со входами сумматора, выход которого является вторйм выходом устройства. Блок определения места ошибки содержит элементы И, триггеры, сумматор и схему сравнения, причем входы блока соединены с первыми входами элементов И, прямые и инверсные выходы которых соединены со входами соответствующих триггеров, выход каждого из которых соединен со бО вторым входом соответствующего элемен" та И, со входами сумматора и со входами блока, выход сумматора через схе му сравнения соединен с выходом блока, Блок анализа содержит сумматоры, эле- 65 менты И и два элемента ИЛИ, причем входы блока соединены со входами сумматоров и со входами первого элемента

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

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

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

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

Устройство состоит из регистра 1, предназначенного для хранения остатков числа по рабочим и контрольному основанию в течение времени обнаружения ошибки, вход 2 которого является входом устройства. Устройство содержит также первый блок 3 модульной свертки, предназначенный для получения остатка числа по контрольному основанию, вход которого соединен с первым входом регистра 1; сумматор 4 по контрольному основанию, предназначенный для вычисления синдрома числа, с помощью которого определяется совокупность возможных ошибок, первый вход которого соединен с выходом первого блока 3 модульной свертки, а второй со вторым выходом регистра 1; блок 5 управления, предназначенный для выработки сигналов, соответствующих одиночной, двойной, тройной и т.д. ошибке; блок 6 памяти, предназначенный для хранения констант ошибок, первый вход которого соединен с выходом блока 5 управления; второй блок 7 модуль-ной свертки, предназначенный для вычисления синдрома ошибок, вход которого соединен " первым выходом блока

6 памяти; схему 8 сравнения, предназначенную для сравнения синдромов числа и ошибок, входы которой соединены соответственно с выходами сумматора по контрольному основанию 4 и второго блока 7 модульной свертки; группу 9 элементов И, входы которой соединены соответственно с выходом схемы 8 сравнения, выходом блока 5 управления и вторым входом блока б памяти: и бло796846 ков определения места ошибки 10.1,10 ° .

2....,10. и, где n — число рабочих оснований системы счисления, входы которых соединены с выходом группы 9 элементов И: блок 11 анализа, предназначенный для выработки сигналов об отсутствии или. наличии в исходном числе ошибки и выработки сигнала на исправление ошибки в числе, входы которого соединены с первыми выходами блоков определения места ошибки 10.1, 10.2,, 10.п. Первый выход блока 11 анализа является первым выходом 12 устройства. Устройство содержит также группу 13 элементов ИЛИ, входы ко орой соединены со вторыми выходами блоков определения места ошибки 10.1, 10.2...10.п группу 14 элементов И, .входы которой соединены соответственно с выходами группы 13 элементов ИЛИ и вторым выходом блока 11 анализа, а выход группы 14 элементов И соединен Щ) со входом блока 6 памяти; группу 15 элементов И,входы которой соединены, ;.соответственно с выходами сумматора

4 по контрольному основанию и вторым выходом блока 11 анализа, а выход груп $ пы 15 элементов И соединен со входом блока 6 памяти; триггер управления 16, вход которого соединен с управляющим входом 17 устройства логический блок

18, предназначенный для пропуска исправляемого числа в случае схождения альтернативной совокупности, входы которого соединены соответственно с выходом триггера 16 управления, с выходами регистра 1 и выходами блока

11 анализа ° группу 19 элементов И, предназначенную для пропуска величины ошибки из блока 6 памяти, входы которого соединены соответственно с первым выходом блока 6 памяти и вторым выходом блока 11 анализа; сумматор 20,4О предназначенный-для получения исправленного числа, путем суммирования неправильного числа с величиной ошибки, входы которого соединены соответствено но с выходом логического блока 18 и выходом группы 19 элементов И, а выход сумматора 20 является вторым выходом 21 устройства.

Блок 10 определения места ошибки (см.фиг.2) состоит из элементов И

22.1,22,2,...22.k триггеров 23.1,.23.

2., 23. k, сумматора 24, схемы срав- нения 25. Здесь величина к принимает следующие значения

С>. .При этом первые входы элементов

И 22 j (здесь и далее j = 1,2,...,k) $$ соединены со входом блока определения ,места ошибки, прямой и инверсный вы,ходы элементов И 22 j соединены соот1 ветственно со входами триггеров 23 j, выходы которых соединены со вто- gg рыми .входами элементов И 22

Выходы триггеров 23 j соединены с выходом блоков 10 i определе-» ния места ошибки и входами сумматора

24. Выход сумматора 24 через схему 6$ сравнения 25 соединен с выходом блока 10 i определения места ошибки. На вто. рой вход схемы сравнения 25 подается

=игнал, соответствующий представлению эдиницы.

Ф

Блок 11 анализа (см.фиг.3) состоит из сумматоров 26.1, 26.2,...26.п, элементов И 27.1,27.2...27.п элементов ИЛИ 28 и 29. При этом входы бло- .. ка 11 анализа соединены со входом каждого из сумматоров 26 j (здесь и далее j = 1,2...n) и входами 28 элемента ИЛИ, выход которого соединен с первым выходом блока 11 анализа.

Первый и второй выходы каждого из сумматоров 26 j через соответствующие элементы И 27 j соединены со входами элемента ИЛИ 29, выход которого подсоединен ко второму выходу блока 11

:анализа.

Логический блок 18 (см.фиг.4), состоит из первой группы 30 элементов

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

Работа осуществляется следующим образом.

На вход 2 устройства подается контролируемое число А = 4 „ аи (. и+ гд ток числа А по модулю Р„;

Р.1 P> ...P„.... P> — рабочие основания системы счисленйя:

P контрольное основание системы счисления, которое записывается на регистр 1. На вход первого блока модульной свертки 3 с первого выхода регистра 1 подается число А =< Ф-,-,«;- и без остатка с(и+ 1по контрольному осно-, ванию, с образованием на его выходе сигнала, соответствующего величине рС )i д. tg g ф...+)i.й.++".+A. g mod P

6+1 1 1 2 2. 1 1 где А„(1 = (и) = константы системы счис» ления.

Остаток С И 1 контролируемого числа А по контрольному основанию Ри со второго выхода регистра 1 и величиI на aL и+„c выхода первого блока модульной свертки 3 подаются на входы . сумматора по контрольному основанию

4 с образованием на его выходе числа, равного

Одновременно с блока 5 управления вырабатывается первая серия сигналов, в соответствии с которыми из блока 6 памяти на вход второго блока 7 модульной свертки поступают значения ошибок

Ь д

1 2 (и с образованием на его выходе сигнала, 796846 соответствующего величине синдрома ошибки

«... «jl, +. + +-«А Q йод „, 1 1 2 2 1 1 Ь И

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

P.

Затем с блока 5 управления выраба- 10 тывается вторая серия сигналов, которая соответствует двойным ошибкам,т.е. ошибке по двум основаниям. В этом случае с первого выхода блока б памяти выдаются ошибки по первому и второму 15 основачиям (д„д2), по первому и тре, тьему основаниям (дq, д +) и т.д. (д„д,). Потом(д д )p ° ° °, (д2 д ) (ди-< д! ) °

Затем с блока 5 управления выраба- р0 тывается третья серия сигналов, которая соответствует тройным ошибкам,т.е. ошибке по трем основаниям. В этом случае с первого выхода блока 6 памяти выдаются Ошибки (д > дд>!Х (д„, д2> д4>,...> (д

2 > !!) (7>+Ú> 4)> (+n < Д >!-4 ДИ)

Последней с блока 5 управления вырабатырается серия сигналов, которая соответствует ошибкам, затрагивающим все (п) основания, т.е.(>a,да," >ди)

Значение d синдрома ошибки срав-30 нивается со зйачением синдрома числа на схема сравнения 8. Если Кд = д д, то в данном числе возможна ошибка, у которой синдром ошибки равен дд.

B этом случае со второго выхода 35 блока б памяти через группу 9 элементов И на один из блоков определения места ошибки 10.1,10.2,... 10.п поступает двоичное слово Х = х.!, х2,..., х„,,, х„,причем х„ Может принимать40 только одно из двух значений (0,1

Величина х =О, если по основайию

Р ошибка д„ невозможна, и х„=1, если по основанию Р„ ошибка возможна. Иными словами, х =1, если основание Р„. входит в альтернативную совокупность, 45 которая может привести к синдрому числа, равному g

Величина Х поступает на один из блоков определения места ошибки 10.1, 10.2,... 10.и в зависимости от количе-® ства х, =1 (i=1, n):åñëè одно x„ =1 — то на блок определения места ошибки 10.1, если два х„=1 — то на блок определения места ошибки 10.2 и т.д.

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

Перед началом работы все триггеры устанавливаются в состояние единицы (установочная шина на фиг.2 не показайа). 60

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

Если Х> =О, то сигнал, соответствую щий нулю, с инверсного выхода элемента И 23 j поступает на вход установки в ноль триггера 23 1,вне зависимости от первоначального состояния триггера

23j.

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

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

Сигналы со входов блока 11 анализа подаются также на входы сумматоров

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

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

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

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

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

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

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

„(б ) д (сЫ,(А ) д (Ад ! 2 1"-! ., ., 1., с выхода блока 6 памяти через группу

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

18 подается исправляемое число с выходов регистра 1.

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

Исправленное число с выхода сумматора 20 поступает на выход 21 устройства.

796846

Если на данном этапе работы устройства в блоке 11 анализа не существует ни одного слова Х, в котором имеются Х„=1 (1 =1,И), то это означает, что в исходном числе ошибок нет. В этом случае с первого выхода блока 11 вырабатывается сигнал, соответствующий 5

О, под воздействием которого число A из регистра 1 через логический блок и сумматор 20 поступает на выход 21 устройства.

Если на данном этапе работы устройства в блоке 11 анализа существуют. слова Х со значениями х = 1 (=1,п), 1 то с выхода блока 11 анализа вырабатывается сигнал, равный единице. 15

Описанным образом устройство работает Ро время работы контролируемого процессора, получая из него очередное значение числа и сигнал управления, равный единице, который устанавливает 20 триггер 16 управления в единичное состояние.

Возможна ситуация, когда процесс вычислений в контролируемом арифметическом устройстве закончен, а ошибка в результате осталась. Это соответствует единичному сигналу на выходе 12 и нулевому состоянию триггера 16 управления (сигнал на его входе со вход- ной шиной управления 17 равен нулю).

В этом случае результат вычислений Зо из регистра 1 через логический блок 18 переписывается в сумматор 20, где он хранится до тех пор, пока не будет обнаружена и исправлена возможная ошибка, о чем будет сигнализировать 35 нулевой сигнал с выхода 12.

Наличие единичного сигнала на выходе 12 при окончанки основных вычислений в контролируемом процессоре приводит к необходимости в проведении 4g ,некоторой последовательности вспомогательных вычислений, необходимых для схождения альтернативной совокупности. В самом простом случае такой пос ледовательностью может быть последовательность операций, осуществляемых арифметическим устройством, начиная с последней.

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

Формула изобретения

1. Устройство для обнаружения и исправления ошибок арифметических операций в системе остаточных классов, содержащее регистрвход которого является входом устройства, сумматор, блок памяти, блок определения места ошибки„бО блок анализа, первый выход которого является первым выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возмож- 45 ности обнаружения и исправления любой ошибки, в устройство введены первый и второй блоки модульной свертки, сумматор по контрольному основанию, схема сравнения, четыре группы элементов И, группа элементов ИЛИ, блоки определения места ошибки, логический блок, триггер управления и блок управления, причем первый выход регистра соединен с первым входом логического блока и со входом первого блока модульной свертки, выход которого соединен с первым входом сумматора по контрольному основанию, второй выход регистра соединен со вторым входом логического блока и со вторым входом сумматора по контрольному основанию, выход которого соединен с первым входом сх мы сравнения и с первыми входа- ми первой группы элементов И, первый выход блока управления соединен с первыми входами элементов И второй группы и первым входом блэка памяти, первый выход которого соединен со входом второго блока модульной свертки и с первыми входами элементов И третьей группы, второй выход блока памяти через вторую группу элементов И соединен со входом каждого блока определения места ошибки, первые выходы которых соединены со входами блока анализа, а вторые — через группу элементов

ИЛИ и четвертую группу элементов И соединены со вторым, входом блока памяти, выход второго блока модульной свертки соединен со вторым входом схемы сравнения, выход которой соединен с третьими входами элементов И второй группы, первый выход блока анализа соединен с третьим входом логического блока, второй выход блока анализа соединен с четвертым входом логического блока и со вторыми входами элементов И третьей, четвертой и первой групп, выход первой группы элементов И соединен с третьим входом блока памяти, управляющий вход устройства соединен со входом триггера управления, выход которого соединен c nÿòûì входом логического блока, выходы логического блока и третьей группы элементов И соединены со входами сумматора, соответственно, выход которого является вторым выходом устройства.

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

3. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок анали11

796846

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

4. Устройство по п.1, о т л и— ч а ю щ е е с я тем,.что логический блок содержит три группы элементов И ® и группу элементов ИЛИ, причем первый. и второй входы блока соединены с первыми и вторыми входами первой, второй и третьей групп элементов. И, третий вход блока соединен с третьим входом 35 второй группы элементов И, четвертый вход блока соединен с третьим входом третьей группы элементов И, пятый вход блока соединен с третьим входом первой группы элементов И, выходы групп элементов И через группу элементов ИЛИ соединены с выходом блока.

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

1. Авторское свидетельство СССР

Р 377780, кл. 6 06 F 11/10, 1971.

2. Авторское свидетельство СССР

Р 398950, кл, G 06 F 11/00, 1971.

3. Авторское свидетельство СССР

Р 226278, кл. G 06 F 11/08, 1965 (прототип).

796846 сия

Составитель В. Крылова

Редактор N. Циткина Техред H.Áàðàäóëèíà Корректор Г.Решетник

Заказ 9770/бб ТиРаж 756 Подписное

ВИИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4