250543

ОПИСАНЙЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ боюз Советских Социалистических Республик/52 присо тнением заявки1 ПК 6 061 оритет Комитет ло делам зобретеиий и открыти ори Совете Министров СССРвано 12,И 11.1969. Бюллетеньбликования описания 16.11.1970 УДК 681,325.5 088.8) ол,и ата опу второбретения ЙЛТЕ 11 ТНОТЕХНИЧЕК,"ЫАЧ БИБЛИОТЕЕд А. Ф, Хведелидзе ститут кибернетики АН Грузинской Саявител ЖИТЕЛЬНОЕ УСТРОЙСТВО В КОДЕ ГРЕЯ ластИз Грея логи гист 1 с едлагаемое устройство относится к оби цифровой вычислительной техники,вестны множительные устройства в коде, содержащие регистры исходных чиселческие схемы определения четности и рер результата,Предлагаемое устроиство отличается от известных тем, что оно содержит регистры сдвига четных и нечетных единиц множимото, первый и второй регистры частичных произведений и первую и вторую группы схем И, счетный вход каждого триггера частичных произведений через линию задержки соединен с,выходом каждой схемы И и соответствующей группы данного результата, единичный вход каждого триггера регистра частичного произведения соединен с выходом схемы И, первый выход которой подсоединен к единичному выходу триггера соседнего младшего разряда, другой - к выходу каждой схемы И той же группы данного разряда, нулевой вход каждого триггера регистров частичных произведений соединен с выходом схемы И фиксации единицы в разрядах регистра, один из входов схемы И данного разряда линии сквозного просмотра каждого регистра частичных произведений подключен к выходу схемы И, первый вход которой подключен к единичному выходу триггера соседнего старщего разряда другого регистра, а второй - к выходу логической схемы сквозного просмотра предыдущего разряда другого регистра, один из входов схемы И,данного раз ряда линии сквозного просмотра результатасоединен с выходом схемы И логической схемы сквозного, просмотра соседнего младшего разряда и через линию задержки - с выходом каждой схемы И, первый вход кото рой подключен к единичному выходу триггера данного разряда регистра частичных произведений, второй - к выходу логической схемы сквозного просмотра предыдущего разряда другого регистра, счетный вход триггера 5 данного разряда регистра результата связанс выходом каждой схемы И логической схемы сквозного просмотра каждого регистра частичных произведений, подключенной к еди.ничному выходу триггера данного разряда о регистра, и с выходом, схемы И, первыйвход которой соединен с единичным выходом триггера регистра результата, а второй - с выходом предыдущего разряда логической схемы сквозного просмотра регистра резуль тата,Предлагаемое множительное устр обеспечивает высокое быстродействие.На чертеже представлена блок-схем сываемого устройства.В основу предлагаемого множительного устройства положен следующий способ умножения в коде Грея. Числа просматриваются от старших разрядов к младшим и определяются четности разрядов сомножителей. Четность младшего разряда множимого фиксируется в разряде четности числа (нулевой разряд): в разряд четности записывается единица, если младший разряд имеет индекс нечетный, и нуль, если младший разряд имеет индекс четный, В разряде четности множителя записывается инверсия значения четности младшего разряда (нулевой разряд множителя всегда имеет индекс нечетный). После этого, множимое вместе с разрядом четности последовательно сдвигается в сторону старших разрядов, и отдельно определяются суммы положительных и отрицательных частичных произведений (нечетные и четные единицы множим ого, включая нулевой разряд, соответственно) по правилу; если очередной разряд множителя (включая, нулевой разряд) имеет индекс нечетный, то позиция частичного произведения определяется позицией,множииого на данином шаге операции, если очередной разряд множителя имеет индекс четный, то позиция частичного произведения определяется позицией множимого на предшествующем шаге операции. Если очередной разряд множителя имеет индекс нечетный, то разряд с записью единица положителыного частичного произведения сохраняет свое значение, если в соседнем младшем разряде отрицательного частичного произведения записан нуль, или нуль записан в соответственном разряде регистра отрицательных частичных произведений или в соседнем младшем разряде. Разряд с записью единица отрицательного частичного произведения сохраняет свое значение, если соседний младший разряд положительного частичного произведения содержит нуль или если нуль записан в соответственном разряде регистра положительных частичных произведений или в соседнем младшем разряде. После этого каждая единица положительного частичного произведения по модулю 2 прибавляется к соответственному разряду суммы положительных частичных произведений и, если в нем в результате предыдущей операции записана единица, в соседнем старшем разряде устанавливается запись единица, если в нем записан нуль. Одновременно каждая единица отрицательного частичного произведения по модулю 2 прибавляется к соответственному разряду суммы отрицательных частичных произведений и, если в нем в результате предыдущей операции записана единица, на единицу устанавливается соседний старший разряд, если в нем записан нуль.Суммы, положительных и отрицательных частичных произведений каждый раз нормализуются таким образом, что инвертпруетсяСомножители и суммы частичных произведений 45 Разряды и их четности 11109 87 б 5 43210+0 00 0500 00 00 00 0 0100 0 множитель (55)нечетные единицы мно.жимогочетные единицы множимогоположительное частичноепроизведение (1) положительное частичноепроизведение (2) сумма положительныхчастичных произведений (1)отрицательное частичноепроизведениеотрицательное частичноепроизведение (2) сумма отрицательныхчастичных произведений (1) О 00 00 О 00 0101 0 00 00 0 1000 1 0 00 00 1 0001 0 100 1 1 0 00 00 00001 01 0 00 00 00101 0 0 00 00 0011 11 65 запись в одноименных равных единице разрядах,Результат устанавливается чередующимсяпоразрядным просмотром сумм частичных5 произведений в сторону младших разрядов,начиная 1 с суммы положительных частичныхпроизведений, При этом, если при просмотреодной суммы встречается разряд с записьюединица, то единица записывается в соот 10 ветственный разряд результата, и, начиная ссоседнего младшего разряда, просматривается вторая сумма частичных произведений.Если при просмотре одной суммы частичных произведений разряду с записью нуль15 соответствует разряд с единицей в другой,то инверсия записывается в данном разрядерезультата и в разряде, соседнем слева с ближайшим старшим разрядом с записью единица при просмотре промежуточного резуль 20 тата справа налево от данного разряда.Если чередующийся поразрядный просмотрзаканчивается на просмотре суммы отрицательных частичных произведений и в нулевомразряде соммы отрицательных частичных25 произведений записана единица, то происходит,инверсия в младшем разряде результата.Если чередующийся поразрядный просмотрзаканчивается на просмотре суммы положительных частичных произведений и в нулевомЗО разряде отрицательных частичных произведений записана единица или если чередующийся поразрядный просмотр заканчивается напросмотре суммы отрицательных частичныхпроизведений и в нулевом разряде отрицатель.З 5 ных частичных произведений записан нуль, тозаписывается инвераия в разряде, соседнемслева с ближайшим разрядом, равном единице, при просмотре результата в сторонустарших разрядов.40 Сформулированное правило умноженияиллюстрируется в таблице,ТаблицаУмножение чисел в коде Грея250543 Продолжение Продолжение Сомножители ц суммычастичных произведений Сомножителя п суммычастичных произведений Разряды и цх четности Разряды ц цх четности 0 11 0 1 10001 0 11 1 1 формирование результат 101 0 О 00110 оноцчательцыц результат 595) 0 00 01 110000 0 00 1 0 0 01000 000111 1000 0 00 00 0 01010 1 0 00 00 1 10 000 000 000 111101 30 35 0 00 11 1 00000 0 00 О 0 01000 0 01 01О 000 0 00 ОООО 01101 40 45 0 00 0 000 10100 0 00 0 00 1 О 101 отрицательное частичное произведецие (5)сумма отрицательных частичных произведений (4) О010000000 00 О О 000 101 нормализованная суммаположительных частич.ных произведений (5) нормализованная суммаотрицательных частичных произведений (5) 65 0 00 00 1 0000 00 01 000 100000 01 101000 00 00 00 010010 00 000 0101000 00 00 0 О 1101 001 0110000 0 0 10 0 О О 0000 0 1 0 00 0000 0 00 0 00100 О 0 00 0 00100000 0 00 0 010 00 01 нормализованная сумма положительных частичных произведений (1)положительное частичное произведение (3)сумма положительных частичных произведе. ций (2)нормализованная сумма отрицательных частич. ных произведениц (1)отрицательное частичное произведение (3)сумма отрицательных частичных произведений (2) нормализованная сумма положительных частичных произведений (2)положительное частичное произведение (4)сумма положительных частичных произведений (3)нормализованная сумма отрицательных частичных произведений (2)отрицательное частиччое произведение (4)сумма отрицательных частичных произведений (3) нормализованная сумма положительных частичных произведенийположительное частичное произведение (5)сумма положительных частичных процзведенцй (4)нормализованная сумма отрицательных частич. ных произведений (3) нормализованная суммаположительных частичных произведений (4) положительное частичноепроизведение (6) сумма положительныхчастичных процзведе.пий (5)нормализованная суммаотрицательных частичных произведений (4) отрицательное частичноепроизведение (6) сумма отрицательныхчастичных произведе.ний (5) 10 15 20 25 50 55 60(+ обозначает признак нечетный,-- признак четный).Устройство выполнено для умножения двух разрядных чисел (число разрядов может быть любым) и включает регистр множимого, содержащий триггеры ( - 2, линию определения частностей из групп схем И 3 и 4, рсгистр множителя, содержащий триггеры 5 и б и линию определения четностей из группы схем 7 и 8, регистр сдвига, нечетных единиц множимого на триггерах 9 - 12, схемах И 13 и линиях задержки 14, регистр сдвига четных единиц множимого на триггерах 15 - 18 (триггер 15 - триггер четности множимого) и линиях задержки 19 и 20, тригггрные регистры на триггерах 21 - 24 и 25 - 28 сумм положительных и отрицательных частичных произведенни соответственно, регистр результата, содержащий триггеры 29 - 32.Две группы вентилей 33 и 34 подключены к единичным выходам триггеров множимого и выходам линии определения четностей данного разряда. Вентили ЗЗ и 34 осуществляют прохождение сигналов от четных и нечетных единиц множимого ко входам уставовки единицы триггеров регистров сдвига четных и нечетных единиц соответственно при поступлении импульса на вход 1, Триггер 15 четности множимого устанавливается на единицу продифференцированным сигналом с выхода линии определения четности, фиксирующей признак нечет. Схемы И 3 и 4 каждой линии определения четности - потенциального типа.На выходе триггеров регистра множителя включены вентили 35 и Зб, образующие вместе с ячейками задержки 37 схему развертки или просмотра индексов четностей от младших разрядов к старшим. Сигналы в схему развертки поступают со входа О. Сигнал со входа 11 или от сборок, объединяющих выходы ячеек задержки 37 поразрядной выборки, через ячейку задержки 38 поступает к нулевым входам триггеров регистров сдвига, Время задержки на ячейке задержки 38 определяется временем прохождения сигнала через один из вентилей 35 и Зб поразрядной выборки, вентиль 39 и 40 триггера 41 четности и группу вентилей 42 - 44, 45 - 48, 49 - 52 или 53 - 54.Схемы И 13 управляют прохождением импульсов в соседний старший разряд при установке на нуль триггеров 9 - 12 и 15 - 18 регистров сдвига, Линии задеркки 14 обеспечивают поступление импульсов на единичные входы триггеров только после окончания в них переходных процессов, 250543Триггер 41 фиксирует четность просматриваемых разрядов множигеля, На нулевой вход триггера 41 пройдя линию задержки 19 приходят сигналы от сборок, объединяющих выходы вентилей 35, на единичный вход триггера 41 пройдя линию задержки 20 приходят сигналы от сборок, объединяющих, выходы вентилей 36. Единице, записанной в триггер 41, соответствует признак нечетный, нулю - признак четный.Линии задержки 19 и 20 обеспечивают изменение состояния триггера 41, управляющего прохождением сигналов через вентили 39 и 40,Вентиль,39 подключен к единичному выходу триггера 41 и осуществляет прохождение импульса, фиксирующего разряд множителя с индексом анечетный, к группе вентилей 42 - 48. Вентиль 40 подключен к нулевому выходу триггера 41 и управляет прохождением импульса, фиксирующего разряд множителя с индексом четный, к группе вентилей 49 - 54,Вентили 43, 45, 47, 48 и 51, 53, 54 определяют значения положительных частичных произведений.Вентили 43 и 48 подключены к единичным выходам триггеров 9 и 12 соответственных разрядов (младшего и старшего) регистра сдвига нечетных единиц множимого. Один вход вентилей 45 и 47 подключен к единичному выходу триггера соответственного разряда регистра сдвига нечетных единиц множимого (триггеров 10 и 11), другой к нулевому выходу триггера соседнего младшего разряда регистра сдвига честных единиц множимого (триггеров 16 и 17), а также к нулевым выходам триггеров соответственного и соседнего младшего разряда регистра суммы отрицательных частичных произведений (триггеров 28, 27 и 27, 26),Вентили 43, 45, 47 и 48 фиксируют значение положительного частичного произведения, определяемого позицией множнмого на данном шаге операции, т. е. управляют прохождением импульса на вход логической схемы (я:ейки 55 и 56) соответственного разряда регистра суммы положительных частичных произведений,Вентили 51, 53 и 54 подключены к единичным выходам триггеров 10 - 12 соответственно и фиксируют значение положительного частичного произведения, определяемого позицией множпмого на предшествующем шаге операции, т, е. управляют прохождение импульса на вход логической схемы (ячейки 55 и 56) - соседнего младшего разряда регистра суммы положительных частичных произведений.Вентили 42, 44, 46 и 49, 50, 52 определяют значения отрицательных частичных произведений.Вентиль 42 подключен к единичному выходу триггера 16 регистра сдвига четных единиц мне пх:го. Один вход вентилей 44 и 4660 б 5 нал на вход цепи сквозного просмотра регистра положительных частичных произведений поступает с выхода схемы развертки через ячейку 67 задержки,Группа вентилей 68 - 71 и 72 - 75 управляегся сднни:.ными выходами триггеров реподключен к единичному выходу триггера соответственного разряда регистра сдвига четныхединиц множимого (триггеров 7 п 18), другой - к нулевому выходу триггера сосед него младшего разряда регистра сдвига нечетных единиц множимого (грпггеров 9 и 10), а также к нулевым выходам триггеров соответственного и соседнего старшего разряда регистра суммы положительных частичных 10 произведений (триггеров 23, 22 и 22, 21),Вентили 42, 44 и 46 фиксируют значениеотрицательного частичного произведения, определяемого позицией множимого на данном шаге операции, т. е. управляют прохож дением импульса па вход логической схемы(ячейки 55 и 56) соответственного разряда регистра суммы отрицательных частичных произведений.Вентили 49, 50, 52 подключены к единичным 20 выходам триггеров 16 - 18 соответственно ификсируют значение отрицательного частичного произведения, определяемого позицией множнмого на предшествующем шаге операции, т. е, управляют прохождением импульса на 25 вход логической семы (ячейки 55 и 56) соседнего младшего разряда регистра суммы отрицательных частичных произведений.Ячейки 55 подключены к единичным выходам триггеров регистров сумм частичных 30 произведений и осуществляют прохождениеимпульсов ко входу установки единицы триггера соседнего старшего разряда.Ячейки 56 задерхкки обеспечивают появление сигнала на счетном входе триггера дан ного разряда регистра суммы частичныхпроизведений сразу же после прохождения импульса через ячейки 55 в соседний старший разряд.Схемы 57 совпадения, управляемые единпч ными выходами триггеров регистров суммчастичных произведений, осуществляют прохождение импульса установки нуля к одпоименным триггерам регистров при нормализации сумм частичных произведений. Им пульс нормализации поступает ко входу схем57 с выходов вентилей поразрядной выборки через ячейку 58 задержки.Время задержки на ячейке 58 определяетсявременем формирования очередной суммы 50 частичных произведений, т. е. временем прохождения импульса с выхода вентилей поразрядной выборки на счетный вход триггера регистра суммы частичных произведений и временем переключения триггера.55 Схемы совпадения (вентили) 59 - 62 и 63 -бб, подключенные к нулевым выходам триггеров регистров сумм частичных произведений, последовательно соединены между собой и образуют цепь сквозного просмотра. СигПр имер.в +А=О 1 0 1=3в + вВ=О 1 1 1=2 010 010 100 0001 0001 0010 гистров сумм частичных произведений и осуществляет пересылку импульса просмотра из одной цепи сквозного просмотра в другую.Схемы совпадения (вентили) 7 б - 78 и 79 - 81, подключенные к единичным выходам триггеров регистров частичных произведений, фиксируют соответственный нулевому разряду просматриваемой суммы разряд с единицей в другой.Выходы вентилей б 9 - 71, 72 - 74, 7 б и 77, 79 - 81 подключены к счетному входу триггера данного разряда регистра результата. Выход вентиля 75 подключен ко счетному входу триггера младшего разряда результата. Сигналы с выхода вентилей бб, 7 б, 77, 78, 80 и 8 поступают через одну пз задержек группы ячеек 82 и 83 в цепь из вентилей 84 - 85 скоз. ного просмотра результата. Время задержки ячеек 82 и 83 - 1 залере;ки Р 1 перекь трегераОперация начинается с подачи высокого потенциала на входы П 1 - КРаботу устройства можно проследить на следующем примере,первое положительное частичноепр оизведениевторое положительное частичноепроизведениепервая сумма положительныхчастичных произведенийпервое отрицательное частичноепроизведениевторое отрицательное частичноепроизведениепервая сумма отрицательныхчастичных произведений 1 0 0 окончательное значение суммыположительных частичных произведений 0 0 1 0 окончательное значение суммыотрицательных частичных произве- дений М=1 1 0 1 окончательный результат (б). Операция начинается с подачи высокого потенциала на входы 1, П 1 и Ю, после чего начинают работу линии определения четностей разрядов сомножителей.Продифференцированный на дифференцирующей цепочке Д сигнал на выходе схемы И 4 младшего разряда регистра множимого поступает на счетный вход триггера 15 регистра сдвига четных единиц множимого и на счетный вход триггера 25 регистра отрицательных частичных произведений, перебрасывая каждый из этих; риггеров из состояния 0 в состояние 1,10 15 20 25 30 35 40 А,5 50 55 60 65 Одновременно с этим на вход 1 подается командный импульс, фиксирующий запись в регистрах сдвига множимого. В результате триггер 10 регистра сдвига нечетных единиц мпожимого перебрасывается в состояние 1.К этому моменту на вход П схемы просмотра четностей разрядов множителя подается импульс, который проходит ко входам вентилей 42 - 48, на линии ячеек задержки 37 и 38, проходит вентиль 35, фиксирующий признак четный младшего разряда, и далее к нулевому входу триггера 41, оставляя без изменения исходное состояние триггера четности.Наличие высокого потенциала с единичного выхода триггера 10 и высокого потенциала с нулевого выхода триггера 9 обеспечивает прохождение сигнала через вентиль 45 (остальные вентили 42 - 48 заперты). Импульс с выхода вентиля 45 через ячейку 5 б (ячейки 55 заперты) поступает на счетный вход триггЕра 22, устанавливая в,нем запись единицы. Получаем первое положительное частичное произведение - 0010 и первое отрицательное частичное произведение - 000(1),Далее импульс проходит ячейку задержки 38 и поступает на входы установки в нуль триггеров регистров сдвига. При этом продифференцированный сигнал с нулевого выхода триггера 10 устанавливает в единицу триггер 11; продифференцированный сигнал с нулевого выхода триггера 15 устанавливают в нуль триггер 1 б (схемы И 13 отперты высоким потенциалом на входе Р).Импульс с выхода ячейки задеркки 37 (время задержки равно времени формирования частичных произведений с момента поступления сигнала на вход П) проходит вентиль 40 и далее вентили 49 и 53, фиксируя второе отрицательное частичное произведение - 000(1). С выходов вентилей 49 и 53 сигналы поступают ко входам ячеек 55, управляемых единичными выходами триггеров 22 и 25, Так как в триггерах 22 и 25 записаны единицы, то сигналы проходят через ячейки 55 и поступают к единичным входам триггеров 23 и 2 б, устанавливая единицу. Поступающие затем на счетный вход триггеров 22 и 25 сигналы от ячеек 5 б задержки устанавливают исходное состояние 0.К этому моменту импульс с выхода ячейки задержки 37 проходит ячейку 58 задержки и поступает ко входам схем совпадения 57 нормализации частичных произведений. На выходе этих схем сигналов нет (так как нет одноименных равных единице разрядов). Получаем окончательное значение сумм частичных произведений 0100 - для положительных частичных произведений, 001 (0) - для отрицательных частичных произведений.Так как к моменту просмотра индекса четности разряда, предшествующего самому старшему разряду множителя, со входа убирается высокий потенциал, то схемы И 3 заперты, и импульс с выхода ячейки задерж 250543ыи 37, пройдя ячейку задержки 38, стирает запись в регистрах сдвига единиц множимого,Сигнал с выхода схемы развертки проходит ячейку б 7 задержки к моменту окончания формирования сумм частичных произведений и поступает,на схему сквозного просмотра регистра положительных частичных произведений. При этом вентиль 59 отперт высоким потенциалом с нулевого выхода триггера 24. Сигнал с выхода вентиля 59 поступает к вентилю б 9 (вентиль бО заперт, и дальнейшее распространение импульса в цепи сквозного просмотра положительных частичных произведений прекращается), проходит его и поступает на счетный вход триггера Л регистра результата, устанавливая в нем единицу, С выхода вентиля б 9 импуль" пересылается в цепь сквозного просмотра отрицательных частичных произведений.Вентиль 74 оказывается отперт (в триггере 2 б записана единица), и импульс поступает на счетный вход триггера 29, пе 1 ребрасывая его в состояние 1.Так как вентиль 78 заперт, то дальнейшее распространение импульса прекращается. Окончательная запись в регистре результата - 0101 (6), что соответствует истине.Предмет изобретенияМножительное устройство в коде Грея, содержащее регистры исходных чисел, логические схемы определения четности и регистр результата, отличаоисееся тем, что, с целью повышения быстродействия, оно содержит регистры сдвига четных и нечетных единиц множимого, первый и второй регистры частичных произведений и первую и вторую группы схем Исчетный вход каждого триггера частичных произведений через линию задерж 12ки соединен с выходом каждой схемы И и соответствующей пруппы данного разряда, едвничный вход каждого триггера регистра частичного произведения соединен с выходом 5 схемы И, первый,выход которой подсоединен к единичному выходу триггера соседнего младшего разряда, другой - к выходу каждой схемы И той же группы данного разряда, нулевой вход каждого триггера репи.10 стран частичных произведений соединен с вы.ходом схемы И фиисации единицы в разрядах регистра, один из входов схемы И данного разряда линии сквозного просмотра каждого регистра частичных произведений 15 подключен к выходу схемы И, первый входкоторой подключен к единичному входу триггера соседнего старшего разряда другого регистра, а второй - к выходу логической схемы сквозното просмотра предыдущего разря да другого рвтистраодин из входов схемыИ данного разряда линии сквозного просмотра результата соединен с выходом схемы И логической схемы сквозного просмотра соседнего младшего разряда и через линию 25 задержии - с выходом каждой схемы И,первый вход которой подключен к единичному выходу триггера данного разряда регистра частичных произведений, второй - к выходу логической схемы сквозного просмотра преды дущего разряда другого регистра, счетныйвход триггера даннопо разряда регистра результата связан с выходом каждой схемы И логической схемы сквозного просмотра каждого регистра частичных произведений, подЗ 5 ключенной к единичному выходу триггера данного разряда репистра, и с выходом схемы И, первый вход которой соединен с единичным выходом триггера регостра результата, а второй - с выходом предыдущего разряда 40 логической схемы сквозного просмотра регистра результата.Составитель В. А. БогатыревРедактор Е. В. Семанова Техред Т. П. Курилко Корректоры: Е. Ласточкинаи А. Абрамова Типография, пр. Сапунов аказ 3637/12ЦНИИПИ Комитета по делаьМоскв Тираж 480зобретений и открытий пр Ж, Раушская иаб., д. Подписноеовете Министров СССР