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

 

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

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

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

РЕСПУБЛИК

716 А1 (19) (11) ш 4 G 06 F 15/332

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

Н ASTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3909616/24-24 (22) 15.04.85 (46) 07.02 ° 87. Бюл. Е 5 (72) Т,И,Федоровская (53) 681.32 (088.8) (5e) Авторское свидетельство СССР

У 1078433, кл. С 06 Г 15/332, 1984.

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

В 1098004, кл. G 06 F 15/332, 1980. (54) ПРОЦЕССОРНЫЙ ЭЛЕМЕНТ УСТРОЙСТВА

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

1 12

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

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

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

Процессорный элемент содержит входные регистры 1-4, регистры 5 и б коэффициента, коммутаторы 7-10, умножители 11-14, регистры 15-20, сумматоры 21 и 22, коммутаторы,2326, сумматоры 22-30, выходные регистры 31-34.

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

А,.Ä (j) А,()) +A,. (k) W ;;

А. (k) А,. (j) — А, (k) W (1) 88716 2 чает комплексное произведение, получают (3) Взвешивание, т.е. умножение на взвешиваемую функцию "окна", производится на первой итерации, при этом значения входных отсчетов

X(n) =Re X(n)+j Im X(n), n=0,N-1

f5 умножаются на взвешивающую функцию .

C(n), значения которой могут храниться в ПЗУ. Полученный результат

А (n)=Re X(n) C(n)+j ImX(n) С(п) = (4)

=Re А,(n)+j ImA (n) 37 А, (j)=A (j) + А (k) °

А, (k) =A,(З) — A. О ) Re А, (j) = Re A,(j)+Re А, (k);

Im А, (j) = Im А (j)+Im А, (k);

Re А, (k) = Re А,{ j ) -Re А,(k) °

Im А, (k) = Im А, (j ) -Im А, (k)

Учитывая равенства (4) выражения (5) принимают вид

Im А,, (j) =Im А, (j)+(Im А; (k) Re W +

+ ReA;(k) ImW 1; (2)

Re А. (k)=Re А, (j)-1Ке A;(k) Re W +

+ ImA; (k) ХшИ

Im А.„, (k) =Im А; (j ) - Im А,, (k) Ке W

Обозначив выражения, стоящи в квадратных скобках, соответственно через Re(KII) и Im(KII),,ãäå КП озна-. где i — номер итерации;

A=Re A(j)+j ImA(j) — значение первого операнда;

A(k) Re A(k)+j Im — значение второго операнда; . 2> .

Р "N Р 2 23"

W =е сов - p j sin p:=

Р

P P

= Re W — j ImW — значение тригонометрического коэффициента, P — - показатель, значение которого зависит от номера интерации и номера первого операнда j или

Re А,„(j) Re А; (j)+1Re A; (k) Re W +

+ ХША,(k) ImW

Re А. (j)=Re А, (j)+Re (КП);

ХшА, (j)=ХшА; (j)+Im {КП);

Re А, .„(k) =Re А; (j ) -Re (KII) ф

Im A;„(k) =Im A; (j)-Im (КП), подвергается спектральной обработке по алгоритму БПФ. Так как на первой итерации в алгоритме с прореживанием по времени значение P для любой пары операндов равно нулю, W =1, то выражения (1) в первой итерации принимают вид

Re А, (j) = Re X(j) C(j) + Re X(k) C(k)g

ImA,(j) = ImX(j) C(j) + ImX(k) С{) () (6)

Re А, (k) = Re X(j) C(j) — Re X(k) C(k);

Im А, (k) = ImX(j) C(j) -ImX(k) C(k);

Эти выражения с точностью до знаков операций совпадают с соответствующими выражениями, стоящими в квадратных скобках указанных формул, и, следовательно, произведения могут быть получены на тех же умножителях, а знаки арифметических операций совпадают со знаками арифметических опе раций соответствующих выражений, которые выполняются на четырех сумматорах одновременно. Следователь12887 но, получить произведения для выражений (5) на умножителях 11-14 можно, подав эти значения на сумматоры 27-30, получить результат первой итерации, совмещенной с операцией 5 взвешивания без перестройки режимов работы сумматоров.

На основании изложенного устройство работает следующим образом. 1р

В первой итерации на первые адресные входы всех коммутаторов поступает сигнал D дающий разрешение на их первые входы, на вторые адресные входы одновременно поступает инверсный сигнал D.

При подаче на тактовые входы первых шести регистров 1-6 сигнала F1 в регистры 1-6 записаны соответственно действительная и мнимая части 2р первого и второго операндов и соответствующие им два коэффициента взвешивающей функции 11окна1 ° Так как первый и второй операнды, независимо от того каков порядок следования 25 входных отсчетов — прямой или двоично-инверсный — отстоят один от другого по номерам íà N/2, то и коэффициенты "окна" первый и второй также отстоят на N/2 номеров, где 30

N — длина обрабатываемой входной последовательности. Таким образом, на входы умножителей 11-14 поступают соответственно следующие пары сомножителей Re X(j ) и C (j ), Re X (k) и C(k), ImX(j) и C(j), Im X(k) и

C(k) . Импульсом F2, сдвинутым относительно F1 на длительность такта умножения, результат произведения с умножителей 11-14 записывается в ре- 4р гистры 15-18, одновременно в этой итерации, как и во всех последующих, в регистры 19-20 переписывается содержимое регистров 1-2, которое в первой итерации не используется, но 45 позволяет ввести одинаковое управление во всех итерациях. Сумматоры

21 и 22 производят операции, но результат с них никуда не поступает, так как вторые входы коммутаторов 5р

23-26 заблокированы, как и для содержимого регистров 19 и 20. Регистры

1-6 свободны для принятия новой информации, и следующим импульсом Р1 производится за s них следующей 55 пары операндов и коэффициентов взвешивающей функции. Одновременно информация с промежуточных регистров 15-18 через входы коммутаторов

16 4

23-26 поступает на сумматоры 27-30, с помощью которых происходит формирование выходного результата в соответствии с выражениями (5), при1 чем первые два сумматора 27 и 28 работают в режиме суммирования, вторые

29 и 30 — в режиме вычитания.

Полученные результаты записываются в регистры 31 — 34 по сигналу F3, задержанному относительно F2 на длительность, равную двум тактам сложения: I — сумматоры 21 и 22, II сумматоры 27 — 30. Для органиэации синхронной работы процессорного элемента (ПЭ) запись информации во все регистры: входные, промежуточные и выходные, должна производиться одновременно, поэтому из двух длительностей -"умножения" и "сложения", выбирается наибольшая и с этим тактом работает ПЭ. Таким образом, сигналы

F1, F2, F3 одинаковые, имеют только различную первоначальную задержку.

При записи информации в регистры 3134 в регистры 15-20 производится запись информации с умножителей 11-14 (результат произведений второй пары операндов на вторые коэффициенты функции "окна"), а на регистры 1-6 происходит запись следующих пар операндов и коэффициентов функции "окна".

После выполнения первой интерации сигналы 0 и 0 изменяют свое значение на инверсное, при этом открытым получается второй вход всех коммутаторов. По сигналу Fl через коммутаторы 7 и 8 в регистры 5-6 записываются значения соответственно действительной и мнимой частей тригонометрического коэффициента, а в регистры

1-4 — соответственно пара операндов в соответствии с реализуемым графом алгоритма БПФ. Затем на умножителях

11-14 вычисляются соответствующие произведения Im A(k).Im W; Re А(1)*

Же W; Re А (k) Im W, ImA(k) ° Re W,. которые по сигналу F2 записываются в регистры 15-18, а в регистры 1920 записываются соответственно Re A(j) и Im A(j) . Далее частичные произведения поступают на сумматоры 21 и 22, на которых вычисляются окончательные значения комплексного произведения, причем сумматор 21 работает в режиме сложения, сумматор 22 — в режиме вычитания. Результат суммирования

Re (КП) и Еш (КП) (формулы 2 и 3) поступает через входы коммутаторов

128871б

55

24-26 на соответствующие входы сумматоров 27-30, на другие входы которых поступает через входы коммутаторов 23 и 25 содержимое регистров 19 и 20. Результат с сумматоров 27 — 30 по сигналу F3 записывается в регистры 31-34. Такт работы во второй и всех последующих итерациях точно та кой же, как и в первой. Дальнейшая обработка аналогична описанной.

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

Процессорный элемент устройства.. для быстрого преобразования Фурье, содержащий первый входной регистр, выход которого подключен к информа— ционному входу первого регистра и первому информационному входу первого коммутатора, выход которого под-4 ключен к первому входу первого умножителя, выход которого подключен к информационному входу второго регистра, выход которого подключен к первому входу первого сумматора, выход второго входного регистра подключен к информационному входу третьего регистра и первому информационному входу второго коммутатора, выход которого подключен к первому входу второго умножителя, выход которого подключен к информационному входу четвертоro регистра, выход которого подключен к первому входу второго сумматора, выход третьего выходного регистра подключен к второму информационному входу второго коммутатора и первому входу третьего умножителя, выход которого подключен к информационному входу пятого регистра, выход которого подключен к второму входу первого сумматора, выход четвертого входного регистра подключен к второму информационному входу первого коммутатора и первому входу четвертого умножителя„ выход которого подключен к информационному входу шестого регистра, выход которого подключен к второму входу второго сумматора, вторые входы третьего, четвертого умножителей, подключены к выходу первого регистра коэффициента, информационный вход которого подключен к выходу третьего коммутатора, первый информационный вход которого является входом реальной части коэффициента устройства, входом мнимой части коэффициента которого является первый информационный вход четвертого коммутатора, выход которого подключен к информацибнному входу второго регистра коэффициента, выход которого подключен к вторым входам первого и второго умножителей, выходы третьего, чет . вертого, пятого и шестого сумматоров подключены к информационным входам соответственно первого, второго, третьего и четвертого выходных регистров, выходы которых являются соответственно выходами реальной и мнимой частей первого результата устройства и выходами реальной и мнимой частей второго результата

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

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

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

Редактор Н.Бобкова Техред Л.Олейник Корректор Т.Колб

Заказ 7810 48 Тираж 673 Подписное

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

rro делам изобретений:и открытий

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 ра четвертого регистра и второго сумматора подключены к вторым информационным входам соответственно пятого, шестого, седьмого и восьмого коммутаторов, первые адресные входы которых соединены между собой и подключены к четвертому тактовому входу устройства, к пятому тактовому входу которо16 8 го подключены соединенные между собой вторые адресные входы коммутато" ров с пятого по восьмой, а вторые информационные входы третьего и четвертого коммутаторов являются входами задания соответственно первой и вто.рой половины весовой функции усввойства.