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

 

АНИЕ

ТЕН ИЯ

ВИДЕТЕЛЬСТВУ

„„7347ОВ. свид-ву

21) 2530580/18-24 (51) М. Кд.

G 06 F 15/34,80. Бюллетень М 18 (53) УДК 681 327 (088.8) описания 20,05. 80 (72) Автор изобретения

И. Г. Грибков (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

Наиболее близким по технической реализации и по выполняемым функциям к данному изобретению является устройся во для реализации быстрого преобразования Фурье, содержащее блок управления, выходы которого соединены с управлжошими входами соответственно первого сумматора-вычитателя, первого, второго, третьего и четвертого умножителей, второго и третьего сумматоров-вычитат елей, первого и второго промежуточного регист2 ров, адресного блока констант и адресного блока исходной информации, выход адресного блока констант через блок постоянной памяти подключен ко входу реГистра констант BBpBGsl BTopGH TpBTbB и четвертая группы выходов которого подключены к первым входам соответственно первого, третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей подключены соответственно ко входам второго и третьего сумматоров-вычитатепей, выходы которых подключены соответственно к первому и второму входам первого промежуточного регистра, выход адресного блока исходной информации подключен к первому входу блока оперативной памяти, первый выход которого подключен ко входу первого входного регистра, выходы которого подключены ко входам первого сумматора»вычитатепя, первая и вторая группы выходов которого подключены ко вторым входам соответственно первого, второго и третьего, четвертого умножителей, пер4708

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) показаньи последовательность выполнения операций умножения на константы W в прототипе (1), последовательность

15 выполнения операций умножения на И для нечетных индексов входной последовательности (IL ), последовательностьдля четных индексов входной последовательности (Щ), участок получения окон20 чательного результата (ф ).

Характерной особенностью вычисления спектра Фурье является то, что все чу ные операнды исходного массива обрабатываются по алгоритму БПФ с разрежением по времени, а все нечетные по алгоритму БПФ с разрежением по частоте.

Такое разбиенйе позволяет так организовать вычисление, что в процессе выполнения удается совмещать во времени определенные шаги, например, практически на том же оборудовании одновременно выполнять первые итерации для четных и нечетных операндов. Совмещение возможно ввиду того, что в этом случае для одних

З5 двухточечных преобразований Фурье для нечетных операндов на первой, итерации не требуется операций умножения на константы, а дпя других (для четных) такая операция требуется, Отсюда следует, что

4О можно совместить эти итерации, изыскав дополнительный вычислительный ресурс для выполнения удвоенного копичества сложения комплексных чисел. В предлагаемом устройстве такой ресурс,,удва45 ивается путем введения дополнительного блока сложения«вычитания, в других случаях можно обойтись одним таким блоком, разделив его ресурс во времени, что однако приведет к усложнению связей и, как следствие, к проигрышу в оборудовании.

Рассмотрим работу устройства. Временная диаграмма, характеризующая по следоватепьность выполнения итераций,. показана на фиг. 3, где использованы следующие обозначения: участок обработки для случая работы прототипов 1, участок обработки нечетных операндов к

5 734708 участок обработки четных операндов И, с участок обрабогки всех операндов (7 . P

На фиг. 3 для примера приведены некоторые показатели степени констант, исполь-, я зуемых на различных этапах, при этом конста|ггы имеют следующий вид У /м = exp(- — )=(exp(i — ц, 4 : =о,— -4

N в о

Как видно из фиг. 3, при обработке одновременно как четных так и нечетных

% и значений исходных операндов необходимо совмещать операции в арифметическом устройстве. B частности должны быть то обеспечены следующие варианты опера-

15 7у ций: (1) о„ а +1(b Ü ) (а -a„).с-(Ь, - b„)S+i((a -а„ в+(Ь-Ь„ ) с) (2) а+(а с-Ь„ ) i<,(сх s b.с)) а -(а„с-b„S)v i(4 -(o„5 4„ñ

2О Ра (3) а +a„+i(b ab„) (4) о 2 а„ (Ь2 b„)

b4Ь"+1(О О ) ре (5) О2-Ь1+ (Ь2+а ) а Ь, 1(O,-,) (6) О2+О4 !(Ь + b„)

Ы,- а„ -,s(b,— Ь„),1(Ь(а, 0 1 ъ (ь -ь„д (7) с4 5(Q Ь„ )q ((b + (а b д

<х 9(О -bÄ)+it(b 5(а Ь Я

В процессе вычисления могут встречться различные ситуации совмещения одной из операций (1), (2) с операциями (3) — (5), а также совмещение раз,личных вариантов операций (6) и (7) между собой.

Л,пя примера, иллюстрирующего ра6оту устройства, рассмотрим два варианта совмещения операций, первый вариант: совмещаются операции (1) и (5), второй вариант: совмещаются операции (6) и (7).

Первый вариант. Обозначим операнды для первой совмешаемой операции, как

О, + >bÄ,О a Ü2, оставив беэ изменения обозначения второй совмещаемой операции. По адресам, вырабатываемым блэком 4, выбираются из блока оперативной памяти 17 соответственно операнды с „+ i b„u cx + 1 Ь,, которые затем" заносятся в промежуточные регистры 8, 10, Далее выбираются аналогично операнды о >b и и + jb и заносятся

6 оотвггственно в промежуточные рогисты 9, 11. По шине 28 блок сложенияычитания устанавливается на выполне и первой части операции 1, по шине

1, второй блок сложения-вычитания станавливается на всю операцию (5). осле этого в блоке 12 выполняются

nePauv.H (a„ ) (b„+b ) (52-„),(62-Ь„Д, блоке 20 (С, -b„) (a i b, (Ь cx„) (Ь -а„ ) . асть результата операции блока 12, а i менно: Д2- Од > (bg- b ) поступает на множит ".и 13-15, на другие Bxîäû корых поступает константа из регистра куда она принимается из блока посянной памяти 3 по адресу, вырабатыемому адресным блоком констант 2. езультаты умножения:(а -о<„ С,(,Ь -b„)S кладываются и вычитаются на суммматох-вычитателях 18, 19, которые устаавливаются на необходимую операцию шинам 29, 30. Результат последних ераций принимается на проллежуточный гистр 9, который принимает операнды

25 по входам, указанным в сигнале, передаваемом по шине 21, Результаты, полученные в блоках 12, 20, попадая во входные регистры 25, 26, они записываются по адресу, выразо батываел1ол у адресным блоком данных 4, в блок оперативной памяти 17.

Второй вариант. После того как исходная информация записана в промежуточные регистры 8-11, по шинам 28, 31, 35 29, 30 поступают сигналы, настраиваюшие сумматоры-вычитатели 12,20, 18, 19 на необходимые операции, по шинам 27 и

21 поступают сигналы, указывающие промежуточным регистрам 10, 9 соответст4о венно, куда выдать и откуда принять информацию.

Далее в блоке 12 проводятся следующие вычисления: {52+a„), (ь2 4 ), (5 -о) (b2-t „) результаты (aa„) и (b>+c>g

45 передаются в промежуточный регйстр 8, результаты . (а2-О4 ) и (62- ь4 ) передаются в умножители 13 и 15. С выхода этих умножителей результаты -"з (52 - Î „)

S (b2-b ) подаются на сумматор-вычитатель 18, где с разделением времени, последовательно образуются: S (o2-a„)-Ь(Ь -bÄ), S(a2-5,) S (b2- Ь ), которые записываются в промежуточный регистр 9.

Так как у умножителей, кроме входа константы имеется два входа операндов, то по шине 22 передается сигнал, который предписывает умножителялт с каждого входа необходимо взять информацию.

7 7347

На вход других двух умножителей

1Я, 15 подаются из промежуточного регистра 10 соответственно операнды с 4 и 44 с выхода умножителей результаты

Scx и Ь4 складываются и вычитаются

5 на сумматоре-вычитателе 19 с разделением времени, результаты этих операций

5(04-04}, 8 (с Ь„), совместно с операндами с выхода промежуточного регистра

11 обрабатываются на сумматоре-вычита- 10 теле 20.

В рассмотренных двух вариантах раскрываются все особенности, которые встречаются в других случаях.

Предлагаемое устройство БПФ обладает большим быстродействием, чем известные устройства. Так, например, в случае классического способа БПФ для исходного массива в N комплексных чисел требуется N/21î NëÌñeêÇ для выполнения вычислений, где д с — время выполнения двухточечного БПФ. В рассматриваемом случаэ это время за счет совмещения операций снижается до (+2Qog2) ) t peewg откуда выигрыш в процентах в быстродействии выражает ся числом 7OO/29og Й при Й>428

На фиг. 4 показан график, иллюстрирующий выигрыш для различных значений и . Как видно, он не превышает

50% для N =128 значений входного массива и ассимптотически. уменьшается с увеличением N. Дпя наиболее . употребительного значения М = 1024, выигрыш составляет несколько больше

30%, что вполне оправдывает то усложmense устройства, которое последовало при реализации принятого алгоритма.

Формула изобретения.

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

40 преобразования Фурье, содержащее блок управления, выходы которого соединены с управляющими аходами соответственно первого сумматора-вычитателя, первого, второго, третьего и четвертого умножи45 телей, второго и третьего сумматороввычитателей, первого и второго промежуточного регистров, адресного блока констант и адресного блока исходной информации, выход адресного блока кон50 стант через блока постоянной памяти подключен ко входу регистра констант, первая, вторая третья и четвертая группы выходов которого подключены к перC 55 вым входам соответственно первого, второго, третьего и четвертого умножителей, выходы первого, третьего и второго, четвертого умножителей подключены

08 8 соответственно ко входам второго и третьего сумматоров-вычитателей, выходы которых подключены соответственно к первому и второму аходам первого промежуточного регистра, выход адресного блока исходной информации подключен к первому входу блока оперативной памяти, первый выход которого подключен ко аходу первого входного регистра, выходы которого подключены ко аходам первого сумматора-вычитателя, первая и вторая группы выходов которого подключены ко вторым аходам соответственно первого, второго и третьего, четвертого умножителей, первая, вторая и третья группы выходов первого сумматора-вычитателя подключены соответственно ко входам первого и второго промежуточных регистров, выходы которых через первый выходной регистр подклю» чены ко второму аходу блока оперативной памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, оно содержит второй входной регистр, третий и четвертый промежуточные регистры, четвертый сумматор-вычйтатель и второй выходной регистр, причем второй выход блока опсративной памяти через второй входной регистр подключен ко аходам третьего и четвертого промежуточного регистров, первая и вторая группы выходов трэтьего промежуточного регистра подключены к третьим входам соответственно первого, второго и третьего, четверто- . го умножителей, первая и вторая группа выходов третьего промежуточного регистра и первая группа выходов четвертого промежуточного регистров подключены соответственно к первой, второй и третьей группе входов четвертого сумматора-вычитателя, четвертая и пятая группы вхо» дов которого подключены соответственно к выходам второго и третьего сумматоров-вычитателей, выходы четвертого сумматора-вычитателя через второй выходной регистр соединены с третьим аходом

" блока оперативной памяти, управляющие ахо,дытретьего промежуточного регистра и ч етвертого сумматора-вычитателя подключены к соответствующим выходам блока управления.

Источники информации, принятые во внимание при экспертизе

l, Авторское свидетельство СССР

34 421 994й кл Й 06 F 15/34ç 1974.

2. Зарубежная радиоэлектроника, 1973, ¹ 2, с. 4-5.

734708

Составитель И. Грибков

Редактор Н. Каменская Техред Н. Ковалеве. Корректор Ю. Макаренко

Заказ 2090/52 Тираж 751 Подписное

UHHHIIH Государственного комитета СССР по делам изобретений и открыгий

1113035, Москва, Ж-35, Раушская наб., pa 4/5

Филиал ППП "Патент, r..Óæãîðoä, ул Проектная, 4