Процессорный элемент устройства для быстрого преобразования Фурье Советский патент 1987 года по МПК G06F17/14 

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

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

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

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

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

А(,, (j)A.(j) +A,.(k)-W А. (k)-A. (J) -А, (k).W%

(1)

где i - номер итерации; (j)+j ImA(j) - значение первого операнда;

A(k)Re A(k)-i-j Im - значение второго операнда; ;2li . 2И . . 271.

W

соа Р J sin Р

ReW - j ImW

35

- значение тригонометрическогокоэффициента; Р - показатель, значение которого

зависит от номера интерации i 40 и номера первого операнда j,

или

ReA., (j)ReA. (j) + lReA(k) ReW + + ImA; (k) ImW

ImAj (j)ImA(j)(k) t- Re A,(k) Imw ;

Re A. (k)Re A. (j)-tRe A-(k) Re W + . + ImA.,(k) Imw ;

ImA.,, (k)ImAi(j)-tlmA.(k) Re W - ReA;(k) ImW

Обозначив выражения, стоящие в квадратных скобках, соответственно через Re(Kn) и 1т(КП),,где КП озна

чает комплексное произведение, получают

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

ImA. (j)ImA,-(j)+Im (КП);

Re А, (k)Re А- (j)-Re (КП);

ImA, (k)ImA. (j)-Im (КП) ;

(3)

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

X(n)ReX(n)+j ImX(n), ,N-1

умножаются на взвешивающую функцию . С(п), значения которой могут храниться в ПЗУ, Полученньй результат

20

A(n)ReX(n) C(n)+j ImX(n) C(n.) ReA(n)+j ImAo(n)

(4)

подвергается спектральной обработке по алгоритму БПФ, Так как на первой итерации в алгоритме с прореживанием по времени значение Р для любой пары операндов равно нулю, , то выражения (1) в- первой итерации принимают вид

А, (j)A,(j) + A/k); A,(k)A(j) - A(k)

35

о

i 40

2)

(5)

или

Re A, (j ) Re A (j ) +Re А„ (k) ; ImA,(j) ImA(j)+ImA(k); ReA, (k) ReA/j)-ReA(k); ImA, (k) ImA/j)-ImA;,(k).

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

ReA,(j) ReX(j) C(j) + Re X(k) C(k); ImA, (j) ImX(j) C(j) +ImX(k) C(k) ReA(k) ReX(j) C(j)-ReX(k) C(k); ImA/k) ImX(j) C(j)-ImX(k) C(k);

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

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

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

При подаче на тактовые входы первых шести регистров 1-6 сигнала F1 в регистры 1-6 записаны соответственно действительная и мнимая части первого и второго операндов и соответствующие им два коэффициента взвешивающей функции окна. Так как первый и второй операнды, независимо от того каков порядок следования входных отсчетов - прямой или двоично-инверсный - отстоят один от другого по номерам на N/2, то и-коэффициенты окна первый и второй также отстоят на N/2 номеров, где N - длина обрабатываемой входной последовательности. Таким образом, на входы умножителей 11-14 поступают соответственно следующие пары сомножителей ReX(j) и С(з),КёХ(К) и C(k), ImX(j) и C(j),ImX(k) и C(k). Импульсом F2j сдвинутым относительно F1 на длительность такта умножения, результат произведения с умножителей 11-14 записьшается в регистры 15-18, одновременно в этой итерации, как и во всех последующих в регистры 19-20 переписывается содержимое регистров 1-2, которое в первой итерации не используется, но позволяет ввести одинаковое управление во всех итерациях. Сумматоры 21 и 22 производят операции, но результат с них никуда не поступает, так как вторые входы коммутаторов 23-26 заблокированы, как и для содержимого регистров 19 и 20. Регистры 1-6 свободны для принятия новой информации, и следующим импульсом F1 производится запись в них следующей пары операндов и коэффициентов взвешивающей функции. Одновременно информация с промежуточньЬс регистров 15-18 через входы коммутаторов

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

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

5

0

0

исходит запись следующих пар операндов и коэффициентов функции окна.

После выполнения первой интерации сигналы D и D изменяют свое значение

на инверсное, при этом открытым получается второй вход всех коммутаторов. По сигналу F1 через коммутаторы 7 и В в регистры 5-6 записьгаают- ся значения соответственно действительной и мнимой частей тригонометрического коэффициента, а в регистры 1-4 - соответственно пара операндов в соответствии с реализуемьтм графом алгоритма БПФ. Затем на умножителях

11-14 вычисляются соответствующие произведения ImA(k) Re A(k) ReW ; ReA (k)-lmw ; ImA(k)ReWr которые no сигналу F2 .записьгоаются в регистры 15-18, а в регистры 1920 записываются соответственно Re A(j) и ImA(j). Далее частичные произведе- НИН поступают на сумматоры 21 и 22, на которых вычисляются окончательные значения комплексного произведения,

причем сумматор 21 работает в режиме сложения, сумматор 22 - в режиме вычитания. Результат суммирования Re (КП) и Ira (КП) (формулы 2 и 3) поступает через входы коммутаторов

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

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

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

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

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

712887

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

8

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

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

w