Устройство для умножения

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 833866 А 1 1)5 О 06 Р 7/52 АВТОР.С У СВИДЕТЕЛЬСТВ СУДАРСТВЕННОЕ ПАТЕНТНО ДОСТВО СССРОСПАТЕНТ СССР)(56) ЕЕЕ Тгапзестопз оп Совротегз чо. с, Ь 3, МагсЬ, 1980,Авторское свидетельство СССР М 1104509, кл. 6 06 Е 7(52, 1984.(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано в Изобретение относится к вычислительной технике и может быть, использбвано в устройствах цифровой обработки сигналов различного назначения.Целью изобретения является сокращение объема оборудования за счет уменьшения емкости блока памяти.На чертеже приведена функциональная схема устройства для умножения (цепи начальной установки регистров не показаны).Устройство содержит сумматоры 1 и 2, блок 3 памяти, селектор 4, сумматор 5, регистры 6 и 7, блоки 8 и 9 элементов "И", элемент 10 "НЕ".Входы регистров 6 и 7 являются входами устройства первого и второго операндов соответственно, выход регистра 6 соединен с входами первых слагаемых сумматоров 1 и 2 и третьими входами элементов И блока 8, прямой выход регистра 7 подключен к входу второго слагаемого сумматора 1 и вторым входам элементов И блока 9, обратный выход регистра 7 соединен с входом второго слагаемого сумматора 2, выходы, сумматоров 1 и 2 без младшего разряда через селекустройствах цифровой обработки сигналов различного назначения. Цельизобретения - сокращение объема оборудования за счет уменьшения емкости блока памяти в 2 раза. Цель достигается сокращением адресов в блоке памяти, по которым хранится заранее занесенная информация, используемая при формировании произведения двух и-разрядных чисел по методу четвертьквадратичного перемножения. 1 ил. тор 4 подключены к блоку 3 памяти, выход з младшего разряда сумматора 1 соединен со вторыми входами элементов И блоков 8 и первыми входами элементов И блока 9, выход переноса из старшего разряда сумматора 2 подключен к третьим входам элементов Ф И блока 9, а через элемент 10 НЕ к первым входам элементов И блока 8, выходы блока 3 памяти, блоков 8 и 9 элементов И соеди-нены с входами второго, третьего и первого слагаемых сумматора 5, выход которого является выходом устройства.Преимущество предлагаемого устрой- СО ства перед прототипом (2) заключается в ЯЬ том, что объем оборудования (емкость памя- фь ти) блока 3 памяти сокращается в 2 раза. Средствами для решения этой задачи являются цепи передачи информации от сумматоров 1 и 2 к блоку 3 памяти, которые выдают результат вычислений в этих сумматорах без младшего разряда. Таким образом, количество адресов блока 3 памяти, по которым хранится заведомо известная информация сокращается в два раза. Для того, чтобы не допустить погрешности в вычисле 1833866нии произведения, когда в младшем разряде результата, поученного в сумматорах 1 и2, будет единица, введены блоки 8, 9 элементов И, элемент 10 НЕ с.соответствующими связями, позволяющие произвестикоррекцию результата произведения в сумматоре 5.Входные регистры 6 и 7 операндов введены как общепринятые узлы в арифметикологических устройствах Входной регистр,позволяет выдать в сумматор 2 операнд вобратном коде ля выполнения операциивычитания.устройство для.умножения предназначено для выполнения этой операции над/двумя и-разрядными операндами, представленными целыми двоичными числами,Назначение узлов устройства для умножения.Регистры 6, 7 "для приема, хранения ивыдачи двоичных и-разрядных исходныхоперандов Х и У.Сумматор 1 - для определения суммыисходных операндов А" Х+ УСумматор 2 - для определения разницыисходных операндов В = Х+ У и преобразовании результата, полученного в обратномкоде, в прямой код в случае. ХУ,Селектор 4 - для последовательной выдачи двоичных чисел А и В без младшегоразряда т.е, А/2 и В/2, в блок 3 памяти. Чторавносильно сдвигу на 1 разряд вправо.Блок 3 памяти - для хранения и выдачичисел(А/2) и(В/2). Причем(8/2) выдаетсяв обратном коде.Сумматор 5 - для формирования окончательного результата умножения с учетоми беэ учета коррекции.Блоки 8, 9 элементов И - для выдачивеличины коррекции, равной Х и У, в сумматор 5 для формирования окончательного результата умножения в зависимости отзначения последнего разряда в сумматоре1 и переноса из старшего разряда в сумматоре 2,Элемент НЕ 10 - для инвертированиязначения переноса из старшего разряда всумматоре 2, поступающего на блок И 8,Устройство работает следующим образом,Умножение производится по методуцифрового четверть квадратного перемножения, основанному на равенстве:Х У -- (Х+ У) (Х У)-х+у (х+чЯ4 4Это выражение можно также представить в виде: Х у=(Х+У)2 (Х-У)Алгоритм функционирования устройства для умножения представлен на рис, 2,5 Операнды Х и У разрядности п, участвующие в операции умножения, поступают свходных регистров 6 и 7, соответственно, навходы сумматоров 1, 2, причем на вход сумматора 2 операнд У подается с инверсного"0 выхода входного регистра 7, На их выходахполучаются величины, равные А = Х+ У иВ - Х+ У. Селектором 4 выходы сумматоров1 и 2 поочередно подключаются к входу блока 3 памяти, причем поступают они без15 младшего разряда (т.е. сдвинуты на 1 разряд вправо), что равносильно выражениямХ+ У Х - У22, в . Сначала на вход блока 3 паХ+У20 мяти поступает целое число, на еговыходе появляется соответствующее емуХ+У 2целое число ( ) , которое поступает всумматор 5 и там хранится, Затем на вход25 блока 3 памяти поступает целое числоХ - У, на его выходе появляется соответстх - У 2вующее ему целое число ( ), которое в30 обратном коде из блока 3 памяти подаетсяна сумматор 5,. где определяется окончаХ+Уг Х - У 2тельный результат ( ) - ( ) = Х У2 2Полученное произведение поступает на35 выходной регистр 8.П р и м е. р: пусть Х и У- и - разрядныечисла, где и = 3Х 110; У=100;Х+У=1010; Х-У=010;40Х+У 101, Х-У 001,( )-11001; ( - ) = оооо 145 ( у ) ( ) = 11000,Таким образом, результат верен,Следует заметить, что в результатесдвига величины Х + У и Х - У вправо на 1Х+У Х - У50 разряд (получение и ) можетбыть потеряна единица младшего разряда(если один из входных операндов четный, адругой - нечетный),Например:Х; У = 010Х+ У = 1001 Х - У = 101х+ -1 ооя х "= 1 о 1 яА это приведет к возникновению погрешности результата умножения.Поэтому в предлагаемом устройствепредусмотрена коррекция результата вычислений. 5Величину коррекции нужно производить от соотношения значений сомножителей при условии, что один из них четный,другой нечетный,10Х У(7; - )г - ( ) + У,если хУ"У( - у - ) - ( 2 ) + Х, если ХУ,При коррекции произведения быстродействие предлагаемого устройства посравнению с прототипом не ухудшается, таккак пока производится обращение к блоку 3Х - Упамяти по адресу, на сумматоре 5Х+Угуже сложатся ( ) и величина коррекции с блоков 9, 10 элементов И (У или Х).Далее к полученной величине прибавляетсяХ - Уг 25величина ( ) и результат произведенияпоступает в выходной регистр 8,Предлагаемое устройство для умножения позволяет выполнить эту операцию соскоростью, свойственной устройствам на 30основе ПЗУ, но значительно меньшем объеме памяти. Объем памяти. сокращается засчет того, что количество адресов блока памяти, по которым находится величина( - у - ) и ( - ) причем множество знаХ+Уг Х - Уг 352Х - Угчений ( ) является подмножествоммножества значений ( ) ) уменьшаетХ+Угся. К этому приводит операция сдвига величины (Х+ У) и (Х- У) вправо на 1 разряд, чторавносильно делению на 2. Объем памяти, требуемый для хранения 45Х+Угмножества значений величин ( -- ) иХ - Уг( ) и составляет(2" х 2 п) бит.2 Выигрыш в объеме блока 3 памяти составляет по отношению к прототипу;2 п+1, 2 и 2 п+1- 2 (раз)и2 п 2 пФормула изобретения Устройство для умножения, содержащее первый и второй входные регистры, первый и второй сумматоры, селектор и блок памяти, вход которого соединен с выходом селектора, первый и второй входы которого соединены соответственно с выходами разрядов суммы, кроме выходов младшего разряда, первого и второго сумматоров, входы первых слагаемых которых соединены с выходом первого входного регистра, вход которого соединен с входом первого операнда устройства, вход второго операнда которого соединен с входом второго входного регистра, прямой выход которого соединен с входом второго слагаемого первого сумматора, о т л и ч а ющ е е с я тем, что, с целью сокращения объема оборудования за счет уменьшения емкости блока памяти, в него введены третий сумматор, два блока элементов И и элемент НЕ, выход которого соединен с первыми входами элементов И первого блока, вторые входы которых соединены с выходом младшего разряда первого сумматора и первыми входами элементов И второго блока, вторые входы которых соединены с входами второго слагаемого первого сумматора и прямым выходом второго входного регистра, инверсный выход которого соединен с входом второго слагаемого второго сумматора, выход переноса которого соединен с входом элемента НЕ и третьими входами элементов И второго блока, выходы которых соединены с входом первого слагаемого третьего сумматора, входы второго и третьего слагаемых которого соединены со.ответственно с выходом блока памяти и выходами элементов И первого блока, третьи входы которых соединены с входами первых слагаемых первого и вторс:о сумматоров и выходом первого. входного регистра, выход третьего сумматора соединен с выходом результата устройства.1833866 Х дакт каз 2686 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 зводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарин Составитель А,Рома Техред М.Моргентал в Корректор О.Густи