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

СООЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИ ХРЕСГУ БЛИК 6 Р 7/72 ПИСАНИЕ ИЗОБРЕТЕНИВТОРСКОМУ СВИДЕТЕЛЬСТВУ УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТМ(71) Научно-исследовательский институт прикладных физических проблем им.А.Н.Севченко(56) Авторское свидетельство СССР Ф 1015382, кл. С 06 Р 7/72, 1981.Авторское свидетельство СССР У 1280625, кл, С 06 Р 7/72, 01.08.85. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ КОМП - ЛЕКСНЦХ ЧИСЕЛ В МОДУЛЯРНОМ КОДЕ (57) Изобретение относится к вычислительнрй технике и может быть использовано в быстродействующих процессорах быстрого преобразования Фурье для умножения комплексных чисел на поворачивающие множители, а также для получения последних, Цель изобретения - сокращение аппаратурныхзатрат. Поставленная цель достигает ся тем, что в устройство для умножения комплексных чисел в модулярномкоде, содержащее входной регистр 12,блок 8 формирования дополнительногокода по модулям системы счисления,блоки 7 и 11 мультиплексоров, группублоков 21 суммирования вычетов, вспомогательные регистры 5,10, 13 и 23,блок 29 деления на вспомогателънь 1 ймодуль, блок 22 модульных сумматоров,блок 17 вычисления интервального индекса и блоки 16 н 18 хранения констант, введены вспомогательные регистры 24, 27 и 30, блок 26 мультиплек оров, блок 5 схем сравнения, многовходовый сумматор 20, блок 28 модульных вычитателей, элементы ИЛИ 6,4и элементы 19, 25 и 31 задержки с соответствующими связями. 2 ил.13 ОЬ 11 Изобретение атцаситсв к вычислительной технике ц мажет быть ггсггсньзояаца в быстрслейстнугщих ггрсцгегсарах быстрого преобразования Фурьегдля умножения комплексных чисел ца понорачинающие множители, а также для получения последних.Цель изобретения - сокращение аппаратурньпс затрат. 10На фиг.1 приведена структурная схема устройства для умножения комплексных чисел в мадулярцам коде; на фиг.2- временная диаграмма работы устройства.Устройство для умножения комплекс ных чисел в модулярном коде (фиг,1) содержит первыйи второй 2 информационньге входы, вход 3 номера константы и группу тактовых входов 4 устройства, первый вспомогательный регистр 5, первый элемент ИЛИ Ь, первый блок 7 мультиплексоров, блок 8 формирования дополнительного кода по модулям системы счисления, выход 9 устройства, второй вспомогательный регистр О, второй блок 11 мультиплексоров, входной регистр 12, третий вспомогательный регистр 13, второй элемент ИПИ 14, блок 15 схем сравнения, первый блок 16 хранения констант, блок З 0 17 вычисления интервального индекса числа, второй блок 18 хранения констант, первый элемент 19 задержки,25 М; , М,/щ;,40 45 50,1)К (Х,1 1), (2) Ч (Х 1 р 1) сК (Х 1 Группа блоков 21 суммиронания вычетов содержит блоки суммирования вычетов по модулям щ, - щ, 1 -й из которых (1=01,1 с) осуществляет слогде г. (Х, 14 1 ) =1 М, .ХЪ 1/щ;1;1 М г гс г Х г/щ 111г Ос; 11 - константа с номером 21+1 1 рЕ 01, 1 Е 101-1число используемых комплексныхконстант (поворачивающих множителей); Х,еО щ; - 1 г 11 1-1 с;щ щ- система попарно взаимно простых модулей, причем щ , , 2 р+ +1-2 р - фиксированное натуральное число, щ, - вспомогательный модуль щр, Р, дскб(щщ,)-1, щ, з 1 с, (1 где К (Х, 11) Х И/щ 1 Д О 1 с;Х, если Х с р Х аХ, если ХРмцрг ц;счвггмм:, р .О, груцгубгрксв 21уммггргггсгг гг,г гс тсггблгс22 мсдульных гумматсрв, четверпгг 1валамг:стельный рс г и тр 23 ггятьп 1нсцсмг.птелг.цый регистр 24второйэлемент 25 задержки, третий блок 26мультиплексоров, шестой вспомогательный регистр 27 блок 28 модульныхнычитателей, блок 29 деления ца вспомогательный модуль седьмой вспомогательный регистр 30, третий элемент31 задержки. Временная диаграмма работы устройства (фиг.2) приведена для случая, когда число асцанаций изменяется от "5" да "8", чта соответствует Т=3. На цей для каждого цз Функциональных узлов устройства показацы такты, н течение которых онц осупестнляют действия по обработке действительной час; ти искомого комплексного числа.Временная диаграмма рабать устроЯ- ства при обработке мнимой части искомого числа получается из приведенной днаграммъг путем сдвига последней на дна такта.Первый блок 16 хранения констант реализован на 1 сэлементах памяти, в ячейку 1-го цз котсрых с адресамг 1Х +1 2 +1 2записывается наборрконстант: 11 с); 1 с - число модулей выбранной мадулярцай системы счисления,.П щ,. Первые, вторые и третьи адресные входы элементов памяти в совокупности образуют соответственна первый, второй и тресий адресные входы блока 16 хранения констант, а выходы, соответствующие перьым и 1-м компонентам выходных наборов вычетов, образуют соответственно первый и 3-й выходы блока 16 хранения констант "21 с+2). В ячейку блока 18 с адресом Х + 1 2+ 1 2 г" записьгвается набор констант:(3) где х , М .х;/в,1(Х) - интервальный индекс числа,15Блок 15 схем сравнения содержит1- схем сравнения, каждая из которых формирует на выходе единичный сигнал, если значение на первом входебольше или равно значению на второмвходе.Блок 29 деления на вспомогательныймодуль реализован на 1 элементах памяти, в ячейку с адресом+2 ф 1251-го из которых записывается вычет Первые входы всех элементов памяти объединены и в совокупности с вторы 30 ми входами образуют вход блока 29 деления на вспомогательный модуль. 1(А ы- А" ы")- , (а" +а,", )+а",+а 1, - я, ; (6) с 1 а" ) аР аР -я 1(АъГ+ А" и)- 7 (а Р,Ы; а. М 1Ыа. И,йс 2в,где а Р,Х 1 Р, На первом и втором тактовых входах4 группы, выходе элемента ИЛИ 14 иэлемента 31 задержки формируются управляющие сигналы 6, - 6Модулярный код (Ы,) мнимойЦ,45 части А числа А, поступающий с второго информационного входа 2 устройства на первый информационный входпервого блока 7 мультиплексоров, науправляющий вход которого подается 50 сигнал б, =О, записывается во входнойрегистр 2; а в регистр 3 через вход3 устройства передается номер комплексной константы И.На первом такте модулярный код(д с) 4 исла А с входа 1 устройства через второй блок 11 мультиплексоров (6 0) поступает на входблока 7 вычисления интервального индекса числа и первый адресный вход 1 Ч 11, ., Ы 3(7) жение за Т = ) 1 ое Етактов наборов и . 1 свычетов по модулю в,.Блок 17 вычисления интервального индекса числа по входному модулярному коду (х ,х) некоторого числа Х модулярной системы счисления определяет машинный интервальный индекс:(1 1; 1. 1ае, ва Р 1(А )1; а1(-А" ) ЪРЯ, - количество переполнений присложении чисел АЯи А ИЯ - количество переполнений присложении чисел А 11" и А " 1".Рассмотрим как работает устройство для умножения комплексных чисел в моцуляриом коде. Элементы 19 и 3 задержки вьп лняют задержку сигнал сответственно на Т и (Т+3) такта.Второй элемент 25 задержки представляет собой цепочку из Тпоследовательно соединенных регистров, вход первого и выход последнего иэ которых являются соответственно входом и вьходом второго элемента 25 задержки,Алгоритм умножения комплексных чисел, реализуемый предлагаемым устройством, базируется на нижеследующем. Пусть требуется перемножить комплекс И ное число АА + 1 А на комплексную И ,И константу И= + 1, имеющую РМ , рМ 1,. номер 1, А,А",И,И - целые числа из диапазона П модулярной системы счисления. 1Действительная и мнимая части профизведения В=В + 1 Вмогут быть вычислены по следующим приближеюым формулам:В -,У (А И + А" Ы), (5) где,1 (Х)1 (Х) /и,- ядерный интервальный индекс числа Х;х 1 - ближайшее к х целое число.При этом1330 3Г5первого блока 16 храпни коцтяцт, на второй и третий адресные входы которого с выходов оответстнсццо ИЗИ 6 элемента и регистра 13 постуияют величины 1 и 1, О, 5На первом выходе первого блока 16 хранения констант формируется набор вычетов г (ь.,1, 1), который цоступает во вспомогательный регистр 24, на -м выходе первого блока 16 10 хранения констант Формируется набор вычетов К ,(Ы 11) (см.формулу (1), который поступает на вход группы блоков 21 суммиронания вычетов, которые в ходе очередных Т тактов 15 суммируют по модулям системы наборы входных вычетов а блок 17 вычисления интервального индекса числа начинает вычисление по модулю в инер-. вального индекса 1(Л ), 20На втором такте работы устроистна модулярный код () числаА с выхода входного регистра 2 через второй блок 11 мультиплексоров (ь 1) поступает ца нхад блок 17 ны числения интервального индекса числа и первый адресный вход первого блока 16 хранения констант, на второй и третий адресные входы которого поступают неличицы 1 и 1 =1. Содержимое З 0Овспомогательного регистра 24 записывается но вспомогательный регистр 27, а во вспомогательный регистр 24 поступает набор вычетов г;(Ы , 1 ,1), который формируется ца первом выходе 35 первого блока 16 хранеция констант.На 1-м ныходе первого блока 16 хранения коцстацт формируется набор вычетов К;. (Ы. 1,1), поступаюций на входы блоков 21 суммирования выче тов, а блок 17 вычисления интервального индекса числа начинает вычисления по модулю тинтернального индекса 1(Л )На третьем такте работь содержи мые вспомогательных регистров 24 и 27 поступат соотнетственно на первый и второц входы блока 15 схем сравнения, ця выходе которого формируются результаты сранцения, которые 50 поступают ця четвертом такте ца вход сумматора 20, который находит величину Я, эяписыцанхпуюся в первый регистр второ о элемента 25 задержки.На (Т)-и такте на вход приема 55 кода регистра 23 поступает сигнал 1,=1, нслелстце чего содержимое 1 регистра 13 я, ыается в регистр 23,611 ти 1-г такта работы устрйстяя ихлс: блока 17 нычцслеця нчерняльцого индекса числа формируется нычет 1.(А ).11 я (Т+1)-м такте величина 1(А) с вьходя блокз 17 нычисления интервального индекса числя поступает на первый адресный вход второго блока 16 хранения констант, ца третий и второй адреснье входы которого подаются соответственно величины 1 О с выхода элемента 19 задержки и величина 1 с выхода регистра 23. На выходе второго блока 18 храцеиия констант формируется набор остатков по модулям величи" цы Я"(Формула (7), которая записывается но вспомогательный регистр 5. Ня выходе группы блоков 2 суммирования вычетов формируется набор ныче.ц, тон по модуяям величины( а ца выходе блока 17 вычисления ицтернальцого индекса числа - вычет 1(А ). Нз (Т+2)-м такте величины с выходов трупп блоков 21 суммирования и нсомогательцого регистра 5 поступают соотетствеццо ца первый и второй вхоль блока модульных сумматоров 22, иа щхде которого формируется вели.( 11чцця .1( =(; + Ц записынаа -екщаяся но вспомогательный регистр 30. Одновременно с этим величина с выхода блока 17 вычисления интервального индекса числа поступает на первый адрссцый вход второго блока 18 хранения констант, ца третий и второй адресные входы которого подаются соответственно величины 1с выхода элемен та 19 задержки и 1 с выхода регистра 13. На выходе второго блока 18 хранения констант формируется набор остатков по модулям величины 1(А " ) И которая записывается во вспомогательный регистр 5. На выходе группы блоков 21 суммирования вычетов формируется набор остатков по модулям вефИличины- , на выходе1второго элемента 25 задержки появляет ся величина Я, .На (Т+3)-м такте величины с выходов группы блоков 21 суммирования вы" четон и вспомогательного регистра 5 подаются соответственно на первый и второй входы блока модульных сумма713тОрОВ 22, НЛ ЫХС)д КС)торс)ГО 11)орМ 1)у -С 1 . Сется величина Хл+ 1(А ) И ), которая злпгваетея овспомогательый регистр 30. ПредыдуЩЕЕ СОДЕРЖИМОЕ ВСПОМОГЛТЕЛЬЦОГО РЕгистра 30 (Х ) поступает нл перьввход блока 28 модульных чТлтелена второй вход которого через третийблок 26 мультиплексоров (Д,=О) с ьхода второго элемента 25 задержки поступает величина Я, Блок модульцьхвычитлтелей 28 находит величину г "1Х, - Якоторая записывается вовспомогательный регистр 10,На (Т+4) -м такте работы устрс)йствлвеличинл Х с выхоцл вспомогательногорегистра 30 подлется ца первый ходблока 28 модульных вьчитателей, цлвторой вход которого через блок 26мультиплексоров (6,=1) с выхода спомогательного регистра 1 О поступает1величина г . Блок модульных вычитателей находит еличину Х - гс-1(А 11 - А " 11") (см.формулу (6),которая записывается во вспомогательньв регистр 10.На (Т+5)- такте содержимое вспомогательного регистра 10 поступаетна вход блока 29 деления ца вспомогательный модуль определяющий модулярный код (р, р ) действитЕЛЬНОй ЧаетИ ИСКОМОГО йРОлЗВЕДЕНИЯкоторый снимается с выхода 9 устройства,В ходе тактов с третьего пс (Т+7)-йвключительно указанные действия ыполняются для модулярцых кодов(- Ы, /гп,) последний из которых натретьем такте работы устройства формируется в блоке 8 формирования дополнительного кода по входному моду 1 слярному коду числа А и записываетсяво входной регистр 12. Иодулярньгйкод ( р11) на (Т+7)-м тактеснимается с выхода 9 устройства ина этом операция умноения комплексных чисел А и 11 завершается.формула изобретенияУстройство для умножения комплексных чисел в модулярном коде, содержащее входной регистр, блок формирования дополнительного кода по модулям системы счисления, два блока мультиплексоров, группу блоков суммирова 10)6)11 10 15 20 25 30 35 40 45 50 55 11111 1 ЧЕТ;)С, ЧЕТЫГЕ С.СС , О,сЕ 1,С1)е 1 ст 1)л, блслк делс 111 я 11,1 сс ч,1те 1 п мс)пуль, блок мс);)ус,с,скуссмс ТОро, бЛОК ВЫЧИСЛЕия ;сцт ра;, ОГОилексл пслл и Дл бзс)к;1 к 11 с 1111констант, причем пег лсе 1111 )г;11 и. и -ные Входы ер)ОО и тог)с)го бло 1 О МУЬТГПЛРКС ОРОВ ГОРДИС 11 Ы Г ОР Е ТЕ Т - ецо г торг и перяым 11 ормл 1 ов ИЫМИ ВХОдаМИ уСтройСГЛ, Ыхссд ПС рО- го блока мультиплекеоросг лине с входом входного регистра, 1,гход которого соединен с входом блока ФормиРОЛЦИЛ ДОПОЛЦИтЕЛЬЦОГО КОДЛ ПО МОдулям системы счисления, ьКОП второго блока мультиплексоров соецспец спервым адресным ходом иерого блока хрсРця констант, вьходы кото)ого, кроме младшего соединены с входами соответствУюЩих блоков сУмРовлнил вычетов группы, выходы которых соединеиь с входом первого слагаемого блока модульных сумматоров, вход второго слагаемого которого соединен с вьг:.одом первого вспомогательного регистра чход которого соединен с ыходом второго блока хранения констант,первый лдресньсй ход которого соедицец с выходом блока вычисления интервального индекса лсцлход которого соединен с Рьходо второго блока мультиплексоров, выход второговспомогательного регистра соединен свходом блока деления на вспомогательный модуль, выход которого являетсявьсходом устройства, вход номера константы устройства соединен с входомтретьего вспомогательного регистра,выход которого соединен с информационным входом четвертого вспомогательного регистра, выходы третьего и четвертого вспомогательных регистров соединены соответственно с вторыми адреснь 6 входами первого и второго блоковхранения констант, первый и второйтактовые входы группы устройства соединены соответственно с входом разрешения приема четвертого вспомогательного регистра и с управляющим входом первого блока мультиплексоров,о т л и ч а ю щ е е с я тем, что, сцелью сокращения аппаратурных затрат,оно содержит пятый шестой и седьмойвспомогательные регистры, третий блокмультиплексоров, блок схем рангения,многовходовай сумматор, блок модульных вычитлтелей, двл элемта ЖИ итри элемента задержки ирчем выход1330631блока формирования дополнительного ко нходом второго блока мультиплексоров, да по модулям системы. счисления сое- второй и третий тактовые входы гру пы динен с вторым информационным входом устройства соединены соответственно первого блока мультиплексоров, выход с вторыми входами первого и второго5входного регистра соединен с вторым элементов ИЛИ, выход многовходового ииформационным входом второго блока сумиаторд соединен с входом второго мультиплексоров, младший выход перво- элемента задержки, выход которого соего блока хранения констант соединен с динен с перным информационным входом входом пятого вспомогательного ре О третьего блока мультиплексоров, втогистра, выход которого соединен с пер рой информационный вход которого соевым входом блока схем сравнения и че" динен с выходом второго вспомогательрез вестой вспомогательный регистр - ного регистра, выход второго элеменс вторым входом блока схем сравнения, тя ИЛИ соединен через третий элемент выход которого соединен с вТорым вхо задержки с управляющим входом третьедом многовходового сумматора, первый го блока мультиплексоров, выход котактовый вход группы устройства соеди торого соединен с входом вычитаемого иеи с первыми входами первого и вто- блока модульных вычитателей, выход рого элементов ИЛИ, выход первого эле. которого соединен с входом второго мента ИЛИ соединен с третьим адресным 20 вспомогательного регистра, выход бловходом первого блока хранения конс- ка модульных сумматоров соединен с таит и через первый элемент задераки - входом седьмого вспомогательного рес третьим адресным входом второго бло. гистра, выход которого соединен с ка хранения констант, выход второго входом уменьщаемого блока модульных элемента ИЛИ соединен с управляющим 5 вычитателей.манера /7 Юл 77 ЮЮ Блок 15 ок 2 Елок ок Елок ло Елок 25 блок дк Ю Составите Техред В. Корр едактор М.Дыл р И.Муск Закаэ 358 ВНИИПИпо д13035 эводственно-полиграфическое предприятие,г.ухгород,ул.Проектная блок 171- с. ооращеюиеблок 17г-с. опрощениеблок 211-с. обращениеЮлон 21г-с опрощение 1 2 3 4 5 б 7 д Тирах 672 Подписносударственного комитета СССРам иэобретений и открытийосква, Ж, Раушская иаб., д,4