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

1

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

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

На чертеже представлена функцио- Ю. нальная схема устройства для выполнения быстрого преобразования Фурье (БПФ) . .

Устройство содержит регистры 1 - 6 (операндов и весового коэффициента), f5 умножители 7-10,- cy мaтopы 11 и 12, вычитатели 13 и 14, дешифраторы 15 и 16, коммутаторы 17 и 18jсумматоры- вычитатели , 19 и 20.

Алгоритм работы устройства описы- 20 , ваетси следующим образом:

КеЛ- ReA- + (( Irnwf) . IipA;., ImA;, + (IraB, - ReWI -ReB, ImW);

ReB- ReA.,-( + ImBj -lmWr); ImB. Im j - (ImB ReW -Re В ) ,

12A29862

Устройство работает следующим о6- . разом. . .,

На i-й итерации алгоритма БПФ в регистры

I -6 поступают соответстдзен- но знд шния ReA;, ReB|, IifBj;, PveWj -, , 1т/1|. Если показатель Р весового коэ(1)фициента Wj; равен нулю, то ReW , ImWf О и в регистр 4 действительной части весового коэффициента запишутся все единицы,. При этом ка выходе дешифратора 15 сфор-.. мируется логическая единица. Если

Р -, то Rewf О, ImW/ 1 и в i i. . Лрегистр 5 мнимой части весового, коэффициента запишутся все единицы, при

, этбм на выходе дещифратора 16 сфор- мируется логическая единица. Значения из дешифраторов 5 и 16 поступают на управляющие входы коммутаторов 17

,п 18 и в зависимости от управляющего входа на выход коммутаторов проходят значения 00-( ReW + ImB Imwf) и ( - ReB, ImW ); 01.- ReB и ImB; 10 - ReB- и ImBj. При коде О па управляющем входе cy№ia- торов вычитателей выполпяется операция сложения, при коде 1 - вычитания. Таким образом, при коде 00 на выходе дешифраторов в устройстве выполпяется выражение (1), ири коде 01 - выражение (2), нри коде 10 - выражение (3). На выход устройства из сумматора .12, вычитателя 14 и сумматоров вычитателей 19 и 20 поступают соответственно значения ReA|;. , , ImBj.vt , ImAuH .

где А ,, - первьш комплексный операнд; B l - второй комнлёксньй операнд; yf - комплексный весовой коэф-

фициент; Р -- показатель степени.

Выражение (l) представляет собой базовую операцию алгоритмаБПФ при

0 и При Р

Р Рг 2

О выражение принимает

вид

ReA ImA

iH

ReA+ ReB;

ImA I + ReA i - ReBj, ; ImA I - ImBj,, при P имеет вид ReAt+ + ImB-; - ReBt; ReAi; - ImAi +

LM

ImB,4i

ImA|;,H

,

ImBf

(2)

(3)

UH

ImBj,; ReBi .

В устройстве .реализуются выражения (i) (3) в зависимости от значения Р.

.

5

0

.

i

На i-й итерации алгоритма БПФ в регистры

5

I -6 поступают соответстдзен- но знд шния ReA;, ReB|, IifBj;, PveWj -, , 1т/1|. Если показатель Р весового коэ(1)фициента Wj; равен нулю, то ReW , ImWf О и в регистр 4 действительной части весового коэффициента запишутся все единицы,. При этом ка выходе дешифратора 15 сфор-.. мируется логическая единица. Если

Р -, то Rewf О, ImW/ 1 и в i i. . Лрегистр 5 мнимой части весового, коэффициента запишутся все единицы, при

, этбм на выходе дещифратора 16 сфор- мируется логическая единица. Значения из дешифраторов 5 и 16 поступают- на управляющие входы коммутаторов 17

,п 18 и в зависимости от управляющего входа на выход коммутаторов проходят значения 00-( ReW + ImB Imwf) и ( - ReB, ImW ); 01.- ReB и ImB; 10 - ReB- и ImBj. При коде О па управляющем входе cy№ia- торов вычитателей выполпяется операция сложения, при коде 1 - вычитания. Таким образом, при коде 00 на выходе дешифраторов в устройстве выполпяется выражение (1), ири коде 01 - выражение (2), нри коде 10 - выражение (3). На выход устройства из сумматора .12, вычитателя 14 и сумматоров- вычитателей 19 и 20 поступают соответственно значения ReA|;. , , ImBj.vt , ImAuH .

Вырал(е1П1е (l) выполп яется в устройстве за время

40

Т - tyH)4

+ 2 ton +

5

0

5

где tcM - время выполнения

операций умножения и сложения; t|, - задержка информации

в коммутаторе.

Выражения (2) и (3) выполняются в устройстве за время

+ Скддх М

где tQffi - время срабатывания дешифратора.

При выполнении алгоритма БПФ число операций вида (2) равно N-I, где N - число отсчетов, число операций вида (3) равно N/2-1, число операций вида (1) равно N/2-logiN - 3/2 N+2. Тогда время выполнения N-точечного

БПФ с использованием предлагаемого устройства равно

Т (|н-2)Т,,+ (|log2N-|N+2)T.

Время выполнения N-точечного БПФ с использованием известного устройства равно

/ NN 10

Т 2 (tijMH +2Ссм) - 2 logJ - T Формула изобретения

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

операнда устройства, входами реальных частей первого и второго операндов которого являются информационные вхо- ды соответственно первого и второго регистров, вторые входы первого и

3

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

10

f5

2025 JQ

5

0

циента которого является информационный вход пятого регистра, выход которого подключал к вторым входам второго и третьего умножителей, инфор- мационный вход шестого регистра является яходом мнимой части первого операнда устройства, отличающееся тем, что, с целью повышения быстродействия, в него введены первый и второй дешифраторы, первый и второй коммутаторы, первый и второй сумматоры-вычитатели, выходы которых являются выходами мндапзгх частей соответственно первого и второго операндов устройства, выход второго регистра подключен .к первым информационным входам первого и второго коммутаторов, вторые информационные входы которых подключены к выходу третьего регистра, выход второго сумматора подключен к третьему информационному входу первого коммутатора, выход которого подключен к вторым входам первого сумматора и первого вычитателя, выход второго вычитателя подключен к третьему инфор- aциoiнioмy входу второго коммутатора, вьпчод которого подключен к первым входам первого и второго суммато- ров-вычитателей, вторые входы которых подключены к выходам шестого регистра, выход четвертого регистра подключен к входу первого дешифратора, выход которого подключен к первым управляющим входам первого и второго коммутаторов, вторые управляющие входы которь гх объединены с управляющем входом первого сумматора-вычитателя и подключены к прямому выходу второго дешифратора, вход которого подключен к выходу пятого регистра, а инверсный выход второго дешифратора подключен к управляющему входу второго сумматора-вычитателя .

Ke8i

Т

фNj/Ф

JmAi-n

/few

3mW- JmAi

Изобретение относится к вычислительной технике и может быть использовано при вычислении спектра сигналов и их фильтрации в частотной области. Цель изобретения - повышение быстродействия устройства. Последнее содержит шесть регистров, четыре умножителя, два сумматора, два вычитателя, два сумматора-вычи- тателя два коммутатора, два дешифратора. 1 ил. Ivd 4 tC се 00 Од

Редактор Н.Гунько

Составитель А.Баранов Техред И.Гайдош

Заказ 3708/50 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4

Корректор О.Луговая