Устройство для вычисления суммпРОизВЕдЕНий упОРядОчЕННыХ МАССиВОВчиСЕл Советский патент 1981 года по МПК G06F7/52 

Изобретение относится к вычислительной технике и может быть примен но в специализированных устройствах ориентированных на решение систем алгебраических, дифференциальных и интегральных уравнений,, вычисление корреляционных функций, коэффициенто Фурье, цифровую фильтрацию сигналов обработку экспериментальных данных и т. п. Под упорядоченным массивом здесь понимается массив, в котором числа расположены в порядке возрастания ил убывания их величины. Упорядоченные массивы довольно часто встречаются на практике, например массивы, полученные в результате квантования и дискретизации по времени процессов разгона двигателей, нагрева слитков в нагревательных колодцах, кривых расхода энергии и материалов, пройде ного пути и т. п. Неупорядоченные массивы могут быть упорядочены с помощью специальных программ или устройств. В данном случае упорядоченным является один из массивов чисел а во втором массиве числа расположены в соответствии с номерами, под которыми расположены соответствуищие им пары в первом массиве. Известны устройства для вычисления суммы произведений двух массивов чисел, содержакше блок памяти для хранен 1я массивов чисел и процессор для перемножения сомножителей и вычисления их суммы Ij . Недостатком таких устройств является их низкое быстродействие, обусловленное тем, что процессор в соответствии с программой последователь- но во времени формирует адреса первого и второго сомножителей, выбирает по ним сомножители из блока памяти, осуществляет их йеремножение, выбирает текущее значение сумкоы, добавляет его к полученному произведению и отсылает в рабочую ячейку памяти, после чего сравнивает текущие адреса чисел массива с концом массива и лереходит на начало программы. Известны устройств для вычисления .суммы произведений двух массивов чисел, содержащие два блока памяти для хранения массивов чисел,-, множительное устройство и накапливающий сумматор 2j . Недостатком устройства является его низкое быстродействие, обусловленное тем,.что для вычисления произведения N пар чисел массивов требуется выполнить N п сложений и N л сдвигов в множительном устройстве (где п - разрядность чисел массивов) .

Цель изобретения - повышение быстродействия устройства за счет сокращения количества операций для вычисления суьФ1ы парных произведений.

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

На чертеже схематически представлено устройство.

Устройство содержит первый 1 и второй 2 запоминающие блоки, счетчик 3 адреса, первый 4 и второй 5регистры числа, схему 6 сравнения, счетчик . 7. сумматор-вычитатель 8, rpynrty элементов И 9, накапливающий сумматор 10, блок 11 управления. Первые 12 и вторые 1.3 входы устройства соединены с входами первого 1 и второго 2 запоминающих блоков, адресные входы которых соединены с выходами счетчика 3 адреса. Выходы первого 1 и второго 2 запоминающих блоков соединены с входами регистров 4 и 5 числа. Выходы первого регистра числа соединены с первыми входами схемы 6 сравнения, втоЕ«де входы которой соединены с выходами счетчика 7. Выходь второго . регистра 5 числа соединена с входами вычитания сумматора-вычитателя 8, входы сложения которого соединены с входами второго запоминающего блока 2, а выходы через группу элементов И 9 ссЬвдйнены с входами накапливающего сумматора 10, выходы которого соединены с выходами 14 устройства. Вход блока 11 управления соединен с выходом cxeNM б сравнения, первый выход ее соединен с входом счетчика 3 адреса, второй выход соединен со счетным входом счетчика 7 и управляющим входом группы элементов И 9, а третий выход соединен с управляющим входом .сумматора-вычитателя 8.

Предлагаемое устройство работает следующим образом.

Под управлением первого выхода блока 11 управления счетчик 3 адреса последовательно формирует адреса ячеек первого 1 и второго 2 запоминающих блоков, в соответствии с котпрыми по входам 12 и 13 производится запись чисел первого и второго массива в запоминающие блоки 1 и 2 соответственно. Оба массива упорядочены по числам первого массива, т.е. числа а; в первом массиве расположены в порядке возрастания их величины, а во втором массиве числа зайисаны в соответствии, с номерами, под которыми расположены соответствующие им пары в первом. Наряду с записью чисел во второй запоминающий бдаок 2 производится их суммирование на сум-, маторе-вычитателе 8, на входы сложения которого под управлением .сигналов по третьему выходу схемы 11 управления поступают числа второго массива.

После запи(и чисел обоих массивов в запоминающие блоки 1 и 2 и вычис- ления суммы чисел второго массива, которая остается в сумматоре-вычитателе В, схема 11.управления по первому выходу управляет счетчиком 3 адреса , который формирует адрес первой ячейки. В соответствии с первым адресом из первого 1 и второго 2 запоминающих блока на регистры 4 и 5 числа считывается пара чисел а и , причем число а является наименьшим числом в первом массиве (вследствие его упорядоченности). После чего блок 11 управления по второму выходу производит выдачу тактовых импульсов, которые открывают группу элементов И 9 и осуществляют передачу содержимого ( -S b ) сумматора-вычитателя 8

5 в накапливающий сумматор 10. Счетчик 7 производит подсчет количества поступивших на него импульсов до момента равенства кода в счетчике 7 и содержимого регистра 4 числа, который

0 определяется -схемЬй б сравнения. При этом схема 6 сравнения выдает сигнал на блок 11 управления, в соответствии с которжам блок 11 управления прекращает вьвдачу тактовых импульсов на второй выход, а по третьему выходу управляет сумматором-вычитателем 8, который вычитает из своего содержимого число b , записанное на втором регистре 5 числа. Затем под управлением по первому выходу схегвл 11 управления.счетчиком 3 адреса формируется адрес второй ячейки запоминающих блоков 1 и 2, из которых считывается их содержимое на регистры 4 и 5 числа. Число ag. считанное с второй ячейки первого запоминающего блока 1, равно или больше числа, считанного ранее (ввиду упорядоченности первого массива). Если числа равны, то происходит повторное срабатывание

cxevsa 6 сравнения, которая через блок 11 управления, производит вычитание из содержимого сумматора-вычитателя второго.числа bg, находящегося на регистре 5 числа. Если считанное второе число из первого массива больше предыдущего числа, то сравнение его с кодом в счетчике 7 (в котором хранится .фактически предыдущее число) не происходит и блок 11 управления производит выдачу тактовых импульсов по второму выходу, которые открывают группу элементов И 9 и осущестапяют передачу нового содержимого ( jZ: Ь сумматора-вычитателя 8 в накепливапщий сумматор 10. Счетчик 7 производи добавление поступающих на его вход тактовых импульсов к ранее .зафиксир ванному: в. нем коду, т. е. .первому числу первого массива. В момен ра венства кода в счетчике 7с содержи мым первого регистра 4 срабатывает схема б сравнения, которая через бло 11 управления производит вычитание числа b2 во втором регистре 5 числа из содержимого сумматора-вычитателя 8. Аналогично осуществляется обработ ка и всех остальных чисел массивов Сравнение последнего (максимального числа в первом массиве с кодом в счетчике 7 приводит к вычитаншо последнего числа второго массива из со держимого сумматора-вычитателя 8, в результате чего он обнуляется, а в накапливанячем сумматоре 10 к этому моменту накапливается сумма произведений двух массивов чисел. Время вычисления суммы произведений двух масйиврр чисел в предлагаемом устройстве слабо зависит от количества чисел массива и в большей степени зависит .от разрядностичисел массива. Формула, изобретения Устройство для вычисления сумм произведений упорядоченных массивов чисел, содержащее первый и второй .запоминающие блоки, информационные входы которых соединены с соответствующими входами устройства, первый и второй регистры числа, входы которых соединены с выходами соответственно первого и второго запоминаи.щих блоков, счетчик адреса, выходы которого соединены с адресньми входами первого и второго запоминающих .блоков, группу элементов И, накапливающий сумматор и блок управления, первый выход KOTOPOI4J соединен с входом счетчика адреса, второй - с управляющими входами элементов И группы, выходы которых соединены . с входами накапливающего сумматора, выходы которого являются выходами устройства, о т л и ч а,ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены схема сравнения, счетчик и сумматорвшчитатель, входы сложения которого ;сйедине$ш с входами второго запоминающего блока, входы вычитания - с выходами второго регистра числа, а выходы - с информационными входами группы элементов И, первые и вторые входы cxevsa сравнения соединены с внходами первого регистра числа и счетчика соответственно, а выход бе подключен к входу блока управления, третий выход которого подключен к управляющему входу сумматора-зычитатёля, счетный вход счетчика подключен к управляю1чим входам группы элементов И. ilcTO4HHkH информации, принятые во внимание при экспертизе 1.Каган Б. Н. и Каневский М. М. Цифровые вычислительные машины и системы, М. , Энергия, 1973, с. . 2.Семотюк М. В. и Боюн В. П. Операционные устройства для суммирования парных произведений и перемножения комплексных чисел. - Управляющие система и машины, 1978, 3, с. 8792, рис. 1 (прототип). .