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

(7) Заявит 4) УСТРОЙСТВО ДЛЯ РЕАЛИ БЫСТРОГО ПРЕОБРАЗОИЯ ФУРЬ Изобретение относится к области вычислительной техники и может быть использовано в системах и устройствах цифровой обработки информации в качестве преобразователей временной последовательности отсчетов входного сигнала в частотную последовательность и наоборот.Известно устройство, содержащее блок оперативной памяти, блок констант, устройство умножения комплексных чисел блок сложения-вычитания, устройствауправления Я.Наиболее близким по технической реализации и по выполняемым функциям к данному изобретению является устройство для реализации быстрого преобразования фурье, содержащее блок управления,оды которого соединены с управлжоми входами соответственно первогоатора-вычитателя, первого, второго, третьего и четвертого умножителей, второго и третьего сумматоров-вычитат елей, первого и второго промежуточного реги выхсумм ров, адресного блока констант и адресно,го блока исходной информации, выход адресного блока констант через блок постоянной памяти подключен ко входу регистраконстант, первая, вторая, третья и четвертая группы выходов которого подключены к первым входам соответственно первого, третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей подключены соответственно ко входам второго и третьего сумматоров-вычитатепей, выходы которых подключены соответственно к первому и второму входам первого промежуточного регистра, выход адресно 5го блока исходной информации подключен к первому входу блока оперативной памяти, первый выход которого подключен ко входу первого входного регистра, выходы которого подключены ко входам первого сумматоравычитатепя, первая и вторая группы выходов которого подключены ко вторым входам соответственно первого, второго ст- и третьего, четвертого умножителей, пер4708 55 3 73 вая, вторая и третья группы выходов первого сумматора-вычитателя подключены соответственно ко аходам первого и второго промежуточных регистров, выходы которых через первый выходной регистр подключены ко второму входу блока оперативной памяти 2.Недостатком этого устройства является низкое быстродействие.Белью изобретения является повышение быстродействия.Цель достигается тем, что предлагаемое устройство содержит второй аходной регистр, третий и четвертый промежуточные регистры, четвертый сумматор-вычитатель и второй выходной регистр, причем второй выход блока оперативной памяти через второй аходной регистр подключен ко входам третьего и четвертого промежуточного регистров, первая и вторая группы выходов третьего промежуточного регистра подключены к третьим аходам соответственно первого, второго и третьего, четвертого умножитслей, первая и вторая группы выходов третьего промежуточного регистра и первая группа выходов четвертого промежуточного регистров подключены соответственно к первой, второй и третьей группе входов четвертого сумматоравычртателя четвертая и пятая группа аходов которого подключены соответственно к выходам второго и третьего сумматоров-вычитателей, выходы четвер- того сумматора-вычитателя через второй выходной регистр соединены с третьим аходом блока оперативной памяти, управляющие аходы третьего промежуточного регистра и четвертого сумматора-вычитателя подключены к соответствующим выходам блока управления.На фиг. 1 представлена структурная схема предлагаемого устройства, на фиг. 2 - граф, алгоритма быстрого преобразования фурье, (БПф) реапизованный в устройстве; на фиг. 3 - временные диаграммы работы устройства; на фиг. 4 - график, показывающий процент выиграша в быстродействии устройствадля массивов различной длины.Схема устройства включает в себя блок управления 1, адресный блок констант 2, блок постоянной памяти 3, адресный блок 4, исходной информации входные регистры 5,6, регистр констант 7, промежуточные регистры 8-11, сумматор-вычитатель 12, умножители13-16, блок оперативной памяти 17,сумматоры-вычитатели 18, 19,20, управляющие шины 21-24, выходные регистры 25,26, управляющие шины 27-31.Граф алгоритма БПф (фиг. 2) показан для аходного массива в 32 значения, На фигуре использованы следующиеобозначения: индексы аходной последовательности 32, индексы выходной последовательности 33, операция умножения 10 на константу 34.На временной диаграмме (фиг, 3) показаньи последовательность выполненияопераций умножения на константы Юв прототипе ( 1), последовательность 15 выполнения операций умножения на Идля нечетных индексов аходной последовательности (К ), последовательностьдля четных индексов входной последовательности (Щ), участок получения окон чательного результата ( 5. ).Характерной особенностью вычисленияспектра фурье является то, что все чуные операнды исходного массива обрабатываются по алгоритму БПФ с разрежением по времени, а все нечетные по алгоритму БПф. с разрежением по частоте.Такое разбиенйе позволяет так организовать вычисление, что в процессе выполнения удается совмещать во времени определенные шаги, например, практически натом же оборудовании одновременно выполнять первые итерации для четных и нечетных операндов. Совмещение возможноввиду того, что в этом случае для одних 35 двухточечных преобразований фурье длянечетных операндов на первой, итерациине требуется операций умножения на константы, а дпя других (для четных) такаяоперация требуется, Отсюда следует, что 40 можно совместить эти итерации, изыскавдополнительный вычислительный ресурсдля выполнения удвоенного копичествасложения комплексных чисел. В предлагаемом устройстве такой ресурсудва ивается путем введения дополнительногоблока сложениявычитания, в других случаях можно обойтись одним таким блоком,разделив его ресурс во времени, что однако приведет к усложнению связей и,как следствие, к проигрышу в оборудовании. Рассмотрим работу устройства. Временная диаграмма, характеризующая по следоватепьность выполнения итераций,. показана на фиг. 3, где испопьзованы следующие обозначения; участок обработки для случая работы прототипов 1, участок обработки нечетных операндов к088 соответственно ко входам второго итретьего сумматоров-вычитателей, выходы которых подключены соответственнок первому и второму аходам первогопромежуточного регистра, выход адресного блока исходной информации подключен к первому входу блока оперативнойпамяти, первый выход которого подключен ко аходу первого входного регистра,выходы которого подключены ко аходампервого сумматора-вычитателя, перваяи вторая группы выходов которогоподключены ко вторым аходам соответственно первого, второго и третьего,четвертого умножителей, первая, втораяи третья группы выходов первого сумматора-вычитателя подключены соответственно ко входам первого и второго промежуточных регистров, выходы которыхчерез первый выходной регистр подключены ко второму аходу блока оперативной памяти, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия устройства, оно содержит второй входной регистр, третий и четвертыйпромежуточные регистры, четвертыйсумматор-вычйтатель и второй выходнойрегистр, причем второй выход блока опсративной памяти через второй входнойрегистр подключен ко аходам третьегои четвертого промежуточного регистров,первая и вторая группы выходов третьего промежуточного регистра подключены к третьим входам соответственнопервого, второго и третьего, четвертого умножителей, первая и вторая группавыходов третьего промежуточного регистра и первая группа выходов четвертогопромежуточного регистров подключенысоответственно к первой, второй и третьейгруппе входов четвертого сумматора-вычитателя, четвертая и пятая группы входов которого подключены соответственнок выходам второго и третьего сумматоров-вычитателей, выходы четвертогосумматора-вычитателя через второй выХодной регистр соединены с третьим аходом 35"блока оперативной памяти, управляющие ахо,дытретьего промежуточного регистра и ч етвертого сумматора-вычитателя подключены к соответствующим выходам блока управления. Источники информации,принятые во внимание при экспертизе 1. Лвторское свидетельство СССР Мю 421994, кл. Й 06 Р 15/34, 1974. 2, Зарубежная радиоэлектроника,1973, Ъ 2, с. 45.7 7347На вход других двух умножителей 14, 15 подаются из промежуточного регистра 10 соответственно операнды о 4 и Ь 4, с выхода умножителей результаты ЯО и 5 Ь 4 складываются и вычитаются5 на сумматоре-вычитателе 19 с разделением времени, результаты этих операций 5(04-04), б (СМЬ), совместно с операндами с выхода промежуточного регистра 11 обрабатываются на сумматоре-вычита теле 20.В рассмотренных двух вариантах раскрываются все особенности, которые встречаются в других случаях.Предлагаемое устройство БПФ обладает большим быстродействием, чем известные устройства, Так, например, в случае классического способа БПФ для исходного массива в Й комплексных чисм требуется И/2 ЬэрйьЦсек 3 для выполнения вычислений, где ас - время выполнения двухточечного БПФ. В рассматриваемом случае это время за счет совмещения операций снижается до (В 2%ор 2 й Ъ) ь 1 сек 1, откуда выигрыш 25 в процентах в быстродействии выражает ся числом 700/21 ор Й при Й 1428На фиг. 4 показан график, иллюстрирующий выигрыш для различных значений й, Как видно, он не превышает 50% для й =128 значений входного массива и ассимптотически уменьшается с увеличением й.Дпя наиболее употребительного значения Й = 1024, выигрыш составляет несколько больше 30%, что вполне оправдывает то услож-, нение устройства, которое последовало при реализации принятого алгоритма.Формула изобретенияУстройство дпя реализации быстрого40 преобразования фурье, содержащее блок управления, выходы которого соединены с управляющими аходами соответственно первого сумматора-вычитателя, первого, второго, третьего и четвертого умножи 45 телей, второго и третьего сумматороввычитатьлей, первого и второго промежуточного регистров, адресного блока констант и адресного блока исходной информации, выход адресного блока кон 50 стант через блока постоянной памяти подключен ко входу регистра констант, первая, вторая третья и четвертая группы выходов которого подключены к пер 4 55 вым входам соответственно первого, второго, третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей подключены734708 20Составитель И. ГрибковРедактор Н. Каменская ТехредН. Ковалева Корректор Ю. Макаренко Заказ 2090/52 Тираж 751 Подписное ЦНИИПИ Государственного комитета СССРпо делам изобретений и открыгий 1113035, Москва, Ж, Раушская наб., д 4/5 филиал ППП "Патент, г. Ужгород, ул, Проектная, 4