Устройство для умножения чисел в @ -кодах Фибоначчи Советский патент 1985 года по МПК G06F7/49 

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

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ В р-КОДАХ ФИБОНАЧЧИ, содержащее регистр множимого, регистр множителя, сумматор, регистр частичных произведений и блок управления, входы регистров множимого и множителя являются соответствующими входами устройства, выход сумматора соединен с информационным входом регист-г ра частичных произведений, выход которого является выходом устройства и соединен с первым информационным входом сумматора, о т л и ч а ю щ ье с я тем, что, с целью повышения его быстродействия, в него введены блоки поразрядных произведений, блоки суммирования, регистры поразрядных произведений, образующие п/(р-ь1) групп (п - разрядность множимого ), блоки коммутации, выходы которых подключают к второму информащюнному входу сумматора, выходы блоков по разрядных произведений каждой группы и соответствующего регистра поразрядных произведений подключены к информационным входам соответствующего блока суммирования, выход кото.рого соединен с информационным вхо- . . дом соответствующего регистра по.разрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки управляющих сигналов, узел анализа содержит элемент ШШ-НЕ, дешифратор, элемент И, элемент и элемент ШШ, узел выработки управлякщих сигналов содержит генератор импульсов, два элемента запрета, .шесть элементов И, четыре элемента ИЛИ, три кольцевых сдвиговых регистра, причем выходы разрядов регистра множителя подключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разря.дов регистра множителя подключены к входам дешифратора узла анализа, выход-элемента 1ШИ-НЕ узла анализа подключен к первому входу элемента И и информационному входу элемента запрета узла анализа, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета н с первьм входом первого элемента И узла выработки управСО ляющих сигналов, первый выход дешиф sl ратора узла анализа подключен к 4аь СП управляющим входам второго элемента запрета и шестого элемента И узла :0 выработки управляющих сигналов информационные входы которых соединены с выходом первого элемента запрета узла выработки управляющих сигнгшов, второй и третий выходы дешиф ратора узла анализа соединены с входами элемента ИШ узла анализа, выход которого подключен к управлякнцему входу ключевого элемента блока управления, информационные входы которого соединены с выходами всех разрядов, . кроме старшего, кольцевого сдвигового регистра блока управления, выход стар

, , t

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

Известно устройство для умножения, содержащее регистры множителя, множимого, частичных произведений, сумматоры,и блок управления,позволяющее умножать коды,представленные в классической двоичной системе счисления f | , Недостатком устройства является невозможность умножения кодов в избыточных 1-системах счисления, обладающих высокой ошибкообнаруживающей способностью, используемой для контроля операции умножения. Известно устройство для умножени целых чисел, содержащее регистр множителя, регистр частичных произведений, сумматор, блок управления генератор последовательности обобще ных чисел Фибоначчи, вход которого .является-вторым входом устройства, а выход соединен с вторым входом сумматора, выход и первый вход которого соединены соответственно с входом и выходом регистра частичных произведений, выход которого также является выходом устройства, вход регистра множителя является первым входом устройства, а выход соединен с входом блока управления, выход ко торого соединен с управляющими входами регистра частичных произведени регистра множителя, сумматора и reH ратора последовательности обобщенны чисел Фибоначчи, В -этом устройстве контроль вычислений осуществляется за счет того, что перемножаемые чис ла представляются в р-кодах Фибонач чи, обладающих высокой ошибкообнару живающей способностью CZl. Недостатком данного устройства является низкое быстродействие его работы, так как для умножения множимого на к-тый разряд множителя требуется последовательно формировать к чисел Фибоначчи, кратных множимому. Целью изобретения является повышение быстродействия работы устрой,ства, заключающееся в одновременном умножении множимого на (р+1) разрядов множителя в случае,, если множимое и множитель представлены в р-ко дах Фибоначчи. Поставленная цель достигается тем, что в устройство для умножения чисел в р-кодах Фибоначчи, содержащее регистр множимого, регистр множителя, сумматор, регистр частичных произведений и блок управления, вхо ды регистров множимого и множителя являются соответствующими входами устройства, выход сумматора соединен с информационным входом регистра Частичных произведений, выход ко торого является выходом устройства и соединен с первь&1 информационным входом сумматора, введены блоки поразрядных произведений, блоки суммирования, регистры поразрядных произведений, образующие п/(р+1) групп (п - разрядность множимого), блоки коммутации, выходы которых подключают к второму информационному входу сумматора, выходы блоков поразрядных произведений кажцой. группы и срответствукицего регистра поразрядиых -произведений, подключены к информационным входам соответствующего блока сумми- . рования, выход которого соединен с информационным входом соответствующего регистра поразрядных произведений, блок управления содержит узел анализа, кольцевой сдвиговый регистр, ключевой элемент и узел выработки : управляющих сигналов, узел анализа ; содержит элемент ИЛИ-НЕ, дешифратор, элемент И, элемент запрета и элемент .ИПИ, узел выработки управляющих сигналов содержит генератор импульсов, два элемента запрета, шесть элемен- : тов И, четыре элемента ИЛИ, три кольцевых сдвиговых регистра, причем вы|ХОды разрядов регистра множителя под ключены к входам элемента ИЛИ-НЕ узла анализа, выходы двух старших разрядов регистра множителя подклк)чены к, входам дешифратора узла анализа, выход элемента ИЛИ-НЕ узла анализа ; подключен к первому входу элемента R и информационному входу элемента запрета узла анализа, выход элемента запрета узла анализа соединен с управляющим входом первого элемента запрета и с первым входом первого элемента ,И узла вьфаботки управляю щих сигналов, первый выход дешифра:тора узла анализа подключен к управляющим входам второго элемента запрета и шестого элемента И узла выработки управляющих сигналов, информационные входы которых соединены с выходом первого элемента запрета узла выработки управляющих сигналов, второй и третий выходы дешифратора узла анализа соединены с входами элемента ИЛИ узла анализа, выход которого подключен к управляющему входу ключевого элемента блока управления, информационные входы которого соединены с выходами всех разрядов, кроме старшего, кольцевого сдвигового регистра блока управления, выход старшего разряда которого соединен с вторым входом элемента И и с управляющим входом элемента запрета узла анализа, выход ключевого элемента блока управления подключен к вторым входам блоков поразрядных произведений, второй выход дешифратора узла анализа подключен к пербому входу второго элемента И узла выработки управляющих сигналов, выход которого соединен с первым входом первого элемента ИЛИ узла выработки управлякяцих сигналов, второй вход которого соединен с выходом шестого элемента И узла выработки управляющих сигналов третий выход дешифратора узла анализа соединен с первыми входами третьего и четвертого элементов И узла выработки упра ляющих сигналов, выход первого разря да первого кольцевого сдвигового регистра узла выработки управляющих сигналов соединен с вторыми входами второго и третьего элементов И узла выработки управляющих сигналов, выходы второго и третьего разрядов первого кольцевого сдвигового регист ра узла выработки управляющих сигналовсоединены с управляющими входа ми блоков суммирования и регистров поразрядных произведений соответственно, выходы третьего и четвертого элементов И узла выработки управляющих сигналов соединены с вхо дами второго элемента ИЛИ узла выработки управляющих сигналов, выход шестого элемента И узла выработки управляющих сигналов подключен к первому входу третьего элемента ИЛИ узла выработки управляющих сигналов, выход которого соединен с управляющим входом регистра множителя, выход четвертого разряда первого кольцевого сдвигового регистра узла выра ботки управляющих сигналов соединен с вторыми входами четвертого эле мента И и третьего элемента ИЛИ узла выработки управляющих сигналов, выходы первого и второго элементов ШШ узла выработки управляющих сигналов подключены к управляющим входам кольцевого сдвигового регистра блока управления, выход первого элемента И узла выработки управляющих сигналов подключен к управляющему входу второго кольцевого сдвигового регистра узла выработки управляющих сигналов, выход первого разряда которого подключен к управляющему входу третьего кольцевого сдвигового регистра узла выработки управляющих сигналов, выходы всех разрядов которого, кроме последнего, подключены к управляющим входам соответствующих блоков коммутации, выходы второго и третьего разрядов второго кольцевого сдвигового регистра .узла выработки управляющих сигналов подключены соответственно к управляющим входам сумматора и регистра частичных произведений, выход четвертого разряда второго кольцевого сдвигового регистра узла выработки управляющих сигналов подключен к первому входу пятого элемента И узла выработки управляющих сигналов, второй вход которого соединен с выходом предпоследнего разряда третьего кольцевого сдвигового регистра узла выработки управляющих сигналов, входы четвертого элемента ИЛИ узла выработки управляющих сигналов подключены к выходу пятого элемента И .узла выработки управляющих сигналов и выходу элемента И узла анализа, а выход подключен к выходу признака, окончания работы устройства, вход запуска которого соединен с входом запуска генератора импульсов узла выработки управляющих сигналов. Суть одновременного умножения на (P+J) и разрядов множителя состоит в следующем. Множимое и множитель представляются в нормальной форме р-кодов Фибоначчи, по свойству которой в соседних (р+1) разрядах не может быть больше одной единицы, т.е. множимое одновременно умножается не болееj чем на один значащий разряд множителя. Для умножения целых чисел, представленных р-кодами Фибоначчи, в устройстве используется следующая формула произведения одноразрядных р-кодов Фибоначчи: i/gCe+fc) при ir {e+ki-ti(e-i)v() при V I plfN ((H))-%((P) при p/2 , где 4p(i) - вес i-го разряда р-кода Фибоначчи, k 2. В Частности, для произведение LXE) 4.(k) представляется в виде следующей суммы v()-v(efk-sJfЧ(e -k-9K... ...l Mc-1-4(() , (2) тде п - частное от деления Е на 2. Общий алгоритм поразрядного умн жения двух чисел, представленных в р-кодах Фибоначчи, состоит в последовательном умножении всех значащих разрядов множимого на все зн чащие разряды множителя по формуле (I). Образованные при таком умноже нии частичные произведения последовательно складываются на суммато ре. Приме р. Умножить в двоично 1-системе счисления число 6 10010 число .. 1)10000 1000 1000100; 2)1 О - I 000 1 000; : 3)1 0000 X 1 О 0000; 4)1 О X 1 О 10; Сложение: 1)1 О О 01 О О Го О Г) О О 1010000 1010000 10000 .1100100 10000100 10000100. +1 о 100001 10 10001000 Результат: 6 х 4 24 1000100 На фиг.1 представлена схема пре лагаемого устройства; на фиг.2 схема блока управления; на фиг.З схема узла выработки управляющих сигналов. 98. Схема устройства для умножения чисел в р-кодах Фибоначчи содержит регистр множимого I, регистр 2 множителя, сумматор 3, регистр 4 частичных произведений, блок 5 управления, блоки 6 поразрядных произведений, блоки 7 суммирования, регистры 8 поразрядных произведений, блоки 9 коммутации, входы 10 - 12 устройства, выход 13 устройства. Блок 5 управления содержит вход 12, выходы 14-21, кольцевой сдвиго- вый регистр 22, ключевой элемент 23 узел 24 анализа, содержащий дешифратор 25, элемент ИЛИ 26, элемент ИЛИ-НЕ 27, элемент И 28, элемент 29 запрета. Блок 5 управления содержит также узел 30 выработки управляющих сигналов, содержащий входы 31-35 выходы 36 и 37, генератор 38 импульсов, кольцевые сдвиговые регистры ;39-41., элементы И 42-47, элементы за,прета 48 и 49, элементы ИЛИ 50-53. Регистр множимого 1 и регистр мно.жителя 2 предназначены для хранения соответственно р-кодов Фибоначчи множимого и множителя. В сумматоре 3 осуществляется сложение частичных произведений по правилам фибоначчиевой арифметики. В регистре 4 частичных произведений хранится текущая сумма частичных произведений. Блок 5 управления предназначен для выдачи сигналов управления блоками |устройства в соответствии с алгоритмом работы устройства. В блоках 6 поразрядных произведений формируются произведения соответствующих разрядов множителя и множимого по формуле {11. Блоки 7 суммирования осуществля- ют сложение поразрядных произведений соответствуницей группы из (р+1) разрядов множимого на группы из (р+1) разрядов множителя. Регистры 8 поразрядных произведений используются дпя хранения текущих сумм поразрядных произведений. Блоки 9 коммутации предназначены для подключения соответствующих регистров поразрядных произведений к сумматору. Входы 10 и 11 являются информационными входами устройства, вход 12 - входом запуска, выход 13 является информационным выходом устройства, выход 14 - выходом признака окончания работы устройства. Работу устройства для умножения р-кодов Фибоначчи опишем для случая . Предлагаемое устройст1во работает следующим образом. В начальный момент все регистры устройства обнулены, в старших разря дах кольцевых сдвиговых регистров 22, 39, 40 и 4 находятся единицы. Множимое и множитель, представленные в 1-кодах Фибоначчи, поступаю в регистры 1 и 2. По сигналу запуска на входе 12 устройства включается генератор импульсов 38. Алгоритм работы устройства определяется содержимым регистра множителя 2, анализ которого выполняется блоком 5 управления. Наличие единичного сигнала на входе 34 узла анализа 24 означает, что содержимое регистра множителя в начальный момент равно О, и резуль тат умножения тоже равен нулю. В это случае на выходе 14 устройства форми руется признак окончания работы устройства, по которому оно завершает работу. В противном случае дальнейшая рйбота устройства определяется содержимым Двух (в,общем случае (р+)) старших разрядов регистра множителя. Если содержимое старших разрядов регистра множителя равно О (единица на выходе 33 узла анализа 24), то в данном такте умножения формировать частичные произведения не требуется. Поэтому в блоке управления вырабатываются сигналы сдвига 1 в кольцевом сдвиговом регистре 22 и и сдвига регистра множителя 2 на 2 разряда в сторону старших разрядов (сигналы на выходах 36 и 21 блока управления). Если содержимое старших разрядов регистра множителя равно 01 ( единица на выходе 32 узла анализа.), то блок управления вначале также выраб тывает на выходе 36 сигнал сдвига в регистре 22 на 2 разряда. Это озн чает, что 1 в регистре 22 будет находиться в том же разряде, что и значащая цифра в регистре множителя и через открытый ключевой элемент 2 единичный сигнал с выхода 15 поступит в блоки поразрядных произведени 6 для формирования частичных произв дений 6 для формирования частичных произведений по формуле (2), (в об5910щем случае по формуле (1)) Так как множимое представлено в нормальной форме 1-кода Фибоначчи, то ненулевое частичное произведение может сформироваться лишь в одном из двух из (р+1)) соседних блоков поразрядных произведений. Поэтому выходы , двух блоков 6, а в общем случае (р+1) таких блоков, соединены с входами одно го блока 7 суммирования. По следующему сигналу на выходе 16 блока управления полученные поразрядные произведения складываются в блоках суммирования 7 с текущей суммой поразрядных произведений из регистров 8, после чего новая сумма по сигналу на выходе 17 блока управлениЯ запишется в эти же регистры. В конце такта выполняется сдвиг регистра множителя на 2 разряда и переход к следующему такту умножения. Если содержимое двух старших разрядов регистра множителя равно 10. (единица на выходе 31 узла анализа/, то вначале выполняется сдвиг 1 в регистре 22 на 1 разряд, после чего образуется новая сумма поразрядных произведений. В конце такта одновременно со сдвигом регистра множителя на 2 разряда выполняется еще один сдвиг регистра 22 на 1 разряд.-, В общем случае, если значаща цифра множителя находится в группе (р+1) разрядов на к-том месте, начиная со старших разрядов, то вначале выполияется сдвиг регистра 22 на к разрядов, а в конце такта умножения - на (р+1-к) разрядов. Умножение выполняется по перечисленным алгоритмам до тех пор, пока содержимое регистра множителя не станет равно нулю (единица на выходе 35 узла анализа). В этом случае в регистрах поразрядных произведений 8 находятся произведения множителя на соответствующие 2, а в об|щем случае на (р+1) разряда множимого . Дальнейшая работа устройства заключается в последовательном сложении полученных кратных множителя на сумматоре 3. В узле вьфаботки управляющих сигналов 30 импульсы от генератора 38 управляют сдвигом 1 в регистре 40 на 1 разряд. При нахождении I в первом разряде регистра 40 происходит сдвиг 1 в регистре 41 на I разряд, за счет чего каждый из регистров

поразрядных произведений 8 по сигналу на соответствующем выходе шины 18 блока управления через блоки коммутат ции 9 подключается к сумматору 3, где происходит сложение соответствующего кратного множителя с суммой частичных произведений, находящейся в регистре 4j и запись новой суммы в тот же регистр.

После того, как все кратные множи теля будут суммированы ив регистТакты умно- РазрядыМножи жения множителя 01 I 00 110 100010010 о 000000000 100010010 201 . 100100 о 100010010 looiioiio , UJUJ 101001000 300-;Сложение кратных множителя: 1)000000000 + 101001000 :- 101001000 40 2)101001000 + 000000000 , 10100100045 3)101001000 + 100100 101101100SO t-LJtJJ 0010000 . ,/ 1000010000 Результат: 6 X 10 60 1000010000 (55+5),.

ре частичных произведений 4 образевано полное произведение множимого на множитель, в блоке управления на выходе 14 сформируется признак окончания работы устройства.

Пример. Умножить число на число В 10 100100 в двоичной фибоначчиевой I-системе счисления.

В таблице показан процесс формирования кратных множителя. оеСодержимое 22 I 10 100000 1000000 000000 100000 0100000 100 0001000 100000 100100 - В предлагаемом устройстве общее время умножения: где время формирования кратных множителя; Т..м время сумьшрования кратных множителя; „, „, . фррм где Т - время формирования частичного произведения, к - число значащих разрядов в множителе, причем .k i т/(р+О .- /VF / где m - разрядность множителя. т„„ -р5г 2 Д разрядность множимого i время сложения двух р-кодов. Таким образом, при умножении «-разрядных р-кодов Фибоначчи 1L . равно: ITT- -T. причем k jg -77 . p4.| В устройстве-прототипе время умножения h-разрядных р-кодов Фибоначчи ТшигР«««° VMH2 3 где Tj - время формирования кратного множимогоt определяемое в основном временем сложения двух предьздущих кратных множимого. Можно считать, что , так как эти времена в основном определяются временем сложения двух р-кодов Фибоначчи.

W 137 5 IQ .;/

Фи7.1 59 14 Для оценки достигаемого эффекта введен коэффициент р - ..т -t Для различньж оснований р-кодов Фибоначчи этот коэффициент имеет следующие значения: R 1-2при ,2-3 при ,3-4 при и Т.Д.Предлагаемое устройство имеет меньшее время работы, чем прототип, причем достигаемый положительный эффект увеличивается при увеличении основания р-системы счисления.

12 35 Л /

38

Т

h-tH

Liffi

Фиг.З

Зв