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

 

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

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

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

РЕСПУБЛИН (51)5 С! 06 F 15/332

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

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

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

ll0 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ МНТ СССР (21) 4492759/24 (22) 10.10.88

<46) l5.02.9I. Вкi. N 6 (71) Специальное ко> структорское бк.р<> вычисл .тельной техники Института кибернетики АН ЭССР (72) И.О.Аррг, Л.Э.Смоля»ский и Т. И. Трумп (53) 681 32,088. 8) (56) Авторское свидетельс тво СССР

11 1254505, кл. G 06 Г 15/332, 1984.

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

В 1425708, кл. 0 06 " 15/332, 1987.

„SU„„!62Я6Б А1

2 (54) УСТРОЙСТВО ДЛЯ 11!ПОЛНЕНИЯ ДИСКРЕТ1!ОГО ПРЕОБРА !ОВА1!11Я ФУРЬЕ (57) Иэг бретение относится к вычис— лительной технике и может бьггь ис»си. - овано в аппаратуре радиоэлектроь» ой и иэмерительной техники. Цель изс бретення — расширение функциональHhlx B0÷ì0æHîñòåA за счет выполнения даунер»ого преобразования Фурье. Поставленная цепь дгстигается за счет того, что в устройство входят блок памяти 1, бпок регистров 2, умножитель 3, арифметический блок 4, блок постоя»ной »амяти 5 и блок управления 6. I з.п.ф-лы, 2 ил.

1628065

О 1 О X(Ii3)

0 1 О 1 Х(Е,Д+ M) ! Π— 1 0 X(I + MJ) о 1 о — x(I -.- м Д+ м) (2) !. X(I,3)

X(I,Д + и)

X(I+М,()

X(T. + М,3+ M) е, Э = о (и-!);

1 1 О О

1 — 1 0 О

О О 1 1

ΠΠ— 1

1 (M;

Е» М, I (Nfg(N;

I > N33(M если если если если (3) К = 1,2 -1; I = (M — М Q/2P) (2M — М Q/2 — 1);

P т = I M Q/Z;,/ = (M(l + 7V)/2",, (M(l + К)/2 — 1); двоично-инверсное значение К.

EA

3. X(I,() = X(I,Д) + Х(Е,.(+ М/2 );

X(I,1) + М/2Р) = X(I, 3 ) .— Х(Е х(д,е) = х(Э,е) + х(Д + м/2,е), Х(Д + M/2P,I) = X(Q,I) — X(3 +

+ М/2 );

I(М;

M/2, I); (4) к= О 2 ; I =M1 2М-1;

Км/2, (М (1 + 2К) /2 — 1 ), 4 Бьгшсление нечетных трансформантных преобразований с периодом 2М дли палусталбдаи с индексами

0,2М-1, причем Е Д, I = М,2M-I, v для полустрок Е = О,м-l, здесь

Q I g = М,211-1.

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

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

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

F C (2B-1) = С н (2В-1)+Сн(2(2В-1) +... +

+С р. (2В-1)+Х (1); (5) Изобретение относится к вычислительной технике и может быть использовано в аппаратуре радиоэлектронной и измерительной техники.

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

Двумерное дискретное преобразование Фурье (ЦДПФ) вещественного исход2. Х(Т, Д ) = -X(I (modN) + М, (), Х(Т, () = X(I (modM) + М, Д ), Х(Э,т) = -Х(д, Ето М) + М), Х((,Т) = Х(Д, I (modM) + M), ного массива X(I,Ý), где I,J

О,N, д 2е, 1б (1,2,... чапредел ляется формулой н-(н- ( та+3 S

F(R,S) -,> X(I,1) W (I) д=о 3=0 ) где W = exp(-2 н j/N) .

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

p = 1, 1оК2М

Гя(2В-1) = ян(2В-1)+S1((R(2B-1)+.. ° +

+S (2R-1)+X(N/4+1); (6) н(4 k где С (2R-l)= Х((2Е-!)К)соэ(2 н х н/а

x(2I-1) (2В-1) /(N/R) ), (7)

H()R (2В-1)=,0 X((2I-1)R)sin(2((х ((/a

x(2I-1) (2В-1) / (1!/8) ) 1 (8)

2О(, (= О, (L-3),B=1, (N/8R) р

Й(2 р 0 (2B- ) = X(I) cos (2 я Е(2В-i)/N;

FS(2В-1) =, 5 X(I) э1п(2 а I(2B-1) /!!) .

1=! (9)

На фиг.! представлена структурная схема предлагаемого устройства, на фиг.2 — структурная схема блока управления °

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

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

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

Устройство для выполнения дискр=7" ного преобразования 7,:урье сь7:7ол>7я> т три типовых операции.

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

Y ХΠ— Хl;

ХО ХО + Хl;

Х1

Типзвая операция 2:

Y2 = Х2 СОО;

Y3 = ХЗ СОО;

Z2 Yl + Y3;

Z3 = Y2-- Y3;

YO = XO-- Z3;

ХО ХО + 23;

Х2 22 — Xl;

ХЗ - 22 + Х1;

Xl YO.

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

YO = Х4 Cl — X5 Sl;

У! = Х4 Sl + X5 С1;

Y2 =- Х6 СЗ вЂ” Х7 83;

Y3 = Хб БЭ + Х7 СЗ;

72 * YO — Y2;

20 YO — Y2Х6 22 + Х2;

Х5 Z2 — Х2;

ЕЗ " Yl + YÇ

Zl m mYl — Y3;

Х7 23 + XÇ;

Х4 ZÇ вЂ” XÇ-, х2 - xl — zl;

Х1 - Х1 + Zd;

ХЗ XO + ZO.

ХО ХО + 20.

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

16 исходных значений, т.е. объединяются 8 типовых операций 1, 4 типовых операций 2 и 2 типовых операций 3, 28065

Эти гр;..>.ь> вы"олняются в в,где с7,ель5

t0

t5

Ю

НЬГС М77КРОПРОГРаММ, .; >næ ТОГО, К.>ЕЮ>ся м77кьопрограммы 77ачальной 0:!rtp ktèè

IkOpE.хода ОТ Однои 1 pV!7!Ibl t 7770!7!ilX 07>е

Ра7777>7 К ДРУГОЙ И 07.0«k.>t!Ible МИКГс ПРОГраммы, Рассмотрим работу ус.трой тва при

IIkttk0rlIIek«tt» типовых опеД. >ц kll, При этом используются следу>вшие Ос:о >н."чени>с:

АБ — арифметический б".ок; У1111 — умножител ° ; ОЗУ вЂ” блок 7>амяти; ПВУ вЂ” бло.< постo>ltrtrr и памяти; Prl — блок рсгнстров; I Y — блок упр; влс>777 >t; У вЂ” знак

rIkkrI0sIkIr .7ИВ СООГВОГС. ВЧЮШЕ77 ОПЕРапии;

И вЂ” с тарш,. > 7асть с во ва; L —; I!In@I!!ая чз; ть сл >;;l, 0,1.2 — 7 ot>pa регистров г р. гис . р.».ом файле 2, . с10 смотр17и вь1по. IHE>! >>!е нач алькой

07.ерс1777777 сс>гл.7сно 77р:..мс иной диаграммс, в перво» такте >О адресу с выхода 7 БУ 6 счптываатсв огп ранд XOl, к>1тс рь>77 3апIIE ываетсв .«рез порт заП" с.:. Vi> 7 бЛОК 2 Пе адрС Су 0 ПО сп> налу 0 выходу Губ.

Во втором т к; с не .1 п>оввчстся пк

Одна пз с.k! L 1>i>lkttlk в силу Осс бенностек времс-.7771ь>х Jr>l:17 p;1,>м используем .х э>>емец гов. трстьс >- г;>хтс 7>о à, lr. су с 7ыхoда j it#6 с п>7ь>ваетев i пера>1д Х1, которь> "t з.>: k>c. п>ается . рез порт зап>. си

WF в блок 2 rro;>дрееу 1 по сигналу с

ыхода 9 БУЬ.

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

В пятом т;,к.. !70 адресу с выхода 7 БУ6 с ситывается операнд Х2, которь>и з > 77ись>пает ся че ре3 1 Орт .> аписи

Ы в блок 2 по адресу 2 по сигналу с выхода 9 БУЬ.

В шестом такте .In сигна,7у с выхода 9 БУ6 считывается через гарт чтения RA блока .". старша; половина операнда Xl с адреса О н через порт чтения RB блока 2 сгаршая половина

Операнда Xll с адреса 1 и подается на входы АБ4. Одн временно с выхо; да 10 БУ6 на ЛБ 4 подаются сигнал пр7keMa операндов и код ort р ции сложения.

В седьмом такте по адресу с вьг>сода " БУ6 считывается операнд Х12, который записывается через порт записи VF в блок ? по адресу 3 по сигналу с выхода 9 БУ6. В то же время по сигналу с выхода 9 Б 6 считывается через чорт чтения RA блока 2 младшая

1628065 полов1гна операнда Хl с адреса 0 и через порт чтения RB блока 2 младшая половина операнда Xll с адреса 1 и подается на входы АБ4. Одновременно с выхода 10 БУ6 на АБ4 подается сигнал

5 приема.

В восьмом такте по сигналу с выхода 9 БУ6 через порт чтения ВА блока 2 считывается старшая половина операнда Xl с адреса 0 и через порт чтения

RB блока 2 старша половина операнда

Xl1 с адреса 1 и подается на входы

ЛБ4, Одновременно с выхода 10 БУ6 на ЛБ4 подаются сигнал приема и код операции вычитания.

В девятом такте по адресу с выхода 7 БУ6 счи-,ывается операнд ХЗ, который записывается через порт записи

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

В десятом такте по сигналу с вы- 30 хода 9 ЬУб через порт чтения RA блока 2 с 1нтывается старшая половина операнда Х2 с адрес:а 2 и через порт чтения 1 В блока 2 старшая половина операнда Х12 с адреса 3 и подаются на входы ЛГ4. Одновременно с выхода 10

БУ6 на АВ4 подаются сигналы приема и код операци1 сложения.

В одиннадцатом такте по адресу с выхода 7 БУ6 считывается операнд

Х13, который записывается через порт записи 1"1 в блок 2 по адресу 5 по сигналу с выхода 9 БУ6. В то же время по сигналу с выхода 9 БУ6 считывается через порт чтения RA блока 2 младшая половина операнда Х2 с адреса 2

45 и через порт чтения PB блока 2 младшая половина операнда Х12 с адреса 3 и подаются на входы ЛБ4. Одновременно с вь;хопа 10 БУ6 на ЛБ4 подается

50 сигнал приема.

В двенадцатом такте по сигналу с выхода 8 БУ6 через порт чтения RA блока 2 считывается старшая полонина

55 операнда Х2 с адреса 2 и через порт

- чтения RB блока 2 старшая половина опеpа11 1а Х12 с адре са 3 и подаются на входы ЛБ4, Одновременно с выхода 10 БУ6 на АБ4 подаются сигнал при-. ема и код операции вычитания.

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

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

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

В шестнадцатом такте по сигналу с выхода 9 БУ6 через порт чтения RA блока 2 считывается старшая половина операнда XÇ с адреса 4 и через порт чтения RB блока 2 старшая половина операнда Х13 с адреса 5 и подаются на входы ЛБ4 ° В то же время с выхода

АБ4 считывается старшая половина результата операции сложения операндов

Х1 и Xll и записывается через порт записи ЫЕ в блок 2 по адресу 16. Одновременно с выхода 10 БУ6 на АБ4 подаются сигналы приема и передачи и код операции вычитания.

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

162806

9 через порт чтения RA блок;. 2 младшая половгп.а опеланда ХЗ с адреса 4 и через порт чтения КВ блока 2 младшая половина операнда Х13 с адреса 5 и подаются на входы АБ4, с выхода ко5 торого считывается младшая половина результата операции сложения операндов Х1 и Хll и записывается через порт записи 1ГР в блок ".. по адресу 16 °

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

В восемнадцатом такте оо сигналу с выхода 9 БУ6 через порт чтения КА блока 2 считывается старшая половина о еранда У4 с здрега 6 и через порт чтения R . блока 2 старшая половина операндя Xl,4 с адреса 7 и подаются

На входь АБ4. B т<. же время с;;ыхода

АБ считывается ст;рпан пггловинз ре- 20 эультата операции вычитания операндов

Xl и Xl! и записывает я,врез порт записи Л з блок 2 по адресу 17. Одновременно с выходз 10 БУ6 на АБ4 лодактся си палы приемы и перед,;чи 25 и код операции сложения.

В девятнадцатом такте по адлесу с выхода 7 БУ6 считывается операнд

Х15, который записывается через порт записи И в блок 2 по адресу 9 по сигналу " выхода 9 БУ6. В то же время по сигналу с выхода 8 Б!Ъ считывается через порт чтения RA блока ? младшая половина операнда Х4 с адреса 6 и через порт чтения RB блока 2 младшая пологина операнда У.14 с адре35 са 7 и подается на входы АБ4, с выхода которого считываетсл младшая половина результата операции ьычитания

oпеРандов Х1 и Xll и зели ывается че- 40 ре3 порт записи NF в блок 2 по а ресу 17, Одновременно с выхода 19 БУ6 на АЪ4 подаются сигналы приема и передачи.

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

Вся работа лредлагае. ого устройства

50 одно- и двумерно-.о дискретного преобразования Фурье синхронизируется последовательностью тактовых импульсов, г|оступаюцих на вход 16 BYC. Запуск устройства осуществляется по импульсному сигналу, гоступающему на

55 вход 17 БУ6.

Тип и размерн.>сть преобразования определяются управляющими словами, 5 10 которые подаются на входы 13-15 БУ6 одновременно с импульсным сигналом, который подается на вход 16 БУ6.

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

K результате этого считывается в регистр 27 следующий адрес для блока 1.

По сигналу с выхода узла 25 увеличиваегся содержимое счетчика 22, выход которого соединен с адресным входом узла 26, и следующий адрес для блока 5 считывается в регистр 29. llo си-.налу с выхода узла 25 совершается работа устройства ° Регистры 27-29 служат для обеспечения синхронизации рабо",ы устройства.

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

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

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

2, Устройство по п.l, о т л и— ч а ю щ е е с я тем, что блок управления содержит четыре счетчика, три регистра, триггер, элемент И-НЕ, и четыре узла постоянной памяти, информационный выход которого подключен к адресному входу первого узла постоянной памяти, выход которого подключен к информационному входу первого регистра, выход которого является пер вым адресным выходом блока, вторым адресным выходом которого является

8065 l2

Ю

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

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

1628065

4302. 2

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

Техред Л.Олийнык Корректор Т. Малец т

Реда. кто р Л . Лежнин а

Заказ 342 Тираж 403 Подпи ное

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

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

Производственно-издательский комбинат "Патент", г. ужгород, ул. Гагарина, 101