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

Союз Советских Социалистических РеспубликОПИСАНИЕИЗОБРЕТЕ ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23) ПриоритетГосударственный комитет СССР по делам изобретений и открытий(71) Заявитель Таганрогский радиотехнический институт им, В.Д. Калмыкова 54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к вычислительной технике и мажет быть использовано при определении спектральных характеристик сигналов,Известно устройство для быстрого преобразования Фурье, содержащее регистры чисел и весового коэффициента, блоки умножения и суммирования (1110Однако известное устройство сложно и обладает недостаточным быстродействием, так как содержит сложные блоки умножения, а суммы поразрядных произведений формируются каждый раз заново, что требует соответствующего времени и оборудования. Наиболее близким к изобретению техническим решением является устройО ство, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и ЗО четвертый сумматоры, выходы которых связаны с выходами устройства 2,Недостатком данного устройства является последовательное образование рассчитываемых коэффициентов, начиная с младшего разряда, что снижает быстродействие процесса вычисления.Цель изобретения - повышение быстродействия устройства и уменьшение оборудования.Это достигается тем, что в устройство, содержащее первый и второй сумматоры, входы которых являются входами вещестенной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей первого операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства, введены регистр суммы и регистр разности вещественной и мнимой частей .первого операнда, два многовходовых сумматора, блок хранения признаков весового коэффициента и два регистра задержки, входы которых являютсявходами второго операнда устройства, при этом входы регистров сумяз и раз ности вещественной и мнимой частей первого операнда подключены к. выходам соответственно первого и второго ,сумматоров, а выходы - соответственно к первым и вторым входам блоков ,вычисления вещественной и мнимой частей первого операнда, соединенных третьими входами с выходом блока хранения признаков весового коэффициента, выходы блоков вычисления вещественной и мнимой частей первого операнда соединены со входами соответственно первого и второго многовходовых сумматоров выходы которых сое 915 динены со входами соответственно третьего и четвертого сумматоров, входы которых подключены к выходам регистров задержки.На чертеже представлена структурная схема предложенного устройсва. 2 ООно имеет входы 1 и 2 вещественной и мнимой частей первого операнда, первый 3 и второй 4 сумматоры, регистр 5 суммы и регистр б разности .вещественной и мнимой частей пер вого операнда, блоки 7.и 8 вычисления вещественной и мнимой частей первого операнда, блок 9 хранения признаков весового коэффициента, блок 10 Формирования признаков весового коэфФициента, входы 11 и 12 вещественной и мнимой частей весового коэффициента, первый 13 и второй 14 многовходовые сумматоры, третий 15 и четвертый 16 сумматоры, входы 17 и 18 второго операнда, регистры 19 и 20 задержки, выходы 21 и 22 устройства,Устройство работает по алгоритму"и (Й= А,Я ;К 1 Е, " =;И- Ф и Во втором такте работы в (и) 50 ячейку блока 9 запишутся четыре признака, соответствующие (и)-му разряду весового коэффициента, а в регистры 5 и б - сумма 5,разностьВи 1вещественной и мнимой частейследующего (в)-го разряда операндаА(К). В логические блоки 7 и 8 поступают значения признаков и-го и(и)-го разрядов весового коэффициента, сумм 5 п 1 и 5 и 1 и разностей ВиВ,вещественной и мнимой частейв-го и (в)-го разрядов операндаЬ(К). В результате на выходах логических блоков 7 и 8, а следовательно и на входах сумматоров 13 и 14,получаем значения соответственно ве 65 цественной и мнимой частей произве где А с индексами - комплексные числа в избыточной двоичной системе счисления, выраженные цифрами Т, 0,1;Х - комплексный весовой коэффициент, выраженный цифрамиТ и 1.Проведение операнда А 1(К) на весовой коэффициент вычисляется по алгоритмуВеА.,(к) уффе К,Я Веа З. А;(у 4 3 аКк) м 1" ь,(к)ке 1-Ве ;(К 11 еч4)Так как каждый разряд комплексного весового коэффициента Я может принимать только значения 1 или 1 то произведения операнда АК) на весовой коэффициент И может быть получено путем формирования суммы или разностиь.Вел,к)Э Ь,(,к),ЙРЙ,К)-З А. (К),вещественной и мнимой частей операн.да А 1(К). Вещественная и мнимая части операнда А(К) подаются поразрядно,начиная со старшего разряда, по входам 1 и 2 в сумматоры 3 и 4. В сум- маторе 3 образуется сумма 51, а в сумматоре 4 - разность В(, которые поступают в регистры 5 и б.Одновременно в логический блок 10 по входам 11 и 12 поразрядноначиная со старшего и-го разряда, подаются значения вещественной и мнимой частей весового коэффициента И, В зависимости от поступающих значений вещественной и мнимой частей весового коэффициента логический блок 10 вырабатывает четыре признака Р Ве 31 Р Ве 1 ЗифР Ве 1 Ки Рд =Ве 1 ч , З,Я, которые записываются в соответствующую ц-ю (с 1 и, и, 1) ячейку блока 9 хранения признаков. С выхода каждой из и-ой ячеек блока 9 хранения признаков в логические блоки 7 и 8 подаются управляющие сигналы, которые управляют работой этих блоков.Рассмотрим несколько тактов работы устройства, В первом такте в и-ю ячейку блока 9 запишутся четыре признака, соответствующие старшему и-му разряду весового коэффициента, а в первые разряды регистров 5 и б - сумма 5 и разность В, вещественной и мнимой частей старшего ю-го разряда операнда А(К).Полученные значения признаков Р, суммы 5,и разности В,и поступают в логические блоки 7 и 8, работающие соответственно по алгоритмам (3)и (4), и в зависимости от значений признаков Р на выходах логических блоков 7 и 8 получим значения вещественной и мнимой частей произведения в-го разряда операнда А(К)на и-й разряд весового коэффициента Ч, которые подаются в и- входовые сумматоры 13 и 14.750494 цений в-го разряда операнда А(К) на (и)-й разряд весового коэффициента и (а)-го разряда операнда А(К) на и-й разряд весового коэффициента. Яа выходах сумматоров 13 и 14 получим значения сумм этих произведений, которые суммируются сумматорами 15 и 16, согласно алгоритмам (1) и (2), с вещественной и мнимой частями операнда А (. Регистры 19 и 20 служат для согласования во времени операндов 10 А(К) и А(. На выходах сумматора 15 получаем вещественные части операндов А;,1(К) и А;,.1 (, а на выходах сумматора 16 - мнимые части этих операндов, которые подаются на выходные шины 21 и 22 устройства.Таким образом, введение и-входных сумматоров и регистров суммы и разности позволяет упростить операции умножения, заменив их операциями суммирования. Эа счет одновременного суммирования и поразрядных произведений А(К), Ч, увеличен в и раэ быстродействие устройства и сокращено оборудование, так как и-входовой сумматор требует меньших аппаратурных затрат по сравнению с двухвходовыми сумматорами. 30 формула изобретения Источники информации,35 принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 421994, кл. С 1 06 Р 15/34, 1974.2. Авторское свидетельство СССРР 467356, кл. 6 06 Р 15/34, 197540 ,(прототип. 12 Составитель А. ЗоринРе актор Т. Клюкина Техред Ж, Кастелевич Корректор И. Мус аказ 4650/38 Тираж 751 Подписное ЦИНИПИ Государственного комитета СССР по делам изобретений и открытий 113035 Москва ЖРаушская наб. д. 4 5илиал ППП "Патентф, г. Ужгород, ул. Проектная Устройство для быстрого преобразования Фурье, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей операнда и блок формирования признаков весового коэффициента первого, причем входы последнего являются входами вещественнойи мнимой частей весового коэффициента устройства, третий и четвертыйсумматоры, выходы которых связаны свыходами устройства, о т л и ч а ю -щ е е с я тем, что, с целью увеличения быстродействия и уменьшенияоборудования,в него введены регистрсуммы и регистр разности вещественной и мнимой частей первого операнда,два многовходовых сумматора, блокхранения признаков весового коэффициента и два регистра задержки, входы которых являются входами второгооперанда устройства, при этом входырегистров суввн и разности вещественной и мнимой частей первого операнда подключены к выходам соответственно первого и второго сумматоров,а выходы - соответственно к первыми вторым входам блоков вычисления вещественной и мнимой частей первогооперанда, соединенных третьими входами с выходом блока хранения признаков весового коэффициента, выходыблоков вычисления вещественной имнимой частей первого операнда соединены со входами соответственнопервого и второго многовходовых сумматоров, выходы которых соединены совходами соответственно третьего ичетвертого сумматоров, входы которыхподключены к выходам регистров задержки.