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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„SU„„2 151 ур 4 С 06 F 15/332 с..

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

Н АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3816662/24-24 (22) 27. 11.84 (46) 15.05.86. Бюл. В 18 (;71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (?2) Ю.С.Каневский, Л.Г.Кравец, Н.E.Êóö, В.И.Лозинский и Б.А.Некрасов (53) 681.32(088.8} (56) Рабннер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. М. г Мир, 19 78 .

Авторское свидетельство СССР

В 999061, кл. С 06 Р 15/332, 1982. (54) АРИФЬЖТИЧЕСКОЕ УСТРОЙСТВО ДЛЯ

БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к области вычислительной техники и может быть использовано при построении специализированных устройств, выполняющих алгоритм быстрого преобразования

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

231513

2 ственно в регистры множимого и множителя умножителя комплексных чисел

1.1-1.8 (здесь.и далее будем считать, что прием в регистры осуществляется в начале такта по фронту синхроимпульса). На выходах матричных умножителей 1.13-1.16 появляются резульХ. P(i) 1+ P(i+ 1) 1+

+ Р(1 + 2).1 + P(i + 3) 1, Х,.„= P(i) 1 + P(i + 1) j +

+ P(i + 2)(-1) + P(i + 3) (-j), (1)

Х, P(i) 1+ Р(з. + 1)(1) +

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

X — P(i) 1 + Ь + 1) (-j)

+ P(i + 2)(-1) + P(i + 3) ° j, где P(i) ° Х M; „., j = -Т, х" - исходные отсчеты;

W - весовые коэффициенты, Х - результаты выполнения элементарной операции БПФ

Выражение (1) может быть представ лено в виде:

4О

ReX. (ReP(i) + ReP(i + 2) +

+ (КеР (л. + 1) + -ReP (i + 3));

ReX,„ = (ReP(i) - ReP(i + 2))

- (IW(i + 1) — тР(+ 3));

ReX, (ReP(i) + ReP(i + 2)) (ReP(i + 1) + ReP(i + 3));

Кех,, (Кер(1) — ReP(i. + 2)) +

+ (ImP(i + 1) - ImP(i + 3));

ImP)(. (ImP(i) + ImP(i + 2Ц +

+ (ImP(i + 1) + 1шР(л. + 3)); (2)

ImX.„ = fImP(i) — IrnP(i + 2)) +

+ .(ReP(i + 1) - ReP(i + 3))

ImX,, = (ImP(i) + ImP(i + 2))

ПшР(1 + 1) + IrnP(i + 3)3

ImX, (АР(1) ImP(i + 2)) — (ReP(i + 1) — ReP(i + 3)) .

В первом такте работы устройства осуществляется прием операнда x(i) и весового коэффициента W; „ соответ1

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

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

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

Арифметическое устройство для быстрого преобразования Фурье содержит умножитель 1 комплексных чисел, состоящий из регистров 1. 1-1.8, умножителей 1.9-1,12, регистров 1.131.16 и сумматоров 1.17-1.18, регистры 2-7, сумматоры 8-9, регистры 1019, сумматоры 20-21, тактовый вход

22 устройства.

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

Ъ вида:!

О

25 таты произведения соответствующих частей комплексных чисел; КеХ,КеИ;;, Imx(i) ImW, Rex(i) ImW;„, Imx(i)

° ReW... которые во втором такте принимаются в промежуточные регистры

1.13-1.16. Во втором такте в регистры 1.1-1.8 принимаются операнды

x(i + 2), W.„ „, Сумматор 1.17 всегда выполняет операцию вычитания, а сумматор 1.18 — сложения и, следовательно, на выходах сумматоров 1.17 и 1.18 присутствуют величины:

ReP(i) = Rex(i) ReW> „ - Imx(i)*

° ImW;,, ImP(i) = Rex(i) ImW, +

+ Imx(i) ReW., В третьем такте в регистры 1.11.8 принимаются операнды x(i + 1) и

Ы ... в регистры 1.13-1.16 — произвеI дения

Rex(i + 2) ReW;, Imx(i + 2) °

° ImW; „„; Rex(i + 2) ImW

Imx(i + 2) ReW в регистр 2 - величина ReP(i),í регистр 4 — величина ImP(i).

В четвертом такте в регистры 1.11.8 принимаются операнды x(i + 3) и

W„„, в регистры 1.13-1.16 — произведения Rex(i + 1) ° W;„,; Irnx(i +

+ I) ImW.„, „; Rex(i + 1) ° ImW.„„„; + 41

Imx(i + I) ReW., в регистр 3 — величина КеР(i + 2); в регистр 3величина ImP(i + 2), в регистр 6 — из регистра 2 величина ReP(i), в регистр, 7 — из регистра 4 величина ImP(i), сумматоры 8 и 9 выполняют операцию сложения.

В пятом такте в регистры 1.1-1.8 принимаются исходные операнды для выполнения следующей базовой операции х(1 + 4) и W „;, в регистры 1.131.16 — произведения Rex(i + 3) ReW., Imx(i + 3)- ImW„» ; Rex(i + 3) ImW.

Imx(i + 3)- ReW;, в регистр 2 — величина ReP(i + 1),в регистр 4 - величина ImP(i + 1), в регистр 10 — величина EReP(i) + ReP(i + 2)), в регистр 15 — величина EImP(i) + ImP(i+

+ 2Н, сумматоры 8 и 9 выполняют операцию вычитания.

3 123

В шестом такте в регистры 1 ° 1-1.8 принимаются операнды x(i + 6) . и W.„„. в регистры 1.13" 1.16 — произведения

Rex(i + 4) ReW.,„„; Imx(i + 4) ImW.,„„

Rex(i + 4) ° ImW.,; Imx(i + 4)" ReW. „ ; в регистр 3 — величина ReP(i + 3), в регистр 4 — величина ImP(i + 3), в регистр 6 — величина ReP(i + 1), в регистр 7 — величина .ImP(i + t), в регистр 12 — величина (ReP(i) — 10 — ReP(i + 2)), в регистр 17 — величина (ImP(i) — ImP(i + 2)) . Сумматоры 8 и 9 выполняют операцию сложения.

В седьмом такте в регистры 1.1- 15

1.8 принимаются операнды x(i + 5) и

W, „, в регистры 1 ° 13-1.16 — произ +5, ведения Rex(i + 6) ReW;, .„.; Imx(i +

+ 6) ImW;.ü J Rex(i + 6) ImW; ь J., Imx(i + 6) ReW.,„, в регистр 2 — ве-20 личина ReP(i + 4), в регистр 4 — величина ImP(i + 4), в регистр 11 — сумма EReP(i + 1) + ReP(i + 3)), в регистр 16 — сумма (ImP(i + 1) + ImP(i+

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

В восьмом такте в регистры 1.11.8 принимаются операнды x(i + 1) и

W;+ „, в регистры 1.13-1.16 — произведения Rex(i + 5) ReW;,», Imx(i +

+ 5) ImW(+5JJ Rex i + 5) ImW 5

Imx(i-+ 5) ReW;,5 „, в регистр 3 — величина ReP(i + 6) в регистр 4 — величина ImP(i + 5), в регистр 6— величина ReP(i + 4), в регистр 7 величина ImP(i + 4), в регистр 13 — . величина (ReP(i + 1) — ReP(i + 3)), s регистр 14 — величина (ImP(i + )— ImP(i + 3)) . содержимое регистров

11 и 16 переписывается в регистры 18 4 и 19 соответственно. Сумиаторы 8 и 9 выполняют операцию сложения, сумматор 20 вычитает содержимое регистров

10 и 12, сумматор 21 — содержимое. регистров 15 и 17. В результате íà 5о выходе сумматора 20 получаем Rex(i +

+ 2), а сумматора 21 — Imx(i + 2).

В девятом такте в регистры 1.1-1.8 принимаются операнды x(i + 8), W;,д„, в регистры 1. 13-1. 16 — произведения

Rex(i + 7) ReW. Imx(i + 7)

1шИ;„,, Rex(i + 7) ImW», Imx(i +

+ 7) ReW;. „, в регистр 2 принимает1

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

+ ImP(i + 6)), сумматоры 8 и 9 выполняют операцию вычитания, сумматор

20 выполняет вычитание содержимого регистров 18 и 14, сумматор 21 - сложение содержимого регистров 19 и 13.

В результате на выходах сумматоров

20 и 21 получаем величины Rex(i + 1) и Imx(i + 1) соответственно.

На десятом такте в регистры 1 ° 11.8 принимаются операнды x(i + 10)

W, „, в регистры 1.13-1.16 - произведения Rex(i + 8) КеИ; „, Imx(i+

+ 8) ImW,; Rex(i + 8) ImW;, Imx(i + 8). ReW в регистр 3 принимается величийа ReP(i + 7) ° в региСтр 5 — величина ImP(l. + 7), в регистр 6 — величина ReP(i + 5), в регистр 7 — величина ImP(i + 5),â регистр 12 — величина (ReP(i + 4) — ReP(i + 6)), в регистр 17 — величина. (ImP(i + 4) — ImP(i + 6)), сумматоры 8 и 9 выполняют операцию сложения, сумматор 20 выполняет сложение содержимого регистров 18 и 14, сумматор 21 — вычитание содержимого регистров 19 и 13. В результате на выходах сумматоров 20 и 21 получаем величины Rex(i + 3) и Imx(i + 3) соответственно.

На одиннадцатом .такте в регистры

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

+ 9) и М,, в регистры 1.13-1.16произведения Rex(i + 9) ReW

Imx(i + 9) ImW „„; Rex(i + 0)

» ImW „„; Imx(i + 9) ReW„< „, в регистр 2 принимается величйна ReP(i+

+ 8), в регистр 4 — величина ImP(i +

+ 8), в регистр 11 — величина (ReP(i

+ 5) + ReP(i + 7Ц, в регистр 16— величина (ImP(i + 5) + ImP(i + 7)), сумма-.оры 8 и 9 выполняют операцию вычитания, сумматоры 20 и 21 — операцию сложения содержимого регистров

10 и 12, 15 и 17 соответственно.

В результате на выходе получаем

x(i + 4).

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

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

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

Тираж 671 Подписное

Закаэ 2653/53

ВНИИПИ

Проиэводств.-полиграф. пред-е г. Ужгород, ул. Проектная, 4 сел, первый, второй, третий и четвертый входы которого являются входами соответственно реальной и мнимой частей операнда и реальной и мнимой частей коэффициента устройства, первый, второй, третий и четвертый сумматоры, выходы третьего и четвертого сумматоров являются выходами соответственно реальной и мнимой частей операндов устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, и него введены шестнадцать регистров, выход реаль.ной части умножителя комплексных чисел подключен к информационным входам первого и второго регистров, выходы которых подключены соответственно к первому входу первого сумматора и информационному входу третье- го регистра, выход которого подключен к второму входу первого сумматора, выход которого подключен к информационным входам четвертого, пятого, шестого и седьмого регистров, выходы которых подключены соответственно к первому входу третьего сумматора, первому входу четвертого сумматора, информационному входу восьмого регистра и второму входу четвертого сумматора, выход мнимой части умножителя комплексных чисел подключен к информационным входам девятого и десятого регистров, выходы которых подключены соответственно к первому входу второго сумматора и информаf0 ционному входу одиннадцатого регистра, выход которого подключен к второму входу второго сумматора, выход которого подключен к информационным входам двенадцатого, тринадцатого, 1 четырнадцатого и пятнадцатого регистров, выходы которых подключены соответственно к первому входу третьего сумматора, информационному входу шестнадцатого регистра, второму вхо20 ду третьего сумматора и первому входу четвертого сумматора, выходы шестнадцатого и восьмого регистров подключены к вторым входам соответственно третьего и четвертого суммато25 ров, а тактовые входы шестнадцати регистров обьединены, и являются тактовым входом устройства.