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

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

Иллюстрации

Показать все

Реферат

 

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

СООЭ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК щ) g С 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО иэОБРетениям и ОТКРытиям

ПРИ ГКНТ СССР

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4480506/24 (22) 05.09.88 (46) 23.08.91. Бюл. М - 31 (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина (72) А.Н.Карташевич, В.M ° Ïðèõoäüêî и А.А.Фомин (53) 681.3(088.8) (56) Авторское свидетельство Ы.СР

М 1056206, кл. С 06 F 15/332, 1981.

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

N 1164730, кл. С 06 F 15/332, 198 .

„„,Ж„„1672468 А1

2 (54) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИ11 БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Из обретение относится к вычислительной технике и может быть использовано для цифровой обработки сигналов. Цель изобретения — повьппение быстродействия. Укаэанная цель достигается за счет того, что устройство содержит блоки оперативной 1, 2 и постоянной 3 памяти, первьп1, второй коммутаторы 13, 11, счетчики 14, 15, конвейерные регистры 6, 7, сдвигающий счетчик 17, умножитель 4, блок 8 синхронизации и блок 16 элементов И, третин, четвертьп1 коммутаторы 12, 10, накапливающий сумматор 5 и сумматорвычитатель 9. 2 ил.

1672468

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

Цель изобретения — повьппение быстродействия °

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

Устройство содержит (фиг . 1 ) первый

1 и второй 2 блоки оперативной памяти, блок 3 постоянной памяти, умножитель 4, накапливающий сумматор 5, первый 6 и второй 7 конвейерные регистры, блок 8 синхронизации, сумматор-вычитатель 9, четвертый 10, второй 11, третии 12 и первыи 13 коммутаторы, первый 14 и второй 15 счетчики, блок 16 элементов И и сдвигаю- 20 щий счетчик 17, Блок синхронизации (фиг.2) содержит первый 18, второй 19 и третий 20 триггеры, генератор 21 синхроимпульсов, одноразрядный счетчик 22, двухразрядный счетчик 23, дешифратор 28, элемент ИЛИ 24, а также первый 25, второй 26, третий 27, четвертьп» 29, пятый 30, шестой 31, седьмой 32, восьмой 33, девятый 34, десятый 35, одиннадцатый 36 двенадцатый 37, тринадцатый 38 и четырнадцатьп» 39 элементы И, первую группу Y 1 выходов

40, 41, вторую группу 72 выходов 4244, третью группу » 3 выходов 45-53, вход 54 запуска, вход 55 останова и вход 56 признака режима работы.

Блоки оперативной 1, 2 и постоянной 3 памяти содержат по 2М ячеек, 40 где N — длина реализации, счетчики

14 и 15 содержат и+1 разрядов, где

n = log

17 вдвигается единица, вследствие

tl ll

55 чего на второй итерации с выхода блока 1Ü элементов И на адресный вход

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

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

Первый информационный вход первого мультиплексора третьего коммутатора

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

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

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

Вьп|олнение итерации быстрого flpt. образования Фурье заключается в последовательном выполнении в устройстве операция вида В+А W, где A и В операнды, извлекаемые из блока оперя72468 () 10

16 тинноп п fMff Tff 1, — экспоненциа.п.ныи л»» ож»»тел»., из f»Jlt. каемый из блока постоянноп памяти. Злел»ег»тарная ont-.ðàция Б!!Ф осуществляется за четыре такта. В устропстве реализован конвейерный принцип обработки, т.е. данные, подготовленные за четыре такт.l первого этапа, заносятся в память за четыре такта второго этапа, а данные, подготовленные на втором этапе, заносятся в память на третьем этапе и т.д., причем после завершения каждой последующей итерации происходит переключение блоков оперативной памяти (на первой итерации информация считывается из второго блока 2 оперативной памяти, а результаты записываются в первый блок 1 оперативной памяти, на второй итерации, наоборот, считывается из первого 1, заносится во второи 2) К„1,2=R В +(К А cos(t)t — 1 А s inst); м

I 1,2=I В «+(К A s inst + 1 Л cosset) .

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

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

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

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

В третьем такте результат умножения I А ° sinCJt с выхода умножителя 4 заносится в накапливающий сумматор 5, вместе с этим из второго блока 2 оперативной памяти считывается действительная часть следующего операнда

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

I А соя(73 С.

Щ

В четвертом такте из регистра 7 депствительная часть операнда Ке В заносится в сумматор-вычитатель 9, и вь»полняется операция сложения, затем из второго блока 2 оперативной памяти считывается мнимая часть операнда 1 В и заносится в регистр 7, вместе с тем в предварительно обнуленный накапливающий сумматор 5 заносится результат умножения I А cosh)t

fff с выхода умножителя 4 и из регистра

6, через первый информационный вход коммутатора 11 записывается через первый вход в умножитель 4 значение действительной части операнда R< А, на второй вход умножителя 4 поступает зна гение синусной составляющей экспоненциального коэффициента, а также производится запись в первый блок 1 оперативной памяти действительной части nåðsoH точки R< 1 = R< В +

+ (R Аcos 63 t — I А sinQt) злее »П ментарного преобразования с выхода сумматора-вычитателя 9.

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

1672468

К 2 = R  — (К А cos% t -I А здпсХ) е е е % элементарного преобразования, вместе с тем в накапливающий сумматор 5 с выхода умножителя 4 записывается ре5 зультат умножения Ке A sin(i3t, полученный в предыдущем такте обработки, и из второго блока 2 оперативной памяти считывается значение действильной wacTH операнд заносится в регистр 6 через первый информационный вход коммутатора 10, и через второй информационный вход коммутатора 11 записывается через первый вход в умножитель 4, на второй вход которого поступает значение косинусной составляющей экспоненциального множителя из блока 3 постоянной памяти.

В следующем такте в сумматор-вычитатель 9 из регистра 7 через первый вход заносится значение мнимой части операнда I В, через второй вход в сумматор-вычитатель 9 заносится значенЛе I А cosЯ t+R

+ (R А sinQt + I А cos Qt) злее tA ментаркого преобразования заносится в первый блок оперативной памяти, а также иэ второго блока 2 оперативной памяти извлекается значение мнимой части операнда I À и через

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

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

55 умиожителя 4 из блока 3 постоянной памяти поступает косинусная составляющая экспоненциальной функции (в предыдущем такте через первый вход в умножитель было занесено значение 1 „A ), сумматор-вычитатель 9

I производит операцию вычитания между операндами, занесенкыми в него в предыдущем такте, и в первый блок 1 оперативной памяти заносится значение мнимой части второй точки элементарного преобразования 1 „ 2 = I „, В— (R< А s in t + Т „„А cos(g t) .

В четвертом такте в сумматор-вычитатель 9 через его первый вход иэ

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

I I части Rg 1 = R<В + (R А cosQt

I À sin63t), затем из второго блока 2 оперативной памяти считывается значение мнимой части операнда

I В и через первый вход коммутатоI ра 10 заносится в регистр 7, с выхода умножителя 4 значение I А cos Gdt

f полученное в предыдущем такте, заносится в накапливающий сумматор 5. Из регистра 6 через первый информационный вход коммутатора !1 через первый вход умножителя 4 заносится значение действительной части Re А операнда, на второй вход умножителя поступает значение синусной составляющей экспоненциальной функции из блока 3 постоянной памяти. В дальнейшем до конца итерации обработка происходит аналогично второму такту обработки.

После считывания из второго блока

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

44 блока 8 синхронизации, происходит переключение блоков оперативной памяти, первый 1 — для чтения, второй

2 — для записи. Импульс, поступающий с выхода переноса второго счетчика 15 поступает на вход сдвигающего счетчика 17, что приводит к тому, что его содержимое сдвигается ка один разргд вправо, а младший разряд заполняется единицей. Преобразованный код с информационного выхода счетчика 17 поступает на второй вход блока 16 эле1672468 ментов И, что приводит к преобразованию кодов, поступающих на адресный вход блока 3 постоянной памяти,.Все .последующие итерации выполняются

5 аналогично первои.

Блок 8 синхронизации работает следующим образ о м. Приходя щий н а вход

54 блока 8 синхронизации пусковой импульс устанавливает первый триггер

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

И 30.

На первом и втором выходах,цну,— разрядного счетчика 23 последовательно формируются коды соответствующих тактов. На первом такте уровень логического нуля с первого выхо35 да счетчика 23 поступает на второй инверсный вход элемента И 30, на первый инверсный вход которого поступает уровень логического нуля с н-.орого выхода счетчика 23, в результате че40

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

50 записи в умножитель 4„

Затем двухразрядный счетчик 23 переходит в следующее состояние. Во время второго такта уровень логической единицы с пернîro выхода двухраз- рядного счетчика 23 поступает через второй выход блока синхронизации на управляющие входы блока 3 постоянной памяти (выбор с»»н/н iп) It нлклплинающег ) с ммлторл 5 (с.t» z» IIII»-/вычитание) и нл первые ходы э. еь1евтон И 34, 35, нл вторые н хо Ibl которых Itoñ гуплют синхропмг|уль сы с пятого выхода ген ераторл 21 ctttIxpottt IIIyllьсов, с выхода элемента И 34 нл выход 48 блока синхронизации поступл T импульсы записи н сумматор-нычнтлтеrlb 9, с ныхс Ia элемента И 35 — импульсы обнуления нлклплинлющего ..умматорл 5. Уровень логическси ..диницы с ипнерсного выхода -pe òü»..l o триггера 20 поступает нл вход одноразрядного счетчика 22, а также на второй вход элемента И 26, на второй вход которого поступает

«ронень логическс го нуля о инверсного выхода второго триггера I9, н результате чего отпирается элема-нт И 25 и через его второй вход на ньнсод 51 блока cvs: J»pott;I I:Ilr HII It I»I>tstatoT поступать импульсы записи н накапливающий сум:1лтор 5.

Во время третьего такта уровень логической» JIIIIIIn(bt е второго выхода днухрлзрядного счетчика 23 открывает элемент И 31, через который тактовые импульсы с четвертого выхода I ett» ратора 21 синхроимпульсон поступают через выход ч7 блока синхронизации нл вход записи регистра 7. Этот же уровень логическои единицы устлнлвJIIIB

ЛОГII»IP» KOI I УЛЯ На ПЕРНОМ НЫХОДЕ днухрлзрядного счетчика 23 злкрывает элемен И 38, уровень логического нуля с выхода этогс элемента блокиPy».. T ПРОХ »» IIHe CIIHXPOIIbtII) Jib COB через элемент И 39 нл выход 53.

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

2l синхроимпульсон, Нл первых трех тактах элемент И 36 блокирован уровнем логическorо нуля с выхода третьего триггера 20, на четвертом такте уровень логической единицы с выхода указанного триггера отпирает элемент И 36, который и свою очередь открывает элемент И 27, с выхода которого синхроимпульсы, поступающие на его второй вход с второго ныходл генератора 2 1 синхроимпульсов, поступают на вход дешифратора

28, с первого либо второго выхода ко1672468 торого через выходы 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 блока синхронизации, в везультате чего происходит переключение блоков оперативной памяти.

Если на первой итерации информация считывалась иэ второго блока оперативной памяти, а запись производилась в первый блок, то на второй итерации инйормация считывается из пер10

55 вого блока, а запись происходит во второй блок оперативной памяти.

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

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

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

1672468

Риг 2

Составитель Ю.Ланцоь

Техред Л.Сердюкова Корректор О.Кравцова

Редактор В.Данко

Заказ 2841 Тираж 388 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r.ужгород, ул. Гагарина,101 информационными входами первого и второго блоков оперативной памяти и является выходом устройства, адресный вход и вход чтения-записи второго

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