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

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

Целью изобретения является упрощение устройства.

На фиг. 1 представлена функциональная схема устройстваJна фиг,2 - схе- ма устройства при N 24 j на фиг. 3 - алгоритм работы.

Устройство содержит информационный вход 1, последовательно включен- ные каскады 2 преобразований, 1 1,М, содержащие коммутатор 3, элементы 4-7 задержки (в 2, 2зд и 2эл+1 каскадах отсутствуют элементы 5 и 7, а в 2 j -м каскаде элементы 6 и 7), множитель 8 (на тривиальные коэффициенты) (в . каскадах, L 1,Л), арифметический блок (АБ)9, умножители 10 и 11 (на поворачивающие множители) .(в

каскадах, L 1 ,)ll , блок 12 управления, блок 13 постоянной памяти (поворачивающих мно.жителей) , выходы которого объединены в шины 14 (i

ТТЛ),

Устройство производит вычисление БПФ массива комплексных операндов размера N, определяемого неравенством

м- П

м П

РПЕ т

N N N П N, (1)

СП to

о ел

со 00

где , ЗД + 1, ЗЛ + 2}, з1-г

2; N3,., 3,

L 1,Л,

Таким образом, число N раскладывается на произведение полных троек сомножителей и может быть еще одной неполной тройкой (2,3) либо двойкой,

В случае, если N , то исходное число операндов следует дополнить

нулевыми отсчетами до общего числа операндов N и производить вычисление N -точечного ДПФ.

Реализованный в устройстве алгоритм БПФ получен на основе представления естественного порядка следования обрабатываемых операндов х(1) в обобщенной позиционной системе счисления.

Для эффективного вычисления ДПФ комплексной последовательности lx(i)}; i 0; N -l, определяемого вь ражением

f/ -l

7:(k) Ц x(i)w :

i-O

(2),

/ . 21

где k 0,N -1; W, exp(j.:j

j -y-i необходимо и достаточно пред-

ставить i и k в виде м „ p

i - Z ,(modN ) ; (3)

m 1 h)

k Z. tr.N,k(raodN ),

(4)

i , k 0,N.,

(5)

это индексы лексикографического представления переменных i и k в обобщен-30 ной позиционной системе счисления для данного разложения числа N на

-ь Z

р.-н р. Р

i:z.

ГГ 1 р П1

, I

Учитывая отношение (1), выражение (9) можно привесдующему виду

v

X(k., .«,Кди) - 2--

..

N -1

2-.

),-0

П W,. L f 2

L-i

. П

,-- . L-2

..

(10)

м

где X(k,,k , ...,k uN.,1

ln

xkJraodN ),.

t- Ы

, i2,...,i

m

xi(modN ),

f .

;i/ при M ЗД Д+1 ,,при M 7

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

сомножители:

m-1..M

П Pg; u П p ,

5;, iTi4-l

4,M 1 .(6)

NS, если (N,N,) 1

I 1, если (N,NS) 5 1

(7)

(а,в) - наибольший общий делитель чисел а и в

Н f W W N

и - iN IN . , . IN р,

Np.. 1, если г О

45

(8)

Из (10) путем соответствующей рас

становки множителей W вдоль внут подставив (3) и (4) в (2). получим Ренних сумм получаем для М ЗД 4 2

(а 2) алгоритм БПФ, реализованный

предлагаемом устройстве (фиг, 1):

А - .,,k„()J .

-т Г - t-. л 1 «j ( ;„-°f.;01,:0 1

А I

W

(2

, 55

is +

4- -

X W, -, w«, Z W,

(9)

z

35

„ f; при M ЗЛ + 1.

)Л+1 при M 3/ + 2

f1 при M ЗЛ , ( 2 при M : 3 Д ,

L. 3L А

-. „Чп

p 3U-2m :3i.t

N. - NP-. .

Mm

L k/modN ).

-m 4

(11)

Из (10) путем соответствующей рас

А I

W

(2

55

is +

4- -

X W, -, w«, Z W,

iin+T o Ci

ss

... w I. W, - у W

is 0 i O

W,

Z W

X(i,,ij,

1

1,

В случае, если М ЗХ + 1, в выражении (12) отсутствует суммирование

а если М ЗЛ, т.о

по индексу л отсутствует также дексу i

суммирование по инт т f

3, и множитель W, . Заметим, что множители W не зависят от различных комбинаций

3 U -1

значении i

эл

и принимают следующие травильные щие от Д :

значения, завися3

W.

3U .-Z

-31

И;

k

3L-1

0,1 для любого

.так как L.

В устройстве реализован поточный процессор БПФ, алгоритм работы которого определяется выражением (12). Он содержит М последовательно включенных каскадов, причем в каскадах с порядковыми номерами 3L - 2 и 3L с помощью соответствуюищх арифметических блоков производится вычислени двухточечных ДПФ, а в каскадах с порядковыми номерами 3L - 1 - вычисление трехточечных ДПФ,

Действительно алгоритм преобразования, выполняемого (ЗЪ-1)-ми кас- .кадами, имеет вид

1; +J при А - нечетное , -J при А - четном (13

X(k,, k

2

31- +

3L-1 2

.)

Лм) «3

О; k

Зи-1 3L- 1

Г

.н-г

15L.

f(k,

где

i

f( kr,...

при М при М

ЗЛ,

зл.

м)

Э - 1 - 3 L

преобразуемые операнды.

При а 1 выражение (14) определяет алгоритмы трехточечного ДПФ, при а 2 значение X с порядковыми номерами индекса совпадает с величинами X при а 1, имеющими соответственно порядковые номера индекса .. 0,2,1,

10

Поэтому при использовании р (31,- - 1)-м каскаде арифметического б.;гокя. выполняющего операцию т11числения трехточечного ДПФ, следует при М ЗА производить взаимные перекрестия его второго.и третьего выходов.

Согласно алгоритму (12) выходные операнды двухточечных ДПФ, выполняемых в (3L - 2)-х каскадах, умножаются на тривильные козффициенты

W

зл з.ь-г

, а результаты двухточечных ДПФ, выполняемых в 3L-X каскадах умножаются на нетривиальные поворачивающие множители W v , где С ц дается выражением (11).

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

На вход коммутатора 3 первого каскада 2, Поступает последовательность из N комплексных операндов (неравенство 1). следующих с периодом Т, порядковые номера которых имеют последовательную нумерацию в обобщенной позиционной системе счисления (формулы 3-8) .

В случае, если преобразуемая последовательность операндов имеет размер N N , то исходная последова- тельность дополняется нулевыми отсчетами до размера N .

В 1-м (1- 1 ,М) каскаде операнды с k-x (k 1,N -1) выходов коммутатора 3 поступ ;ют соответственно через k-e элементы задержки входы арифметического блока 9. Сигнал с

45

50

55

выхода коммутатора поступает на Nj-й вход АБ непосредственно.

В (3L - 2)-м, (L 1, А+1) каска- дд де сигналы с выходов АБ 9 поступают на входы коммутатора (SL- -l)-го каскада непосредственно и через включенные последовательно умножитель 8 на тривиальные коэф)ициенты 1 j 4j (при нечетном Д и 1; -j ( при четном Д ) и элемент 6.

В (3L-1)-N, L 1, А каскаде сигналы с выхода АБ заводятся на вход коммутатора 3L-ro каскада непосредственно. Операнды с остальных выходов АБ при числе каскадов М, кратным трем (М ЗА),.поступают на входы коммутатора 3L-ro каскада соответственно через элементы 6 и 7 задержки. При числе каскадов М, некратном трем (М ), второй и третий выходы АБ должны быть подключены соответственно к входам элементов 7 и 6 (на фиг. 1 этот случай показан пунктиром).

В каскаде сигналы с выходов 9 поступают на входы коммутато ра (3L-f-1)-ro каскадта соответстпенно через ;ножители 10 и t1 на нетривиальные поворачивающие множители W При М ЗЛ -f- 2 В(ЗД + О каскаде отсутствует умножитель 8 на тривиальные коэффициенты. При этом сигнал с второго выхода АБ поступает непосредственно на вход элемента 6. При М ЗЯ, 3 + 1 или ЗЛ 2 выходами устройства являются выходы, АБ соответствутоа|:их М-х каскадов.

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

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

М- f

каскадов преобразования (где П. М

N Мб ЗД; ЗД + 1; ЗД + 2,

т т

Зь-7 N3L Мз:л-1 2; N3,-i N,j 2 3; L 1,Л, N - размер преобразования) , блок управления и блок постоянной памяти, причем каскад пре- образования с номером 1 |3L - 2, 3L, ЗА + 1 содержит арифметический блок, первый и второй элементы задержки и коммутатор, при этом входы первого и второго операндов арифме- тического блока подключены соответственно, к выходу первого элемента задержки и первому выходу коммутатора, второй выход которого подключен к входу первого элемента задержки, выход первого операнда арифметического блока и выход второго элемента задержки подключены соответственно к первом и второму информационным входам коммутатора (1 + 1)-го каска- да преобразования, а в ЗЬ-м {L -- 1,Д) каскаде преобразования выход второго операнда арифметического блока подключен к первому входу умножителя, выход которого подключен к входу второго элемента задержки, причем тактовые выход первой группы блока управления подключены к управляющим вхрдам коммутаторов соответствующих каскадов преобразования, так-, товые выходы второй группы блока управления подключены к тактовым входам первого и втсфого элементов задержки соответств ;,то1цих каскадов преобразования, адресный выход блока управления подключен к адресному входу блока постоянной памяти,выходы первой группы которого подключены к вторым входам умножителей соответст- ВУЮ1ЦИХ каскадов преобразования, о тл и ч а ю Et е е с я тем, что, с

целью упрощения устройства в (ЗЪ-2)-м каскаде преобразования, выход второго операнда арифметического блока : подключен к первому входу умножителя,

выход которого подключен к входу второго элемента задержки, выход второго операнда арифметического блока (3 Л + 1)-го каскада преобразования подключен к входу второго элемента задержки, в ЗЬ-м каскаде преобразования первый выход арифметического блока подключен к первому входу второго умножителя, выход которого подключен к первому информационному

входу коммутатора (3L+1)-ro каскада, при этом каскады преобразования с номерами (3L-1) (L 1 , , 1) содержат арифметический блок, коммутатор и четыре элемента задержки, при этом

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

и второго операндов которого подключены к выходам соответственно первого и второго элементов задержки, вы- ход первого операнда арифметического блока, выходы третьего и четвертого

элементов задержки подключены соответственно к первому, второму и третьему информационнь1м входам коммутатора 3L-ro (L i,/) каскада преобразования, входы третьего и четвертого

элементов задержки подключены при М - 3/ соответственно к выходам второго и третьего операндов арифметического блока, а при М ЗЛ - соответственно к выходам третьего и второго операндов арифметического блока, при этом выхода второй группы блока постоянной памяти подключены к вторым входам вторых умножителей соответствующих каскадов преобразования.

2

ZJ

ш

ж

г«

№1

Е

г-зл-г

-W

ТТЛ ГТТ

ГР

13

73

22

ш

А

/3

л

AS:

г,

-54S

т

2зу

I

v«

2jx/

фиг.1

trp

-gf S

«V /А

%

(г

Ос.. ю.

4-4L

ттппп

-Л

I . , К

(Ч|

«s4 чэ

ч К

34ч 5 caC3 ti-. N4

v 5j«--,ca t- 5a i t5,. i,

w-f «5i 53 v- 5 S5 -. ti b- caC5it-- 5st:iS

ч si 4 сэ t5 - ca ca la « sfcscst5 4-.

Редактор В.Бугренкова

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

Техред Л.Сердюкова Корректор Л.Патай

Заказ 6760/51

Тираж 668

ВШШПИ Госудярственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

v 5j«--,ca t- 5a i t5,. i,

«5i 53 v- 5 S5 -. ti b- caC5it-- 5st:i

Подписное