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

ЗЕВС 0 ОПИСАНИ К АВТОРСКОМУ ЕТЕНИУ БР СТВ во ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Специальное конструкторское бюро фВиброприбор"(56) 1. Авторское свидетельство СССРВ 736113, кл. С 06 Р 15/332, 22,11.77.2. Авторское свидетельство СССРР 467356, кл. 6 06 Р 15/332,25.0374.(54)(57) 1. УСТРОЙСТВО ДЛЯ БЬИ:ТРОГОПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее регистры синусного и косинусного весовыхкоэффициентов, параллельные входыкоторых являются входами коэффициен-.тов устройства, четыре регистра, трикоммутатора, два сумматора к блок управления, о т л и ч а ю щ е е с ятем, что, с целью упрощения устройства, оно содержит четвертый коммутатор, причем входы действительной имнимой частей отсчетавходного сигна=ла устройства подключены к первыминформационным входам первого и вто.: рого коммутаторов, выход первогосумматора подключен к информационнымвходам первого и второго регистров,выход второго сумматора подключен кинформационным входам третьего ичетвертого регистров, выходы первогои второго регистров, являющиеся выходами действительной.и мнимой частейпервого результата устройства, под-.ключены к информационным входам третьего коммутатора, выход которогоподключен ко второму информационномувходу первого сумматора, выходытретьего и четвертого регистров, являющиеся выходами действительной имнимой частей второго результата,устройства, подключены к информационным .входам четвертого коммутатора,выход которого подключен ко второмуинформационному входу второго сумматора, выход второго регистра подключен ко второму информационному входу второго коммутатора, причем знаковый выход второго регистра соединен с инвертирующим разрядным входом второго коммутатора, выход четвертого регистра подключен ко второму информационному входу первого коммутатора, последовательные входы регистров синус- ного и косинусного весовых коэффициентов подключены к источнику единичного сигнала; последовательный выход регистра косинусного весового коэффициента подключен к управляющим входам первого и третьего регистров и к первому входу блока управления, д :последовательный выход регистра синус Е сного весового коэффициента подклю-, чен к управляющим входам второго и четвертого регистров и ко второму входу блока управления, первый выход блока управления подключен к тактовым входам первого и третьего регйстров и к тактовым входам регистров синусного и косинусного весовых коэффициентов, второй выход блока управления подключен к тактовым входам второго и четвертого регистров, третий выход блока управления подключен к управляющим входам ,первого и второго сумматоров, четвертый выход блока управления подключен к управляющим входам сдвига третьего и четвертого коммутаторов, пятый выходблока управ-; ления подключен к управляющим входам первого и второго коммутаторов, шестой выход рлока управления подключен к переключающим входам третьего и четвертого коммутаторов,2; Устройство по п.1, о т л и ч аю щ е е с я тем, что блок управления состоит из триггера, счетчика, блока постоянной памяти и пяти элементов И, причем синхронизирующий вход триггера является тактовым входом устройства и подключен к первым входам пер1018123 30 40 го и второго элементов И, инверсныйи прямой выходы триггера подключеныко вторым входам первого и второгоэлементов И, выход первого элементаИ попключен ко входу счетчика, выходсчетчика подключен к адресному входублока постоянной памяти, первый, второй и третий выходы блока постояннойпамяти подключены к первым входамтретьего, четвертого и пятого элементов И соответственно, вторые входытретьего и четвертого элементов Иподключены к прямому выходу триггера,третий вход четвертого элемента Исоединен со вторым входом пятого элеИзобретение относится к автоматике и вычислительной технике и можетиспользоваться в процессорах дляспектральнокорреляционного анализавиброакустических сигналов.Известно устройство для быстрогопреобразования Фурье, содержащее регистры, сумматоры, коммутаторы и умножитель 1 .Недостатком известного устройстваявляется его сложность, обусловленная, в первую очередь, наличием умно- жителя.Наиболее близким техническим решением к изобретению является устройство для быстрого преобразованияФурье, в состав которого входят регистры синусной и косинусных частейкомплексного весового коэффициента,два числовых регистра, четыре сумматора и три логических блока, выполняющих функции коммутаторов.Поскольку сумматоры являются накопительными, они обязательно содержат по паре регистров, ибо результатом БПФ являются четыре вещественных операнда, составляющие два комплексных, Таким образом, в устройстве-прототипе можно выделить четыре сумматора, шесть регистров, два регистра весовых коэффициентов, четыре коммутатора. В этом устройстве операция умножения заменена последовательным сложением поразрядных произведений,:что позволяет исключить сложный блок, каким является умножитель 2 ).Однако указанное устройство. имеет также сложную конструкцию.Цель изобретения - упрощение устройства.Поставленная цель достигается тем, что устройство для быстрого преобразования Фурье, содержащее регистры синусного и косинусного весовых коэффициентов, параллельные входы мента И, выход которого подключен кинверсному единичному, к инверсномупрямомуи к счетному входу триггера,третий и второй входы пятого элемента И являются первым и вторым входамиблока управления, выходы первого, вто-рого и третьего элементов И являютсясоответственно первым, вторым и третьим выходами блока управления, четвертый и пятый эыходы блока постоянной памяти являются четвертым и пятымвыходами блока управления, выход четвертого элемента И являетсяшестым выходом блока управления. 2которых являются входами коэффицией.тоэ устройства, четыре регистра, три ;коммутатора, два сумматора и блок управления, содержит четвертый комму 5 татор, причем входы действительной и,мнимой частей отсчета входного сигнала устройстэа подключены к первым информационным входам первого и второгокоьеиутаторов, выход первого суммато ра подключен к информационным входампервого и второго регистров, выходвторого сумматора подключен к информационным входам третьего и четвертого регистров, выходы первого и второго регистров, являющиеся выходамидействительной и мнимой частей первого результата устройства, подключенык информационным входам третьего коммутатора, выход которого подключенко второму информационному входу пер вого сумматора, выходы третьего ичетвертого регистров, являющиеся эМходами действительной и мнимой частейвторого результата устройства, подключены к информационным входам чет вертого коммутатора, выход которогоподключен ко второму информационномувходу эторого сумматора, выход вто, рого регистра подключен ко второму информационному входу второго коммутатора, причем знаковый выход второго регистра соединен с инвертирующимразрядным входом второго коммутатора, выход четвертого регистра подключен ко второму информационному35 входу первого коммутатора, паследовательные входы регистров синусного и косинусного весовых коэффициентов подключены к источнику единичного сигнала, последовательный выход регистра косинусного весового коэффициентасподключен к управляющим входам первого и третьего регистров ик первому входу блока управления,последовательный выход регистра,синусного весового коэффициента подключен к управляющим входам второгои четвертого регистров и ко второмувходу блока управления,. первый выходблока управления подключен к тактовымвходам первого и третьего регистров 5и к тактовым входам регистров синус.ного и косинусного весовых коэффициентов, второй выход блока управленияподключен к тактовым входам второгои четвертого регистров, третий выход 10блока управления подключен к управляющим входам первого и второго сумматоров четвертый выход блока управления подключен к управляющим входамсдвига третьего и четвертого коммутаторов, пятый выход блока управленияподключен к управляющим входам первого и второж коммутаторов, шестой выход блока управления подключен к переключающим входам третьего и четвер того коммутаторов. Кроме того, блок управления состоит из триггера, счетчика, блока постоянной памяти и пяти элементов И, причем синхронизирующий вход триггера является тактовым входом устройства и подключен к первым входам первого и второго элементов И, инверсный и пря-. мой выходы триггеров подключены ко вторым входам первого и.второго эле- .З ментов И, выход первого элемента И подключен ко входу счетчика, выход счет,чика .подключен к адресному входу блока постоянной памяти, первый, второй и . третий выходы блока постоянной памяти35 подключены к первым входам третьего, четвертого и пятого элементов И соответственно, вторые входа третьего и четвертого элементов И подключены к прямому выходу тригвера, третий вход 41 четвертого элемента И соединен со вторым входом пятого элемента И, вы- ход которого подключен к инверсному единичному, к инверсному прямому и к счетному входу триггера, третий и второй входы пятого элемента И являются первым и вторым входами блока управления, выходы первого, второго и третьего элементов И являются соответственно первым, вторым и третьим выходами блока управления, четвертый и пятый выходы блока постоянной памяти являются четвертым и пятым выходами блока управления, выход четвертого элемента И является шестым выходом блока управления. 55На чертеже представлена Функциональная схема предложенного устройства. Устройство содержит сумматоры 1 и 2, регистры 3-6, регистр 7 косинусного весового. коэффициента, ре гистр 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) +О; (3 с) 6(; (1)+=О;(1)-О Жф; (2)где символом О обозначен комплексный операнд, индекс при символе соответствует номеру итерации, а в скобках указан адрес операнда, М; - комплексный весовой коэффициент, представляе,мый косинусной (ВИ ) и сийусной (1 И;) частями, связанными (в случае прямого БПФ) выражением"= е" -щ" (3) В результате произведение комплексов в (1) и (2) имеет вид:йе (О (К) М) =й О (1) йР М + 160 (ф) 1 ФН(5)Базовая операция выполняется в такой последовательности: вначале вычисляются четыре произведения (В,Р) й, 1 Р 1 , 1 О (1 с) йИ;, е 0 (Ц 1 дИ,), которые затем суммируются в соответствии с выражениями (4),и (5), после чего полученные суммю прибавляются к 0.(1) по алгоритмам (1) и (2). Процесс перемножения, дающий одновременно четыре произведения, длится и командных тактов (и- разрядность И), при этом число тактов основной тактовой серии по шине 43 может быть несколько больше, чем и. Каждый командный такт сопровождается увеИичением кода счетчика 36 (адрес для ПЗУ 30) на единицу. В течение всех и тактов умножения на выходе 37 ПЗУ держится потенциал "0",задавая сумматорам 1 и 2 режим суммирования, на.выходе 25 ПЗУ держится потенциал "1 ф, задавая коммутаторам 12 и 13 режим деления на два пропускаемых чисел путем сдвига их вправо на один разряд, на выходе 26 ПЗУдержится "Оф, замыкая коммутаторы14 и 15 на первые входы 16 и 17 соответственно, на выходе 38 ПЗУ дер-жится "1"; разрешая работу элемента 32 И, на выходе 39 ПЗУ держится "1", разрешая. работу элементов 33 И. В исходном состоянии в регистры 7 и8 занесены значения косинуса (В%; и синуса Р,Р;) угла,на который не 5 обкодимо повернуть вектор О;(К),зна-; чения реальной и мнимой частей кото-, рого устанавливаются на шинах 16 :и 17 соответственно, Регистры 3- 6 "сброшены" в "нулевое" состоя ние. На шины 28 и 29 из регистров 7 и 8 выдаются значения старших разрядов косинусного и синусного весовых коэффициентов, В зависимости от них устанавливаются режимы работы регистров 3-6. Потенциал "1 ф задает регистру режим занесения числа по параллельным входам, а потенциал "0" - режим сдвига на его тактовый вход тактового импульса. Предположим, что з начение косинусного разряда равно "1 а синусного - "0", В этом случае потенциал "1" на шине 28 задает режим занесения в регистры Зи 5,а потенци-.л "0 на шине 29 задает режим сдви га регистрам 4 и . Одновременно в зависимости от потенциалов на шинах 28 и 29 определяется сигнал на выходе 27 блока управления, замыкающий коммутаторы 12 и 13 на первые входы при значении "0", и - на вторые входы при значении "1". В рассматриваемом примере потенциал шины 27 будет равен "0", поскольку синусный разряд шина 29) находится в "нулевом" состоянии и запирает элемент 33 И, для которого 35 шина 27 является выходной, Таким об разом, коммутаторы 12 и 13 замыкают выходы регистров 3 и 5,установленных в режим занесения, с первыми входами сумматоров 1 и 2 соответственно. После прохождения тактового импульса по - шинам 23 и 22 в регистры 3 и 5 записываются числа с выходов сумматоров 1 и 2, равные входным операндам В,О; и 1 О,. соответственно,. так как на 45 первом такте к ним прибавляются "нули" из регистров 3 и 5. В регистрах 4 и 6 содержимое сдвигается на разряд вправо, оставаясь равным 10".Если бы косинусные и синусные раз ряди приняли противоположные значения т.е, на шину 28 вышел бы потенциал "О", на шину 29 - потенциал "1"), то режим работы регистров 3, 5 и 4, 6 поменялись бы: регистры 3 и 5 сдвйнули бы содеркимые "нули" вправо на один разряд, не йэмеиив фактического состояния, а в регистры 4 и 6 занеслись бы входные операнды; В дальнейшем процесс протекает именно таким образом с той лишь разницей, что за-,60 писывающий регистр добавляет к накопленной в нем и разделенной на два с помощью коммутатора сумме. входной операнд, а регистр осуществляет деление на два своей накопленной суммы путем 6 внутреннего сдвига на разряд вправо без добавления входного операнда.Если потенциалы на шинах 28 и 29 одновременно равны "О", то все регистры 3-6 выполняют сдвиг ранее записанных чисел с появлением очередного тактового импульса.Во всех трех рассмотренных случаяхт.е. при соотношении потенциалов на шинах 28 и 29 "1 сО", "0:1" и фО:О" все четыре регистра 3-6 срабатывают одновременно, а это значит, что одновременно в этих случаях вычисляются все четыре частичные произведения, и командный такт равен одному фактическому такту серии импульсов по шине 43Это ясно из рассмотрения работы блока управления.Элемент 32 И во всех трех упомянутых случаях заперт входными "нулями", и поэтому вырабатывает потенциал"0" на шину 41, подключенную к обоим установочным входам к и Я потенциального триггера 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, в результате наперекос" снимается, и триггер 0 устанавливается в "единичное" состояние по счетному входу Т. В результате командный такт процесса вычислений занимает два импульсных такта. При "единичном" состоянии триггера 40 на шину 44 проходит потенциал "1". Он разрешает прохождение тактового импульса через элемент 34 на шину 23 и одновременно, будучи пропущенным элементом ЗЗ Й на шину 27, замыкает коммутаторы 12 и 13 на вторые входы, т.е. подключает первые входы сумматоров 1 и 2 к выходам регистров 4 и 6, при этом элемент 35 И заперт.Таким образом, в первом такте сработают лишь два регистра 4 и 6, записав новые результаты с выходов сумматоров. Задним фронтом первого тактового импульса триггер 40 переклю, Составитель В.БайковМ. Еелемеш Техред О.Неце Корректор С.Шекмар едакт ак филиал ППП "Патентф, г.ужгород, ул.Проект 46/48.Тираж 706 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, Р чф