Устройство для умножения чисел в -кодах фибоначчи

09 01) СОЮЗ СОВЕТСНИХОИФВЛИППНЕСНИРЕСПУБЛИН 4 (51) 6 06 Р 7/49ОПИСАНИЕ ИЗОБРЕТЕНИЯ / Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ, кл. С 06 Р 7/38, опублик. 1977.2, Авторское свидетельство СССРУ 662941, кл. С 06 Р 7/49, 1976(54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯЧИСЕЛ В р -КОДАХ ФИБОНАЧЧИ, содержащее регистр множимого, регистр множителя, сумматор, регистр частичныхпроизведений и блок управления, входы регистров множимого и множителяявляются соответствующими входамиустройства, выход сумматора соединен с информационным входом регист-.ра частичных произведений, выход ко-торого является выходом устройстваи соединен с первым инФормационнымвходом сумматора, о т л и ч а ю щ е.е с я тем, что, с целью повышенияего быстродействия, в него введеныблоки поразрядных произведений, блоки суммирования, регистры .поразрядных произведений, образующие в/(р+1)групп (и - разрядность.множимого 1,блоки коммутации, выходы которыхподключают к второму информационномувходу сумматора, выходы блоков поразрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены кинформационным входам соответствующего блока суммирования, выход кото.,рого соединен с информационным вхо-,дом соответствующего регистра по=,разрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ИЛИ-НЕ, дешифратор, элемент И, элемент запрета и элемент ИЛИ, узел выработки управляющих сигналовсодержит генератор импульсов, два элемента запрета, .шесть элементов И, четыре элемента ИЛИ, три кольцевых сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разря.дов регистра множителя подключены к входам дешифратора узла анализа,выход .элемента ИЛИ-НЕ узла"анализа подключен к первому входу элемента И и информационному входу элемента С запрета узла анапиза, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета и с первым входом первого элемента И узла выработки управляющих сигналов, первый выход дешифратора узла анализа подключен к управляющим входам второго элемента запрета и шестого элемента И узла выработки управляющих сигналовинформационные входы которых соедине" ны с выходом первого элемента запрета узла выработки управляющих сигналов, второй и третий выходы дешифратора узла анализа соединены с вхо- . ф дами элемента ИЛИ узла анализа, выходкоторого подключен к управляющему входу ключевого элемента блока управления, информационные входы которого соединены с выходами всех разрядов, кроме старшего, кольцевого сдвигового регистра блока управления, выход стар1137459 Составитель В,Березкинедактор И,Недолуженко Техред Т,Дубинчак. Коррект лак одпис аказ Филиал ППП "Патент", г.уж ул.Проектная, 4 25/36 ВКПБ по 11303Тираж 710осударственного комитета СССРлам изобретений и открытийМосква, Ж, Раушская наб1137459 шего разряда которого соединен с вторым входом элемента И и с управляющим входом элемента запрета узла анализа, выход ключевого элемента блокауправления подключен к вторым входам блоков поразрядных произведений,.второй выход дешифратора узла анализа подключен к первому входу второго элемента И узла выработки управляющих сигналов, выход которого соединен с первым входом первого элемента ИЛИ узла выработки управляющих сигналов, второй вход которогосоединен с выходом шестого элементаИ узла выработки управляющих сигналов, третий выход деширатораузла анализа соединен с первыми входами третьегои четвертого элементовИ узла выработки управляющих сигналов, выход первого разряда первогокольцевого сдвигового регистра узлавыработки управляющих сигналов соединен с вторыми входами второго итретьего элементов И узла выработкиуправляющих сигналов, выходы второгои третьего разрядовпервого кольцевогосдвигового регистра узла выработкиуправляющих сигналов соединены суправляющими входами блоков суммирования и регистров поразрядных произведений соответственно, выходытретьего и четвертого элементов Иузла выработки управляющих сигналовсоединены с входами второго элемента ИЛИ узла выработки управляющихсигналов, выход шестого элемента Иузла выработки управляющих сигналовподключен к первому входу третьегоэлемента ИЛИ узла выработки управляющих сигналов, выход которогосоединен с управляющим входом регистра множителя, выход четвертого разряда первого кольцевого сдвигового регистра узла выработки управляющих .сигналов соединен с вторыми входами Изобретение относится к вычислительной технике, предназначено для умножения многоразрядных р-кодов Фи- боначчи и .может быть использовано в отказоустойчивых процессорах обработки данных. четвертого элемента И и третьего элемента ИЛИ узла выработки управляющих сигналов, выходы первого и второго элементов ИЛИ узла выработкиуправляющих сигналов подключены куправляющим входам кольцевого сдвигового регистра блока управления, выход первого элемента И узла выработки управляющих сигналов подключен куправляющему входу второго кольцевого сдвигового регистра узла выработки управляющих сигналов, выход первого разряда которого подключен куправляющему входу третьего кольцевого сдвигового регистра узла выработки управляющих сигналов, выходывсех разрядов которого, кроме последнего, подключены к управляющим входам соответствующих блоков коммутации, выходы второго и третьего разрядов второго кольцевого сдвигового регистра узла выработки управляющих сигналов подключены соответственно к управляющим входам сумматора и регистра частичных произведений, выход четвертого разряда второго кольцевого сдвигового регистраузла выработки управляющих сигналовподключен к первому входу пятогоэлемента И узла выработки управляющих сигналов, второй вход которогосоединен с выходом предпоследнегоразряда третьего кольцевого сдвигового регистра узла выработки управляющих сигналов, входы четвертогоэлемента ИЛИ узла выработки управляющих сигналов подключены к выходу .пятого элемента И узла выработкиуправляющих сигналов и выходу элемента И узла анализа, а выход подключен к выходу признака окончанияработы устройства, вход запуска которого соединен с входом запуска генератора импульсов узла выработкиуправляющих сигналов. 2Известно устройство для умножения, содержащее регистры множителя, множимого, частичных произведений, сумматоры,и блок управления, позволяющее умножать коды, представленные вклассичесиой двоичной системе счисления 11.3 11374Недостатком устройства является невозможность умножения кодов в избыточных 1-системах счисления, обладающих высокой ошибкообнаруживающей способностью, используемой для контроля операции умножения.Известно устройство для умножения целых чисел, содержащее регистр множителя, регистр частичных произведений, сумматор, блок управления и генератор последовательности обобщенных чисел Фибоначчи, вход которого ,является-вторым входом устройства, а выход соединен с вторым входом сумматора, выход и первый вход которого соединены соответственно с входом и выходом регистра частичных произведений, выход которого также является выходом устройства, вход регистра множителя является первым входом устройства, а выход соединен с входом блока управления, выход которого соединен с управляющими входами регистра частичных произведений, регистра множителя, сумматора и генератора последовательности обобщенных чисел Фибоначчи. В этом устройстве контроль вычислений осуществляется за счет того, что перемножаемые числа представпяются в р-кодах Фибоначчи, обладающих вьгсокой ошибкообнару 30 живающей способностью Г 2"1.Недостатком данного устройства является низкое быстродействие его работы, так как для умножения множимого на к-тый разряд множителя З 5 требуется последовательно формировать к чисел Фибоначчи, кратныхмножимомуЦелью изобретения является повышение быстродействия работы устрой О ства, заключающееся в одновременном умножении множимого на (у+) разрядов множителя в случае, если множимое и множитель представлены в р-кодах Фибоначчи. 45Поставленная цель достигается тем, что в устройство для умножения чисел в .р-кодах Фибоначчи, содержащее регистр множимого, регистр множителя, сумматор, регистр частичных 50 произведений и блок управления, входы регистров множимого и множителя являются соответствующими входами устройства, выход сумматора соединен с информационным входом регист ра частичных произведений, выход ко-, торого является выходом устройства и соединен с первым информационным 59 4входом сумматора, введены блоки поразрядных произведений, блоки суммирования, регистры поразрядных произведений, образующие и/(р+) групп (и - разрядность множимого), блоки коммутации, выходы которых подключают к второму информационному входу сумматора, выходы блоков поразрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены к информационным входам соответствующего блока суммирования, выход которого соединен с информационным входом соответствующего регистра поразрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ИЛИ-НЕ, дешифратор, элемент И, элемент запрета и элемент ,ИЛИ, узел выработки управляющих сиг-. налов содержит генератор импульсов, два элемента запрета, шесть элементов И, четыре элемента ИЛИ, три кольцевык сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разрядов регистра множителя подключены к входам дешифратора узла анализа, выход элемента ИЛИ-НЕ узла анализа, подключен к первому входу элемента И и информационному входу элемента запрета узла анализа, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета и с первым входом первого элемента,И узла выработки управляющих сигналов, первый выход дешифратора узла анализа подключен к управляющим входам второго элемента запрета и шестого элемента И узла выработки управляющих сигналов, информационные входы которых соединены с выходом первого элемента запрета узла выработки управляющих сигналов, второй и третий выходы дешифратора узла анализа соединены с входами элемента ИЛИ узла анализа, выход которого подключен к управляющему входу ключевого элемента блока управления, информационные входы которого соединены с выходами всех разрядов, кроме старшего, кольцевого сдвигового регистра блока управления, выход старшего разряда которого соединен с вторым входом элемента И и с управляющим входом элемента запре 41137459 Ч(П (Ц= 5 о та узла анализа, выход ключевогоэлемента блока управления подключен,к вторым входам блоков поразрядныхпроизведений, второй выход дешифратора узла анализа подключен к первому входу второго элемента И узлавыработки управляющих сигналов, выход которого соединен с первым входом первого элемента ИЛИ узла выработки управляющих сигналов, второй 10вход которого соединен с выходомшестого элемента И узла выработкиуправляющих сигналов, третий выходдешифратора узла анализа соединен спервыми входами третьего и четвертого элементов И узла выработки управляющих сигналов, выход первого разряда первого кольцевого сдвиговогорегистра узла выработки управляющихсигналов соединен с вторыми входамивторого и третьего элементов И узлавыработки управляющих сигналов,выходы второго и третьего разрядовпервого кольцевого сдвигового регистра узла выработки управляющих сигналов соединены суправляющими входами блоков суммирования и регистровпоразрядных произведений соответственно, выходы третьего и четвертого элементов И узла выработкиуправляющих сигналов соединены с входами второго элемента ИЛИ узла выработки управляющих сигналов, выходшестого элемента И узла выработкиуправляющих сигналов подключен к первому входу третьего элемента ИЛИ уз- Зла выработки управляющих сигналов,выход которого соединен с управляющим входом регистра множителя, выходчетвертого разряда первого кольцевого сдвигового регистра узла выра 40ботки управляющих сигналов соединен с вторыми входами четвертого элемента И и третьего элемента ИЛИ узла выработки управляющих сигналов,выходы первого и второго элементовИЛИ узла выработки управляющих сигналов подключены к управляющим входам кольцевого сдвигового регистраблока управления, выход первого элемента И узла выработки управляющихсигналов подключен к управляющемувходу второго кольцевого сдвиговогорегистра узла выработки управляющихсигналов, выход первого разряда которого подключен к управляющему входу третьего кольцевого сдвиговогорегистра узла выработки управляющих,сигналов, выходы всех разрядов которого, кроме последнего, подключены к управляющим входам соответствующих блоков коммутации, выходы второго и третьего разрядов второго кольцевого сдвигового регистра,узла выработки управляющих сигналов подключены соответственно к управляющим входам сумматора и регистра частичных произведений, выход четвертого разряда второго кольцевого сдвигового регистра узла выработки управляющих сигналов подключен к первому входу пятого элемента И узла выработки управляющих сигналов, второй вход которого соединен с выходом предпоследнего разряда третьего кольцевого сдвиГового регистра узла выработки управляющих сигнаЛов, входы четвертого элемента ИЛИ узла выработки управляющих сигналов подключены к выходу пятого элемента И .узла выработки управляющих сигналов и выходу элемента И узла анализа, а выход подключен к выхо". ду признака, окончания работы устройства, вход запуска которого соединен с входом запуска генератора импульсов узла выработки управляющих сигналов.Сутьодновременного умножения на (р+1) и разрядов множителя состоит в следующем. Множимое и множитель представляются в нормальной форме р-кодов фибоначчи, по свойству которой в соседних (р+) разрядах не может быть больше одной единицы, т.е. множимое одновременно умножается не более, чем на один значащий разряд множителя.Для умножения целых чисел, представленных р-кодами Фибоначчи, в устройстве используется следующая формула произведения одноразрядных р-кодов Фибоначчи: Ч (ЕМ) пРи у=ОЧ (Е+11-У (ИЯ (М) при р:1У (М)-Ч (ЕЯ (%-р) -Р Р Р+ 10000 2) 11 001000000110 1 0001000 где м - частное от деления 2 на 2.Общий алгоритм поразрядного умножения двух чисел, представленных в р-кодах Фибоначчи, .состоит в последовательном умножении всех значащих разрядов множимого на все значащие разряды множителя по формуле (1). Образованные при таком умножении частичные произведения последовательно складываются на сумматоре. П р и м е р. Умножить в двоичной1-системе счисления число 6=10010 ичисло 4=1010. 1) 10000 1000 = 1000100; 2)О 1. ОООООО 3) 1 0000 х 1 0 =0000;0000100 10000100.3) + 1 0 Результат: 6 х 4 = 24 = 10 00 10 00.На фиг.1 представлена схема предлагаемого устройства; на фиг.2 - схема блока управления; на фиг.3 - схема узла выработки управляющих сигналов. 8,Схема устройства для умножениячисел в р - кодах Фибоначчи содержитрегистр множимого 1, регистр 2 множителя, сумматор 3, регистр 4 частичных произведений, блок 5 управления, блоки 6 поразрядных произведений, блоки 7 суммирования, регистры 8 поразрядньгл произведений,блоки 9 коммутации, входы 1 0 - 12О устройства, выход 13 устройства.Блок 5 управления содержит вход12, выходы 14-21, кольцевой сдвиговый регистр 22, ключевой элемент 23узел 24 анализа, содержащий дешиф 15 ратор 25, элемент ИЛИ 26, элементИЛИ-НЕ 27, элемент И 28, элемент 29запрета. Блок 5 управления содержиттакже узел 30 выработки управляющих сигналов, содержащий входы 31-35выходы 36 и 37, генератор 38 импульсов, кольцевые сдвиговые регистры39-41, элементы И 42-47, элементы за,прета 48 и 49, элементы ИЛИ 50-53,Регистр множимого 1 и регистр множителя 2 предназначены для хранения1соответственно р-кодов Фибоначчи множимого и множителя.В сумматоре .3 осуществляется сложение частичных произведений по правилам "фибоначчиевой" арифметики.В регистре 4 частичных произведений хранится текущая сумма частичныхпроизведений.Блок 5 управления предназначен для35выдачи сигналов управления блоками;устройства в соответствии с алгоритмом работы устройства.В блоках 6 поразрядных произведе-ний формируются произведения соот 4 Оветствующих разрядов множителя и множимого по формуле ( .Блоки 7 суммирования осуществляют сложение поразрядных произведений соответствующей группы из (р+1)разрядов множимого на группы из (р+145разрядов множителя.Регистры 8 поразрядных произведений используются для хранения текущих сумм поразрядных произведений.Блоки 9 коммутации предназначеныдля подключения соответствующих регистров поразрядных произведений ксумматору.Входы 10 и 11 являются информационными входами устройства, вход12 - входом запуска, выход 13 является информационным выходом устройства, выход 14 - выходом признакаокончания работы устройства.9 11374 Работу устройства для умноженияр-кодов Фибоначчи опишем для случая рюПредлагаемое устройство работает следующим образом. 5В начальный момент все регистры устройства обнулены, в старших разрядах кольцевых сдвиговых регистров 22, 39, 40 и 4 находятся единицы.Множимое и множитель, представ- О ленные в 1-кодах Фибоначчи, поступают в регистры 1 и 2.По сигналу запуска на входе 12 устройства включается генератор им,пульсов 38. 15Алгоритм работы устройства опре- . деляется содержимым регистра множителя 2, анализ которого выполняется блоком 5 управления.Наличие единичного сигнала на 2 О входе 34 узла анализа 24 означает, что содержимое регистра множителя в начальный момент равно "0", и результат умножения тоже равен нулю. В этом случае на выходе 14 устройства форми-д руется признак окончания работы устройства, по которому оно завершает работу. В противном случае дальнейшая работа устройства определяется содержимым двух (в,общем случае30 (р+1 старших разрядов регистра множителя.Если содержимое старших разрядов регистра множителя равно "О" (единица на выходе 33 узла анализа 24), то в данном такте умножения формиро 35 вать частичные произведения не требуется. Поэтому в блоке управления вырабатываются сигналы сдвига "1" в кольцевом сдвиговом регистре 22 и40 и сдвига регистра множителя 2 на 2 разряда в сторону старших разрядов ( сигналы на выходах 36 и 21 блока управления).Если содержимое старших разрядов45регистра множителя равно 01 ( единица на выходе 32 узла анализа.7, тоблок управления вначале также вырабатывает на выходе 36 сигнал сдвига "1" в регистре 22 на 2 разряда, Это означает, что "1" в регистре 22 будет находиться в том же разряде, что изначащая цифра в регистре множителя, и через открытый ключевой элемент 23 единичный сигнал с выхода 15 поступит в блоки поразрядных произведений 5" 6 для формирования частичных произведений 6 для формирования частичных произведений по формуле (2), (в об 59 1 О.щем случае по формуле (1. Так как множимое представлено в нормальной форме 1-кода Фибоначчи, то ненулевое частичное произведение может сформироваться лишь в одном из двух из (р+1 соседних блоков поразрядных произведений. Поэтому выходы, двух блоков 6, а в общем случае (р+1) таких блоков, соединены с входами одно го блока 7 суммирования.По следующему сигналу на выходе 16 блока управления полученные поразрядные произведения складываются в блоках суммирования 7 с текущей суммой поразрядных произведений из регистров 8, после чего новая сумма по сигналу на выходе 17 блока управления запишется в зти же регистры.В конце такта выполняется сдвиг регистра множителя,на 2 разряда и переход к следующему такту умножения, Если содержимое двух старших разрядов регистра множителя равно 1 О. ( единица на выходе 31 узла анализа), то вначале выполняется сдвиг "1" в регистре 22 на 1 разряд, после чего образуется новая сумма,поразрядных произведений. В конце такта одно временно со сдвигом регистра множителя на 2 разряда выполняется еще один сдвиг регистра 22 на 1 разряд.,.1 В общем случае, если значащая цифра множителя находится в группе ( р+1) разрядов на к-том месте, начиная со старших разрядов, то вначале выполняется сдвиг регистра 22 на к разрядов, а в конце такта умножения - на ( р+1-к) разрядов.Умножение выполняется по перечисленным алгоритмам до тех пор, пока содержимое регистра множителя не станет равно нулю (единица на выходе 35 узла анализа). В этом случае в регистрах поразрядных произведений 8 находятся произведения множителя на соответствующие 2, а в общем случае на ( р+11 разряда множимого.Дальнейшая работа устройства заключается в последовательном сложении полученных кратных множителя на сумматоре 3.В. узле выработки управляющих сигналов 30 импульсы от генератора 38 управляют сдвигом "1" в регистре40 на 1 разряд, При нахождении "1" в первом разряде регистра 40 происходит сдвиг "1" в регистре 41 наразряд, за счет чего каждый иэ регистров7459 11 33 З поразрядных произведений 8 по сигналу на соответствующем выходе шины 18блока управления через блоки коммута-. ции 9 подключается к сумматору 3, где происходит сложение соответствующего кратного множителя с суммой частичных произведений, находящейся в. регистре 4, и запись новой суммы в тот же регистр.После того, как все кратные множителя будут суммированы и в регист 12,Множимое Содержимое Р 22 Разрядымножителя Такты умножения 01 10 00 100030010 0000000000 1 О 100000 000000 1000000 100010010 100000 100 100000100100 30003000 00 101001000 2) 01001000 + 000000000 Тф,чкТ,45 где Т - время формирования частичного произведения,к - число значащих разрядов в множителе, причем(55+5). ре частичных произведений 4 образо-,:вано полное произведение множимогона множитель, в блоке управленияна выходе 14 сформируется признакокончания работы устройства.П р и м е р. Умножить числоА=6=010010 на число В=30=100100в двоичной фибоначчиевой 1-системесчисления.30 В таблице показан процесс формирования кратных множителя. В предлагаемом устройстве общее время умножения: змн 14 орм с 1 м ф=.Т + Тгде ТФ 0 - время формирования кратных множителя; Тм - время суммирования кратных множителя;где ш - разрядность множителя. иТ щ --- е Тсмр+1 2где и - разрядность множимого55Т 2 - время сложения двух р-кодов.Таким образом, при умноженииь-разрядных р-кодов фибоначчи т14 137459 13Т И + -- -Тимн 1 1 р+ 2 ф причем 1 с 4 - -,ир+1В устройстве-прототипе время умножения Ь-разрядных р-кодов Фибоначчи ТравиоТ,г ьТз ф где Т - время формирования кратного множимого, определяемое в основном временем сложения двух предЫдущих кратных множимого.МОжнО считатьчто Т. Ф Т Ф Т так как эти времена в основйом опрецеляются временем сложения двух р-кодов Фибоначчи. Для оценки достигаемого эффекта введен коэффициентТмнТуми 1Для различных оснований р-кодов Фибоначчи этот коэффициент имеет следующие значения: К=1-2 при р=1;К=1,2-3 при,р=2;К=1,3-4 при р=3 и т.д; Предлагаемое устройство имеетменьшее время работы, чем прототип,причем достигаемый положительныйэффект увеличивается при увеличенииоснования р-системы счисления.