Устройство для вычисления двухмерного преобразования фурье
Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах обработки сигналов и изображений высокой производительности. Цель изобретения - повышение быстродействия. Поставленная цель достигается за счет того, что в состав устройства входят первый и второй блоки 7, 8 ввода, вычислительный блок 9, состоящий из групп процессорных элементов 1-го и 2-го типов, блок 10 вывода и соответствующие связи между узлами устройства. 3 з.п. ф-лы, 8 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 6 06 F 15/332
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ у22 уО
lt уело уй уЮ у3 уа
ro(0 (Ь 4
О
О Ь,,/ 4с ь
Ю сю.1
«er «й т Ф «н «» ii «м«м
Ди!
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4658440/24 (22) 06.02.89 (46) 07,07.91. бюл. ¹ 25 (72) В.П. Якуш, П.И. Соболевский, Н.А. Лиходед и В.В. Косьянчук (53) 681.32(088.8) (56) Thompson C,D, Fourler Transforms in
VLSI, — IEEE Trans. on Compat, 1983, v. С вЂ” 32, ¹ 11, р. 1051.
Кухарев Г.А., Майоров С.А., Тропченко А.Ю.
Принципы организации процессоров многомерного дискретного преобразования
Фурье. — В кн.; Методы и микроэлектронные средства цифрового преобразования и обработки сигналов. Институт электроники и вычислительной техники АН Латв, ССР, 1986, т. 2, с, 504-507.
„„Я2„„1бб1790 А1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ПРЕОбРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано в вычислител ьных системах обработки, сигналов и иэображений высокой производительности. Цель изобретения — повышение быстродействия. Поставленная цель достигается эа счет того, что в состав устройства входят первый 7 и второй 8 блоки ввода, вычислительный блок 9, состоящий из групп процессорных элементов 1-го и 2-ro типов, блок 10 вывода и соответствующие связи . между узлами устройства. 3 з,п. ф-лы, 8 ил.
1661790
Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах обработки сигна( лов и изображений высокой производительности.
Цель изобретения — повышение быстродействия устройства.
На фиг. 1 представлена структурная схема устройства вычисления двумерного
ДПФ для N<=Nz=3; на фиг. 2 — функциональная схема первого блока ввода; на фиг. 3— функциональная схема второго блока ввода; на фиг, 4 — функциональная схема вычислительного блока с входными и выходными потоками данных, на фиг, 5 — функциональная схема вычислительного блока с входными и выходными потоками данных для
N1=N2=3; на фиг. 6 — функциональная схема процессорного элемента первого типа, на фиг. 7 — функциональная схема процессорного элемента второго типа; на фиг. 8— функциональная схема блока вывода.
Устройство для вычисления двумерного
ДПФ (фиг. 1) содержит первые 1> — 1з, вторые
21 — 2з, третьи 31 — Зз, четвертые 41 — 4з и пятые
51 — 5з информационные входы, вход 6 синхронизации, первый 7 и второй 8 блоки ввода, вычислительный блок 9, блок 10 вывода и информационные выходы 111 — 119.
Первый блок 7 ввода (фиг. 2) содержит информационные входы 12;(i=1,К1 Я2), выход 13 синхронизации, элементы 14 задержки, группы элементов ИЛИ 151(i=2,N>+ N z--2 и информационные выходы 161(i=1,N1+ N2-1).
Второй блок 8 ввода (фиг. 3) содержит информационные входы 171 (i=1, НА+1), вход
18 запуска, вход 19 синхронизации, регистры 201 (i=1, Nz+ 1), группы элементов ИЛИ
21 (!=айэн- 1J, группы элементов И 22; (i=1, Й21) и информационный выход 23, Вычислительный блок 9 (фиг, 5) содержит информационные входы первой группы
24 (i=1,N1), ин юрмационные входы второй группы 25 (i=1,N1), информационные входы третьей группы 261 (l=1,N>), информационные входы четвертой группы 271 (i=-1,%+й2-1), информационный вход пятой группы
28, процессорные элементы первого типа
29ц (Ц=1Я1), процессорные элементы второго типа 3011 Я=1%) и информационные выходы 311(l=1,N 1).
Процессорные элементы 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 группы выходов, 5 Блок вывода (фиг. 8 содержит информационные входы 611(l=1,Ni), вход 62 синхронизации, злы 631 (l=1,й1) задежки, регистры
64 (j=1, N2+;1=1,N1) и информационные выходы 651 (i=1, 1 г), 10 В основу работы устройства положено вычисление двумерного ДПФ
111 -1 уп11п12 Х Х Х» п2®М1 + 2
» =0 п2=0
2 уг т1=0,М1-1; юг=О,Nz — 1;ви = ехр(-I )
N с помощью рекуррентных соотношений ь1(уу1г = Х,,Мг (оl (И.1= n (+ ) Ê,пу <1" 11„М -гу1-< p
i 1У1, ГЛг (1 1 (4- 1) 25 (К1->) УУ1 111г У11т ТУ1г ууу 1 П1г Мг,mà М 30 1 1111у =. О г1 1 ) 1т1г П = О "г ) hl =1,Nг-1 > 8=1,М,-1 Первый блок 7 ввода (фиг. 2) работает 35 следующим образом, Входные отсчеты Xn hz от источника сигналов подаются одновременно на входы 12 и через соответствующие элементы 14 l задержки (индекс l указывает количество 40 тактов задержки) и группы элементов ИЛИ 15 на соответствующие выходы 16 блока ввода. Отсчет Х» ng задерживается в элементах задержки 14 на i тактов, i где при N<> hh М,-min(n,,"t)-<;n, N, М,.1,М,;n =0М,,, N Ам(nÄn,)1n, 0К М2 г, ОМ при N<< Nz N,- n(n,,n,)-1; п,.0,М,- <, nz= М -N,it, М 1= М -1уэоу(11„nt)-I niеО,Й,-1 п2-0 М,-К,, С учетом задержек отсчетов Х» nz элемен55 тами 14 задержки на 1-м такте только на один вход группы элементов ИЛИ 15 подается соответствующее m-разрядное значение Х» ng, которое выдается на соответствующий выход 16 блока. При такой по1661790 следовательной подаче значений Xni nz на один из входов группы элементов ИЛИ 15 информация не искажается. Таким образом, на выходах 16 блока 7 ввода формируется поток данных Хй1nz (t — номер такта работы устройства), который подается в вычислительный блок 9. Очередность подачи данных Х„ nz в вычислительный блок 9 показана на фиг.4 и 5, Второй блок 8 ввода (фиг, 3) работает следующим образом, В исходном состоянии регистры 20i (1= Г,Й2+1) находятся в нулевом состоянии. При подаче на вход 18 нулевого сигнала группы элементов И 12; (l=ll ) эвкрыввются и на вторые входы групп элементов ИЛИ 21 (I = 1,Nz + 1) подаются нулевые значения, на первые входы групп элементов ИЛИ 2 1 i (i=1,И2+1) подаются соответствующие коэффициенты вм2 п2 (mz = = О,Nz — 1) с дополнительным (а+1)-м единичным разрядом и на первые входы группы элементов ИЛИ 21 Nz + 1 — нулевые значения, которые записываются в соответствующие регистры 20i. Нулевое значение в регистр 20 Nz +1 записывается с целью обеспечения поточного режима работы устройства (для обнуления триггера 55 в процессо рном элементе), При подаче на вход 18 единичного сигнала группы элементов И 22i открываются, блок 8 ввода работает в режиме кольцевого счетчика и на выходе 23 блока 8 ввода формируются соответствующие коэффициенты в42 и 2. Процессорный элемент 9.первого типа работает следующим образом. На входы 32, 33 и 34 (фиг. 6) подаются соответственно значения Xin, cUln и Yin, которые по заднему фронту тактового импульса записываются соответственно в регистры 36 — 38. На выходе 39 формируется значение Yin в,, которое подается на вход сумматора 40, на второй вход которого подается значение Xin, На выходе сумматора 40 формируется значение Ymt= Yin а п + Xin, которое подается на выход 43, а на выходы 41 и 42 подаются значения Х, и а, соответственно. Процессорный элемент 10 второго типа работает следующим образом. Регистры 48 — 52 и триггер 55 находятся в начальном состоянии, На входы 44 — 46(фиг. 7) подаются соответственно значения Yin, вь и Х >, причем m-разрядное значение в, подается с дополнительным (m+1)-м единичным разрядом. В регистр 50, построенный на однотактных триггерах. по переднему фронту тактового импульса записывается значение 10 Х,. В регистр 51, построенный на однотактных триггерах, записывается значение Х п, которое подается на его информационный вход с выхода регистра 50. В регистр 51 запись разрешается единичным сигналом, который подается с инверсного выхода триггера 55 на вход разрешения записи регистра 51 (8 начальном состоянии на инверсном выходе триггера 55 единичный сигнал). По заднему фронту тактового импульса знвчения Yin,в „и Xin записываются соответственно в регистры 48 и 49 на двухтактных триггерах и в регистр 52 на однотактных триггерах, триггер 55 устанавливается в 15 единичное состояние. С инверсного выхода триггера 55 подается на вход разрешения записи регистра 51 нулевой сигнал, при этом запись в регистр 51 запрещается. Элемен- HE 56 обеспечивает запись значения 20 Xin в регистр 52 по заднему фронту тактового импульса. На выходе умножителя 53 формируется значение Yin вь, на выходе сумматора 54 — значение Yin, Vn + Xin. Для записи в регистр 51 нового значения Xiп необходимо триггер 55 установить в начальное состояние путем подачи на (m+1)-й вход второй группы 54 нулевого сигнала. Блок 10 вывода работает следующим образом. На входы 61i (i=1 N<) последова30 тельно подаются значения элементов Ym) mz (я =0 N1 Х; Гп2=0,И2 — 1), которые записываются в регистры 64 узлов 63 задержки (фиг, 8). С выходов 65igl=1,Nz) элементы— Yml mz снимаются одновременно. С целью обеспечения одновременной выдачи элементов Ymi mz узлы 63i задержкисостоятиз последовательно соединенных регистров Nz- -i (i=1, N i). Устройство работает следующим образом. В исходном состоянии регистра процессорные элементы 36, 27, 38, 48, 49. 50 и 51 и триггер 55 устанавливаются в нулевое со45 стояние, в регистры 64i блока 10 ввода записываются соответствующие коэффициeHTbl lLiN2 m2 . На входы З.и 5 постоянно подаются нулевые значения, а на входы 4i — элементы 50 > N <, Nz — i + 1 где 1=1, N1 Рассмотрим работу устройства при вычислении элемента Y 2о для случая Й1=Й2=3 (фиг. 5). На нулевом такте на входы 24з, 27з и 28 55 процессорного элемента 30зз подаются соответственно нулевое значение, элемент (в 2, 0; 1) и элементы Xozz. На выходе сумматора 54 процессорного элемента 30зз формируется значение У z(0)=Xzz. На пер(о) 1661790 вом такте на вход 274 подается элемент . х zi, в процессорном элементе 302з на выходе сумматора 54 формируется значение Y()(0) = Y()(О) в)ч2,p+Xzq. На втором такте на вход 275 подается элемент Х 2о, процессорный элемент 30 з на выходе сумматора 54 формирует значение У(т) (О) = Уэ) (О) . гдчэ,о 4- хэо . На третьем такте на выходе сумматора 40 процессорного элемента 29зз формируется значение У =0 в(ч,p+Y (О), На (2) четвертом такте на выходе сумматора 40 процессорного элемента 29з2 формируется эначениеУЦ = (ф оэгго + Y(l)(0). на пятом такте на выходе сумматора 40 процессорного элемента 29з2 формируется значение увоо — — у(эт)т = YQ гонг,о + уЯ) (О), которое подается на выход 31з. Аналогично вычислению элемента Уоо вычисляются и другие элементы Ym mz (фиг. т 5). Вычисленные элементы Ymt mz записываются в регистры 64((i= 1,Nz) блока 10 вывода для N>= М2=3 на 10-м такте и одновременно выдаются на выходы 11 устройства. Формула изобретения 1. Устройство для вычисления двумерного преобразования Фурье, содержащее вычислительный блок, содержащий N> — 1 и М2 процессорных элементов соответственно первого и второго типа (где Ni u Nz— размерности входной матрицы), при этом процессорный элемент первого типа содержит два регистра, умножитель и сумматор, а процессорный элемент второго типа — регистр, умножитель и сумматор, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены первый и второй блоки ввода и блок вывода, причем i-й информационный вход первой группы ((=1,М1 Nz) устройства подключен к I-му информационному входу первого блока ввода, i-й информационный вход второй группы ((=1,N2) устройства подключен к i-му информационному, входу второго блока ввода, I-й информационный вход третьей группы ((=1,М1) устройства подключен к i-му информационному входу первой группы вычислительного блока, 1-й информационный вход четвертой группы (i=1,N>) устройства подключен к i-му информационному входу второй группы вычислительного блока, I-й информационный вход пятой группы (I=1,N>) устройства подключен к i-му информационному входу третьей группы вычислительного блока, !-е информационные выходы первого блока ввода (l=-1,141ч 14т-1) подключены к соответствующим информационным входам шестой группы вычислительного блока, информационный выход второго блока ввода подключен к информационному входу вычислительного блока, I g 5 информационный выход вычислительного блока (I=1,N1 N2) подключен к i-му информационному входу блока вывода, I-й информационныи выход блока вывода (i=I,N N4) подключен к I-муинформацион10 ному выходу устройства, вход синхронизации которого соединен с входами . синхронизации первого и второго блоков ввода, блока вывода и подключен к тактовому входу устройства, причем в вычислитель15 ный блок введено Ni(N> — 1)+1 процессорных элементов первого типа и Nz(Nz — 1) процессорных элементов второготипа, причем входы первой группы (М2,j)-х процессорных элементов второго типа 0=1,N 1) подключены 20 к соответствующим информационным входам первой группы вычислительного блока, входы второй группы (М2,N<)-го процессорного элемента подключены к информационным входам пятой группы вычислительного 25 блока, входы третьей группы (М2.J)-õ процессорных элементов второго типа О=3,Й )-и (I а(1) х процессорных элементов второго т)гna(I = 1,Nz -1) подключены к информационным входам соответственно четвертой и 30 шестой групп вычислительного блока, входы второй группы (I,N>)-õ процессорных эле-. ментов первого типа(1=1,N>) подключены к информационным входам второй группы вычислительного блока, входы третьей груп35 пы (I,М1)-х процессорных элементов первого типа (1=1,М1) подключены к информационным входам третьей группы вычислительного блока, входы первой группы (I))ro процессорного элемента второго 40 типа (1= 1,М - 1;)=1.141) подключены к выходам первой группы (I+ 1 j)-го процессорного элемента второго типа, входы второй группы (1Ц)-гО процессорного элемента второго типа (i=1,Nz -1;j= 1,Ni) подключены к выхо45 дам первой группы (I+1,J)-го процессорного элемента второго типа, входы второй группы (Ц)-го процессорного элемента второго типа (l=1,N2-1;j= 1,N1) подключены к выходам второй группы (i+1,J)-го процессорного 50 элемента второго типа, входы второй группы (Ц)-гоп ооцессо >ноого элемента второго типа (1- 1,N2-1;j= 1,N1) подключены к выходам четвертой группы (I+ 1,J)-го процессорного элемента второго типа, входы третьей 55 группы (Nz,j)-ro процессорного элемента второго типа (j= 1,N>-1) подключены к выходам третьей группы (Nz,j+ 1)-го процессорного элемента второго типа. выходы первой группы (Ц)-го процессорного элемента вто1661790 5 45 55 рого типа (1=1,Nz — 1;J=1,N1-1) подключены к входам первой группы (i+1,)+1)-го процессорного элемента первого типа, первый вход (1,J)-го процессорного элемента первого типа(J=1,N<) подключен к первому выходу (N1,J)-го процессорного элемента первого типа, второй вход (Ц}-го процессорного элемента первого типа (i=1,N<-1;J=1,N ) подключен к второму выходу (i+1,J)-ro процессорного элемента первого типа, третий вход (i,j)-ro процессорного элемента первого типе о= 1,М1, =ГМ1 - ) подключен к третьему входу (l,j+1)-го процессорного элемента первого типа, третий выход (i,1)-го процессорного элемента первого типа (I-1,N1) подключен к i-му выходу вычислительного блока, причем в процессорный элемент первого типа введен регистр, первый вход процессорного элемента подключен к информационному входу первого регистра, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, первый и второй входы которого подключены к выходам соответственно второго и третьего регистров, второй и третий входы процессорного элемента подключены соответственно к информационным входам второго и третьего регистров, первый, второй и третий выходы процессорного элемента подключены соответственно к выходам первого и второго регистров и сумматора, вход синхронизации процессорного элемента подключен к входам разрешения записи первого, второго и третьего регистров, причем в процессорный элемент второго типа введены четыре регистра, триггер и элемент НЕ, причем m входов первой группы процессорного элемента подключены к mразрядному информационному входу первого регистра, выход которого подключен к первому входу умножителя (где m — разрядность чисел), m входов и (m+1)-й вход второй группы процессорного элемента подключены соответственно к m-разрядному информационному входу второго регистра и к информационному входу триггера, выход второго регистра и прямой выход триггера подключены соответственно к m выходам второй и четвертой групп выходов процессорного элемента и к (m+ 1)-му выходу второй и четвертой групп выходов процессорного элемента, выход второго регистра подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, m-разрядный выход которого подключен к m выходам первой группы процессорного элемента, а второй вход умножителя подключен к выходу четвертого оегистра, информационный вход которого соединен с информационным входом пятого регистра и подключен к выходу третьего регистра, m-разрядный информационный вход которого подключен к m входам третьей группы процессорного элемента, выходы третьей группы процессорного элемента подключены к выходам пятого регистра, инверсный выход триггера подключен к входу разрешения записи четвертого регистра, выход элемента НŠ— к входу разрешения записи пятого регистра, вход синхронизации процессорного элемента — к входам разрешения записи первого, второго и третьего регистров, к управляющему входу триггера и к входу элемента НЕ. 2. Устройство по п,1, о т л и ч а ю щ е ес я тем, что первый блок ввода содержит й2 . Ni элементов задержки и Ni+Nz — 3 групп элементов ИЛИ, причем i-й информационный вход блока ввода (i=1,N> Nz) подключен к информационному входу I-го элемента задержки, выходы первого и (М1 . Щ-го элементов задержки подключены соответственно к первому и к (N>+Nz — 1)му информационным выходам блока ввода входы I-x групп элементов ИЛИ (1=2,N>+ -i Й2-2) подключены к выходам разрядов (i — 1)-х элементов задержки, а выходы элементов ИЛИ групп подключены к выходам группы блока ввода. 3, Устройство по п,1, о т л и ч а ю щ е ес я тем, что второй блок ввода содержит Nz+ регистров, Nz+1 групп элементов И и Nz+1 групп элементов ИЛИ, причем 1-й информационный вход (1=1,ЪЬ+1) блока подключен к первому входу I-й группы элементов ИЛИ, вход запуска устройства подключен к первым входам элементов И 1-й группы, вход синхронизации блока ввода подключен к тактовым входам всех регистров, информационный вход i-го регистра (1=1,Nz+1) подключен к выходу i-й группы элементов ИЛИ, второй вход которого подключен к выходу 1-й группы элементов И, второй вход i-й группы элементов И (=1,Nz) подключен к выходу (!+1)-го регистра, выход первого регистра подключен к второму входу элементов И (Nz+1)-й группы и к i-му выходу блока ввода, 4. Устройство по п.1, о т л и ч а ю .ц е ес я тем, что блок вывода содержит N1 узлов задержки, причем i-й информационный вход блока вывода (i=1,N>) подключен к информационному входу i-ro узла задержки, I-й информационный выход (i=1,Й2) j-го узла задержки (J=1,N >) подключен к соответствующему выходу блока вывода, вход синхронизации которого подключен к тактовым входам всех узлов задержки. 1661790 1661790 1661790 1661790 Составитель А. Варанов Техред M.Moðãåíòàë Корректор И, Муска Редактор А. Козориз Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина, 101 Заказ 2126 Тираж 413 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5
