Устройство для возведения п-разрядных чисел в квадрат Советский патент 1982 года по МПК G06F7/552 

(S) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ п-РАЗРЯДНЫХ ЧИСЕЛ В КВАДРАТ

I

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

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

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

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

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

10 выполнения, и невысокая производительность.

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

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

20 i элементов в каждом (где i - номер группы (i 1,...п-1) и сумматор, введены схема сравнения, элемент ИЛИ, полусумматоры и сумматоры по модулю . 39 два, причем элементы И групп объединены в матрицу, каждый столбец которой является i-ой группой,первые входы элементов И каждого i-ro столб ца матрицы объединены и подключены к (1+1)-му разряду входного кода устройства, к i-y разряду входного кода устройства подключены вторые входы каждого i-ro элемента И всех столбцов матрицы, первый вход i-ro разряда схемы сравнения и первый -ВХОД i-ro полусумматора,выходы элемента И каждой j-ой строки матрицы(,2,...n-3j соединены со входом (j+1)-ro разряда сумматора, выход каждого 2i-го разряда которого подключен ко второму входу i-ro полусум матора и первому входу i-ro сумматора по моду/чо два, подключенного своим вторым входом к ВЫХОДУ i-ro полусумматора и соответствующему 2i-My разряду выходно-о кода устройства, а выходом ко второму входу соответствующего разряда схемы сравнения, выход каждого (2i-1)-ro разряда сумматора сое динен с (2i-1)-M разрядом выходного кода, старший разряд которого соединен с выходом элемента ИЛИ, к первому и второму входам которого подключеиы выходы переноса сумматора и пол сумматора предыдущего разряда, а выход переноса каждого (i+1)-ro полусумматора соединен со входом сумматора последующего разряд:а,(2п-1)-й и 2п-й разряды выходного кода подключены соответственно к шине логического нуля и к п-му разряду входн го кода. На чертеже представлена схема устройства для возведения п-разрядных чисел в квадрат для случая, когда информация представлена двоичными разрядами. Устройство содержит матрицу 1, сумматор 2, схему сравнения 3, элемент ИЛИ 4, полусумматоры 5,одноразрядные вычитатели 6. Матрица 1 из. элементов И 7 выполнена из (п-1)-го столбца, каждый i-й (,2,...п-1) столбец которой сдвинут относительно (i-l)-ro на один разряд вниз. Сумматор 2 выполнен из одноразрядных сумматоров 8. Каждый i-й разряд схемы сравнения 3 выполнен из элемента 9 сложения по модулю два, выход которого подключен к i-му входу схемы ИЛИ 10. Работу предлагаемого устройства поясним на примере возведения в квадрат числа X по выражению , предварительно представленному в разрядной форме. Д g °lfc| Ll5il-V-|4| 11 ... -разрядные векторы, представляющие собой разрядное изображение чисел X и У соответственно: разрядная матрица, представляющая собой разрядное изображение X при п 3. Выражение (1) в развернутой форме при п 5 представляется в виде 5 и положено в основу алгоритма парал лельного функционирования предлага мого устройства. Для увеличения надежности устройства путек реализации параллельного контооля вычислительного процесса (т.е. осуществления параллельной проверки правильности выполнения операции возведения в квадрат) и увеличения произво дительности путем фиксации момента выполнения операции (т.е. переходного процесса в схеме) разрешим выражение (2) относительно знамений Ч разрядов X вектора X 1 2 ia V-(XX.p) 4 2i 14 4 A 44 У- (XX + XX f.,) V-S X V - (XX + Ь 44 Ь X V - (XX + „ - - (XX) y-S ( 444 Q. где значение переноса (в выражении (2) и младшего в старший разряд, т.е. в шес той, четвертый и второй соответственно:

е л5 34 а 5 6

1 11 U

s XX; s XX + XX + р

,

Операция определения значений X вектора л из выражения (3) реализуется на базге предлагаемого Выражения,, положенного в основу функционирования каждого разряда вычитателя

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

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

V

V

5

V в Р

вектора S в процессе вычисления их компонент.

Рассмотрим вышеизложенное на конкретном примере значения ,90625 и, соответсгвенно, результата вычисления 0,8212890625 или в разрядной ормеt

-П|1И1оП1

F И1ЧоИ|о|Д|Чо|ор

в соответствии с выражением (5) вычислительный процесс нахождения v

тора А

V может быть представлен в виде 20 Таким образом, реализовав выражение (5), получим квадрат значения исла X, а реализовав на основе выраженияу.(5) выражение С), получим вектор л,сравнивая который с заданным вектором X , определим правильность выполнения операции возведения в квадрат и момент ее окончания, при этом значение раз-; 1-Шм2 V.V,V, вектора Viwierer .1466Г72Т47 Гв и разрядов S,S,S,S.BeKTOpaSi:|SiS|s|s определяется в процессе вычисления V9 V квадрата числа X V, а разность V V векторов V и S (т.е. контроль вычислительного процесса) реализуется параллельно с вычислительным процессом возведения в квадрат путем п разрьдного вычитания из вектора 79 n 4 6 в где S , S , S О,, S , а процесс реализации параллельного контроля вычислений на основании вы ражения С) соответственно 1 1 Ф о 1 1 ® о X 1 о® 1 i 1.2,3. о о Ф о Работа предлагаемого устройства осуществляется следующим образом. V При подаче на входную шину числа 11) 1 )0|Г JB устройстве протекает переходной процесс, после окон чания которого на выходе второго, четвертого, шестого и восьмого разрядов одноразрядных сумматоров 8 cyfwaTopa 2 образуются соответствен но значения |г О, о, S 4, 0| поступающие соответственно н вторые входы одноразрядных вычитателей 6, а на выходах полусумматоров 5 образуются соответственно зна чения o. Т V разрядов искомого вектора Y которы поступают на первые входы одноразря ных вычитателей 6, в которых реализуется разность поступивших компоut 1 .. нент у и S,На выходах одноразрядных вычитателей 6 образуются соответст1 а венно значения разрядов X 1, X 4V 1 X 1, X О вектора Х« каждая X i компонента которого поступает на второй вход i-ro разряда элемента сложения по модулю два 9 схемы срав нения 3,на первый вход которого поступает соответственно X i-я компонента заданного вектора л с вы хода i-ro разряда входной шины. В схеме сравнения 3 реализуется V сравнение заданного вектора X с вычисленным в процессе решения вектора X и на выходе схемы ИЛИ 10 схемы сравнения 3 вырабатывается сигнал, оповещающий, что оп рация возведения в квадрат выполне на правильно и переходной процесс схеме закончен, -а на вход устройст |МОжно подавать следующее число. Использование новых элементов схемы сравнения, элемента ИЛИ, полусумматоров и одноразрядных вычислит лей - ВЫГОДНО отличает предлагаемое устройство от известного, так как в предлагаемом устройстве существенно повышается надежность благодаря тому, что в устройстве параллельно с вычислительным процессом осуществляется контроль правильности его выполнения, при этом в проVfl V цессе вычисления X V вычисляется ч вектор S , а разность между V и S является параллельным контролем вы,числительного процесса (начиная с младшего и заканчивая старшим разрядом) ; кроме того, существенно увеличивается производительность предлагаемого устройства благодаря тому, что на выходе схемы сравнения 3 вырабатывается сигнал конца переходного процесса в схеме и устройство может сразу же запускаться на следующий цикл работы. В противном случае (когда сигнал конца переходного процессе не вырабатывается) устройство будет-находиться в режиме ожидания, пока не закочится такт его работы,после чего оно запускается на следующий цикл, а поскольку длительность переходного процесса при подаче на его вход различных чисел различна , устройство достаточно долго простаивает. Формула изобретения Устройство для возведения п-разрядных чисел в квадрат, содержащее (п-1) группу элементов И по i элементов в каждой группе (где i - номер группы (i 1....|-1) и сумматор, о т л и ч а ю щ е. е с я тем, что, с целью повышения надежности ипроизводительности, оно дополнительно содержит схему сравнения, элемент ИЛИ, полу сумма -.и суммйторы по модулю два, причем элементы И групп образуют матрицу, первые входы элементов И каждого д-го столбца которой объединены и подключены к () разряду входного кода устройства, к i-y разряду входного кода устройства подключены вторые входы i-ro элемента И всех столбцов матрицы, первый вход i-ro разряда схемы сравнения и первый вход i-ro разряда схемы