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

О)

&э со со

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

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

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

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

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

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

На фиг. 1 обозначены блок управ™ ЛИНИЯ, c nepBci o по восьмой элементы задержки, элемент НЕ 10, с пер вого по пятый управляющие триггеры 11-15, элемент 1ШИ 16, первый 17 и второй 18 элементы И с первого по четвертый сумматоры 19-22, блоки 2J3-25 начального приближения, регистр 2|6 приращений, первая, вторая, и тре- TJbH группы 27-29 элементов И и блок 0 преобразования приближенных зна- енпй

Блок управления содержит (фиг. 2) регистр 31 команд, дешифратор 32 команд, заторможенный мультивибратор 33, счетчик 34, многовходовый элемент lUHi 35 и многовходовый элемент И 36.

Блок 30 (фиг. З) образуют две - 1группы элементов НЕ 37 и три группы |1, М, Ml) элементов И 38, вторые «ходы которых объединены в одну вход- Ную шину блока 30.

Блоки 24 и 25 включают {фиг. 4) Элемент 39 задержки, элементы НЕ 40, элемент 2И-4ИЛИ-КЕ 41, элемент И 42, элементы 43 и 44 постоянной памяти (ПЗУ) и элементы И 45.

Элементы 41 и 42 содержат (фиг. 5) элемент ИЛИ 46, элемент НЕ 47 и элементы И 48. В качестве элементов 43 и 44 блоков 24 и 25 можно использовать, например, ПЗУ серии Е 155-РЕЗ, в которые предварительно занесены входные значения согласно таблице. В таблице символом обозначено состояние 9VI, т.е. для этого случая значение О на входе 1 ПЗУ РЕЗ определяет 1 на выходах А, В и С независимо от значений, поступающих на входы 10-13,

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

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

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

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

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

В начале операции извлечения квадратного корня управляющие триггеры Н-15 находятся в состоянии О. Управляющий сигнал с выхода блока 1 поступает на счетный вход триггера J2 и на первый счетный вход триггера 11,

10

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

ЛУ

га

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

И

является значение лх -,.

UXJ осуществляется в сумматоре

переводя их в состояние 1. Посколь-15 21,н вторые входы которого поступает

значение лх с выходов элементов И 29 (на первые входы сумматора 21 в этот момент ничего не поступает) . С выходов сумматора 21 и регистра 26 значе- второй входы элемента И 18 сигналы 20 ния х и дх поступают на входы блоков поступают с выходов блока 1 и триггера 12. Одновременно с выходов блока 1

ку триггер 13 в это время находится в состоянии О, то с выхода элемента НЕ 10 на третий вход элемента И 18 поступает сигнал I. На.первый и

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

и триггера 1I сигналы поступают на второй и первьш входы элемента И 17.

сигнал Y4 от элемента 5 задержки, который позволяет прохождение значения

На выходах элементов И 18 и 17 появ- 25 Е(Х), равного старшей цифровой едиляются управляющие сигналы Y1 и Y2 соответственно.

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

нице прямого кода значения х, на вход сумматора 20 (сумматор 20 предварительно обнуляется). Сигнал Y4 разрешает прохождение величины Е(&х) с вы чение X с выхода сумматора 21. Одновременно на вход блока 30 поступает управляющий сигнал Y5, разрешающий

Поскрльку в сумматоре 19 записан дополнительный код подкоренной величины У, то на выходах 1-15 блока 23 (, соответственно) появляется значение Е(у), равное старшей цифровой единице прямого кода у. С выходов блока 23 значение Е(у) поступает на вторые входы элементов И 27 в качестве первого приближения подкоренной величины у. Кроме того, сигнал с выхода блока 23 поступает на вход триггера 13, переводя его в состояние 1, поэтому на входах элемента И 18 появляется сигнал О, определяющий конец действия сигнала Y1. На первые входы элементов И 27 поступает сигнал Y2 с выхода элемента 2 задержки, разре- шая прохождение значения Е(у) в сумматор 19, где оно суммируется с дополнительным кодом подкоренной величины у. При этом результат Ду на выходах сумматора 19 определяется как ДУ Е (у.) У. Одновременно с вепичи чение X с выхода сумматора 21. Одновременно на вход блока 30 поступает управляющий сигнал Y5, разрешающий

35 прохождение величины х, сдвинутой влево на 2Е(дх) разрядов, на вход сумматора 19, на выходах которого формируется очередное значение Лу. Сигнал от блока I через элемент 3

40 задержки переводит управляющий триггер 1 из состояния О в состояние 1. Триггер 15 при этом остается в состоянии О. Требуемая длительност задержки управляющего сигнала элемен

45 том 3 задержки определяется исходя из условий одновременности появления управляющего сигнала Y3 на выходах блоков 16 и 4.

50

С выходов блока 25 сигнал проходи через элемент 7 задержки и изменяет состояние триггеров 14 и 15 с 1 и О на О и 1 соответственно. При каждой последующей итерации в опреде лении величин Дх, X и ду состояние

- / - ,, /- г-.f - -,,

ной Е(у) с выходов блока 23 на входы. триггеров 14 и 15 изменяется на про- втррого 20 и третьего 21 сумматоров тивоположное, определяя управляющий поступает значение х, которое составляет первое приближение вычисляемого

сигнал новой итерации либо с выхода триггера 14, либо с выхода триггера

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

ЛУ

га

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

И

является значение лх -,.

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

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

сигнал Y4 от элемента 5 задержки, который позволяет прохождение значения

Е(Х), равного старшей цифровой едихода блока 25 на вход блока 30, на другие входы которого поступает зна

нице прямого кода значения х, на вход сумматора 20 (сумматор 20 предварительно обнуляется). Сигнал Y4 разрешает прохождение величины Е(&х) с выхода блока 25 на вход блока 30, на другие входы которого поступает зна

чение X с выхода сумматора 21. Одновременно на вход блока 30 поступает управляющий сигнал Y5, разрешающий

прохождение величины х, сдвинутой влево на 2Е(дх) разрядов, на вход сумматора 19, на выходах которого формируется очередное значение Лу. Сигнал от блока I через элемент 3

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

50

С выходов блока 25 сигнал проходит через элемент 7 задержки и изменяет состояние триггеров 14 и 15 с 1 и О на О и 1 соответственно. При каждой последующей итерации в определении величин Дх, X и ду состояние

,,

триггеров 14 и 15 изменяется на про- тивоположное, определяя управляющий

сигнал новой итерации либо с выхода триггера 14, либо с выхода триггера

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

I При каждой итерации очередное (кие йу определяется согласно выражан1«о

тёта

-259 2 -32

s -4.

Д8 - 4 44.

10

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

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

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

20 задержки, первую и вторую группы элементов И, первые и вторые входы элементов И первой из которых подключены к выходам первого-элемента задержки

15 первого блока начального приближе- 4teHHoe значение U у Ui сравнивается в 25 i. i „,, u г ц.| информационный вход которого .tf« QM л TTr4i-trrrt Ttt tiT-tTii rrT-TJt TX ат-ТЯ-

йу;, ()+(

В этом выражении значение 2Е(йХ ,)x + f-l;;(йx ;) определяется блоком 30, в котором умножение величин х; и их заменяется сдвигом значения х на Е(йх) разрядов. Добавление единичного значения Е(ДХ; ) практически не увеличи- в|ает задержку сигнала блоком 30. Па- рйллельно с вычислениями вновь полубЬоке 30 с предельным минимальным зна Чением (контрольным) ду, поступающим Через вход 1 устройства. При удовлетворении условия , ЛУ (; значение Квадратного корня с выхода сумматора 21 передается на вход устройства че- элементы И группы 28, на входы 5|готорык поступает разрещающий сигнал выхода сумматора 22. Для определе- фия квадратного корня с помощью пред- фагасмого устройства его начальное :|1риближение, получаемое на-выходе блока 23, уточняется согласно выраже30

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

35 блок .преобразования приближенных значений, второй, третий, четвертый и . пятьв управляющие триггеры, с четвертого по восьмой элементы задержки, элемент НЕ, причем в ыход блока уп|1И50 U.X

причем приращение их

г. ч X /

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

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

Пусть у г 2045. Требуется определить X 47Итерацииs

&у.:у-у, 2045 - 1024

йх,

16,

Xj и- их, 32 + 16 48;

Уг йу, 2Е(йх,)х, - Е{йх,) - 259;

тёта

-259 2 -32

s -4.

Д8 - 4 44.

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

0

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

5 блок .преобразования приближенных значений, второй, третий, четвертый и . пятьв управляющие триггеры, с четвертого по восьмой элементы задержки, элемент НЕ, причем в ыход блока уп0 равления подключен к второму входу первого и первому входу второго ментов И, к первому входу первого управляющего триггера, к входам второго элемента задержки и второго уп-.

5 равляющего триггера, выход которого соединен с вторым входом второго элемента И, третий вход которого подключен к выходу элемента НЕ, вход которого соединен с выходом третьего

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

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

713997328

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

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

второй входы элементов И второй груп 25 ственно , выходы элементов И пы соединены с выходами соответствен- второй группы являются выходом но четвертого и третьего сумматоров, . ..устройства.

Лл 2

3L.

3d

ЗЕ

3

Фа2.2

2J

фИ.З

16