Устройство для извлечения квадратного корня

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств и машин. Цель изобретения -повышение быстродействия - достигается благодаря введению в устройство, содержащее сумматор 19, блок 23 начального приближения, блок управления 1, логический элемент И 17, группы 27, 28 элементов И, элементы задержки 2-4 и

СОЮЗ СОВЕТСНИК

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

А1 (192 (11) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМЪб СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4123951/24-24 (22) 23.06.86 (46) 30.05.88. Бюл. Р 20 (71) Киевский институт инженеров гражданской авиации им. 60-летия СССР (72) И.А. Жуков, А.М. Карцев, Л.Я. Нагорный и Д. Сингх (53) 681.325(088.8) (56) Авторское свидетельство СССР

11 553622, кл . G 06 F 15/32, 1977.

Введение в кибернетическую техни:ку: Обработка физической информации/

Под ред. Б.Н. Малиновского. Киев:

Наукова Думка, 1979, с, 156, рис. 59. (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к вычислительной технике и может быть испольэовано при построении специализированных вычислительных устройств и машин. Цель изобретения — повышение быстродействия — достигается благодаря введению в устройство, содержащее сумматор 19, блок 23 начального приближения, блок управления 1, логический элемент И 17, группы 27, 28 элементов И, элементы задержки 2-4 и

1399732 управляющий триггер 11, сумматоров

20-22, регистра приращений 26, второго и третьего блоков 24 и 25 начального приближения, третьей группы 29 элементов И, блока 30 преобразования

1

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

|х вычислительных устройств и машин. 5

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

На фиг. 1 представлена блок-схема п едлагаемого устройства; на фиг.2-5— с емы блока управления, блока преобр зования приближенного значения, второго.и третьего блоков начального приближенияй элемента 2И-4ИЛИ-НЕ и э1 емента И второго и третьего блоков н1 чального приближения; на фиг.6 и 7 - 15 схемы соединения элементов третьей группы элемептов И.

Па фиг. 1 обозначены блок 1 управ- " л ния, с первого по восьмой элементы

2 9 задержки, элемент НЕ 10, с перво-20

r по пятый управляющие триггеры

Ill-IS элемент ИЛИ 16, первый 17 н в арой 18 элементы И; с первого по четвертый сумматоры 19-22, блоки

2 3-25 начального. приближения, регистр25 ! 26 приращений, первая, вторая, и третья группы 27-29 элементов И и блок

30 преобразования приближенных знаЧенпй.

Блок управления содержит (фиг. 2) регистр 31 команд, дешифра-ор 32 коМанд, заторможенный мультивибратор

33, счетчик 34, многовходовый элемент ИЛИ 35 и многовходовый элемент

И 36.

Блок 30 (фиг. 3) образуют две групп элементов НЕ 37 и три группы

11, 111) элементов И 38, вторые входы которых объединены в одну вход- 40 иую шину блока 30.

Блоки 24 и 25 включают (фиг. 4)

Элемент 39 задержки, элементы НЕ 40, Элемент 2И-4ИЛИ-HE 41, элемент И 42, Элементы 43 и 44 постоянной памяти 45 (ПЗУ) и элементы И 45. приближенных значений, элемента ИЛИ

16, управляющих триггеров 12-15, элементов задержки 5-9, второго элемента И 18 и элемента НЕ 10 с соотвечствующими связями. 7 ил., l табл.

Злементы 41 и 42 содержат (фиг. 5} элемент ИЛИ 46, элемент НЕ 47 и элементы И 48. В качестве элементов 43 и 44 блоков 24 и 25 можно использовать, например, ПЗУ серии Е 155-РЕ3, в которые предварительно занесены входные значения согласно таблице.

В таблице символом + обозначено состояние О I т.е. для этого случая значение 0 на входе 1 ПЗУ РЕ3 определяет 1 на выходах А, В и С независимо от значени", ;, поступающих на входы 10-13.

Блок 29 (фиг. 6) содержит схемы

49» сдвига числа на заданное число разрядов. Для рассматриваемого примера 1 = 1,2,...,8. Каждая схема 49; (для примера t = 5) содержит элементы И 50 (фиг. 7).

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

В начале операции извлечения квадратного корня значение подкорениой величины в дополнительном коде заносится в сумматор 19.

Команда извлечения квадратного корня записана в регистре 31 блока 1.

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

Импульсы от мультивибратора 33 посту" лают на вход счетчика 34, уменьшая содержимое счетчика на единицу при каждом поступлении. Выходы всех разрядов счетчика 34 через многовходовый элемент ИХЛ 35 объединены в одну управляющую шину. На выходе элемента ИЛИ 35 единичныйсигнал сохраняется до тех пор, пока содержащееся в счет32

4 квадратного корня х = -Д:(у). Г выходов сумматоров 20 и 19 величины х и у поступает на первые и вторые входы элементов И 29, на третьи входы которых с выхода элемента 4 задержки поступает управляющий сигнал УЗ. Выходным значением группы 29 элементов

ЬУ

И является значение 1 х = =. -)-, ко2ЕЕ(х) торое является поправкой величины х.

Его знак определяется знаком величины х. Коррекция величины х как х;„ =

=х, + х; осуществляется в сумматоре

21,на вторые входы которого поступает значение х с выходов элементов И 29 (на первые входы сумматора 2! в этот момент ничего не поступает). С выходов сумматора 21 и регистра 26 значения х и х поступают на входы блоков

24 и 25. Одновременно на другие входы этих блоков поступает управляющий сигнал У4 от элемента 5 задержки, который позволяет прохождение значения

Е(х), равного старшей цифровой единице прямого кода значения х, на вход сумматора 20 (сумматор 20 предварительно обнуляется). Сигнал У4 разрешает прохождение величины Е(йх) с выхода блока 25 на вход блока 30, на другие входы которого поступает значение х с выхода сумматора 21. Одновременно на вход блока 30 поступает управляющий сигнал У5, разрешающий прохождение величины х, сдвинутой влево на 2Е(Ьх) разрядов, на вход сумматора 19, на выходах которого формируется очередное значение у.

Сигнал от блока 1 через элемент 3 задержки переводит управляющий триг

rep 1 из состояния "Ot в состояние

"1". Триггер 15 при этом остается в состоянии "0 . Требуемая длительность задержки управляющего сигнала элементом 3 задержки определяется исходя из условий одновременности появления управляющего сигнала УЗ на выходах блоков 16 и 4.

С выходов блоха 25 сигнал проходит через элемент 7 задержки и изменяет состояние триггеров 14 и !5 с "1" и

"0" на "0" и "1" соответственно. При каждой последующей итерации в определении величин Ьх, х и Ьу состояние триггеров 14 и 15 изменяется на противоположное, определяя управляющий сигнал новой итерации либо с выхода триггера 14, либо с выхода триггера э 13997 чике значение превышает нуль, т.е. пока хотя бы один из его разрядов содержит единицу. Этот сигнал, поступая на вход 2 элемента И 36 опредеэ

5 ляет длительность прохождения через элемент И 36 управляющего сигнала с выхода дешифратора 32.

В начале операции извлечения квадратного корня управляющие триггеры !О

ll-15 находятся в состоянии "0". Управляющий сигнал с выхода блока 1 поступает на счетный вход триггера 12 и на первый счетный вход триггера 11, переводя их в состояние 1, Посколь- !5 ку триггер 13 в это время находится в состоянии "0", то с выхода элемента

НЕ 10 на третий вход элемента И 18 поступает сигнал "I". На.первый и второй входы элемента И 18 сигналы 20 поступают с выходов блока 1 и триггера 12. Одновременно с выходов блока 1 и триггера 11 сигналы поступают на второй и первый входы элемента И 17.

На выходах элементов И 18 и 17 появ- 25 ляются управляющие сигналы Yl и У2 соответственно.

Управляющий сигнал Yl поступает на вход блока 23 и разрешает прохождение через него сигнала "1" с самого 30 старшего разряда сумматора 19, который находится в нулевом состоянии.

Поскольку в сумматоре 19 записан дополнительный код подкоренной величины

У, то на выходах 1-15 блока 23 (2 -2 35 соответственно) появляется значение

E(y), равное старшей цифровой единице прямого кода у. С выходов блока 23 значение Е(у) поступает на вторые входы элементов И 27 в качестве пер- 4О вого приближения подкоренной величины у. Кроме того, сигнал с выхода блока 23 поступает на вход триггера

13, переводя его в состояние "1", поэтому на входах элемента И 18 появ45 ляется сигнал "0", определяющий конец действия сигнала У1. На первые входы элементов И 27 поступает сигнал У2 с выхода элемента 2 задержки, разре" ,шая прохождение значения Е(у) в сум50 матор 19, где оно суммируется с дополнительным кодом подкоренной величины у. При этом результат Ьу на выходах сумматора 19 определяется как ду = Е(у) " у. Одновременно с величиной Е(у) с выходов блока 23 на входы. второго 20 и третьего 21 сумматоров поступает значение х, которое составляет первое приближение вычисляемого

1399732 6

h. -259

Q x э- .4

2Е х 2 .32

15. Время t каждой итерации при вычислении квадратного корня с помощью предлагаемого устройства определяется сдвигом числа, выделением старшей единицы и двумя сложениями и, следовательно, не намного превышает время итерации при вычислении с помощью

t известного устройства (— - 1 - 1,5).

При каждой итерации очередное зна-. чение ру определяется согласно выражению

:. >у „=ьу.-(2Е(Ьх;)x;+E. (ьх,) )

В этом выражении значение 2Е(х;}х +

+ (Ьх;) определяется блоком 30„ в кот >ром умножение величин х; и Ьх заменяется сдвигом значения х на Е(ах)

p ýðÿäîâ. Добавление единичного значения E(Zx;) практически не увеличивает задержку сигнала блоком 30. Параллельно с вычислениями вновь полученное значение gy;+, сравнивается в 25 блоке 30 с предельным минимальным значением (контрольным) у„, поступающим

Через вход 1 устройства. При удовлетворении условия hy „, «Ьу < значение

Квадратного корня с вь ода сумматора 30

21 передается иа вход устройства через элементы И группы 28, иа входы которых поступает разрешающий сигнал выхода сумматора 22. Для определения квадратного корня с помощью пред-, Аага<:мого устройства его начальиое

35 приближение, получаемое иа выходе блока 23, уточняется согласно выражеНию х =- †:-(- -, причем приращение pх

2Е(х7

40 является многоразрядным значением и определяется в блоке 29.

Пример. Извлечение квадратноГо корня из десятичного целого числа.

Пусть y -"- 2045. Требуется опредед5 лить х = +y.

Итерации"„

l. у,=Е(у)=Е(2045)=2 ; х,= у, =

=«2 = 2

48 ° 55

Е(ьх, ) h.ó, .=у"y, = 2045 — 1024 = 1021; ьу, 1021 „

gх = .,-У- = — -" 16.

2ЕE(x ) 2 32

2. х =х, +6х, = 32+ 16 у = у, - 2Е(ьх,)><, 259:

3. х = хам+ах = 48 — 4 = 44.

Для определения величины х = 44 от у =- .2045 с помощью известного устройства требуется Не- 3> а 13 итераций..

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

Устройство для извлечения квадрат ного корня, содержащее блок управления, первый сумматор, первый блок начального приближения, первый элемент

И„ первый вход которого соединен с выходом первого управляющего триггера; первый, второй и третий элементы задержки, первую и вторую группы элементов И, первые и вторые входы элементов И первой из которых подключены к выходам первого элемента задержки и первого блока начального приближе" иия, информационный вход которого соединен с выхо;,ом первого сумматора, первый вход которого подключен к выходам элементов И первой группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй, третий и четвертый сумматоры, регистр приращений, второй и третий блоки начального приближения, третья группа элементов И, блок преобразования приближенных значсний, второй, третий, четвертый и пятый управляющие триггеры, с четвертого по восьмой элементы задержки, элемент НЕ, причем выход блока управления подключен к второму входу первсго и первому входу второго зле ментов И, к первому входу первого управляющего триггера, к входам второго элемента задержки и второго уп-. равляющего триггера, выход которого соединен с вторым входом второго элемента И, третий вход которого подключен к выходу элемента HE вход которого соединен с выходом третьего управляющего триггера, вход которого и первые входы второго и третьего сумма оров подключены к выходу первого блока начального приближения, управляющий вход которого соединен с выходом второго элемента И, выход первого элемента И через первый элемент задержки подключен к входу тре" ,! тьего элемента задержки, выход которого и выход элемента ИЛИ соединены

1399732 с первыми входами элементов И тр -тьей группы и через ч::твертый элема ::г:: †:адержки с управляющими входами второго и третьего блоков начального приближения и входом пятого элемента задержки, выход которого соединен с управляющим входом блока преобразова.ния приближенных значений, первый и второй информационные входы которого 10 подключены соответственно к вьгходам третье о сумматора и третьего блока начального приближения, выход последнего из которых через шестой элемент задержки соединен с вторым входом 15 первого, первым .входом четвертого и входом пятого управляющих триггеров, выходы двух госледних из которых соответственно через седьмой и восьмой элементы задержки подключены к 2р первому и второму входам элемента

ИЛИ, второй вход четвертого управляющего триггера соединен с выходом второго элемента задержки, первый и второй входы элементов И второй груп" 25 пы соединены с выходами соответственно четвертого и третьего сумматоров, 1ьхзд последнего из которых и выход регистра приращений подключены к информационнь:м входам второго и третье."о блоков начального гриближения, вход регистра приращений и второй вход третьего сумматора соединены с выходами элементов И третьей группы, вторые входы элементов И которой первый вход четвертого сумма- о1а поп"ключены к выходу первого сумма-,ора. а третьи входы соединены с выходом второго сумматора, второй вход которого соединен с выходом второго блока началЬного приближения, второй и третий входы первого сумматора подключены соответственно к входу задания аргумента устройства и выходу блока преобразования приближенных значений, второй и третий входы четверто".: î сумматора соединены с входом задания минимального значения функции устройства и выходом перв orо блока начальных приближений соотв етственно, выходы элементов И второй группы являются выходом ус тройс тва . блока 44

1 О 0 О О

3 0 О 0 0

3 О 0 3 О

0 О 3 3

1 0 I О О

3 .О 3 0 l

i 0 l 1 0.3 О ) 1 !

3 О

1 1 О О

1 1 0 1 О

1 1 О 1 3

О 0 О

О 0 3

0 0 О

3 1 1 О О

Вхсды блока 43 . Выходи бло

5 14 3 (2 1 1Д2

Входы ПЗУ РЕ3 иходы ПЗУ

14 13 )2 )1 А В

I 0 О 0 О I I

0 О 0 0 0 0 О 0

О 0 О 1 I 0 О 0

О 0 1 0 0,0 1 0

О О 1 0 l О 0 0

О 0 I I О 1 О О

О 0 - I l. 1. 0 0 Î

0 3 О О 0 0 0 О

О I О. О ) О О 0.0 1 О ) 0 ) 0 О

0 l О l ) О ° 0 0

О l l 0 0 О 1 0

О О 1

О 3

О - О

3 1, 1

О О )

0 1

0 О 1

0 3 3

1399732

Продолжение таблицы г у

Взводы ПЗУ РЕЗ

Входы ПЗУ РЕ3

Выходы ПЗУ 3 Е

14 13 12 11

1/ ,! 1 О !

О 1 О

;О 1 .l 1! О О О

О 3 О О

3 l ! 0

О l !. 1 !

Вкоды блока 4З . Выходы блока

I IQT Г

5 4 3 . 2 1 1 2 3 5 4 3 2

14 13 12 3 l 10 А. В С

; О 3 1 I l 0 О О

0 О 1 ! О 1

О 3 ! I

1399732

1399732

@ac.5 риг. 7

Составитель Д,Си1и х

Техрец С.Сердюкова Корректор С. Черни

Редактор Л.Or ap

Тираж 704 Подписное

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

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

Закаэ 2666/48

rip o2l 8 Bogle TBe H rro-rrorrM rp aeHg e cKoe Греддрияти е Г. ymropop t ул. IIpoeKT B B8 ° 4