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

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, выполняющих алгоритм быстрого преобразования Фурье . (БПФ) по основанию 4.

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

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

Арифметическое устройство для быстрого преобразования Фурье содержит умножитель 1 комплексных чисел, состоящий из регистров 1.1-1„8, умножителей 1.9-1,12, регистров 1.16 и сумматоров .18, регистры 2-7, сумматоры 8-9, регистры 10- t9, сумматоры 20-21, тактовый вход 22 устройства.

Арифметическое устройство процессора БПФ выполняет элементарную операцию алгоритма БПФ по основанию 4 вида:

X.

P(i) 1 P(i + D- 1 +

P(i + 2)- 1 + P(i X. , P(i)- 1 + P(i

3).U 1).j +

+ P(i + 2)-(-l) + P(i + 3).(-j)i (1)

P(i) 1 + + f(i + 2) 1 +

X;,j P(i).1 +

+ P(i + 2)(-1) +

де P(i) X, -W;

y.

P(i + 1)-(-1) + P(i + 3(-1)-, P(i + IH-J) + P(i 3).j ,

ГТ

. i,j J - исходные отсчеты;

W - весовые коэф4 ициенты1 X - результаты выполнения

элементарной операции БПФ, Вьфажение (1) может быть представено в виде:

ReX. ReP(i) + ReP(i + 2) keP(i + 1) -f-ReP(i + 3) ; ReXj. tReP(i) - ReP(i + 2)1 (i + 1) - ItnP(i + 3) ; ReX,, LReP(i) + ReP(i + 2)1 -tReP(i + 1) + ReP(i + 3)1 ; ReX.j tReP(i) - ReP(i + 2) + + ImP(i + 1) - IraP(i + 3); ImPX ClraP(i) + ImP(i + 2)1 -f

+ lmP(i + 1) + IraP(i + 3)1. (2) ImX., ImPd) - ImP(i + 2) + + ReP(i + 1) - ReP(i + 3). ImXi.j llmP(i) + ImP(i + 2) -tlraPd -t- 1) + IraP(i -t- 3); ImX,.j ImPd) - ImP(i + 2) (i + 1) - ReP(i + 3) .

В первом такте работы устройства существляется прием операнда x(i) весового коэффициента W, соответ- ственно в регистры множимого и множителя умножителя комплексных чисел 1.1-1.8 (здесь.и далее будем считать, что прием в регистры осуществляется

в начале такта по фронту синхроимпульса) . На выходах матричных умножителей 1.13-1.16 появляются результаты произведения соответствуюв11«с частей комплексных чисел; ReX,,

Imx(i)-ImW. .: Rex(i) ImW- :. Imx(i).

ReW.

.j

SJ

, j , которые BO втором такте принимаются в промежуточные регистры 1.13-1.16о Во втором такте в регистры 1.1-1.8 принимаются операнды x(i + 2), . Сумматор 1,17 всегда выполняет операцию вычитания, а сумматор 1.18 - сложения и, следовательно, на выходах сумматоров 1.17 и 1.18 присутствуют величины:

ReP(i) Hex(i)-ReWi j - Imx(i) IraW- ; ImP(i) Re x(i)-IraW. .+ + Imx(i) ReW.

I, j В третьем такте в регистры 1.1- 1.8 принимаются операнды x(i + 1) и W.ij, в регистры 1.13-1.16 - произведения

Rex(i + 2) ReWj.jji-ImxCi + 2)

ImW

1tt,J

ItnWi,,j ; Rex(i + 2) Im(i + 2) ReW,, ;

в регистр 2 - величина ReP(i),B регистр 4 - величина ImP(i).

В четвертом такте в регистры 1.1- 1.8 принимаются операнды x(i + 3) и i+3.j регистры 1.13-1.16 - произведения Rex(i + 1)-W.,j ; Imx(i +

.J i O-ImWi,,,,; Iinx(i -f 1)-ReW.,j , в регистр 3 - величина ReP( i -f 2) j в регистр 3 - величина ImP(i « 2), в регистр 6 - из регистра 2 величина ReP(i), в регистр, 7 - из регистра 4 величина ImP(i), сумматоры 8 и 9 выполняют операцию

сложения.

В пятом такте в регистры 1.1-1.8 принимаются исходные операнды для выполненрш следующей базовой опера- ции x(i 4) и , в регистры 1.131.16 - произведения Rex(i + 3) ReW; jj; Itnx(i + 3)-ImW.,,jj ; Rex(i + 3)-ImW. Imx(i + 3)- , в регистр 2 - личина ReP(i + 1),Б регистр 4 - величина ImP(i + 1), в регистр 10 - ве-

личина ReP(i) + ReP(i 2)1 , в регистр 15 - величина IraP(i) + ImP(i+ + 2), сумматоры 8 и 9 выполняют операцию вычитания.

В шестом такте в регистры 1.1-1.8 принимаются операнды x(i + 6) и W в регистры 1.13-1.16 - произведения 4) ReW., i : Imx(i + Д)- ImW

ся величина ReP(i + 5) , в регистр 4- величина ImP(i + 5), в регистр 10 - величина ReP(i + А) + ReP(i + 6)) , в регистр 15 величина linPd + 4) +

Rex(i 4) ; Imx(i + .,

Rex(i 4) IraW. j ; Imxd + 4)ReW. - 5 + ImP(i + 6) , сумматоры 8 и 9 выпол- ., / . IN 1 НЯЮТ операцию вычитания, сумматор

в регистр 3 - величина ReP(i + 3), в регистр 4 - величина IinP(i + 3), в регистр 6 - величина ReP(i + 1), в регистр 7 - величина .ImP(i +1), в регистр 12 - величина CReP(i) - - ReP(i 2) , в регистр 17 - величина TlmPd) - ImP(i + 2) . Сумматоры 8 и 9 вьтолняют операцию сложения.

В седьмом такте в регистры 1.1- t.8 принимаются операнды x(i +5) и

20 вьшолняет вычитание содержимого регистров 18 и 14, сумматор 21 -- сложение содержимого регистров 19 и 13, (О В результате на выходах сумматоров 20 и 21 получаем в&личины Rex(i + 1) и Imx(i + 1) соответственно.

На десятом такте в регистры 1,1- 1.8 принимаются операнды x(i + ТО),

t5 W.

(4io,j

В регистры 1.13-1.16 - регистры 1.13-1.16 - произведения Rex(i + 6) ReWjVg.j-; Inix(i +

+ 6) ImW,-,j ; Rex(i + 6j ImWj

+6,J

изведения Rex(i + 8) j, 1пк(1+ + 8) ImW,,g ; Rex(i + 8)-imW;, ImxCi + 8)- ReW j , в регистр 3 принимается величина ReP(i + 7), в реlmx(i + 6) , в регистр 2 - ве-20 гийтр 5 - величина IinP(i + 7), в личина ReP(i + 4), в регистр 4 - ве-регистр 6 - величина ReP(i + 5), в

личина ImP(i + 4), в регистр 11 - сум- регистр 7 - величина ImP(i + 5),в рема ReP(i + 1) + ReP(i + 3)j , в регистр 16 - сумма ImP(i + 1) + ImP(i+

гистр 12 - величина ReP(i + 4) - - ReP(i + 6)J , в регистр 17 - вели+ 3)1 .Сумматоры 8 и 9 выполняют one-25 чина. ImP(i + 4) - ImP(i + 6) , cyrtрацию вычитания, сумматор 10 - сложение содержимого регистров 10 и 12, сумматор 21 - сложение содержимого регистров 15 и 17. В результате на выходе сумматора 20 получаем Rex(i), а сумматора 21 - Imx(i).

В восьмом такте в регистры 1.1- 1.8 принимаются операнды x(i + 1) и W;, j , в регистры 1.13-1.16 - произведения Rex(i -t- 5)-ReW; s,; Imx(i + + 5)-lraW; s j; Rex4 + 5) imW,,j ; Imx( 5) ReVI| 5j , в регистр 3 - величина ReP(i + 6J, в регистр 4 - величина ImP(i + 5), в регистр 6 - величина ReP(i + 4), в регистр 7 - величина ImP(i + 4), в регистр 13 т величина ReP(i + 1) - ReP(i + 3)J , в регистр 14 - величина fImP(i + )- - lmP(i + 3) , содержимое регистров

30

матеры 8 и 9 выполняют операцию сложения, сумматор 20 выполняет сложение содержимого регистров 18 и 14, сумматор 21 - вычитание содержимого регистров 19 и 13. В результате на выходах сумматоров 20 и 21 получаем величины RexCi + 3) и Imx(i + 3) соответственно.

На одиннадцатом -такте в регистры 35 1.1-1.8 принимаются операнды x(i +

i 9,J

+9)иW;,„,, В регистры 1.13-1,16 произведения Rex(i + 9) ReW , Imx(i + 9) ImW.,,j -, RexCT-- - 5). ImW;, j-, Imx(i + 9) , в pe- 40 гистр i принимается величина ReP(i+ + 8),- в регистр 4 - величина IraP(i + и- 8), в регистр 11 - величина ReP{i + 5) + ReP(i + 7) , в регистр 16 - величина ImP(i + 5) + ImP(i -i- 7) ,

произведения Rex(i + 9) ReW , Imx(i + 9) ImW.,,j -, RexCT-- - 5). ImW;, j-, Imx(i + 9) , в pe- 40 гистр i принимается величина ReP(i+ + 8),- в регистр 4 - величина IraP(i и- 8), в регистр 11 - величина ReP{ + 5) + ReP(i + 7) , в регистр 16 - величина ImP(i + 5) + ImP(i -i- 7) ,

11 и 16 переписывается в регистры 18 45 сумма-горы 8 и 9 выполняют операцию и 19 соответственно Сумматоры 8 и 9 вычитания, сумматоры 20 и 21 - one- выполняют операцию сложения, сумматор 20 вычитает содержимое регистров 10 и 12, сумматор 21 - содержимое регистров 15 и 17. Б результате на so выходе сумматора 20 получаем Rex(i -sрацию сложения содержимого регистров Ю и 12, 15 и 17 соответственно.

В результате на выходе получаем x(i - 4).

Далее работа устройства продолжается аналогичным образом.

2), Ц сумматора 2t - Imx(i + 2).

В девятом такте в регистры 1.1-1.8 принимаются операнды x(i +8), WI +S,J

в регистры 1.13-1.16 - произведения RexCi + 7)-ReW.,j ; Imxd + 7)

IJoW,4,,, ,

Rex(i + 7) ImW

+ 7,J

Imx(i +

+ 7) ReW;., J , в регистр 2 принимается величина ReP(i + 5) , в регистр 4- величина ImP(i + 5), в регистр 10 - величина ReP(i + А) + ReP(i + 6)) , в регистр 15 величина linPd + 4) +

20 вьшолняет вычитание содержимого регистров 18 и 14, сумматор 21 -- сложение содержимого регистров 19 и 13, В результате на выходах сумматоров 20 и 21 получаем в&личины Rex(i + 1) и Imx(i + 1) соответственно.

На десятом такте в регистры 1,1- 1.8 принимаются операнды x(i + ТО),

W.

(4io,j

В регистры 1.13-1.16 - произведения Rex(i + 8) j, 1пк(1+ + 8) ImW,,g ; Rex(i + 8)-imW;, ImxCi + 8)- ReW j , в регистр 3 принимается величина ReP(i + 7), в ре регистр 7 - величина ImP(i + 5),в регистр 12 - величина ReP(i + 4) - - ReP(i + 6)J , в регистр 17 - вели

матеры 8 и 9 выполняют операцию сложения, сумматор 20 выполняет сложение содержимого регистров 18 и 14, сумматор 21 - вычитание содержимого регистров 19 и 13. В результате на выходах сумматоров 20 и 21 получаем величины RexCi + 3) и Imx(i + 3) соответственно.

На одиннадцатом -такте в регистры 1.1-1.8 принимаются операнды x(i +

i 9,J

+9)иW;,„,, В регистры 1.13-1,16 произведения Rex(i + 9) ReW , Imx(i + 9) ImW.,,j -, RexCT-- - 5). ImW;, j-, Imx(i + 9) , в pe- гистр i принимается величина ReP(i+ + 8),- в регистр 4 - величина IraP(i + и- 8), в регистр 11 - величина ReP{i + 5) + ReP(i + 7) , в регистр 16 - величина ImP(i + 5) + ImP(i -i- 7) ,

сумма-горы 8 и 9 выполняют операцию вычитания, сумматоры 20 и 21 - one-

сумма-горы 8 и 9 выполняют операцию вычитания, сумматоры 20 и 21 - one-

рацию сложения содержимого регистров Ю и 12, 15 и 17 соответственно.

В результате на выходе получаем x(i - 4).

Далее работа устройства продолжается аналогичным образом.

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

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

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

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

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

внишш

Заказ 2653/53

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

Тираж 671

Подписное

Изобретение относится к области вычислительной техники и может быть использовано при построении специализированных устройств, выполнямщи алгоритм быстрого преобразования Фурье по основанию 4. Цель изобрете- ния - повьнпение быстродействия. В состав устройства входит умножитель комплексных чисел, шестнадцать регистров и четыре сумматора с соответ- ствукяцими связями между ними. 1 ил. ю 00 У 00