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

И

17

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах обработки сигналов и изображений высокой производительности. Цель изобретения - повышение быстродействия процессора. Он содержит вход 1 задания коэффициентов, информационный вход 2, дополнительный операционный блок 3, систолическую матрицу 5 из /N-1/ операционных блоков 6, группу 7 из блоков коммутации 8, дополнительный операционный блок 11, систолическую матрицу 13 из /N-1/ операционных блоков 14, группу 15 сдвиговых регистров 16 и блок синхронизации 18. 3 ил.

19

20

10

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

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

На фиго 1 представлена функциональная схема систолического процессора для двумерного дискретного преоб- зования Фурье; на фиго 2 - функциональная схема операционного блока; на фиг 3 - функциональная схема блока коммутациио

Процессор содержит (фиг 1) вход 1 задания коэффициентов, информационньй вход 2, дополнительный операционный блок 3, вход 4 задания коэффициентов, группу 5 из (N-l)-ro операционных блоков 6, группу 7 из N блоков 8 коммутации, общий выход 9 группы 7 блоков коммутации, вход 10 задаш я коэф- фициентов,дополнительный операционный блок 11, вход 12 задания коэффициен- 25 тов, группу 13 из (N-l)-ro операционных блоков 14, группу 15 сдвиговых регистров 16, информационный выход 17 процессора, блок 18 синхронизации,тактовые входы 19, 20 и вход 21 запуска, jo

Операционные блоки 6 и 14, а также дополнительные операционные блоки 3 и 11 (фиг с 2) со держат входы 22 к 23 регистр 24, умножитель 25, выходы 26 и 27, сумматор 28, вход 29 и выход 30 о

Блок коммутации (фиг. 3) содержит

20

5

35

регистр 31, демультиплексор 32, элемент 33 задержки, вход 34, выход 35, выход 36, вход 37, в ыход 38

Процессор работает следующим образом

При вьшолнении двумерного ДПФ

40

N

(EN

где X,.rJ, Vk,m 61,N

X,)H

N

(1)

ck.tnl

матрица исходных данных;

CH .

Yk,mer;N - матрица результатов

(Hit - )

J.

%k,mei,N - матрица дискретных

экспоненциальных функций,

„PH4e«« - -exp -i|-(k-1)(n.-0

процессор реализует слеу вычислительных операций:

(k).

.И Н

(E,)

(и - (в

х ,

5 jo

0

х«. 5 .VebS.

В (2) преобразование по первой

координате (Е, для каждого kG1,N выполняется один раз совокупностью блоков, в состав которой входят: до- полнительньш операционный блок 3, группа 5 и группа 7 блоков коммутации, Преобразование по второй координате, представленное в (2) рекуррентно-свд- занными операциями умножения иа W и суммирования, выполняются группой блоков, включающих дополнительный операционньш блок 11, группу 13 и группу 15 сдвиговых регистров

Первая совокупность блоков обеспечивает последовательно-параллельное вычисление компонент одномерного ДПФ 1

в каждый; такт по k-й (k | строке исходных данных по следующему соотношению:., , «

.,(h-n,Ue-0

35

ТТ

k,e,,E,(n-.,(n-noMJ N

40

Yk,le 1,N; 1 n при ksl.

(3)

45

50

,

где k - номер обрабатываемой

строки данных; 1 - номер блока 8 коммутации в

группе 7;

n - текущий такт вычислений, причем hp п : N + 1, DO 1 +(5 1 )N n - начальный такт вычисления

1-й компоненты в К-м цикле; (Ы+п-1)-Такт, при котором заканчиваются вычисления 1-й компоненты в К-м цикле; значение накопленной в регистре 31 1-го блока 8 коммутации суммы на п-м такте вычислений;

то же, на (п-1) такте; X., ;- значение обрабатьшаемого в

1-м операщюнном блоке 6 отсчета исходных данных в п-м ;

k,E,n

.Г

Mtt-tto l)

- значение весового множителя, поступившего на вход 1-го операционного блока 6 в п-й

.

Цп-Пв+1)

тупающего на вход умножителя

значение операнда, пос

с предыдущего операционного

блока 6 в п-й такто Как видно из (3), накопление в п-й такт осуществляется в независи Мз1х 1-х блоках 8 коммутации (k - фик с1ровано), что исключает необходимос и пользования вычислительной схемы Г:)рнера и тем самым обеспечивает бол га/ю точность вычислений за счет разд л гния групп операций умножения и сум- мррованияо

Процессор в п-й такт времени рабо- тлет следующим образом. Текущие k(n-( поступают в каж- д.ш такт на вход дополнительного операционного блока 3 с входа 2„ На другой вход операционного блока 3 с вхо- да 1 поступают на каждом такте весо- вие множители W.(y,j,), позволя- юцие выполнять взвешивание обрабатываемой матрицы X )| по строкам или маешгабировать данные (в этом случае G) (О const) На следующем такте ре- зульта.ты обработки в операционном блоке; 3 х() х(«) 6о() передаются на в:з:од группы 5 и в блок 8 коммутации, Нг второй вход группы 5 с входа 1 весе вых множителей одновременно посту- шют весовые (поворачивающие) множи- телиУ; -( W,- где k - Ib - 1 Г

.IN L

+ 1

При этом на входы операционного блока 3 поступают новые исходные дан- нь|е х() и весовые множители й)(Оо

В следуюпщй такт (п+1), такт в пер ром операцион:ком блоке 6, получается п)оизведение х() W которое по -.кончании такта передается во второй операционный блок 6, куда поступает .и . Одновременно с этой передачей осуществляется прием данных в первый оп(рационный блок 6 из операцион- блока 3 и с входа 4 и прием ноиых данных х() и (0(О в опера- 1ЩОННЫЙ блок 3;,

В такт (п+2) во втором операционной блоке 6 получается произведение () ) Wfj , которое передается одновременно с по окончании этого такта дальше.

10

«

20

2586886

При этом выполняются все пересып ки данных, поворачивающих множителей и текунщх произведений из предыдущих операционных блоков 6 в последующие, и на (п+3) такте в обработку ScC ) и W| включается уже операционный блок 3, с которым одновременно работают все предьщущие блоки (если К 1) и все последующие (если К Ь 2)„

При этом не только загружается группа 5 и вычисляются текущие произведения, но и выполняется сложение (3) текущих произведений с результатами предьщущих суммирований, хранящихся в регистрах 31 1-х блоков 8 коммутации При этом выход 30 каждого операционного блока 6 через вход 34 блока 8 и демультиплексор 32 подключен к регистру 31, выход 35 которого подключен к входу 29 блока 6

Для осуществления операций (3) каждый блок 6 группы 5 реализует следующие функции (фиго 2):

bb.,

(4)

« ,BX

и - данные на входах 22,

23 и 29 соответственно 1-го операционного блока 6;

fiBbi) е,вв1х

и Уе,вых Даииые на выходах 27, 26 и 30 соответственно 1-го операционного блока 6

25

Дополнительный операционный блок О 3 также выполняет функции (4) для случая, когда «().

Начиная с (n+N) такта результат одномерного ДПФ/..

(кМ)(т-0

5

k.8

iTlcl

k,m-W

Vkei,N (5)

0

5

при поступлении от блока 18 управления на вход 19 управляющего сигнала g 1 передается на общий выход 9 группы 7 сначала из первого блока 8 (1 1), затем в (n+N+1) такт из второго блока 8 и ТоДа, а сигнал g 1 передается далее на вход 37 (1+1)-го блока 8; Для вьтолнения этого демуль- типлексоры 32 осуществляют подключение сумматоров 28 к выходу 9 по цепи 30 32 36, при этом соответствующие регистры 31 обнуляются и,/ таким образом, подготавливаются к i

формированию результатов по следующей строке данныхс

При выходе результатов из первого блока 8 к выходу 9 группы 7 подключа- ется выход сумматора 28 дополнительного операционного блока 3 по аналогичной цепи.

Результаты (5) с выхода 9 группы 7 постзшают, начиная с (n+N)-ro так- та работы процессора, на вход дополнительного операционного блока 11, на другой вход которого поступают весовые коэффициенты вида оо (К) с входа 10, позволяющие вьшолнить взвешивание данных по второй координате, или масштабирование промежуточных результатов (в этом случае С0() const), или симметрировать одномерньй спектр путем домножения на фазовый множитель вида:

W (k)

t ) -j-(N-1)(n+k) - при нечетном N

Рчс А Jivjpa 1

I J (n+k) - при четном N

На каждом следующем такте результаты обработки в операционном блоке 11 вида с() С(«)-СО.() поступают в первый регистр 16 группы 15 и на вход группы 13о На другой вход одновременно поступают с входа 12 весовые (поворачивающие) множители вида « и , где k - номер строки коэффициентов i одномерного ДПФ матрицы Х.1. г

При этом группа 13 и группа 15 сдвиговых регистров повторяют описа н - ный выше процесс вычислений с той лищь разницей, что накопление частичных сумм в дополнительном операцион- ном блоке 11 и в операционных блоках 14 осуществляется через каждые N тактов, поскольку каждьй результат суммирования поступает в свой регистр 16 группы 15 сдвиговых регистров и воз- вращается к. сумматору 28 соответствующего операционного блока через N тактово Операционные блоки 14 группы 13 вьшолняют Фзшкции (4) о

В процессоре к началу N-ro такта все операционные блоки 6 группы 5 и дополнительный операционный блок 3 работают параллельно Первый результат С, с выхода 9 группы 7 появится к концу N-ro такта и, начиная с (N+1) такта, в работу вступает дополнитель- ный операционный блок 11 , а с (N+2) такта и группа 13 При этом на ()-м такте работы процессора в дополнн

тельньш операционный блок 3 поступаю весовые множители СО ( ) и отсчеты втрой строки исходных данных х и, таким образом, начинает совмещаться обработка данных по первой координате, которая в дальнейшем выполняется синхронно в обеих матрицахо

Формула изобретения Систолический процессор для двумерного дискретного преобразования Фурье, содержащий первую и вторую группы из N-1 (N - размер преобразования) операционных блоков, группу из N блоков коммутации и блок синхронизации, причем первый и второй выходы i-ro (i 1,N-2) операционного блока j-й (J 1,2) группы подключены соответственно к первому и второму информационным входам (i+.1)-ro операционного блока j-й группы, первые информационные входы первых операционных блоков первой и второй групп являются первым и вторым входами задания коэффициентов процессора, третий выход 1-го (1 1,N-1) операционного блока первой группы подключен к информационному входу (1+1)-го блока ко1/ мутации группы, первый выход которого подключен к третьему информационному входу 1-го операционного блока первой группы, тактовьй вход которого соединен с тактовым входом 1-го операционного блока второй группы, тактовыми входами всех блоков коммутации и подключен к первому выходу блока синхронизации, вто рой выход которого подключен к второму информационному входу первого блока коммутации группы, второй выход 1-го блока коммутации группы подключен к второму, информационному вхо- ДУ (1+.1)-го блока коммутации группы, а вход запуска блока синхронизации является входом запуска процессора, причем операционный блок содержит сумматор, умножитель и регистр, выход которого является первым выходом операционного блока и подключен к первому входу умножителя, выход которого является вторым выходом операционного блока и подключен к первому входу сумматора, выход которого является третьим выходом операционного блока, первым, вторым и третьим информационными входами которого являются соответственно информационный вход регистра, вторые входы умножит шя и сумматора, тактовым входом операционного блока является тактовьш в:|сод регистра, отличающий- я тем, что, с целью повьшения бысФродействия, в него введены группа им N регистров сдвига, первый и вто- Р(

Kit

Ч

Р

|й дополнительные операционные бло- , вторые вьпсоды которых подключены вторым информационным Ьходам пер- BiJK операционных блоков соответственпервой и второй групп, третий вы- хсд 1-го операционного блока подклю- н к информационному входу (1+1)-го гистра сдвига группы, информацион- нь|й выход которого подключен к треть- у информационному входу 1-го опера- щ-онного блока второй, группы и является информационным выходом процессора, третьим и четвертым входами зада- HP я коэффициентов которого являются первые информационные входы соответственно первого и второго дополнитель ньх операционных блоков, третьи выхо дь блоков коммутации группы подклю- чены к второму информационному входу второго дополнительного операционного 6j:oKa, третий выход которого подключен к информационному входу первого регистра сдвига группы, выход которо- ГС подключен к третьему информационному входу второго дополнительного огерационного блока и информационно23

22

I

o

5 0 5 о

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

df

2

27

f

25

26

28

29

30

Фаг. 2

75 J