Устройство для вычисления двухмерного преобразования фурье

(54)5 0 06 Г 15/33 ОПИСАН ЗОБРЕТЕНЕЛЬСТВУ ВТОРСКОМУ С% 11, р. 1051.Кухарев Г.А., Майоров С.А., ТропченПринципы организации процессоровмерного дискретного преобразоФурье, - В кн.; Методы и микроэлектсредства цифрового преобразованиработки сигналов. Институт электровычислительной техники АН Латв1986, т. 2, с, 504-507. Лихог Тгапз 1 оггпз и ат, 1983,к С - 32,ко А,Ю.многования ронные я и обники и ССР,уело фд 1 ф,о) с ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯРИ ГКНТ СССР(54) УСТРОИСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО ПРЕОбРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и может быть использовано в вычислител ьных системах обработки, сигналов и иэображений высокой производительности, Цель изобретения - повышение быстродействия. Поставленная цель достигается эа счет того, что в состав устройства входят первый 7 и второй 8 блоки ввода, вычислительный блок 9, состоящий из групп процессорных элементов 1-го и 2-го типов, блок 10 вывода и соответствующие связи между узлами устройства. 3 з,п, ф-лы, 8 ил.егистры 48 - 52, умножитель 53, сумматор 4, триггер 55, элемент НЕ 56, первую 57, торую 58, треью 59 и четвертую 60 группы ыходов,Блок вывода (фиг, 8 содержит информаионные входы 61 (1=1,й 1), вход 62 синхроизации злы 63 ( - 1,й 1) задежки, регистрый 1) и информационные 64 =1 выходы 65 (1 В основу вычисление д 1 т 11 - 1 тп 11 п 1 г = Х п 1 =О=О, й 2 - 1;викуррентных оиства пПФ жен п 11 п 1, е п 2 1 т 21 22 лехр(=О,й 1-1; тг омощью ре отношен 1 М 2. )Пэ=ЯМ ю оИ = 111 х Ч П 1=О,Н ф =11 М 2 Первый блок 7 ввода (фиг, ) работает следующим образом,Входные отсчеты Хп 1 ь 2 от источника сигналов подаются одновременно на входы 12 и через соответствующие элементы 14задержки (индексуказывает количество тактов задержки) и группы элементов ИЛИ 15 на соответствующие выходы 16 блока ввода. Отсчет Хп 1 п 2 задерживается в элементах задержки 14 на тактов,где при й 1 й 2 2 1 ппп 2)-(, П,.М; 1, М 11 п 2 М, п,М, -1121 г 11 еО М "п 1 п(пэ,п 21-11 и, О,М,-1, п 2= М -Й ф 1 М 2М-пэахпПд, й 1 еОЙ; ; Ь -О, М 2 К 1 С учетом задержек отсчетов Хп 1 п 2 элементами 14 задержки на 1-м такте только на один вход группы элементов ИЛИ 15 подается соответствующее а-разрядное значение Хп 1 п, которое выдается на соответствующий выход 16 блока. При такой повторого типа вторую 45 инхровход 47,Изобретение относится к вычислитель- . рной технике и может быть использовано в 5вычислительных системах обработки сигна- влов и изображений высокой производитель- вности. 5Цель изобретения - повышение быстро- цдействия устройства. нНа фиг. 1 представлена структурнаясхема устройства вычисления двумерногоДПФ для й 1=й 2=3; на фиг.2 - функциональная схема первого блока ввода; на фиг. 3 -функциональная схема второго блока ввода;на фиг, 4 - функциональная схема вычислительного блока с входными и выходнымипотоками данных, на фиг, 5 - функциональ л 1ная схема вычислительного блока с входными и выходными потоками данных дляй 1=й 2=3; на фиг. 6 - функциональная схемапроцессорного элемента первого типа, нафиг. 7 - функциональная схема процессорного элемента второго типа; на фиг. 8 -функциональная схема блока вывода.Устройство для вычисления двумерногоДПФ (фиг. 1) содержит первые 11 - 1 з, вторые21 - 2 з, третьи 31 - Зз, четвертые 41-4 з и пятые 2551-5 з информационные входы, вход 6 синхронизации, первый 7 и второй 8 блоки ввода, вычислительный блок 9, блок 10 вывода1 и информационные выходы 111 - 119.Первый блок 7 ввода (фиг, 2) содержит 30информационные входы 12(=1 й 1 Я 2), выход 13 синхронизации, элементы 14 задержки, группы элементов ИЛИ 15 (=2,й 1+ й 2 - 21и информационные выходы 16(1=1,й 1+ й 2-1),Второй блок 8 ввода (фиг. 3) содержит 35информационные входы 17 (1=1, й 2+1), вход18 запуска, вход 19 синхронизации, регистры 20 (1=1, й 2+ 1), группы элементов ИЛИ2111=ГЙ 2 т 1),группы элементов И 22;(1=1,%+1) и информационный выход 23, 40Вычислительный блок 9 (фиг, 5) содержит информационные входы первой группы241 (1=1,й 1), инюрмационные входы второйгруппы 25 (1=1,й 1), информационные входытретьей группы 26 (1=1,й 1), информационные входы четвертой группы 27 (1=-1 й 1+й 2-1), информационный вход пятой группы28, процессорные элементы первого типа29 ц (1,)=1 й 1), процессорные элементы второго типа 30 л Я=1 й 2) и информационные 50выходы 31 (1=1,й 1).Процессорные элементы 9 первого типа(фиг. 6) содержит первый 32, второй ЗЗ итретий 34 входы, вход 35 синхронизации,регистры 36 - 38, умножитель 39, сумматор 5540, первый 41, второй 42 и третий 43 выходы.Процессорный элемент 10следовательной подаче значений Хуу 1 п 2 на один из входов группы элементов ИЛИ 15 информация не искажается. Таким образом, на выходах 16 блока 7 ввода формируется поток данных ХП 12 (т - номер такта работы устройства), который подается в вычислительный блок 9. Очередность подачи данных ХП 1 уу 2 в вычислительный блок 9 показана на фиг,4 и 5,Второй блок 8 ввода (фиг, 3) работает следующим образом,В исходном состоянии регистры 201 (1=ГБ 2+Я находятся в нулевом состоянии. При подаче на вход 18 нулевого сигнала группы элементов И 121 (1=ГМ 2 Л эвкрыввются и на вторые входы групп элементов ИЛИ 21 ( = 1,Й 2 + 1) подаются нулевые значения, на первые входы групп элементов ИЛИ 21(1=1,И 2+1) подаются соответствующие коэффициенты й 4 ч 2 п 2 (в 2 = = О,Й 2 - 1) с дополнительным (а+1)-м единичным разрядом и на первые входы группы элементов ИЛИ 21 и 2 +1 - нулевые значения, которые записываются в соответствующие регистры 20 ь Нулевое значение в регистр 20 и 2+1 записывается с целью обеспечения поточного режима работы устройства (для обнуления триггера 55 в процессорном элементе), При подаче на вход 18 единичного сигнала группы элементов И 22 открываются, блок 8 ввода работает в режиме кольцевого счетчика и на выходе 23 блока 8 ввода формируются соответствующие коэффициенты в 2 п 12.Процессорный элемент 9 первого типа работает следующим образом. На входы 32, 33 и 34 (фиг. 6) подаются соответственно значения Х 1 л, йп и Уьп, которые по заднему фронту тактового импульса записываются соответственно в регистры 36 - 38, На выходе 39 формируется значение Уь в и, которое подается на вход сумматора 40, на второй вход которого подается значение Хп, На выходе сумматора 40 формируется значение Ув= У 1 п ап + Х 1 п, которое подается на выход 43, а на выходы 41 и 42 подаются значения Хп и ип соответственно.Процессорный элемент 10 второго типа работает следующим образом. Регистры 48 - 52 и триггер 55 находятся в начальном состоянии, На входы 44 - 46(фиг, 7) подаются соответственно значения Уь, вь и Хь, причем гп-разрядное значение вп подается с дополнительным (в+1)-м единичным разрядом. В регистр 50, построенный на однотактных триггерах. по переднему фронту тактового импульса записывается значение510 Хь. В регистр 51, построенный на однотактных триггерах, записывается значение Хь, которое подается на его информационный вход с выхода регистра 50. В регистр 51 запись разрешается единичным сигналом, который подается с инверсного выхода триггера 55 на вход разрешения записи регистра 51 (в начальном состоянии на инверсном выходе триггера 55 единичный сигнал). По заднему фронту тактового импульса знвчения Уь,ви Хп записываются соответственно в регистры 48 и 49 на двухтактныхтриггерах и в регистр 52 на однотактныхтриггерах, триггер 55 устанавливается в15 единичное состояние. С инверсного выходатриггера 55 подается на вход разрешениязаписи регистра 51 нулевой сигнал, приэтом запись в регистр 51 запрещается, Элемент НЕ 56 обеспечивает запись значения20 Хь в регистр 52 по заднему фронту тактового импульса. На выходе умножителя 53формируется значение Уь вь на выходесумматора 54 - значение Уп, Й 4 п + Хп. Длязаписи в регистр 51 нового значения Хь25 необходимо триггер 55 установить в начальное состояние путем подачи на (в+1)-й входвторой группы 54 нулевого сигнала.Блок 10 вывода работает следующимобразом. На входы 61 (1=1 Л 1) последова 30 тельно подаются значения элементовУ 1 п 12 (в 1=0,61-Х; Гп 2=0,Й 2 1), которые записываются в регистры 64 узлов 63 задержки (фиг, 8). С выходов 65 (1=1,82) элементы -Уу 1 п 2 снимаются одновременно. С цельюобеспечения одновременной выдачи элементов Уп 1 уп 2 узлы 63 задержки состоят изпоследовательно соединенных регистровй 21 ( =1 Л 1),устройство работает следующим образом.В исходном состоянии регистра процессорные элементы 36, 27, 38, 48, 49. 50 и 51 итриггер 55 устанавливаются в нулевое со 45 стояние, в регистры 64 блока 10 вводазаписываются соответствующие коэффициЕнты Ия 2 гп 2,На входы Зи 5 постоянно подаются нулевые значения, а на входы 4 - элементы50 м,м 2 - +1, где 1=1,И 1,Рассмотрим работу устройства при вычислении элемента У 2 о для случая й 1=Й 2=3(фиг. 5).На нулевом такте на входы 24 з, 27 з и 2855 процессорного элемента 30 зз подаются соответственно нулевое значение, элемент(вй 2, О; 1) и элементы ХО 22. На выходе сумматора 54 процессорного элемента 30 ззформируется значение У 2(О)=Х 2 з, На пер(о)вом такте на вход 274 подается элемент . Х 21, в процессорном элементе 3023 на выходе сумматора 54 формируется значение У ) (О) = У ) (О) в)ч 2,о + Х 21, На втором такте на вход 275 подается элемент Х 2 о, процессорный элемент 301 з на выходе сумматора 54 формирует значение Утт) 10) = Ут) 10)оэчэ,о 4 хэоНа третьем такте на выходе сумматора 40 процессорного элемента 29 зз формируется значение У об = 0 вм,о + У (О), На12) четвертом такте на выходе сумматора 40 процессорного элемента 29 з 2 формируется эначениеУЦ =(ф оэгго ч. У0, на пятом такте на выходе сумматора 40 процессорного элемента 29 з 2 формируется значение Усо=уэ 1 =Уц гонг,о+УЯ) 10), которое подается на выход 31 з.Аналогично вычислению элемента Уоо вычисляются и другие элементы У)1 п 2 (фиг.5). Вычисленные элементы Уп)1 п 2 записываются в регистры 64) (ви 1,Й 2) блока 10 вывода для М 1= М 2=3 на 10-м такте и одновременно выдаются на выходы 11 устройства.Формула изобретения 1, Устройство для вычисления двумерного преобразования Фурье, содержащее вычислительный блок, содержащий Й 1 - 1 и М 2 процессорных элементов соответственно первого и второго типа (где М 1 и М 2 - размерности входной матрицы), при этом процессорный элемент первого типа содержит два регистра, умножитель и сумматор, а процессорный элемент второго типа - регистр, умножитель и сумматор, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены первый и второй блоки ввода и блок вывода, причем -й информационный вход первой группы (=1,М 1 Й 2) устройства подключен к -му информационному входу первого блока ввода, -й информационный вход второй группы (=1,Й 2) устройства подключен к -му информационному, входу второго блока ввода, -й информационный вход третьей группы (=1,Й 1) устройства подключен к 1-му информационному входу первой группы вычислительного блока, -й информационный вход четвертой группы (=1,М 1) устройства подключен к -му информационному входу второй группы вычислительного блока, 1-й информационный вход пятой группы (=1,Й) устройства подключен к -му информационному входу третьей группы вычислительного блока, 1.е информационные выходы первого блока ввода 111,141 ч сэт) подключены к соответствующим информационным входам шестой группы вычислительного блока, информационный выход второго блока ввода подключен к информационному входу вычислительного блока, -,р) 5 информационный выход вычислительногоблока (=1,М 1Йг) подключен к -му информационному входу блока вывода, 1-й информационныи выход блока вывода 11=1,41 142) подключен к ьму информацион ному выходу устройства, вход синхронизации которого соединен с входами синхронизации первого и второго блоков ввода, блока вывода и подключен к тактовому входу устройства, причем в вычислитель ный блок введено М 1(Й - 1)+1 процессорныхэлементов первого типа и Й 2(М 2-1) процессорных элементов второго типа, причем входы первой группы (Й 2,)-х процессорных элементов второго типа О=1,М 1) подключены 20 к соответствующим информационным входам первой группы вычислительного блока, входы второй группы (М 2,М 1)-го процессорного элемента подключены к информационным входам пятой группы вычислительного 25 блока, входы третьей группы (Й 2 )-х процессорных. элементов второго типа О=ГУЖ-и 11 4 1) х процессорных элементов второго тг.па( = 1,М 2 -1) подключены к информационным входам соответственно четвертой и 30 шестой групп вычислительного блока, входы второй группы (,Й 1)-х процессорных элеп ментов первого типа(1=1,М) подключены к информационным входам второй группы вычислительного блока, входы третьей груп пы (,Й 1)-х процессорных элементов первого типа (=ГЙ 1) подключены к информационным входам третьей группы вычислительного блока, входы первой группы 1 Ц)го процессорного элемента второго 40 типа 11= 1,М;=1.141) подключены к выхо.дам первой группы (+ 1,-го процессорного элемента второго типа, входы второй группы 1 Ц).гО процессорного элемента второго типа (=1,М 2 -1;)= 1,Й 1) подключены к выхо дам первой группы (+1 )-го процессорногоэлемента второго типа, входы второй группы (Ц)-го процессорного элемента второго типа (=1,М 2-1:)= 1,Й 1) подключены к выходам второй группы (+Ц)-го процессорного 50 элемента второго типа, входы второй группы (Ц)-го п)эоцессооноого элемента второго типа (" 1,М 2-1;)= 1 Й) подключены к выходам четвертой группы (+ 1,)-го процессорного элемента второго типа, входы третьей 55 группы (Й 2,)-го г)ооцессорного элементавторого типа Ц= 1,Й 1-1) подключены к выходам третьей группы (М 2,4+ 1)-го процессорного элемента второго типа, выходы первой группы (,)-го процессорного элемента вто 1661790 105 10 15 20 25 30 35 40 45 50 55 рого типа (1=1,Й 2-1:)=1,М 1-1) подключены к входам первой группы (+1,)+1)-го процессорного элемента первого типа, первый вход 1,го процессорного элемента первого типа Я=1,И 1) подключен к первому выходу (Й 1,-го процессорного элемента первого типа, второй вход(Ц)-го процессорного элемента первого типа (1=11,И 1-1;)=1,Я 1) подключен к второму выходу (+1,-го процессорного элемента первого типа, третий вход (1,-го процессорного элемента первого типе о= 1,М, З=ГМ 1-1) подключен к третьему входу (1,)+1)-го процессорного элемента первого типа, третий выход (1,1)-го процессорного элемента первого типа (1=1,М 1) подключен к 1-му выходу вычислительного блока, причем в процессорный элемент первого типа введен регистр, первый вход процессорного элемента подключен к информационному входу первого регистра, выход которого подключен к первому входу сумматора, второй вход которого подключен к выходу умножителя, первый и второй входы которого подключены к выходам соответственно второго и третьего регистров, второй и третий входы процессорного элемента подключены соответственно к информационным входам второго и третьего регистров, первый, второй и третий выходы процессорного элемента подключены соответственно к выходам первого и второго регистров и сумматора, вход синхронизации процессорного элемента подключен к входам разрешения записи первого, второго и третьего регистров, причем в процессорный элемент второго типа введены четыре регистра, триггер и элемент НЕ, причем а входов первой группы процессорного элемента подключены к щразрядному информационному входу первого регистра, выход которого подключен к первому входу умножителя (где в - разрядность чисел), в входов и (в+1)-й вход второй группы процессорного элемента подключены соответственно к гл-разрядному информационному входу второго регистра и к информационному входу триггера, выход второго регистра и прямой выход триггера подключены соответственно к в выходам второй и четвертой групп выходов процессорного элемента и к (в+ 1)-му выходу второй и четвертой групп выходов процессорного элемента, выход второго регистра подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, а-разрядный выход которого подключен к в выходам первой группы процессорного элемента, а второй вход умно- жителя подключен к выходу четвертого оегистра, информационный вход которого соединен с информационным входом пятого регистра и подключен к выходу третьего регистра, щ-разрядный информационный вход которого подключен к а входам третьей группы процессорного элемента, выходы третьей группы процессорного элемента подключены к выходам пятого регистра, инверсный выход триггера подключен к входу разрешения записи четвертого регистра, выход элемента НЕ - к входу разрешения записи пятого регистра, вход синхронизации процессорного элемента - к входам разрешения записи первого, второго и третьего регистров, к управляющему входу триггера и к входу элемента НЕ,2. Устройство по п,1, о т л и ч а ю щ е ес я тем, что первый блок ввода содержит й 2 К 1 элементов задержки и Й 1+Й 2 - 3 групп элементов ИЛИ, причем -й информационный вход блока ввода 1=1,ЬИар) подключен к информационному входу 1-го элемента задержки, выходы первого и (м 1 Й 2)-го элементов задержки подключены соответственно к первому и к (И 1+И 2 - 1)- му информационным выходам блока ввода входы -х групп элементов ИЛИ (1=2,И 1+ + Й 2-2) подключены к выходам разрядов ( - 1)-х элементов задержки, а выходы элементов ИЛИ групп подключены к выходам группы блока ввода. 3, Устройство по п,1, о т л и ч а ю щ е ес я тем, что второй блок ввода содержит 82+1 регистров, К 2+1 групп элементов И и М 2+1 групп элементов ИЛИ, причем 1-й информационный вход (1=12+1) блока подключен к первому входу 1-й группы элементов ИЛИ, вход запуска устройства подключен к первым входам элементов И 1-й группы, вход синхронизации блока ввода подключен к тактовым входам всех регистров, информационный вход 1-го регистра (1=1,И 2+1) подключен к выходу 1-й группы элементов ИЛИ, второй вход которого подключен к выходу 1-й группы элементов И, второй вход 1-й группы элементов И (=1,82) подключен к выходу(+1)-го регистра, выход первого регистра подключен к второму входу элементов И (И 2+1)-й группы и к 1-му выходу блока ввода,4. Устройство по п,1, о т л и ч а ю .ц е ес я тем, что блок вывода содержит М 1 узлов задержки, причем 1-й информационный вход блока вывода (1=1,Й 1) подключен к информационному входу 1-го узла задержки, 1-й информационный выход (=1,Й 2) )-го узла задержки Ц=1,М) подключен к соответствующему выходу блока вывода, вход синхронизации которого подключен к тактовым входам всех узлов задержки, 1 Б 617901661790 Составитель А. ВарановРедактор А. Козориз Техред М.Моргентал Корректор И, Муска роизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 10 аказ 2126 Тираж 413ВНИИПИ Государственного комитета по113035, Москва, ЖПодписноеобретениям и открытиям при ГКНТ СССауш,ская наб., 4/5