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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН рц С 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТЮ (2 1) 3648205/24-24 (22) 10.08.83 (46) 28. 02. 85, Бюл. В 8 (72) А.Н.Карташевич, М.С.Курлянд и А.И.Ходосевич (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государственном университете им. В.И.Ленина (53) 681.32(088.8) (56) 1. Аврорин А.В. и др. Система для цифрового восстановления голографических изображений в реальном времени эксперимента. — "Автометрия", 1978, Ф 4.

2. Авторское свидетельство СССР

В 809198, кл. С 06 F 15/332, 1979 (прототип); (54) (57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ

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

„„Я0„„1142845 А первого разряда которого подключен к первому информационному входу вто- . рого коммутатора и первому входу элемента И, выход которого подключен к управляющему входу второго регистра сдвига, информационный выход которого подключен к адресному входу блока постоянной памяти, управляющий вход первого регистра сдвига подключен.к выходу старшего разряда счетчика адреса, .выход третьего разряда которого подключен к входу синхронизации регистра, информационный выход которого подключен к информационному входу второго регистра сдвига, выход второго разряда счетчика адреса подключен к второму входу элемента И и первому информационному входу первого коммутатора, второй информа ционный вход которого подключен пораз. рядно к выходам разрядов c(n+3)-го по, (2n+1) -ый(n — число итераций) счетчика leal адреса, выходы разрядов с 4 по(+2)-й фюий которого йораэрядно подключены к вто- ф рому информационному входу второго фф коммутатора, причем арифмегический блок содержит умножитель комплексных чисел, увел буферной памяти, накапливающий сумматор, коммутатор, дешифратор, элемент И и счетчик, информационный выход которого подключен к

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

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

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

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

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

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

3 му выходу регистра, второй и третий выходы которого подключены, соответственно, к первым входам сумматора и узла задания режима, третий и четвертый выходы которого подключены, соответственно, ко входам первого и второго счетчиков, первые выходы которых соединены, соответственно, со вторым и третьим входами узла задания режима, пятый выход подключен ко входу региСтра, вторые выходы первого и второго счетчиков соединены с первыми входами, соответственно, первого и второго коммутаторов, вторые входы которых соединены с выходами элементов И, соответственно, первой и второй группы, выходы коммутато- ров являются выходами устройства, выход сумматора соединен через узел обращения кода адреса с выходом устройства и через регистр хранения адреса со своим вторым входом (2).

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

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

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

Ю ров, управляющие входы которых соединены с первым входом сумматора и подключены к информационному выходу первого регистра сдвига, регистр, информационный выход которого подключен ко второму входу сумматора, выход которого подключен к информационному входу регистра, введены счетчик адреса,. элемент И, второй регистр сдвига и синхронизатор, пер- 10 вый выход которого подключен к счетному входу счетчика адреса, выход первого разряда которого подключен к первому информационному входу второго коммутатора и первому входу эле- 15 мента И, выход которого подключен к управляющему входу второго регистра сдвига, информационный выход которо- го подключен к адресному входу блока постоянной памяти, управляющий 20 вход первого регистра сдвига подключен к выходу старшего разряда счетчиica адреса, выход третьего разряда которого подключен ко входу синхронизации регистра, информационный вы- 25 ход которого подключен к информационному входу второго регистра сдвига, выход второго разряда счетчика адреса подключен ко второму входу элемента И и первому информационному 30 входу первого коммутатора, второй информационный вход которого подключен поразрядно к выходам разрядов с (п+3)-ro по (2п+1)-ый (и — число итераций) счетчика адреса, выходы раз" рядов с 4 по (n+2)-й которого поразрядно подключены ко второму информационному входу второго коммутатора, причем арифметический блок содержит умножитель комплексных чисел, узеп щ буферной памяти, накапливающий сумматор, коммутатор, дешифратор, элемент И и счетчик, информационный выход которого подключен ко входу дешифратора, установочному входу на- 4И капливающего сумматора и первому информационному входу коммутатора, информационный выход которого подключен к адресному входу узла буферной памяти, информационный выход которо- щ го подключен к информационному входу накапливающего сумматора, вход управления знаком которого подключен к выходу дешифратора, выход умножителя комплексных чисел подключен .к инфор- мационному входу узла буферной памяти, а вход синхронизации накапливаюmего сумматора подключен к выходу элемента И арифметического блока, первый и второй входы умножителя комплексных чисел арифметического блока подключены к информационным выходам соответственно блока памяти и блока постоянной памяти, второй выход синхронизатора подключен к счетному входу счетчика и первому входу элемента И арифметического блока, выходы первого, второго и третьего разрядов счетчика адреса подключены к установочному входу счетчика, управляющему и второму информационному входам коммутатора, входу дешифратора и второму входу элемента И арифметического блока, выход накапливающего сумматора которого подключен к Информационному входу блока памяти.

Предлагаемое устройство позволяет. выполнить вычисление БПФ двумерного массива размерностью N.N за и итераций (где n=log М), что вдвое меньше по сравнению с прототипом.

На фиг. 1 привецена структурная схема предлагаемого устройства; на фиг. 2 — приведена функциональная схема арифметического блока; на фиг. 3 — временные диаграммы синхронизатора.

Устройство для реализации двумер- . ного быстрого преобразования Фурье (фиг. 1) содержит блок 1 оперативной памяти, арифметический блок 2, блок

3 постоянной памяти коэффициентов, иразрядные коммутаторы 4 и 5,п-разрядный регистр 6 сдвига,(п-1)-разрядный итерационный регистр 7 сдвига,(2п+1)— разрядный счетчик 8 адреса,.элемент

И 9, (n-1)-разрядный регистр 10 хранения, (и-1)-разрядный сумматор 11, синхронизатор 12.

Арифметический блок 2 (фиг. 2) содержит умножитель 13 комплексных чисел, узел 14 буферной памяти, накапливающий сумматор 15, коммутатор (на два канала) 16, дешифратор .17 знака, счетчик 18, элемент И 19.

Частота импульсов, поступающих на вход:ХЗ арифметического блока с выхода синхронизатора 12, в четыре раза выше частоты импульсов, поступающих на счетный вход счетчика 8 с другого выхода синхронизатора 12.

На информационные входы коммутатора поданы г.отенциалы логических

"0" и "1" таким образом, чтобы получить на выходе серию импульсов

f142845

0000001101010110 с частотой, равной частоте импульсов на выходе первого разряда счетчика 18.

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

Устройство работает следующим об10 разом.

Исходный массив размерностью N N занесен в блок 1 оперативной памяти в двоично-инверсном порядке как по строкам, так и по столбцам.

В исходном состоянии регистр 6

15 сдвига, регистр 10 хранения, счетчик 8, счетчик 18 и накапливающий сумматор 15 обнулены, во все разряды итерационного регистра 7 сдвига занесена логическая "1".

На счетный вход адресного счетчика 8 с первого выхода синхронизатора 12 поступают тактовые импульсы, по которым (2n+1)-разрядный счетчик

8 на выходах формирует последователь25 ные коды, которые поступают на информационные входы первого и второго коммутаторов 4 и 5. На выходе первого коммутатора 4 формируются адреса записи-считывания операндов из блока 1 30 оперативной памяти по строкам,на выходе

-, второго коммутатора 5 — по столбцам.

Формирование адресов экспоненциальных множителей на выходе регистра

10 хранения осуществляется по импуль-35 сам с выхода третьего разряда счетчика 8 с помощью регистра 10 хранения аналогично прототипу.

Выполнение итераций БПФ в предлагаемом устройстве заключается в по- 411 следовательном повторении элементарного цикла видах +QM+x И+х М ь х +х й-х>М-х Ф; х -х И+х M-х и

4S

1 х1 хам хЭ11+х40 ь

Где х венно, первый, второй, третий, четвертый операнды, извлекаемые из блока 1 оперативной памяти; M — - экспоненциальный множитель, извлекаемый из блока 3 постоянной памяти коэффициентов.

При выполнении каждого элементарного цикла в накапливающем сумматоре 55

15 необходимо производить операцию суммирования со следующими .знаками:

++++++++++ь поэтому на выходе дешифратора

17 знака формируется последовательность управляющих импуlbcoB;

0000001101010110.

Каждый элементарный цикл в арифметическом блоке 2 выполняется следующим образом.

По низкому уровню импульса записисчитывания с выхода третьего разряда счетчика 8 из блока 1 оперативной памяти производится последовательное считывание четырех операндов, умножение их на соответствующие экспоненцнальные множители (первый. операнд умножается на единицу) и занесение полученных произведений в узел 14 буферной памяти по адресам, сформированным на выходе коммутатора 16 на два канала.

По высокому уровню импульса записи-считывания с выхода третьего разряда счетчика 8, в соответствии с импульсами управления знаком суммирования с выхода дешифратора 17 знака, в накапливающем сумматоре 15 производится первое суммирование четырех произведений, извлеченных иэ узла 14 буферной памяти,и занесение полученкой суммы на место извлеченного ранее из блока 1 оперативной памяти первого операнда; затем производится второе суммирование и занесение в блок

1 оперативной памяти, а затем — третье и четвертое.

Возведение в квадрат экспоненциального множителя в предлагаемом устройстве осуществляется с помощью регистра 6 сдвига следующим образом.

Экспоненциальный множитель в общем виде записывается где k " номер множителя, возведение экспоненциального множителя в квадрат равноценно удваиванию его номера, а следовательно, и удваиванию его адреса.

Адрес экспоненциального множителя, сформированный на выходе регистра 10 хранения, заносится в и-разрядный регистр б сдвига так, что и-й разряд остается свободным, и если на вход регистра 6 сдвига с выхода элемента

И 9 импульс удваивания не поступил, то адрес не удваивается и неизменным подается на адресный вход блока 3

1142845 постоянной памяти коэффициентов. При поступлении на вход регистра 6 сдвига импульса удваивания с выхода элемента И 9 происходит сдвиг адреса, занесенного в регистр 6 сдвига на . 5 один разряд в сторону старших разрядов. Импульс удваивания формируется на выходе элемента И 9 при совпадении уровней на выходах первого и второго разрядов счетчика 8, т.е. для каждого четвертого операнда, извлекаемого из блока 1 оперативной памяти.

После окончания каждого элементарного цикла итерации мерного БПФ сигналом перехода из состояния логической ™1" в "0" старшего счетчика

18 накапливающий сумматор 15 обнуляется.

После окончания первой итерации сигналом перехода из состояния логической 1 в 0 старшего разряда счетчика 8 в итерационном регистре

7 сдвига происходит сдвиг информации в сторону младших разрядов с занесением логического "0" в старший разряд и устройство начинает вычисление новой итерации.

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

2

3 ф

8

8

Составитель А.Баранов

Редактор С.Тимохина Техред С.Мигунова Еорректор М. Самборская

Заказ 738/42 Тираж 110 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r.ÓæãîÐîä, ул.Проектная, 4