Устройство для возведения п-разрядных чисел в квадрат

 

институт инженеров гражданской авиации (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ и-РАЭРЯДНЫХ

ЧИСЕЛ В КВАДРАТ

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

Известно устройство для возведения дво:1чных чисел в квадрат, содержащее счетчик, счетный вход которого через элемент И соединен со входом блока элементов ИЛИ, рекурентный регистр сдвига, блок сумматоров по модулю два, первый и второй блоки элементов И P3. .В устройстве исходное. число преобразуется в К псевдослучайных последовательностей и реализуется последующая их обработка, что определяет невысокое быстродействие устройства и производительность, а также невысокую надежность вычислений иэ-за невозможности реализовать одновременный контроль вычислительного процеСса.

Из известных устройств наиболее близким к предлагаемому по технической сущности является устройство,содержащее (и-1) группу элементов И по 1 элементов в каждой (где номер группы), сумматор 121.

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

Цель изобретения - повышение надежности и производительности устройства для возведения п-разрядных

15 чисел в квадрат.

Указанная цель достигается тем, что в устройство для возведения и-разрядных чисел в квадрат, содержацее (n-1) группу элементов И по

20 элементов в каждом (где i -. номер группы (i = 1, ;и-1) и сумматор, введены схема сравнения, элемент ИЛИ, полусумматоры и сумматоры по модулю разрядная матрица, представляющая собои разрядное иэображение Х при и = 3 °

Х =

Выражение (1) в развернутой форме

40 при и = 5 представляется в виде

3 911520 два, причем элементы И групп объединены в матрицу, каждый i-й столбец которой является i-ой группой, первые входы элементов И каждого i-ro столбца матрицы объединены и подключены к (1+1)-му разряду входного кода устройства, к i-у разряду входного кода устройства подключены вторые входы каждого i-ro элемента И всех столбцов матрицы, первый вход i-ro 10 разряда схемы сравнения и первый вход 1-го полусумматора,выходы элемента И каждой j-ой строки матрицы" (j=1,2,...п-3) соединены со входом

O+1)-ro разряда сумматора, выход И каждого 21- го. разряда которого подключен ко второму входу i-го полусумматора и первому входу -го сумматора по модулю два, подключенного своим вторым входом к выходу ув

i"ro полусумматора и соответствующему 2д-му разряду выходно-о кода устройства, а выходомко второму входу соответствующего разряда схемы сравнения, выход каждого (2i-I)-ro разряда сумматора соединен с (2i-1)-м разрядом выходного кода, старший разряд которого соединен с выходом элемента ИЛИ, к первому и второму входам которого подключены выходы переноса сумматора и полусумматора предыдущего разряда, а выход переноса каждого (i+1)-ro полусумматора соединен со входом сумматора последующего разряда,(2n-1)-й и 2п-й разряды выходного кода подключены соответственно к шине логического нуля и к и-му разряду входного кода.

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

Устройство содержит матрицу 1, сумматор 2, схему сравнения 3, элемент ИЛИ 4, полусумматоры 5,одноразрядные вычитатели 6. Матрица 1 из элементов И 7 выполнена иэ (n-1)-ro столбца, каждый i-й (i=1 2,...n-1) столбец которой сдвинут относительно (i-1)-го на один разряд вниз. Сумматор 2 выполнен из одноразрядных сумматоров 8. Каждый i-й разряд схемы сравнения 3 выполнен из элемента

9 сложения по модулю два, выход которого подключен к i-му входу схемы ИЛИ 10, Работу предлагаемого устройства поясним на примере возведения в квадрат числа X по выражению Х =Х X=V предварительно представленному в разрядной форме. е ч а —.

Х эс Ч, ч +уФ и где ... 4-v y -раэ рядные векторы, представляющие собой разрядное изображение чисел Х и Y соответственно:

ЙППИЯ

911520 6 и положено в основу алгоритма парал- а лельного функционирования предлагае- Х +

f мого устроиства. Для увеличения на- ХХ

V. г дежности устройства путем реализаа ции параллельного контооля вычислиS V тельного процесса (т.е. осуществле- .V ния параллельной проверки правиль- 5 Щ ности выполнения операции воэведеЧ (5) ниЯ в кваДРат) и УвеличениЯ произво- 1аким образом реал эовав в разом, реализовав выражедительности путем фиксации момента о ние получим квад ат знач выполнениЯ операции (т.е. переход- числа Х а реализо а на с а реализовав на основе выного пРоцесса в схеме) РазРешим вы- ражения (5) выражение (4), получим

Ражение (2) относительно значений вектор Х срав ивая который с за аv разрядов Х вектора Х ным вектором, определим праЯ. Я.

15 вильность выполнения операции

= V — (XX + р )

Я

= V-S возведения в квадрат и момент

4 9 14 4 Д 44

1 ее окончания, при этом значение раз= V -. (+ XX + р„+ р ) = V-S

Ь 34 М 6" 6 Ь

Ь а ч34ЬЕ

Х = Ч - (XX + XX + p„) рядов V,V,V,V вектора V1= Ъ У V Ч

В 46 " Ве о. a ЬВ

246 6 (ХХ) =Ч S р) и разрядов S,Á,S,S,âåêòoðà бб определяется в процессе вычисления ч Ч где р„ р1р р1 зна e""e пеРеноса квадрата числа Х = V, а разность (в выражении (2) из ч ч младшего в старший 25 вектоРов V и $ (т.е. контРоль выРазряд т е в шес числительного процесса) реализуется тои четвертый и параллельно с вычислительным процесвторой соответ- сом возведения в квадрат путем по.ственно: разрядного вычитания из вектора Ч ф1

9 45 Ь 34 Ф 5 6 1 1Ъ 9. о вектора S в процессе вычисления их

Х + XX + р1 ХХ+р1 компонент.

Операция определения значений Х Рассмотрим вышеизложенное на конвектора из выражения (3) реализу- кретном примере значения Х=0 90625 ется на базе предлагаемого выраже- и, соответсгвенно, РезУльтата вычисния,, положенного в основу функцио- >5 ления = 0,8212890625 или в разрядной нирования каждого разряда вычита- форме теля

Х-11.10

У. Ф . 1

1

Х-V

2 4

Х=V

3 6

X=V

4 8

Х-V

Х=V

® S

® S

Э S

0+ S, 21

З S

8 соответствии с выражением ($) вычислительный процесс нахождения векч ч тора X = V может-быть представлен

45 (4) где 9 - знак, обозначающий сложе ние по модулю два.

В соответствии с выражениями (3) и (4) выражения (2) можно записывать в виде

911520

1Е

1 = 1,2,3,4

7 ь В где 1 =, 3 = 0, s = 1, а процесс реализации параллельного контроля вычислений на основании выражения (4) соответственно

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

П и по аче на входную шину числа

Х = 1 1 1 0 1 в устройстве .протекает переходной процесс, после окончания которого на выходе второго, четвертого, шестого и,восьмого разрядов одноразрядных сумматоров 8 сумматора 2 обоазчются соответственС о значения = О, 3 = О, Х- 4>

= 0> поступающие соответственно на вторые входы одноразрядных вычитателей 6, а на выходах полусумматоров 5 образуются соответственно зна4 Е, Е ченияg 1,$ *1,1(О, 1 =О ю ч разрядов искомого вектора 1(, которые поступают. на первые входы одноразрядных вычитателей 6, в которых реали- зуется, разность поступивших компоЖ нент и S,Иа выходах одноразрядных вычитателей б,образуются соответст1 О. венно значения разрядов Х = 1, Х = 1, 4

= 1, Х = 0 вектора Х, каждая Х i-я компонента которого поступает на второй вход i-ro разряда элемента сложения по модулю два 9 схемы сравнения З,на первый вход которого по1 ступает соответственно Х i-я ком. понента заданного вектора X с .вы° хода i-го разряда входной шины.

В схеме сравнения 3 реализуется

v сравнение заданного вектора Х с вычисленным в процессе решения вектора Х и на .выходе схемы

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

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

v„v„ вектор, а разность между Ч и S является параллельным контролем вычислитель, ного процесса (начиная с младшего и заканчивая старшим разрядом); кроме того, существенно увеличивается производительность предлагаемого устройства благодаря тому, что на выходе схемы сравнения 3 вырабатывается сигнал конца переходного процесса в схеме H устройство может сразу же запускаться на следующий- цикл работы. В противном случае (когда сигнал конца переходного процессе не вырабатывается) устройство будет находиться в режиме ожидания, пока не закочится такт его работы, после чего оно запускается на следующий цикл, а поскольку длительность переходного процесса. при подаче на его вход различных чисел различна, устройство достаточно долго простаивает .

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

Устройство для возведения и-раз4В рядных чисел в квадрат, содержащее (и-1) группу элементов И по i элементов в каждой группе (где i - номер группы (i =" 1;....(-1) и сумматор, о т л и ч а а щ е е с я тем, что, с целью повышения надежности и производительности, оно дополнительно содержит. схему сравнения, элемент ИЛИ, полусумматоры:и сумматоры по модулю два, причем элементы И групп образу ют матрицу, первые входы элементов И каждого i-ro столбца которой объединены и подключены к (1+1) разряду входного кода устройства, к 1-у разряду входного кода устройства под55 ключены вторые входы i-ro элемента И всех столбцов матрицы, первый вход 1-го разряда схемы сравнения и первый вход i-го разряда схемы

Составитель О. Свиридов

Техред A.Ач Корректор Ю. Макаренко

Редактор А. Фролова

Заказ 1129/40 Тираж 732 Подписное

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

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

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

9 9 сравнения и первый вход i-го полусумматора, выходы элемента И каждой

j-ой строки матрицы (j = 1,2...,n-3) соединены со входом (j+1)-го разряда сумматора, выход каждого 2i-го разряда которого подключен ко второму входу i-ro полусумматора и первому входу i-ro сумматора по модулю два, подключенного своим вторым входом к выходу i-го полусумматора и соответствующему 2i-му разряду выходного кода устройства, а выходом - ко второму входу соответствующего разряда схемы сравнения, выход каждого (2i-1)-ro разряда сумматора соединен с (2i-1)-м разрядом выходного кода устройства, старший разряд которого соединен с выходом элемен11520 10 та ИЛИ, к первому и второму входам которого подключены выходы переноса сумматора и полусумматора предыдущего разряда, а выход переноса каждого (i+1)-ro полусумматора соединен со входом сумматора последующего разряда, (2n-1)-й и 2п-й разряды выходного кода подключены.соответственно к шине логического ну10 ля и к п-му разряду входного кода.

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

1. Авторское свидетельство CCCP, М 628487, кл. C 06 F 7/38, 1978.

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

h" 623201, кл. Ь 06 F 7/38, 1978 (прототип).