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

(56) Авторское свидеФ 798825, кл. С 06 РАвторское свидете9 993252, кл. С 06 Р У 32и Р.М.Фернеза Ленина полиим. Ленинского тельство СС 7/38, 1977 льство СССР 7/38, 1981 СУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬ 1 ТИ(54)(57) АРИФМЕТИКО-ЛОГИЧЕСКОЕ УСТРОЙСТВО, содержащее и последовательно соединенных решающих блоков,где П - разрядность операндов, каж-.дый из которых включает три регистра, сумматор, три коммутатора и и .узлов управления записью операндов,которые включают элемент ИЛИ и дваэлемента И, выходы которых соединены с входами элемента ИЛИ, причемпервая группа информационных входовустройства соединена с входами первого регистра первого решающегоблока, вторая группа информационныхвходов устройства подключена к первым входам элементов И узла управления записью операнда. соответствующего разряда, выходы элементов ИЛИузлов управления записью операндовсоединены с соответствующими входами второго. регистра первого решающего блока, третья группа информационных входов устройства соединенас входами третьего регистра первогорешающего блока, выходы разрядов первого регистра 1 с-го решающего блока,где 1 с=1,2п, соединены с пер 901176321 А вой группой входов сумматора, прямые выходы разрядов второго регистрад-го решающего блока, где 1=1,2(и), соединены с входами второгорегистра (1+1)-го разрешающего блока,инверсный ипрямой выходы (д 1)-горазряда второго регистра 1,-го решающего блока соединены с информационными входами первого коммутатора,выход первого коммутатора соединенс вторым входом (+1)-го разрядасумматора 1-го решающего блока, прямые выходы Е-х разрядов третьегорегистра 1-го решающего блока соединены с входами Ь)-х разрядов третьего регистра (1+1)-го решающегоблока, выход второго коммутатора1-го решающего блока соединен с входом -го разряда второго регистра(1.+1)-го решающего блока, первый ивторой информационные входы второгокоммутатора К-го Решающего блокасоединены соответственно с прямымвыходом к-го разряда второго регистра и с инверсным выходом знакового разряда сумматора К-го решающего блока, в каждом решающем блоке информационные входы с первогопо четвертый К-го разряда третьегокоммутатора соединены соответственно с выходом (1 с)-го разряда первого регистра, выходом (1+1)-го разряда первого регистра., выходом(К+1)-го разряда сумматора, управляющие входы третьего коммутаторасоединены соответственно с прямыми инверсным выходами знакового разряда сумматора и первого разряда третьего регистра, выход К-го разряда третьего коммутатора -го решающего блока соединен с входом К-горазряда первого регистра (+1)-горешающего блока, инверсный выходзнакового разряда д-го решающегоблока соединен с входом п-го разряда третьего регистра (х+)-го решающего блока, в К-м решающем блокеинверсные выходы всех разрядов второго регистра, кроме (К+1)-го, соединены с второй группой входов сумматора, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей за счет выполнения операции сортировки, в неговведен блок управления, включающийгенератор тактовых импульсов, элементы И, ИЛИ, триггер, счетчик,дешифраторы и и узлов анализа, каждый из которых содержит триггеры,элементы ИЛИ, И, в каждый решающийблок введены четвертый и пятый коммутаторы, причем в каждом решающемблоке инверсные выходы второго регистра соединены с соответствующими информационными входами первойгруппы четвертого коммутатора, информационные входы второй группы которого подключены к инверсным выходампятого коммутатора и-го решающегоблока, первый и второй управляющиевходы -го разряда четвертого коммутатора подключены к выходу (+1)-горазряда четвертого коммутатора и кпервому управляющему входу -го разряда пятого коммутатора, первыйинформационный вход К-го разряда пятого коммутатора подключен к инверсному выходу К-го разряда второго регистра, вторые управляющие и информационный входы К-го разряда пятогокоммутатора (+1)-го решающего блокаобъединены и соединены с прямым выходом 1-го разряда пятого коммутатора 1-го решающего блока, в первомрешающем блоке вторые информационныеи управляющие входы пятого коммутатора объединены и соединены с шинойнучевого потенциала устройства,подключенной также к пятому информационному входу К-разряда пятогокоммутатора, выход К-го разрядапятого коммутатора -го решающегоблока подключен к пятому информационному входу К-го разряда пятого коммутатора (х+1)-го решающего блока,в блоке управления выход генератора тактовых. импульсов соединен с первыми входами первого и второгоэлементов И, второй вход элементаИ соединен с выходом "Сортировка"первого дешифратора, входы которо"го подключены к входам кода операцииустройства, выход первого элементаИ подключен к счетному входу счетчика, выходы разрядов которого соединены с соответствующими входами вто"рого дешифратора, выход которогоподключен к первым входам установки в нулевое состояние первого и тре-.тьего регистров всех решающих блоков,информационному входу триггера,первому входу элемента ИЛИ и второмувходу второго элемента И, выход которого подключен к входам разрешения записи регистров всех решающихблоков, вход общего сброса устройства соединен с входом установки внулевое состояние счетчика и вторымвходом элемента ИЛИ, первыми входами первых элементов ИЛИ всех узлованализа и вторыми входами установкив нулевое состояние регистров всехрешающих блоков, выход элемента ИЛИблока управления подключен к входу .установки в нулевое состояние триггера, выход которого соединен с первыми входами первых элементов И узлов анализа, выходы которых соединены с объединенными управляющимивходами и разрядов четвертых коммутаторов и к первому управляющемувходу и-го разряда пятого коммутатора соответствующего решающего блока, в каждом узле анализа выход первого элемента ИЛИ соединен с входомустановки в нулевое состояние первого триггера, выход которого соединен с первыми входами второго и третьего элементов ИЛИ и второго элемента И и единичным входом второготриггера, инверсный выход которогосоединен с вторым входом первого элемента И, а прямой выход - с вторымвходом первого элемента ИЛИ, выходвторого элемента ИЛИ р-го узла анализа соединен. с третьим входом первогоэлемента ИЛИ и вторым входом второго элемента ИЛИ (1+11-го узла анализа, в первом узле анализа третийвход первого элемента ИЛИ и второйвход третьего элемента ИЛИ объединены и подключены к шине нулевогопотенциала устройства, выход третьего элемента ИЛИ 1-го узла анализа подключен к дополнительному1176321 управляющему входу третьего коммутатора Ь-го решающего блока, выходпервого разряда четвертого коммутатора к-го решающего блока соединенс входом установки в единичное состояние первого триггера 1-го узлаанализа, выходы "Деление" ,и "Умножение, сортировка" первого дешифратора блока управления соединены суправляющими входами соответственно первых и вторых элементов И узлов управления записью операндов,выход "Деление, извлечение корня"первого дешифратора блока управления соединен с первыми управляющи-. 1Изобретение относится к вычислительной технике и может быть использовано для выполнения операцийсложения, вычитания, умножения, деления, извлечения корня при обработке больших массивов многоразрядныхчисел, а также для выполнения операции сортировки,Целью изобретения является расширение функциональных возможностей Оустройства за счет выполнения операции сортировки.На Фиг. 1 представлена Функциональная схема арифметико-логическогсустройства; на фиг. 2 - схема блока синхронизации.Устройство фиг. 1) содержит ирешающих блоков 1, каждый из которых имеет регистры 2, 3 и 4, сумматор 5 и коммутаторы б, 7,и 8, и .20логических узлов 9 управления запи-.сью операндов, содержащих элементы И 10, 11 и элемент ИЛИ 12,входные шины 13, 14 и 5, управляющие шины 16-23, В каждом решающем. 25блоке 1 имеется также и коммутаторов 24,1 коммутаторов 25, и входов 26,входов 27, и выходов 28,Выходами устройства являются шины 29-32Имеется также блок 33 30управления с выходами 34 и 35, ивходами 36 и 37. Коммутаторы 6,24 и 25 являются й -разрядными,коммутаторы 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. Сигнал "О" на выходе дешифратора 44 также держит закрытыми элементы И 50 через триггер 42, который установлен в "0" по Я -входу сиг-, налом с шины 37, хотя на вторых входах элементов И 50 установлены "1" по инверсным выходам триггеров 48, Сигнал "0" на выходе элемента И 39 держит закрытыми элементы И 49 всех, узлов 46 анализа и не позволяет про 11763215 0 15 20 25 ЗО 35 40 45 50 55 ходить "1", которые могут появиться на шине 28 и через элементы 47, 48 и 50 пройти на шину 27.При выполнении сортировки тактовые импульсы поступают через элемент И 40 на выход 34 и одновременно через элемент И 39 при сигнале "1" на выходе 23 на вход счетчика 43 и дешифратора 44. По завершении отсчета счетчиком 43 и тактов на выходе дешифратора 44 появляется "1"Г которая закрывает элемент И 40 и т 1 рекращает дальнейшее поступление тактовых импульсов на выход 34 и.регистры 2, 3 и 4 блоков 1, сбрасывает й "О" по выходу 35 содержимое регистров 2 и регистров 4, исключая первые разряды регистров 4, установленные сигналом 23 в "1". Триггер 42 по 5- входу устанавливается в , открывает элементы И 50, и на шине 27 появляются единичные сигналы. Единичный потенциал на выходе элемента И 39 также снимает запрет на прохождение сигналов через элементы И 49.Если на выходе 28 какого-либо решающего блока 1 появляется сигналто он устанавливает в "1" по 5-входу триггер 47 соответствующего узла 46, Через элемент ИЛИ 53 "1" поступает на соответствующую шину 18 данного блока 1, и срдержимое сумматора 5 этого решающего блока считывается через коммутатор б.Задним фронтом этого же импульса, поступающего через элемент И 49 на С-вход триггера 48 под управлением прямого выхода триггера 47, единица с выхода триггера 47 переписывается в триггер 48 и через элемент ИЛИ 51 по й-входу сбрасывает триггер 47. В дальнейшем триггер 47 не сможет установиться в "1", пока не будет сброшен триггер 48 при последующем поступлении сигнала "Общий сброс" по шине 37, Таким образом, в следующих тактах по шине 27 на соответствующий решающий блок 1 подается "0" с инверсного выхода триггера 48 через элемент И 50, Сигнал "0" исключает из дальнейшего просмотра слово, записанное в регистре 3, т.е. слово, которое в предыдущем такте считано как максимальное. При поиске максимума воз можно появление "1" на нескольких шинах 28 при наличии нескольких одинаковых слов, являющихся максимальными. При этом считывается и исключается из дальнейшего просмотра первое (сверху )иэ них. Для этого в блок 33 управления введена схема выборки первого ответчика, состоящая из элементов ИЛИ 52, Если на одном из триггеров 47 установлена "1", то она проходит через все элементы ИЛИ 52 и через элемент ИЛИ 51 сбрасывает в "0" по й -входу триггеры 47 последующих (нижних) ячеек, т.е для тех решающих блоков, кроме первого сверху, для которых значение, записанное в регистр 3, также выбрано как максимальное,При умножении в первом такте первое множимое, поступающее по шине 14, проходит на регистр 3 через элементы И 11, ИЛИ 12, а первый множитель - по шине 15 на регистр 4, причем первый разряд регистра 4 является младшим разрядом множителя. Содержимое регистра 3 (инверсные выходы) блока 1,1 проходит на сумматор 5, где складывается с нулевыми значениями регистра 2. Инверсные значения,2-го разряда регистра 3 блока 1.1, 3-го разряда регистра 3 блока 1.2 и т,д. проходят через коммутатор 7 по сигналу с шины 21. Если первый разряд множителя регист" ра 4 равен "1", то коммутатор 6 пропускает на.регистр 2 блока 1,2 сдвинутые (к+)-е разряды сумматора 5. Если первый разряд множителя равен "О", то коммутатор 6 пропускает те же разряды регистра 2 блока 1.1. Во втором такте в блок 1,1 поступает вторая пара операндов и в сумматоре 5 получают сумму произведения второй пары чисел. В блоке 1,2 частичную сумму произведения первой пары чисел регистра 2 складывают в сумматоре 5 с содержимым регистра 3, при этом инверсное значение 3-го разряда регистра 3 проходит через коммутатор 7, В зависимости от значения второго разряда первого множителя (регистр 4) в сумматоре 5 получают вторую частичную сумму произведения первой пары чисел (производится сложение или Г сдвиг операндов).При и -разрядных входных операндах результат вычислений первой пары чисел получают иа выходе 29 сумматора 5 блока 1,и через и тактов, а всехпоследующих пар чисел - через одинтакт.При делении первое делимое запизсывают в регистр 2, а первый дели 5тель - по шине 14 в регистр 3 через .элементы И 1 О, ИЛИ 2 (прямые значения ). Деление выполняют с восстановлением остатка,В нервом такте в сумматоре 5 блока О1.1 вычитают. из первого делимого инверсные значения первого делителя.При этом инверсное значение 2-го разряда регистра 3 блока 1. проходитчерез коммутатор 7 при управлении.сигналом с шины 21. Если остаток положителен, разряд частного равен "1"и коммутатор б пропускает сдвинутые(%-1 )-е разряды сумматора 5 под уп- .равлением инверсного выхода знакового разряда сумматора 5 и сигнала сшины 19,.Если остаток отрицателен,выход частного равен "0", коммутатор6 пропускает (-1)-е разряды регистра 2 под управлением прямого выходазнакового разряда сумматора 5 и сигнала с шины 19.Во втором такте первый остаток отделения первой пары чисел переписывается в регистр 2 блока 1,2 из комму-ЗОтатора б, первый делитель переписывается в регистр 3, а первая цифра частного - в и-й (старшийразряд регистра 4 блока 1,2 как значение инверсного выхода знакового разряда 35сумматора 5 блока 1.1. В сумматоре5 блока 1,2 получают второй остатокот деления первой пары чисел ивторую цифру частного. Одновременно в регистры 2 к 3 блока 1.1 запи- Юсывают вторую пару операндов и получают первый остаток от деления второй пары операндов и первую цифручастного.Результат вычислений первой пары чисел получают на выходах 31 и32 (последний разряд ) регистра 4 блока 1,и через и тактов, а результатвычислений последующих пар чисел -через каждый такт, 50При извлечении квадратного корняв первом такте первое подкоренноевыражение поступает в регистр 2по шине 13, а затем в сумматор 5,где происходит вычитание инверсных 55значений регистра 3 с пропуском2-го разряда, поступающего черезкоммутатор 7 при управлении сигналом с шины 20, т.е. вычитание числа10111 Если остаток сумматора5 положителен (знак сумматора ра"вен нулю ), информация с выходов(-Ц-х разрядов сумматора 5 поступает на коммутатор 6 под управлениеминверсного выхода знакового разряда сумматора 5 и сигнала с шины19, т.е. со сдвигом вправо. Прн этомпервое число результата равно "1"и записывается через коимутатор 8как.,прямое значение 1-го разрядарегистра 3 блока 1,1 при управляющемсигнале с шинн 20 в первый разряд регистра 3 блока 1.2 Если остаток сумматора 5 отрицателен, происходит восстановление остатка и сдвигего вправо аналогично операции деления за счет пропускания через коммутатор 6 содержимого регистра 2под управлением сигнала с шины 19.При этом число результата равно "0",Во втором такте содержимое блока1.1 переписывается в регистр 2 блока 1,2, а в регисТр 2 блока 1.1 записывается второе подкоренное выражение. В блоке 1.1 вычисляют первыйчастный результат второго операнда,а в блоке 1.2 вычисляют второй частный результат первого подкоренноговыражения. Окончательный результатполучают на выходе 30 блока 1. впрямом коде.При сортировке используется алгоритм упорядочения на основе базовой операции "Поиск максимума".Перед началом работы сбрасываютсявсе регистры сигналом с шины 37,а в первые разряды регистров 4всех решающих блоков 1 записывается"1" сигналом с шины 23, Информационный массив поступает по шине 14,через элементы И 11, ИЛИ 12 логических узлов 9 на входы регистра 3блока 1,1,В первые в тактов производитсязапись массива из д слов в регистры 3 всех решающих блоков 1 путемих последовательной потактовой пере"дачи через %-ые прямые выходы регистров 3. Тактовые импульсы поступают по шине 34, В (0+1 -и тактепрекращается подача тактовых импульсов и по шине 27.на все решающиеблоки поступает сигнал "1".В горизонтальном направлении(справа налево )комиутаторы 24 обра 7 11 зуют цепь, просматривающую последовательно содержимое разрядов регистра 3 и продолжающую этот просмотр, если в данном разряде содержится "1" либо если во всех одно именных разрядах регистров 2 всех решающих блоков содержатся нули. Эта цепь реализует ФункциюЕ 1 =Е, (а.1, чу 1,)где Е - сигнал на выходе %-го раз%ряда коммутатора, 24;Е - сигнал на выходе (+-го1 сразряда коммутатора 24;аК - содержимое Й-го разрядарегистра 3;у,1 - значение инверсного выхода-го разряда коммутатора 24в блоке 1, и (сигнал 26, Ъ),Сигнал на шине.26.В вырабатывает вертикальная цепь, состоящая из;-х; разрядов коммутаторов 25 всех решающих блоков, Значение этого сигнала может бь 1 ть равным ."1" только в том случае, если в 1 с-х разрядах.1 егистров 3 всех решающих блоков, . подлежащих просмотру 1,сигнал на шине 27 равен "1" ), содержатся "О", Эта цепь реализует Функциюх, =х,. уа 1 Е 1где х, - сигнал на выходе Ь-го раз 1 с 1ряда коммутатора 25 решающего блоках - сигнал на выходе А-го разЬ ряда коммутатора 25 решающего блока 1.(1 -1 ),Сигнал на шине 26.% равену =х 76321 8где х - сигнал на инверсном выходес.лВ-го разряда коммутатора25 блока 1,й,Наличие на выходе 28,1 решающего.блока 1.1 сигнала "1" говорит о том,.что слово, содержащееся в регистре3 этого блока, является максимальным. Это слово суммируется на сумматоре 5 с нулевым значением регистра .10 2 и .считывается через коммутатор бэтого же решающего блока под управ, лением сигнала с шины 18, а далеепод управлением: сигнала с шины23 через коммутаторы Б последую 15 щих решающих блоков,В следующем (ь+2)-м такте пошине 27 на все решающие блоки поступает "1", кроме первого сверху,20 для которого на выходе 28 в предыдущем такте установился сигнал "1",.т,е. значение регистра 3 которогобыло считано в предыдущем такте какмаксимальное. Это слово в дальней 25 ших тактах не просматривается, поскольку по входу 27 на этот решающий блок подается "Оц,ЬДальнейшее описание работы ана- ЗО логично описанию для (о+1) -готакта. Для сортировки массива из .пслов требуется 2 о тактов, иэ которых первые и тактов требуются длязаписи массива в регистры 3, В каждом последующем такте выбираетсяи считывается максимальное из просматриваемых слов. Считанные в предыдущих тактах слова в.последующихтактах не просматриваются,"Патент", г, Ужгород, ул, Проектная,Филиал Тираж 710Государственногделам изобретениосква, Ж, Рауш Подписно омитета СССР открытий ая наб д, 4/5