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

 

1. УСТРОЙСТВО ДЛЯ -БЫСТРОГО ; ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее регистры синусного и косинусного весовых коэффициентов, параллельные входы которых являются входами коэффициентов устройства,, четыре регистра, три ко№ утатора, два сумматора и блок управления , о т л и ч а ю 14 е е с я тем, что, с целью упрощения устройства , оно содержит четвертый коммутатор , причем входы действительной и мнимой частей отсчетавходного сигна-ла устройства подключены к первым информационным входам первого и второго коммутаторов, выход первого сумматора подключен к информационным входам первого и второго регистров, выход второго сумматора подключен к информационным входам третьего и четвёртого регистров, выходы первого и второго регистров, являющиеся выходами действительной и мнимой частей первого результата устройства, под-: . ключены к информационным входам третьего коммутатора, выход которого подключен ко второму информационному входу первого сумматора, выходы третьего и четвертого регистров, являющиеся выходами действительной и мнимой частей второго результата . устройства, подключены к информационным входам четвертого коммутатора, . выход которого подключен ко второму информационному входу второго-сумматора , выход второго регистра подключен ко второму информадионноиу входу второго коммутатора, причем знаковый вызсод второго регистра соединен с инвертирующим разрядным входом второго коммутатора, выход четвертого регистра подключен ко второму ин фо1 ационному входу первого коммутатора, последовательные входы регистров синусного и косинусног( весовых коэффициентов подключены к источнику единичного сигнала; последовательный клход регистра косинусного весового коэффициента подключен к управляюшлм входам первого и третьего регистров и к первому входу блока управления, : последовательный выход регистра сину-ч сного весового коэффициента подклю-. чен к управляющим входам второго и четвертого регистров и ко второму входу блока управления, первый выход блока управления подключен к тактрр вым входам первого и третьего регйст-Si ров и к тактовым входамрегистров синусного и косинусного весовых коэффициентов , второй выход блока управления подключен к тактовым входам второго и четвертого регистров, тре00 тий выход блока управления подключен к управляющим входам первого и второго сумматоров, четвертый выход блока ю управления подключен к управляющим со входам сдвига третьего и четвертого коммутаторов, пятый выходблока управ-; ления подключен к управляющим входам первого и второго коммутаторов, шестой выход лока управления подключен к переключающим входам третьего и четвертого коммутаторов. 2; Устройство по п.1, отличают е е с я тем, что блок управления состоит из триггера, счетчика, блока постоянной памяти и пяти элементов И, причем синхронизирующий вход триггера является тактовым входом устройства и подключен к первым входам перво

ЗаВС 06

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ, ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3337100/18-24 (22) 07.07.81 ,(46) 15.05 ° 83. Бюл. 9 18 (72) B,Ä.Ãócåâ и С.И.Алферов (71) Специальное конструкторское бюро "Виброприбор" (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

В 736113, кл. G 06. F 15/332, 22,11.77.

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

9 467356, кл. G 06 F 15/332, 25. 03 ° 74. (54) (57) 1. УСТРОЙСТВО ДЛЯ БЬИ ТРОГО

ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее регистры синусного и косинусного весовых коэффициентов, параллельные входы которых являются входами коэффициен-. тов устройства, четыре регистра, три коммутатора, два сумматора к блок управления, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит четвертый коммутатор, причем входы действительной и мнимой частей отсчета входного сигна= ла устройства подключены к первым информационным входам первого и вто.: рого коммутаторов, выход первогосумматора подключен к информационным входам первого и второго регистров, выход второго сумматора подключен к . информационным входам третьего и четвертого регистров, выходы первого и второго регистров, являющиеся выходами действительной.и мнимой частей первого результата устройства, под-.. ключены к информационным входам третьего коммутатора, выход которого подключен ко второму информационному входу первого сумматора, выходы третьего и четвертого регистров, являющиеся выходами действительной и мнимой частей второго результата . устройства, подключены к информационным .входам четвертого коммутатора, выход которого подключен ко второму информационному входу второго суммаSU„„01812 А тора, выход второго регистра подключен ко второму информационному входу второго коммутатора, причем знаковый выход второго регистра соединен с инвертирующим разрядным входом второго коммутатора, выход четвертого регистра подключен ко второму информационному входу первого коммутатора, последовательные входы регистров синусного и косинусного весовых коэффициентов подключены к источнику единичного сигнала; последовательный выход регистра косинусного весового коэффициента подключен к управляющим входам первого и третьего регистров и к первому входу блока управления, д

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

2; Устройство по п.1, о т л и ч аю щ е е с я тем, что блок управления состоит из триггера, счетчика, блока постоянной памяти и пяти элементов И, причем синхронизирующий вход триггера является тактовым входом устройства и подключен к первым входам перво1018123

40

ro и второго элементов И, инверсный и прямой выходы триггера подключены ко вторым входам первого и второго элементов И, выход первого элемента

И попключен ко входу счетчика, выход счетчика подключен к адресному входу блока постоянной памяти, первый, второй и третий выходы блока постоянной памяти подключены к первым входам третьего, четвертого и пятого элементов И соответственно, вторые входы третьего и четвертого элементов И подключены к прямому выходу триггера, третий вход четвертого элемента И "оединен со вторым входом пятого элеФ

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

Известно устройство для быстрого преобразования Фурье, содержащее регистры, сумматоры, коммутаторы и умножитель 1 j.

Недостатком известного устройства является его сложность, обусловленная, в первую очередь, наличием умножителя.

Наиболее близким техническим решением к изобретению является устройство для быстрого преобразования

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

Поскольку сумматоры являются накопительными, они обязательно содержат по паре регистров, ибо результатом

БПФ являются четыре вещественных опе.ранда, составляющие два комплексных.

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

Однако указанное устройство. имеет также сложную конструкцию.

Цель изобретения — упрощение устройства.

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

2 которых являются входами коэффицией.тоэ устройства, четыре регистра, три

;коммутатора, два сумматора и блок

|управления, содержит четвертый комму5 татар, причем входы действительной и ,мнимой частей отсчета входного сигнала устройстэа подключены к первым информационным входам первого и второго коьеиутаторов, выход первого суммато10 ра подключен к информационным входам первого и второго регистров, выход второго сумматора подключен к информационным входам третьего и четвертого регистров, выходы первого и второго регистров, являющиеся выходами действительной и мнимой частей первого результата устройства, подключены к информационным входам третьего коммутатора, выход которого подключен ко второму информационному входу пер20 ваго сумматора, выходы третьего и четвертого регистров, являющиеся вМходами действительной и мнимой частей второго результата устройства, подключены к информационным входам чет25 вертога коммутатора, выход которого подключен ко второму информационному входу эторого сумматора, выход вто, рого регистра подключен ко второму информационному входу второго коммутатара, причем знаковый выход второго регистра соединен с инвертирующим разрядным входом второго коммутатора, выход четвертага регистра подключен ко второму информационному

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

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

Кроме того, блок управления состоит из триггера, счетчика, блока постоянной памяти и пяти элементов И, причем синхронизирующий вход триггера является тактовым входом устройства и подключен к первым входам первого и второго элементов И, инверсный и пря-. мой выходы триггеров подключены ко вторым входам первого и.второго элементов И, выход первого элемента И подключен ко входу счетчика, выход счет,чика .подключен к адресному входу блока постоянной памяти, первый, второй итретий выходы блока постоянной памяти 35 подключены к первым входам третьего, четвертого и пятого элементов И соответственно, вторые входа третьего и четвертого элементов И подключены к прямому выходу тригпера, третий вход 40 четвертого элемента И соединен со вторым входом пятого элемента И, вы- ход которого подключен к инверсному единичному, к инверсному прямому и к счетному входу триггера, третий и второй .входы пятого элемента И являются первым и вторым входами блока управления, выходы первого, второго и третьего элементов И являются соответственно первым, вторым и третьим 50 выходами блока управления, четвертый и пятый выходы блока постоянной памяти являются четвертым и пятым выходами блока управления, выход четвертого элемента И является шестым выходом блока управления. 55

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

1 и 2, регистры 3-6, регистр 7 косинусного весового. коэффициента, ре- .60 гистр 8 синусиого весового коэффйциента, параллельные входы 9 и 10 регистров 7 и 8, блок 11 управления, коммутаторы 12-15, входы 16 и 17 действительной и мнимой частей отсчета 65 входного сигнала, выходы 18-21 устройства, выходы 22-27 блока управления, входы 28 и 29 блока управления. являющиеся последовательными выходами регистров 7 и 8; блок 30 постоянной памяти (ПЗУ), элементк 31-35 И, счетчик 36, выходила 37, 38 и 39 блока

30 постоянной памяти, триггер 40, выход 41 элемента 32 И, инверсный выход

42 триггера 40, синхронизирующий вход 43 триггера 40 (тактовый вход устройства ), прямой выход 44 триггера 40, шина 45 источника единичного „ сигнала.

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

Основу быстрого преобразования Фурье -(БПФ) составляет базовая операция ал горитма

О (Т)=д;(1)+О ° (1с)И; (1)

+.,(k)=O-(I)-О.(k) ; (2) где символом О обозначен комплексный операнд, индекс при символе соответствует номеру итерации, а в скобках указан адрес операнда, М; — комплексный весовой коэффициент, представляе.мый косинусной (R

В» ю (3)

В результате произведение комплексов в (1) и (2) имеет вид: ке(О» (k) W») =йеО» (k) RpW>+QO» Ck) I Wi (4)

1 п(О (Е)И;)-Х,О; (k)R И; -R λ(k) Т, И» (5)

Базовая операция выполняется в такой последовательности: вначале вы:числяются четыре произведения (;(k) ф», ;(k I W;, I O» (k) R W;, R О» (k) QW ), которые затем суммируются в соответствии с выражениями (4),и (5), после чего полученные сумма прибавляются к О. (I) по алгоритмам (1) и (2) . Процесс перемножения, дающий одновременно четыре произведения, длится и командных тактов (иразрядность W ), при этом число тактов основной тактовой серии по шине

43 может быть несколько больше, чем и. Каждый командный такт сопровождается увеИичением кода счетчика 36 (адрес для ПЗУ 30) на единицу. В течение всех и тактов умножения на выходе 37 ПЗУ держится потенциал "0", задавая сумматорам 1 и 2 режим суммирования, на выходе 25 ПЗУ держится потенциал "1", задавая коммутаторам

12 и 13 режим деления на два пропус каемых чисел путем сдвига их вправо на один разряд, на выходе 26 ПЗУ держится "0", замыкая коммутаторы

14 H 15 на первые входы 16 и 17 соответственно, на выходе 38 ПЗУ дер- °

1018123 жится " 1"; разрешая работу элемента 32 И, на выходе 39 ПЗУ держится

"1", разрешая. работу элементов 33 И.

В исходном состоянии в регистры 7 и

8 занесены значения косинуса .(В %;т и синуса Р,„ ;) угла,на который не5 обкодимо повернуть вектор 0; (Y ), зна-:, чения реальной и мнимой частей кото-. рого устанавливаются на шинах 16

: и 17 соответственно. Регистры 36 "сброшены" в "нулевое" состоя- 10 ние. На шины 28 и 29 из регистров 7 и 8 выдаются значения старших разрядов косинусного и синусного весовых коэффициентов. В зависимости от них устанавливаются режимы работы ре-15 гистров 3-6. Потенциал "1" задает ре гистру режим занесения числа по параллельным входам, а потенциал "0" — режим сдвига на его тактовый вход тактового импульса. Предположим, что з начение косинусного разряда равно "1 а синусного - "0". В-этом случае потенциал "1" на шине 28 задает режим занесения в регистры 3 и 5,а потенци-. ал "0" на шине 29 задает режим сдвига регистрам 4 и g. Одновременно в зависимости от потенциалов на шинах

28 и 29 определяется сигнал на выходе

27 блока управления, замыкающий коммутаторы 12 и 13 на первые входы при значении "0", и — на вторые входы при значении "1". В рассматриваемом примере потенциал шины 27 будет равен

"0", поскольку синусный разряд (шина

29) находится в "нулевом" состоянии и запирает элемент 33 И, для которого 35 шина 27 является выходной. Таким образом, коммутаторы 12 и 13 замыкают выходы регистров 3 и 5,установленных в режим занесения, с первыми входами сумматоров 1 и 2 соответственно. Мос-4Q ле прохождения тактового импульса по шинам 23 и 22 в регистры 3 и 5 записываются числа с выходов сумматоров

1 и 2, равные входным операндам К О; и 1 О,. соответственно,. так как на 45 первом такте к ним прибавляются "-нули" из регистров 3 и .5. В регистрах

4 и 6 содержимое сдвигается на разряд вправо, оставаясь равным "0".

Если бы косинусные и синусные раз ряди приняли противоположные значения (т.е. на шину 28 вышел бы потенциал "0", на шину 29 — потенциал "1"), то режимт работы регистров 3, 5 и 4, 6 поменялись бы: регистры 3 и 5 сдвйнули бы соде)ркимые "нули" вправо на один разряд, не изменив фактического состояния, а в регистры 4 и 6 занеслись бы входные операнды; В дальнейшем процесс протекает именно таким образом с той лишь разницей, что за- .60 писывающий регистр добавляет к накопленной в нем и разделенной на два с помощью коммутатора сумме. входной операнд, а регистр осуществляет деление на два своей накопленной суммы путем 65 внутреннего сдвига на разряд вправо без добавления входного операнда.

Если потенциалы на шинах 28 и 29 одновременно равны "0", то все регистры 3-6 выполняют сдвиг .ранее записанных чисел с появлением очередного тактового импульса.

Во всех трех рассмотренных случаяхт.е. при соотношении потенциалов на шинах 28 и 29 "1т0", "0:1" и "От0" все четыре регистра 3-6 срабатывают одновременно, а это значит, что одновременно в этих случаях вычисляются все четыре частичные произведения, и командный такт равен одному фактическому такту серии импульсов по шине 43 °

Это ясно из рассмотрения работы блока управления.

Элемент 32 И во всех трех упомянутых случаях заперт входными "нулями", и поэтому вырабатывает потенциал

"0" на шину 41, подключенную к обоим установочным входам R и Я потенциального триггера 40. Следствием этого является "перекос" триггера 40: оба его плеча вырабатывают потенциалы

"1" на шины 42 и 44. Потенциалы "1" разрешают одновременное прохождение через элементы .34 и 35 И тактового импульса с шины 43 на шины 23 и 22, который и принимается регистрами 3-6.

Случай, когда синхронные разряды косинусного и синусного регистров 7 и 8 находятся в значении "1" оба одновременно, что,приводит к соотношению"1:1 потенциалов на шинах 28 и

29, является особым и последним из числа возможных. Частота его появления меньше, чем любого другого из рассмотренных случаев. В этом случае все числовые регистры 3-6 находятся в режиме занесения. Но поскольку на каждую пару произведений приходится по одному сумматору, занесение выполняется по очереДи следующим образом, при появлении потенциалов "1" на шинах 28 и 29 элемент 32 И пропускает потенциал "1" на шину 41, в результате "перекос" снимается, и триггер 40 устанавливается в "единичное" состояние по счетному входу T ° В результате командный такт процесса вычислений занимает два импульсных такта. При "единичном" состоянии триггера 40 на шину 44 проходит потенциал

"1". Он разрешает прохождение тактового импульса через элемент 34 на шину 23 и одновременно, будучи пропущенным элементом 33 Й на шину 27, замыкает коммутаторы 12 и 13 на вторые входы, т.е. подключает первые входы . сумматоров 1 и 2 к выходам регистров

4 и 6, при этом элемент 35 И заперт.

Таким образом, в первом такте сработают лишь два регистра 4 и 6, записав новые результаты с выходов сумматоров. Задним фронтом первого тактового имттульса триггер 40 переклю1018123. чается в "нулевое" состояние, запирающее элемент 34 И и отпирающее элемент 35 И. Потенциал "0" шины 44 приводит к "обнулению" шины 27, в результате коммутаторы 12 и 13 подключают к первым входам. сумматоров 1 и 5

2 выходы регистров 3 и 5 соответственно. Импульс, пропущенный на шину

22, записывает новый результат в регистры 3 и 5. Этот же импульс, оканчивая .командный такт, производит сдвиг 10 коэффициентов R W„ è I N в регистрах 7 и 8, меняя состоянйе шин 28 и

29, и увеличивает на единицу код счетчика 36.

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

В течение и тактов умножения все разряды регистров. 7 и 8 по мере "вы- талкивания" из них кодов косинуса и синуса заполняются сигналами "1", подаваемыми. на последовательный вход по шине 45. Поэтому> начиная с (и+3)го командного такта на шинах 28 и 29 постоянно существуют потенциалы "1", задавая регистрам 3-6 режим занесения.

На (и+1)-ом комайдном такте ПЗУ - ® выработает: на выходе 37 потенциал

"0", задающий сумматорам 1 и 2 режим суммирования, на.выходе 25 — потенциал "0", задающий коммутаторам 12 и

13 режим пропускания чисел с входа.на, З5 выход без сдвига, на выходе 26 - потенциал "1", замыкающий коммутаторы

14 и 15 на вторые входы, на выходе

38 - потенциал "0", запирающий элемент 32 И и устанавливающий таким 40 образом триггер 40 в состояние "перекоса" независимо от потенциалов на шинах 28 и 29; на выходе 39. — потенциал ".0", обнуляющий шину 27 и замыкающий коююутаторы 12 и 13 на первые 45 входы независимо от потенциалов на шинах 28 и 29. В результате командный такт ° соответствует одному импульсному такту, импульс шины 43 проходит одновременно на шины 23 и 22 и в ре- 50 гистры 3-6 записываются сумяя в соответствии с выражениями (4) и (5) > чем . сумма (4) записывается одновременно в регистры 3 и 4, а разность (5) - в регистры 5 и 7.

Следующий (и+2)-ой такт является последним командным тактом и длится два импульсных такта. ПЗУ 37 при этом вырабатывает: на .выходе 37 — потенциал "1", вследствие чего режим сумматоров 1 и 2 зависит от состояния .триггера 40; на выходе 25 - потенци- .ал "0", отменяющий сдвиг чисел при пропускании их коммутаторами 12 и 13 на выходе 26 — потенциал "0", замыкающий коммутаторы 14 и 15 не первые входы (шииы) 16 и 17; на выходе 38потенциал "1", разрешающий работу элемента 32 И> на выходе 39 — потенць= ал "1", отпирающий элемент 33 И. В

-указанном (n+2)-ом командном такте на входы 16 и 17 устройства вызывается из памяти операнд О (1); причем на вход 16 подается его часть

R<0i(I) а на вход 17 - часть ?,„б (I).

Работа устройства в этом командном такте аналогична случаю выполнения поразрядного умножения при единичном" состоянии обоих синхронных разрядов весового коэффициента с тем различи,ем, что в первом импульсном такте сум-! маторы 1 и 2 выполняют вычитание с ( занесением в регистры 4 и 6 величины (2), а во втором импульсном такте сувматоры 1 и 2 суммируют слагаемые в выражении (1) и результат заносится в регистры 3 и 5.. Режим работы сумматоров 1 и 2 определяется потенциалом на шине 44, который равен "1" в первом импульсном такте (режим вычитания) и "0" во втором импульсном такте (сложение).

В итоге в регистрах 3 и 5 образуются соответственно R<Ор (I) и

I б;+ (1), а в регистрах 4 и 6 образуются соответственно R<0;+„(k) и

1 0<+< (k). На этом обработка текущей пары операндов заканчивается,.и устройство переходит к обработке новой пары, начиная описанный цикл сначала.

Предлагаемое устройство по сравнению с известным имеет более простую конструкцию за счет меньшего числа регистров и сумматоров.

1018123 . Составитель В.Байков .Редактор М.Еелемеш Техред О. Непе Корректор С.Шекмар

Заказ 3546/48. Тираж 706 Подписное

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

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

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