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

(19) (11) А З(59 С 06 Г 15/332 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(71) Киевский ордена Ленина политехнический институт им.50-летия Великой Октябрьской социалистической революции(56) 1. Авторское свидетельство СССР 1( 399859, кл. С Об Е 7/38, 1971.2. Авторское свидетельство СССР У 736 113 з клС Об Р 15/332 1977 (прототип)(54)(57) УСТРОЙСТВО ДЛЯ БЫСТРОГОПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащеевходной регистр чисел, входной регистрвесового коэффициента, информационные входы которых являются входамиустройства, множительный блок, регистр слагаемых, сумматор, четыререгистра результатов и блок управления, о т л и ч а ю щ е е с я тем,что, с целью уменьшения аппаратурных затрат, в него введен элементИЛИ, а блок управления состоит изгенератора синхроимпульсов, счетчика тактов, элемента И, элемента НЕи блока памяти, при этом выход цифровых разрядов регистра весового коэффициента соединен с цифровыми разрядами первого входа множительногоблока, выход знакового разряда регистра весового коэффициента соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен сознаковым разрядом первого входа множительного блока, второй вход которого соединен с выходом входного регистра чисел, выход множительного блока соединен с информационным входом регистра слагаемых, инверсный выход которого соединен с первым информационным входом сумматора, выход которого соединен с информационными входами четырех регистров результатов, выходы ко торых объединены и подключены к выходу устройства и к второму информационному входу сумматора, выход генератора синхроимпульсов блока управления соединен со счетным входом счетчика тактов, выходы разрядов которого соединены с адресными входами блока памяти, выход первого разряда счет- Ж чика тактов соединен с входом приема регистра слагаемых, выход второго разряда счетчика тактов соединен с входом элемента НЕ, выход которого соединен с первым входом элемента И, выход которого соединен с входом уста. новки в "0" счетчика тактов, выходы третьего и четвертого разрядов которого соединены с вторым и третьим входами элемента И, выходы первой группы блока памяти соединены с входами приема входного регистра чисел, входного регистра весового коэффициента, регистра слагаемых и регистров результатов соответственно, выходы второй группы блока памяти соединены с входами выдачи регистров результатов соответственно, выход фр третьей группы блока памяти соединенс с входом установки в "0" входного регистра весового коэффициента и с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы четвертой группы блока памяти соединены с управляющими входами сумматора, 1101836Изобретение относится к вычислительной технике и может быть испальзована при построении устройства, реализующих алгоритм быстрого преобразования Фурье (ВПФ).5Известно устройство, выполняющее операции с комплексными числами. Устройство содержит регистры действительной и мнимой частей сомножителей, формирователи поразрядных произведений, 10 комбинационно-накапливающие сумматоры, блок перевода в дополнительный код 1 .Однако это устройство требует большого объема оборудования, 15Наиболее близким к изобретению по технической сущности является устройства для быстрого преобразования Фурье, содержащее четыре входных регистра чисел и два входных реги стра весового коэффициента, входы которых являются входами устройства, множительный блок, сумматор, коммутатор слагаемых, коммутатор сомножителей, два регистра слагаемых, четы 2 ре регистра произведений и блок управления, первый вход которого соединен с управляющим входом коммутатора слагаемых, второй - с управляющим входом коммутатора сомножителей, выходы регистров весового коэффициента соединены с первыми двумя инФормационными входами коммутатора сомножителей, выходы которого соединены с входами множительного блока выходы которого соединены с входами регистров произведений, выходы которых соединены с первыми четырьмя инФормационными входами коммутатора слагаемых, другие четыре инфарамционных входа которого соединены с выходами входных регистров чисел, выходы коммутатора слагаемых соединены с входами сумматора, выход которого соединен с выходом устройства и с входами регистров слагаемых, выходы которых соединены с третьим и чегвертым информационными входами регистра сомножителей 2.50Недостатком известного устройства являются большие затраты оборудованияКроме того, к недостаткам можно отнести наличие множества входов, чта требует распараллеливания памя- у ти, а это, в свою очередь, приводит к увеличению внешних связей и усложнению адресации либо к необходимости установки распределителя данных на входе устройства.Целью изобретения является уменьшение аппаратурных затрат и числа внешних связей.Поставленная цель достигается тем, чта в устройство для быстрого преобразования Фурье, содержащее входной регистр чисел, входной регистр весового коэффициента, информационные входы которых являются входами устройства, множительный блок, регистр слагаемых, сумматор, четыре регистра результатов и блок управления, введен элемент ИСКЛ 10 ЧЛЮЩЕЕ ИЛИ, а блок управления состоит из генератора синхроимпульсав, четырехразряднага счетчика тактов, э.пемента И, элемента НЕ и микропрограммного блока памяти, при этом выход циФровых разрядов регистра весового коэффициента соединен с цифровыми разрядами первого входа множительного блока, выход знакового разряда регистра весового коэффициента соединен с первым входам элемента ИСКЛЮЧЛЮЩЕЕ ИЛИ, выход которого соединен са знаковым разрядам первого входа множительного блока, второй вход которого соединен с выходам входного регистра чисел, выход множительного блока соединен с информационным входом регистра слагаемьп, инверсный выход которого соединен с первым информационным вхадом сумматора, выход кстараго соединен с информационными входами четырех регистров результатов, выходы которых объединены и подключены к выходу устройства и к второму информационному входу сумматора, выход генератора синхраимпульсов блока управления соединен са счетным входом счетчика тактов, выходы разрядов которого соединены с адресными входами блока памяти, выход первого разряда счетчика тактов соединен с входом приема регистров слагаемых, выход второго разряда счетчика тактов соединен с входам элемента НЕ, выход которого соединен с первым входом элемента И, выход которого соединен с входом установки в "О счетчика тактов, выходы третьего и четвертого разрядов которого соединены с вторым и третьим входами элемента И, выходы первой группы блока памяти соединены с соответствующими входами приема входного регистра чисел, входного регистравесового коэффициента, регистра слагаемых и регистров результатов, выходы второй группы блока памяти сое.динены с входами выдачи регистроврезультатов соответственно, выходтретьей группы блока памяти соединен с входом установки в "0" входного регистра весового коэффициентаи с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы четвертой группы 10блока памяти соединены с входамиуправляющими сумматора.На фиг. 1 представлена структурная схема устройства для быстрогопреобразования Фурье, на фиг. 2 - 15структурная схема блока управления,на фиг. 3 - временная диаграмма,иллюстрирующая работу устройства, нафиг. 4 - блок-схема алгоритма функционирования блока управления,20Устройство для быстрого преобразования Фурье содержит входной регистр 1 чисел, вход которого является первым входом устройства, а вы ход подкпючен к первому входу множительного блока 2, к цифровым разрядам второго входа множительного блока 2 подключены выходы цифровых разрядов и входного регистра 3 весового коэффицента, вход которого является вторым входом устройства. При этом выход знакового разряда регистра 3 весового коэффициента подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4, выход которого соединен с35входом знакового разряда второго вхо.да множительного блока 2, Выход множительного блока 2 соединен с информационным входом регистра 5 слага 40емых, выход которого подключен к первому информационному входу сумматора 6. Выход сумматора 6 соединен с информационным входами четырех регистров 7-10 результатов, вы 45 ходы которых объединены и подключены к второму входу сумматора 6 и к выхо.ду неего устройства. Выходы блока 11 управления соединены с управляющими входами всех регистров (1,3,5, 7-,10), сумматора 6 и с вторым вхо 50 дом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4.Сумматор 6 представляет собой сум. матор с расширенными функциональными возможностями, Требуется, чтобы он вы полнял следующие три операции; сложение, вычитание и пропуск одного ,из операндов без изменений. Непосредственное объединение выходов регистров допуСтимо, если в качестве этих регистров использовать регистры с тремя состояниями на выходе.Блок 11 управления может быть реализован, например, как показано на фиг. 2. Он содержит генератор 12 синхроимпульсов, счетчик 13 тактов, блок 14 памяти, элемент И 15, элемент НЕ 16, причем зыход генератора 12 подключен к счетчному входу четырехразрядного счетчика 13 тактов, выходы соединены с соответствующими входами микропрограммного блока 14 памяти. Кроме того, выход первого (младшего) разряда счетчика 13 тактов является выходом 17 блока управления и соединен с входом приема регистра 5 слагаемых, выход второго разряда счетчика 13 тактов соединен с входом элемента НЕ 16, выход которого соединен с первым входом элемента И 15. Выходы третьего и четвертого разрядов счетчика 13 тактов соединены соответственно с вторым и третьим входами элемента И 15, выход которого соединен с входом установки в "0" счетчика 13 тактов. Выходы блока 14 памяти являются выходами 18-;30 блока 11 управления, причем выход 18 соединен с синхровходом приема регистра 1 чисел, выход 19 соединен с синхровходом приема регистра 3 весового коэффициента, выходы 20-;23 подключены к синхровходам приема регистров 7-10 результатов соответственно, а выходы 24-;27 - соответственно к входам управления выдачей информации тех же регистров 7-,10. Выходы 28 и 29 соединены с входами управления. выполняемой операцией сумматора 6, выход 30 подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 4, и к входу установки в "0" регистра 3 весового коэффициента. На фиг. 4 а и 4 б приняты следующиеусловные обозначения:. г- 1-й такт,3-й - иолутакт, С - результат на выходе сумматора 6, БПФ - момент выдачи результатов преобразования с указанием, какой именно результат выдается, Рг 1 - входной регистр 1 чисел;Рг 3 - входной регистр 3 весового коэффициента; Рг 5 - регистр 5 слагаемых;Рг 7-;Рг 10 - регистры 7-;10 результатов,МО - результат на выходе множительного блока, 1101836Устройство выполняет базовую операцию алгоритма быстрого преобразованияФурье по основанию 2 А;=8+с; Э )Мед,= 8 еВ 0 еСЙеФ(-1,С; 1,М;15=18; г кеС, 1,%11,с; Де%,8 ея;=РеВ-Кес; Цеа 1 с, 1,а;1 б;,=18, кеС, 1,М/"-1 С; Ре 99,10 где В;, С, - исходные отсчеты, АА,1 - преобразованные отсчеты; М - ве - 1.1 ЯЙ,совой коэФфициент, Б = е ";И - количество отсчетов в исходноммассиве; Ке- действительнаячасть числа; 1 - мнимая часть числа,Рассмотрим работу устроиства прин 20выполнении базовой операции. Будемсчитать, что прием информации в регистры осуществляется в момент прихода заднего фронта синхроимпульса.. 25Устройство работает с дополнитель.ными кодами чисел. Из внешней памяти весовые коэффициенты М поступаютпроинвертированными, т.е. (И"(-1Информация на первый вход сумматора 6снимается с инверсных выходов реги 30стра 5 слагаемых, На третий вход самого младшего разряда сумматора б(вход переноса) постоянно заведенсигнал, соответствующий наличию переноса, т.е, "1". 35В конце первого такта по сигналус выхода 18 блока 11 управления вовходной регистр 1 чисел принимается действительная часть КеС; исходногсотсчета С во входной регистр 3 40 весового коэффициента по сигналу с выхода 19,принимается действительная часть КеМ весового коэффициента ЫВо втором такте выполняется умножение в множительном блоке 2 и по сиг 45 налу с выхода 17, в конце такта произведение КеС КеМпринимается в регистр 5. По сигналу с выхода 19 в регистр 3 принимается мнимая часть ,1 И весового коэффициента И".Ф50В третьем такте в множительном блоке 2 выполняется умножение и произведение КеС 1 И по сигналу с выхода 17 принимается в регистр 5 слагаемых. Сумматор 6 по сигналам 55 с выходов 28 и 29 выполняет пропуск ,первого операнда и в регистр 7 по сигналу с выхода 20 принимается произведение КеС;,. РеУ. Во входной регистр 1 чисел по сигналу с выхода 18 принимается действительная часть КеВгисходного отсчета ВВ четвертом такте в множительномблоке 2 выполняется умножение действительной части КеВ, исходного отсчета В 1 на единицу и КеВ без изменений по сигналу с выхода 17 принимается в регистр 5, Умножение наединицу выполняется по сигналу с выхода 30, который устанавливает в "0"содержимое регистра 3, а значениезнакового разряда инвертирует,То естьв качестве множителя подается число1.000, при умножении на котороепроизведение равно множимому. Сумматор б по сигналам с выходов 28 и 29выполняет пропуск первого операндаи в регистр 8 результатов по сигналус выхода 21 принимается произведениеКеС 1 П". Во входной регистр 1 посигналу с выхода 18 принимается мнимая часть 1 В исходного отсчета В.В пятом такте в множительном блоке 2 выполняется умножениеб, наединицу и по сигналу с выхода 17 1 г В,принимается в регистр 5. Во входнойрегистр 1 но сигналу с выхода 18 принимается мнимая часть 1 щ С исходногоотсчета С В регистр 3 весовогокоэффициента по сигналу с выхода 19принимается мнимая часть 1 г, м" весового коэффициента У". По сигналу свыхода 24 из регистра 7 выдаетсяпроизведение КеС, КеЫ . Кроме того,в первой половине пятого такта сумматор 6 выполняет операцию вычитания и в середине такта по сигналус выхода 22 в регистр 9 принимаетсяразность ВеВ -КеС КеЫ, Во второйполовине пятого такта сумматора бпо сигналам с выходов 28 и 29 выполняет операцию слОжения и в концетакта по сигналу с выхода 20 суммаКеВ;ФКеС, КеЫ принимается в регистр 7,В шестом такте в множительном блоке 2 выполняется умножение и произведение 1 С 7 Б по сигналу с выГП 1 Р 1хода 17 принимается в регистр 5, во входной регистр 3 весового коэффициента по сигналу с выхода 19 принимается действительная, часть КеИ весового коэффициента Б". Из регистра 8 по сигналу с выхода,25 выдается произведение КеС; 1 И". Кроме того, 1101836в первой половине шестого такта сумматор 6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в середине такта в регистр 10 по сигналу с выхода 23 принимается раз ность 1 В -КеС 1 И. Во второй половине такта сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 21 в регистр 8 принимается сумма 1 ВКеС1 И. 1 ОъеВ седьмом такте в множительном блоке 2 выполняется умножение и по сигналу с выхода 17 в регистр 5 принимается произведение 1 С КеИ, во входной регистр 1 принимается дей ствительная часть КеС,исходного отсчета С , во входной регистр 3 принимается действительная часть КеИ весового коэффициента И", Кроме1 ф 1того, в первой половине седьмого 20 такта по сигналу с выхода 24 выдается содержимое регистра 7 КеВ;+КеС КеИ, Сумматор 6 по сигналам с выходов 28 и 29 выполняет операцию вычитания и в регистр 7 в середине такта по 25 сигналу с выхода 20 принимается действительная часть КеА,= КеВ; КеС, ГеИ -1 С 1 И". Во второй половине седьмого такта по сигналу с выхода 26 из регистра 9 выдается КеВ, -КеС ,:.еИ", ЗО сумматор 6 выполняет операцию сложения и в конце такта по сигналу с выхода 22 в регистр 9 принимается действительная .часть КеА = КеВ; -КеС КеИ 1 С;1 щИ. В восьмом такте в множительном блоке 2 выполняется,умножение и произведение КеС; КеИн 1(И по сигналу с выхода 17 принимается в регистр 5, во входной регистр 3 по сигналу с выхода 19 при О нимается мнимая часть 1Ивесового коэффициента И . Кроме того, в первой половине восьм го такта из регистра 10 по сигналу с выхода 27 выдается 1 В" - КеС 1 И , сумматор 45 б по сигналам с выходов 28 и 29 выполняет операцию вычитания и в середине такта по сигналу с выхода 23 в регистр 10 принимается мнимая, часть 1,А; = 1,В -КеС 1 И"- 1,С КеИ, Во второй половине восьмого такта из регистра 8 по сигналу с выхода 25 выдается 1 В, КеС, 1 И, сумматор 6 вылполняет операцию сложения и по сигналу с выхода 21 в регистр 8 принимается мнимая часть 1 А = 1 В КеС .Т Иффщ 1 а 1 1 щ ф 1 С. КеИ. В девятом такте в множи 1 Ътельном блоке 2 выполняется умножение и произведение КеС 1 И по сигйналу с выхода 17 принимается в регистр 5 слагаемых, сумматор 6 по сигналам с выходов 28 и 29 выполняет пропуск первого операнда, произведение КеС; КеИ по сигналу с выхода 20 принимается в регистр 7. Во входной регистр 1 принимается действительная часть КеВ; исходного отсчета В;Кроме того, в первой половине девятого такта из регистра 7 на выход устройства по сигналу с выхода 24 выдается КеА,. Во второй половине девятого такта по сигналу с выхода 25 на выход устройства выдается мнимая часть 1 А;.В десятом такте в множительном блоке 2 выполняется умножение действительной части КеВ;,на единицу и по сигналу с выхода 17 КеВ, принимается в регистр 5, во входной регистр 1 по сигналу с выхода 18 прини мается мнимая часть 1, 8;,исходного отсчета В;. Кроме того, в первой половине десятого такта по сигналу с выхода 26 из регистра 9 на выход устройства выдается действительная часть КеА;д, а во второй половине десятого такта на выход устройства по сигналу с выхода 27 выдается мнимаяДалее работа всего устройства аналогична.Таким образом, по сравнению с известным устройством предлагаемое устройство при той же производительности имеет на пять регистров и два сумматора меньше.Кроме того, известное устройство имеет шесть входов, тогда как предлагаемое устройство только два, что существенно уменьшает число внешних связей и позволяет работать с линейно организованной памятью.=1 пзС 1, 1 щЫ Составитель А. ФедороТехред Т. Маточка ректор В. Бутя аж 699венного комитет тений и открыти 35 Раущская на дписно Заказ 4769/33 и ВНИИПИ Государст а ССС по делам изобре й13035, Москва, Ж- б д 4/5 Проектная, 4 илиал ЛПП "Патент", г. Ужгород,С=Рг 5- Рг 9Рг 9=0Рг 1= йеСьРг 3 =ее И 1Рг 5=г 10 С=Рг 50 П Ф = Рг 8 =21,-2Рг 7= СРг 1= йеВ 1,Рг 5=МО=йЕСь 1 Ы Редактор В. Иванова С= Рг 5ВПФ= РгРгб=СРг 5 =М С= Рг 5+Рг 7Рг 7=СРг 5=М 0=1 т бсРг 3=1 а ЫРг 1=1 е С 1,С= Рг Рг 8= .Рг 5= Р 3=