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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 51) 5 06 ) 15 332 ГОСУД АРС ПО ДЕЛАМ ННЫЙ КОМИТЕТ СОБРЕТЕНИЙ И ОТКРЫТ ОПИСАНИЕ ИЗОБРЕТ ВТОРСН СВИД ЬСТВ(56) 1. Оппенгейм Э. Проной обработки сигналММир , 1980, фиг2, Авторское свидет9 421994, кл,06 1 1(прототип),(54) (57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИАЛГОРИТМА БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ, содержащее регистры действительной и мнимой частей операнда,регистры действительной и мнимойчастей весового коэффициента, четыре умножителя и шесть сумматоров,причем входы регистров действительной и мнимой частей весового коэффициента являются нходами действительйой и мнимой частей весовогокоэфФициента устройства, о т л ич а ю щ е е с я тем, что, с цельюповышениЛ быстродействия устройства,оно содержит два коммутатора и дешифратор, причем вход действительнойчасти первого операнда устройствасоединен с входом регистра действительной части операнда, входы мнимой.части первого операнда и дейстнительной части второго операнда устройства соединены .с информационными входами первого и второго коммутаторон,выход первого коммутатора подключенк первым входам первого и второго умножителей, выход второго коммутатора подключен к входу регистра мнимой части операнда, вход мнимой части второго операнда устройства соединен с первыми входами третьего и четвертого умножителей, ныход регистра действительной части весового коэффициента подключен к вторым входам первого и четвертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и второго коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго и третьего умножителей, выходы первого и третьего умножителей подключены к входам первого сумматора, выходы второго и четвертого умножителей подключены к входам второго сумматора, выход регистра действительной части операнда подключен к первым входам третье. го и четвертого сумматоров, выход Я регистра мнимой части операнда подключен к первым входам пятого и шестого сумматоров, выход первого сумматора подключен к вторым входам третьего и четвертого сумматоров, выход второго сумматора подключен к вторым входам пятого и шестого сумматоров, выходы четнертого и шестога сумматоров являются выходами действительной и мнимой частей первого резуль 1 тата устройства, выходы третьего и пятого сумматоров являются ныходами действительной и мнимой частей нторо го реэультата устройства, 1078434Изобретение относится к автоматике и вычислительной технике и можетбыть использовано для вычисленияспектра сигналов и их фильтрации вчастотной области в системах связи,навигации, телеметрии и других областях техники,Известно устройство для выполнения быстрого преобразования Фурье,которое содержит сумматоры и блокумножения на комплексный весовой10коэффициент (1,Наиболее близким техническим решением к изобретению является устройство для реализации алгоритма быстрого преобразования Фурье, содержащее 15четыре умножителя, шесть сумматоров,регистры действительной и мнимой частей операндов, регистры действительной и мнимой частей весового коэффициента, причем выходы регистров действительной и мнимой частей весовогокоэффициента соединены с первыми вхо.дами умножителей с первого по четвертый, вторые входы которЫх соединены с выходами регистров действительной и мнимой частей первого ивторого операндов, выходы с третьего по шестой сумматоров соединенысо сдвигающими входами регистровоперандов 2),30Недостатком известных устройствявляется низкое быстродействие из"заизбыточного общего количества арифметрических операций,Цель изобретения - повышениебыстродействия устройства,Поставленная цель достигаетсятем, что устройство для реализации алгоритма быстрого преобразования Фурье, содержащее регистрыдействительной и мнимой частей операнда, регистры действительной имнимой частей весового коэффициента, четыре умножителя и шесть сум"маторов, причем входы регистровдействительной и мнимой частей весового коэффициента являются входами дейст,;ительной и мнимой частейвесового коэффициента устройства,содержит два коммутатора и дешифратор, причем вход действительной 50части первого операнда устройствасоединен с входом регистра действительной части операнда, входымнимой части первого операнда идействительной части второго операнда устройства соединены с ин. Формационными входами первого ивторого коммутаторов, выход перво-го коммутатора подключен к первымвходам первого и второго умножителей, выход второго коммутатора подключен к входу регистра мнимой,части операнда, вход мнимой части второго операнда устройства соединенс первыми входами третьего и четвертого умножителей, выход регистра 65 действительной части весового коэффициента подключен к вторым входам первого и четвертого умножителей, а также к входу дешифратора, выход которого подключен к управляющим входам первого и второго коммутаторов, выход регистра мнимой части весового коэффициента подключен к вторым входам второго и третьего умножителей, выходы первого и третьего умножителей подключены к входам первого сумматора, выходы второго и четвертого умножителей подключены к входам второго сумматора, выход регистра действительной частиоперанда под- ключен к первым входам третьего и четвертого сумматоров, выход регистра мнимой части операнда подключен к первым входам пятого и шестого сум.- маторов, выход первого сумматора под ключен к вторым входам третьего и четвертого сумматоров, выход второго сумматора подключен к вторым входам пятого и шестого сумматоров, выходы четвертого и шестого сумматоров являются выходами действительной и.мнимой частей первого результата устройства, выходы третьего и пятого сумматоров являются выходами действительной и мнимой частей второго результата устройства.На чертеже приведена функциональная схема устройства для реализации алгоритма быстрого преобразования Фурье.Устройство содержит коммутаторы 1 и 2, регистры 3 и 4 действительной и мнимой частей операнда, регистры 5 и б действительной и мнимой частей весового коэффициента, умножители 7-10, сумматоры 11-1 б, дешифратор 17, шину 18 мнимой части операнда А;(к), шину 19 действительной части операнда А(к)шину 20 мнимой части операнда А;(, шину 21 действительной части операнда А, шину 22 мнимой части весового коэфФициента, шину 23.действительной части весового коэффициента, выод ход 24 мнимой части операнда А., (, выход 25 мнимой части операнда А (й), выход 26 действительной части операнда А, , выход 27 действительной части операнда А, (М). Алгоритм работы устройства описывается следующим обраом:А =В +В 1 (к)Фр. (1)А ( (к)= ( В ( )-В Ь)Ч где В, ( ) ) А ), при рФОф С КеА (1)+ 1 ЯЕА(к),при р=О .А;(к), при рО1 щА; ( )+1.А (к), (2)при р:означает операцию комплексного сопряжения.1078434 Заказ 965/43 . Тираж 669 Подписно НИ Филиал ППП "Патент", г. Ужгород, УлПроектная, 4 Выражения (1) и (2) представляют собой базовую операцию алгоритма БПФ.Устройство работает следующим обраэор.На (.-й итерации алгоритма БПФ на входы 18-21 подаются два комплексных операнда й, и А,(к), а значения весовых коэффициентов поступают на регистры 5 и 6 по .входам 22 и 23. Если показатель р весового коэффициента Фк равен нулю, то е Ър - 1 рР1 вВ: 0 и в регистр 5 действительнойОчасти весового коэффициента запишутся все единицы. При этом на выходе дешифратора 17 сформируется логичес - кая единица, которая поступает на 15 управляющие входы коммутаторов 1 и 2, и выполняется коммутация операндов й ( ) и А; (к) в соответствии с выражением (2). Если же показатель р весового коэффициента не равен нулю, то в двоичном представлении действительной части весового коэффициента будет всегда хотя бы один нуль, Поэтому на выходе дешифратора 17 будет логический нуль и коммутация операндов Аи А(к) в соответствии с выражением (2) осуществляться не будет. После выполнения коммутации резуль тирующее значение операнда В( записывается в регистры 3 и 4, а значение операнда В,(к) подается на входы умножителей 7-10. На выходах умножителей 7-10 формируются одновременно четыре произведенияРЕ В (к) РЕЭ, РЕ В (к) 1 еаХВ; (к) Яее,5 В (к) 1 паНа выходах сумматоров 12 и 11М образуются значения действительной и мнимой частей произведения двух комплексных чисел Вк)1 ВКеВ;(к) чЧ= Ре В(к) ЯЕ И- в 1 щ В(к) 1 м Ф,1В; (к ) И= к е В; (к) 1 ф( Р ++1 В,(к) ке аВ соответствии с выраженИЙ (1) сумматоры 15 и 13 образуют значения соответственно действительной и мнимой частей нового операнда А,. С помощью сумматоров 16 и 14 форйируется значение операнда А+к) . Результирующие значения операндов А;+,(1), А+, (к) поступают на выходы 24-27 устройства.В зависимости от интерпретации знакового разряда сумматора 14 с вы" ходов 25 и 27 снимаются сопряженные значения операнда А;,1 (к) .Использование изобретения позволяет увеличить быстродействие устройства быстрого преобразования Фурье более чем в 2 раза по сравнению с прототипом. Это обусловлено тем, что при вычислении спектра число базовых операций вида (1) и (2) уменьшается более чем в 2 раза по сравнению с числом базовых операций, используемых в прототипе.