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

) 111) 332 4151) С 06 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ. ЗОБРЕТЕНТЕЛЬСТВУ ТОРСКОМУ С(56) 1. Аврорин А.В. и др. Сдля цифрового восстановленияфических изображений в реальмени эксперимента. - "Автоме1978, Р 4.2. Авторское свидетельВ 809198, кл. С 06 Р 15/3(прототип)лаевскии,1 инстиоблем стем гологром врерия",СССР981 ств 32,(54)(57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИДВУХМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАТЕЛЯФУРЪЕ, содержащее блок памяти, информационный выход которого соединенс информационным входом арифметического блока, информационный выход которого подключен к информационномувходу блока памяти, адресный входкоторого подключен к первому выходублока управления, второй выход которого соединен с входом синхронизацииарифметического блока, вход заданиякоэффициентов которого подключен квыходу блока постоянной .памяти, адресный вход которого соединен с тре"тьим выходом блока управления, о т -л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в. неговведены первый, второй регистры сдви"га и коммутатор, выход которого соединен с информационным входом первогорегистра сдвига, информационный выходкоторого подключен к информационному ОПИСАНИЕ входу арифметического блока, информационный выход которого соединен с информационным входом второго регистра сдвига и первым входом коммутатора, второй вход которого подключен к информационному выходу второго регистра сдвига, четвертый выход блока управления соединен с управляющим вхо-; дом блока памяти, управляющим входомпервого регистра сдвига и управляющим входом коммутатора, а пятый выход блока управления соединен с входами записи информации первого и второго регистров сдвига, причем блок управления содержит первый, второй, третий, четвертый и пятый коммутаторы, регистр, регистр итераций, группу элементов И, первый, второй и третий, счетчики, триггер, дешифратор и генератор тактовых импульсов, первый выход которого является вторым выходом блдка управления, второй выход гене-, ратора тактовых импульсов соединен с первым входом дешифратора, первый выход которого соединен с входом Оа) первого разряда первого счетчика, Май йнформационный выход которого подклю- фД чен к первым входам элементов И группы и информационному входу регистра,СвР выход младшего разряда которого сое динен с первым входом первого коммутатора, первый выход которого подключен к входу старшего разряда регист ра,выход (в-л+1)-го разряда(в =10 М.ф = Во И, М Ч - размер преобразования) которого подключен квторому входу первого коммутатора, второй вы-, ход которого соединен с вторым входом, дешифратора,второй выход которого соединен с входом (ь - о +1) -го раэ1164730 ряда первого счетчика, выход перенолнения которого подключен к входу записи "1" в старший разряд регистра итераций и тактовому входу второгочи,д. Е - о (Е=Е, ) и ,К - СК= Е.,М р-р. - р. единены соответственно с первым и вторым входами второго коммутатора, выход которого подключен к входу установки в "О" регистра итераций и тактовому входу третьего счетчика, выходы Ю -го и й -го разрядов которого подключены соответственно к первому и второму входам третьего коммутатора, выход которого лодключен к входу триггера, выход которого объединен с первым выходом генератора тактовых импульсов и является пятым выходом блока управления и Изобретение относится к вычислительной технике и может быть использовано для решения задач цифровой голографии и антенной техники.Известно устройство, выполненное 5как внешний процессор ЭВМ и содержащее арифметический блок, блок, генерирующий комплексные тригонометричес" . кие константы, блок сверхоперативной10 памяти для хранения одного вектора, блок прямого доступа, в котором содержится, индексный кольцевой счетчик памяти ЭВМ, старшая и младшая группы разрядов которого путем переключения ,счетного входа и флага переполнения счетчика могут меняться местами для виртуального транспортирования массива 1Существенными недостатками этого устройства являются его низкое быст-. 20 родействие и большие аппаратурные затраты. Кроме того, устройство вычисляет коэффициенты Фурье только квадратного массива данных М М, а для вычисления, коэффициентов Фурье.М И требуются дополнительные аппаратурныезатраты.Наиболее близким к изобретению является устройство, выполненное как специализированный процессор БПФ и соединен с вторым входом дешифратора и управляющими входами второго,третьего, четвертогои пятого коммутаторов, информационный выход третьего счетчика соединен с первымивходами четвертого и пятого коммутаторов, выход младшего разряда второго счетчика является четвертым выходом блока управления и соединен свходом записи регистра, информационный выход которого подключен к вторым входам четвертого и пятого коммутаторов, выходы которых являютсяпервым выходом блока управления,информационный выход регистра итераций подключен к вторым входам элементов И группы, выходы которых являются третьим выходом блока управления. 2содержащее арифметический блок, соединенный с постоянной памятью, блоком управления, кроме того, блок управления устройства содержит регистр, первую и вторую группы элементов И, первый и второй коммутаторы, узел задания режима, первый и второй счетчики, сумматор, регистр хранения адреса и узел обращения кода адреса 21.Для вычисления коэффициентов Фурье двухмерного массива входных данных размерностью МИ устройство выполняет следующие операции: Н- М-1 - Е,к, 16РОс 1.=Е Е С(ее,е е е,:о Е,=о Выполнение указанного алгоритма обеспечивает блок управления.Информация в двоично-инверсном порядке заносится в оперативную память, отдельно действительная и мнимая части. В постоянной памяти записаны значения четверти периода косинуса. По кодам адресов, вырабатываемых блоком управления, выбираетсяинформация из оперативной и постоянной памяти и поступает в арифметический блок, где производятся вычисления элементарных операций БПФ. Рез 11 б 4730, 4зультаты вычислений снова заносятся ,. равляющим входом коммутатора, а пяв оперативную ламять по адресам, вы- тый выход блока- управления соединен1рабатываемым в блоке управления. с входами записи информации первогоКоды на выходах блока управления и второго регистров сдвйга, причем определяют адреса ячеек оперативной 5 блок управления содержит первый, памяти, информация из которых посту- . второй, третий, четвертый и пятый пает в арифметический блок на обра- коммутаторы, регистр, регистр итеработку, или заносится в оперативную ций, группу элементов И, первый, память после обработки в. арифметичес- второй и третий счетчики, триггер, ком блоке, 10 дешифратор и генератор тактовых имПорядок выборки адресов из постоянной памяти. также онределяется. кодом на выходах блока управления и сохраняется всегда одним и тем же при любом числе итераций и любом объ-.15 пульсов, первый выход которого является вторым выходом блока управления, второй выход генератора тактовых импульсов соединен с первым входом дешифратора, первый выход которого соеме .выборки.Элементарная операция БПФ производится в арифметическом блоке устройства за 4 шага.Недостатком такого устройства явединен с входом первого разряда первого счетчика, информационный выХодкоторого подключен к первым входамэлементов .И группы и информационномувходу регистра, выход младшего разряра сдвига, четвертыйвыход блока управления соединен с управляющимвходом блока памяти, управляющимвходом первого регистра сдвига и уп" ка соединен с первыми входами. четвертого и пятого коммутаторов, выходмладшего разряда второго счетчикаявляется четвертым выходом блока упляется низкое быстродействие, по-да которого соединен с первым входом скольку цикл вычисления элементарной первого коммутатора, первый выход операции БПФв арифметическом блоке которого подключен к входу старшего происходит за 4 шага. разряда регистра, выход (Ъ-+1)-гоЦель изобретения - повышение бшст.25 разряда (п.:Со М, п: Соф, й, МаЧ - родействия устройстваразмер преобразования) которого подПоставленная цель достигается тем, ключен .к второму входу первого комчто в устройство для реализации двух- мутатора, второй выход которого соемерного быстрого преобразования Фу- динен с вторым входом дешифратора, рье, содержащее блок памяти., информа второй выход которого соединен с ционный выход которого соединен с ин- входом (в-а +1)-го разряда первого формационным входом арифметического . счетчика, .выход переполнения которо- блока,.информационный выход которого го подключен к входу записи "1" в подключен к информационному входу старший разряд регистра итераций и блока памяти, адресный вход которого д тактовому входу второго счетчика, подключен к первому выходу блока уп- выходы 6 -го И = Кок . ) и К -го равления, второй, выход которого сое- Й =ЯоЯ и ) разрядов которого соедиьгдинен с входом синхронизации арифме- . нены соответственно с первым и втотического блока, вход задания коэф- рым входами второго коммутатора выЖю фициентов которогр подключен к выхо ход которого подключен к входу устаду блока постоянной памяти, адресный новки в "О" регистра итераций и таквход которого соединен с третьим вы- товому входу третьего счетчика, выходом блока управления, введены пер- ходы щ -го и 11 -го разрядов котороивыи, второй регистры сдвига и комму- . го подключены соответственно к пе -о к пертатор, выход которого соединен с ин вому и второму входам третьего ком-. формационным входом первого регистра мутатора, выход которого подключен к сдвига, информационный выход которо- входу триггера, выход которого объего подключен к информационномувходу .динен с первым вЫходом генератора арифметического блока, информацион- тактовых импульсов и является пятым ный:выход которого соединен с инфср . выходом блока управления, и соединен мационным входом второго регистра с вторым входом дешифратора и управ- сдвига и первым входом коммутатора, ляющими входами второго третьегоЭ Ф второй вход которого подключен кин- четвертого и пятого коммутаторов, формационному выходу второго регист- информационный выход третьего счетчи 1164730равления и соединен с входом записирегистра, информационный выход которого подключен к вторым входам четвертого и пятого коммутаторов, выходы которых являются первым выходом бло ка управления, информационный выход регистра итераций подключен к вторым входам элементов И группы, выходы которых являются третьим выходом блока управления. 10. На фиг. 1 изображена блок-схема устррйства для реализации двухмерного быстрого преобразователя Фурье," на фиг.2 в . блок-схема блока управления, на фиг.3 - блок-схема арифмети .ческого блока.Устройство содержит арифметический блок 1, блоки постоянной 2 памяти и блок (оперативной) 3 памяти, блок управления 4, коммутатор 5, первый 6 .20 и второй 7 регистры сдвига.Блок управления 4 содержит триг- гер 8, счетчики 9, 10 и 1,1, регистр12, коммутаторы 13 и 14, регистр итераций 15, группу элементов И 16, . ф 5 коммутаторы 17, 18 и 19,дешифратор 20 и генератор 21 тактовых импульсов.Арифметический блок 1 содержит первый 22 и второй 23 входные регистры, регистр синуса 24, регистр ко-ЗО синуса 25, первый 26 и второй 27 коммутаторы, первый 28, второй 29, третий 30 и четвертый 31 арифметические узлы, первый 32,второй 33, третий .34 и четвертый 35 регистры хранения.При обработке по строкам массиваМ Й входных:данных (И - число выборок в строке, И - число выборок в столбце, МИ) разрядность первого .счетчика 11 определяется числом л 1 = 40 =1 о 8 М, разрядность второго 10 счетчика - ( =1 оя ш, разрядность третьего 9 счетчика - и 1 од,11.При обработке по столбцам массива разрядность первого счетчика 11 опре.4 деляется числом й =1 о 88, второго 10 счетчика - 1 =1 од,8, третьего 9 счет. чика в .а .=1 о 8,М.Число разрядов регистра 12 при об. работке .по строкам, равно в, при об 59 работке по столбцам - ПЧисло разрядов регистра итераций 15 равно п 3 -1.Число элементов группы элементов И 16, первой 13 и второй 14 групп коммутаторов равно соответственно %-1 1 и В е Устройство для реализации двумерного быстрого преобразования фурье работает следующим образом. Информация в двоично-инверсном порядке, отдельно действительная и мнимая.час.ть, записана в блок памяти .3. По кодам адресов, вырабатываемых блоком управления 4, в арифметический блок 1 записывается значение экс- . поненциальных множителей из постоянной памяти 2, а из блока памяти 3 значение двух. точек строки (столбца) матрицы М 11 входных данных, и варифметическом блоке 1 происходит вычисление одной элементарной операции БПФ. Результат вычисления заносится во второй 7, и, через коммутатор 5, первый 6 регистры сдвига. Сигналы занесения информациипоступают с. первого выхода блока 2 1 синхронизации У 4, причем первый операнд поступает в первый регистр 6., а второй - во второй регистр . При этомна третьи управляющие входы первого регистра 6, коммутатора 5 и блока 3 с четвертого выхода УЗ блока управления4 поступает сигнал "0", причем блок3 работает в режиме "Считывание", регистры в режиме "Запись со сдвигом наодин разряд", а выход блока 1 черезкоммутатор .5 подключается к входу первого регистра 6 Дальше вычислениеэлементарных операций БПФ до полного завершения одной итерации аналогично. После окончания первой итерации на третьи входы регистра 6, блока 3 и коммутатора 5 поступает сигнал "1", причем блок 3 работает в режиме "Запись", регистр 6 - в режиме "Считыва.ние со сдвигом ва один разряд", а че рез вход коммутатора 5 выходвторого регистра 7 подключается к входу первого 6 регистра сдвига, с выхода которого в арифметический блок 1 последовательно поступают операнды хранящиеся в первом 6 и втором 7 регистрах сдвига. Происходит вторая итерация вычисления БПФ, причем результат. вычислений заносится в блок памяти 3 на место выбранной при первой итерации информации. Дальнейший процесс обработки значений одной строки (столбца) матрицы входных данных аналогичен, т.е. во время четной итерации информация поступает в арифметический блок 1 из первого 6 и второго 7 регистров сдвига, а во время нечетной"- из блока памяти 3. При этом на вторые вхо711647ды регистров 6 и 7 с выхода триггера8 поступает сигнал "0", который определяет разрядность регистров 6 и 7,равную М,/2. После завершения вычисления элементарных операций БПФ по 5строкам (столбцам), происходит вычисление БПФ по столбцам (строкам) данных, причем на выходе триггера 8 по- .является сигнал "1.", по которому разрядность регистров 6 и 7 устанавливается равной М /2. Обработка по столбцам .данных .аналогична обработке построкам данных,Блок управления 4 устройства, работает следующим образом. 15В начале работы на выходе триггера 8 и выходах разрядов счетчиков 9;.10 и 11, регистра 12 и регистра ите-раций 15 устанавливается потенциал"0", Генератор 2 1 генерирует серии20тактовых импульсов, поступающие через дешиФратор 20 на входпервогоразряда счетчика 11,: При переходепотенциала на.выходе, старшего разря- .да счетчика 11 из "1"в "0" в старший разряд регистра итераций 15 записывается "1" со сдвигом хранимойв регистре итераций 15 информациина один разряд. Кроме того, .импульсы,поступающие на вход счетчика .10, депятая в зависимости от числа требуемых итераций БПФ строки (столбца)матрицы входных данных. Задний срезимпульсов, поступающих через коммутатор 18 с выхода е.-го.разряда вто 35рого счетчика 10, устанавливает.на .выходах разрядов регистра итерацийпотенциал "0". Состояние разрядовтретьего счетчика 9 изменяется взависимости от числа поступивших на 40его вход импульсов, Код с выходовразрядов счетчика 9 через коммутатор13 подается на адресные входы блока3, определяя номер обрабатываемойстроки массива данных, а код с. выходов разрядов счетчика 11 поступаетв регистр 12, где преобразуется взависимости от режима работы регистра 12 (режим работы задается потенци. алом на .третьем выходе счетчика 10), 50и через коммутатор 14 подается наадресные входы блока 3, определяя номерапары ячеек в строке, с .которыхсчитывается информация (нечетная итерация) или в которые записываются 55операнды после обработки в блоке 1(четная итерация). Коды адресов вы"борки информации иэ блока 2 опреде 30 8ляются в зависимости от номера итерации состоянием разрядов регистра. итераций 15 и счетчика 11, причем выход разрядов регистра итераций 15 управляет прохождением информации через группу элементов И 16.При, поступлении на вход триггера 8 через коммутатор 17 заднего среза импульса с выхода П -го разряда счетчика 9 начинается .обработка по столбцам массиваданных. При этом на. выхо- де триггера 8 появляется сигнал "1",. счетчики 11, 10 и .9 перестраиваются (т.е. изменяется их разрядность), авходы коммутаторов 13 и 14 подключаются к выходам .разрядов соответственно регистра 12 и счетчика 9, при-. чем состояние на выходах разрядов счетчика ,9 определяет номер обрабатываемого столбца, а состояние на выходах разрядов регистра 12"- номера пары ячеек в столбце, гдехранятся. (либо куда поступают) операнды,участвующие в элементарном преобразовании БПФ при нечетной(либо четной) итерации соответственно. Порядок выборки информации из блока 2 сохраняется тем же, причем считываемые значения,экспоненциальных множителей соответствуют изменившемуся размеру графа БПФ (всего Н /2 значений половины периода косинуса). Работа бло. ка управления 4 при вычислении БПФпо столбцам данных аналогична работе при вычислении БПФ по строкам данных.Арифметический блок 1 устройства работает. следующим образом.При вычислении элементарных операций БПФ блок 1 управляется тактовыми импульсами, поступающими с второго выхода 4 блока управления 4Входы Х 1 и Х 2 входных регистров .22 и 23 являются соответственно вхо- дами действительной и мнимой части операндов, выбираемых из блока 3 или первого 6 и второго 7 регистров сдвига.Арифметический блок 1 вычисляет коэффициенты согласно с алгоритмом Р;,И)=Г; СЗ)+Г;(К) Ы; Р Ь)=Г;(З)-Р;Ь) Ы,Приведенный алгоритм реализуется в арифметическом блоке за два шага.Первый шаг. В первом 22 и втором 23 входных регистрах хранится информация о действительной и мнимой части операндов, выбираемых из блока1164730 Составитель А.Барановедактор А.Гулько Техред М.Пароцай Коррек Зимокосов Зака иал ППП "Патент", г,ужгород, ул.Проек 4 189/47 Тираж 710ВНИИПИ Государственнпо делам изобретени 113035, Москва, Ж,Подписиго комитета СССРй и открытийаушская наб., д.4/5