Процессор быстрого преобразования фурье

 

Изобретение относится к вычислительной технике, предназначено для вычисления спектров сигналов по алгоритму быстрого преобразования Фурье с выполнением контрольных функций и может быть использовано в анализаторах спектра, работающих в реальном масштабе времени, в геологии, медицине , радиолокации. Цель изобретения - повышение достоверности результатов вычислений. Поставленная цель достигается тем, что в состав процессора входят генератор тактовых импульсов , счетчик, счетчик итераций, формирователь адреса, дешифратор, два мультиплексора, блок буферной памяти, блок памяти, регистр адреса, арифметический блок, четыре регистра, два регистра результата, умножитель, сумматор , элемент ИЛИ, триггер, группа регистров, регистр коэффициента, блок постоянной памяти микрокоманд, блок постоянной памяти коэффициентов с соответствующими связями. 2 ил. с $ а с ГС ел 4ik СЛ С ф

СОЮЗ СОВЕТСНИХ

СО1ЩИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51) 4 С 06 F 15 332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

° )(1

° ВВ

ГОСУДАРСТВЕННЫЙ НОМИТ Т СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ б (21) 3849938/24-24 (22) 24.01. 85 (46) 30.08.86. Бюл. Р 32 (71) Киевский ордена Ленина политехнический институт имени 50-летия Великой Октябрьской социалистической революции (72) Ю.С.Каневский, Н.Е.Куц, Л.M.Ëîгинова, Б.А.Некрасов и А.Л.Третьяк (53) 681.32(088.8) (56) Авторское свидетельство СССР

В 1092517, кл. С 06 F 15/332, 1983.

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

Н 1095188, кл. С 06 F 15/332, 1983. (54) ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике, предназначено для вычисления спектров сигналов по алгоритму быстрого преобразования Фурье

„„SU„, 1254506 с выполнением контрольных функций и может быть использовано в анализаторах спектра, работающих в реальном масштабе времени, в геологии, медицине, радиолокации. Цель изобретения — повышение достоверности результатов вычислений. Поставленная цель достигается тем, что в состав процессора входят генератор тактовых импуль сов, счетчик, счетчик итераций, формирователь адреса, дешифратор, два мультиплексора, блок буферной памяти, блок памяти, регистр адреса, арифметический блок, четыре регистра, два регистра результата, умножитель, сумматор, элемент ИЛИ, триггер, группа регистров, регистр коэффициента, блок постоянной памяти микрокоманд, блок постоянной памяти коэффициентов с соответствующими связями. 2 ил.

1254506

1

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

Цель изобретения — повышение дос- !О товерности результатов.

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

Процессор содержит блок 1 вычисления скользящего спектра, состоящий из блока 2 буферной памяти, мультиплексора 3, арифметического блока 4, блока 5 памяти и блока 6 синхронизации, выполненного в виде генератора 20

7 тактовых импульсов, счетчика 8, формирователя 9 адреса, мультиплексора 10, счетчика 11 итераций, дешифратора 12 и регистра 13 адреса, бло-. ки постоянной памяти микракаманд 25

14.1 и тсоэффициентав 14.2, регистры

15.1, 15 ° 2, 16. 1, 16.2, 17 и 18, умножитель 19, выходы 20..1, 20.2, 21, 22.1, 22.2, 23.1, 23.2, 24, 25 и

26 блоков 14.1 и 14.2, сумматор 27, группа регистров 28.1-?8.п, элемент

ИЛИ 29, триггер 30, выходы 31.1 — 31.п, 32.1-32.п и 33 блоков 14.1 и l4.2, регистр 34 коэффициента, тактовый вход 35 регистра и вход 36 синхронизации.

В устройстве 1 из исходного вектора Йм вычисляется вектор каэффицттентав Фурье Г, Алгоритм работы устройства 1 предполагает хранение вектора f в блоке 2 в течение всего времени вычисления вектора E . Это позволяет использовать Гт„ для параллельного и независимого вычисления контрольного вектора Мт,, т.-и элемент т к которого вычисляется по алгоритму ДПФ у- ; н-т 2ITk .

m. = 2 à W =,> à (cos — — к-о

N к=а

2!lk .

sin ---т ) N!

К где 1 — весовой коэффициент.

Сравнение соответствующих результатов вычисления коэффициентов ДПФ 55 в устройстве 1 с элементами вектора

М! дает информацию о достоверности к полученных результатов.

Рассмотрим работу устройства на примере вычисления контрольного вектора N = 1 m, m ш, тп 1, если N

1024.

2Пk ., 2Пk тп = а (cos --- — j sin --- )

К т

К=О

2П 2lT

m = а,,(ros -- — 2k — j sin --2k);

2Л 2!! тп = ) а (cos -- Çk — j sin -- Çk).

5 К т

У к=о й-1 27 . . 2П

m = à (cos --4k — j sin -- 4k). к т,т N, к=о

В исходном состоянии счетчик 8, счетчик 11 итераций, регистры 28.1—

28.п и триггер 30 находятся в нулевом состоянии. В соответствии с алгоритмом работы устройства 1 в каждом первом и втором тактах шага иэ блока

2 выполняется считывание .саатветственна элементов а и а вектаNgiK К ра f . Следавательт а, в данный ма". мент из блока 2 па адресу 10...0 выполняется считывание операнда а,, l2 действительная Еа и мнимая Jm части которого поступают соответственна на входы регистров 15.1, 15,2, 16,1 и 16.2. Из блока 14.2 считывается значение cos О. Примем исходное состояние за первый такт первого шага рабаты устройства.

Ва втором такте первого шага (состаяние счетчика 8 тактов 00...01) из блока 2 выполняется считывание а, а о из блока 14.2 — значения cos О, по синхраимпульсу 35 в регистр 34 записывается cos О.

В третьем такге первого шага (состояние счетчика 8 тактов 00... 10) па синхраимпульсу 20.1 положительным перепадом выполняется прием Ее а, и Im а, соответственно в регистры 15.1 и !6.1, на управляющем входе 22.1 присутствует единичное значение, которое разрешает поступление Ве а, на вход умножителя 19, в этом такте в регистр 34 па синхраимпульсу 35 выполняется запись значения cos О, которое затем поступает на вход умнажителя 19. Результат умножения Re a . cos О проходит через сумматор 27 Ges изменения на входы регистров 28.128.п (на управляющем входе 33 — "0"), так как присутствующее на управляющем входе 31.1 единичное значение разрешает прохождение на второй вход сумматора 27 нулей, записанных в ре3 1254 гистре 28.1. Из блока 14 .2 выполняется считывание значения sin О.

В четвертом такте первого шага (состояние счетчика 8 тактов 00...

11) по синхроимпульсу 32.1 выполняет- 5 ся запись Re а, cos О в регистр 28.1, по синхроимпульсу 35 в регистр 34 записывается sin О. Состояние управляющего входа 22.1 не изменяется, и в умножителе 19 вычисляется Re.a, ° з1п О, которое проходит через сумматор 27 без и-менения на входы регистров 28. 1-28.п; на управляющем входе

31.2 единичное значение (на остальных управляющих входах 31.1, 31.2

31.n — "О") разрешает прохождение на второй вход сумматора 27 нулей, записанных в регистре 28.2. Из блока 14.2 считывается значение sin О.

В первом такте второго шага (состояние счетчика 8 тактов 00...100) синхроимпульсом 32.2 выполняется запись Re à, sin О в регистр 28.2. Состояние управляющих входов 22. 1, 23. 1, 23.2, 24 и 25 — "О", управляющего 25 входа 23.1 — "1", в умножитель 19 поступает значение Im а,, состояние регистра 34 подтверждается. В умножителе 19 вычисляется Лт à,. sin О и поступает на вход сумматора 27, на втором входе сумматора 27 присутствует операнд Re а, cos О, так как на управляющем входе 31.1 — "1", на входах 31.2-31 — "О". На управляющем входе 33 значение "1" обеспечивает вычисление Re à,. cos Π— Jm à, .sin О=

= Re А.. Из блока 2 считывается а,„, иэ блока 14.2 — значение

cos О.

Во втором такте второго шага (сос40 тояние счетчика 8 тактов 00... 101) синхроимпульсом 32. 1 выполняется запись Re А, в регистр 28., по синхроимпульсу 35 в регистр 34 записывается cos О, состояние управляющих сигналов 22.1, 23.1, 22.2, 24, 25

45 не уменьшается и в умножителе 19 вычисляется Xm à cos О, которое затем поступает на вход сумматора 27, на втором входе сумматора 27 присут50 ствует операнд Re à sin О, так как на управляющем входе 31.2 — "1", на входах 31.1, 31.3-31.n — "0". На управляющем входе 33 значение "О" обеспечивает вычисление Re à,- sin 0 +

+ Xm à cos О = Xm А. Из блока 2

55 считывается а,, из блока 14.2 — эна2 чение cos — — k (k = 1) .

506 4

В третьем такте второго шага (сос тояние счетчика 8 тактов 000...fiO) синхроимпульсом 32.2 выполняется запись Xm А. в регистр 28.2, по синхроимпульсу 35 в регистр 34 записывает2й ся cos — — k (k = 1) по синхроимN

У пульсу 20.1 выполняется прием Re а„ и Ет а, соответственно в регистры

15.1 и 16. 1, на управляющем входе

22.1 присутствует единичное значение, которое разрешает прохождение

Re а„ на вход умножителя 19. Резуль"IT тат умножения Re à cos - — — k (k = 1) и поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28. I (на управляющем входе 31. 1 — " 1", на входах

31.2-31.п — "0"). В сумматоре 27 вы2И числяется Re А,+ Re а, cos --„— k (на управляющем входе 33 — "О"), Из блока 14.2 считывается значение

21Е

sin — — k (k = 1).

В четвертом. такте второго шага (состояние счетчика 8 тактов 00...

111) синхроимпульсом 32.1 выполня2П ется запись Re А + Re à cos и I N (k = 1) в регистр 28. 1, по синхроимпульсу 35 в регистр 34 записывается

211

sin --- k (k = 1) . Состояние управN ляющего входа 22.1 не изменяется, и в умножителе 19 вычисляется Re а, 2 11 з1п — — k (k = 1) которое затем

У .поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28.2 (на управляющем rxope 31.2 — "1", на управляющих входах 31.1, 31.3-31.n — "О") .

В сумматоре 27 вычисляется Im A, +

2TI

+ Re à sin †- k (k = 1) (на управ1 N ляющем входе 33 — "0"). Из блока 14.2

2ЕГ считывается значение sin †â€, k (k

1).

Работа устройства в остальные

N/2 — 2 шаги аналогична описанной.

В первом такте первого шага на второй итерации (состояние счетчика

8 тактов 00...0) синхроимпульсом

tijjg-ÿ

32.2 выполняется запись Im А„+ к=о

1254

2П

+ Re A, . sin --- k (1c = N/2 — 1) й/2- в регистр 28.2. Состояние управляющих входов 22.1, 22.2, 23.2, 24, 25

"0"„ управляющего входа 23. 1 — " 1", в умножитель 19 поступает значение

Im aN1 „, в регистр 34 записан

2тт

sin --- k (k = N/2 — 1) и поступает

N на вход сумматора 27, на втором входе сумматора 27 присутствует операнд тгг2. 2 2ll

Re A +ReА cos — — k (k к=тг

К ч1 -г N

20 ф-- гг 12-2 вычисление, Im Л „+ Im А =7 Im Л . 50 к= сг

К М12„К

2Il

Из блока 14.? считывается cos --- k (1c = Л1/2). В регистры 15.2 и 16.2 синхроимпульсом 20.2 выполняется прием соответственно Не а„ и ?тп а„

М(2 (на первой интерации прием в регистры 15.2 и 16.2 может выполняться, но на работу устройства оп влияния не

1), так как на управляющем входе 3 1. 1 — " 1 1, на управляющих входах 31.2-31.п — "0". На управляющем входе 33 значение !" обеспечивает

N /2-2 вычисление L Re A„+ Ве Л .. Из ггl 2-с

К=О блока 2 считывается а,,, из блока

14.2 — значение сов — — k (k

11 2

1)

Во втором такте второго шага второй итерации (состояние счетчика 8 тактов 00...01) синхроимпульсом 32. 1

30 выполняется запись„ Не Л, в регистр к=а

?8. 1, по синхроимпульсу 35 в регистр

2 N

34 записывается cos =--- lc (lc

N ?

1). Состояние управляющих входов

22. 1, 23. 1, 22. 2, 24, 35 не изменяется, и в умномсптеле 19 вычисляется

?П N

1гт а соя "— k (k = --" — 1) и nocNI2- лг 2

40 тупает на вход сумматора 27, на втором входе сумматора 27 присутствует гг12- 2 211 операнд 2 lm A + Re а 1 sin --- k, к=о так как на управляющем входе 31.2

"1", на управляющих входах 31. 1, 31.3-31.n — "0". На управляюцем входе 33 значение "О" обеспечивает

506 б оказывает, так как на управляющем входе регистров 15.2 и 16.2 присутствует значение "0").

В третьем такте второго шага (состояние счетчика 8 тактов 00...10) синхроимпульсом 32.2 выполняется загг12-1 пись Im А, в регистр 28.2, по синk"-д хроимпульсу 35 в регистр 34 записы2П вается cos --- k (k = N/2), единичное значение на управляющем входе

22.2 разрешает прохождение в этом такте йе а „1 на вход умножителя 19.

2l

Результат Re à cos — — k (k =N/2) г 1г N поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28.1 и в суммагт 12- г торе 27 вычисляется ? Re A + Re a

2IT ч12

N х cos --- k (k = N/2) . Из блока 14. 2

2Тс считывается значение зг.п †- k (k

N — N/2) .

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

Отличие в работе устройства на второй итерации состоит в приеме во втором такте каждого шага в регистры, 15 2 и 16.2 соответственно операндов

Re а и Ima ц и выдаче из них инфоргг1 к 2+" мации на вход умножителя в третьем такте.

Таким образом, к концу выполнения второй итерации в peãèñòðàõ 28.1 и

28.2 вычисляются значения действигг- 2 N-1 тельтгой2 Re Л„и мнимой im А часК=О к=о тей коэффициента Фурье m, На третьей и четвертой итерациях аналоничным образом вычисляются действительная и мнимая части коэффициента

Фурье вг, которые будут храниться в регистрах 28.3 и 28.4. На пятый и шестой — m в регистрах 28.5 и 28.6, на седьмой и восьмой — тп в регист г рах 28.7 и 28.8.

Значения весовых коэффициентов для вычисления ш, т, m„ oáeñïå÷èвает блок 14.2.

На девятой итерации управляющие сигналы с шины 21 синхронизации не поступают.

На десятой ифгерации работы устройства 1 выполняется сравнение коэффициентов т, т, m,,m с анапогичными коэффициентами Г, Р, F

1 7

F, вычисленными по алгоритму БПФ в

Э устройстве 1. Из -алгоритма работы устройства 1 следует, что F, F

F, F получаются в третьих тактах

3 Ф 4 соответственно шагов N/4, N/8, 3N/4, N/6, т.е. F получаем на 1024/16 — 64 шаге; à — на 128 шаге; F, — на

256 шаге; F — на 384 шаге.

Рассмотрим работу устройства на десятой итерации на 64, 128, 256 и

384 шагах. 1

На 64 шаге в третьем такте на выходе арифметического блока 4 присутствует операнд Г, действительная и мнимая части которого по синхроимпульсу 26 записываются соответствен- 2 но в регистры 17 и 18, на управляющем входе 24 — " 1", в регистр 34 по синхроимпульсу 35 выполнена запись кода 11...1, поэтому значение Re F проходит через умножитель 19 без из- 25 менений и поступает на вход сумматора 27. На второй вход сумматора 27 в этом такте поступает содержимое регистра 28.7 (на управляющем входе

32.7 — "1"), на управляющем входе ЗО

33 сумматора 27 присутствует код "1", выполняется операция вычитания, значение разрядов сумматора 27 поступает на схему ИЛИ 29, результат логического преобразования присутствует на входе триггера 30 ошибки.

45

В четвертом такте синхроимпульсом

36 выполняется запись результата сравнения в триггер 30 ошибки. Если триггер не изменяет своего состояния, результат верен, если изменяет, в вычислениях произошла ошибка. Аналогичным образом;: четвертом такте выполняется сравнение мнимых частей коэффициентов Г и m, записанных

4 соответственно в регйстры 18 и 28.8.

В первом такте 65 шага результат сравнения может быть записан в триггер 30.

Работа схемы на 128, 256 и 384 шагах аналогична и отличается от описанной для 64 шага значениями управляющих сигналов, обеспечивающих выдачу соответственно из регистров

28.3, 28.4, 28.1, 28.2, 28.5, 28.6.

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

1254506

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

Процессор быстрого преобразования

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

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

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

ИЛИ, выход которого подключен к уста новочному входу триггера, выход ко9 второго является контрольным выходом процессора, информационные выходы счетчика и счетчика итераций подключены к адресным входам блока постоянной памяти микрокоманд и блока постоянной памяти коэффициентов, выход последнего подключен к информационному входу регистра коэффициента, выход которого подключен к второму входу умножителя, выход i-ro (i = 1, n) разряда блока постоянной памяти микрокоманд подключен к управ ляющему входу i-ro регистра группы, тактовый вход которого подключен к выходу (i + n) -го разряда блока постоянной памяти микрокоманд, выходы (2п+1)-ro, (2п+2) — ro, (2п+3) -го,(2n+

+4) -го, (3n+5) -го и (?и+6) -го разрядов блока постоянной памяти микрокоманд подключены к управляющим входам соответственно первого, второго, 1254506 третьего,и четвертого регистров, первого и второго регистров результата, выходы (2n + 7)- ro, (2n + 8) — го и (2п + 9)-ro разрядов блока постоянной памяти микрокоманд подключены к тактовым входам соответственно перI вого и второго регистров, третьего и четвертого регистров, первого и второго регистров результата, выходы (2n + 10)-ro и (2n + 11) -го разрядов блока постоянной памяти подключены к входам синхронизации соответственно сумматора и триггера, информационный выход арифметического блока подключен к информационным входам первого и второго регистров результата, выходы которых подключены к первому входу умножителя, а выход генератора тактовых импульсов подключен к тактовому входу регистра коэффициенI B °

1254506

Составитель А.Баранов

Редактор А.Огар Техред И.Попови Корректор М.Максимишинец

Заказ 4723/54 Тираж 671 Подписное

ВНИИПИ Гасударственного комитета СССР по делам изобретений и открь тий

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

Производственно-полиграфическое предприятие, r.ужгород, ул.Проектная, 4