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

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕ ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6f) Дополнительное к авт. свид-ву— (S 1 } V К л 3

Об 1." 15/34 (22) Заявлено05.12.77 (21) 2550548/18-24 с присоединением заявки ¹â€” (23) ПриоритетГосударственный комитет

СССР по делам изобретений и открытий

Опубликовано 2 3Q78Q Бюллетень ¹ 27

Дата опубликования описания 250780 (53) УДК681. 3 (088. 8) (72) Авторы изобретения

А, Ю. Арцатбанов, A. И. Гречишников и В. А. Телековец (71) Заявитель

Таганрогский радиотехнический институт им. В.Д. Калмыкова 54) УСТРОЙСТВО ДЛЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Изобретение относится к вычислительной технике и мажет быть использовано при определении спектральных характеристик сигналов.

Известно устройство для быстрого преобразования Фурье, содержащее регистры чисел и весового коэффициента, блоки умножения и суммирования $13

Однако известное устройство сложно и обладает недостаточным быстродействием, так как содержит сложные блоки умножения, а суммы поразрядных произведений формируются каждый раз заново, что требует соответствующего времени и оборудования.

Наиболее близким к изобретению техническим решением является устрой-щ ство, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой час-75 тей операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и gp четвертый сумматоры, выходы которых связаны с выходами устройстваt 2).

Недостатком данного устройства является последовательное образование рассчитываемых коэффициентов, начиная с младшего разряда, что снижает быстродействие процесса вычисления.

Цель изобретения — повышение быстродействия устройства и уменьшение оборудования.

Это достигается тем, что в устройство, содержащее первый и второй сумматоры, входы которых являются входами вещестенной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей первого операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства, введены регистр суммы и регистр разности вещественной и мнимой частей .первого операнда, два многовходовых сумматора, блок хранения признаков весового коэффициента и два регистра задержки, входы которых являются

750494 входами второго операнда устройства, при этом входы регистров сумюы и раз ности вещественной и мнимой частей первого операнда подключены к. выходам соответственно первого и второго ,сумматоров, а выходы - соответствен но к первым и вторым входам блоков ,вычисления вещественной и мнимой частей первого операнда, соединенных третьими входами с выходом блока хранения признаков весового коэффициента, выходы блоков вычисления вещественной и мнимой частей первого операнда соединены со входами соответственно первого и второго многовходовых сумматоров выходы которых сое-!

15 динены со входами соответственно третьего и четвертого сумматоров, входы которых подключены к выходам регистров задержки.

На чертеже представлена структурная схема предложенного устройства. 20

Оно имеет входы 1 и 2 вещественной и мнимой частей первого операнда, первый 3 и второй 4 сумматоры, регистр 5 суммы и регистр 6 разности вещественной и мнимой частей пер- 25

soro операнда, блоки 7.и 8 вычисления вещественной и мнимой частей первого операнда, блок 9 хранения признаков весового коэффициента, блок 10 формирования признаков весового коэфФициента, входы 11 и 12 вещественной и мнимой частей весового коэффициента, первый 13 и второй 14 многовходовые сумматоры, третий 15 и четвертый 16 сумматоры, входы 17 и 18 второго операнда, регистры 19 и 20 задержки, выходы 21 и 22 устройства.

Устройство работает по алгоритму (1j=А bj 1" Х

А;,(4= К;И- К;(К1- Я, где A с индексами — комплексные числа в избыточной двоичной системе счисления, выраженные цифрами Т, 0,1;

9/ - комплексный весовой коэффициент, выраженный цифрами

T H 1.

Проведение операнда А1(К) на весовой коэффициент вычисляется по алгоритму

Кф.,® 7фРЕ A;(j.йЕ1А1 3 - ;Я.3 1Д, ЬЖ )g gÔjR - 5(y)3 (4)

Так как каждый разряд комплексного весового коэффициента W может принимать только значениями или 1, то произведения операнда A<(К) на весовой коэффициент W может быть получено путем формирования суммы или разности

s- Re K, êj+Э A,,,(), Р=-йй,(aj-З g. (К ), 65 вещественной и мнимой частей операнда А (К).

Вещественная и мнимая части операнда А (К) подаются поразрядно, начиная со старшего разряда, по входам 1 и 2 в сумматоры 3 и 4. B сум- маторе 3 образуется сумма Si, а в сумматоре 4 — раз ность R i, которые поступают в регистры 5 и б.

Одновременно в логический блок

10 по входам 11 и 12„ поразрядно,,начиная со старшего и-го разряда, подаются значения вещественной и мнимой частей весового коэффициента W, В зависимости от поступающих значений вещественной и мнимой частей весового коэффициента логический блок 10 вырабатывает четыре признаР = " 3 W<рз= е1 3 W и Р =RåW ; 3 W, которые записыва4 ются в соответствующую q-ю (q n, п-1, 1) ячейку блока 9 хранения признаков. С выхода каждой из и-ой ячеек блока 9 хранения признаков в логические блоки 7 и 8 подаются управляющие сигналы, которые управляют работой этих блоков.

Рассмотрим несколько тактов работы устройства. В первом такте в и-ю ячейку блока 9 запишутся четыре признака, соответствующие старшему и-му разряду весового коэффициента, а в первые разряды регистров 5 и б— сумма Б и разность R вещественной и мнимой частей старшего m-го разряда операнда А(К).

Полученные значения признаков Р, суммы S и разности йщ поступают в логические блоки 7 и 8, работающие соответственно по алгоритмам (3)и (4), и в зависимости от значений признаков Р„ на выходах логических блоков 7 и 8 получим значения вещественной и мнимой частей произведения

m-ro разряда операнда A(K)на и-й разряд весового коэффициента Ч, которые подаются в и- входовые сумматоры

13 и 14.

Во втором такте работы в (и-1) ячейку блока 9 запишутся четыре признака, соответствующие (и-1)-му разряду весового коэффициента, а в регистры 5 и б — сумма Ь,п1разность

R вещественной и мнимой частей следующего (m-1)-ro разряда операнда

А(К). В логические блоки 7 и 8 поступают значения признаков и-го и (n-1)-ro разрядов весового коэффициента, сумм S и бп и разностей Ви

R вещественной и мнимой частей

m-го и (m-1)-го разрядов операнда

A(К). В результате на выходах логических блоков 7 и 8, а следовательно и на входах сумматоров 13 и 14, получаем значения соответственно вецественной и мнимой частей произве-!

750494

Формула изобретения

Составитель А. Зорин

Редактор Т. Клюкина Техред Ж. Кастелевич Корректор И. Муска

Тираж 751 Под пи с но е

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва Ж-35 Раушская наб. д. 4 5

Заказ 4650/38

Филиал ППП "Патент", г. Ужгород, ул. Проектная, цений m-го разряда операнда A(K) на (и-1)-й разряд весового коэффициента и (m-1)-го разряда операнда A(K) на и-й разряд весового коэффициента. Яа выходах сумматоров 13 и 14 получим значения сумм этих произведений, которые суммируются сумматорами 15 и

16, согласно алгоритмам (1) и (2), с вещественной и мнимой частями операнда A (j). Регистры 19 и 20 служат для согласования во времени операндов

А(К) и A(j). На выходах сумматора

15 получаем вещественные части операндов А;,1(К) и А;+,1 ()), а на выходах сумматора 16 — мнимые части этих операндов, которые подаются на выходные шины 21 и 22 устройства.

Таким образом, введение и-входных сумматоров и регистров суммы и разности позволяет упростить операции умножения, заменив их операциями суммирования. 3а счет одновременного суммирования и поразрядных произведений А(К), Ч, увеличен в и раэ быстродействие устройства и сокращено оборудование, так как и-входовой сумматор требует меньших аппаратурных затрат по сравнению с двухвходовыми сумматорами.

Устройство для быстрого преобразования Фурье, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой частей операнда и блок формирования признаков весового коэффициента первого, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства, о т л и ч а ю— щ е е с я тем, что, с целью увеличения быстродействия и уменьшения оборудования,в него введены регистр суммы и регистр разности вещественной и мнимой частей первого операнда, два многовходовых сумматора, блок хранения признаков весового коэффициента и два регистра задержки, входы которых являются входами второго операнда устройства, при этом входы регистров суввн и разности вещественной и мнимой частей первого операнда подключены к выходам соответственно первого и второго сумматоров, а выходы — соответственно к первым и вторым входам блоков вычисления вещественной и мнимой частей первого операнда, соединенных третьими входами с выходом блока хранения признаков весового коэффициента, выходы блоков вычисления вещественной и мнимой частей первого операнда соединены со входами соответственно первого и второго многовходовых сумматоров, выходы которых соединены со входами соответственно третьего и четвертого сумматоров, входы которых подключены к выходам регистров задержки.

Источники информации, 35 принятые во внимание при экспертизе

1. Авторское свидетельство СССР .Р 421994, кл. G 06 F 15/34, 1974.

2. Авторское свидетельство СССР Р 467356, кл. G 06 Р 15/34, 1975

40,(прототип1.