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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51) 4 С 06 Г 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

<

1 п

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4288252/24-24 (22) 21.07.87 (46) 07.11.89. Бюл. < <- 41 (71) Одесский политехнический институт (72) M.Б.Сведлик, А.А.Назаренко, В.Л.Евсеев и Б.Г.Горинштейн (53) 68 1.32(088.8) (56) Авторское свидетельство СССР

У 1107132, кл. С 06 F 15/332, 1984.

Патент США 3588460, кл. С 06 F 7/38, опублик. 19?8.

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

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

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

Устройство содержит информационный вход 1, последовательно включенные каскады 2 преобразований, 1 =

1,М, содержащие коммутатор 3, элементы 4 — 7 задержки (в 2 „2 >„и

2 >>+, -м каскадах отсутствуют злементы 5 и 7, а в 2, -м каскаде элементы б и 7), умножитель 8 (на тривиальные коэффициенты) (в 2>< >-х каскадах, I. = 1,(<), арифметический блок (АБ)9, умножители 10 и 11 (на поворачивающие множители) .(в 2 z-x

„„SU„„1520538 А 1

2 (54)- УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области цифровой обработки. сигналов и может быть использовано в системах связи, гидролокации, радиолокации. Цель изобретения — упрощение устройства.

Цель достигается за счет того, что устройство содержит информационный вход, каскады преобразования, элементы задержки, умножитель, арифметический блок, умножители, блок управления и блок постоянной памяти. 3 ил. каскадах, L = <,,Д, блок 12 управления, блок 13 постоянной памяти (поворачивающих множителей), выходы которого объединены в шины 14, (i

1,Л).

Устройство производит вычисление

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

П И cN (N П Ne, (1)

<<<= < <п < где Mt: 13Л, ЗЛ + 1, 3 A + 2), N3l 2 134 > зл+1 2 я<.- "зд+ т

1, ? .

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

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

15?0538

М.! А нулевыми отсчетами Jlo общего числа операндов N и производить вычисление !

N -точечного ДПФ.

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

Для эффективного вычисления ДПФ комплексной последовательности

1х(1) ; i = 0, N 1, определяемого выражением

hl =1 15

Х (k) = > Х (1) rrrI (2) „ =о

27 где k = 0 N 1, M,= ехр(-j

= -1, необходимо и достаточно представить и k и виде ° 20

+,) а

1 1с р (modN )

">1>

+ ; а„, а„, = р

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

10 М -1 Й

° ° °

i t--о (3) где i,„k„, = О,N (5) это индексы лексикографического представления переменных i u k в обобщен- 30 ной позиционной системе счисления для данного разложения числа N на ! сомножители".

xi„(modN )J, Д при И = ЗЛ

Е

Л+1,при M 7 ЗЛ;

Л приИ <ЗЛ+1

35 Л+1 при И = ЗЛ + 21 м

11„= П Р,.;

5е >!1! 1

1 приМ=ЗЛ 1

2приМ )ЗЛ, (6) 1 1м

N, если (р! Л )=1 если (N,N ) Ф 1

3L с,= р=эь-z

N. Nр-11

: 1р °

»1=3Се1

i 1с (шойИ ) ..

Nt, I N1 N, Nr

N != 1, если r 0

45 (8) получим

1с (юос1И )g

Z, x(7 1=

А =х(е

=Х.".

"1-"

Е"

i -о

1,"

55 (9) М=О!

)И„„! м а р=!

x i (modN где Г

>г е 1 лл

i = .К g i, (modN )/ !11 м

k = Х, Ъ„и „,! km(modN ) .

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

Подставив (3) и (4) в (2) .

x(k1 к " skag) = Х м =

l4 -1 ,0 Х(11,1„° 4 9 iN) x

1„=0

Е 13! Z gr, Z х П 1!

>31 „3 С, 1 3I 31.

3 х

4=1 1.x Z

31 з1-, р1

Л 3 гК Л С1, 1. 1 г>>е X!k,,k>,...,k - Х > е lp„N,!*

11> 1

x k (modN )), Л1

Xj1,, 1„...,1„) = Х(Е „

Иэ (10) путем соответствующей рас1> становки множителей 11„ вдоль внутренних сумм получаем для M ЗЛ + 2 (а 2) алгоритм БПФ, реализованный в предлагаемом устройстве (фиг. 1):

I>a+Z-=O

ЭЛА 1 0Л" 1 Л 3Л ЗЛ

1 3Л+!ео > Яео

С1 1 13 < Х!! 2 и — з

3 11 =о

1570538

К, Х 1:1, 1-

1 = 1»л

1 а (12)

1и

В случае, если М = ЗХ + 1, в выражении (12) отсутствует суммирование по индексу j. „,, а если М = ЗЛ, то отсутствует также суммирование по инЛексу 1 3 л „и множитель W í .„

Заметим что множители W Э

4 не зависят от различных комбинаций значений i л »,k з„ и принимают следующие травильные значения, зависящие от Л:

iJl .

3b Э -Ь

31 К

1, + j при М вЂ” нечетное, 1; -j при Л вЂ” четном, (13) 2О.так как i „, k „= О, 1 для любого

L.

В устройстве реализован поточный процессор БПФ, алгоритм работы кото- 25 рого определяется выражением (12).

Он содержит М последовательно включенных каскадов, причем в каскадах с порядковыми номерами ÇL — 2 и ЗЬ с помощью соответствующих арифметических блоков производится вычисление двухточечных ДПФ, а в каскадах с порядковыми номерами ÇL — 1 — вычисление трехточечных ДПФ.

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

Х(1 1» 1 »

31-1 Эг. » г

1) = f(kt

3I,-1

l3I,»1»

1 к

З1.-i ЛЬ-1

Э (14) 45 где

1, приИ=ЗЛ.

2, при M ) ЗЛ.

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

При а = 1 выражение (14) определяет алгоритмы трехточечного ДПФ, при а = 2 значение Х с порядковыми номе55 рами индекса k > „, = 0,1,2 совпадает с величинами Х при а = 1, имеющими соответственно порядковые номера индекса k>„, = 0,2, t, Поэтому при использовании н (31,—

1)-м каскаде ".ðèÀMPтического блока, выполняющего операцию RbliIHcJIpния трехточечного ДЛФ, следуе" при М 3Л производить взаимные перекрестия его

5 второго.и третьего выходов.

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

И " з -1, я результаты двухточечных ДПФ, выполняемых в ЗЬ-х кас.кадах умножаются на нетривиальные поворачивающие множители И,", где

С1 дается выражением (11).

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

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

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

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

N -й вход АБ непосредственно.

В (ЗЬ вЂ” 2)-м, (Z. = 1, Л+1) каскаде сигналы с выходов АБ 9 поступают на входы коммутатора (ÇL- 1-)-го каскада непосредственно и через включенные последовательно умножитель 8 на тривиальные коэффипиенты 1 »j (при нечетном 1 и 1; -j (при четном Л ) и элемент 6.

В (ÇL-1)-N, L = 1, Л каскаде сигналы с выхода АБ заводятся на вход коммутатора ÇL-ro каскада непосредственно. Операнды с остальных выходов

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

В ЗI м !(ас кале сигггалы с выходов

Л! 9 поступают на входы коммутатора (3I,+1)-го каскада соответственно через умножители О и 11 на нетривиаль5 ные поворачивающие множители И ц", При !! = ЗЛ + 2 В(34 + !) каскаде отсутствует умножптель 8 на тривиальные коэффициенты. При этом сигнал с второго выхода AF> поступает непосредственно иа вход элемента 6. При М = 33, 3 A + 1 или 31 + 2 выходами устройства являются выходы. АБ соответствующих

И-х каскадов.

ФоpMyла из обpетения

Устройство для выполнения быстрого преобразования Фурье, содержащее М м-f каскадов преобразования (где П- N (2p

М

N СПИ„; М6 3 ; ЗЛ+ 1; ЗЛ+ 2), N„ N зь N з -1 2; N зь-1

N> „> = 3" 1. = 1 5, N — размер <Ре- 25 образования), блок управления и блок постоянной памяти, причем каскад пре, образования с номером 1 F (3L — 2, 3L, 3 h + 1) содержит арифметический блок, первый и второй элементы за- 3Q держки и коммутатор, при этом входы первого и второго операндов арифметическог о блока подключены соответственно к выходу первого элемента задержки и первому выходу коммутатора„ второй выход которого подключен квходу первого элемента задержки, выход первого операнда арифметического блока и выход второго элемента задержки подключены соответственно к первому и второму информационным входам коммутатора (1 + 1)-го каскада преобразования, а в ÇL-м (I. =

1, Ц каскаде преобразования выход второго операнда арифметического бло- 45 ка подключен к первому входу умножителя, выход которого подключен к входу второго элемента задержки, причем тактовые выходы первой группы блока управления подключены к управляющим входам коммутаторов соответствующих каскадов преобразования, так-, товые выходы второй группы блока управления подключены к тактовым вхо8 Я дам первого и второго -. ïåìåíòîâ чав держки соответствующих каскадов преобразования, адресный выход блока управления подключен к адресному вхо— ду блока постоянной памяти, выходы первой группы которого подключены к вторым входам умножителей соответствующих каскадов преобразования, о тл и ч а ю щ е е с я тем, что, с целью упрощения устройства в (31.-2)-м каскаде преобразования, выход второго оп ранда арифметического блока подключен к первому входу умножителя, выход которого подключен к входу второго элемента задержки, выход второго операнда арифметического блока (ЗД + 1)-го каскада преобразования подключен к входу второго элемента задержки, в ÇL-м каскаде преобразования первый выход арифметического блока подключен к первому входу второго умножителя, выход которого подключен к первому информационному входу коммутатора (ÇL+1)-го каскада, при этом каскады преобразования с номерами (ÇL-1) (I. = 1, 3 + 1) содержат арифметический блок, коммутатор и четыре элемента задержки, при этом первый, второй и третий выходы коммутатора подключены соответственно к входам первого и второго элементов задержки и входу третьего операнда арифметического блока, входы первого и второго операндов которого подключены к выходам соответственно первого и второго элементов задержки, выход первого операнда арифметического блока, выходы третьего и четвертого элементов задержки подключены соответственно к первому, второму и третьему информационным входам коммутатора ЗЬ-ro (1. = 1, ) каскада преобразования, входы третьего и четвертого элементов задержки подключены при

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

1520533

1520538

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

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

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

Подписное

Тираж 668

Заказ 6760/51

ВНИИПИ Государственного комитета по изобретениям и открьгтиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101