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

выходу дешифратора, выход умножителя комплексных чисел подключен к информационному входу узла буферной памяти, а вход синхронизации накапливающего сумматора подключен к выходу элемента И арифметического блока, первый и второй входы умножителя комплексных чисел арифметического блока подключены к информационным выходам соответственно блока памяти и блока постоянной памяти, второй выход синхронизатора подключен к

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

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ, содержащее блок постоянной памяти, арифметический блок, блок памяти, адресный вход которого подключен к информационным выходам первого и второго коммутаторов, управляющие входы которых соединены с первым входом сумматора и подключены к информационному выходу первого регистра сдвига, регистр, информационный выход которого подключен к второму входу сумматора, выход которого подключен к и{|формационному входу регистра, отличающееся тем, что, с целью повышения быстро- . действия устройства, в него введены счётчик адреса, элемент И, второй регистр сдвига и синхронизатор, первый выход которого подключен к счетному входу счетчика адреса, выход первого разряда которого подключен к первому информационному входу второго коммутатора и первому входу элемента И, выход которого подключен к управляющему входу второго регистра сдвигу; информационный выход которого подключен к адресному входу блока постоянной памяти, управляющий вход первого регистра сдвига подключен, к выходу старшего разряда счетчика адреса, выход третьего разряда которого подключен к входу синхронизации регистра, информационный вы- . ход которого подключен к информационному входу второго регистра сдвига, выход второго разряда счетчика адреса подключен к второму входу элемен(О та И и первому информационному входу первого коммутатора, второй информационный вход которого подключен поразрядно к выходам разрядов с (п +3) -го по I

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

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

Недостатком известного устройства является низкое быстродействие и большие аппаратурные затраты.

Наиболее близким по технической сущности к предлагаемому является устройство для реализации быстрого преобразования Фурье (БПФ), содержащее оперативную память, постоянную память, арифметический блок и блок управления, причем первый, второй и iтретий выходы блока управления соединены, соответственно, со входами постоянной памяти, арифметического блока и оперативной памяти, первая и вторая группы входов арифметического блока соединены, соответственно с группами выходов постоянной и оперативной памяти, блок управления содержит регистр, первую и вторую труп пы элементов И, первый и второй счетчики, сумматор, регистр хранения адреса и узел обращения кода адреса, причем первый и второй выходы узла задания режима соединены с первыми входами элементов И, соответственно, первой и второй группы, вто рые входы которых подключены к первому выходу регистра, второй и третий выходы которого подключены, соответственно, к первьм входам сумматора и узла задания режима, третий и четвертый выходы которого подключены, соответственно, ко входам первого и второго сч.етчиков, первые выходы которых соединены, соответственно, со вторым и третьим входами узла задания режима, пятый.выход подключен ко входу регистра, вторые выходы первого и второго счетчиков соединены с первыми входами, соответственно, первого и второго коммутаторов, вторые входы которых соединены с выходами элементов И, соответственно, первой и второй группы, выходы коммутаторов являются выходами устройства, выход сумматора соединен через узел обращения кода адреса с выходом устройства и через регистр хранения адреса со своим вторым входом L2J.

Однако известное устройство характеризуется низким быстродействием при вычислении двумерного БПФ за счет необходимости последовательного вычисления БПФ по строкам и столбцам.

Цель изобретения - повышение быстродействия (при вычислении думёрного БПФ за счет одновременного вычисления БПФ по строкам и столбцам).

Поставленная цель достигается тем что в устройство, содержащее блок постоянной памяти, арифметический блок, блок памяти, адресный вход которого подключен к информационным выходам первого и второго коммутаторов, управляющие входы которых соединены с первым входом сумматора и подключены к информационному выходу первого регистра сдвига, регистр, информационный выход которого подключен ко второму входу сумматора, выход которого подключен.к информационному входу регистра, введены счетчик адреса, элемент И, второй регистр сдвига и синхронизатор, первый выход которого подключен к счетному входу счетчика адреса, выход первого разряда которого подключен к первому информационному входу второго коммутатора и первому входу элемента И, выход которого подключен к управляющему входу второго регистра сдвига, информационный выход которого подключен к адресному входу блока постоянной памяти, управляющий вход первого регистра сдвига подключен к выходу старшего разряда счетчи ка адреса, выход третьего разряда которого подключен ко входу синхронизации регистра, информационный выход которого подключен к информацион ному входу второго регистра сдвига, выход второго разряда счетчика адреса йодключен ко второму входу элемента И и первому информационному входу первого коммутатора, второй информационный вход которого подключен поразрядно к выходам разрядов с (п+3)-го по (2п+1)-ый (п - число ите раций) счет.чика адреса, выходы разрядов с 4 по (п+2)-й которого поразрядно подключены ко второму информационному входу второго коммутатора, причем арифметический блок содержит умножитель комплексных чисел, узел буферной памяти, накапливающий сумматор, коммутатор, депшфратор, элемент И и счетчик, информационный выход которого подключен ко входу дешифратора, установочному входу накапливающего сумматора и первому информационному входу коммутатора, информационный выход которого подключен к адресному входу узла буферной памяти, информационный выход которого подключен к информационному входу накапливающего сумматора, вход управ ления знаком которого подключен к выходу дешифратора, выход умножителя комплексных чисел подключен к информационному входу узла буферной памяти, а вход синхронизации накапливающего сумматора подключен к выходу 1 54 элемента И арифметического блока, первый и второй входы умножителя комплексных чисел арифметического блока подключены к информационным выходам соответственно блока памяти и блока постоянной памяти, второй выход синхронизатора подключен к счетному входу счетчика и первому входу элемента И арифметического блока, выходы первого, второго и третьего разрядов счетчика адреса подключены к установочному входу счетчика, управляющему и второму информационному входам коммутатора, входу дешифратора и второму входу элемента И арифметического блока, выход накапливающего сумматора которого подключен к Информационному входу блока памяти. Предлагаемое устройство позволяетвыполнить вычисление БПФ двумерного массива размерностью N«N за п итераций (где ), что вдвое меньше по сравнению с прототипом. На фиг. 1 приведена структурная схема предпагаемого устройства; на фиг. 2 - приведе11а функциональная схема арифметического блока; на фиг. 3 - временные диаграммы синхронизатора. Устройство для реализации двумер- . ного быстрого преобразования Фурье (фиг. 1) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 постояннойпамяти кЪэффициентов, празрядные коммутаторы 4 и 5,п-разрядный регистр 6 сдвига,(п-1)-разрядный итерационный регистр 7 сдвига ,(2п+1)разрядный счетчик 8 адреса, элемент И 9, (п-1)-разрядный регистр 10 хранения, (п-1)-разрядный сумматор 11, синхронизатор 12. Арифметический блок 2 (фиг. 2) содержит умножитель 13 комплексных чисел, узел 14 буферной памяти, накапливающий сумматор 15, коммутатор (на два канала) 16, дешифратор 17 знака, счетчик 18, элемент И 19. Частота импульсов, поступающих на вход ХЗ арифметического блока с выхода синхронизатора 12, в четьфе раза выше частоты импульсов, поступающих на счетный вход счетчика 8 с другого выхода синхронизатора 12. На информационные входы коммутатора поданы потенциалы логических О и 1 таким образом, чтобы получить на выходе серию импульсов 0000001101010110 с частотой, равной частоте импульсов на выходе первого разряда счетчика 18. В предлагаемом устройстве реализован безызбыточный алгоритм одновременного ВЕЛчисления БПФ по строкам и столбцам двумерного массива с замещением и прореживанием по времени. Устройство работает следующим образом. Исходный массив размерностью N-N занесен в блок 1 оперативной памяти в двоично-инверсном порядке как по строкам, так и по столбцам. В исходном состоянии регистр 6 сдвига, регистр 10 хранения, счетчик 8, счетчик 18 и накапливающий сумматор 15 обнулены, во все разряды итерационного регистра 7 сдвига занесена логическая 1. На счетный вход адресного счетчика 8 с первого выхода синхронизатора 12 поступают тактовые импульсы, по которым (2п+1)-разрядный счетчик 8 на выходах формирует последователь ные коды, которые поступают на инфор мационные входы первого и второго коммутаторов 4 и 5. На выходе первого коммутатора 4 формируются адреса записи-считывания операндов из блока оперативной памяти по строкам,на выход второго коммутатора 5 - по столбцам Фор1 рование адресов экспоненциальных множителей на выходе регистр 10 хранения осуществляется по импул сам с выхода третьего разряда счетч ка 8 с помощью регистра 10 хранения аналогично прототипу. Вьтолнение итераций БПФ в предла гаемом устройстве заключается в последовательном повторении элементар ного цикла вида . x +X2W+x x j+XjW-XjW-x W ; X;,-XjW+XjW-x W x -XjW-XjW+x W, Где X,,, Xji, Xj, х - соответственно, первый, второй, третий, четвертый операнды, извлекаемые из .бло ка 1 оперативной памяти; W - экспоненциальный множитель, извлекаемый из блока 3 постоянной памяти коэффи циентов . При выполнении калдого элементар ного цикла в накапливающем сумматор 15 необходимо производить операцию суммирования со следую11р1ми .знаками: + + + + + + - + --+. поэтому на выходе дешифратора 17 знака формируется последовательность управляющих импульсов,: 0000001 1010101 10. Каждый элементарный цикл в арифметическом блоке 2 выполняется следующим образом. По низкому уровню импульса записисчитьшания с выхода третьего разряда счетчика 8 из блока 1 оперативной памяти производится последовательное считывание четырех операндов, умножение их на соответствующие экспоненциальные множители (первый-операнд умножается на единицу) и занесение полученных произведений в узел 14 буферной памяти по адресам, сформированным на выходе коммутатора 16 на два канала. По высокому уровню импульса записи-считьшания с выхода третьего разряда счетчика 8, в соответствии с импульсами управления знаком суммирования с выхода дешифратора 17 знака, в накапливающем сумматоре 15 производится первое суммирование четьфех произведений, извлеченных из узла 14 буферной памяти,и занесение полученной суммы на место извлеченного ранее из блока 1 оперативной памяти первого операнда; затем производится второе суммирование и занесение в блок 1 оперативной памяти, а затем - третье и четвертое. Возведение в квадрат экспоненциального мнояятеля в предлагаемом устройстве осуществляется с помощью регистра 6 сдвига следующим образом. Экспоненциальный множитель в общем виде записывается ««.f( где k - номер множителя,возведение экспоненциального множителя в квадрат равноценно удваиванию его номера, а следовательно, и удваиванию его адреса. Адрес экспоненциального множителя, сформированный на выходе регистра 10 хранения, заносится в п-разрядный регистр 6 сдвига так, что п-й разряд остается свободным, и если на вход регистра 6 сдвига с выхода элемента И 9 импульс удваивания не поступил, то адрес не удваивается и неизменным подается на адресный вход блока 3 постоянной памяти коэффициентов. При поступлений на вход регистра 6 сдвига импульса удваивания с выхода элемента И 9 происходит сдвиг адреса, занесенного в регистр 6 сдвига на один разряд в сторону старших разрядов. Импульс удваивания формируется на выходе элемента И 9 при совпадении уровней на выходах первого и вто рого разрядов счетчика 8, т.е. для каждого четвертого операнда, извлекаемого из блока 1 оперативной памяти. , После окончания каждого элементарного цикла итерации мерного БПФ сигналом перехода из состояния логической 1 в О старшего счетчика 11

Ри,/ 58 18 накапливающий сумматор 15 обнуляется. После окончания первой итерации сигналом перехода из состояния логической 1 в О старшего разряда счетчика 8 в итерационном регистре 7 сдвига происходит сдвиг информации в сторону младших разрядов с занесением логического О в старший разряд и устройство начинает вычисление новой итерации. Таким образом, предлагаемое устройство позволяет повысить быстродействие вычисления двумерного БПФ за счет одновременного вычисления БПФ по строкам и столбцам. ШШЛnnnn nnnn rninn nnnn nniin

ХЗ хч Фг/г. 2 jinflfL jumn

Фиг.З nnnn nnnn ШШЛnnnn-