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

 

Изобретение относится к вычислительной технике и может быть использовано в аппаратуре радиоэлектронной и измерительной техники. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят блок памяти 1, коммутаторы 2-5, регистр 6, блоки регистров 7-9, арифметический блок 10, умножитель 11, регистры 12, 13, блок постоянной памяти 14, блок синхронизации 15, информационный вход 16 устройства, информационный выход 1 7 устройства,выходы 18-40 блока синхронизации,тактовый вход 41 и вход запуска 42 устройства. 1 з.п. , 3 ил. (Л

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

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

РЕСПУБЛИК

А1

„;SU„„ 142570 511 4 С 06 F 15/332

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

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

ПО ДЕЛ*М ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ С8ИДЕТЕЛЬСТВУ (21) 4213589/24-24 (22) 18.03.87 (46) 23,09.88. Бюл. У 35 (71) Специальное конструкторское бюро вычислительной техники Института кибернетики АН ЭССР (72) И.О.Арро, Э,И.Герми и Л.Э.Смолянский (53) 621.32(088.8) (56) Авторское свидетельство СССР

У 1078434, кл. G 06 F 15/332, 1982.

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

Р 1020833, кл. G 06 F 15/332, 1981. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано в аппаратуре радиоэлектронной и измерительной техники. Цель изобретения — повышение быстродействия.

Поставленная цель достигается эа счет того, что в состав устройства входят-блок памяти 1, коммутаторы

2-5, регистр 6, блоки регистров 7-9, арифметический блок 10, умножитель

11, регистры 12, 13, блок постоянной памяти 14, блок синхронизации 15, информационный вход 16 устройства, информационный выход 17 устройства, выходы 18-40 блока синхронизации,тактовый вход 41 и вход запуска 42 устройства, 1 s.ï. ф.спы, 3 ил.! 425708 с в оди тс я к н еч е тным трансформа нт ным преобразованиям НТП-М/Н.

Тогда косинус-коэффициенты спектра располагаются в выходном массиве в порядке возрастания номеров гармоник с первого адреса по адрес

N/2 + 1, а синус — коэффициенты гармоник спектра в порядке убывания номеров с адреса N/2 + 2 по адрес N.

Для определения произвольных НТПN/R следует воспользоваться нечетными трансформантными преобразованиями более коротких периодов и транс15 формантным расширителем, состоящим из циклически повторяющихся двойных

"бабочек" со спектральным расширением (СПР), исходя из установившейся терминологии, Для стыковки HTII-N/2 и двух НТПN/4 с циклически повторяющимися двойными "бабочками" с СПР при двоичноинверсном порядке адресов исходных данных необходимо осуществить обмен

25 данными.

Каждый из массивов разностей Z(I) разбивается на три части, одна из которых образует половину, а две остальных — по четверти объема исход30

Математически нечетное трансформантное преобразование описывается следующими формулами.

XC(R(2k+1) = С 1„(К (г!+!)) + (12 и (1 (1) (2) (3) (4) Формулы (3) и (4) показывают, что в случае комплексных входных данных косинусиые и синусные преобразования массива X(I) выполняются в отдельности для реальной и мнимой частей. Поэтому в дальнейшем полага- 40 ют, что X(I) содержит только вещественные числа.

Тогда вычисление XC(k) и XS(k) путем вычисления сумм и разностей

Q = .X(I) = X(I) + X(I + М) 2; (5) +...+S1s (К(2!с+1)) + х (2k+1) / (M/Р);

55 м/4Р

S! ((2k+1) N/Ì =, L(2IP) х м/р т=!

= О, (I P — 3) Изобретение относится к вычислительной технике и может быть использовано в радиоэлектронной и измерительной технике.

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

Дискретное преобразование Фурье

X(k) исходного массива X(I), I LP гдето=1, N, k=1, N, N=2, определяется формулой й

X(k) = X(I) ехр

I! — 1) (k — 1)/М), где Т = — g-1

X(k) = XC(k) + TXS(k); N

XC(k) + X(1) сов (2 ю (1

Т1 — 1> (k — 1) /N)! и

XS(k) = Q X(I) sin (2 (I—

ga!

Д =* Z(I) = X(I) — X(I + N/2), (6)

I=1,М/2, где Х(Т) — входной (выходной) массив объема, М;

Z(I) — массив разностей;

M=N/R — период нечетного трансформ тного преобразования (НТП-N/R), R = 2, r =

+ С1,„/, (K(2k+1) )+ )

+... +C1s (К (2k+1) ) +

+ е(!);

XS(R(2k+1)) = Б! м (R (2k+1) ) +

+ S1„/ (R(2k+1)) + (8) + (-1) Z(M/4+1); ! м/4) ((2k+1)N/М = + Z(2IP)x м/р 1 х cos (2!1 (2I-1) х (9) 1425708

Y = Х2 — XÇ;

x s in (2 i (2 I-1) х х (2k+1) (М/P) );

Х2 = Х2 + ХЗ;

С1„,„(М/4P.-(2k+1) = -С1„, р (М/4Р+ (11)

+ (2k+1) X3 = Y, Базовая операция 2:

У1 =X0-Х1; м)р M/4Р- (2k+1) = Sl »> (M/4Р+

10 (12) ХО=ХО+Х1;

+(2)с+1) ) .

Y2 = Х2 — ХЗ;

Здесь Сl (p и Sl„-)p — косинусные и синусные нечетные трансформанты с периодом М/Р.

Общее количество арифметических операций для НТП вЂ” может быть опре- . делено по формуле

Х2 = Х2 + ХЗФ

Y3 - =Х4- Х5;

Х4 = Х4 + X5;

0(N) = (LP-2)N, N >. 8 (13) Y4=X6-Х7;

Y6 = Хб — Х7;

У3 х СОО;

У4 х СОО;

Р2

Z1 = Рl — Р2;

Z2 = Рl + Р2;

Хl = Yl + Zl;

X3 = Y1 - Z1if

Х5 = Z2 — 72;

Х7 = Z2-У2;

Ба з ов ая опеоация 3:

Мl = Х4+ Х5;

М2 = Хб + Х7;

Р1=М1 хС1; д р

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

50 четыре типовые операции: три базовые операции и одну оконечную операцию.

Базовая операция 1:

Р2 = M2 х С2;

РЗ = Х5 х СЗ;

Р4 = Х7 х С4;

Р5 Х4 х С5;

Y-=ХО-Xi;

Р6=Хбх Сб;.ХО =ХО+ Х1;

Y1 = P1 — P3;, Хl причем из них 25Х операций умножения и 757 операций сложения, На фиг.l представлена схема устройства; на фиг.2 — схема блока синхронизации; на фиг.3 — граф алгоритма.

Устройство для выполнения,дискретного, преобразования Фурье (фиг.l) со- 30 держит блок 1 памяти, коммутаторы

2-5 (операндов), регистр 6 (операндов), блоки 7-9 регистров (операндов), арифметический блок 10, умножитель

11, регистры 12 и 13 (слагаемых), блок 35

14 постоянной памяти, блок .15 синхронизации, информационный вход 16 устройства, информационный выход 17 устройства, выходы 18-40 блока синхронизации; входы (тактовый и запу- 40 ска) 41 и 42 блока синхронизации.

Блок 15 синхронизации (фиг.2) со- . держит элементы И-НЕ 43-48, счетчики

49 и 50, триггер 51, узлы 52 и 53 постоянной памяти, элементы И 54-56, 45. элементы HE 57 и 58, регистр 59,элемент 60 за е жки.

1425708

У2 Р1 - P5;

Y3 = Р2 — Р4;

У4 Р2 — Р6;

Z1 Y1+ У3

22 У2 — У4;

YÇ Y1 - Y3t

Z4 Y2+У4;

Y ХО+ Z1Х4 =ХО+ Z1;

X0 Y j

Y = Х1 + Z2Х5 Х1-$2 х1 Ó;

У = ZÇ - Х2;

Х6 - "ЕЗ+ Х2;

Х2 = X5-, X5 - =У1

У = Z4 — ХЗ;

Х7 - Z4 + XÇХЗ - "Х4;

Х4 Y.

У1 =ХО+Х1;

У1 = ХΠ— Х1;

У2 = Х2 + XÇ;

ХЗ = Х2 ХЗ;

Р1 =Х1 хСО1;

Р2 = Y2 х СО1;

ХО =Р1+Р2;

Х2=Р1-Р2, Оконечная операция:

10 !

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

В превом такте по адресу AO,ñôîðмированному на выходе 18 блока 15 синхронизации, из блока 1 памяти считывается значение операнда.

Во втором такте по сигналу с выхода 20 блока 15 синхронизации ком- . мутатор 2 подключает выход блока 1 памяти к входу регистра 6 и по сигналу с выхода 21 блока 1) синхронизации в регистр 6 принимается операнд

ХО. Одновременно,по сигналу с выхода

24 блока 15 синхронизации коммутатор

3 подключает выход регистра 6 к входу блока 7 регистров и по сигналу с выхода 31 блока 15 синхронизации в блок

7 регистров принимается операнд ХО по адресу ФО, сформированному на выходе 32 блока 15 синхронизации. Кроме того, по адресу А1, сформированному на выходе 18 блока 15 синхронизации, из блока 1 памяти считывается значение on ер анда Х1, В третьем такте по адресу А2, сформированному на выходе 18 .блока

15 синхронизации, из блока 1 памяти считывается значение операнда Х2.

Одновременно по сигналу с выхода 20 блока 15 синхронизации коммутатор 2 подключает выход блбка 1 памяти к входу регистра 6 и по сигналу с выхода 21 блока 15 синхронизации в регистр 6 принимается операнд Х1. Кроме того, по сигналу с выхода 23 блока

15 синхронизации коммутатор 4 подключает выход регистра 6 к входу блоI ка 8 регистров и по сигналу с выхода 28 блока 15 синхронизации в блок

8 регистров принимается операнд Х1 по адресу ФО, сформированному на выходе 29 блока 15 синхронизации.

В четвертом такте по адресу А3, сформированному на входе 18 блока 15 синхронизации, из блока 1 памяти считывается значение операнда ХЗ. Одно-. временно по сигналу с выхода 20 блокд 15 синхронизации коммутатор 2. подключает выход блока 1 памяти к входу регистра 6 и по сигналу с выхода 21 блока 15 синхронизации в регистр 6 принимается операнд Х2, а по

1425708 сигналу с выхода 24 блока 15 синхронизации коммутатор 3 подключает выход регистра б к входу блока 7 регистров и по сигналу с выхода 31 бло5 ка 15 синхронизации в блок 7 регистров принимается операнд Х2.по адресу Ф1, сформированному на выходе 32 блока 15 синхронизации. Кроме того, по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию сложения над операндами ХО и Х1, считываемыми соответственно иэ блоков 7 и 8 регистров по адресам ФО, сформированым на выходах 33 и 30 блока 15 синхронизации.

В пятом такте по сигналу с выхода 21 блока 15 синхронизации в ре-. гистр 6 принимается операнд К3, по сигналу с выхода 23 блока 15 синхронизации коммутатор 4 подключает выход регистра 6 к входу блока 8 регистров и по сигналу с выхода 28 блока 15 синхронизации в блок 8 регистров принимается операнд ХЗ по адресу

Ф1, сформированнбму на выходе 29 блока 15 синхронизации. Одновременно по сигналу с выхода 38 блока 15 синхронизации арифметический, блок

10 выполняет операцию вычитания над операндами ХО и Х1, считываемыми соответственно из блоков 7 и 8 регистров по адресам ФО,сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенного в четвертом такте сложения с выхода арифметического блока 10, этот же результат по сигналу с выхода 40 блока 15 синхро40 низации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу АО, сформированному на выходе 18 блока 15 синхронизации.

В шестом такте по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию сложения над операндами Х2 и Х3, считываемыми соответственно из блоков регистров .7 и 8 по адресам Ф1, сформированным на выходах 33 и 30 блока 15 синхронизации. Одновременно по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в пятом такте операции вычитания с выхода арифметического блока 10, этот же результат по сигналу с выхода 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 19 блока 15 синхронизации в блок 1 памяти по адресу А1, сформированному на выходе 18 блока 15 синхронизации °

В седьмом такте по сигналу с выхода 38 блока 15 синхронизации арифметический блок 10 выполняет операцию вычитания над операндами Х2 и Х3, считываемыми соответственно из блоков регистров 7 и 8 по адресам Ф1, сформированным на выходах 33 и 30 блока 15 синхронизации, Одновременно по сигналу с выхода 39 блока

15 синхронизации в регистр 12 принимается результат проведенной в шестом такте операции сложения с выхода арифметического блока 10, этот же результат по сигналу с выхрда 40 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода 9 блока 15 синхронизации в блок 1 памяти по адресу А2, сформированному на выходе 18 блока 15. синхронизации.

B восьмом такте по сигналу с выхода 39 блока 15 синхронизации в регистр 12 принимается результат проведенной в седьмом такте операции вычитания с выхода 39 блока 15 синхронизации принимается в регистр 13 и записывается по сигналу с выхода

19 блока 15 синхронизации в блок

1 памяти по адресу А3, сформированному на выходе 18 блока 15 синхронизации.

Аналогичным образом могут быть рассмотрены выполнения второй, третьей базовых операций и оконечной операции. Так, например, при выполнении базовых операций 2 и 3 используются также умножитель 11, блок

14 постоянной памяти, коммутатор 5 и блок 9 регистров.

Вся работа устройства дискретного преобразования Фурье синхронизируется последовательностью тактовых импульсов, поступающих на вход 41 блока синхронизации и .одновременно на счетные входы счетчиков 49 и 50,. триггера 51, один из входов элемента И 54 и вход элемента НЕ 57. Сигналы, необходимые для работы, вырабатываются блоком 15 синхронизации

1425708

1О после поступления на вход 42 сигнала, запуска н виде короткого импульса отрицательной полярности.

Н результате по сигналам с вы5 ходов триггера 51 и элемента И 54 разблокируются счетчики 49 и 50 и на выходах узлов постоянной памяти 52 и 53 появляются соответствующие сигналы управления. 10

Работа завершается и блок 15 синхронизации принимает исходное состояние прк поступлении импульса с выхода узла 52 постоянной памяти на вход триггера 51. При этом сигналами 15 с выходов триггера 51 и элемента И

54 блокируются счетчики 49 и 50.

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

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

2 ° 7cTpoHcTBo IIo II. 1, о T JI H ч а ю щ е е с я тем, что-блок синхронизации содержит дна узла постоянной памяти, дна счетчика, триггер, регистр, три элемента И, дна элемента НЕ, элемент задержки, шесть элементов И-НЕ, информационный выход первого счетчика подключен к

1425708

25 28 (7) И 19

Фиг. 2

N 27 адресному входу первого узла постоянной памяти, с первого по четвертый выходы которого подключены соответственно к первому установочному вхо5 ду триггера, первому входу первого элемента И, к первому и второму разрядам информационного входа регистра, выход которого подключен к адресному входу второго узла постоянной памяти,1О .выходы с первого по седьмой которого подключены к первым входам соответ ственно второго и третьего элементов И, с первого по пятый элементов

И-НК, выход триггера подключен к вхо- 5

\ ду обнуления первого счетчика и первому входу шестого элемента И-НЕ, выход которого подключен к второму установочному входу триггера, тактовый вход которого соединен со счетными 20 входами первого и второго счетчиков, вторым входом первого элемента И, входом первого элемента НЕ и является тактовым входом блока, входом запуска которого является второй вход

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

14 25708 х (б) х 10)

X 2б)

Х б) 6 гх)

x(zo) к(п)

Х 2В)

x2) х хх)

x{az) 6{ 1

6(6j

S(2)

s{r) Редактор M.Áëàíàð

Заказ 4773/49, Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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

К(1)

6Гх) . К(2Я .*Ф к za) к a)

6 {э)

К(27)

61(7)

6{66)

М (Л) . Составитель А.Баранов

Техред M.Дидик Корректор В.Бутяга

2 Г(,72)

2 С(()) с)й

Ю

c(y

С(5)

С(б

C(7

С16

c(e) с(н) сбх б(й