Устройство для реализации быстрого преобразования фурье Советский патент 1980 года по МПК G06F17/14 

1

Изобретение относится к области вьгаиспитепьной техники и может быть использовано в системах, и устройствах цифровой обработки информации в качестве преобразователей временной П(ХМ1едоватеЛьности отсчетов входного сигнала в частотную последовательность и наоборот.

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

Наиболее близким по тахнической реализации и по выполняемым функциям к данному изобретению является устройство для реализации быстрого преобразования Фурье, содержащее блок управления, выходы которого соединены с управляк шими входами соответственно первого сумматора-вычитателя, первого, второго, третьего и четвертого умножителей, второго и третьего сумматоров-вьнитат-елей, первого и второго промежуточного регистров, адресного блока констант и адресно.го блока исходной информации, выход адресного блока констант через блок постоянной памяти подключен ко входу регистра констант, первая, вторая, третья и четвертая группы выходов которого подключены к первым аходам соответственно первогоа третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей под10ключены соответственно ко входам второго и третьего сумматоров-вычитателей, .выходы которых подключены соответстве но к первому и второму входам первого промежуточного регистра, выход адресно15го блока исходной информации подключен к первому входу блока оперативной памяти, первьй выход которого подключен ко входу первого входного регистра, выходы подключены ко входам первого сумматогора-вычитателя, первая и вторая группы выходов которого подключены ко вторым входам соответственно первого, второго и третьего, четвертого умножитепай, первая, вторая и третья группы выходов первого сумматора-вычитателя подключены соответственно ко аходам первого и второго промежуточных регистров, выходы которых через первый выходной регистр подключены ко второму входу блока оперативной памяти LSQ.

Недостатком этого устройства является низкое быстродействие. Целью изобретения является повышение Ю быстродействия,. Цель достигается тем, что- предлагаемое устройство содержит второй входной регистр, третий и четвертьй промежуточ ные регистры, четвертый сумматор-вычитатель и второй выходной регистр, ,-1 причем второй выход блока оперативной памяти через второй входной регистр подключен ко входам третьего и четвертого промежуточного регистров, первая и вторая группы выходов третьего промежуточного регистра подключены к третьим аходам соответственно первого, второго и третьего, четвертого умножителей, первая и вторая группы выходов третьего промежуточного регистра и пер вая группа выходов четвертого промежуточного регистров подключены соответственно к первой, второй и третьей группе входов четвертого сумматоравыч|{тателя, четвертая и пятая группа входов которого подключены соответственно к выходам второго и третьего сумматоров-вычитат елей, выходы четвер того сумматора-вычитателя через второ выходной регистр соединены с третьим входом блока оперативной памяти, управ ляющие входы третьего промежуточного регистра и четвертого сумматора-вычитатапя -подключены к соответствующим выходам блока управления. На фиг. 1 представлена структурная схема предлагаемого усТройства1 на фиг. 2 - граф, алгоритма быстрого преобразования Фурье, (БПФ) реализованный в устройстве; на фкг 3 - временные диаграммы работы устройства; на фиг, 4 - график, показьшаюишй процент вьшграша в быстродействии устройства для массивов различной длины. Схема устройства включает в себя блок управления 1, адресный блок констант 2, блок постоянной памяти 3, адресный бвок 4, исходной информации входные регистры S,6, регистр констан 7, промежуточные регистры 8-11, сум матор-вычитатель 12, умножители 13-16, блок оперативной памяти 17,

сумматоры-вычитатели 18,19,20, управляющие шины 21-24, выходные регистры 25,26, управляющие щины 27-31,

Граф алгоритма БПФ (фиг. 2) показан для входного массива в 32 значения. На фигуре использованы следующие обозначения: индексы входной последовательности 32, индексы выходной последовательности 33, операция умножения на константу 34, На временной диаграмме (фиг, 3) показаньс последовательность выполнения операций умножения на константы W в прототипе (I), последовательность выполнения операций умножения на W для нечетных индексов входной последовательности (IT), последовательность для четных индексов входной последовательности (ТВ) участок получения окон-чательного результата ( Ш ) Характерной особенностью вычисления спектра Фурье является то, что все чет ные операнды исходного массива обрабатываются по алгоритму БПФ с разреж-ением по времени, а все нечетные по алгоритму БПФ с разрежением по частоте. Такое разбиение позволяет так организовать вычисление, что в процессе выполнения удается совмещать во времени определенные шаги, например, практически на том же. оборудовании одновременно выполнять первые итерации для четных и не- . четных операндов. Совмещение возможно ввиду того, что в этом случае для одних двухточечных преобразований Фурье для нечетных операндов на первой ..итерации не требуется операций умножения на константы, а для других (для четных) такая операция требуется. Отсюда следует, что можно совместить эти итерации, изыскав дополнительный вычислительный ресурс для выполнения удвоенного количества сложения комплексных чисел, В предлагаемом устройстве такой ресурс Лудваивается путем введения дополнительного блока сложения-вычитания, в другах случаях можно обойтись одним таким блоком, разделив его ресурс во времени, что однако приведет к усложнению связей и, как следствие, к проигрышу в оборудовании. Рассмотрим работу устройства. Временная диаграмма, характеризующая последовательность выполнения итераций,, показана на фиг, 3, где использованы следующие обозначения; участок обработки для случая работы прртотипов I, участок обработки нечетных операндов Ж , участок обработки четных, операндов 13 участок обработки всах операндов {V , На фиг. 3 для примера приведены нек торые показатр-пи степени констант, ис зуемых, на различных этапах, при этом константы имеют следующий вид , Z.O&-1, I Г7 i- ЬА, Как видно из фиг, 3, при обработке одновременно как четных так и нечетны значений исходных операндов необходим совмещать операции в арифметическом устройств е, В частности допясны быть обеспечены следующие варианты опера- ций: (1) а/а(ь 4ЬЛ (o -cxJ-c-Cb,,-b;)SV.t(a,,) с (2)o,-(a;c-b.s)b(a.s.) «1- ( -. IV ( Ь.СП (3) ) .) (4) а 4a-kiCb5 4b,) VbJ(( (5)o,-b,/(b.a,) ,) (6)(a(,) Sta,,- s (b,- bJ t s(a a;) t i СЬг- b,-)l (7)a,iS(a,-):C4tS(,)-i cx,,tS(o,-b,)V, sCa,. b.l. В процессе вычисления могут встречться различные ситуации совмещения одной из операций (1), (2) с операциями (3) - (5), а также совмещение раз. личных вариантов операций (6) и (7) между собой. Для примера, иллюстрирующего работу устройства, рассмотрим два варианта совмещения операций, первый вариант: совмещаются операции (1) и (S), второй вариант : совмещаются операции (6 и (7). Первый вариант. Обозначим операнды для первой совмещаемой операции, как oi.-.b jOi, , оставив без изменения обозначения второй совмещаемой операции. По адресам, вырабатьшаемым бпоком 4, выбираются из блока оперативно памят11 17 соответственно операнды Ьд и с -v Ьд , которые затем заносятся в промежуточные регистры 8, 1О, Далее выбираются аналогично операнды и а,4 ib; и заносятся соответственно в промож точные регистры 9, 11, По ши11е 28 блок сложениявычитания устанавливается на выполнении первой части операции 1, по шине 31, второй блок сложення-вычитания устанавливается на всю операцию (5). После этого в блоке 12 выпол 1яются операции (5 «j), (b b ,( (- в блоке 20 ((а ь,), , (,} . Часть результата операции блока 12, а i именно; () ДЬд,-1) i) поступает на умножители; 13-15, на другие входы которых поступает константа из регистра 7, куда она принимается пз блока постоянной памяти 3 по адресу, вырабатываемому адресным блоком констант 2, Результаты умножения:(5j--oi c,( складьшаются и вычитаются на суммматорах-вьиитателях 18, 19, которые устанавливаются на необ.ходимую операцию по шинам 29, ЗО. Результат последних операций принимается на промежуточный регистр 9, которьй принимает операнды по входам, указанным в сигнале, передаваемом по щине 21. Результаты, полученные в блоках 12, 20, попадая во кходные регистры 25, 26, они записьшаются по адресу, вырабатываемому адресным блоком данных 4, в блок оперативной памяти 17. Второй вариант. После того как исходная информация записана в промежуточные регистры 8-11, по шинам 28, 31, 29, 30 поступают сигналы, настраиваю- щие сумматорьг-вычитатели 12,20,18,19 на необ.ходимые операции, по шинам 27 и 21 поступают сигналы, указывающие промежуточным регистрам 10, 9 соответственно, куда выдать и откуда принять информацию. Далее в блоке 12 проводятся следую- вычисления: (), ( , (Oj-Oi) (bj-b ) , результаты {О4.) и ( передаются в промежуточный регистр 8, результаты .( ) и (Ьг-Ь передаются в умножители 13 к 15. С выхода этих умножителей результаты о () 5 (b,f Ь) подаются на сумматор-вычитатель 18, где с разделением времени, последовательно Ьбразуются: 6 (aQ.-a)S(b,i-b), S{aj-a,)-v S (bj-Ь; ), которые аписываются в промежуточньй регистр 9, Так как у умножителей, кроме входа константы имеется два ахода операндов, то по шине 22 передается сигнал, который предписывает умножителям с каждого ахода необходимо ваять информадию. На аход других двух умножителей 14, 15 подаются из промежуточного регистра 1О соответственно операнды и Ь; , с выхода умножителей результат So( и Sb,( складываются и вычитаются на сумматоре-вычитателе 19 с раздел-ени ем времени, результаты этих операций 3(,), S ) совместно с .операндами с вькода промежуточного регистра 11 обрабатываются на сумматоре-вычита теле 2О. В рассмотренных двух вариантах раскрываются все особеннос.ги, которые встречаются в других случаях. Предлагаемое устройство БПФ обладает большим быстродействием чем известные устройства. Так, например, в случае классического cnfjco6a БПФ для исходного массива в N комплексньк чисел требуется N/aCog- NAttceKi для выполнения вычислений, где At - время выполнения двухточечного БПФ, В рассматриваемом случае это время за счет совмещения операций снижается до (4/г%38-2Н-)д Ссекз , откуда выигрыш в процентах в быстродействии выражается числом 7oo/2eog ti при На фиг. 4 показан график, иллюстрирующий выигрыш для различных значений Н . Как видно, он не превышает 5О% для Н 128 значений входного массива и вссимптотически. уменьшается с увеличением (Ч. - Для наибоп.ее употребительного значения Н 1О24, вьшгрыш составляет несколько больше ЗО%, что вполне оправдывает то усяожнение устройства, которое последовало при реализации принятого алгоритма. Формула изобретени Устройство для реализации бьютрого преобразования Фурье, содержащее блок управления, выходы которого соединены с управляющими входами Соответст1&ённо первого сумматора-вычитателя, первого, второго, третьего и четвертого умножителей, второго и третьего сумматороввьиитат яей, первого и второго промежуточного регистров, адресного блока констант и адресного блока исходной информации, выход адресного блока констант через блока постоянной памяти подключен ко входу регистра констант, первая, вторая третья и четвертая группы выходов которого подключены к первым входам соответственно первого, вто рого, третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей подключены 7 88 соответственно ко входам второго и третьего сумматоров-вычитателей, вькоды которых подключены соответственно к первому и второму входам первого промежуточного регистра, выход адресного блока исходной информации подключен к первому В.ХОДУ блока оперативной памяти, первый выход которого подключен ко нходу первого нходного регистра, выходы которого подключены ко входам первого сумматора-вычитателя, первая и вторая группы выходов которого подключены ко вторым аходам соот&етственно первого, второго и третьего, четвертого умножителей, первая, вторая и третья группы выходов первого сумматора-вычитателя подключены соответст венно ко входам первого и второго промежуточных регистров, выходы которьЬс через первый выходной регистр подключены ко второму аходу блока оперативной памяти, отличающееся тем, что, с целью повышения быстродействия устройства, оно содержит второй входной регистр, третий и четвертый промежуточные регистры, четвертый сумматор-вычитатель и второй выходной регистр, причем второй выход блока оперативной памяти через второй входной регистр подключен ко нходам третьего и четвертого промежуточного регистров, первая и вторая группы выходов трэть его промежуточного регистра подключены к третьим входам соответственно первого, второго и третьего, четверто- го умножителей, первая и вторая группа выходов третьего промежуточного, регистра и первая группа выходов четвертого промежуточного регистров подключены соответственно к первой, второй и третьей группе входов четвертого сумматора-вычитатеяя, четвертая и пятая группы вхо- дов которого подключены соответственно к вьссодам второго и третьего сумматоров-вычнтаталвй, выходы четвертого сумматора-вычитателя через второй вы.хйдной регистр соединеныс третьим входом блока оперативной памяти, управляющие в.хо- .ды ретьего промежуточного регистра и четвертого сумматора-вычитат ел я подключены к соответствующим выходам блока управления. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 421994, кл, Q 06 F 15/34, 1974. 2.Зарубежная радиоэлектроника, 1973, № 2, с. 45.

т 6 011S2 It08

Фиг.З

ucflo дВу)( П P

700

20

I

о

16 32 6 Ш 256 5П 1024 тб д1Э2

-чх.

-о-

N

ФигЛ