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

I

(21)4480506/24

(22)05.09,88

(46) 23.08.91. Бюл. № 31

(71)Специальное конструкторско-тех- нологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина

(72)А.Н.Карташевич, В.М.Приходько и А.А.Фомин

(53) 681.3(088.8)

(56) Авторское свидетельство СССР

Г 1056206, кл. G 06 F 15/332, 1981.

Авторское свидетельство СССР № 1164730, кл. G 06 F 15/332, 198.

(54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТ- РОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

(57) Изобретение относится к вычислительной технике и может быть испол - эовано для цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Указанная цель достигается за счет того, что устройство содержит блоки оперативной 1, 2 и постоянной 3 памяти, первый, второй коммутаторы 13, 11, счетчики 14, 15, конвейерные регистры 6, 7, сдвигающий счетчик 17, умножитель 4, блок 8 синхронизации и блок 16 элементов И, третий, четвертый коммутаторы 12, 10, накапливающий сумматор 5 и сумматор- вычитатель 9. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано для цифровой обработки сигналов. Цель изобретения - повышение быстродействия. Указанная цель достигается за счет того, что устройство содержит блоки оперативной 1, 2 и постоянной 3 памяти, первый, второй коммутаторы 13, 11, счетчики 14, 15, конвейерные регистры 6, 7, сдвигающий счетчик 17, умножитель 4, блок 8 синхронизации и блок 16 элементов И, третий, четвертый коммутаторы 12, 10, накапливающий сумматор 5 и сумматор-вычитатель 9. 2 ил.

00

с

о VJ

го

Јь О 00

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

Цель изобретения - повышение быстродействия.

На фиг.1 приведена функциональная схема устройства; на фиг. 2 - пример реализации блока синхронизации.

Устройство содержит (фиг.1) первы 1 и второй 2 блоки оперативной памяти, блок 3 постоянной памяти, умножитель 4, накапливающий сумматор 5, первый 6 и второй 7 конвейерные ре- гистры, блок 8 синхронизации, сумма- тор-вычитатель 9, четвертый 10, второй 11, третий 12 и первый 13 коммутаторы, первый 14 и второй 15 счетчики, блок 16 элементов И и сдвигаю- щий счетчик 17с

Блок синхронизации (фиг.2) содержит первый 18, второй 19 и третий 20 триггеры, генератор 21 синхроимпульсов, одноразрядный счетчик 22, двух- разрядный счетчик 23, дешифратор 28, элемент ИЛИ 24, а также первый 25, второй 26, третий 27, четвертый 29, пятый 30, шестой 31, седьмой 32, восьмой 33, девятый 34, десятый 35, одиннадцатый 36,двенадцатый 37, тринадцатый 38 и четырнадцатый 39 элементы И, первую группу Y1 выходов 40, 41, вторую группу Y2 выходов 42- 44, третью группу Y3 выходов 45-53, вход 54 запуска, вход 55 останова и вход 56 признака режима работы.

Блоки оперативной 1, 2 и постоянной 3 памяти содержат по 2N ячеек, где N - длина реализации, счетчики 14 и 15 содержат п+1 разрядов, где n , сдвигающий счетчик 17 является n-разрядным. Блок 16 И является группой из n элементов И, пер- вые входы которых соединены с п-раз- рядным выходом первого счетчика 14, вторые входы соединены с п-разрядным выходом сдвигающего счетчика 17 в двоично-инверсном порядке. На первой итерации счетчик 17 и блок 16 элементов И блокированы нулями, находящимися в счетчике 17, после первой итерации с выхода переноса второго счетчика 15 в итерационной регистр 17 вдвигается единица, вследствие чего на второй итерации с выхода блока 16 элементов И на адресный вхо 3 постоянной памяти поступает значе

Q

0

5 Q -

о 5

0

5

ние старшего разряда первого счетчика 14 и т.д.

Первый 13 и третий 12 коммутаторы представляют собой группу из n мультиплексоров на два входа, причем первый информационный вход первого мультиплексора первого коммутатора 13 соединен с выходом нулевого разряда первого счетчика 14, второй информационный вход указанного мультиплексора - с выходом первого разряда второго счетчика 15, первый информационный вход второго мультиплексора первого коммутатора 13 - с выходом первого разряда первого счетчика 14, второй информационный вход указанного коммутатора - с выходом второго разряда второго счетчика 15 и т.д., первый информационный вход n-го мультиплексора первого коммутатора 13 соединен с вькодом n-го разряда первого счетчика 14, второй информационный вход указанного мультиплексора - с выходом нулевого разряда второго счетчика 15.

Первый информационный вход первого мультиплексора третьего коммутатора 12 соединен с выходом первого разряда второго счетчика 15, второй информационный вход указанного мультиплексора - с выходом нулевого разряда первого счетчика 14, первый информационный вход второго мультиплексора третьего коммутатора 12 - с выходом второго разряда второго счетчика 15, второй информационный вход указанного мультиплексора - с выходом первого разряда первого счетчика 14 и т.д., первый информационный вход n-го мультиплексора третьего коммутатора 12 соединен с выходом нулевого разряда второго счетчика 15, второй информационный вход указанного мультиплексора - с. выходом n-го разряда первого счетчика 14.

Устройство работает следующим образом.

Информация в двоично-инверсном порядке, отдельно мнимая и действительная части, занесена во второй блок 2 оперативной памяти, первый 14 и второй 15 счетчики и сдвигающий счетчик 17 обнулены.

Выполнение итерации быстрого преобразования Фурье заключается в последовательном выполнении в устройстве операция вида B+A W, где А и В - операнды, извлекаемые из блока оператинной памяти, W - экспоненциальный множитель, извлекаемый из блока постоянной памяти. Элементарная операции БНФ осуществляется за четыре такта. В устройстве реализован конвейерный принцип обработки, т.е. данные, подготовленные за четыре такта первого этапа, заносятся в память за четыре такта второго этапа, а данные, подготовленные на втором этапе, заносятся в память на третьем этапе и т.д., причем после завершения каждой последующей итерации происходит переключение блоко,в оперативной памяти (на первой итерации информация считывается из второго блока 2 оперативной памяти, а результаты записываются в первый блок 1 оперативной памяти, на второй итерации, наоборот, считывается из первого во второй 2)

1, Заносится

Re1, + (ReA cosOJt 1 A1 s irtQt);

1 1, В +(R0A sinMt + I A CosQt).

in nn - сгтп

На выходе 42 блока 8 синхронизации формируется управляющий код, поступающий на управляющие входы первого 1 3 и третьего 12 коммутаторов, в результате чего к выходам коммутаторов подключаются их вторые информационные входы. Адреса для считывания операндов формируются на информационном выходе первого счетчика 14, адреса для записи операндов формируются на информационном выходе второго счетчика 15. При переключении блоков оперативной памяти изменяются управляющие коды на управляющих входах коммутаторов, в результате чего на адресные входы блоков оперативной памяти поступают либо адреса записи, либо считывания.

В первом такте по управляющим сигналам, поступающим с выхода 44 блока 8 синхронизации, из второго блока 2 оперативной памяти считывается действительная часть операндов Rg-A, которая через первый информационный вход коммутатора 10 заносится в регистр 6 и через второй информационный вход коммутатора 11 заносится через первый вход в умножитель 4, на второй вход которого из блока 3 постоянной памяти поступает косинусная составляющая экспоненциального множителя. Во втором такте результат умножения Re A-cosCO t с выхода умножителя 4 заносится в пред24686

варитглыш обнуленный накапливающий

сумматор 5, одновременно из второго блока 2 оперативной памяти считывает0

5

5

ся мнимая часть операнда , которая через первый информационный вход коммутатора 10,и второй информационный вход коммутатора 11 записывается через первый вход в умножитель 4, на второй вход которого из блока 3 постоянной памяти поступает синусная составляющая экспоненциального множителя.

В третьем такте результат умножения ImA-sin(Jt с выхода умножителя А заносится в накапливающий сумматор 5, вместе с этим из второго блока 2 оперативной памяти считывается действительная часть следующего операнда о е в и заносится в регистр 7. Одновременно на второй вход умножителя 4 из блока 3 постоянной памяти поступает косинусная составляющая экспоненциального множителя и происходит умножение мнимой части операнда Im A, занесенной в умножитель 4 во втором такте, на косинусную составляющую экспоненциального коэффициента

I A-cosCJt. m

В четвертом такте из регистра 7

действительная часть операнда Rg- В заносится в сумматор-вычитатель 9, и .выполняется операция сложения, затем из второго блока 2 оперативной памяти считывается мнимая часть операнда и заносится в регистр 7, вместе с тем в предварительно обнуленный накапливающий сумматор 5 заносится результат умножения I A cosCJt с выхода умножителя 4 и из регистра 6, через первый информационный вход коммутатора 11 записывается через первый вход в умножитель 4 значение действительной части операнда Rg A, на второй вход умножителя 4 поступает значение синусной составляющей экспо- .ненциального коэффициента, а также производится запись в первый блок 1 оперативной памяти действительной части первой точки Rg 1 Rg В +

0

5

0

5

0

+ (R- A-cosCOt

- ImA

sinfjt) элементарного преобразования с выхода сумматора-вычитателя 9.

На первом такте второго этапа об- работки сумматор-вычитатель 9 производит операцию вычитания между теми же операндами, и в первый блок 1 оперативной памяти заносится значение действительной части второй точки

Re2 ReB - (Rg A-coscOt -I A-sinlOt элементарного преобразования, вместе с тем в накапливающий сумматор 5 с выхода умножителя 4 записывается результат умножения Rg-A sinOQt, полученный в предыдущем такте обработки, и из второго блока 2 оперативной памяти считывается значение действительной части операнда Re А, которое заносится в регистр 6 через первый информационный вход коммутатора 10, и через второй информационный вход коммутатора 11 записывается через первый вход в умножитель 4, на второй вход которого поступает значение косинусной составляющей экспоненциального множителя из блока 3 постоянной памяти.

В следующем такте в сумматор-вы- читатель 9 из регистра 7 через первый вход заносится значение мнимой части операнда ImB, через второй вход в сумматор-вычитатель 9 заносится значение ImA-coscO inCJt с выхода накапливающего сумматора 5, затем сумматор-вычитатель 9 заполняет операцию сложения, и значение мнимой части первой точки 1,1 1 В +

+ (R- A-sinODt + I A cos COt) элееtn

ментарного преобразования заносится

в первый блок 1 оперативной памяти, а также из второго блока 2 оператив

ной памяти извлекается значение мнимой части операнда ImA и через первый информационный вход коммутатора 10 и второй информационный вхо коммутатора 11 записывается через первый вход в умножитель 4, на второй вход которого поступает синусна составляющая экспоненциального множителя из блока 3 постоянной памяти вместе с тем в предварительно обнуленный накапливающий сумматор 5 заносится результат умножения cosG полученный в предыдущем такте.

В третьем такте второго этапа элементарного преобразования из второго блока 2 оперативной памяти считывается действительная часть операда Rg В и через первый информацион- ный вход коммутатора 10 заносится в регистр 7, в накапливающий сумматор 5 с выхода умножителя 4 заносит

i ся значение I A-sinQt, полученное

т

в предыдущем такте, на второй вход умножителя 4 из блока 3 постоянной памяти поступает косинусная составляющая экспоненциальной функции

0

(в предыдущем такте через первый вход в умножитель было занесено значение ImA ), сумматор-вычитатель 9 производит операцию вычитания между операндами, занесенными в него в предыдущем такте, и в первый блок 1 оперативной памяти заносится значение мнимой части второй точки элементарного преобразования Im2 I ,„ В |т)- х m ,А cos63t).

5

0

5

0

5

0

ходит

-(Re A sincot + 1,

В четвертом такте в сумматор-вы- читатель 9 через его первый вход из регистра 7 заносится значение R Вг, через второй вход в сумматор-вычитатель 9 заносится содержимое накапливающего сумматора 5, сумматор-вычитатель производит операцию сложения и в первый блок 1 оперативной памяти, записывается значение действительной части Rg1 R е В + (R A cosCO t -IMA sintoO затем из второго блока 2 оперативной памяти считывается значение мнимой части операнда ImB и через первый вход коммутатора 10 заносится в регистр 7, с выхода умножителя 4 значение I A cosCJt, полученное в предыдущем такте, заносится в накапливающий сумматор 5. Из регистра 6 через первый информационный вход коммутатора 11 через первый вход умножителя 4 заносится значение действительной части Rg A

0

5

операнда,

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

После считывания из второго блока 2 оперативной памяти значений действительной н мнимой частей последней пары точек первой итерации и их обработки в течение четырех тактов происзапись результатов в первый блок 2 оперативной памяти, затем по сигналам, поступающим с выходов 43 и 44 блока 8 синхронизации, происходит переключение блоков оперативной памяти, первый 1 - для чтения, второй 2 - для записи. Импульс, поступающий с выхода переноса второго счетчика 15, поступает на вход сдвигающего счетчика 17, что приводит к тому, что его содержимое сдвигается на один разряд вправо, а младший разряд заполняется единицей. Преобразованный код с информационного выхода счетчика 17 поступает на второй вход блока 16 эле10

20

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

Блок 8 синхронизации работает следующим образом. Приходящий на вход 54 блока 8 синхронизации пусковой импульс устанавливает первый триггер 18 и через элемент 1ШИ 24 второй триггер 19. Уровень логической единицы с выхода первого триггера 18 поступает на управляющий вход генератора 21 синхроимпульсов и разрешает его работу, уровень логической единицы с выхода второго триггера 19 открывает элемент И 33, через первый вход которого с первого выхода генератора 21 синхроимпульсов поступают тактовые импульсы на выход 41 блока синхронизации, уровень логической единицы с выхода второго триггера 19 сбрасывает третий триг гер 20, С третьего выхода генератора 21 синхрона- 25 пульсов тактовые импульсы поступают на вход двухразрядного счетчика 23, с четвертого выхода генератора импульсы поступают на входы элемента И

На первом и втором выходах цвух,- разрядного счетчика 23 последовательно формируются коды соответствующих тактов. На первом такте уровень логического нуля с первого выхода счетчика 23 поступает на второй инверсный вход элемента И 30, на первый инверсный вход которого поступает уровень логического нуля с второго выхода счетчика 23, в результате чего тактовый импульс с четвертого выхода генератора 21 синхроимпульсов проходит на выход 46 блока синхронизации. На выходе элемента И 38 формируется уровень логической единицы, который поступает на первый вход элемента И 39, на второк вход которого поступают тактовые импульсы с четвертого выхода генератора 21, в результате чего на выходе 53 блока синхронизации формируется импульс записи в умножитель 4.

Затем двухразрядныи счетчик 23 переходит в следующее состояние. Во время второго такта уровень логичеспамяти (, выпор cos /sin) и накакпиваю- nier э сумматора 5 (г чсжен не /вычитание) и на первые нходы эмементон И 34, 35, на вторые входы которых росгупают синхроимпульсы с пятого выхода генератора 21 синхроимпульсов, г выхода элемента И 34 на выхог 48 блока синхронизации поступает импульсы записи в сумматор-вычитатечь 9, с выхода элемента И 35 - импульсы обнуления накапливающего :умматора 5. Уровень логической единицы с инверсного выхода третьего триггера 20 поступает на вход одноразрядного счетчика 22, а также па второй вход элемента И 26, на второй вход которого поступает уровень логического нуш с инверсного выхода второго триггера i9, в результате чего отпирается элемеп И 25 и через его втором вход на выход 51 блока сиьхроннзтции начинают поступат импульсы записи в накапливающий сум- .штор 5.

Во время третьего такта уровень погическон единицы с второго выхода двухразрядного счетчика 23 открывает элемент И 31, через который тактовые импульсы с четвертого выхода генератора 21 синхроимпульсов пос гупают через выход 47 блока синхронизации на вход записи регистра 7. Этот же уровень логической единицы устанавливает третий триггер 20. вровень логического i уля на первом выходе двухразрядного счетчика 23 закрывает эпемен - И 38, уровень лопгчссксю нуля с выхода этого элемента блокирует прохождение синхроимпульсов через элемент И 39 на выход 53.

Во время четвертого такта уровень логического нуля с инверсного выхода триггера 20 открывает элемент И 32, в результате чего чер. . выход 40 блока синхронизации проходят синхроимпульсы с первого BMXOJ., i генератора 21 синхроимпульсов.

На первых трех тактах элемент И 36 блокирован уровнем логического нуля с выход третьего триггера 20, на четвертом такте уровень логической едлпицы с выхода указанного триггера отпирает элемент И 36, который в свою очередь открывает элемент И 27, С выхода которого синхроимпульсы, по30

35

40

45

50

кой единицы с первого выхода двухраз- i5 ступающие на его второй вход с второрядного счетчика 23 поступает через второй выход блока синхронизации на управляющие входы блока 3 постоянной

10

20

25

т67246810

памяти (, выпор cos /sin) и накакпиваю- nier э сумматора 5 (г чсжен не /вычитание) и на первые нходы эмементон И 34, 35, на вторые входы которых росгупают синхроимпульсы с пятого выхода генератора 21 синхроимпульсов, г выхода элемента И 34 на выхог 48 блока синхронизации поступает импульсы записи в сумматор-вычитатечь 9, с выхода элемента И 35 - импульсы обнуления накапливающего :умматора 5. Уровень логической единицы с инверсного выхода третьего триггера 20 поступает на вход одноразрядного счетчика 22, а также па второй вход элемента И 26, на второй вход которого поступает уровень логического нуш с инверсного выхода второго триггера i9, в результате чего отпирается элемеп И 25 и через его втором вход на выход 51 блока сиьхроннзтции начинают поступать импульсы записи в накапливающий сум- .штор 5.

Во время третьего такта уровень погическон единицы с второго выхода двухразрядного счетчика 23 открывает элемент И 31, через который тактовые импульсы с четвертого выхода генератора 21 синхроимпульсов пос гупают через выход 47 блока синхронизации на вход записи регистра 7. Этот же уровень логической единицы устанавливает третий триггер 20. вровень логического i уля на первом выходе двухразрядного счетчика 23 закрывает эпемен - И 38, уровень лопгчссксю нуля с выхода этого элемента блокирует прохождение синхроимпульсов через элемент И 39 на выход 53.

Во время четвертого такта уровень логического нуля с инверсного выхода триггера 20 открывает элемент И 32, в результате чего чер. . выход 40 блока синхронизации проходят синхроимпульсы с первого BMXOJ., i генератора 21 синхроимпульсов.

На первых трех тактах элемент И 36 блокирован уровнем логического нуля с выход третьего триггера 20, на четвертом такте уровень логической едлпицы с выхода указанного триггера отпирает элемент И 36, который в свою очередь открывает элемент И 27, С выхода которого синхроимпульсы, по30

35

40

45

50

- i5 ступающие на его второй вход с второго выхода генератора 21 синхроимпульсов, поступают на вход дешифратора 28, с первого либо второго выхода которого через выходы 43 и 44 блока синхронизации импульсы записи поступают на первый 1 либо второй 2 блоки оперативной памяти. Выбор блоков опера- тивной памяти осуществляется по импульсам, поступающим с выхода одноразрядного счетчика 22. Эти же импульсы через выход 42 блока синхронизации поступают на управляющие вхо- ды первого 10, третьего 12 и четвертого 13 коммутаторов. На четвертом такте импульс с выхода элемента И 29 через выход 50 блока синхронизации поступает на управляющий вход второ- го коммутатора 11.

До конца одной итерации блок синхронизации работает аналогично. В конце итерации импульс, поступающий на вход 56 блока синхронизации, сбрасывает второй триггер 19, уровень логического нуля с выхода второго триггера 20 блокирует прохождение тактовых импульсов с первого выхода генератора 21 синхроимпульсов через элемент И 33 на выход 41 блока синхронизации. Затем в течение четырех тактов на соответствующем выходе блока синхронизации формируются импульсы записи в блок оперативной па- мяти. Уровень логической единицы с инверсного выхода второго триггера 19 поступает на вход элемента И 26, с выхода которого уровень логической единицы поступает через элемент ИЛИ Г 4 на вход второго триггера и устанавливает его, уровень логической единицы с выхода второго триггера 19 поступает на вход третьего триггера 20 и сбрасывает его, уро- вень логической единицы с инверсного выхода третьего триггера 20 поступает на вход одноразрядного счетчика 22 и пег еводит его в следующее состояние,

Уровень логической единицы с выхода счетчика 22 поступает на управляющий вход дешифратора 28, в результате чего второй его выход подключается к входу. Этот же импульс поступает нд выход 42 блока синхронизации в Результате чего происходит переключение блоков оперативной памяти. Если на первой итерации .информация считывалась из второго блока оперативной памяти, а запись производилась в первый блок, то на второй итерации информация СЧИТЫВЭРТСЯ из первого блока, а запись происходит во второй блок оперативной памяти.

В дальнейшем блок синхронизации работает аналогично описанному.

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

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

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

Q 5

0

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

40