Устройство для вычисления дискретного преобразования фурье в модулярной системе счисления

ИЯ СВИДЕТЕЛЬСТ ВТОРСК ЛЕНИЯ ВАНИЯ Е СЧИГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ПИСАНИЕ ИЗО(71) Научно-исследовательский институт при кладных физических проблем им. А Н. Севченко(54) УСТРОЙСТВО ДЛЯ ВЫЧИС ДИСКРЕТНОГО ПРЕОБРАЗОФУРЬЕ В МОДУЛЯРНОЙ СИСТЕМ СЛ ЕНИЯ(57) Изобретение относится к вычислительной технике и предназначено для использования в высокоскоростных процессорах, базирующихся на алгоритмах типа Винограда. Цель изобретения - повышение быстродействия и расширение области применения за счет реализации преобразова. ния для произвольного целого значения основания. Для достижения цели устройство содержит регистры 11.1 - 14,1, сумматоры 15.1, 16.1 по модулю т 1, вычитатели 171, 18.1 по модулю т 1, операционные блоки 19.1, 20.1, преобразовател ь 21 двоичного кода в модулярный и преобразователь 22 с масштабированием модулярного кода в двоичный, 1 табл. 3 ил.Изобретение относится к вычислительной технике и предназначено для использования в высокоскоростных процессорах быстрого преобразования фурье, базирующихся на алгоритмах типа Винограда.Цель изобретения - повышение быстродействия и расширение области применения за счет реализации преобразования для произвольного целого значения основания.На фиг. 1 представлена структурная схема устройства для вычисления дискретного преобразования Фурье в модулярной системе счисления; на фиг. 2 и 3 - структурные схемы операционных блоков соответственно первой и второй групп.Устройство содержит информационный вход 1, первый 2 и второй 3 установочные входы, входы 4 - 8 кода операции, знаковый вход 9, тактовый вход 10, четыре группы регистров 11.1 - 14.1, две группы сумматоров 15.1, 16.1 по модулю т 1,две группы вычитателей 17.1, 18.1 по модулю т 1,две группы операционных блоков 19.1 и 20.1, преобразователь 21 двоичного кода в модулярный, преобразователь 22 с масштабированием модулярного кода в двоичный, выход 23. Индексы номеров блоков (1=1, 2, ,К),совпадают с порядковыми номерами модульных оснований т, т 2т, связанных с этими блоками.Операционный блок 19.1 первой группы состоит (фиг. 2) из групп регистров 24.р - 29.р (р=0, 1, , (Л - 1)/2), группы сумматоров 30.р по модулю т 1 и группы умножителей 31.р по модулю т 1.Операционный блок 20.1 содержит (фиг. 3) группы регистров 32.г - Зб.г (г=1,2(Л - 1)/2), группу сумматоров 37.г ло модулю т 1 и группу умножителей 38.г по модулю т 1.Входы разрешения записи регистров 25.0, 25.1, , 25. (Х - 1)/2 объединены и подключены к входу 39 кода операции устройства. Входы 40 - 42 кода операции устройства соединены с входами разрешения записи соответственно регистров 24.р, 26.р и 27.р (р= =0,1(А - 1)/2) операционных блоков 19.1 группы и соответственно регистров 32.г - 34.г (г= 1,2(% - 1)/2) операционных блоков 20.1 группы. Входы разрешения записи регистров 28.0, 28.1, , 28(М - 1)/2 и 29.0, 29.1, , 29(Л - 1)/2 объединены и подключены к входу 43 кода операции устройства.Входы 44 и 45 кода операции устройства соединены с входами разрешения выдачи соответственно регистров 25.р и 26.р групп.Входы 46 и 47 кода операции устройства содержат по (Л+1)/2 шин, причем р-я шина входа 46 заведена на вход разрешения выдачи регистра 28,р, а р-я шина 47 - на вход разрешения выдачи регистра 29.р (р=0,1 (А -)/21,г-я шина входа 46 заведена на вход разрешения выдачи регистра 35.г, а г-я шина входа 47 устройства -на вход разрешения выдачи регистра Зб.г(=1 " (ф - 1) /2) Б качестве преобразователя 21 двоичного кода в модулярный и преобразователя 22 с масштабированием модулярного кода в двоичный мо.;но использовать любые известные устройства, работающие в конвейерном режиме. Тогда преобразователь 21 будет осу. ществлять преобразование двоичного кода в модулярный за 1 тактов (7= 1 од 2 К) с пропускной способностью одно число за такт, а преобразователь 22 в перевод числа из модулярной системы счисления в двоичную и масштабирование на константу Г) за 7+3 тактов с пропускной способностью одно число за акт.Реализация дискретного А.точеч ного (Л-простое число) преобразования Фурье входной последовательности у(л) =17(л) + +ц" (л) (л=0,1, , А; у(л) и у"(л) соответственно действительная и мнимая составляющие входного отсчета у(л заклю. чается в вычислении 40 45 50 55 Все функциональные узлы устройства могут быть реализованы на основе поетоянных запоминающих устройств (ПЗУ) небольшой емкости (например, серий К 556, К 541) и регистров разрядностью Ь= 1 од 2 т 1, черезхобозначается наименьшее целое число, не 1 О меньшее действительного числа х, где 1 соответствует индекс) номера регистра или операционного блока, куда входит регистр. Причем выходы регистров 25.р, 26.р, 28.р, 29.р, 35.г, 3 б.г (р=0,1(% - 1)/2; г=1,2(Л - -1 ) /2) могут переходить в высокоомное третье состояние, что позволяет обьединить выходы блоков и осуществлять таким образом мультиплексирование данных. Информация на выходе этих регистров появляется ири наличии сигнала низкого уровня на входе 20 разрешения выдачи кода соответствующегорегистра. Запись информации в любой ре.гистр устройства осуществляется нарастающим фронтом тактового сигнала на тактовом входе регистра ири наличии низкого уровня на входе разрешения приема кода.25 Сумматоры 15.1, 16.1, 30.р, 37.г и вычитатели 17.1, 18.1 (1=1,2К; р=0,1 (Л 1) /2; г=1,2 (А - 1) /2) могут представлять собой ПЗУ емкостью 2"слов по Ь, бит, в которых ио адресу Х+ У 2" записана сумма Л+Уи для сумматоров или разность Х - У),для нычитателей. Сумматоры 16.1 и вычитатели 18.1 имеют управляемые выходы с гремя состояниями. Информация иа их выходах появляется ири наличии сигнала низкого уровня на входе разрешения выдачи.В остальное время выход находится в высо коомном состоянии. Умножитслн 3.р и 38.г1-х операционных блоков также могут являться ПЗУ емкостью соответственно 2 и 2"фслов по б, бит.(и)= 1(у(п)сов(2 лип/Л+ у(п)бп(2 лип/А(;Дйфф- их (и)= - г(у (п)сок(2 лип)А)-у(л)яп(2 лип/А. (3) Учитывая периодичность со(2 лил/Л и б(п(2 лип/Л) и аппроксимируя их соответственно дробями Л(ип)/О и Уфил)/Я, исходное ДПФ можно переписать в следующем приближенном виде+Х А (А -2(ь(ЯА,)=" )+У (Аи ; ( )и Л( ) ии(А Через Х обозначается ближайшее к Х целое число. В последнем выражении( это некоторое целое число, задающее диапазон измерения действительной и мнимой составляющих констант еР (р=О, А - 1) .Рассмотрим, как работает устройство для вычисления Л(-точечного дискретного преобразования Фурье в модулярной системе счисления (А -простое).Двоичные числа, постчпающие на информационный вход устройства, а также формируемые на его выходе, принадлежат диа. пазону, - ,), - ,)+1 , гдевыбирают из условия л - вспомогательный модуль, выбираемый из чсловий тэ 2 тК - 2, и, э К - Я За время очередного преобразования Фу.рье через информационный вход 1 за 2 А так.тов поступают А комплексных отсчетову(0), У(1), , у(А - 11, причем установлен20 следующий порядок их поступленияд (0), У(1). у (А - 1), У(2), д(- 2), , УА- 1)/2), уА+1)/2), у",0,и), у "(,Ъ - 1),У ( , )/2) и+1,Так как устройство работает в конвейерном режиме с пропускной сиособность однопреобразование Фурье за 2 А тактов, то каждый блок устройства занят в данном преобразовании в течение 2 А тактов. Если заначало текущего преобразования принятьмомент поступления первого отсчета на ин 3 О формационный вход 1 устройства, то началоработы любого блока устройства в данномпреобразовании будет сдвинуто на вличинузадержек в предыдущих блоках устройства.Рассмотрим вначале подробно обработкчдействительных частей входных огсцетов, по 35 ступающих на устройство в течени крвыхА тактов. С информационного входа 1 устройства отсчеты попадают в преобразователь21, который осуществляет перевод числа нздвоичной системы в модулярную Число уп)(п=0,1, , Л - 1) проходит преобразователь4 О 21 за Т тактов и появляется на его выходев виде набора остатков у(л), у.(л)у(л),где у (л) ц(п)1 =1.2К). На (-м такте отначала преобразования на входе 4 появляет.ся сигнал низкого уровня Г 1=0 ( м, таблицу,45 где указаны номера тактов, во время которых на установочные входы кода операции устройства посгупают сигналы низкогоуровня, управляющие работой блоков устройства) и в регистр 11.( заносится вычетУ(0). Одновременно сигнал (х 1=0 с первого5(1 установочного входа 2 устройства обнуляетрегистр 12.(. Тогда на следующем (Т+1)-мтакте с входа 6 чстройства по тупает сигналГЗ=О, и число у О), после сложения (вычитания) с нулем в сумматоре 15.( и вычитателе17.( заносится в регистры 13.(, 14 В этом55 же такте по Г 1=0 в регистр1. занесетсявычет 1).По сигналу Г 2=0 на входе 5 устройствав регистр 12. поступает на (2-м такте7число у(Л - 1). Одновременно вычет у(0) из регистра 131 поступает в операционный блок 191, где после умножения н умножителе 31.0 на Я произведение у)(0)заносится в регистры 25.0 - 25. (А - 1) /2 по сигналу Г 6=0, поступающему н данном такте (см. таблицу) с входа 39 устройства. На (Т+3)-м такте пара чисел у(1) и у(Л 1) формирует согласно формуле (5) на выхо дах сумматора 15.1 и вычитатечя 17.1 неличи. ны А,(1) и АфМ - 1), которые поступают ссютветственно в регистры 131 и 14.1 по сигналу ГЗ=О с входа 6 устройства. В этом же такте н регистр 11.1 по сигналу Г 1=0 заносится новое число у(2), Таким образом,/поочередно через такт вычеты у(1) и у(Т - 1) (1=1,2(Л 7 - 1)/2) с 1-го выхода преобразователя 21 заносятся соответственно н регистры 1,1 и 12.1. Тогда на выходе сумматора 151 формируется величина А(1)г а на выходе вычитателя 17,1 - величина А(Ю - 1), которые запоминаются ссютветственно в регистрах 13. и, 14.1 по сигналу ГЗ=О, поступающему с входа 6 устройства на (Т+1+2)-м тактах. С выхода регистра 13.1 число А,(1) поступает на (Т+2+21)-м такте на входы умножителей 31.р (р=0,1(А - 1)/2).Иа выходе умножителя 31.г (г=1,2 (А)/2) формируется произведениеА(1)Х ХЛф(г)1 которое заносится в этом же такте в регистр 24.г по сигналу Г 7.=0, поступающему с входа 40 устройства. Этим же сигналом в регистр 24.0 заносится величина 1 А(1) Яс умножителя 31.0 На (1+5)-м такте на вход разрешения выдачи числа регистров 25.р поступает сигнал Г 11=0 с входа 44 устройства, По этому сигналу число А,(0)Япоступает на первые входы сумматоров ЗО.р, где оно складывается с числом 1 А(1) Я(для сумматора 30.0) и с числом А Л(г(для сумматора 30.г). Сумма заносится в регистр 26.р по сигналу Г 8=0, поступающему на вход разрешения записи этого регистра в данном такте с входа 41 устройства. Далее на (+3+21 ) -м такте (1=2, 3, , (А - 1/2) осуществляется суммирование содержимого регистра 26.0 с числом А (1) =Я) поступающим из регистра 24.0. При этом на входы разрешения выдачи регистров 26.р поступают на (Т+3+21).х тактах с входа 45 устройства сигналы Г 12=0 (см. таблицу). Результат суммирования поступает с выхода сумматора 30.0 в регистр 26.0, где запоминается по сигналу Г 8=0.Одновременно в регистре 26.г по этому же сигналу запоминается сумма от сложения содержимого регистра 26,г и числаАТ) Х ХЛ (г)1 (г=(гм-у+1), Таким образом,через А тактов от начала работы сумматора 30.0 на его выходе сформируется величина(фф-Фе,(Дур(0)+ЯХ Афщ,а на выходе сумматора ЗО.г - величина()Г.фф 1+ поступает со знакового входа 9 устройства, 40 содержащего (А - 1)/2 шин, причем г-я шиназаведена на второй вход умножителя 38.г операционного блока 20.1. С выхода регистра 32.г числа поступают на второй вход сумматора 37.г, где они суммируются с содержимым регистра ЗЗ.г (г=г - 2 г.,)1+ ).Результат сложения по сигналу Г 8.=0з а пом и наетс я вновь в регистре 33.г. Г 1 ри этом на Т 4-м такте на установочные входы регистров 33.1, 33.2, , 33. (Л 1 - 1)/2 поступает сигнал Я 2=0 с установочного входа 3 50 устройства. В результате действия этого сигнала н указанных регистрах появляются нули, Тогда на (Т+5) -м такте в регистр ЗЗ.г поступает суммаЬг 1 А,(Н)Х(г) Далее, на (+3+21)-м (1=2, 3, , (Л 1 -)/2) такте в регистр ЗЗ.г по сигналу Г 8=0 поступает 55 результат сложения величины Бг 1 А 1 М - 1)ХХ 7"(г)с содержимым регистра ЗЗ.г.Таким образом, на (1+%+2)-м такте навыходе сумматора 37.г появляется сумма 5 10 15 20 25 30 35( И)й,Е=4На (+Л+2)-м такте по сигналу Г 9=0, поступающему с входа 42 устройстна, перная изэтих величин заносится в регистр 27.0, авторая - н регистр 27.г,.Аналогичным образом в течение следующих М тактов осуществляется обработкаследующих А входных отсчетон у (О), У (1),ЧЛ 1-1), ц "(2) У (О)/2), У %+1)/2).Сформированная на (Т+2 М+2)-м такте ве.личина(лl-),Ц у(0)+С А,(1)1заносится с выхода сумматора 30,0 н регистр29.0, а величина1 и-)йЯВ(0)+ А(1) Л(г 1)1,. с выхода сумматора 30.г н регистр 29.г, Одновременно осуществляется перезапись чисел из регистра 27.р в регистр 28.р. Запись в регистры 28.р и 29.р осуществляется по сигналу Г 10=0, поступающему на (Т+2 А +2)-м такте с входа 43 устройства.Г 1 ареллельно с работой операционного блока 191 осуществляется обработка вычейтон А(,17 - 1) и А(Ф - 1) н операционном блоке 20 1. В соответствии с этим вычет А 1(Л - 1), поступающий с выхода регистра 14.1 на первые входы умножителей 38.г (г=1,2(Ю - 1)/2), совместно со знаковым признаком 5 г 1 на втором входе умножителя формирует произведениеЗг 1 А(А - 1)Х ХУ(г),. которое поступает на Т+21+2).м такте в регистр 32,г. Запись в регистр 32.г осуществляется по сигналу Г 7=0.Знаковый признаквления преобразования для произвольного целого значения основания Л, в него введены вторые группы сумматоров и вычитателей по модулю т 1, четвертая группа регистров и первая и вторая группы операционных блоков, п ри этом информационный вход преобразователя двоичного кода в модулярный является информационным входом устройства, а 1-й выход преобразователя двоичнго кода в модулярный соединен с информационными входами 1-х регистров первой и второй групп, второй установочный вход устройства подключен к установочным входам операционных блоков второй группы, третий вход кода операции устройства подключен к входам разрешения записи регистров четвертой группы, четвертый и пятый входы кода операции устройства подключены к входам разрешения выдачи соответственно сумматоров по модулю т 1 и вычитателей по модулю а 1 вторых групп, выход 1-го регистра первой группы соединен с первыми входами 1-х сумматора по модулю т 1 и вычитателя по модулю т 1 первых групп, вторые входы которых подключены к выходу 1-го регистра второй группы, выход 1-го сумматора по модулю т 1 первой группы соединен с информационным входом 1-го регистра третьей группы, выход которого соединен с информационным входом 1-го операционного блока первой группы, выход 1-го вычитателя по модулю т 1 первой группы соединен с информационным входом 1-го регистра четвертой группы, выход которого соединен с информационным входом 1-го операционного блока второй группы, знаковый вход которого соединен со знаковыми входами операционных блоков второй группы и подключен к знаковому входу устройства, выход 1-го операционного блока второй группы соединен с первыми информационными входами 1-х сумматора по модулю т 1 и вычитателя по модулю т 1 вторых групп, вторые информационные входы которых подключены к первому выходу 1-го операционного блока первой группы, второй выход которого соединен с выходами 1-х сумматора по модулю т 1 и вычитателя по модулю т 1 вторых групп и подключен к 1-му входу преобразователя с масштабированием модулярного кода в двоичный, выход которого является выходом устройства, тактовый вход которого подключен к тактовым входам операционных блоков первой и второй групп и регистров четвертой группы, причем 1-й операционный блок первой группы содержит с первой по шестую группы регистров по (А+1)/2 регистров в каждой, группу из (М+ )/2 сумматоров по модулю т 1 и группу из (%+1)/2 умножителей по модулю т 1, при этом входы умножителей подключены к информационному входу операционного блока первой группы, выход р-го умножителя, где р=0,1(Л 1 - 1)/2, соединен с информационным входом р-го регистра первой группы, кроме того, выход нулевого умножи теля соединен с информационными входами регистров второй группы, выход р-го регистра первой группы соединен с первым входом р-го сумматора по модулю т 1 группы, выход нулевого регистра второй группы соединен с выходом нулевого регистра третьей группы и подключен к второму входу нулевого сумматора по модулю т 1 группы, 0 выход которого соединен с информационными входами нулевых регистров третьей, четвертой и шестой групп, выход г-го регистра, где г= 1,2, ,(Л 1)/2, второй группы соединены с выходом (г - 2(А - 1)/2+ )-го )5 регистра третьей группы и подключен кпервому входу г-го сумматора по модулю т 1 группы, выход которого соединен с информационными входами г-го регистра третьей группы и ( г( Л -) /2 + 1) регистров четвертой и шестойрупп, выход р-го регист ра четвертой группы соединен с информационным входом р-го регистра пятой группы, выходы нулевых регистров пятой и шестой групп соединены и являются первым выходом операционного блока первой груп пы, а выходы остальных регистров пятойи шестой групп соединены между собой и образуют второй выход операционного блока первой группы, тактовые входы всех регистров операционного блока первой группы соединены между собой и образуют такЗ 0 товый вход операционного блока первойгруппы, причем 1-й операционный блок второй группы содержит с первой по пятую группы регистров по (А - 1) /2 в каждой, группу из (Л - )/2 сумматоров по модулю т 1 и группу из (Х)/2 умножителей по З 5 модулю т 1, при этом первые входы умножи.телей соединены между собой и являются информационным входом операционного блока второй группы, вторые входы умножителей образуют знаковый вход операционного блока второй группы, выход г-го умножителя, где г=1, 2, , (Л - 1)/2, соединен с информационным входом г-го регистра первой группы, выход которого соединен с первым входом г-го сумматора по модулю т 1 группы, второй вход которого подклю 45 чен к выходу (г - 2(А - 1)/2+ ) регистравторой группы, а выход - соединен с информационными входами г-го регистра второй группы и (г - 21(М - 1)/2+1) регистров третей и пятой групп, выход г-го регистра третьей группы соединен с информационным 50 входом г-го регистра четвертой группы,входы установки в О регистров второй группы являются установочным входом операционного блока второй группы, выходы регистров четвертой и пятой групп соединены через монтажное ИЛИ и образуют выход 55 операционного блока, а тактовые входы всехрегистров являются тактовым входом операционного блока, шестой вход кода опера1 б 334 3 14 ции устройства подключен к входам разрешения записи регистров второй группы операционных блоков первой группы, седьмой вход кода операции устройства подключен к входам разрешения записи регистров первых групп операционных блоков первой и второй групп, восьмой вход кода операции устройства подключен к входам разрешения записей регистров третьей группы операционных блоков первой группы и регистров второй группы операционных блоков второй группы, девятый вход кода операции устройства подключен к входам разрешения записи регистров четвертой группы операционных блоков первой группы и регистров третьей группы операционных блоков второй группы, десятый вход кода опе 1)аПоследуюиие такты (прибавляются к тахту от начала преобразования) од Тахт от начала преобразо- вания Сиг 2 Я2 ЯО 1 " 3 4 Ч-" ЯЯ Я+1 Яф 2 Я+3 Я+4 о 3 О 0) 0 о о о 0 0 о о/с ооо о оо оо о о22о12Я г с о т+3+2 Я т+3+2 Я т+э+гя т+3+гя о оо о о о Т+Э+2 Я 81 гягГ 1 4Г 2 5ГЭ 6Г 4 7Г 5 8Г 6 39Г 7 43Г 8 41Г 9 42Г 10 43Г 11 44Г 12 45Г 13.0 46Г 13. 1 46Г 13.2 46Я Г 13. в -46гГ 14. С 47Г 14, 1 47Г 14.2 47Я Т 14. в -472 т т т т т+1 Т+3+2 Я т+3+2 Я т+г т+ т+э Т+3 т+3 Т+5 Т+3 т+Э+2 Я т+3+2 Я т+3+гя ции устройства подключен к входам разрешения записи регистров пятой и шестой групп операционных блоков первой группы и регистров четвертой и пятой групп операционных блоков второй группы, одиннадцатый и двенадцатый входы кода операции устройства подключены к входам разрешения выдачи регистров соответственно второй и третьей групп операционных блоков первой группы, тринадцатый и четырнадцатый входы кода операции устройства подключены к входам разрешения выдачи регистров соответственно пятой и шестой групп операционных блоков первой группы и регистров соответственно четвертой и пятой групп операционных блоков второй группы.1633423ль Ю. Лавчмк ВНИИПИ Гос рственного комитета по изобретениям 13035, Москва, Ж - 35, Раугцская о.издательский комбинат Патент, г и открыти наб., д. Ужгород зводствен Редактор В. ДанЗаказ 6 8 СоставТехред А. КТираж 409 ов КоррекПодпис р Т. Малеце м прн ГКНТ ССС /5 л Гагарина. 10