Устройство для умножения комплексных чисел в модулярной системе счисления

(21) (22) (46) (71) тут им. А (72) (53) (56) й инств- облем ЛЕК СЧИ (5,7 тел а ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ 3938741/24-2401.08.8530.12.86. Бюл. М 48Научно-исследовательски прикладных физических пр .М.СенченкоА.А.Коляда681,325 (088.8)Авторское свидетельство СССР 7860,.кл. С 06 Р /72, 1980. вторское сивдетельство СССР 15382, кл. С 06 Р 7/72, 1981. УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ КОМПНЫХ ЧИСЕЛ В МОДУЛЯРНОЙ СИСТЕМЕ ЛЕНИЯИзобретение относится к вычисли ной технике и может быть испольно в быстродействующих процессобыстрого преобразования Фурье для умножения комплексных чисел наповорачивающие множители. Цель изобретения - повышение быстродействияустройства. Поставленная цель достигается тем, что устройство, содержащее первый входной регистр, первыйблок вычисления интегрального индекса, группу модульных сумматоров,вспомогательный регистр, группу вспомогательных регистров, группу блоковсуммирования вычетов и группу блоковделения на константу, содержит б,окформирования дополчительного кода помодулю, первый и второй блоки мультиплексоров, второй входной регистр,группу блоков памяти, второй блок вы- учисления интервального индекса и элемент задержки с соответствующими связями, 3 ил.=-1 щ при а=1к шк 55 при =1 ск Изобретение относится к вычислительной технике и может быть использовано в быстродействующих процессорах быстрого преобразования Фурье для умножения комплексных чисел на поворачивающие множители.Целью изобретения является повышение Ьыстродействия.На Фиг.1 и 2 приведена схема устройства для умножения комплексных 10 чисел в мсдулярной системе счисления; на Фиг.3 - схема блока вычисления интервального индекса.Устройство для умножения комплексных чисел в модулярной системе счиспения (Фиг.1) содержит тактовый входустройства, первую группу информационных входов 2.1 2 К устройства, вторую группу информационных входов 3.1-3.К устройства (К - количество 20 основных модулей системы счисления), вход 4 номера константы устройства, блок 5 Формирования дополнительного кода по модулям, первый блок 6 мультиплексоров, первый и второй входные ,регистры 7 и 8, второй блок 9 мультиплексоров, группу блоков 10. 1, 10,2, , 10.К памяти первый и второй блоки 11 и 12 вычисления интервального индекса, элемент 13 задержки, группу блоков 14.1, 14.2 14 К+1 суммирования вычетов, группу модульных сумматоров 15.1, 15.215 К+1, вспомогательный регистр 16, группу вспомогательных регистров 17.1, 17.2 35 17.К+1, группу блоков 18.1, 18.2 18.К деления на константу и группу выходов 19.1, 19,219.К устройства.Блоки 11 и 12 вычисления интервального индекса (Фиг,3) имеют конвей ерную структуру и содержат элементы 20 памяти, регистры 21 и сумматоры 22 (для К=7).Отдельный блок вычисления интервального индекса по входному модулярному коду (д,Ы ) некоторого числа А из диапазона Э=-рЫрМ -1 модулярной системы счисленияк-осуществляют Формирование за Т тактов вычета 1(А)=/1(А)/ к интервального 50индекса числа А, определяемого соотношениямик1(А)-Е - .К, Ы ф)гдехнаименьший неотрицательный вычет по некоторому моцулю ш;Фиксированное натурапьноечисло такое, что ш 2 р+,:1Остатки Ми сявляются соответственно младшими и старшими разрядами входа элемента 20, памяти, по которому записывается вычет 18 ++ Н р 1 Ц=12 3 Г ) - целая часть).В ячейку блока 10.1 памяти записывйется набор констант, компоненты которого опрецеляются выражениями:ЦУ-тки если У,р,Х.,У и 1 - значения разрядов, начиная с младшего адресного входа блока 10памяти;И и И - целые числа из диапазонаЭ модулярной системысчисления, определяющиесоответственно действительную и мнимую части1-.ой из используемых вустройстве комплексныхконстант.Элемент 13 задержки представляетТсобой цепь из-регистров. Информа 2ционный вход первого регистра является входом элемента задержки, выходы первого и последнего регистров являются соответственно первым и вторым выходами элемента 13 задержки, управляющие входы всех регистров цепи объединены и подключены к тактовому входу элемента 13 задержки, Управляющий вход элемента 13 задержки и селекторныс входы блоков групп мультиплексоров 6 и 9 объединены и подключены к управляющему входу 1 устройства, 128062 эБлок 14.1 суммирования вычетов (.=1,2К+1) выполняет сложение по модулю ш; наборов из Квычетов за Т тактов. Структурно блоки суммирования вычетов аналогичны блокам 11 и 12 вычисления интервального индекса.Блок 18.1 деления на константу реализован на постоянном запоминающем устройстве, в ячейку которого записывается вычет 10 1 к2 Ч к+в.: +1 1=1 Кэзгде 1. и 1 - значения младших и1 КФ 1старших Разрядов адресного входа постоянного запоминающегоустройства,Алгоритм умножения комплексных чисел, реализуемый предлагаемым устройством, базируется на следующем,Пусть требуется перемножить комплексное число А=А +1 А на комплексную И . Мконстанту М= --- -+1 --- , имеющую но к. р к номер 10,1,1 -1Действительная и мнимая части исГ , Ц/ комого произведения В=Б + 1 В могут быть вычислены по следующим приближен ным формулам:30,1(А Ъ 7 -А У )шк+1(А+А " )к+ 35Устройство для умножения комплексных чисел в модулярной системе счисления работает следующим образом. По сигналу Г=1, подаваемому в каждом четном такте работы устройства с входа 1 на селекторные входы первого и второго блоков 6 и 9 мультиплексоров и управляющий вход элемента 13 задержки, модулярный код (с,Ы ) действительной части комплексного чис. ла А с входа 2.1, 2,22.К через информационные входы второй группы блока 6 поступает в первый входной регистр 7, модулярный код (о5 ОЦ,Ы ) мнимой части числа с входов 3.1, к3.2З,К через вторую группу инфор-мационных входов блока 9 групп мультиплексоров поступает во второй входной регистр 8, а в элемент 13 задержки через вход 4 устройства передается номер 1 комплексной константы, после этого начинается первый такт операции умножения комплексных чисел. На первом такте цифра с с 1-говыхода регистра 7 подается на 1-йинформационный вход первой группыблока 9, 1-й вход блока 11 вычисленияинтервального индекса, а также намладшие разряды адресного входа блока10.1 (1 Ф 1) памяти; цифра,(" с -говыхода регистра 8 подается на 1-евходы блока 5 формирования дополнительного кода, блока 12 вычисленияинтервального индекса, а также наследующие разряды адресного входаблока 10.1 (111) памяти, а номер 1константы с первого выхода элемента13 задержки поступает на старшие разряды адресного входа блоков памяти10.1, 10.210.К. В блоке 5 осуществляется формирование дополнительного кода ( - сФ.,1-Ы 1который с выхода блока 5 через первую группу информационных входов блока б групп мультиплексоров (ввидуГ=О) поступает во входной регистр 7;в регистре 8 посредством блока 9 мультиплексоров формируется модулярныйкод (Ы К). Из блока 10 памяти3считывается набор констант Я,. Ы;,Ы;,1), 1-я компонента которого с 1-говыхода блока 10.1 памяти передаетсяв д-й входной регистр блока 14,1суммирования вычетов, а блоки 11 и12 начнут вычисление по модулю г интервальных индексов. По истеченииТ-го такта на выходах блоков 11 и 12сформируются соответственно вычеты1(А ) и 1(А ), которые на (Т+1) - мтакте подаются на младшие разрядыадресного входа блока 10.К памяти.Б то же время на старшие разряды адресного входа блока 1 О.К памяти свторого выхода элемента 13 задержкиподается номер 1 константы, В результате из блока 1 О.К памяти считываетсянабор констант Я (1(А ), 1(А ), 1),который запоминается во вспомогательном регистре 16. Параллельно с этимв ходе тактов с второго по (Т+1)-йблок 14.3, суммируя по модулю наборвходных вычетов, находит величинуС =На Т-м такыре величины ". и 0"с выхода блока 14, и -го выходавспомогательного регистра 16 подают-,ся соответственно на первый и второйвходы модульного сумматора 15.1, который получает 1-ю цифру1280 б 25 5 Ю 20 льтиплексорав соединен"с входом вто 35 соответственно с входами первого ивторого блоков вычисления интервального индекса, вход номера константыустройства соединен с информационнымвходом элемента задержки, первый вы О хад которого соединен со старшими. разрядами адресного входа 1-га блокапамяти группы, выходы первого, второго блока вычисления интервальногоиндекса и второй выход элсмента заустройство для умножения комплексных чисел в мадулярной системе счисления содержащее первый входной регистр, первый блок вычисления интервального индекса,группу модульных сум- маторов, вспомогательный регистр, группу вспомогательных регистров, группу блоков суммирования вычетов и группу блоков деления на константу, причем вход х-го вспомогательного регистра группы соединен с вьгходом соответствующего модульного сумматора группы (г=1-К+1, К - количествоосновных .модулей системы счисления), выходы вспомогательных регистров группы кроме (К+1)-га, соединены с младшими разрядами входа соответствующих блоков деления на константу группы, старшие разряды входа которых соединены с выходом (К)-го вспомогательного регистра группы, о т л и ч а " ю щ е е с я тем, что, с целью повышения быстродействия оно содержит блок Формирования дополнительного модулярного кода интервального индекса 1(А И +А И ) числа; при этомзапоминается во вспомогательном регистре 17.На (Т+3)-м такте вычеты 1, и 1,с выходов вспомогательных регистров17. и 17 поступают соответственкно на Младшие и старшие разряды входаблока 18, деления, который определяет -ю цифру модулярного кода мнимойчасти искомого произведения, при этомИмадулярный кад мнимой части (8,) снимается с выходов 19.1, 19,2,19.К устройства,В ходе тактов с второго по (Т+4)-йописанные действия выполняются для1модулярных кОдОВ ( 0 1 , й, О 1. )и (с,с), сформированных на первом такте соответственно в регистрах7 и 8. В результате по окончании (Т++4)-го такта блоки 18.1, 18.218,К деления получат модулярный код(, ) действительной части исккомаго произведениЛ, который снимается с вьглодов 19.1, 19,2 19.Кустройства, на этом операция умножения комплексных чисел Завершается,Благодаря конвейерной структуреустройства для умножения комплексныхчисел в мадулярной системе счисленияначиная с третьего такта в нем можетбыть начато выполнение новой операции. Формула изобретения кода по модулям, первый и второй блоки мультиплексоров, второй входнойрегистр, группу блоков памяти, второйблок вычисления интервального индекса и элемент задержки, причем выходблока Формирования дополнительногокода соединен с первым информационным входам первого блока мультиплексоров, второй информационный вход которого является первой группой информационных входов устройства, выходпервого блока мультиплексоров соединен с входом первого входного регистра, выход кстарога соединен с первым информационным входом второго блока мультиплексоров, второй информационный вход которого является второй группой инФормационных входовустройства, выход второго блока мурого входного регистра, выход которого соединен с входом блока Формирования дополнительного кода па модулям,селектарные входы блоков мультиплексоров и тактовый вход элемента задержки объединены и подключены к тактовому входу устройства разряды адресного входа, кроме старших 1-габлока памяти группы (1=1-К) соединены соответственна с разрядами 1-Йгруппы первого и второго входных регистров, выходы первого и второговходных регистров, входы первого ивторого входных регистров. соединены держки соединены соответственно сразрядами адресного входа К-го блока памяти группы, выход которого соединен с входом вспомогательного регистра, первый и второй входы 1-го модульного сумматора группы подключены саатве"ственна к выходу -го блока суммирования вычетов группы и к х-й группе разрядов выхода вспомогательного регистра, выходы блоков деления йа константу группы являются группойвьгходов устройства, .г-я группа разрядов выхода 1-га блока г,:амяти группысоединена с 1-м входам -го алакасуммирования вычетов группы.1280625 Составитель С.Понлихина Техред Л. Олейник в орректор А Обручар актор Н аказ 7067/5 7 а н И Госелам оск изводственно-полиграФическое предприятие, г,ужгород, ул,Проектная ВНИИП по д 13035, Подпомитета ССткрытийая наб д арственногообретений иЖ, Рауш