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

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

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

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

Процессор содержит блок 1 вычисле- ния скользящего спектра, состоящий из блока 2 буферной памяти, мульти- -плексора 3, арифметического блока 4, блока 5 памяти и блока 6 сиихроныза- .ции, выполненного в виде генератора 7 тактовых импульсов, счетчика 8, формирователя 9 адреса, мультиплексора 10, счетчика 11 итераций, дешифратора 12 и регистра 13 адреса, блоки постоянной памяти микрокоманд 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-28.П, элемент ИЛИ 29, триггер 30, выходы 31.1-31.п 32.1-32.п и 33 блоков 14.1 и 14.2, регистр 34 коэффициента, тактовый вход 35 регистра и вход 36 синхронизации.

В устройстве 1 из исходного вектора f вычисляется вектор коэсМ Ицнен- тов Фурье F . Алгоритм работы устройства 1 предполагает хранение век- Тора f в блоке 2 в течение всего

времени вычисления вектора F, позволяет использовать f

ы для

Это

- /j,jiy. параллельного и независимого вычисления контрольного вектора М, i-й элемен которого вычисляется по алгоритму ДП

( 2TVk. С a,(cos ---.

-, J

sin

2%i N

где W - весовой коэффициент.

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

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

,|.

В исходном состоянии счетчик 8, счетчик 11 итераций, регистры 28.1- 28.п и триггер 30 находятся в нулевом состоянии. В соответствии о алгоритмом работы устройства 1 в каждом первом и втором тактах шага из блока 2 выполняется считывание .соответственно элементов а., и а векто.г г.N2tK к

ра т. Следовательно, в данный момент из блока 2 по адресу 10...О выполняется считывание операнда а|,.| , действительная Ra. и мнимая 3т части которого поступают соответственно на входы регистров 15.1, 15,2, 16.1 и 16.2. Из блока 14.2 считывается значение cos 0. Примем исходное состояние за первы.й такт первого шага .работы устройства.

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

Б третьем такге первого шага (состояние счетчика 8 тактов 00...10) по синхроимпульсу 20.1 положительным перепадом выполняется прием Re а и tim а соответственно в регистры 15.1 и 16.1, на управляющем входе 22.1 присутствует единичное значение, которое разрешает поступление Re а на вход умножителя 19, в этом такте в регистр 34 по синхроимпульсу 35 выполняется запись значения cos О, которое затем поступает на вход умножителя 19. Результат умножения Re а х «cos О проходит через сумматор 27 без изменения на входы регистров 28.1- 28,п (на управляющем входе 33 - О), так как присутствующее на управляющем входе 31.1 единичное значение разрешает прохождение на второй вход сумматора 27 нулей, записанных в регистре 28.1. Из блока 14,2 выполняется считывание значения sin О,

В четвертом такте первого шага (состояние счетчика 8 тактов 00.., 11) По синхроимпульсу 32.1 выполняет ся запись Re О в регистр 28.1 по синхроимпульсу 35 в регистр 34 записывается sin 0. Состояние управляющего входа 22.1 не изменяется, и в умножителе 19 вычисляется Re.a sin О, которое проходит через сумматор 27 без и,менения на входы регистров 28.1-28.П; на управляющем входе 31.2 единичное значение (на остальных управляющих входах 31.1, 31.2 - 31.п - О) разрешает прохождение на второй вход сумматора 27 нулей, записанных в регистре 28.2. Из блока 14. считывается значение sin 0.

В первом такте второго шага (сое- тояние счетчика 8 тактов 00...100) синхроимпульсом 32.2 выполняется запись Re О в регистр 28.2. Состояние управляющих входов 22.1, 23.1 23.2, 24 и 25 - О, управляющего входа 23.1 - 1, в умножитель 19 . поступает значение Зга а, состояние регистра 34 подтверждается. В умножителе 19 вычисляется Лт sin О и поступает на вход сумматора 27, на втором входе сумматора 27 присутствует операнд Re О, так как на управляющем входе 31.1 - 1, на входах 31.2-31 - О. На управляющем входе 33 значение 1 обеспечивает вычисление Re О - 3т а sin 0 Re Ад. Из блока 2 считывается а ИЗ блока 14.2 - значение cos 0.

Во втором такте второго шага (состояние счетчика 8 тактов 00...101) синхроимпульсом 32.1 выполняется запись Ее А в регистр 28.i, по синхроимпульсу 35 в регистр 34 записывается cos О, состояние управляющих сигналов 22.1, 23.1, 22.2, 24, 25 не уменьшается и в умнолсителе 19 вычисляется 1т О, которое затем поступает на вход сумматора 27, на втором входе сумматора 27 присутствует операнд Re О, так как на управляющем входе 31.2 - 1, на входах 31.1, 31.3-31.п - О. На управляющем входе 33 значение О обеспечивает вычисление Re а„- sin О + + 1т а cos О Im А. Из блока 2 считывается а,, из блока 14.2 - значение cos --- k (k 1). N

.

-, юfj 2

20 , 25 -JQ

35

40

45

50

55

В третьем такте второго шага (сос тояние счетчика 8 тактов 000...110) синхроимпульсом 32.2 выполняется запись Im А„ в регистр 28.2, по синхроимпульсу 35 в регистр 34 записывает2ТГ

ся cos --- k. (k 1) , по синхроимпульсу 20.1 выполняется прием Re а и 1т а соответственно в регистры 15.1 и 16.1, на управляющем входе 22.1 присутствует единичное значение, которое разрешает прохождение Re а на вход умножителя 19. Результат умножения Re а cos --- k (k 1)

поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28.1 (на управляющем входе 31.1 - 1, на входах 31.2-31.П - О). В сумматоре 27 вы2Пчисляется Ее А Re --- k (на

управляющем входе 33 - О) , Из блока 14.2 считывается значение

2W sin --- k (k 1) .

В четвертом.такте второго шага (состояние счетчика 8 тактов 00... 111) синхроимпульсом 32.1 выполня2ITется запись Re А + Re а cos --- k

(k 1) в регистр 28.1, по синхроимпульсу 35 в регистр 34 записывается

2И

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

2TF --- k (k 1), которое затем

,,поступает на вход сумматора 27, на второй вход сумматора 27 поступает содержимое регистра 28.2 (на управляющем Ех.оде 31.2 - 1, на управляющих входах 31.1, 31.3-31.П - О). В сумматоре 27 вычисляется 1т А„ +

2F

+ Re а,sin -п- k (k 1) (на управляющем входе 33 - О). Из блока 14.2

2ТГ считывается значение sin -г k (k

1).

Работа устройства в остальные N/2 - 2 шаги аналогична описанной.

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

N/i-Z

32.2 выполняется запись З Im А -ь

n и„ „„,„„„„ „,„ поступает на вход cyMJiaTopa 27, на ,, „ второй вход сумматора 27 поступает

512545066

tig л .4 2ТТ , , ..оказывает, так как на управляющем

N/2- Nвходе регистров 15,2 и 16.2 присутв регистр 28,2. Состояние управляю-ствует значение О). щих входов 22.1, 22.2, 23.2, 24, 25 - В третьем такте второго шага (, управляющего входа 23.1 - 1, тонкие счетчика 8 тактов 00..,10)

в умножитель 19 поступает значениесинхроимпульсом 32.2 выполняется за- Im 5 в регистр 34 записанN12-)

2ТГ . ,пись Im А в регистр 28.2, по син- sin --- k (k N/2 - 1) И поступает р., „-, хроимпульсу 35 в регистр 34 записы- на вход сумматора 27, на втором вхо- ю2ТТ

де сумматора 27 присутствует операндвается cos --- k (k N/2), единичН . „ . 211 ,,, -ное значение на управляющем входе

X Re Л + Re А I cos --- k (k ото

« Nla-1 N/2.2 разрешает прохождение в этом

такте Re а, на вход умножителя 19.

- 1), так как на управляющем р.езультат Re а cos k (k N/2) входе 31.1 - 1, на управляющих входах 31.2-31.п - О. На управляющем

входе 33 значение. 1 обеспечивает«о

1 содержимое регистра 28.1 и в сумма- вычисление L-Re А, + Re Aj,., . Изторе 27 вычисляется 5Z Re А + Re а . ,К:021Г

блока 2 считывается , , из блока °« Т °

2ТТ , .,N

14.2 - значение cos --- k (.k -. 2ТТ.

25считывается значение sin k (k

„ 1ЛN

T /9

Во втором такте второго шага вто- / / .

рой итерации (состояние счетчика 8 В четвертом такте работа устройтактов 00...01) синхроимпульсом 32, аналогична описанной для четверi j( 2-iтых тактов первой итерации . выполняется запись Re А в регистр ° Отличие в работе устройства на

К--0второй итерации состоит в приеме во

28.1, по синхроимпульсу 35 в регистрвтором такте каждого шага в регистры,

; N15 2 и 16.2 соответственно операндов

34 записывается cos ---- k (k у- -;

- 1). Состояние управляющих входов 5Re а,и Ima .,,и выдаче из них инфор22 1 23 1. 27.2, 24, 25 не измекя „мации на вход умножителя в третьем

ется, и в умнохштеле 19 вычисляется

.ТИКTS

Im а cos -- k (k. - - 1) и пос- Таким образом, к концу выполнения

40второй итерации в регистрах 28.1 и

тупает на вход сумматора 27, иа вто- 8.2 вычисляются значения действи- ром входе сумматора 27 присутствует,

14J2-Jо .

К-т л -1- 13о ч г-тп --Vтельной) Re А, и мнимой А., часоперанд)1т А + Ке кТо о

так как на управляющем входе 31.2 -тей коэффициента Фурье га,.. На , на управляющих входах 31,1, ;.тьей и четвертой итерациях анало- .

31.3-31.П - О. На управляющемничным образом вычисляются действивходе 33 значение О обеспечиваеттельная и мнимая части коэффициента

Фурье т, которые будут храниться в

|j Nii-2--регистрах 28.3 и 28.4. На пятый и

вычисление I,Tm А + Im 1m А. 50„естой - т в регистрах 28.5 и 28.6,

2ТТ ,на седьмой и восьмой - m в регист- ,

Из блока 14.2 считывается cos --- kpax 28.7 и 28.8,,

(k N/2). В регистры 15.2 и 16.2 Значения весовых коэффициентов

синхроимпульсом 20,2 выполняется при-для вычисления т,, ш, т обеспечием соответственно Re а, и Im а.вает блок 14.2.

(на первой интерации прием в регис- На девятой итерации управляющие

тры 15.2 и 16.2 может выполняться, .сигналы с шины 21 синхронизации не

но на работу устройства он влияния непоступают.

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

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

устройстве 1. Из .алгоритма работы устройства 1 следует, что F , F , F , F получаются в третьих тактах соответственно шагов N/A, N/8, 3N/4 N/6, т.е. F получаем на 1024/16 64 шаге; F - на 128 шаге; F .- на 256 шаге; F - на 384 шаге. . Рассмотрим работу устройства на десятой итерации на 64, 128, 256 и 384 шагах.

На 64 шаге в третьем такте на выходе арифметического блока 4 присутствует операнд F , действительная и мнимая части которого по синхроимпульсу 26 записываются соответственно в регистры 17 и 18, на управляющем входе 24 - 1, в регистр 34 по синхроимпульсу 35 выполнена запись кода 1 1 ... 1, поэтому значение Re F проходит через умножитель 19 без изменений и поступает на вход сумматора 27. На второй вход сумматора 27 в этом такте поступает содержимое регистра 28.7 (на управляющем входе 32.7 - 1), на управляющем входе 33 сумматора 27 присутствует код 1 выполняется операция вычитания, значение разрядов сумматора 27 поступает на схему ИЛИ 29, результат логического преобразования присутствует на входе триггера 30 ошибки.

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

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

Работа схемы на 128, 256 и 384 шагах аналогична и отличается от описанной для 64 шага значениями управляющих сигналов, обеспечиваю1дих выдачу соответственно из регистров 28.3, 28.4, 28.1, 28.2, 28.5, 28.6.

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

1254506

Формула

изобретения

10

15

20

25

0

5

0

5

0

5

Процессор быстрого преобразования Фурье, содержащий генератор тактовых импульсов, выход которого подключен к входу формирователя адреса и счетному входу счетчика, выход переноса которого подключен к счетному входу счетчика итераций, информационный выход которого подключен к входу дешифратора и управляющему входу первого мультиплексора, выход которого подключен к адресному входз блока памяти, выход которого подключен к . перв Ьму информационному входу второго мультиплексора, выход которого подключен к информационному входу арифметического блока, информационный выход арифметического,блока подключен к информационному входу блока памяти, второй информационный вход второго мультиплексора подключен к выходу блока буферной памяти-, адресный вход которого подключен к выходу регистра адреса, информационный вход которого подключен к выходу формирователя адреса, а выход дешифратора подключен к управляющему входу второго мультиплексора, выход первого разряда счетчика подключен к управляющим входам блока буферной, памяти и блока памяти, выходы разря-- дов счетчика подключены к соответствующим информационным входам первого мультиплексора, информационный вход блока буферной .памяти является информационным входом процессора, отличающийся тем, что, с целью повышения достоверности, в него введены четыре регистра, два регистра результата, умножитель, сумматор, элемент 5 ШИ, триггер, группа регистров, регистр коэффициента, блок постоянной памяти-микрокоманд,, блок постоянной коэффициентов, выход блока буферной памяти подключен к информационным входам первого, второго, третьего и четвертого регистров, выходы которых подключены кпервому входу умножителя, выход которого подключен к первому входу сумматора, выход которого подключён к информационным входам регистров группы, выходы которых подключены к второму-входу сумматора, выходы разрядов которого подключены к соответствующим входам элемента ИЛИ, выход которого подключен к установочному входу триггера, выход ко foporo является контрольным выходом процессора, информационные выходы счетчика и счетчика итераций под- тспючены к адресным входам блока постоянной памяти микрокоманд и блока постоянной памяти коэффии -гентов, выход последнего подключен к информационному входу регистра коэффициента, выход которого подключен к второму входу умножителя, выход i-ro (i 1, п) разряда блока постоянной памяти микрокоманд подключен к управляющему входу i-ro регистра группы тактовый вход которого подключен к выходу (1 + п)-го разряда блока пос- тониной памяти микрокоманд, выходы (2п-|-1)-го, (2п+2)-го, (2п+3)-го, (2п+ +4)-го, (2п+5)-го и (2п+6)-го разрядов блока постоянной памяти NmKpo- команд подключеьгы к управляющим вхо- дам соответственно первого, второго,

третьего .и четвертого регистров, первого и второго регистров результата, выходы (2п + 7)-го, (2п + 8)-го и (2п + 9)-го разрядов блока постоянной памяти микрокоманд подключены к тактовым входам соответственно пер- вого и второго регистров, третьего и четвертого регистров, первого и второго регистров результата, выходы (2п + 10)-го и С2п + 11)-го разрядов блока постоянной памяти подключены к входам синхронизации соответственно сумматора и триггера, информационный выход арифметического блока подключен к информационным входам первого и второго регистров результата, выходы которых подключены к первому .входу умножителя, а выход генератора тактовых импульсов подключен к тактовому входу регистра коэффициента.

Фиг,Г

Редактор А.Огар

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

Техред Н.ГТопов№1 Корректор М- Максимишинец

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

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

9US.2

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