Арифметико-логическое устройство Советский патент 1990 года по МПК G06F7/38 G06F7/06 

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

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

Схема устройства представлена на чертеже.

Устройство содержит управляющий коммутатор 1, элемент ИСКЛОЧАЮИЩЕ ИЛИ 2, элемента И-НЕ 3, элемент НЕ 4, управляющий триггер 5, элемент И 6, регистр 7перезаписи и ri вычислительных блоков 8, где п - разрядность операндов. Каждый вычислительный блок содержи- регистры 9-11, сумматор- вычитатель 12, коммутаторы 13-17, элементы ИСКЛЮЧАРЩЕ ИЛИ 18,19, триггеры 20,21, элементы И 22 - 26, эле- менты ИЛИ 27 - 29, элемент НЕ 30, Устройство содержит также информаци- онные входы 31 - 33, тактовый-вход 34 входы задания режимов вычисления квадратного корня 35, деления 36, сортировки 37 и з множения 38, вход 39 начальной установки, информационные выходы 40-42,

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

Умножение в устройстве производится с младших разрядов множителя со сдвигом частного произведения вправо при неподвижном множимом. Частное произведение, в з ависимости от з наче- ния п-го и (п+1)-го разряда множителя получается или путем сложения содержимого регистра 9 с co epжимым регистра 11 (n4-1)lj, или путем i. вычитания содержимого регистра 11 из содержимого регистра (п+1)0 или в качестве частного произведения берет ся содержимое регистра 9; п (п+1) , .

Деление в устройстве сводится к

выполнению последовательности вычита НИИ (знак делителя равен знаку (i-1) го частного остатка) или суммирований (знак делителя не равен знаку (i-l)-ro частного остатка) делителя сначала с делимым, а затем с образо вавшимися в процессе деления частными остатками, сдвинутыми на один разряд влево. После каждого вычитания

-

с

ю

15 20 25 , Q

35

ддj ,

- 50

55

или сумми рования определяется значение i-ro разряда частного 1 (знак делителя равен знаку i-ro частного остатка) или О (знак делителя не равен знаку i-ro частного остатка),

Вычисление квадратного корня в устройстве сводится к выполнению последовательности операций вычитания (результат предыдущей операции положительный) или суммирования (результат предьщущей операции отрицательный) чисел, полученных в процессе вьиисле- ния, сначала из подкоренного выражения, а затем -из частных подкоренных выражений, за которые берутся результаты операций, сдвинутые на один разряд влево. Первая операция, которая выполняется - это вычитание числа 0,01, Знак результата этого вычитания определяет старший разряд результата вычисления квадратного корня (результат положительный - старший разряд , отрицательный - ), остальные разряды (Bg,,,,,) определяются аналогично. Последующие числа вычитания или суммирования получаются путем записи кода ,.4 3 два разряда.после разрядов результата извлечения корня квадратного.

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

При операции умножения на вход 38 подается логическая единица. Множимое и множитель поступают соответственно на входы 32 и 33, а на вход 31 при .этом поступает число нуль,

По первому тактовому импульсу в триггер 20 первого вычислительного блока записывается логическая единица, а в регистры 9, 11, 10 этого же вычислительнбго блока - соответственно нуль, множимое и множитель. Сигнал .с выхода триггера -20 задает суммато- ру-вьгчитателю операцию в.митания.

Значение п-го и (п+1)-го разрядов множителя поступают на входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 18, и в случае.

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

Информация с выходов элемента ИС- KJlI04AJiPJEE ИЛИ 18 проходит через элементы И 22,23 и поступает на управлящие входы коммутаторов 14 и 17.

Коммутатор 14 в зависимости от информации на его управляюпщх входах может переставать на выход сдвинутый вправо на один разряд код либо с выхда регистра 9, либо с выхода суммато ра-вычитателя 12. Код с выхода коммутатора 14 первого вычислительного блока 8 поступает на вход первого регистра 9 (п старших разрядов) второго вычислительного блока 8.

Значение п-го разряда множителя чрез коммутатор 13 поступает на информационный вход триггера 20 второго вычислительного блока 8;. Множимое с выходов регистра 11 (кроме второго и третьего разрядов) поступает на вход соответствующих разрядов регистра 11 второго вычислительного блока 8. Второй и третий разряд множимого через коммутатор 15 пос гупает на входы второго и третьего разрядов регистра 11 второго вычислительного блока B-j.

По второму тактовому импульсу информация с выходов первого вычислительного блока 81 записывается в триггеры 20, 21, регистры 9-11 второго вычислительного блока .. Одновременно в первый вычислительный блок 8 записываются новые числа для выполнения операции умножения. В каждом вычислительном блоке 8 выполняется одна микрооперация алгоритма умножения. Результат умножения с удвоенной точностью формируется на выходах коммутаторов 14,17 и регистра 10 п-го .вычислительного блока 8 г после прохождения данных через все вычислительные блоки 8, т.е. после п-го тактового импульса.

При. операции деления на вход 36 подается потенциал, логической еди-. ницы.

Старшие разряды делимого (первое полуслово) поступают на вход 31, а его младшие разряды (второе полуслово) - на вход 33, причем младший разряд второго полуслова поступает на вход первого разряда этого информационного входа. Делитель поступает на

10

15

20

25

5

30

35

40

45

0

5

вход 32. Знаковые разряды делимого и делителя поступают на входы элемента ИСКЛЮЧАЮ1ЦЕЕ ИЛИ 2, на выходе которого формируется знак частного, который записывается в триггер 20 первого вычислительного блока 8(.

По первому тактовом импульсу делитель и делимое записываются в регистры 9 - 1 1 . -.

Сигнал с выхода триггера 20 устанавливает сумматор-вычитатель 12 или в режиме вычитания (логическая единица) или в режим суммирования (логический нуль). Инверсное значение знака результата, полученное на выходе сум- матора-вычитателя 12 поступает на вход элемента ИСКГИОЧАЮР ЕЕ ИЛИ 19, на другой вход которого поступает знак делителя.

В случае равенства этих знаков на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 19 формируется сигнал логического нуля, которьй через кo мyтaтop поступает на вход триггера 20 второго вычислительного блока 82.

Код с выходов суммаТора-вычита- теля 12, сдвинутый влево на один разряд, проходит через коммутатор 14 и поступает на входы старших разрядов регистра 9 второго вычислительного блока 8. На вход младшего разряда регистра 9 второго вычислительного блока 8j поступает код с выхода п-го. разряда регистра 10 первого вычислительного блока 84, прошедишй через п-й разряд коммутатора 14 этого вычислительного блока. Код с выхода коммутатора 17 поступает на вход первого разряда регистра 10 второго вычислительного блока 82. На входы остальных разрядов регистра 10 поступает код с выходов регистра 10 первого вычислительного блока В, сдвинутый вправо на один разряд. Делитель с выхода регистра 11 через кoм гi тaтopы 16 и 15 поступает на входы соответствующих разрядов регистра 11 второго вычислительного блока 85.

По второму тактовому импульсу информация с выходов первого вычислительного блока 8 записывается в триггеры 20, 21, регистры 9-11 гзторого вычислительного блока 82.

Одновременно в первый вычислительный блок 8ч записываются новые дели- j тель и делимое для выполнения операции деления. В каждом вычислительном блоке 8 выполняется одна итерация алгоритма деления. Результат деления формируется на выходах 1-го 2-го... (n-l)-ro разрядов регистра 10 .и ком- мутатора 17 п-го вычислительного блрка 8п, причем информация на выходе ,(п-1)-го разряда регистра 10 является знаком результата, а информация на выходе коммутатора 17 - младпшм разрядом частного.

При вычислении квадратного корня на вход 35 подается потенциал логической единицы. Старшие разряды подкоренного числа (первое полуслово) поступают на вход 31, младшие разряды (второе полуслово) - на вход 32, причем младший разряд второго полуслова поступает на вход первого разряда этого входа. На вход 33 поступает нуль. На выходе элемента И-НЕ 3 устанавли- вается потенциал логической единиг№1, которьй поступает на вход триггера 20 первого вычислительного блока 8. Потенциал логической единицы с входа 35 поступает на входы установки в едини- цу третьего, четвертого...-(i+2)-го разрядов регистров 11 соответственно первого Si, второго 8з1...8-1 вычислительного блока и устанавливает данные разряды регистров 11 в единичные зна- чения. .

По первому тактовому импульсу в триггер 20 первого вычислительного блока 8 г записывается логическая единица, а в регистры 9 - 11 этого же вычислительного блока - код подкоренного выражения и нуль с входов 31 - 33 соответственно. На сумматоре-вы- читателе 12 происходит вычитание сб- держимого регистра 10 (0.010.,.0) из содержимого регистра 9. Результат вычитания, .сдвинутый влево на один разряд, проходит через коммутатор 14 и поступает на входы старших разрядов регистра 9 второго вычислительного блока 8й. На вход младшего разряда регистра 9 поступает код с выхода п-горазряда регистра 10 первого вычислительного блока B, прошедший через п-й разряд коммутатора 14 этого вычислительного блока.

Инверсное значение знака результата вычитания, полученное на выходе сумматора-вычитателя 12, поступает на вход элемента ИС1ШОЧАЮ1 Ц5Е ИЛИ 19, на другой вход которого поступает сигнал логического нуля с выхода первого разряда регистра 11.- В случае равенства этих знаков на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 19 формируется логический нуль, который через коммутаторы 13 и 17 поступает соответственно на вход триггера 20 и на вход первого разряда регистра 10 второго вычислительного блока 82. Код с выходов регистра 11 (кроме второго и третьего разрядов), через коммутатор 16 поступает на входы соответствующих разрядов регистра 11 второго вычислительного блока 8. На второй и третий разряд данного регистра 11 поступает соответственно инверсное и прямое значение знака вычитания, прошедшее через коммутатор 15.

Код с выходов регистра 11, сдвинутый вправо на один разряд, поступает на входы регистра 11 второго вычислительного блока 8.

По второму тактовому импульсу информация с выходов первого вычислительного блока 84 записывается в триггеры 20,21 и в регистры 9-11 второго вычислительного блока 8 д. Одновременно в первый вычислительный блок 8 1 записывается новое подкоренное вьфажение для извлечения квадратного корня. В каждом вычислительном блоке 8 выполняется одна, итерация алгоритма вычисления квадратного корня.

Результаты вычисления квадратного корня формируются на выходе коммутаторов 16 и 15 п-го вычислительного блока .8.

При сортировке на вход 37 подается потенциал логической единицы. Перед началом сортировки импульсом с входа 39 начальной установки триггер 21 п-го вычислительного блока 8 fj устанавливается в нулевое состояние. Сортируемые числа поступают на вход 31, а на входы 32 и 33 поступают нули. Потенциал логической единицы с входа 37 поступает на входы установки в единицу триггеров 20 и уста- . навливает их в единичное состояние.

По переднему фронту первого тактового импульса в регистр 9 всех вычислительных блоков 8 записывается первое число сортируемого массива, а в триггер 5 - нуль.

За время первого тактового импульса сигнал логической единицы с инверсного выхода триггера 5, проходя через элемент И 6, устанавливает тригеры 21 во всех вычислительных блов единичное состо

как 8 и триггер 5 яние.

По второму тактовому импульсу происходит запись второго числа из сортируемого массива в регистры 7 и 9, запись первого числа с выходов коммутатора 1 в регистр 9 первого вычислительного блока 8(; перезапись кодов с выходов коммутаторов 16 и 15 предыдущих вычислительных блоков в регистры 9 последующих вычислительных блоков 8; запись нуля с инверсного выхода триггера 5 в триггер 21 первого вычислительного блока 8(. В первом вычислительном блоке 8 из содержимого регистра 9 вычитается содержимое регистра 11. Если содержимое регистра 9 больше или равно содержимому регистра 1 1 , то на инверсном выходе знаково го разряда сумматора-вычитателя формируется сигнал логической единицы, и сигнал логического нуля - в противном случае.

Этот сигнал через элемент 1-ШИ 28 поступает на вход элемента И 25, где он разрешает (логическая единица) или запрещает прохождение тактовых импульсов через этот элемент. Кроме этого, данный сигнал управляет переклю- чением коммутаторов 16 и 15.

По третьему тактовому импульсу происходит запись третьего числа из сортируемого массива в регистры 7 и 9 перезапись информации с выходов коммутаторов 16 и 15 пред1, вычислительных блоков 8 в регистры 11 последующих вычислительных блоков 8, за- пись нуля с выхода триггера 21 первого вычислительного блока 8 в триггер 21 второго вычислительного 82, запись кода с выходов коммутатора 1 (для случая, когда второе число больше первого) в регистр 11 первого вычислительного блока 8.

По приходу следующих тактовых импульсов устройство работает аналогично ;

По фронту ()-го тактового импульса происходит запись первого числа второго сортируемого массива в регистры 7 и 9, запись кода с выходов коммутаторов 16,15 предыдущих вычислительных блоков 8 в регистры 11 последующих вычислительных блоков 8, запись логического нуля с выхода триггера 21 п-го вычислительного блока 8 ri в триггер 5.

За время (п+1)-го тактового импульса сигнал логической единицы инверсного выхода триггера 5 через элемент И 6 устанавливает все триггеры 21 и триггер 5 в единичное состояние.

После поступления (п+1)-го тактового импульса числа первого массива отсортированы в порядке убывания (наибольшее число находится в регистре 9 первого вычислительного блока 8) .

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

20

5

Формула изобретения Арифметико-логическое устройство, содержащее элемент HCKJUOHAIOIiJEE ИЛИ, элемент И-НЕ и п вычислительных блоков, где п - разрядность операндов, каждый вычислительный блок со25 держит три регистра, сумматор-вычи- татель, первый триггер, первый элемент ИЛИ, элемент НЕ, два элемента И, два элемента ИСКП аЧАЮ1 (ЕЕ ИЛИ и три коммутатора, причем в каждом i-м вычислительном блоке, где ,2,3..., п, входы первых разрядов первой и второй групп устройства соединены соответственно с первым и вторым входами элемента ИСКЛПЧАМ1ЦЕЕ ИЛИ, выход которого соединен с первым входом элемента И-НЕ, второй вход которого подключен к входу задания режима деления устройства, выход элемента И-НЕ соединен с информационным входом первого триггера первого вычислительного блока, входы первой и третьей групп устройства соединены с информационными входами соответственно первого и второго регистров первого вычислитель5 ного блока, вход задания режима вычисления квадратного корня устройства соединен в i-м вычислительном блоке с первым входом первого элемента ИЛИ и входом установки в единичное состояние (i+2)-ro разряда третьего регистра, вход задания режима деления устройства соединен с вторыми входами первых элементов ИЛИ всех вычислительных блоков, вход задания режима умножения устройства соединен с первыми входами первого и второго элементов И и первыми управляющими входами первых коммутаторов всех вычислительных блоков, тактовый

0

0

5

вход устройства соединен с входами - синхронизации первых триггеров и первых и вторых регистров всех вычислительных блоков, в i-M вычислительном блоке выход первого триггера соединен с управляющим входом сумматора-вычи- тателя, выходы разрядов первого ре- гистра соединены с входами соответствующих разрядов первой группы информационных входов сумматора-вычитателя и со сдвигом на один разряд в сторону младших разрядов - с входами разрядов первой группы информационных входов второго коммутатора, выходы разрядов сумматора-вычитателя соединены .со сдвигом на один разряд в сторону младишх разрядов с входами разрядов второй группы информационных входов второго коммутатора и, со сдвигом на один разряд в сторону старших разрядов - с входами разрядов третьей группы информационных входов второго коммутатора, первый и второй управляющие входы которого подключены к выходу соответственно первого и второго элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам первого элемента ИСКЛОЧА10ЩЕ ИЛИ, первый, и второй входы которого подключены к выходам соответственно п-го и (п+1)-го разрядов второго регистра, выход первого элемента ИЛИ соединен с вторым управляющим входом первого коммутатора и третьим управляющим входом второго коммутатора, выходы разрядов третьего регистра соединены с входами соответствующих разрядов второй группы информационных входов сумматора-вычитателя, выходы (i+1)--ro и (i+2)-ro разрядов третьего регистра соединены с входами соответственно первого и второго разрядов первой группы информационных входов третьего коммутатора, прямой и инверсный выходы первого , разряда сумматора-вычитателя соедине- ны с входами соответственно первого и второго разрядов второй группы информационных входов третьего коммутатора, инверсньш вьрсод первого разряда су матора-вычитателя соединен с первым, входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого подключен к выходу первого разряда третьего регистра, первый и второй информационные входы первого коммутатора подключены соответстаенно к выходу п-го разряда второго регистра и к выходу

второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход j-ro разряда второго регистра -вычислительного блока, где ,3, mn; ,2...n-1| соединен с информационным входом j-ro разряда второго регистра (k+1)-ro вычислительного блока, выход j-ro разряда второго регистра п-го вычислительного блока

является J-M разрядом первой группы выходов устройства,, вход п-го разряда третьей группы информационных входов второго коммутатора подключен к выходу .п-го разряда второго регист5 Ра выход первого коммутатора k-ro вычислительного блока соединен с информационным входом первого триггера (k+1)-ro вычислительного блока, группа выходов второго коммутатора и вы0 ходы первого и второго разрядов третьего коммутатора k-ro вычислительного блока соединены соответственно с информационными .входами соответствующих разрядов первого регистра и с

5 информационными входами (k+1)-ro и (k+2)-ro разрядов третьего регистра (k-i-l)-ro вычислительного блока, группа- выходов второго коммутатора п-го вычислительного блока является вто0 рой группой выходов устройства, отличающееся тем, что, с целью расширения функциональных возможностей путем обеспечения выполнения сортировки чисел, в него введены регистр перезаписи, управляющий триггер, элемент И, управляющий коммутатор, элемент НЕ, а в каждый вычислительный блок - второй триггер, третий, четвертый и пятый элементы И, второй

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

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

0 коммутатора, выходы разрядов второго коммутатора п-го вычислительного блока соединены с инфopмaциoнньnvIи входами соответствующих разрядов регистра перезаписи, входы второй группы устг ройства и выходы разрядов регистра перезаписи соединены соответственно с первой и Второй группами информационных входов управляющего коммутатора, выходы которого соединены с ин13 .15

формационными входами соответствующих разрядов третьего регистра первого вычислительного блока, выход второго триггера k-ro вычислительного блока соединен с информационным входом второго триггера (k+1)-ro вычислительного блока, выход второго триггера п-го вычислительного блока соединен с информационным входом управляющего триг гера, инверсный выход которого соединен с информационным входом второго триггера первого вычислительного блока и с первым входом элемента И, выход которого соединен с входами уста- норки в единичное состояние вторых триггеров всех вычислительных блоков и управляющего триггера, вход синхронизации которого, а также второй вход элемента И и входы синхронизации регистра перезаписи и вторых триггеров и вторые входы третьих элементов И всех вычислительных блоков подключены к тактовому входу устройства, в i-M вьтислительном блоке вход зада- ния режима сортировки устройства соединен с первыми входами четвертого и пятого элементов И, входом установки в.единичное состояние первого триг

гера, четвертым управляющим входом второго коммутатора и через элемент НЕ - С вторым .входом второго элемента КТИ, прямой выход которого соединен с вторыми входами третьего и пятого элементов И, выход пятого элемен та И соединен с первым входом третьего элемента 1ШИ, выход которого соединен с первым управляюидим входом .третьего коммутатора, вход задания режима вычисления квадратного корня устройства соединен с вторыми управляющими входами третьих коммутаторов всех вычислительных блоков, входы задания режимов деления и умножения устройства соединены соответственно с вторыми и третьими входами третьих элементов ИЛИ всех вьтислительных блоков, входы первой группы устройства соединены с информационными входами четвертых групп вторых коммутаторов всех вычислительных блоков, в i-M вычислительном блоке инверсный выход первого разряда сумматора -вычи

14

д i о 50

0

.

5

0

тателя соединен с вторым входом второго элемента ИЛИ, инверсный выход которого соединен с вторым входом четвертого элемента И, прямой выход которого соединен с третьим управляющим входом третьего jcoMMyfaTopa и первым, уаравлякицим входом четвертого коммутатора, второй управляющий вход, ко- торого подключен к инверсному выходу четвертого элемента И, выход второго триггера соединен с третьим входом второго элемента ИЛИ, выходы разрядов первого и третьего регистров, кроме их (i+1)-ro и (i-f2)-ro разрядов соединены с входами соответствующих разрядов соответственно первой и второй групп информационных входов четвертого коммутатора, вьрсоды (i+1)-ro и (i+2)-ro разрядов первого регистра соединены соответственно с входами первого и второго разрядов третьей группы информационных входов третьего коммутатора, выход второго элемента ИСКЛ11)ЧА101ЦЕЕ ИЛИ и выходы п-х разрядов сумматора-вычитатеогя и первого регистра соединены соответственно с первым, вторым и третьим информационными входами пятого коммутатора, первый, второй и третий управляюп ие входы которого подключены к выходам соответственно первого элемента ИЛИ, второго и первого элементов И, выход третьего элемента И соединен с входом синхронизации третьего регистра, выходы разрядов четвертого коммутатора kro вычислительного блока соединены с информационными входами срответст- вующих разрядов, кроме (k+D-ro и (k+2)-ro разрядов первого и третьего регистра (k+1)-ro вычислительного блока, выход пятого коммутатора k-ro вычислительного блока соединен с ин- формаищонным входом первого разряда второго регистра (k+1)-ro вычислительного блока, выход пятого коммутатора п-го вычислительного блока является первым разрядом первой группы выходов устройства, группа выходов четвертого коммутатора п-го вычислительного блока является третьей группой выходов устройства.

Изобретение относится к вычислительной технике. Цель изобретения - расширение функциональных возможностей. Устройство содержит управляющий коммутатор 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 2, элементы И-НЕ 3, элемент НЕ 4, управляющий триггер 5, элемент И 6, регистр 7 перезаписи и N вычислительных блоков 8₁-8_N, где N - разрядность операндов. Каждый вычислительный блок содержит регистры 9,10,11, сумматор-вычитатель 12, коммутаторы 13-17, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 18,19, триггеры 20,21, элементы И 22-26, элементы ИЛИ 27,28,29, элемент НЕ 30. Устройство содержит также информационные входы 31,32,33, тактовый вход 34, входы 35-38 задания режимов, вход 39 начальной установки, информационные выходы 40,41,42. Изобретение позволяет выполнять операции умножения, деления, извлечения квадратного корня и сортировки массива чисел. 1 ил.