Арифметико-логическое устройство

Арифметико-логическое устройство

Иллюстрации

Показать все

Реферат

 

АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТ- : РОЙСТВО, содержащее п последовательно соединенных решающих блоков, где празрядность операндов, каждый из которых включает три регистра , сумматор, три коммутатора и п узлов управления записью операндов, которые включают элемент ИЛИ и два элемента И, выходы которых соединены с входами элемента ШШ причем первая группа информационных входов устройства соединена с входами первого регистра первого решающего блока, вторая группа информационных входов устройства подключена к первым входам элементов И узла управления записью операнда соответствующего разряда, выходы элементов ИЛИ узлов управления записью операндов соединены с соответствующими входами второго.регистра первого решающего блока, третья группа информационных входов устройства соединена с входами третьего регистра первого решающего блока, выходы разрядов первого регистра k-ro решающего блока, где ,2,...,n, соединены с первой группой входов сумматора, прямые выходы разрядов второго регистра i-ro решающего блока, где ,2,..., (п-1), соединены с входами второго регистра (i+l)-ro разрешающего блока,инверсный ипрямой выходы (i)-го разряда второго регистра k-ro решающего блока соединены с информационными входами первого коммутатора, выход первого коммутатора соединен с вторым входом (i+l)-ro разряда сумматора k-ro решающего блока, прямые выходы k-x разрядов третьего регистра i-ro решающего блока соединены с входами (k-l)-x разрядов треi тьего регистра (i+l)-ro решающего блока, выход второго коммутатора (Л i-ro решающего блока соединен с входом разряда второго регистра (i+l)-ro решающего блока, первый и второй информационные входы второго коммутатора k-ro решающего блока соединены соответственно с прямым выходом к-го разряда второго ре sj гистра и с инверсным выходом знаОд кового разряда сумматора k-ro решаСО N9 ющего блока, в каждом решающем бло-ке информационные входы с первого по четвертый k-ro разряда третьего коммутатора соединены соответственно с выходом (k-l)-ro разряда первого регистра, выходом (k+l)-ro разряда первого регистра, выходом (k-l)-ro разряда сумматора, выходом (k+l)-ro разряда сумматора, управляющие входы третьего коммутатора соединены соответственно с прямым и инверсным выходами знакового разряда сумматора и первого разряда третьего регистра, выход k-ro раз

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

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

РЕСПУВЛИК (51)4 G 06 F 7/38

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3612890/24-24 (22) 01.07.83 (46) 30.08.85. Бюл. № 32 (72) Н.В.Черкасский и Р.М.Фернеза (71)Львовский ордена Ленина политехнический институт им. Ленинского комсомола (53) 68).325(088.8) (56) Авторское свидетельство СССР № 798825, кл. G 06 F 7/38, 1977.

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

¹ 993252, кл. G 06 F 7/38, 1981. (54)(57) АРИФ))ЕТИКО-ЛОГИЧЕСКОЕ УСТРОЙСТВО, содержащее и последовательно соединенных решающих блоков, где П вЂ” разрядность операндов, каж-. дый из которых включает три регистра, сумматор, три коммутатора и n . узлов управления записью операндов, которые включают элемент ИЛИ и два элемента И, выходы которых соединены с входами элемента ИЛИ, причем первая группа информационных входов устройства соединена с входами первого регистра первого решающего блока, вторая группа информационных входов устройства подключена к первым входам элементов И узла управления записью операнда. соответствующего разряда, выходы элементов ИЛИ узлов управления записью операндов соединены с соответствующими входами второго. регистра первого решающего блока, третья группа информационных входов устройства соединена с входами третьего регистра первого решающего блока, выходы разрядов первого регистра k-го решающего блока, где k=),2,...,ï, соединены с пер„„SU„„1176321 A вой группой входов сумматора, прямые выходы разрядов второго регистра

i-ro решающего блока, где i=1,2,..., (n-l), соединены с входами второго регистра (i+l)-го разрешающего блока,инверсный ипрямой выходы (i+))-го разряда второго регистра ),-го решающего блока соединены с информационными входами первого коммутатора, выход первого коммутатора соединен с вторым входом (i+l)-ãî разряда сумматора k-ro решающего блока, прямые выходы k-х разрядов третьего регистра i-го решающего блока соединены с входами tk-1)-х разрядов третьего регистра (i+1)-ro решающего Е

Q блока, выход второго коммутатора

j-ro решающего блока соединен с входом Q-го разряда второго регистра С» (i+1)-го решающего блока, первый и второй информационные входы второго коммутатора k-го решающего блока соединены соответственно с прямым выходом к-го разряда второго регистра и с инверсным выходом знакового разряда сумматора k-го реша- ОЪ ющего блока, в каждом решающем бло- Col ке информационные входы с первого Я по четвертый К-го разряда третьего ива коммутатора соединены соответственно с выходом (1с-1)-ro разряда первого регистра, выходом (1+1)-го разряда первого регистра., выходом (k-1)-го разряда сумматора, выходом,файв (k+1)-ro разряда сумматора, управляющие входы третьего коммутатора соединены соответственно с прямым и инверсным выходами знакового разряда сумматора и первого разряда третьего регистра, выход k-го раз1176321 ряда третьего коммутатора i-ro решающего блока соединен с входом k-ro разряда первого регистра (i+1)-ão решающего блока, инверсный выход знакового разряда i-ro решающего .блока соединен с входом п-ro разряда третьего регистра (i+I)-го решающего блока, в k-м решающем блоке инверсные выходы всех разрядов второго регистра, кроме (k+1)-ro, соединены с второй группой входов сумматора, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет выполнения операции сортировки, в него введен блок управления, включающий генератор тактовых импульсов, элементы И, ИЛИ, триггер, счетчик, дешифраторы и и узлов анализа, каждый из которых содержит триггеры, элементы ИЛИ, И, в каждый решающий блок введены четвертый и пятый коммутаторы, причем в каждом решающем блоке инверсные выходы второго регистра соединены с соответствующими информационными входами первой группы четвертого коммутатора, информационные входы второй группы которого подключены к инверсным выходам пятого коммутатора n-ro решающего блока, первый и второй управляющие входы i-ro разряда четвертого коммутатора подключены к выходу (i+1)-ro разряда четвертого коммутатора и к первому управляющему входу i-го разряда пятого коммутатора, первый информационный вход К-го разряда пятого коммутатора подключен к инверсному выходу k-ro разряда второго регистра, вторые управляющие и информационный входы k-го разряда пятого коммутатора (i+1)-ro решающего блока объединены и соединены с прямым выходом fc-ro разряда пятого коммутатора q-ro решающего блока, в первом решающем блоке вторые информационные и управляющие входы пятого коммутатора объединены и соединены с шиной нучевого потенциала устройства, подключенной также к пятому информационному входу К-разряда пятого коммутатора, выход k-го разряда пятого коммутатора i-го решающего блока подключен к пятому информационному входу k-го разряда пятого коммутатора (i+1)-го решающего блока, в блоке управления выход генератора тактовых. импульсов соединен с первыми входами первого и второго элементов И, второй вход элемента

И соединен с выходом "Сортировка" первого дешифратора, входы которого подключены к входам кода операции устройства, выход первого элемента

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

1176321 управляющему входу третьего коммутатора Ь-ro решающего блока, выход первого разряда четвертого коммутатора к-го решающего блока соединен с входом установки в единичное состояние первого триггера k-ro узла анализа, выходы "Деление",и "Умножение, сортировка" первого дешифратора блока управления соединены с управляющими входами соответственно первых и вторых элементов И узлов управления записью операндов, . выход "Деление, извлечение корня" первого дешифратора блока управления соединен с первыми управляющи-.

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

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

На фиг. 1 представлена функцио.нальная схема арифметико-логическогс устройства; на фиг. 2 — схема бло- 15 ка синхронизации.

Устройство (фиг. 1) содержит и решающих блоков 1, каждый из которых имеет регистры 2, 3 и 4, сумматор 5 и коммутаторы 6, 7,и 8, и .20 логических узлов 9 управления запи-. сью операндов, содержащих элемен. ты И 10, 11 и элемент ИЛИ 12, входные шины 13, 14 и !5, управляющие шины 16-23. В каждом решающем. 25 блоке 1 имеется также и коммутаторов 24,р коммутаторов 25, и входов 26, входов 27, и выходов 28.

Выходами устройства являются шины 29-32 ° Имеется также блок 33 управления с выходами 34 и 35, и входами 36 и 37 ° Коммутаторы 6, 24 и 25 являются h -разрядными, коммутаторы 7 и 8 — одноразрядными.

Блок 33 управления (фиг. 2) со35 . держит генератор 38 тактовых импульми входами третьих коммутаторов всех решающих блоков, вторые управляющие входы которых соединены с выходом "Умножение" первого дешифратора блока управления, выход "Сорте тировка которого соединен с третьими управляющими входами третьих коммутаторов всех решающих блоков, первые и вторые управляющие входы первых коммутаторов всех решающих блоков подключены соответственно к выходам "Извлечение корня", и "Деление, умножение" первого дешифратора блока управления.

2 сов, элементы И 39, 40, элемент

ИЛИ 41, триггер 42, счетчик 43, дешифраторы 44, 45 и и узлов 46 анализа, каждый из которых содержит триггеры 47 и 48,.элементы И 49, 50 и элементы ИЛИ 51, 52 и 53.

Арифметико-логическое устройство работает следующим образом.

Перед началом работы по шине 37 поступает сигнал "Общий сброс" от

ЭВМ, сбрасывающий все тригГеры блока 33 и регистры 2, 3 и 4 блоков 1 ° .

Генератор 38 вырабатывает тактовые импульсы, которые при выполнении всех операций, кроме сортировки, поступают через элементы И40 на выход

34 блока управления, т.е. на все регистры 2, 3 и 4 блоков 1. Сигнал

"0" на выходе 23. дешифратора 45 не позволяет проходить синхроимпульсам через элемент И 39, работать счет чику 43 и дешифратору 44. Нулевой потенциал на выходе дешифратора 44 не разрешает проходить сигналу "Сброс" на выход 35 и не препятствует прохождению синхроимпульсов.через элемент

И 40. Сигнал "0" на выходе дешифратора 44 также держит закрытыми элементы И 50 через триггер 42, который установлен в "0" по Я -входу сиг-. налом с шины 37, хотя на вторых входах элементов И 50 установлены "1" по инверсным выходам триггеров 48.

Сигнал "0" на выходе элемента И 39 держит закрытыми элементы И 49 всех, узлов 46 анализа и не позволяет про1176321 ходить "1", которые могут появиться на шине 28 и через элементы 47, 48 и 50 пройти на шину 27.

При выполнении сортировки тактовые импульсы поступают через элемент И 40 на выход 34 и одновременно через элемент И 39 при сигнале

"!" на выходе 23 на вход счетчика

43 и дешифратора 44. По завершении отсчета счетчиком 43 rl тактов на выходе дешифратора 44 появляется "1"

Г которая закрывает элемент И 40 и т1рекращает дальнейшее поступление тактовых импульсов на выход 34 и.регистры 2, 3 и 4 блоков 1, сбрасывает в "0" по выходу 35 содержимое регистров 2 и регистров 4, исключая первые разряды регистров 4, установленные сигналом 23 в "1". Триггер 42 по 5входу устанавливается в "!", открывает элементы И 50, и на шине 27 появляются единичные сигналы. Единичный потенциал на выходе элемента И 39 также снимает запрет на прохождение сигналов через элементы И 49.

Если на выходе 28 какого-либо решающего блока 1 появляется сигнал

"1", то он устанавливает в "I" по

5-входу триггер 47 соответствующего узла 46. Через элемент ИЛИ 53

"1" поступает на соответствующую шину 18 данного блока 1, и срдержимое сумматора 5 этого решающего блока считывается через коммутатор 6 °

Задним фронтом этого же импульса, поступающего через элемент И 49 на С-вход триггера 48 под управлением прямого выхода триггера 47, единица с выхода триггера 47 переписывается в триггер 48 и через элемент ИЛИ 51 по Я-входу сбрасывает триггер 47. В дальнейшем триггер 47 не сможет установиться в "1", пока не будет сброшен триггер 48 при последующем поступлении сигнала "Общий сброс" по шине 37, Таким образом, в следующих тактах по шине 27 на соответствующий решающий блок 1 подается "0" с инверсного выхода триггера 48 через элемент И 50, Сигнал "0" исключает из дальнейшего просмотра слово, записанное в регистре 3, т.е. слово, которое в предыдущем такте считано как максимальное. При поиске максимума воз можно появление "1" на нескольких

t0

ЗО

35 ао

55 шинах 28 при наличии нескольких одинаковых слов, являющихся максимальными. При этом считывается и исключается из дальнейшего просмотра первое (сверху )иэ них. Для этого в блок 33 управления введена схема выборки первого ответчика, состоящая из элементов ИЛИ 52. Если на одном из триггеров 47 установлена "1", то она проходит через все элементы ИЛИ 52 и через элемент

ИЛИ 51 сбрасывает в "0" по и -входу триггеры 47 последующих (нижних) ячеек, т.е., для тех решающих блоков, кроме первого сверху, для которых значение, записанное в регистр 3, также выбрано как максимальное.

При умножении в первом такте первое множимое, поступающее по шине

14, проходит на регистр 3 через элементы И 11, ИЛИ 12, а первый множитель — по шине 15 на регистр 4, причем первый разряд регистра 4 является младшим разрядом множителя.

Содержимое регистра 3 (инверсные выходы) блока 1.1 проходит на сумматор 5, где складывается с нулевыми значениями регистра 2. Инверсные значения .2-ro разряда регистра 3 бло1 ка 1.1, 3-го разряда регистра 3 блока 1.2 и т.д. проходят через коммутатор 7 по сигналу с шины 21.

Если первый разряд множителя регистра 4 равен "1", то коммутатор 6 пропускает на регистр 2 блока 1.2 сдвинутые (+!)-е разряды сумматора 5.

Если первый разряд множителя равен

"0", то коммутатор 6 пропускает те же разряды регистра 2 блока !.1. Во втором такте в блок 1.1 поступает вторая пара операндов и в сумматоре

5 получают сумму произведения второй пары чисел. В блоке 1.2 частичную сумму произведения первой пары чисел регистра 2 складывают в сумматоре 5 с содержимым регистра 3, при этом инверсное значение 3-го разряда регистра 3 проходит через коммутатор 7, В зависимости от значения второго разряда первого множителя (регистр 4) в сумматоре 5 получают вторую частичную сумму произведения первой пары чисел (производится сложение или Г сдвиг операндов).

При и --разрядных входных операндах результат вычислений первой пары чисел получают иа выходе 29 сумматора

5 блока I,и через п тактов, а всех!!7632! последующих пар чисел — через один такт.

При делении первое делимое запиз сывают в регистр 2, а первый дели 5 тель — по шине 14 в регистр 3 через . элементы И 10, ИЛИ !2 (прямые значения ). Деление выполняют с восстановлением остатка.

В нервом такте в сумматоре 5 блока !О

1.1 вычитают из первого делимого инверсные значения первого делителя.

При этом инверсное значение 2-го разряда регистра 3 блока I.! проходит через коммутатор 7 при управлении. сигналом с шины 21. Если остаток гголожителен, разряд частного равен "I" и коммутатор 6 пропускает сдвинутые (%-1 )-е разряды сумматора 5 под уп- . равлением инверсного выхода энакового разряда сумматора 5 и сигнала с шины 19..Если остаток отрицателен, выход частного равен "0", коммутатор

6 пропускает (3c-1)-е разряды регистра 2 под управлением прямого выхода знакового разряда сумматора 5 и сигнала с шины 19.

Во втором такте первый остаток от деления первой пары чисел переписывается в регистр 2 блока 1.2 из комму-..ЗО татора 6, первый делитель переписывается в регистр 3, а первая цифра частного — в и-й (старший ) разряд регистра 4 блока 1.2 как значение инверсного выхода знакового разряда 35 сумматора 5 блока 1.1. В сумматоре

5 блока 1.2 получают второй остаток от деления первой пары чисел и вторую цифру частного. Одновремен но в регистры 2 и 3 блока 1.1 запи- 40 сывают вторую пару операндов и получают первый остаток от деления вто- . рой пары операндов и первую цифру частного.

Результат вычислений первой па- 45 ры чисел получают на выходах 3I и

32 (последний разряд ) регистра 4 блока I,п через и тактов, а результат вычислений последующих пар чисел— через каждый такт. 50

При извлечении квадратного корня в первом такте первое подкоренное выражение поступает в регистр 2 по шине 13, а затем в сумматор 5, где происходит вычитание инверсных 55 значений регистра 3 с пропуском

2-ro разряда, поступающего через коммутатор 7 при управлении сигналом с шины 20, т.е. вычитание числа

I0llll.... Если остаток сумматора

5 положителен (знак сумматора равен нулю ), информация с выходов (g-l.)-x разрядов сумматора 5 поступает на коммутатор 6 под управлением инверсного выхода знакового разряда сумматора 5 и сигнала с шины

19, т.е. со сдвигом вправо. Прн этом первое число результата равно "I" и записывается через коимутатор 8 как.,прямое значение 1-го разряда регистра 3 блока 1.1 при управляющем сигнале с шинн 20 в первый pasряд регистра 3 блока 1.2 Если остаток сумматора 5 отрицателен, происходит восстановление остатка и сдвиг его вправо аналогично операции деления за счет пропускания через коммутатор 6 содержимого регистра 2 под управлением сигнала с шины 19.

При этом число результата равно "0".

Во втором такте содержимое блока !.I переписывается в регистр 2 блока !.2, а в регистр 2 блока I.! записывается второе подкоренное выражение. В блоке 1.1 вычисляют первый частный результат второго операнда, а в блоке 1.2 вычисляют второй частный результат первого подкоренного выражения. Окончательный результат получают на выходе 30 блока 1.!! в прямом коде.

При сортировке используется алгоритм упорядочения на основе базовой операции "Поиск максимума".

Перед началом работы сбрасываются все регистры сигналом с шины 37, а в первые разряды регистров 4 всех решающих блоков I записывается

"I" сигналом с шины 23. Информационный массив поступает по шине 14, через элементы И II, ИЛИ !2 логических узлов 9 на входы регистра 3 блока I.I.

В первые n тактов производится запись массива из д слов в регистры 3 всех решающих блоков 1 путем их последовательной потактовой пере" дачи через 1с-ые прямые выходы регистров 3. Тактовые импульсы поступают по шине 34. В (0+1 )-M такте прекращается подача тактовых импульсов и по шине 27.на все решающие блоки поступает сигнал "I", В горизонтальном направлении (справа налево )комиутаторы 24 обра7 ll зуют цепь, просматривающую последовательно содержимое разрядов регистра 3 и продолжающую этот просмотр, если в данном разряде содержится "1" либо если во всех одно именных разрядах регистров 2 всех решающих блоков содержатся нули.

Эта цепь реализует функцию = „(a > vy„), где Z — сигнал на выходе -%-го раз-!

% ряда коммутатора, 24;

2 — сигнал на выходе (%+1)-го

1с

I разряда коммутатора 24; а — содержимое к-го разряда регистра 3; у — значение инверсного выхода

g-ro разряда коммутатора 24 в блоке 1. и (сигнал 26. Ъ).

Сигнал на шине.26.% вырабатывает вертикальная цепь, состоящая из ф-х; разрядов коммутаторов 25 всех .решающих блоков. Значение этого сигнала может быть равным ."1" только в том случае, если в 1с-х разрядах. регистров 3 всех решающих блоков, . подлежащих просмотру (сигнал на шине 27 равен "1" ), содержатся "О", Эта цепь реализует функцию х„. =х„,. Уа1Е1,, f где х . — сигнал на выходе 1с-го раз1

Сигнал на шине 26.% равен

t у =х„

76321 8 где х — сигнал на инверсном выходе

1с.п

1 -го разряда коммутатора

25 блока 1.п.

Наличие на выходе 28,i решающего. блока 1.1 сигнала "1" говорит о том, .что слово, содержащееся в регистре

3 этого блока, является максимальным. Это слово суммируется на сумматоре 5 с нулевым значением регистра .

10 2 и .считывается через коммутатор 6 этого же решающего блока под управ. лением сигнала с шины 18, а далее под управлением: сигнала с шины

23 через коммутаторы 6 последую15 щих решающих блоков, В следующем (и+2 )-м такте rro шине 27 на все решающие блоки поступает "1", кроме первого сверху, 20 для которого на выходе 28 в предыдущем такте установился сигнал "1", .т.е. значение регистра 3 которого было считано в предыдущем такте как максимальное. Это слово в дальнейших тактах не просматривается, поскольку по входу 27 на этот решающий блок подается "О".

Дальнейшее описание работы анаЗо логично описанию для (+1) -го такта. Для сортировки массива из .п слов требуется 2 тактов, иэ которых первые .п тактов требуются для записи массива в регистры 3, В каждом последующем такте выбирается и считывается максимальное из просматриваемых слов. Считанные в предыдущих тактах слова в последующих тактах не просматриваются..

1!76321

78.

78

1176321

Составитель Е,Иванова

Редактор И.Рыбченко Техред С.Мигунова Корректор А.Обручар

Заказ 5362/48 Тираж 710 Подписное

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

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

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