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

Description

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

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

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

Наиболее близким к изобретению техническим решением является устрой~20 ство, содержащее первый и второй сумматоры, входы которых являются входами вещественной и мнимой частей первого операнда устройства, блоки вычисления вещественной и мнимой час-25 тей операнда и блок формирования признаков весового коэффициента, причем входы последнего являются входами вещественной и мнимой частей весового коэффициента устройства, третий и четвертый сумматоры, выходы которых связаны с выходами устройства[2].

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

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

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

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

Оно имеет входы 1 и 2 вещественной и мнимой частей первого операнда, первый 3 и второй 4 сумматоры, регистр 5 суммы и регистр 6 разности .вещественной и мнимой частей первого операнда, блоки 7 и 8 вычисления вещественной и мнимой частей первого операнда, блок 9 хранения признаков весового коэффициента, блок 10 формирования признаков весового коэффициента, входы 11 и 12 вещественной и мнимой частей весового коэффициента, первый 13 и второй входовые сумматоры, третий вертый 16 сумматоры, входы второго операнда, регистры задержки, выхода 21 и 22 устройства.

Устройство работает по алгоритму ^At+4 (ib SCi)+b(R) w,,

14	много-
15	и	чет-
17	и	18
19	и	20

Mbгде А с индексами - комплексные числа в избыточной двоичной системе счисления, выраженные цифрами Т, 0,1;

W - комплексный весовой коэффициент, выраженный цифрами Т и '1.

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

Re[&. (k>w]= Re -А. (к)· Rew G_m· A-,(b-3_mW,

Так как каждый разряд комплексного весового коэффициента W может ’принимать только значения1 или 1, то произведения операнда At(К) на весовой коэффициент W может быть получено путем формирования суммы или разности s-ReA-Ju)*^*.^) _г R-Re’A.(K)-3_mA.(KV no (3) (M вещественной и мнимой частей операнда А,(К).

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

Одновременно в логический блок 10 по входам 11 и 12, поразрядно,, начиная со старшего η-го разряда, подаются значения вещественной и мнимой частей весового коэффициента W. В зависимости от поступающих значений вещественной и мнимой частей весового коэффициента логический блок 10 вырабатывает _четыре признайка P^ReW-lmW, Р_г= ReW-a_mW₄P₃=ReW3_mW и Р₄ =ReW которые записываются в соответствующую q-ю (q = n, η-1,..1) ячейку блока 9 хранения признаков. С выхода каждой из η-ой ячеек блока 9 хранения признаков в логические блоки 7 и 8 подаются управляющие сигналы, которые управляют работой этих блоков.

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

Полученные значения признаков Р_о, суммы Sfri ^и разности R_m поступают в логические блоки 7 и 8, работающие соответственно по алгоритмам (3)и (4), и в зависимости от значений признаков Р_п на выходах логических блоков 7 и 8 получим значения вещественной и мнимой частей произведения m-го разряда операнда А(К)на п-й разряд весового коэффициента W, которые подаются в п- входовые сумматоры 13 и 14.

Во втором такте работы в (п-1) ячейку блока 9 запишутся четыре признака, соответствующие (п-1)-му разряду весового коэффициента, а в регистры 5 и б - сумма разность вещественной и мнимой частей следующего (m-l)-ro разряда операнда А(К). В логические блоки 7 и 8 поступают значения признаков η-го и (n-l)-ro разрядов весового коэффициента, сумм Sfr, и БггцИ разностей R_wh R^^ вещественной и мнимой частей m-го и (т-1)-го разрядов операнда А(К). В результате на выходах логических блоков 7 и 8, а следовательно и на входах сумматоров 13 и 14, получаем значения соответственно вещественной и мнимой частей произве5 цений m-го разряда операнда А(К) на (п-1)-й разряд весового коэффициента и (m-l)-ro разряда операнда А(К) на η-й разряд весового коэффициента. На выходах сумматоров 13 и 14 получим значения сумм этих произведений, которые суммируются сумматорами 15 и 16, согласно алгоритмам (1) и (2), с вещественной и мнимой частями операнда A (J). Регистры 19 и 20 служат для согласования во времени операндов А(К) и A(j). На выходах сумматора 15 получаем вещественные части операндов A-_t<.₄(K) и А·,^ (j), а на выходах сумматора 16 - мнимые части этих операндов, которые подаются на выходные шины 21 и 22 устройства.

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

Claims (2)

1. (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. 2.Авторское свидетельство СССР № 467356, кл. G 06 Р 15/34, 1975 , ( прототип).