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

) С 06 Р 15/33 ЕТЕНИЯ К янд ско-тех- проиэ- ударст- Ленина стема голо ом вреия",2. АвторскВ 809198, кл.(прототип); тво ССС 2, 1979 свидетел06 Р 15 о информационныйчен к адресномупамяти, информаго подключен кнакапливающеголения знаком ко орого подкл ла буферной ыход которо входу Ъционный нформац иному входу вход управключгн к умматораорого под ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТЮ САНИЕ ИЗОБ ТОРСИОМУ СВИДЕТЕЛЬСТВ(71) Специальное конструкторнологическое бюро с опытнымводством при Белорусском госвенном университете им. В.И(56) 1, Аврорин А.В. и др. Сдля цифрового восстановленияфических изображений в реальмени эксперимента. - "Автомет1978, В 4.(54) (57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯФУРЬЕ, содержащее блок постояннойпамяти, арифметический блок, блокпамяти, адресный вход которого подключен к информационным выходам первого и второго коммутаторов, управляющие входы .которых соединены с первым входом сумматора и подключенык информационному выходу первого регистра сдвига, регистр, информационный выход которого подключен к второму входу сумматора, выход которогоподключен к информационному входурегистра, о т л и ч а ю щ е е с ятем, что, с целью повышения быстро- .действия устройства, в него введенысчетчик адреса, элемент И, второйрегистр сдвига и синхронизатор, первый выход которого подключен к счетному входу счетчика адреса, выход первого разряда которого подключенк первому информационному входу второго коммутатора и первому входу элемента И, выход которого подключен куправляющему входу второго регистрасдвига, информационный выход которого подключен к адресному входу блока постоянной памяти, управляющийвход первого регистра сдвига подключен,к выходу старшего разряда счетчика адреса, .выход третьего разрядакоторого подключен к входу синхронизации регистра, информационный выход которого подключен к информационному входу второго регистра сдвига,выход второго разряда счетчика ад еР са подключен к второму входу элемента И и первому информационному входу первого коммутатора, второй информа ционный вход которого подключен поразрядно к выходам разрядов с(п+3)-го по, (21+1) -ый( ь - число итераций) счетчика фаЮ адреса, выходы разрядов с 4 по(+2) -й вевь которого йораэрядно подключены к вт ф рому информационному входу второго фф коммутатора, причем арифмегический блок содержит умножитель комплексных чисел, узел буферной памяти, накапливающий сумматор, коммутатор, дешифратор, элемент И и счетчик, информационный выход которого подключен к ,входу дешифратора установочному входу накапливающего сумматора и первому информационному входу коммутатора,выход кот1142845 выходу дешифратора, выход умножителя комплексных чисел подключен к информационному входу узла буфернойпамяти, а вход синхронизации накапливающего сумматора подключен к выходу элемента И арифметического блока, первый и второй входы умножителя комплексных чисел арифметическогоблока подключены к информационнымвыходам соответственно блока памятии блока постоянной памяти, второйвыход синхронизатора подключен к Изобретение относится к вычислительной технике и может быть исполь-зовано для обработки двумерных сигналов, в частности для цифровой обработки изображений и пространственновременной обработки,Известно устройство, содержащееарифметический блок, блок комплексных тригонометрических констант,блок сверхоперативной памяти, блок 10прямого доступа 13Недостатком известного устройства является низкое быстродействиеи большие аппаратурные затраты.Наиболее близким по технической 15сущности к предлагаемому является. устройство для реализации быстрогопреобразования Фурье (БПФ), содержащее оперативную память, постояннуюпамять, арифметический блок и блок 2 руправления, причем первый, второй итретий выходы блока управления соединены, соответственно, со входамипостоянной памяти, арифметическогоблока и оперативной памяти, первая 25и вторая группы входов арифметического блока соединены, соответственно,с группами выходов постоянной и оперативной памяти, блок управления содержит регистр, первую и вторую груп- щпы элементов И, первый и второй счет,чики, сумматор, регистр храненияадреса и узел обращения кода адреса, причем первый и второй выходы узла задания. режима соединены спервыми входами элементов И, соответственно, первой и второй группы, вторые входы которых подключены к перво-.: счетному входу счетчика и первомувходу элемента И арифметическогоблока, выходы первого, второго и третьего разрядов счетчика адреса подключены к установочному входу счетчика, управляющему и второму информационному входам коммутатора, входудешифратора и второму входу элемента И арифметического блока, выходнакапливающего сумматора которогоподключен к информационному входублока памяти. 3му выходу регистра, второй и третий выходы которого подключены, соответственно, к первым входам сумматора и узла задания режима, третий и четвертый выходы которого подключены, соответственно, ко входам первого и второго счетчиков, первые выходы которых соединены, соответственно, со вторым и третьим входами узла задания режима, пятый выход подключен ко входу региСтра, вторые выходы первого и второго счетчиков соединены с первыми входами, соответственно, первого и второго коммутаторов, вторые входы которых соединены с выходами элементов И, соответственно, первой и второй группы, выходы коммутаторов являются выходами устройства, выход сумматора соединен через узел обращения кода адреса с выходом устройства и через регистр хранения адреса со своим вторым входом 2,Однако известное устройство характеризуется низким быстродействием при вычислении двумерного БПФ за счет необходимости последовательного вычисления БПФ по строкам и столбцам.Цель изобретения - повышение быстродействия (при вычислении думерного БПФ за счет одновременного вычисления БПФ по строкам и столбцам).Поставленная цель достигается тем, что в устройство, содержащее блок постоянной памяти, арифметический блок, блок памяти, адресный вход которого подключен к информационным выходам первого и второго коммутато1142845 3ров, управляющие входы которых соединены с первым входом сумматора и подключены к информационному выходу первого регистра сдвига, регистр, информационный выход которого под ключен ко второму входу сумматора, выход которого подключен к информационному входу регистра, введены счетчик адреса,. элемент И, второй регистр сдвига и синхронизатор, пер вый выход которого подключен к счетному входу счетчика адреса, выход первого разряда которого подключен к первому информационному входу второго коммутатора и первому входу эле мента И, выход которого подключен к управляющему входу второго регистра сдвига, информационный выход которо- го подключен к адресному входу блока постоянной памяти, управляющий 20 вход первого регистра сдвига подключен к выходу старшего разряда счетчика адреса, выход третьего разряда которого подключен ко входу синхронизации регистра, информационный вы ход которого подключен к информационному входу второго регистра сдвига, выход второго разряда счетчика адреса подключен ко второму входу элемента И и первому информационному 30 входу первого коммутатора, второй информационный вход которого подключен поразрядно к выходам разрядов с (и+3)-го по (2 п+1)-ый (и - число итераций) счетчика адреса, выходы раз" рядов с 4 по (и+2)-й которого поразрядно подключены ко второму информационному входу второго коммутатора, причем арифметический блок содержит умножитель комплексных чисел, узел 40 буферной памяти, накапливающий сумматор, коммутатор, дешифратор, элемент И и счетчик, информационный выход которого подключен ко входу дешифратора, установочному входу на капливающего сумматора и первому информационному входу коммутатора, информационный выход которого подключен к адресному входу узла буферной памяти, информационный выход которо го подключен к информационному входу накапливающего сумматора, вход управления знаком которого подключен к выходу дешифратора, выход умножителя комплексных чисел подключен .к инфор мационному входу узла буферной памяти, а вход синхронизации накапливающего сумматора подключен к выходу элемента И арифметического блока, первый и второй входы умножителя комплексных чисел арифметического блока подключены к информационным выходам соответственно блока памяти и блока постоянной памяти, второй выход синхронизатора подключен к счетному входу счетчика и первому входу элемента И арифметического блока, выходы первого, второго и третьего разрядов счетчика адреса подключены к установочному входу счетчика, управляющему и второму информационному входам коммутатора, входу дешифратора и второму входу элемента И арифметического блока, выход накапливающего сумматора которого подключен к Информационному входу блока памяти.Предлагаемое устройство позволяет выполнить вычисление БПФ двумерного массива размерностью Ж И за и итераций (где п=1 од М), что вдвое меньше по сравнению с прототипом.На фиг. 1 привецена структурная схема предлагаемого устройства; на фиг. 2 - приведена функциональная схема арифметического блока; на фиг, 3 - временные диаграммы синхронизатора.Устройство для реализации двумер- . ного быстрого преобразования Фурье (фиг. 1) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 постоянной памяти коэффициентов, и- разрядные коммутаторы 4 и 5,п-разрядный регистр 6 сдвига,(п)-разрядный итерационный регистр 7 сдвига,(2 п+1)- разрядный счетчик 8 адреса,.элемент И 9, (и)-разрядный регистр 10 хранения, (и)-разрядный сумматор 11, синхронизатор 12.Арифметический блок 2 (фиг. 2) содержит умножитель 13 комплексных чисел, узел 14 буферной памяти, накапливающий сумматор 15, коммутатор (на два канала) 16, дешифратор .17 знака, счетчик 18, элемент И 19.Частота импульсов, поступающих на вход ХЗ арифметического блока с выхода синхронизатора 12, в четыре раза выше частоты импульсов, поступающих на счетный вход счетчика 8 с другого выхода синхронизатора 12.На информационные входы коммутатора поданы г.отенциалы логических "0" и "1" таким образом, чтобы полу" чить на выходе серию импульсов0000001101010110 с частотой, равнойчастоте импульсов на выходе первогоразряда счетчика 18.В предлагаемом устройстве реализован безызбыточный алгоритм одковременного вычисления БПФ по строками столбцам двумерного массива с замещением и прореживанием по времени.,Устройство работает следующим об 10разом.Исходный массив размерностью Н Хзанесен в блок 1 оперативной памятив двоично-инверсном порядке как построкам, так и по столбцам.В исходном состоянии регистр 615сдвига, регистр 10 хранения, счетчик 8, счетчик 18 и накапливающийсумматор 15 обнулены, во все разряды итерационного регистра 7 сдвигазанесена логическая "1",На счетный вход адресного счетчика 8 с первого выхода синхронизатора 12 поступают тактовые импульсы,по которым (2 п+1)-разрядный счетчик8 на выходах формирует последователь 25ные коды, которые поступают на информационные входы первого и второгокоммутаторов 4 и 5, На выходе первого коммутатора 4 формируются адресазаписи-считывания операндов из блока 1 О30оперативной памяти по строкам,на выходе, второго коммутатора 5 - по столбцам.Формирование адресов экспоненциальных множителей на выходе регистра10 хранения осуществляется по импуль сам с выхода третьего разряда счетчика 8 с помощью регистра 10 храненияаналогично прототипу.Выполнение итераций БПФ в предлагаемом устройстве заключается в по фследовательном повторении элементарного цикла видах +хУ+х ьь+хМ ьх+хЯ-хИ-х 4 ьх,-х И+хУ-х и45Где хь х, хь х, - соответственно, первый, второй, третий, четвертый операнды, извлекаемые из блока 1 оперативной памяти; И - экспоненциальный множитель, извлекаемыйиз блока 3 постоянной памяти коэффициентов.При выполнении каждого элементарного цикла в накапливающем сумматоре 55 15 необходимо производить операцию суммирования со следующими .знаками:+ + + +ь поэтому на выходе дешифратора17 знака формируется последовательность управляющих импульсов;0000001 10101 01 10.Каждый элементарный цикл в арифметическом блоке 2 выполняется следующим образом.По низкому уровню импульса записисчитывания с выхода третьего разрядасчетчика 8 из блока 1 оперативной памяти производится последовательноесчитывание четырех операндов, умножение их на соответствующие экспоненцнальные множители (первый операндумножается на единицу) и занесениеполученных произведений в узел 14буферной памяти по адресам, сформированным на выходе коммутатора 16на два канала.По высокому уровню импульса записи-считывания с выхода третьего разряда счетчика 8, в соответствии симпульсами управления знаком суммирования с выхода дешифратора 17 знака,в накапливающем сумматоре 15 производится первое суммирование четырехпроизведений, извлеченных иэ узла 14буферной памяти,и занесение полученкой суммы на место извлеченного ранееиз блока 1 оперативной памяти первого операнда; затем производится второе суммирование и занесение в блок1 оперативной памяти, а затем - третье и четвертое,Возведение в квадрат экспоненциального множителя в предлагаемомустройстве осуществляется с помощьюрегистра 6 сдвига следующим образом.Экспоненциальный множитель в общем виде записываетсяЖфекР 1где 1 с " номер множителя, возведение экспоненциального множителя в квадрат равноценно удваиванию его номера, а следовательно, и удваиванию его адреса.Адрес экспоненциального множителя, сформированный на выходе регистра 10 хранения, заносится в и-разрядный регистр б сдвига так, что и-й разряд остается свободным, и если на вход регистра 6 сдвига с выхода элемента И 9 импульс удваивания не поступил, то адрес не удваивается и неизменным подается на адресный вход блока 3постоянной памяти коэффициентов. Припоступлении на вход регистра 6 сдвига импульса удваивания с выхода элемента И 9 происходит сдвиг адреса,занесенного в регистр 6 сдвига на . 5один разряд в сторону старших разрядов. Импульс удваивания формируетсяна выходе элемента И 9 при совпадении уровней на выходах первого и второго разрядов счетчика 8, т.е. для 1 фкаждого четвертого операнда, извлекаемого из блока 1 оперативной памяти,После окончания каждого элементарного цикла итерации мерного БПФсигналом перехода из состояния логической "1" в "О" старшего счетчика 18 накапливающий сумматор 15 обнуляется.После окончания первой итерации сигналом перехода из состояния логической "1" в "О" старшего разряда счетчика 8 в итерационном регистре 7 сдвига происходит сдвиг информации в сторону младших разрядов с занесением логического "0" в старший разряд и устройство начинает вычисление новой итерации. Таким образом, предлагаемое устройство позволяет повысить быстродействие вычисления двумерного БПФ за счет одновременного вычисления БПФ по строкам и столбцам.,Тимохина Техред С.Мигунова Реда аз 738/4 Тираж 110 Государственного комите елам изобретений и откры , Москва, Ж, Раушская одписно ССй;б.,д. 4/ 303 ород ул Проектная 4 Филиал ППП "Патент",рректор И.Самборская