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

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

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

Изобретение относится к автоматике и вычислительной технике и может, использоваться в процессорах для oneктральнокорреляционнбго анализа виброакустических сигналов. Известно устройство для быстрого преобразования Фурье, содержащее регистры, сумматоры, коммутаторы и умножитель С1 Недостатком известного устройства является его сложность, обусловленная , в первую очередь, наличием умно жителя. Наиболее близким техническим ремением к изобретению является устройство для быстрого преобразования Фурье, в состав которого входят регистры синусной и косинусных частей комплексного весового коэффициента, два числовых регистра, четыре сумматора, и три логических блока, выполня ющих функции коммутаторов. Поскольку сумматоры являются нако пительными , они обязательно содержат по паре регистров, ибо результатом БПФ являются четыре вещественных one ранда, составляющие два комплексных. Таким образом, в устройстве-прототипе можно выделить четыре сумматора, шесть регистров, два регистра весовых коэффициентов, четыре коммутатора. В этом устройстве операция умножения заменена последовательным сложением поразрядных произведений, что позволяет исключить сложный блок, каким является умножитель (23. Однако указанное устройство.имеет также сложную конструкцикг. Цель изобретения - упрощение устройства. Поставленная цель достигается тем, что устройство для быстрого преобразования Фурье, содержащее регистры синусного и косинусного весовых коэффициентов, параллельные вход которых являются входами коэффициен.тов устройства, четыре регистра, три коммутатора/ два сумматора и блок управления, содержит четвертый коммутатор, причем входа действительной и мнимой частей о.тсчета входного сигнала устройства подключены к первым информационным входам первого и второго кокфлутаторов, выход первого сумматора подключен к информационным входам первого и второго регистров, выход второго сулфлатор.а подключен к информационньо входам третьего и четвертого регистров, выходы первого и второГО регистров, являющиеся выходами действительной и частей первого результата устройства, подключены к информационным входам третьего коммутатора, выход-которого подключен ко второму информационному входу первого сумматора, выхода третьего и четвертого регистров, являющиеся выходами действительной и мнимой частей вторюго результата устройства, подключены к информационным входам четвертого коммутатора, выход которого подключен ко второму информационному входу второго сумматора, выход второго регистра подключен ко второму информационному входу второго коммутатора, причем знаковый выход второго регистра соединен с инвертирующим разрядным входом второго коммутатора, выход четвертого регистра подключен ко второму информационному входу первого коммутатора, последовательные входы регистров синусного и косинусного весовых коэффициентов подключены к источнику единичного сигнала, последовательный выход регистра косинусного весового коэффициентасподключен к управлякицим входам первого и третьего регистров и к первому входу блока управления, последовательный выход регистра

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

входного сигнала, выходы 18-21 устройства, выходы 22-27 блока управления, входы 28 и 29 блока управления, являющиеся последовательными выходами регистров 7 и 8, блок 30 постоянной памяти (ПЗУ), элементы 31-35 И, счетчик 36, выходы 37, 38 и 39 блока 30 постоянной памяти, триггер 40, выход 41 элемента 32 И, инверсный выход 42 триггера 40, синхронизирующий вход 43 триггера иО (тактовый вход устройства ), прямой выход 44 триггера 40, шина 45 источника единичного г сигнала.

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

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

1 flCl

0(I)i(I)6.(k)W

(1) 0-,(lc)6.(I)-n.(k)W-) (2) где символом О обозначен комплексный операнд, индекс при символе соответствует номеру итерации,,а в скобках указан адрес операнда, W- - комплексный весовой коэффициент, представляемыК косинусной () и crfHycнoй () частями, связанными (в случае прямого БПФ) выражением , В результате произведение комплексов в (1) и (2) имеет вид: R€ (О,- (1) W iO Re О i Ck) Rp,W- +1„,0 (k) ,I(0.(k),0(k)RgW,--ReOj(k)VV Базовая операция выполняется в та;кой последовательности; вначале вычисляются четыре произведения ())ImWt )RcW, RgO (k) ) , которые затем суммируются в соответствии с выражениями (4) .и (5), после чего полученные суммы прибавляются к О.(1) по алгоритмам (1) и (2). Процесс перемножения, дающий одновременно четыре произведения, длится п командных тактов tn разрядность W), при этом число тактов основной тактовой серии по шине 43 может быть несколько больше, чем п. Каждый командный такт сопровождается увеличением кода счетчика 36 (ajsjec для ПЗУ 30) на единицу. В течение всех п тактов умножения на выходе 37 ПЗУ держится потенциал О, задавая сумматорам 1 и 2 режим суммирования, на выходе 25 ПЗУ держится потенциал 1, задавая коммутаторам 12 и 13 режим деления на два пропускаемых чисел путем сдвига их вправо на один разряд, на выходе 26 ПЗУ держится О, замыкая коммутаторы 14 и 15 на первые входы 16 и 17 соответственно, на выходе 38 ПЗУ дер-

жится разрешая работу элемента 32 И, на выходе 39 ПЗУ держится 1, разрешая, работу элементов 33 И. В исходном состоянии в регистры 7 и 8 занесены значения косинуса () и синуса угла, на который необходимо повернуть вектор д-(У),зна чения реальной и мнимой частей которого устанавливаются на шинах 16 .и 17 соответственно. Регистры 36 сброшены в нулевое состояние. На шины 28 и 29 из регистров 7 и 8 выдаются значения старших разрядов косинусного и синусного весовых коэффициентов, В зависимости о них устанавливаются режимы работы ре гистров 3-6. Потенциал 1 задает регистру режим занесения числа по паралельным входам, а потенциал О - режим сдвига на его тактовый вход тактового импульса.Предположим,что зна-чение косинусного разряда равно 1 , а синусного - О. В-.этом случае потенциал 1 на шине 28, задает режим занесения в регистры 3 и 5,а потенциал О на шине 29 задает сдайга регистрам 4 и . Одновременно в зависимости от потенциалов на шинах 28 и 29 определяется сигнал на выход 27 блока управления, замыкающий коммутаторы 12 и 13 на первые входы при значении О, и - на вторые входы при значении 1. В рассматриваемом примере потенциал шины 27 будет равен О, поскольку синусный разряд (шина 29) находится в нулевом состоянии запирает элемент 33 Н, для которого шина 27 является выходной. Таким образом, коммутаторы 12 и 13 эа.мыкают выходы регистров 3 и 5,установленных в режим занесения, с первыми входами сумматоров 1 и 2 соответственно. Пос ле прохождения тактового импульса по шинам 23 и 22 в регистры 3 и 5 записываются числа с выходов сумматоров 1 и 2, равные входным операндам RgO,и . соответственно, так как на первом такте к ним прибавляются нули из регистров 3 и 5. В регистрах 4 и 6 содержимое сдвигается на разряд вправо, оставаясь равным О.

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

внутреннего сдвига на разряд вправо без добавления входного операнда.

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

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

Элемент 32 И во всех трех упомянутых случаях заперт входными нулями, и поэтому вырабатывает потенциал О на шину 41, подключенную к обоим установочным входам R и S потенциального tpHrrepa 40. Следствием этого является перекос триггера40: оба его плеча вырабатывают потенциалы 1 на шины 42 и 44. Потенциалы 1 разрешают одновременное прохождение через элементы .34 и 35 И тактового импульса с шины 43 на шины 23 к 22, который и принимается регистрами 3-6.

Случай, когда синхронные разряда косинусного и синусного регистров 7 и 3 находятся в значении 1 оба одновременно, что .приводит к соотношению 1:1 потенциалов на шинах 28 и 29, является особьгм и последним из числа возможных. Частота его появления меньше, чем любого другого из рассмотренных случаев. В этом случае все числовые регистры 3-6 находятся в режиме«занесения. Но поскольку на каждую пару произведений приходится по одному сумматору, занесение выполняется по очереди следукядим образом.

При появлении потенциалов 1 на шинах 28 и 29 элемент 32 И пропускает потенциал 1 на шину.41, в резу/1ьтате перекос снимается, и триггер4б устанавливается в единичное состояние по счетному входу Т. В результате командный такт процесса вычислений занимает два импульсных такта. При единичном состоянии триггера 40 на шину 44 проходит потенциал 1. Он разрешает прохождение тактового импульса через элемент 34 на шину 23 и одновременно, будучи пропущенным элементом 33 И на шину 27, за1уыкает коммутаторы 12 и 13 на вторые входы, т.е. подключает первые входысумматоров 1 и 2 к выходам регистров 4 и 6, при этом элемент 35 Л заперт.

Таким образом, в первом такте сработают лишь два регистра 4 и 6, записав новые результаты с выходов сумматоров. Задним фронтом первого тактового импульса триггер 40 переключается в нулевое состояние, эапиракицее элемент34 И и отпирающее элемент 35 И. Потенциал О шины 44 приводит к обнулению шины 27, в результате коммутаторы 12 и 13 подключают к первым входам- сумматоров 1 и 2 выходы регистров 3 и 5 соответственно. Импульс, пропущенный на шину 22, записывает новый результат в регистры 3 и 5. Этот же импульс, оканчивая командный такт, производит сдвиг коэффициентов и в регистрах 7 и 8, меняя состояние шин 28 и 29, и увеличивает на единицу код счетчика 36.

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

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

На (n+t)-oM KOMaifflHOM такте ПЗУ выработает: на выходе 37 потенциал О, задающий сумматорам 1 и 2 режим суммирования, на вйходе 25 - потенциал О, задающий коммутаторам 12 и

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

14и 15 на вторые входы) на выходе 38 - потенциал О, запирающий элемент И и устанавливающий таким образом триггер 40 в состояние перекоса независимо от потенциалов на шинах 28-и 29) на выходе 39 - потенциал О, обнуляющий шину 27 и замакающий ко1«1утаторы 12 и 13 на первые входы независимо от потенциалов на шинах 28 и 29. В результате командный такт.соответствует одному импульсному такту,.импульс шины 43 проходит одновременно на шины 23 и 22 и в регистры З-б записываются суммы в соответствии с выражениями (4) и (5),причем сумма (4) записывается одновременно в регистры 3 и 4, а разность (5) - в регистры 5 и 7.

Следующий (п-«-2)-ой такт является последним командным тактом и длится два имгтульсных такта. ПЗУ 37 при этом вырабатывает: на выходе 37 - потенциал

вследствие чего режим сумматоров 1 и 2 зависит от состояния iTpHrrepa 40; на вмходе 25 - потенциотменяющий сдвиг чисел при

.ал

пропускании их коммутаторами 12 и 13(, на выходе 26 - потенциал О, замлкающий коммутаторы 14 и 15 на первые входы (шины) 16 и 17; на выходе 38 потенциал 1, разрешающий работу элемента 32 И на выходе 39 - потенциал 1, отпирающий элемент 33 И. В .указанном (п+2)-ом командном такте на входы 16 и 17 устррйства вызывается из памяти операнд 0(1), причем на вход 16 подается его часть RgOj (1), а на вход 17 - часть 1,„(Т(1) Работа устройства в этом командном такте аналогична случаю выполнения поразрядного умножения при единичном состоянии обоих синхронных разрядов весового коэффициента с тем различием, что в первом импульсном такте сум1маторы 1 и 2 выполняют вычитание с занесением в регистры 4 и б величины (2), а во втором импульсном такте сумматоры 1 и 2 суьфшруют слагаемое в выражении (1) и результат заносится в регистры 3 и 5,- Режим работы сумматоров 1 и 2 определяется потенциалом на шине 44, который равен 1 в первом иишульсном такте (режим вычитания) и 0 во втором импульсном такте (сложение).

В итоге в регистрах 3 и 5 образуются соответственно RgOij (I) и (1), а в регистрах 4 и б образуются соответственно (l) и (J этом обработка текущей пары операндов заканчивается,, и устройство переходит к обработке новой пары, начиная описанный цикл сначала.

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