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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных системах многоканальной обработки сигналов и в измерительно-вычислительных системах. Цель изобретения - расширение области применения за счет многоканальной обработки данных. Поставленная цель достигается за счет того, что в состав устройства входят коммутатор 1, операционный блок 2, блок постоянной памяти 3, группа 4 из К-1 /К- размер преобразования/ операционных блоков 5, блок постоянной памяти 6, группа 7 из К блоков хранения 8, коммутатор 10 и блок управления 11. 6 ил.

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

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

РЕСПУБЛИИ

„„SU„„1615741

А1 щ)5 .G 06 F 15/332

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

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

Фиг.7

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1, (21 ) 4643347/24-24 (22) 27. 01. 89 (46) 23.12.90. Бюл. М 47 (71) Ленинградский институт точной механики и оптики (72) Г. А. Кухарев и А. Ю. Тропченко (53) 681.32(088.8) (56) Системы"параллельной обработки.

M.: Мир, 1985.

Kung Н. T. Systolic algoritms. for

CNU WARP Processor.. II Int, Conf;

Pattern Recogn. — Montreal, July 30-„ August/2, 1984, р.р. 570-575. (54) СИСТОЛИЧЕСКИЙ ПРОЦЕССОР, ДИСКРЕТ- НОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

2 (57) Изобретение относится к вычисли тельной технике:и может быть исполь-

I зовано в специализированных система с многоканальной обработки сигналов.и в измерительно-вычислительных системах. Цель изобретения — расширение об ласти применения за счет многоканальной обработки данных. Поставленная цель достигается за счет того, что в состав устройства входят коммутатор 1, операционный блок 2 блок 3 постоянной памяти, группа 4 из К-1 (К вЂ” раз-. мер преобразования) операционных блоков 5, блок 6 постоянной памяти, группа 7 из К блоков 8 хранения, коммутатор 10 и блок 11 управления. 6 ил.

1615741

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

Цель изобретения — расширение области применения за счет многоканальной обработки данных.

На фиг. 1 представлена функциональная схема (многоканального) систолического ДПФ-процессора; на фиг. 2— функциональная схема операционного блока; на фиг. 3 — функциональная схема блока хранения; на фиг. 4функциональная схема коммутатора бло-! ка хранения :на фиг, 5 - функциональЭ ная схема блока управления; на фиг. 6функциональная схема второго дешифра-. 20 тора состояний счетчика.

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

7 из N блоков 8 хранения, выход 9 группы 7, (выходной М-канальный) ком, мутатор 10, блок 11 управления, тактоI вый выход 12 блока управления, первый 13 и второй 14 управляющие выходы блока управления, адресный выход

15 блока управления и тактовый вход 16.

Операционный блок процессора (фиг. 2) содержит первый 17, второй, . 18 и третий 19 входы, регистр (весовых коэффициентов) 20, тактовый вход

21, умножитель 22, сумматор 23, пер40 вый 24, второй 25 и третий 26 выходы.

Каждый блок 8 хранения (фиг. 3) содержит входы 27 и 28, коммутатор

29, тактовый вход 30, вход 31, элемент 32 задержки, выход 33, узлы 34

45 и 35 регистров из (М-1) v i M регистров

36 соответственно и выходы 37 и 38.

Коммутатор 29 (фиг. 4) содержит первый 39 и второй 40 вход данных, вход 41, управляющий вход 42, элементы И 43 - 45, элемент ИЛИ 46, пер вый 47 и второй 48 выходы.

Блок 11 управления (фиг. 5) содержит генератор 49 тактовых импульсов

log NM-разрядный двоичный счетчик

50, первый дешифратор 51 состояний счетчика и второй дешифратор 52.

Второй дешифратор 52 блока управления (фиг. 6) содержит log, (N-1)И-й элемент ИЛИ 53, 1оя N-входной элемент ИЛИ 54, элемент НЕ 55, элемент И 56, выходы 57 и 58.

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

Блок 3 взвешивающих множителей емкостью слов имеет страничную организацию из N страниц по M слов. В каждой странице блока 3 записаны взвешиваюшие множители для отсчетов данных с номера х;„, где i Е 1, М, а Кпорядковый йомер страницы. Для обращения к блоку 3 по адресному выходу

15 блока 11 передается (log N +

+ 1о@ М)-разрядный адрес.

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

Log, М разрядов адресного выхода !6 блока 12 к адресному входу данного блока.

Перед началом работы процессора счетчик 50 обнулен и тем самым на управляющих входах 41 и 42 коммутаторов 29 всех блоков 8 поступают управляющие:сигналы, обнуляющие все peL гистры 36 всех секций 34 и 35 памяти: типа FIF0.

Пусть И входных параллельных пото" ков данных формируются так, что в те-. чение очередных М тактов времени на вход процессора поступает по одному отсчету данных в каждый такт, при этом последовательно поступают M отсчетов данных х от каждого из М каб налов - источников данных (Vi Ю 1, M) где n g О, М- 1, номер отсчета данных,N — длина входной:.последовательности (число отсчетов). данных, à i — номер канала данных.

Отсчеты данных х, (Qi:6 1, М; К Е

6 1 М} поступают на входы входного

M-канального коммутатора 1, управляющий вход которого соединен с выходом первого дешифратора 51 состояний счетчика 50. В результате на 1-м такте ра ,боты О = i k i 61, Мр К 11, М) Кй отсчет данных от i-го канала переда-. ется с входа коммутатора 1 на его выход и далее на первый вход операци-: онного .блока 2.

На второй вход блока 2 поступают с выхода блока 3 взвешивающих множи- ) телей отсчеты весовой функции "окна"

1615?

k -<

ЬЫХ ЬХ И

30 хмЫВХ = -X i k - Я < :

k-< k-1

)" М " )" << 8ЫХ

К-1

2Щ

1 раз (3) с тем же темпом и синхронно с отсчетами данных х;

Блок 2 реалйзует операции вида

К-< при этом текущая сумма вида x; „х

l<

I <Ъ< в первом блоке 8 группы 7. Значение х Х передается далее на первый вход

s«

К 61, N от блока 6 весовых коэффипн- 20 к-< ентов. Отсчеты M поступают на вход систолическои матрицы 4 с тем же темпом и синхронно с отсчетами х

В блоке 5 систолической матрицы 4 с номером 1 (161, N-1) и связанным с ним блоком 8 с номером (1+1) реализуются функции

М вв в "ввв вх + в ((x;в, Q, х<<<= <

<<< "< <<<-< < <<- < . хЯ„)v Ä ...)ы „

40 (2)

Текущее значение суммы в выражейии (2) накапливается в блоке 8 с номером

1+1. Тем самым блок 2 блок 5 систоУ

45 лической матрицы 4 и связанные с ними блоки 8 группы 7 реализуют в совокупности вычисление одномерного ДПФ с предварительным взвешиванием отсчетов исходных данных по выражению

Данное выражение вычисляется в

55 процессоре за 2(N-1)И тактов. При этом в течение первых 1(М-1)М+1-ij тактов во второй секции 35 узла реги-

4) 6 стров блока 8 с номером 1 (Н1 Е 1, N) осуществляется накопление текущей суммы в соответствии с выражениями (1) и (2), в течение всего данного промежутка времени с второго управляющего выхода 14 блока 11 управления на управляющих входах коммутатора 29 блока 8 с номером 1 присутствуют сигналы у =, 1, у = О, сформированные вторым дешифраторок 52 состояний счетчика 50 блока управления (поскольку

С ((!<<-1)М в течение первых (N-1)M тактов работы). ,Данные с первого входа 27 1-го блока 8 поступают на второй выход коммутатора 29 и с него на вход второй секции узла 35, который соединен с входом первого регистра 36 данной секции. Данные, являющиеся частичными сумками в выражениях (1) и (2), последовательно переписываются из регистра в регистр данного второго узла

35, с выхода последнего регистра" 36 данного узла поступают на первый выход 3? блока 8, а дальше на,третий вход 19,соответствующего блока 5 сис о< толической матрицы 4 (при 1 2) или на третий вход 19 блока 2 (при 1=1).

В течение следующих М тактов работ ты процессора в блоке 2 нли в блоке .5 с номером (1-1)(У1 <= 2, N) систолической матрицы 4 формируются окончательные результаты в соответствии с выражениями (1) и (2). Каждый результат С поступает при этом уже в пер<,п вую секцию узла 34 соответствующего

1 блока 8, так как íà (N-1)M-м такте работы вторым дешифратором 52 счетчи.ка 50 формируются управляющие сигналы у = 0 и у = 1, которые сохраняются до такта 1 = NM с начала обработки данных х, в процессоре. При этом данные, поступающие на первый вход

27 блока 8 через коммутатор 29, поступают на его первый выход, соединенный с входом первой секции узла 34, Поскольку каждый блок 5 включается в работу тактом позже, то через (И-1) тактов с начала переключения секций заполняется первая секция узла 34 первого блока 8., через М тактов — второго блока 8 и так далее до блока 8 с номером N,, Вторые секции узла 35 блоков 8 при этом отключены от входов блока, и содержимое регистров Зб вторых секций узла 35 за этот период обнуляется.

1615741

Начиная с такта M(N-1), т.е. на

М-м такте после переключения секций узлов 34 и 35, в первом блоке 8 vpo, изводится вывод результатов С, с вто10 ,рого выхода 38 данного блока 8, ко " торый занимает М тактов. 13ыводимые отсчеты C,,o с второго выхода 38 первого блока 8 поступают на выход 9 руппы блоков 8 и с него на выход 1р

ыходного М-канального коммутатора 10 далее в выводные каналы данных. При том выходной И-канальный коммутатор равляется также управляющими сигалами от первого дешифратора 51 счет -,g ика 50, представляющими собой униарный M-разрядный код. В результате а каждом 1-м такте (1 = i n + NN де i 6 1, М, и C 1, N) отсчет резульата С;„ передается в i-й выходной анал.

На такте (М+1) с начала вывода анных коммутатор 29 первого блока 8 руппы 7 подключает к второму входу

8 данного блока 8 второй выход 38 25 торого блока 8. Это осуществляется оступлением на управляющие входы 41

42 коммутатора управляющих сигналов

1, уо = О, сформированных к это- у моменту дешифратором 56. При этом 3О аборе управляющих сигналов у< в. у анные поступают на второй вход 42 оммутатора 29 и с его первого вы" ода 47 на вход первой секции узла

34. Одновременно с этим данные с первого входа 27 блока 8 (т.е„ от тре35 т его выхода 26 блока 2) поступают

1 на первый вход коммутатора 29 перво,го блока 8 и с его второго выхода 48 на вход второго узла 35. .О

На такте (M+1) с начала вывода д нных аналогичные переключения осуществляются в 1-ro блока 8, в кото ром вновь третий выход 26 соответствующего блока 5 подключается комму"

45 т@тором 29 к входу второго узла 35, а вход первого узла 34 в данном блок1@ оказывается подключенным к втором;у выходу 38 следующего (1е1)-го

Моха 8 (Yl B 2, 8-1).

Таким образом, в течение следующих

"Q

Æ11 тактов, считая с начала вывода результатов, осуществляется вывод

1 в()ех сформированных результатов С, ), П(рвые узлы 34 всех блоков 8 при э ом оказываются последовательно под-. и

5 к) юченными один за другим, образуя кйк бы единую память типа FIFO емкостью N(M-1) регистров. Одновременно во вторых узлах 35 постепенно накай- 1 ливаются текущие суммы в соответствии с выражениями (1) и (2) для вновь поступающих следующих последовательностей данных х, к по всем входным каналам, тем самым в таком многоканаль-, ном процессоре отсутствуют паузы на ввод/вывод данных.

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

+1)-)".o операционного блока, тактовые входы всех операционных блоков подключены к тактовому выходу блока управления, тактовый вход котсрого подключен к тактовому входу процессора, при этом операционный блок содержит сумматор, умножитель и регистр, выход которого подключен к первому входу уиножителя, выход которого подклю«чен к первому информацчонному входу сумматора и является первым выходом операционного блока, вторым выходом. которого является выход регистра, тактовый вход которого соединен с так— товым входом умножителя.и является тактовым входом операционного блока, первым и вторым информационными входами которого являются соотввтственно второй информационный вход умножителя и информационный вход регистра, о 1 л и ч а ю шийся тем, что, с целью раслирения области применения за счет многокачальной обработки данных, в него введены два блока по-" стоянной памяти, два коммутатора, К-й операционный блок из K блоков хранении, при агом первый выход и первый иыеорманионнвй вход р-го (р= 1, к-1}; *, блока хранения чодключены соответственно к управляющему входу и второму выходу (р+1)-го блока хранения, третий выход К-гo (К=1, К) операционного блока подключен к второ)ому информационному входу К-го блока хранения, третий выход которого подключен к третьему информационному входу К-го операционного блока, первый управляющий выход блока управления подключен к управляющим входам первого и

1615741

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

1615741 ба. Б

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

Редактор А. Козориз Техред Л. Сердюкова КорректорИ,Шароши

Заказ 3989

Тираж 567 Подписное

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

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

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