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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ДВУХМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАТЕЛЯ ФУРЬЕ, содержащее блок памяти, информационный выход которого соединен с информационным входом арифметического блока, информационньш выход которого подключен к информационному входу блока памяти, адресный вход которого подключен к первому выходу блока управления, второй выход которого соединен с входом синхронизации арифметического блока, вход задания коэффициентов которого подключен к выходу блока постоянной .памяти, -адресный вход которого соединен с третьим выходом блока управления, о т личающ-ееся тем, что, с целью повьшения быстродействия, в-него введены первый, второй регистры сдвига и коммутатор, выход которого соединен с информационным входом первого регистра сдвига, информационный выход которого подключен к информационному входу арифметического блока, информационный выход которого соединен с информационным входом второго регистра сдвига и первым входом коммутатора, второй вход которого подключен к информационному выходу второго регистра сдвига, четвертьй выход блока управления соединен с управлянлцим вхо-. дом блока памяти, управляющим входом первого регистра сдвига и управляющим входом коммутатора, а пятый выход блока управления соединен с входами записи информации первого и второго регистров сдвига, причем блок управления содержит первый, второй, третий , четвертый и пятый коммутаторы, регистр, регистр итераций, группу (Л элементов И, первый, второй и третий, счетчики, триггер, дешифратор и генератор тактовых импульсов, первый выход которого является вторьм выходом блока управления, второй выход гене-, ратора тактовых импульсов соединен с первым входом дешифратора, первый О) выход которого соединен с входом NU первого разряда первого счетчика, информационный вькод которого подклю00 чен к первым входам элементов И группы и информационному входу регистра, выход младшего разряда которого сое- i динен с первым входом первого коммутатора , первый выход которого подключен к входу старшего разряда р.егист-1 ра,выход (т-п+1)-г9 разряда(т ц , М N - размер преобразования ) которого подключен к второму входу первого коммутатора, второй вы-, ход которого соединен с вторым входом, дешифратора, второй выход которого соединен с входом (hi-n-vl) -го раз

(r9) () 1)

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

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

РЕСПУБЛИК

4 is)) С 06 F 15/332

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (2 1) 3450597/18-24 (22) 11.06.82 (46). 30.06.85. Бюл. ¹ 24 (72) А.Н.Карташевич, В.В.Николаевский, А.А.Рябцев и А.И.Ходасевич (7 1) Научно-исследовательский институт прикладных физических проблем им.акад.А.Н.Севченко (53) 681. 32(088. 8) (56) 1. Аврорин А.В. и др. Система для цифрового восстановления голографических изображений в реальном времени эксперимента. — "Автометрия", 1978, № 4.

2. Авторское свидетельство СССР № 809198, кл. С 06 F 15/332, 1981 (прототип) ° (54) (57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

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

ФУРЪЕ, содержащее блок памяти, информационный выход которого соединен с информационным входом арифметического блока, информационный выход которого подключен к информационному входу блока памяти, адресный вход которого подключен к первому выходу блока управления, второй выход которого соединен с входом синхронизации арифметического блока, вход задания коэффициентов которого подключен к выходу блока постоянной .памяти, адресный вход которого соединен с тре" тьим выходом блока управления, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в- него введены первый, второй регистры сдви" га и коммутатор, выход которого соединен с информационным входом первого регистра сдвига, информационный выход которого подключен к информационному входу арифметического блока, информационный выход которого соединен с информационным входом второго регистра сдвига и первым входом коммутатора, второй вход которого подключен к информационному выходу второго регистра сдвига, четвертый выход блока управления соединен с управляющим вхо-; дом блока памяти, управляющим входом первого регистра сдвига и управляющим входом коммутатора, а пятый выход блока управления соединен с входами записи информации первого и второго регистров сдвига, причем блок управления содержит первый, второй, третий, четвертый н пятый коммутаторы, регистр, регистр итераций, группу элементов И, первый, второй и третий, Ц / счетчики, триггер, дешифратор и гене- С ратор тактовых импульсов, первый выход которого является вторым выходом блчка управления, второй выход гене-. ратора тактовых импульсов соединен с первым входом дешифратора, первый выход которого соединен с входом С5. первого разряда первого счетчика, I4h йнформационный выход которого подключен к первым входам элементов И груп- фф пы и информационному входу регистра, ) выход младшего разряда которого сое- 1 динен с первым входом первого коммутатора, первый выход которого подключен к входу старшего разряда регист-) ра,выход (rn-r)+1)-го разряда(rr) =

r) = Cog N, M ° N — размер преобразова" ния) которого подключен к второму входу первого коммутатора, второй вы-, ход которого соединен с вторым входом, дешифратора, второй выход которого соединен с входом (ь - n +1) -го раэ1164730 ряда первого счетчика, выход перенолнения которого подключен к входу записи "1" в старший разряд регистра итераций и тактовому входу второго счетчика, выходы Г -го (P = op, m) и .

К -ro (К= Е.,n) ра.рядов .оторого соединены соответственно с первым и вторым входами второго коммутатора, выход которого подключен к входу установки в "0" регистра итераций и тактовому входу третьего счетчика, выходы W -го и и -ro разрядов которого подключены соответственно к первому и второму входам третьего коммутатора, выход которого лодключен к входу триггера, выход которого объединен с первым выходом генератора тактовых импульсов и является пятым выходом блока управления и

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

Известно устройство, выполненное 5

1 как внешний процессор ЭВМ и содержащее арифметический блок, блок, генерирующий комплексные тригонометричес", кие константы, блок сверхоперативной

10 памяти для хранения одного вектора, блок прямого доступа, в котором содержится, индексный кольцевой счетчик памяти 3ВМ, старшая и младшая группы разрядов которого путем переключения .счетного входа и флага переполнения счетчика могут меняться местами для виртуального транспортирования массива (1) .

Существенными недостатками этого устройства являются его низкое быст-. 2О родействие и большие аппаратурные затраты. Кроме того, устройство вычисляет коэффициенты Фурье только квадратного массива данных М» М, а для вычисления, коэффициентов Фурье.М» И требуются дополнительные аппаратурные затраты.

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

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

Для вычисления коэффициентов Фурье двухмерного массива входных данных размерностью M»N устройство выполняет следующие операции: и-1 м-1 -3 — „ g,k, )ь 6,1 (4,<=K E f(e„e, 1Е .е

Р,=о g,=o

Выполнение указанного алгоритма обеспечивает блок управления.

Информация в двоично-инверсном порядке заносится в оперативную память, отдельно действительная и мнимая части. В постоянной памяти записаны значения четверти периода косинуса. По кодам адресов, вырабатываемых блоком управления, выбирается информация из оперативной и постоянной памяти и поступает в арифметический блок, где производятся вычисления элементарных операций БПФ. Рез 11б4730, 4 зультаты вычислений снова заносятся,- равляющим входом коммутатора, а пяв оперативную ламять по адресам, вы- тый выход блока- управления соединен

I рабатываемым в блоке управления. с входами записи информации первого

Коды на выходах блока управления и второго регистров сдвйга, причем определяют адреса ячеек оперативной 5 блок управления содержит первый, памяти, информация из которых посту- . второй, третий, четвертый и пятый пает в арифметический блок на обра- коммутаторы, регистр, регистр итеработку, или.заносится в оперативную ций, группу элементов И, первый, память после обработки в. арифметичес- второй и третий счетчики, триггер, ком блоке. fp дешифратор и генератор тактовых имПорядок выборки адресов из постоянной памяти. также онределяется кодом на выходах блока управления и сохраняется всегда одним и тем же при любом числе итераций и любом объ-. 5 пульсов, первый выход которого является вторым выходом блока управления, второй выход генератора тактовых импульсов соединен. с первым входом дешифратора, первый выход которого соеме .выборки.

Элементарная операция БПФ производится в арифметическом блоке устройства за 4 шага.

Недостатком такого устройства явединен с входом первого разряда первого счетчика, информационный выХод которого подключен к первым входам элементов .И группы и информационному входу регистра, выход младшего разряра сдвига, четвертый выход блока уп- 55 равления соединен с управляющим входом блока памяти, управляющим входом первого регистра сдвига и уп- ка соединен с первыми входами. четвертого и пятого коммутаторов, выход младшего разряда второго счетчика является четвертым выходом блока упляется низкое быстродействие, по- да которого соединен с первым входом скольку цикл вычисления элементарной . первого коммутатора, первый выход операции БПФ в арифметическом блоке которого подключен к входу старшего происходит за 4 шага.. разряда регистра, выход (y- +g) ro

Цель изобретения — повышение бшст. 25 разряда (п.=log М, п = fog, К, Марв родействия устройства.. размер преобразования) которого подПоставленная цель достигается тем, ключен .к второму входу первого комчто в устройство для реализации двух- иутатора, второй выход которого сое-мерного быстрого преобразования Фу- динен с вторым входом дешифратора, рье, содержащее блок памяти., информа- M второй выход которого соединен с ционный выход которого соединен с ин- входом (в-а +1)-го разряда первого формационным входом арифметического . счетчика, .выход переполнения котороблока,.информационный выход которого ro подключен к входу записи "1" в подключен к информационному входу старший разряд регистра итераций и блока памяти, адресный вход которого 5 тактовому входу второго счетчика, подключен к первому выходу блока уп- выходы С -го (1 = Eo . ) и К -ro Z равления, второй, выход которого сое- (k =Cog n ) разрядов которого соедиьz динен с входом синхронизации арифме- . нены соответственно с первым и втотического блока, вход задания коэф- рым входами второго коммутатора вы ж, фициентов которогр подключен к выхо- 40 ход которого подключен к входу устаду блока постоянной памяти, адресный новки в "О" регистра итераций и таквход которого соединен с третьим вы- товому входу третьего счетчика, выходом блока управления, введены пер- ходы щ -го и 11 -ro разрядов которовыи, второй регистры сдвига и комму- го подключены соответственно к пе— о к пертатор, выход которого соединен с ин- 45 вому и второму входам третьего ком-. формационным входом первого регистра мутатора, выход которого подключен к сдвига, информационный выход которо- входу триггера, выход которого объего подключен к информационному входу .динен с первым вЫходом генератора арифметического блока, информацион- тактовых импульсов и является пятым ный выход которого соединен с инфср- 50 . выходом блока управления, и соединен мационным входом второго регистра с вторым входом дешифратора и управсдвига и первым входом коммутатора, ляющими входами второго третьего

Э Ф второй вход которого подключен к ий-. четвертого и пятого коммутаторов, формационному выходу второго регист- информационный выход третьего счетчи1164730 равления и соединен с входом записи регистра, информационный выход которого подключен к вторым входам четвертого и пятого коммутаторов, выходы которых являются первым выходом блока управления, информационный выход регистра итераций. подключен к вторым входам элементбв И группы, выходы которых являются третьим выходом блока управления. 10 . На фиг. 1 изображена блок-схема устройства для реализации двухмерного быстрого преобразователя Фурье," на фиг.2 †. блок-схема блока управления, на фиг.3 — блок-схема арифмети- 1$ . ческого блока.

Устройство содержит арифметический блок 1, блоки постоянной 2 памяти .и блок (оперативной) 3 памяти, блок управления 4, коммутатор 5, первый 6 .20 и второй 7 регистры сдвига.

Блок управления 4 содержит триг- гер 8, счетчики 9, 10 и 1,1, регистр 12, коммутаторы 13 и 14, регистр итераций 15, группу элементов И 16, коммутаторы 17, 18 и 19, дешифратор

20 и генератор 21 тактовых импульсов.Арифметический блок 1 содержит первый 22 и второй 23 входные регист-. ры, регистр синуса 24, регистр ко- ЗО синуса 25, первый 26 и второй 27 коммутаторы, первый 28, второй 29, третий 30 и четвертый 31 арифметические узлы, первый 32, второй 33, третий .34 и -четвертый 35 регистры хранения.

При обработке по строкам массива

М Й входных:данных (И - число выборок в строке, N — число выборок в. столбце, M>N) разрядность первого .счетчика 11 определяется числом л2 = 40

=log М, разрядность второго 10 счетчика-- (=log ш, разрядность третьего 9 счетчика — п 1оя И.

При обработке по столбцам массива разрядность первого счетчика 11 onpeg$ деляется числом и =logzN, второго 10 счетчика — k =log,N третьего 9 счет чика †.а .=log Ì.

Число разрядов регистра 12 при обработке .по строкам, равно m при .об59 работке по столбцам — П

Число разрядов регистра итераций

15 равно N -1.

Число элементов группы элементов И 16, первой 13 и второй 14 групп коммутаторов равно соответственно -1, 2 ив .

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

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

3. По кодам адресов, вырабатываемых блоком управления 4, в арифметический блок 1 записывается значение экс- . поненциальных множителей из постоянной памяти 2, а из блока памяти 3 значение двух. точек строки (столбца) матрицы М»22 входных данных, и в арифметическом блоке 1 происходит вычисление одной элементарной. операции БПФ. Результат вычисления заносится во второй 7, и, через коммутатор 5, первый 6 регистры сдвига.

Сигналы занесения информации поступают с. первого выхода блока 2 1 синхронизации У4, причем первый операнд поступает в первый регистр 6, а второй — во второй регистр 7. При этом на третьи управляющие входы первого регистра 6, коммутатора 5 и блока 3 с четвертого выхода У3 блока управления

4 поступает сигнал "0", причем блок

3 работает в режиме "Считывание", регистры в режиме "Запись со сдвигом на один разряд", а выход блока 1 через коммутатор .5 подключается к входу первого регистра 6.. Дальше вычисление элементарных операций БПФ до полного завершения одной итерации аналогично.

После окончания первой итерации на третьи входы регистра 6, блока 3 и коммутатора 5 поступает сигнал "I", причем блок 3 работает в режиме "3aпись", регистр 6 - в режиме "Считыва.ние со сдвигом ва один разряд", а че. рез вход коммутатора 5 выход второго регистра 7 подключается к входу первого 6 регистра сдвига, с выхода которого в арифметический блок 2 последовательно поступают операнды> хранящиеся в первом 6 и втором 7 регистрах сдвига. Происходит вторая итерация вычисления БПФ, причем результат. вычислений заносится в блок памяти 3 на место выбранной при первой итерации информации. Дальнейший процесс обработки значений одной строки (столбца) матрицы входных данных аналогичен, т.е. во время четной итерации информация поступает в арифметический блок

1 из первого 6 и второго 7 регистров сдвига, а во время нечетной"- из блока памяти 3. При этом на вторые вхо7

11647 ды регистров 6 и 7 с выхода триггера

8 поступает сигнал "0",.который определяет разрядность регистров 6 и 7, равную 4,/2. После завершения вычисления элементарных операций БПФ по строкам (столбцам), происходит вычисление БПФ по столбцам (строкам) данных, причем на выходе триггера 8 по- . является сигнал "1.", по которому разрядность регистров 6 и 7 устанавлива- 1Р ется равной М /2. Обработка по столбцам данных .аналогична обработке по строкам данных..

Блок управления 4 устройства, ра— ботает следующим образом. 15

В начале работы на выходе триггера 8 и выходах разрядов счетчиков 9;.

10 и 11 регистра 12 и регистра итераций 15 устанавливается потенциал

"0". Генератор 2 1 генерирует серик 2р тактовых импульсов, поступающие через дешифратор 20 на вход первого разряда счетчика 11,: При переходе потенциала на выходе, старшего разря- . да счетчика 11 из "1" в "0" в стар- 25 ший разряд регистра итераций 15 записывается "1" со сдвигом хранимой в регистре итераций 15 информации . на один разряд. Кроме того, импульсы, поступающие на вход счетчика .10, де - 30 пятая в зависимости от числа требуе= мых итераций БПФ строки (столбца) матрицы входных данных. Задний срез импульсов, поступающих через коммутатор 18 с выхода е.-го разряда вто35 рого счетчика 10, устанавливает на . выходах разрядов регистра итераций потенциал "0". Состояние разрядов третьего счетчика 9 изменяется в зависимости от числа поступивших на 4р его вход импульсов. Код с выходов разрядов счетчика 9 через коммутатор

13 подается на адресные входы блока

3, определяя номер обрабатываемой строки массива данных, а код с выхо- 45, дов разрядов счетчика 11 поступает в регистр 12, где преобразуется в зависимости от режима работы регистра 12 (режим работы задается потенци. алом на .третьем выходе счетчика 10), 5р и через коммутатор 14 подается на адресные входы блока 3, определяя номера пары ячеек в строке, с .которых считывается информация (нечетная итерация) или в которые записываются 55 операнды после обработки в блоке 1 (четная итерация). Коды адресов вы" борки информации иэ блока 2 опреде30 8 ляются в зависимости от номера итерации состоянием разрядов регистра. итераций 15 и счетчика 11, причем выход разрядов регистра итераций 15 управляет прохождением информации

:через группу элементов И 16.

При, поступлении на вход триггера

8 через коммутатор 17 заднего среза импульса с выхода rl--го разряда счетчика 9 начинается .обработка по столбцам массива данных. При этом на. выхо- де триггера 8 появляется сигнал "1",. счетчики. 11, 10 и 9 перестраиваются (т.е. изменяется их разрядность), а входы коммутаторов 1 3 и 14 подклю.чаются к выходам .разрядов соответст» венно регистра 12 и счетчика 9, при-. чем состояние на выходах разрядов . счетчика,9 определяет номер обрабатываемого столбца, а состояние на выходах разрядов регистра 12"- номера пары ячеек в столбце, где хранятся(либо куда поступают) операнды,участвующие в элементарном преобразова- . нии БПФ при нечетной(либо четной) итерации соответственно. Порядок выборки информации из блока 2 сохраняется тем же, причем считываемые зна-чения .экспоненциальных множителей соответствуют изменившемуся размеру графа БПФ .(всего N /2 значений половины периода косинуса).- Работа блока управления 4 при вычислении БПФ по столбцам данных аналогична работе при вычислении БПФ по строкам данных.

Арифметический блок 1 устройства работает следующим образом.

При вычислении элементарных операций БПФ блок 1 управляется тактовыми импульсами, поступающими с второго выхода 4 блока управления 4..

Входы Х1 и Х2 входных регистров .22 и 23 являются соответственно вхо- дами действительной и мнимой-части операндов, выбираемых из блока 3 или первого 6 и второго 7 регистров сдвига.

Арифметический блок 1 вычисляет коэффициенты согласно с алгоритмом

F;,„(Д)=Г; (3)+Г;(1) Ы;

F „,, (k) =F; (Я) -F; (k) .M.

Приведенный алгоритм реализуется в арифметическом блоке за два шага.

Первый шаг. В первом 22 и втором

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

9 ° 11647

3, или первого 6 и второго 7 регистров сдвига (при нечетной итерации вычисления БПФ одной строки (столбца) матрицы входных данных информация в блок 1 поступает из блока 3, а при . четной — из первого 6 и второго 7 регистров сдвига). В регистрах синуса 24 и косинуса 25 хранится информа ция, выбираемая из блока 2.

Операнды из первого 22 и второго 10

23 входных регистров через первый 26 и второй .27 коммутаторы параллельно поступают на первые входы первого

28, второго 29, третьего 30 и четвер- . того 31 арифметических логических уэ- 15 лов соответственно. Выходы младших разрядов регистров синуса 24 и косинуса 25 соединены с управляющими входами первого 28, третьего 30, второго 29 и четвертого 31 узлов соответ- 20 ственно. Регистры синуса 24 и косинуса .25 работают в режиме сдвига в сторону младших разрядов, а выход младшего разряда управляет режимом работы узлов 28, 29, 30 и 31. При сигнале 25

"1" на выходе младшего разряда регистра синуса в зависи .:ости от знака. функции узлы 28, 29, 30 и 31 выполняют операции либо А+В, либо А-В. При сигнале "0" осуществляется перезаписьgp. со сдвигом информации через АЛУ в, регистры хранения. Для выполнения комплексного умножения F; (k) W=F„(k) необходимо выполнить операции умно30

10 жения вещественных чисел, одно сложение .и одно вычитание. Формирование действительной

ВеCF. (k)j =R F» (k) ReW CF (k) I W . и мнимой I $F (k) =R F„(k) I„W+Ig. (k) ,:t RpW частей Fj (k) производится путем переключения коммутаторов 2 1 и 22.

Затем происходит вычисление величин

F;„(1) =F, ()+F; (); .Г,Ä(k) =F (3).-Г, (k) .

Второй шаг. Результат. вычисления с выходов У8 и У7 арифметического блока 1 поступает на информационные входы либо блока, либо первого 6 и второго 7 регистров сдвига (во время нечетной итерации информация поступает в первый 6 и второй 7 регистры сдвига, а во время четной — в блок памяти 3), а на входы Х2, Х1 поступает информация, выбираемая из блока

3 (при нечетной итерации), или первого 6 и второго 7 регистров сдвига (при четной итерации). На входы К4 и ХЗ поступает информация, выбираемая из-блока ПП (2).

Описан один цикл вычисления элементарной операции БПФ, дальнейшая работа арифметического блока 1 аналогична..

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

У7

Cur. У

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

Редактор А.Гулько Техред М.Пароцай Корректор A.Çèìîêoñoâ

Заказ 4189/47 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4