Устройство для вычисления двухмерного преобразования фурье Советский патент 1991 года по МПК G06F17/14 

«W

J- ц,

4 , v

О (

О

о

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

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

На фиг. 1 представлена структурная схема устройства вычисления двумерного ДПФ для на фиг. 2 - функциональная схема первого блока ввода; на фиг. 3 - функциональная схема второго блока ввода; на фиг. 4 - функциональная схема вычислительного блока с входными и выходными потоками данных; на фиг. 5 - функциональная схема вычислительного блока с входными и выходными потоками данных для на фиг. 6 - функциональная схема процессорного элемента первого типа; на фиг. 7 - функциональная схема процессорного элемента второго типа; на фиг. 8 - функциональная схема блока вывода.

Устройство для вычисления двумерного ДПФ (фиг. 1) содержит первые , вторые 21-2з, третьи Зг-Зз, четвертые 41-4з и пятые 5-|-5з информационные входы, вход 6 синхронизации, первый 7 и второй 8 блоки ввода, вычислительный блок 9, блок 10 вырода и информационные выходы 111-11g.

Первый блок 7 ввода (фиг.)одержит информационные входы 12i(,NT TM2), выход 13 синхронизации, элементы 14 задержки, группы элементов ИЛ И 15i C JNliN и информационные выходы 16i(,Ni+N2 1).

Второй блок 8 ввода (фиг. 3) содержит информационные входы 17i(, №41), вход 18 запуска, вход 19 синхронизации, регистры 20ijj 1, ). группы элементов ИЛИ 211 (), группы элементов И 22i (, N2+1) и информационный выход 23.

Вычислительный блок 9 (фиг. 5) содержит информационные входы первой группы 24| ( ,Ni), информационные входы втооой группы 25| (,NI), информационные входы третьей группы 2б| ( ,N1), информационные входы четвертой группы 27i ( ,Ni+N2- -1), информационный вход пятой группы 28, процессорные элементы первого типа 29ij (i,,Ni), процессорные элементы второго типа 30ijiy 1,N2) и информационные выходы 311 (,NI),

Процессорные элементы 9 первого типа (фиг. 6) содержит первый 32, второй 33 и третий 34 входы, вход 35 синхронизации, регистры 36-38, умножитель 39, сумматор 40, первый 41, второй 42 и третий 43 выходы.

Процессорный элемент 10 второго типа (фиг. 7) содержит первую 44, вторую 45 и третью 46 группы входов, синхровход 47,

регистры 48-52, умножитель 53, сумматор 54, триггер 55, элемент НЕ 56, первую 57, вторую 58, третью 59 и четвертую 60 группы выходов.

Блок вывода (фиг. б срдержиг информационные входы 61i (), вход 62 синхронизации, узлы 63i ( ,N1) задежки, регистры 64j (N2:n T)) и информационные выходы 65i (,NTp fsfe).

В основу работы устройства положено ычисление двумерного ДПФ

N1-1 N2 - 1

Yml гп2 2I Хп1 п2 ft/uV1 u/tf2n2 ;

П1 0 П2 0

тНШМ; ;WN exp{ -I -} с помощью рекуррентных соотношений

ЙМ хП(МГЧ

(.N,,,..,;

,. (0) , Nr ( Ь

пМ l, , о го,тг ) т,тг )

VY(N

т,тпг vn,m7 )

т, п, « o.N,-1; 1,-г О, Na-i j

т i,N2-i j и«1(ыГ 1.

Первый блок 7 ввода (фиг. 2) работает

следующим образом,

Входные отсчеты Хщ h2 от источника сигналов подаются одновременно на входы 12 и через соответствующие элементы 141 задержки (индекс I указывает количество

тактов задержки) и группы элементов ИЛИ 15 на соответствующие выходы 16 блока ввода. Отсчет Хпщ2 задерживается в элементах задержки 141 на тактов, где при Ni N2

; fN7-m;«(n,1«4)-(;nl«NrNlH,N|-,nl ,-™4у (п„пг}-(; n.rQ.N.-Nz; hz.O,N2-f,

при Ni N2

i-N,(n,1niVr,nl-o,Nl-ij пг , Мг; Nl-max(h,ltt.);w,«6,Nrt; .Nj-N,,

С учетом задержек отсчетов Xni n2 элемен- тами 14 задержки на k-м такте только на один вход группы элементов ИЛИ 15 подается соответствующее т-разрядное значение Xni n2 - которое выдается на соответствующий выход 16 блока. При такой последовательной подаче значений Хщ па на один из входов группы элементов ИЛИ 15 информация не искажается. Таким образом, на выходах 16 блока 7 ввода формируется

поток данных Xni n2 (t номер такта работы устройства), который подается в вычислительный блок 9. Очередность подачи данных

Xni n2 B вычислительный блок 9 показана на фиг. 4 и 5,

Второй блок 8 ввода (фиг. 3) работает следующим образом,

В исходном состоянии регистры 20| () находятся в нулевом состоянии. При подаче на вход 18 нулевого сигнала группы элементов И 22 (i l7N2+TJ закрыва- ются и на вторые входы групп элементов ИЛИ 21i (I 1.N2 + 1) подаются нулевые значения, на первые входы групп элементов ИЛИ 211 (,№+17 подаются соответствующие коэффициенты UN2 (12 0,№ - 1) с дополнительным (т+1)-м единичным разрядом и на первые входы группы элементов ИЛИ 21 N2 + 1 нулевые значения, которые записываются в соответствующие регистры 20|. Нулевое значение в регистр 20 N2 +1 записывается с целью обеспечения поточного режима работы устройства (для обнуления триггера 55 в процессорном элементе). При подаче на вход 18 единичного сигнала группы элементов И 22i открываются, блок 8 ввода работает в режиме кольцевого счетчика и на выходе 23 блока 8 ввода формируются соответствующие коэффициенты ГТ12Процессорный элемент 9-первого типа работает следующим образом. На входы 32, 33 и 34 (фиг. 6) подаются соответственно значения Xin, и Yin, которые по заднему фронту тактового импульса записываются соответственно в регистры 36-38. На выходе 39 формируется значение Ущ Win, которое подается на вход сумматора 40, на второй вход которого подается значение Х|П. На выходе сумматора 40 формируется значение Ymt Yin coin + Xin, которое подается на выход 43, а на выходы 41 и 42 подаются значения Х|П и оцп соответственно.

Процессорный элемент 10 второго типа работает следующим образом. Регистры 48-52 и триггер 55 находятся в начальном состоянии. На входы 44-46 (фиг. 7) подаются соответственно значения Yin, coin и Xin, причем m-разрядное значение tuin подается с дополнительным (т+1)-м единичным разрядом. В регистр 50, построенный на однотак- тных триггерах, по переднему фронту тактового импульса записывается значение

Х|П. В регистр 51, построенный на однотак- тных триггерах, записывается значение Х|П, которое подается на его информационный вход с выхода регистра 50. В регистр 51 5 запись разрешается единичным сигналом, который подается с инверсного выхода триггера 55 на вход разрешения записи регистра 51 (в начальном состоянии на инверсном выходе триггера 55 единичный сигнал). 0 По заднему фронту тактового импульса значения Yjn.uJn и Х|П записываются соответственно в регистры 48 и 49 на двухтактных триггерах и в регистр 52 на однотактных триггерах, триггер 55 устанавливается в единичное состояние. С инверсного выхода триггера 55 подается на вход разрешения записи регистра 51 нулевой сигнал, при этом запись в регистр 51 запрещается. Элемент НЕ 56 обеспечивает запись значения Xin в регистр 52 по заднему фронту тактового импульса. На выходе умножителя 53 формируется значение Yin ftJtn на выходе сумматора 54 - значение Yin, + Х|П. Для записи в регистр 51 нового значения Xin необходимо триггер 55 установить в начальное состояние путем подачи на (т+1)-й вход второй группы 54 нулевого сигнала.

Блок 10 вывода работает следующим образом. На входы 61i (,Ni) последовательно подаются значения элементов .Ymi m2 (,NT-T; гг),№-1), которые записываются в регистры 64 узлов 63 задержки (фиг. 8). С выходов 65i(,N2) элементы - Ymi m2 снимаются одновременно. С целью обеспечения одновременной выдачи элементов Ymi гл2 узлы 63| задержки состоят из последовательно соединенных регистров №-1-1 (M.Ni).

Устройство работает следующим образом.

В исходном состоянии регистра процессорные элементы 36, 27, 38, 48, 49, 50 и 51 и триггер 55 устанавливаются в нулевое состояние, в регистры 64| блока 10 ввода записываются соответствующие коэффициенты Ум2 т2

На входы 3|И 5i постоянно подаются нулевые значения, а на входы 4| - элементы

«N1.N2 -1+1 - гДе .N1.

Рассмотрим работу устройства при вычислении элемента У 20 для случая (фиг. 5).

На нулевом такте на входы 24з, 27з и 28 процессорного элемента ЗОзз подаются соответственно нулевое значение, элемент

(й$2. О 1) и элементы Х°22. На выходе сумматора 54 процессорного элемента ЗОзз формируется значение Y 2(0)X22. На пер5

0

5

0

5

0

5

0

5

вом такте на вход 274 подается элемент Х121, в процессорном элементе 3023 на выходе сумматора 54 формируется значеvЈ1) (0) YЈ°) (0) ,о + X2i. На втоние

ром такте на вход 27s подается элемент Х220, процессорный элемент ЗОчз на выходе сумматора 54 формирует значение

) (0) уф (0) WN2,o + Х20 .

На третьем такте на выходе сумматора 40 процессорного элемента 29зз формируется значение Y® 0 .O + Y) (0), На четвертом такте на выходе сумматора 40 процессорного элемента 29з2 формируется

значение YQ Q© «MNI.O + YV(0). На пятом такте на выходе сумматора 40 процессорного элемента 29з2 формируется значение

Y5oo УгЙ YrJi} UJNI.O + Ytf) (0), которое подается на выход 31з.

Аналогично вычислению элемента YOO

вычисляются и другие элементы Ymi 012 (фиг. 5). Вычисленные элементы Ymi m2 записываются в регистры 64i (i 1,№) блока 10 вывода для Ni на 10-м такте и одновременно выдаются на выходы 11 устройства. Формула изобретения 1. Устройство для вычисления двумерного преобразования Фурье, содержащее вычислительный блок, содержащий Ni-1 и N2 процессорных элементов соответственно первого и второго типа (где NI и N2 - размерности входной матрицы), при этом процессорный элемент первого типа содержит два регистра, умножитель и сумматор, а процессорный элемент второго типа - регистр, умножитель и сумматор, отличающееся тем, что, с целью повышения быстродействия, в него введены первый и второй блоки ввода и блок вывода, причем 1-й информационный вход первой группы (,Mr N2) устройства подключен к 1-му информационному входу первого блока ввода. 1-й информационный вход второй группы (,N2) устройства подключен к i-му информационному входу второго блока ввода, 1-й информационный вход третьей группы (,NI) устройства подключен к i-му информационному входу первой группы вычислительного блока, 1-й информационный вход четвертой группы ( ,Ni) устройства подключен к i-му информационному входу второй группы вычислительного блока, 1-й информационный вход пятой группы (,NI) устройства подключен к i-му информационному входу третьей группы вычислительного блока, 1-е информационные выходы первого блока ввода (M,Ni+ N2-1) подключены к соответствующим информационным входам шестой группы вычислительного блока, информационный выход второго блока ввода подключен к информационному входу вычислительного блока, -f

информационный выход вычислительного блока (,NI N2) подключен к i-му информационному входу блока вывода, 1-й информационный выход блока вывода (,NI N2) подключен к I-му информационному выходу устройства, вход синхронизации которого соединен с входами синхронизации первого и второго блоков ввода, блока вывода и подключен к тактовому входу устройства, причем в вычислительный блок введено Ni(Ni-1)+1 процессорных элементов первого типа и N2() процессорных элементов второго типа, причем входы первой группы (N2,J)-x процессорных элементов второго типа ,N i) подключены

к соответствующим информационным входам первой группы вычислительного блока, входы второй группы (№,Ni)-ro процессорного элемента подключены к информационным входам пятой группы вычислительного

блока, входы третьей группы (N2.j)-x процессорных элементов второго типа ( (l.NQ-x процессорных элементов второго т,и- па(1 1.N2 -1) подключены к информационным входам соответственно четвертой и

шестой групп вычислительного блока, входы второй группы (l,Ni)-x процессорных эле- ментов первого типа (,NI) подключены к информационным входам второй группы вычислительного блока, входы третьей группы (i,Ni)-x процессорных элементов первого типа ( ,IsTi) подключены к информационным входам третьей группы вычислительного блока, входы первой группы (t,j)-ro процессорного элемента второго

типа (i 1,N2-1;j 1,Ni) подключены к выходам первой группы (i+ 1,j)-ro процессорного элемента второго типа, входы второй группы (l,j)-roj jpioyeccoj}Hpro элемента второго типа (,N2 -1;j 1,Ni) подключены к выходам первой группы (i+1,j)-ro процессорного элемента второго типа, входы второй группы Q,J)-rp процессорного элемента второго типа (М,N2-1:1 1,Ni) подключены к выходам второй группы (H-1,j)-ro процессорного

элемента второго типа, входы второй группы 0,)-го леоцессо 1ного элемента второго типа (1 1,N2-1;j iTNiyподключены к выходам четвертой группы (1+ LjVro процессорного элемента второго типа, входы третьей

группы (N2,J)-roпроцессорного элемента второго типа () 1,Ni-1) подключены к выходам третьей группы (№,+ 1)-го процессорного элемента второго типа, выходы первой группы (i,J)-ro процессорного элемента второго типа (,,Ni-1) подключены к входам первой группы (l+1,j+1)-ro процессорного элемента первого типа, первый вход (1 ,j)-ro процессорного элемента первого типа (,NI) подключен к первому выходу (N1,j)-ro процессорного элемента первого типа, второй axofl(i,j)-ro процессорного эле- мента первого типа (,Ni-1;J CNi) подключен к второму выходу (l + 1,j)-ro процессорного элемента первого типа, тре- тий вход (I.J)-ro процессорного элемента первого типа (i 1,Ni; ,Ni-1) подключен к третьему входу (l,j+1)-ro процессорного элемента первого типа, третий выход (i.t)-ro процессорного элемента первого типа (,NI) подключен к i-му выходу вычислительного блока, причем в процессорный элемент первого типа введен регистр, первый вход процессорного элемента подключен к информационному входу первого регистра, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, первый и второй входы которого подключены к выходам соответственно второго и третьего регистров, второй и третий входы процессорного элемента подключены соответственно к информационным входам второго и третьего регистров, первый, второй и третий выходы процессорного элемента под- ключены соответственно к выходам первого и второго регистров и сумматора, вход синхронизации процессорного элемента подключен к входам разрешения записи первого, второго и третьего регистров, причем в процессорный элемент второго типа введены четыре регистра, триггер и элемент НЕ, причем m входов первой группы процессорного элемента подключены к т- разрядному информационному входу пер- вого регистра, выход которого подключен к первому входу умножителя (где m - разрядность чисел), m входов и (т+1)-й вход второй группы процессорного элемента подключены соответственно к m-разрядному инфор- мационному входу второго регистра и к информационному входу триггера, выход второго регистра и прямой выход триггера подключены соответственно к m выходам второй и четвертой групп выходов процес- сорного элемента и к (т+ 1)-му выходу второй и четвертой групп выходов процессорного элемента, выход второго регистра подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, m-разрядный выход которого подключен к m выходам первой группы процессорного элемента, а второй вход умножителя подключен к выходу четвертого оегистра, информационный вход которого

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

2.Устройство поп.1,отличающее- с я тем, что первый блок ввода содержит N2 NI элементов задержки и N1+N2-3 групп элементов ИЛИ, npH46Mj информационный вход блока ввода (,NI N2) подключен к информационному входу 1-го элемента задержки, выходы первого и (Ni №)-го элементов задержки подключены соответственно к первому и к (Ni+N2 1)- му информационным выходам блока вврда входы 1-х групп элементов ИЛИ (,NI+ ) подключены к выходам разрядов (i-1)-x элементов задержки, а выходы элементов ИЛИ групп подключены к выходам группы блока ввода.

3.Устройство поп.1,отличающее- с я тем, что второй блок ввода содержит N2+1 регистров, N2+1 групп элементов И и N2+1 групп элементов ИЛИ причем i-й информационный вход (,) блока подключен к первому входу 1-й группы элементов ИЛИ, вход запуска устройства подключен к первым входам элементов И 1-й группы, вход синхронизации блока ввода подключен к тактовым входам всех регист- ров, информационный вход 1-го регистра (,N2+1) подключен к выходу i-й группы элементов ИЛИ, второй вход которого подключен к выходу 1-й группы элементов И, второй вход i-й группы элементов И (,N2) подключен к выходу (i+1)-ro регистра, выход первого регистра подключен к второму входу элементов И (№+1}-й группы и к i-му выходу блока ввода.

4.Устройство поп. 1, отличаю щ е е- с я тем, что блок вывода содержит N1 узлов задержки, причем i-й информационный вход блока вывода (,NI) подключен к информационному входу 1-го узла задержки, i-й информационный выход (,№)-го узла задержки (,Ni) подключен к соответствующему выходу блока вывода, вход синхронизации которого подключен к тактовым входам всех узлов задержки.

Чъ-tV - .

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах обработки сигналов и изображений высокой производительности. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят первый и второй блоки 7, 8 ввода, вычислительный блок 9, состоящий из групп процессорных элементов 1-го и 2-го типов, блок 10 вывода и соответствующие связи между узлами устройства. 3 з.п. ф-лы, 8 ил.

Xoo X

. X#rtO

Фиг. 2

(а,,А(1 &,,,,-№

/(

о,

п

т чг

,

)

,

Чгг

06А1991

Фиг. 6

Фи.1