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

 

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

СОЮЗ СОВЕтСНИХ социАлистичесних

РЕСПУБЛИК (19) щ)5 G 06 F 15/332

OC

ПОИ

ПРИ

КАВ

4602180/24-24

05.11 88

3.11.90. Б)0л. № 43 енинградский институт точной ки и оптики .А. Кухарев и А.Ю. Тропченко

81.32 (088.8) ен Дж. Архитектура вычисли)х устройств для цифровой обрасигналов ТИИЭР. 1985, № 5. орское свидетельство СССР

243, кл. G 06 F 15/332.

СТОЛИЧЕСКИЙ ПРОЦЕССОР ДЛЯ ДВУО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ (21) (22) (46) (71) меха (72) (53) (56) тель ботки

Ав № 136 (54)

МЕРН0

ФУРЬЕ (57) APCTBEHHblA КОМИТЕТ

БРетениям и отнРытиям

НТ СССР

ТОРСНОМУ СВИДЕТЕЛЬСТВУ зобретение относится к вычисли2 тельной технике и может быть использовано в специализированных системах обработки сигналов и изображений высокой производительности. Цель изобретения — повышение быстродействия процессора. Он содержит вход T задания коэффициентов, информационный вход 2, дополнительный операционный блох 3, систолическую матрицу 5 иэ (N-!) операционных блоков 6, группу

7 из блоков коммутации 8, дополни- ° тельный операционный блок 11э систоли лическую матрицу 13 из (N-1) операционных блоков 14, группу 15 сдвиговых регистров 16 и блок синхронизации 18.

3 ил.

1608688 (2) (3) где k

СН - (Eи ХН).ЕМ и причем Ь п о

45 (N+n -1)—

50

kg, (n- ) k

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

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

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

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

26 и 27, сумматор 28, вход 29 и выход 30.

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

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

При выполнении двумерного ДПФ где Х = х, Д, f К;ш 61,N — матрица исходных данных р

ЕН"t „„=W„, 3, fk,m 6 1,N — матрица дискретных экспоненциальных функций, М(-«) - .ь

Мрмчем W = ехр(-j „(k-1) (т-1)7, процессор реализует следующую Группу вычислительных операций: (,) И

Р) н (., (k) .

С = (W> (Е,„Х ) ) е (н и (Р- ) (к). (a)

-, (w„° . ° (w„(E x ).)...) () г

Х ) х х еееo х) );» G (с с еее

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

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

- п-1 Г в каждый такт по k-й (k = +1). и строке исходных данных по следующему соотношению: л л (-, )(е-)

С =c +х W

kg, М,<.-1 Ц Yl,+<) N fk1Е 1N; 1 (и при k=1, номер обрабатываемой строки данных, номер блока 8 коммутации в группе 7; текущий такт вычислений, .п <- N+ по- 1, и„= 1+(k — 1)N начальный такт вычисления

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

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

1608688 и

Г д в

30 п1 но но (х од

ro (и „ такте, WN — значение весового множителя, поступившего на вход 1-ro операционного блока 6 в и-й такт; (-ч (г- ).

k(ll-n,+1)

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

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

Процессор в п-й такт времени рабо- 20 т ет следующим образом. Текущие данн 1е х „,)g) х(° ) поступают в каж1й такт на вход дополнительного опер ционного блока 3 с входа 2. На друг и вход операционного блока 3 с вхо- 25

1 поступают на каждом такте весо1е множители W („, Ik,)q ц(о), позволяю е выполнять взвешивание обрабать в емой матрицы Х по строкам или масш абировать данные (в этом случае

Q (° ) = const) . На следующем такте рез льтаты обработки в операционном блок 3 х(° ) = х(° ) ° 63() передаются на в од группы 5 и в блок 8 коммутации.

Н второй вход группы 5 с входа 1 вес вых множителей одновременно посту35 п т весовые (поворачивающие) множит ли Ы1 (ll-(К-<)й-l I (1

= W где k

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

В следующий такт (n+1), такт в пер-. операционном блоке 6, получается оизведение х(° ) W<, которое по ()

45 ончании такта передается во второй о ерационный блок 6, куда поступает и „, Одновременно с этой передачей

H ос ествляется прием данных в первый оп рационный блок 6 из операционо блока 3 и с входа 4 и прием но ых данных х() и Q (° ) в операци нный блок 3.

В такт (и+2) во втором операционблоке 6 получается произведение

-) ° И ) М, которое передается () (1 овременно с Ф по окончании этой такта дальше.

1 !

При этом выполняются все пересылки данных, поворачивающих множителей и текших произведений из предыдущих операционных блоков 6 в последующие, и на (n+3) такте в обработку х() и (° 1

WN включается уже операционный блок

3, с которым одновременно работают все предыдущие блоки (если К = 1) и все последующие (если К 2).

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

34 блока 8 и демультиплексор 32 подключен к регистру 31, выход 35 которого подключен к входу 29 блока 6.

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

"еь х

l где W< х (4) и у .„— данные на входах 22, 23 и 29 соответственно

1-го операционного блока 6;

М х е, BDIX,BDI3 и у „- данные на выходах 27, 26 и 30 соответственно

1-го операционного блока 6.

Дополнительный операционный блок

3 также выполняет функции (4) для случая, когда Wp,sy =Я () °

Начиная с (и+И) такта результат одномерного ДПФ:, (К-1) (1П-l)

С О = x W„, Vk 61,N (5)

Ф 1 при поступлении от блока 18 управления на вход 19 управляющего сигнала

g = 1 передается на общий выход 9 группы 7 сначала из первого блока 8 (1 = 1), затем в (и+И+1) такт из второго блока 8 и т.д., а сигнал g "1" передается далее на вход 37 (1+1)-ro блока 8. Для выполнения этого демультиплексоры 32 осуществляют подключение сумматоров 28 к выходу 9 по цепи

30 34 - 32 -36, при этом соответствующие регистры 31 обнуляются и,г таким образом, подготавливаются к

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

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

Результаты (5) с выхода 9 группы

7 поступают, начиная с (n+N)-го такта работы процессора, на вход дополнительного операционного блока 11, на другой вход которого поступают весовые коэффициенты вида Я (К) с входа

10, позволяющие выполнить взвешивание 15 данных по второй координате, или масштабирование промежуточных результатов (в этом случае Я () = const), или симметрировать одномерный спектр путем домножения на фазовый множитель 20 вида: .2и ехр -j — (N-1) (n+k) — при неN четном N

exp (jи (x+k) — при четном N 25

На каждом следующем такте результаты обработки в операционном блоке

1 1 вида c () = С (е ) Я (е) поступают в первый регистр 16 группы 15 и на вход группы 13. На другой вход одновременно пост упают с входа 12 весовые (поворачивающие) множители вида 1 где k — - номер строки коэффициентов одномерного ДПФ матрицы Х .. .

При этом группа 13 и группа 15 сдвиговых регистров повторяют описайный выше процесс вычислений с той лишь разницей, что накопление частичных сумм в дополнительном операцион- 40 ном блоке 11 и в операционных блоках

14 осуществляется через каждые N тактов, поскольку каждый результат суммирования поступает в свой регистр 16 группы 15 сдвиговых регистров и воз- 45 вращается к сумматору 28 соответствующего операционного блока через N тактов. Операционные блоки 14 группы

13 выполняют функции (4).

В процессоре к началу N-ro такта все операционные блоки 6 группы 5 и

50 дополнительный операционный блок 3 работают параллельно. Первый результат С с выхода 9 группы 7 появится к концу N-ro такта и, начиная с (N+1) такта, в работу вступает дополнитель55 ный операционный блок 11, а с (N+2) такта и группа 13. При этом на (И+1)-м такте работы процессора в дополнительный операционный блок 3 поступают весовые множители Q () и отсчеты вто.— рой строки исходных данных х« и, таким образом, начинает совмещаться обработка данных по первой координате, которая в дальнейшем выполняется синхронно в обеих матрицах.

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

Систолический процессор для двумерного дискретного преобразования

Фурье, содержащий первую и вторую группы из N-1 (N — размер преобразования) операционных блоков, группу из N блоков коммутации и блок синхронизации, причем первый и второй выходы i-ro (i = 1,N-2) операционного блока j-й (j = 1,2) группы подключены соответственно к первому и второму информационным входам (i+1)-ro операционного блока j-й группы, первые информационные входы первых операционных блоков первой и второй групп являются первым и вторым входами задания коэффициентов процессора, третий выход 1-ro (1 = 1,N-1) операционного блока первой группы подключен к информационному входу (1+1)-ro блока коммутации группы, первый выход которого подключен к третьему информационному входу 1-го операционного блока первой группы, тактовый вход которого соединен с тактовым входом 1-го операционного блока второй группы, тактовыми входами всех блоков коммутации и подключен к первому выходу блока синхронизации, второй выход которого подключен к второму информационному входу первого блока коммутации группы, второй выход 1-го блока коммутации группы подключен к второму. информационному входу (1+1)-ro блока коммутации группы, а вход запуска блока синхронизации является входом запуска процессора, причем операционный блок содержит сумматор, умножитель и регистр, выход которого является первым выходом операционного блока и подключен к первому входу умножителя, выход которого является вторым выходом операционного блока и подключен к первому входу сумматора, выход которого является третьим выходом операционного блока, первым, вторым и третьим информационными входами которого являются соответственно информационный вход регистра, вторые входы умножи1608688 о к н

P н ег нь дЬ ч в б

r н о

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

5 родействия, в него введены группа

N регистров сдвига, первый и втой дополнительные операционные бловторые выходы которых подключены вторым информационным входам перrx операционных блоков соответственпервой и второй групп, третий выд 1-ro операционного блока подклюн к информационному входу (1+1)-ro гистра сдвига группы, информационвыход которого подключен к третьу информационному входу 1-го операонного блока второй. группы и являся информационным выходом процессотретьим и четвертым входами задая коэффициентов которого являются рвые информационные входы соответвенно первого и второго дополнительоперационных блоков, третьи выхо-блоков коммутации группы подклю- 25 ны к второму информационному входу срого дополнительного операционного ока, третий выход которого подклюн к информационному входу первого гистра сдвига группы, выход которо- ЗО подключен к третьему информационму входу второго дополнительного ерационного блока и информационному выходу процессора, информационным входом которого является второй ин- формационный вход первого дополнительного операционного блока, третий выход которого подключен к первому информационному входу первого блока коммутации группы, второй выход которого подключен к третьему информационному входу первого дополнительного операционного блока, тактовый вход которого соединен с тактовым входом второго дополнительного операционного блока, тактовыми входами регистров сдвига группы и подключен к первому тактовому выходу блока управления, причем блок коммутации содержит элемент задержки, демультиплексор и регистр, выход которого подключен к информационному входу демультиплексора, первый выход которого является первым выходом блока коммутации, первым и вторым информационными входами которого являются соответственно информационный вход регистра и вход элемента задержки, выход которого является вторым выходом блока ком" мутации и подключен к управляющему входу демультиплексора, второй выход которого является третьим выходом блока коммутации, тактовым входом которого является тактовый вход регистра.

1608688

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

Техред А.Кравчук Корректор р. Кравцова

Редактор Н. Тупица

Заказ 3619 Тираж 567 . Подписное

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

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

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