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

(19) П ) 55 0 06 Е 15/33 ОБРЕТ САНИ ОМУ СВИД ЬСТВУ А 2 015 6,90(56) Кухарев Г.А, и др, Систолическиепроцессоры для обработки сигналов, Мн 1988,с.75, рис. 4,3.1,(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к области вычислительной техники и может быть использованов высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов и изображенийдля вычисления двумерного ДПФ. Цель изоэл бласти выть исполь- специалитвах обравумерного ние обьема тение относится к о ой техники и может б сокопроизводительны х машинах и устрой лов для вычисления Иэобре числительн зовано в вы зированны ботки сигна ДПФ.Цель из оборудован ного нныи овые сокрдщ обретия. ого На фиг.1 приведена структурустройства для вычисления двДПФ; на фиг,2 - организация ввыходного потоков устройства;организация входного и выходноустройства для=т = Р = С = 3;функциональная схема операциока первого типа; на фиг,5 - функцсхема операционного блока втона фиг.6 - схема первого блока в ип4 ход зел затор тов ГОСУЛАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ная схемаумерного ходного и на фиг,3 - го потоков на фиг,4 - нного блоиональная рого типа;вода (К = ) бретения - сокращение обьема оборудования, Поставленная цель достигается тем, что устройство содержит Р операционных блоков первого типа, Р операционных блоков второго типа, гре Р - размерность входной матрицы Х (Р,С), и три блока ввода, причем операционный блок первого типа содержит умножитель, сумматор; два регистра, два триггера, узел задержки натактов, где- размерность выходной выходной матрицы У (, т), две группы элементов И, группу элементов ИЛИ, элемент И и элемент НЕ, а операционный блок второго типа содержит умножитель, сумматор, два регистра, узел задержки на С тактов, два триггера, четыре группы элементов И, две группы элементов ИЛИ, элемент И и емент НЕ, 7 ил. и второго блока ввода (К = т); на фиг.7 - стретьего блока ввода,Устройство для вычисления двумерДПФ (фиг.1) содержит группу информонных входов 1( = 1,Р), информациовход 2, первый-четвертый 3(-34 тактвходы, синхровход 6, первый-третийблоки ввода, операционные блоки пертипа 101( = 1,Р), операционные блоки вго типа 11 = 1,Р) и выход 12.Операционный блок 10 первого(фиг.4) содержит пеГвый 13, второйтретий 15 информационные входы, пе16 и второй 17 тактовые входы, синхро18, первый 19 и второй 20 регистры,задержки натактов 21, регистры узлдержки 22( = 1,), умножитель 23, сумм24, первую 25 и вторую 26 группы элемеИ, группу элементов ИЛИ 27, первыйгеры 53 и 54 устанавливаются в единичйоесостояние, Во втором режиме на входы 38 и39 подаются соответственно единичный инулевой сигналы, на вход 37 подается элемент Х 1. При этом запись в регистр 41 запрещается (в регистре хранится элемент в),через группу элементов И 47 и группу элементов ИЛИ 51 в регистр 441 записываетсяэлемент х 1, в регистры 42 и 442 записывается элемент Х " Ь (триггер 53 находится в 10" единичном состояни 1, группа элементов И49 открыта, через нее и группу элементовИЛИ 52 обеспечивается подача элементах на информационный вход регистра 42), Навыходе умножителя 45 формируется значение х в, а на выходе сумматора 46 - значение Ь 1 - Ь в+ х 1, В третьем режимеработы на входы 38 и 39 подаются соответственно нулевой. и единичный сигналы, навход 36 подается элемент в 1, При этом в 20регистр 41. записывается элемент в (элемент И 55 открыт и разрешается запись врегистр 41), через группу элементов И 50 игруппу элементов ИЛИ 52 в регистр 42 записыьается значение Ь 1, на выходе элемента НЕ 56 формируется единичный сигнал,который открывает группу элементов И 48 ичерез группу элементов ИЛИ 51 обеспечивается циклическая запись элементов х 1; из44 я-го регистра в 44 ч+1-й регистр. В четвертом режиме работы на входы 38 и 39 подаются нулевые сигналы, в регистре 41хранится элемент в 1, группа элементов И48 открывается и обеспечивается циклическая запись элементов х из 44 ч-го регистра 35в 44 ч+1-й регистр. Если на предыдущем такте триггер 54 находится в единичном состоянии, то открыта группа элементов И 49,через которую в регистр 42 записываетсяэлемент хк = Ь. Если триггер 54 находится .40в нулевом состоянии, то открыта группаэлементов И 50, через которую в регистр42 записывается значение Ьк = Ь, котороесформировано на выходе сумматора 46 напредыдущем такте. При этом на выходе 45сумматора 46 формируется значение Ь в 1 ++х 1,Рассмотрим работу первого 7 блокаввода (фиг.б). При подаче на вход 62 нулевого сигнала /3 группы элементов И 67 к(К=Г) 50закрываются и на вторые входы групп элементов ИЛИ ббк(К = 1,) подаются нулевыезначения, на первые входы которых подаются соответствующие коэффициенты в, которые записываются в соответствующие 55регистры 65 к(К = 1,) при наличии на входе63 единичного сигнала (элемент И 68 открывается и тактовый импульс подается на синхровходы всех регистров 65 к). При йодаче на вход 62 единичного сигнала 3 группыэлеентов И 67 к(К - 1 Я открываются, навходы 61 г подаются нулевые значения, навход 63 подается последовательность единичных управляющих сигналов ос О-го такта по (О+ - 1)-й такты, на выход 69 подаютсясоответствующие коэффициенты в с О-го1такта по (О+ - 1)-й такты (фиг.2) и блок ввода7 за счет обратной связи, соединяющей регистр 651 и группу элементов И 67 К, работает в режиме кольцевого счетчика.Второй блок ввода 8 (К = т) работаетаналогично. В регистры 65 К(К = 1, т) при8 = 0 "предварительно записываются соответствующие коэффицие ты в,На вход 63 подаются единичные управляющие сигналы а в моменты О, О, 2 О;(т - 1)О, которые открывают элемент И 68и в эти же моменты времени на выход 69подаются соответствующие коэффициентыв, (фиг,б),Третий блок ввода 9 работает следующим образом (фиг,7), На входы 70( = 1,Р)подаются соответствующие элементы хаявходной матрицы Х в моменты времени 1 (одновременно подаются элементы о-гостолбца матрицы Х), которые задерживаются элементами задержки 71 на (Р-) тактови подаются на соответствующие выходы 73 ьОрганизация элементов входной матрицыХ на выходе блока ввода 9 приведена нафиг.2,Рассмотрим работу устройства для =т= Р = О = 3 (фиг,2). Входной и выходной поток данных приведен на фиг,2 и 3,где в обозначении а индекс 1 указываетномер такта работы устройства, На вход 2 .постоянно подается нулевое значение. Рассмотрим работу устройства при формировании элемента 111. На нулевом такте на вход1 з устройства и вход 36 операционного блока 11 з подаются соответст,венно элемейтых 22 и вз 0, на входы Зз и 34 - единичныесигналы, В операционный блок 11 з в регистры 41 и 44 записываеются соответственноэлементы вз 0 и юг = Ь(0,2,0). На первом тактена вход 1 з подается х 21, на входы Зз и 34 -соответственно единичный и нулевой сигналы. В операционном блоке 11 з формируется значение Ь(0,2,1) - Ь(0,2,0) щз++х 21, На втором тагте га вход 1 з подаетсяэлемент х 20, на входы Зз и 34 - соответственно единичный и нулевой сигналы. Воперационном блоке 11 з формируется значение Ьаг = Ь(0,2,2) = Ь(0,2,1) са+ хна, которое подается на третий информационныйвход 15 оперативного блока 10 з, На третьемтакте на вход 13 операционного блока 10 зподается элемент вз . В операционном21751778 8 15 20 25 30 35 40 50 55 блоке 10 з формируется значение У(2,0,0)- У(2,0,-1) вз. + Ьог, которое подается на вход 14 операционного блока 10 г. На четвертом такте в операционном блоке 10 гг формируется значение У(2,0,1) = У(2,0,0) вз Ьо 1, которое подается на вход 14 операционного блока 101. На пятом такте в операционном блоке 10 формируется значение УгоУ(2,0,2) - -У(2,0, 1) озг+ Ьоо,Аналогичным образом формируются остальные элементы Уц, Время вычисления двумерного ДПФ предлагаемым устройством составляетт+ Р + О - 2 тактов, а при=т=Р-О-М равной +2 И - 2гтактов. Например, для й = 3 устройство реализует вычисление двумерного ДПФ за 13 тактов. Формула изобретения Устройство для вычисления двумерного дискретного преобразования Фурье, содержащее Р операционных блоков первого типа, где Р - размерность входной матрицы Х Р,О 1, и Р операционных блоков второго типа, причем операционный блок первого типа содержит два регистра, умножитель и сумматор, а операционный блок второго типа - регистр, умножитель и сумматор, о тл ич а ю ще е с я тем, что. с целью сокращения объема оборудования, оно содержит три блока ввода, каждый операционный блок первого типа содержит узел задержки, две группы элементов И, группу элементов ИЛИ, двэ триггера, элемент И и элемент НЕ, каждый операционный блок второго типа - узел задержки, регистр, два триггера, четыре группы элементов И, две группы элемен.тов ИЛИ, элемент И и элемент НЕ, причем первый и второй тактовые входы устройства подключены соответственно к первому и второму тактовым входам первого и второго. блоков ввода, выходы которых подключены соответственно к первыминформационным входам Р - х операционных блоков первого и второго типа, информационный вход устройства подключен к второму информаци. онному входу Р-го операционного блока первого типа, первый и второй тактовые входы группы устройства - соответственно . к первому и второму тактовым входам Р-го операционного блока первого типа, третий и четвертый тактовые входы группы устройства - соответственно к первому й второму тактовым входам Р-го операционного блока второго типа, 1-й вход группы информационных входов устройства подключен к -му информационному входу третьего блока ввода, -й выход которого подключен к второму информационному входу -го операционного блока второго типа, синхровход устройства подключен к синхровходам всех операционных блоков первого и второго типа устройства, первый и второй информационные входы -го операционного блока первого типа О - 1,Р) подключены соответственно к первомуи второму информационным выходам 0+1)-го" операционного блока первого типа, первый информационный вход 1-го операционного блока второго типа подключен к первому информационному входу +1)-го операционного блока второго типа,. первый и второй тактовые входы -го операционного блока первого типа ( - 1,Р) подключены соответственно к первому и второму тактовым входам (+1)-го операционного блока первого типа, первый и второй тактовые входы -го операционного блока второго типа ( = 1,Р) подключены соответственно к первому и второму тактовым выходам (+1)-го операционного блока второго типа, второй информационный выход 1-го операционного блока второго типа подключен к третьему информационному входу 1-го операционного блока первого типа, второй информационный выход первого операционного блока первого типа подключен к выходу устройства, причем в операционном блоке первого типа первый информационный вход подключен к первым входам элементов И первой группы, вторые входы которых соединены с информационным входом первого триггера и подключены к первому управляющему входу операционного блока первого типа, а выходы элементов И первой группы соответственно подключены к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, а выходы - к соответствующим информационным входам узла задержки, первый информационный выход которого подключен к первому входу умножителя и к первому информаци онному выходу операционного блока первого типа, а второй информационный выход - к первым входам элементов И второй группы, вторые входы которых подключены к выходу элемента НЕ, вход которого пбдключен к первому тактовому входу оперэционного блока первого типа, второй информационный вход которого подключен к информационному входу первого регистра, вйход которого подключен к второму входу умножителя, выход которого подключен к первому входу сумматора, выход которого подключен к второму информационному выходу операционного блока первого типа, третий информационный вход которого подключен к информационному входу второго-7,Я регистра, выход которого подключен к второму входу сумматора, первый вход элемента И соединен с информационным входом второго триггера и подключен к второмутактовому входу операционного блока первого типа, выходы первого и второго триггеров подключены соответственно к первому и второму тактовым выходам операционного блока первого типа, синхровход которого подключен к синхровходам первого регистра, узла задержки, первого и второго триггеров и второму входу элемента И, при этом . в операционном блоке второго типа первый информационный вход подключен к информационному входу первого регистра, выход которого подключен к первому входу умно- жителя и к первому информационному выходу операционного блока второго типа; второй информационный вход которого подключен к первым входам элементов И первой группы, вторые входы которых соединены с входом элемента НЕ, информацион ным входом первого триггера и подключены к первому тактовому входу операционного блока второго типа, а выходы элементов И первой группы под.ключены к первым входам соответствующих элементов ИЛИ первой группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, а выходы - к информационным входам узла задержки на О тактов, первый информационный выход которого подключен к первым входам элементов И третьей группы и к первому входу сумматора, а второй информационный выход - к пеовым входам элементов И второй группы, вторые входы которых подключены 5 к выходу элемента НЕ, второй вход умножителя подключен к выходу второго регистра, информационный вход которого поразрядно подключен к выходам элементов ИЛИ второй группы; первые входыкоторых под ключены к выходам соответствующих эле. ментов И третьей группы, а вторые входы -к выходам соответствующих элементов И четвертой группы, первые входы которых подключены к инверсному выходу второго 15 триггера, а вторые входы - к второму информационному выходу операционного блока второго типа и к выходу сумматора, второй вход которого подключен к выходу умножителя, второй тактовый вход операционного 20 блока второго типа подключен к первомувходу элемента И и к информационному входу второго триггера, прямой выход которого подключен к второму тактовому выходу операционного блока второго типа и к вторым 25 входам элементов И третьей группы, прямой выход первого триггера подключен к первому тактовому выходу операционного блока второго типа, выход элемента И - к тактовому входу первого регистра, синхров ход операционного блока второго типа. - ксинхровходам второго регистра, узла задержки, первого и второго триггеров и к второму входу элемента И.Ъ цСО ОЗ фф 4 МО3 ес Ф 9 Ц о М3 о О О1751778 Составитель В. Якушехред М.Моргентал О, Спесивых Корректор ВЯетра едак Подписноеитета по изобретениям и открытиям при ГКНТ ССква, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 М)фЧф аказ 2693 ВНИИПИ Госуда Тиренного13035, М фФ я "5 ф