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

(54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ j Изобретение относится к вычислительной технике и может быть использовано при определении спектральных характеристик сигналов. Известно устройство для быстрого преобразования Фурье, содержащее регистры чисел и весового коэффициента, блоки умножения и суммирования 1 , Однако известное устройство сложно и обладает недостаточным быстродействием, так как содержит сложные блоки умножения, а суммы поразрядных произведений формируются каждый раз заново, что требует соответствукщего времени и оборудования. Наиболее близким к изобретению техническим решением является устрой ство, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой час тей операнда и блок формирования при наков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весово го коэффициента устройства, третий четвертый сумматоры, выходы которых связаны с выходами устройстваJ2. Недостатком данного устройства является последовательное образование рассчитываемых коэффициентов, начиная с младшего разряда, что снижает быстродействие процесса вычисления. Цель изобретения - повышение быстродействия устройства и уменьшение оборудования. Это достигается тем, что в устройство, содержащее первый и второй сумматоры, входы которых йвляются входами вещестенной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей первого операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства, введены регистр суммы и регистр разности вещественной и мнимой частей первого операнда, два многовходовых сумматора, блок хранения признаков весового коэффициента и два регистра зсщержки, входы которых являются Входами второго операнда устройства при этом входы регистров суммы и ра ности вещественной и мнимой частей первого операнда подключены к.выходам соответственно первого и второг ;сумматоров, а выходы - соответствен но к первым и вторым входам блоков вычисления вещественной и мнимой частей первого операнда, соединенны третьими входами с выходом блока хр нения признаков весового коэффициента, выходы блоков вьачисления вещественной и мнимой частей первого операнда соединены со вxoдa ш соответственно первого и второго многов довых сумматоров, выходы которых со динены со входами соответственно третьего и четвертого сумматоров, входы которых подключены к выходам регистров задержки, На чертеже представлена структур ная схема предложенного устройства. Оно имеет входы 1 и 2 вещественной и мнимой частей первого операнда, первый 3 и второй 4 сум1«1аторы, гистр 5 суммы и регистр 6 разности ,вещественной и мнимой частей первого операнда, блоки 7.и 8 вычисления вещественной и мнимой частей пе вого операнда, блок 9 хранения приз ков весового коэффициента, блок 10 формирования признаков весового коэ фициента, входы 11 и 12 вещественно и мнимой частей весового коэффициента, первый 13 и второй 14 много входовые сумматоры, третий 15 и чет вертый 16 суьвлаторы, входы 17 и 18 второго операнда, регистры 19 и 20 задержки, выходы 21 и 22 устройства Устройство работает по алгоритму .., (} .W-W, Ш где А с индексами - комплексные чис ла в избыточной двоичной системе счисления, выраженные цифрами Т, 0, W - комплексный весовой коэффициент, выраженный цифрами Т и 1. проведение операнда Aj(K) на весовой коэффициент вычисляется по алгоритму Re.()..(к).(з, (j) mk(,(K ReV4-Re.K;(K). , Так как каждый разряд комплексно го весового коэффициента W может принимать только значения или 1, то произведения операнда А И К) на весовой коэффициент W может быть получено путем формирования суммы или разности s,.,iк), R..ReK,((J вещественной и мнимой частей операнда А-, (К). Вещественная и мнимая части опе,ранда А(К) подаются поразрядно,начиная со старшего разряда, по входам 1 и 2 в сумматоры 3 и 4. в сумматоре 3 образуется сумма S , а в сумматоре 4 - разность Ri, которые поступают в регистры 5 и б, Одновременно в логический блок 10 по входам 11 и 12, поразрядно,, начиная со старшего п-го разряда, подаются значения вещественной и мнимой частей весового коэффициента W. В зависимости от поступающих значений вещественной и мнимой частей весового коэффициента логический блок 10 вырабатывает четыр1е призна.ка P,,fReW-3n,W, Р ReW-JrnW P3 ReW-J W и , которые записываются в соответствующую q-ю (, п-1,..1) ячейку блока 9 хранения признаков. С выхода каждой из п-ой ячеек блока 9 хранения признаков в логические блоки 7 и 8 подаются управляющие сигнсшы, которые управляют работой этих блоков. Рассмотрим несколько тактов работы устройства. В первом такте в п-ю ячейку блока 9 запишутся четыре признака, соответствующие старшему п-му разряду весового коэф.фициента, а в первые разряды регистров 5 и 6 сумма разность Rm вещественной и мнимой частей старшего тп-го разряда операнда А(К). Полученные значения признаков Р, суммы S(Ti и разности R поступают в логические блоки 7 и 8, работающие соответственно по алгоритмам (3)и (4), и в зависимости от значений признаков Р, на выходах логических блоков 7 и 8 получим значения вещественной и мнимой частей произведения т-го разряда операнда А(К)на п-й разряд весового коэффициента W, которые подаются в п- входовые сумматоры 13 и 14. Во втором такте работы в (п-1) ячейку блока 9 запишутся четыре признака, соответствующие (п-1)-му разряду весового коэффициента, а в регистры 5 и б - сумма S,;( разность RfT вещественной и мнимой частей следующего {т-1)-го разряда операнда А(к). В логические блоки 7 и 8 поступают значения признаков п-го и (п-1)-го разрядов весового коэффициента, сумм SfYi и разностей В,„и R.д вещественной и мнимой частей т-го и (m-l)-ro разрядов операнда А(к). В результате на выходах логичёских блоков 7 и 8, а следовательно и на входах сумматоров 13 и 14, получаем значения соответственно веиественной и мнимой частей произвецений m-го разряда операнда А(К) на (п-1)-й разряд весового коэффициент и (m-l)-ro разряда операнда А(К) на п-й разряд весового коэффициента. На выходах сумматоров 13 и 14 получим значения сумм этих произведений, которые суммируются сумматорами 15 и 16, согласно алгоритмам (1) и (2), с вещественной и мнимой частями операн да А (j). Регистры 19 и 20 служат дл согласования во времени операндов А(к) и A(j). На выходах сумматора 15 получаем вещественные части операндов АН-,(К) и А-, (j), а на выходах сумматора 16 - мнимые части этих операндов, которые подаются на выходные шины 21 и 22 устройства. Таким образом, введение п-входных сумматоров и регистров суммы и разности позволяет упростить опера ции умножения, заменив их операциями суммирования. За счет одновременного суммирования п поразрядных произведений А(К), W, увеличен в п раз быстродействие устройства и сокращено оборудование, так как п-входовой сумматор требует меньших аппаратурных затрат по сравнению с двухвходовыми сумматорами. Формула изобретения Устройство для быстрого преобразования Фурье, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей операнда и блок формирования признаков весового коэффициента первого, причем входы последнего являются входами вещественной ,и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства, отличающееся тем, что, с целью увеличения быстродействия и уменьшения оборудования,в него введены регистр суммы и регистр разности вещественной и мнимой частей первого операнда, два многовходовых сумматора, блок хранения признаков весового коэффициента и два регистра задержки, входы которых являются входами второго операнда устройства, при этом входы регистров суммы и разности вещественной и мнимой частей первого операнда подключены к выходам соответственно первого и второго сумматоров, а выходы - соответственно к первым и вторым входам блоков вычисления вещественной и мнимой частей первого операнда, соединенных третьими входами с выходом блока хранения признаков весового коэффициента, выходы блоков вычисления вещественной и мнимой частей первого операнда соединены со входами соответственно первого и второго многовходовых сумматоров , выходы которых соединены со входсшт соответственно третьего и четвертого сумматоров, входы которых подключены к выходам регистров задержки . Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР P 421994, кл. Q об F 15/34, 1974. 2.Авторское свидетельство СССР № 467356, кл. G 06 Р 15/34, 1975 , (прототип).