Устройство для выполнения дискретного преобразования Фурье Советский патент 1991 года по МПК G06F15/332 

05

О

о &

ел

Изобретение относится к вычислительной технике; и може.т быть ис- пол човано в аппаратуре радиоэлектронной и измерительной техники. Цель изобретения - расширение функциональных возможностей за счет выполнения двумерного преобразования Фурье. Поставленная цепь достигается за счет того, что в устройство входят блок памяти 1, бпок регистров 2, умножитель 3, арифметический блок 4, блок постоянной памяти 5 и блок управления 6. I з.п.ф-лы, 2 нл.

13 № 15 16 17

Фиг.1

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

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

Двумерное дискретное преобразова- |Q ние Фурье (ДДПФ) вещественного исход

О (М-1);

Х(Т, 3 ) X(I(modM) + М,J ),еслиI М;

Хр.Т) -Х(3 .imoJM) + М),еслиI

Х(3,Т) X(3,I(modM) н М),если1 М&;)М

К 1,2р-1; I (М - M-Q/2P); (2М - M-Q/2P- 1); Т

1 + M-Q/2P

0 (М(1 + 2K)/2P+V, (M(1 + К)/2Р- I); - двоично-инверсное значение К.

1П

Х(1,3) + М/2р) Х(1,3 ) - Х(1 ,3 + М/2Г);

Х(Э,1) Х(3,П + X(J + М/2Р,1), КМ;(А)

Х(3 + М/2Р,1) Х(3,1) - Х(3 + М/2Р,1);

К 0, 2м; I М, 2М-1;

. 3 КМ/2Р, (М(1 + 2Ю/2Р 1- 1), Р 1, log2M . 1, Вычисление нечетных трансфер-FS(2B-1) SN(2B-1 )(2B-l) + . . .+

0

45

мантных преобразований с периодом 2М для полустолбцов с индексами Д - 0,2М-1, причем V 3 , I М,2М-1, и для полустрок I О,М-1, здесь VI, Э - М.2М-1.

Во всех формулах М N/2 , L

1, log2 NТак как по формуле (3) производится только перестановка данных и перемена знака некоторых из них в практической реализации действия по формулам (3) и (4) целесообразно объеди- нить, тогда они, как и действия по формуле (2), представляют собой сумма- разностные преобразования.

Нечетное трансформантное преобразо+S.(2B-1)+X(N/4+l);(6)

3N/4H

где CN/R (2B-I) X((2l-)R)cos( x

х(21-1)(2В-1)У(И/Ю), (7)

K/4R

SM/R (2B-1)- SlX((2I-l)R)sin(2iix

x(2I-l)(2B-U/(N/R));(8)

R 2(У, 0( 0, (L-3),, (N/8R);

N/2 FC(2B-1) 2lX(I)cos(2 I 2B-П/N-F 1

U/N,M/4

FS(2B-1) X(I)sin(2ff I(2B-D/N). 1Г(

На фиг.1 представлена структурная

Нечетное трансформантное преобразо- схЈма предлагаемого устройства на ванне с периодом N вычисляется следую- - структурная схема блока управ щим образом:пения

FC (2B-1) CN(2B-1)+CN/2(2B-I)...+

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

+C8(2B-I)+X(1);

(5)

ного массива Х(1,3), где 1,3

- O.N-I, N - 2е, 16 {|,2,... }определяется формулой

м-( м-1

F(R,S)

о где W exp.(-2/it j/N).

x(i,3)-w

I-RO-S

,(D

Для вычисления ДДПФ используется сокращенный алгоритм, состоящий из четырех частей:

(2)

(3)

+S.(2B-1)+X(N/4+l);(6)

3N/4H

где CN/R (2B-I) X((2l-)R)cos( x

х(21-1)(2В-1)У(И/Ю), (7)

K/4R

SM/R (2B-1)- SlX((2I-l)R)sin(2iix

x(2I-l)(2B-U/(N/R));(8)

R 2(У, 0( 0, (L-3),, (N/8R);

N/2 FC(2B-1) 2lX(I)cos(2 I 2B-П/N-F 1

U/N,M/4

FS(2B-1) X(I)sin(2ff I(2BУстройство для выполнения дискретного преобразования Фурье содержит

(фиг.1) блок 1 памяти (дл.. хранении входных данных, промежуточных результатов вычислений и результатов преобразования), шестипортовый блок 2 регистров (регистровый файл; (с 32 регистрами), умножитель 3, арифметический блок (АБ) 4, блок 5 постоянной памяти (для хранения коэффициентов преобразования), блик 6 управления, адресные выходы и выходы синхронизации блока управления 7-12, входы 13- 17 блока управления и информационный вход/выход 18 устройства.

Блоч 6 управления содержит (фиг.2) четыре загружаемых счетчика 19-22, четыре узла 23-26 постоямний памяти, три регистра 27-29, тригггр 30 элемент И-НЕ 31.

Устройство для выполнения дискг т ного преобразования -урье п ;:юлня т три типовых операции.

Типовая операция 1:

Y XO - XI;

XO XO + XI;

XI Y.

Типовая операция

У2 X2-COO;

овая операция 3: X4-CI - X5-S); X4-S) + X5-CI; - Х6-СЗ - X7-R3;

YO - Y2;

YO - Y2;

Z2

Z2

Y1

Y1

Z3

Z3

XI

XI

ХО

ХО

+ Х2;

-Х2; + Y3;

-Y3; + ХЗ;

-ХЗ;

-21; + Zd; + ZO. + ZO.

Для обеспечения поточной обработки типовые операции группируются так, чтобы в каждой группе использовались 16 исходных значений, т.е. объединяются 8 типовых операций 1, 4 типовых операций 2 и 2 типовых операций 3.

0

,

0

5

0

5

0

5

0

5

Эти rpj .кы вы -олняютс .j киде с-ь.ель- ных микропрограмм, кpovr того, имеются микропрограммы мочальной операции перехода от одной i рупмы типочых oi;r- рацич к другой и окоаеччые микпопрог- раммы.

Рассмотрим работу устройства при выполнении типовых .ш. При этом используются следующие oiо н ченин: АБ - арифметический УМН - умножитель; ОЗУ - блок памяти; ПЗУ - блс. постоянней памяти; РФ - блок регистров; - блок упранленгя; У - знак BiinojiiK чия соответствующей операции; М - старш. я часть rr ona; L - младшая чз. ть ciioi.a; 0,1.2 - номера регистров я регистровом файл 2.

Г ассмо рпм выпо.чнсчяо начальной операции гоглтсно рр:мг нной диаграм- t.

ь первом такте о адресу с выхода 7 БУ 6 СЧИТЫЯТРТСЯ операнд Х01, который записывается чорез порт за- г ч.. W ь 6jioK 2 пг адресу 0 по сшналу с выходу ЕУ6.

iio втором т-1::, с не пмпопьчется нк одна из спер.чпии я силу особенностей рремс-нных дн 1грлмм используем; ;х элс- менгол.

: - третье к гак re nn с РЫУ.О- дл / гипынаечгя пперпнд XI, ко- Topt .i a.iiinc .шается ч--рея порт записи WF n блок 2 по адресу 1 по сигналу с ььжода 9 БУ6.

В четвертом - пето не выполняется ни одна из операций.

В пятом T;JK-Ј по адресу с ьыхо- да 7 БУ6 считывается операнд Х2, кото pbui -зиписыг с1ется через 1;орт аписи WF в блок 2 по пдресу 2 по сигналу с выхода 9 БУ6.

В шестом такте ло сигналу с выхода 9 БУ6 считывается чиро.з порт чтения RA блока старшая половина операнда XI с адреса 0 и через порт чтения RB блока 2 старшая половина операнда XII с адреса 1 и подается на входы АБ4. Одновременно с выхо,- да 10 БУ6 на АБ 4 подаются сигнал приема операндов и код сложения.

В седьмом такте по адресу с РЫХО- да 7 БУ6 считырается операнд XI2, который записывается через порт записи WF в блок 2 по адресу 3 по сигналу с выхода 9 БУ6. В то же время по сигналу с выхода 9 БУ6 считывается через порт чтения RA блока 2 младшая

половина операнда XI с адреса 0 и чсз- рез порт чтения RB блока 2 младшая половина операнда XI1 с адреса 1 и

подается на входы АБА. Одновременно с выхода 10 БУ6 на АБА подается сигнал приема.

В восьмом такте по слгналу с выхода 9 БУ6 через порт чтения RA блока 2 считывается старшая половина операнда XI с адреса 0 и через порт чтения RR блока 2 старшая половина операнда XI1 с адреса 1 и подается на входы АБА, Одновременно с выхода 10 БУ6 на АБА подаются сигнал приема и код операции вычитания.

В девятом такте по адресу с выхода 7 БУ6 считывается операнд ХЗ, который записывается через порт записи WF в блок 2 по адресу 4 по сигналу с выхода 9 БУб. В то же время по сигналу с выхода 9 БУ6 считывается через порт чтения RA блока 2 младшая половина операнда XI с адреса 0 и через порт чтения RB блока 2 младшая поло- вина операнда XII с адреса 1 и подаются на входы АБА. Одновременно с выхода 10 БУб на АБА подается сигнал приема.

В десятом такте по сигналу с вы- хода 9 БУ6 через порт чтения RA блока 2 считывается старшая половина операнда Х2 с адреса 2 и через порт чтения КБ блока 2 старшая половина операнда XI2 с адреса 3 и подаются на входы АБА. Одновременно с выхода 10 БУ6 на АБА подаются сигналы приема и код операции сложения.

В одиннадцатом такте по адресу с выхода 7 БУб считывается операнд XI3, который записывается через порт записи VF в блок 2 по адресу 5 по сигналу с выхода 9 БУб. В то же время по сигналу с выхода 9 БУб считывается через порт чтения RA блока 2 младшая половина операнда Х2 с адреса 2 и через порт чтения RB блока 2 младшая половина операнда XI2 с адреса 3 и подаются на входы АБА. Одновременно с ьчхода 10 БУб на АБА подается сигнал приема.

В двенадцатом такте по сигналу с выхода 8 БУб через порт чтения RA блока 2 считывается старшая половина операнда Х2 с адреса 2 и через порт чтения RB блока 2 старшая половина операнда XI2 с адреса 3 и подаются1 на входы АБА. Одновременно с выхо

0

5

0

5

-jg 5

10

5

0

да 10 БУб на АБА подаются сигнал при-, ема и код операции вычитания.

В тринадцатом такте по адресу с выхода 7 БУб считывается операнд ХА, который записывается через порт записи WF в блок 2 по адресу 6 по сигналу с выхода 9 БУб. В то же время-по сигналу с выхода 8 БУб считывается через порт чтения RA блока 2 млаД- шая половина операнда Х2 с адреса 2 и через порт чтения RB блока 2 младшая половина операнда XI2 с адреса 3 и подаются на входы АБА. Одновременно с выхода 10 БУб на АБА подается сигнал приема.

В четырнадцатом такте по сигналу с выхода 9 БУб через порт чтения RA блока 2 считывается старшая половина операнда ХЗ с адреса А и через порт чтения RB блока 2 старшая половина операнда XI3 с адреса 5 и подаются на входы АБА. Одновременно с выхода 10 БУб на АБА подаются сигнал приема и передачи и код операции сложения .

В пятнадцатом такте по адресу с выхода 7 БУб считывается операнд XIА, который записывается через порт записи WF в блок 2 по адресу 7 по сигналу с выхода 9 БУб. В то же время по сигналу с выхода 9 БУб счктывается- через порт чтения RA блока 2 младшая половина операнда ХЗ с адреса А и через порт чтения RB блока 2 младшая половина операнда XI3 с адреса 5 и подаются на входы АБА. Одновременно с выхода 10 БУб на АБА подаются сигналы приема и передачи.

В шестнадцатом такте по сигналу с выхода 9 БУб через порт чтения RA блока 2 считывается старшая половина операнда ХЗ с адреса А и через порт чтения RB блока 2 старшая половина операнда XI3 с адреса 5 и подаются на входы АБА. В то же время с выхода АБА считывается старшая половина результата операции сложения операндов XI и XI1 и записывается через порт записи WF в блок 2 по адресу 16. Одновременно с выхода 10 БУб на АБА подаются сигналы приема и передачи и код операции вычитания.

В семнадцатом такте по адресу с выхода 7 БУб считывается операнд Х5, который записывается через порт запи- ,си WF в блок 2 по адресу 8, по сигналу с выхода 9 БУб. В то же время по сигналу с вьгхода 9 БУб считывается

через порт чтения RA блок:. 2 младшая полевика опе.панда ХЗ с адреса 4 и через порт чтения RB блока 2 младшая половина операнда XI3 с адреса 5 и подг уугсп на входы АБА, с выхода которого считывается младшая половина результата операции сложения операндов XI и XII и записывается через порт записи VF в блок по адресу 16. Одновременно с выхода 10 БУ6 на АБ4 подаются сигналы приема и передачи.

В восемнадцатом такте по сигналу с выхода 9 через порт чтения RA блока 2 считывается старшая половинч .черанда УЛ с адреса б и через порт чтения RA Слога 2 старшая половина операнд л XI/} с адреса 7 и подаются на входы АБА. Б то же время с ьяхода АБА считывается половика ре- эультата операции вычитания операндов XI п XI и записывается через порт записи WF в блок 2 по адресу 17. Одновременно с выхода 10 6 на АБА подаются сигналы приема и п«рец.чи и код операции сложения.

В девятнадцатом такте по arn°ecv с выхода 7 БУ6 считывается шеранд Х15, который записывается порч записи WF в блок 2 по адресу 9 по сигналу с выхода 9 БУ6. В то же время по сигналу с выхода 8 БУС считывается череп аорт чтения RA блока 2 младшая половина операнда ХА с адреса 6 и через попт чтения RB блока 2 младшая пологина операнда У. 1А с адреса 7 и подается на входы АБА, г выхода которого считывается младшая половина результата операции вычитания операндов XI и XII и записывается че-

tm ,-

рез порт записи WF в блок / по ачре- су 17. Одновременно с выхода 19 на АБА подаются сигналы приема и передачи.

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

Вся робота предлагаемого устройств одно- и двумерного дискретного преобразования Фурье синхронизируется последовательностью тактовых импульсов, поступающих на вход 16 БУ6. Запуск устройства осуществляется по импульсному сигналу, поступающему на

вход 17 БУ6.

Тип и размерность преобразования определяются управляющими словами,

5

о „

5

5

0

5

которые подаются на входы БУ6 одновременно с импульсным сигналим, который подается на вход 16 БУ6.

Узел 25 содержит микропрограммы. Каждая команда микропрограммы состоит из команды чтения/записи для блока, управляющих слов для блока 2, блока 4 и умножителя 3 соответственно , сигнала окончания данной микропрограммы, сигнала запроса адреса для блока и сигнала окончания работы устройства. Узел 25 адресуется при помоги счетчика 21, на вход которого подаются тактовые импульсы. По окончании данной микропрограммы по сигналу с выхода узла 25 увеличивается содержимое счетчики 20, выход которого является адресом для узла 24. В результате с узла 24 считывается адрес следующей микропрограммы через регистр 28 в загружаемый счетчик 21. По сигналу с выхода узла 25 увеличивается содержимое счетчика 19, выход которого является адресом для узла 23. t результате этого считывается в регистр 27 следующий адрес для блока 1. По сигналу с выхода узла 25 увеличивается содержимое счетчика 22, выход которого соединен с адресным входом узла 26, и следующий адрес для блока 5 считывается в регистр 29. По сигналу с выхода узла 25 совериается работа устройства. Регистры 27-29 служат для обеспечения синхронизации работы устройства.

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

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

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

5

0

5

0

5

Фиг.2