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

ряда первого счетчика, выход перепол ifeHHH которого подключен к входу залиси 1 в старший разряд регистра итераций и тактовому входу второг.о счетчика, выходы -го (2 о гп) и Х-го (К ) разрядов которого со единены соответственно с первым и вторым входами второго коммутатора, В.ЫХОД которого подключен к входу установки в О регистра итераций и тактовому входу третьего счетчика, выходы im -го и п -то разрядов которого подключены соответственно к первому и второму входам третьего коммутатора, выход которого лодключен.к входу триггера, выход которого объединен с первым выходом генератора тактовых импульсрв и является пятым выходом блока управления и

64730

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

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

1 , ,

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

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

счетного входа и флага переполнения счетчика могут меняться местами для виртуального транспортирования массива lj .

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

Наиболее близким к изобретению является устройств,о, выполненное как специгшизированный процессор БПФ и

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

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

Для вычисления коэффициентов Фурье двухмерного массива входных данных размерностью MN устройство вьшолняет следующие операции:

,. НИ м-1jife..,,,,

rlKi, И i(e, е,)е-е

е,-о е,о

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

Информация в двоично-инверсном порядке заносится в оперативную память, отдельно действительная и мнимая части. В постоянной памяти записаны значения четверти периода косинуса. По кодам адресов, вырабатываемь1х блоком управления, выбирается информация из оперативной и постоянной памяти и поступает в арифметический блок, тде производятся вычисления элементарных операций БПФ. Результаты вычислений снова- заносятся в оперативную ламять по адресам, вырабатываемым в блоке управления. . Коды на выходах блока управления определяют адреса ячеек оперативной памяти, информация из которых поступает в арифметический блок на обработку, ИЛИзаносится в оперативную, память после обработки в- арифметичес ком блоке. Порядок выборки адресов из постоянной памяти также определяется, кодом на выходах блока -управления и сохраняется всегда одним и тем же при любом числе итераций и любом обЪ еме .выбо.рки. . Элементарная операция БПФ производится в арифметическом блоке устройства за 4 шага. Недостатком такого устройства является низкое быстродействие, поскольку цикл вычи.сления элементарной операции БПФ в арифметическом блоке происходит за 4 шага-. Цел изобретения - повышение быст родействия устройства. Поставленная цель достигается тем что в устройство для реализации дву.х мерного быстрого преобразования Фурье, содержащее блок памяти, информа ционный выход которого соединен с ин формационным входом арифметического блока,, информационный выход которо.го подключен к информацирнному входу блока памя.ти, адресный вход которого подключен к первому выходу блока уцравления, второй.выход которого соединен с входом синхронизации арифметического блока, вход задания коэффициентов которого подключен к выхсду блока постоянной памяти, адресный вход которого соединен с третьим выходом блока управления, введены первый, второй регистры сдвига и коммутатор, выход которого соединен с .ийформационньи входом первого регистра сдвига, информационный вьгход которого подключен к информационному входу арифметического блока, информационный :выход которого соединен с ниформационным входом второго регистра сдвига и первым входом коммутатора, второй вход которого подключен к ий- формационному выходу второго регистра сдвига, четвертый выход блока управления соединен с управляющим входом блока памяти, управляющим входом первого регистра сдвига и yn-i р.авляющйм входом коммутатора, а пятый вьгход блока- управления соединен с входами записи информации первого и второго регистров сдвйг.а, причем блок управления содержит первый, второй, третий, четвертый и пятый коммутаторы, регистр, регистр итераций, группу злементов И, первый, второй и третий счетчики, триггер, дешифратор и генератор тактовых импульсов, первый выход которого является вторым выходом блока управления, второй выход генератора тактовых импульсов Соединен с первым входом дешифратора, первый выход котор.ого соединен с входом первого разряда первого счетчика,информационный выход которого под1шючен к первым входам элементов И группы и информационному входу регистра, выход младшего разряда которого соединен с первым входом первого комму-татора, первый выход которого подключен к входу старшего рааряда регистра, выход (m-h+1)-ro разряда (ln. М , nreog.jN, M«N - размер преобразования) которого подключен .к второму входу первого коммутатора, второй выход которого соединен с вторым входом дешифратора, второй выход которого соединен с входом (m-rv + 1)-ro разряда первого Счетчика, .выход переполнения которого подключен к входу записи 1 в старший разряд регистра итераций и тактовому входу второго счетчика, выходы t -го ( Eog.j Ы ) и К-го (); ) разрядов которого соединены соответственно с первым и вторым входами в.торого коммутатора, выход которого подключен к входу установки в О регистра итераций и тактовому входу третьего счетчика, выходы m -го и п -го разрядов которого подключены соответственно к первому и второму входам третьего ком-мутатора, выход которого подключен к входу триггера, выход которого объединен с первым выходом генератора тактовых импульсов и является питым выходом блока управления, и соединен с вторым входом дешифратора и управлякяцими входами второго, третьего, четвертого и пятого коммутаторов, информационный выход третьего счетчика соединен с первыми входами четвертого и пя.того коммутаторов, выход младшего разряда второго счетчика является четвертым выходом блока управпения и соединен с входом записи регистра, информационный выход- которого подключен к вторьм входам четвертого и пятого коммутаторов, выход которых являются первым выходом бдока управления, информадионньм выход регистра итераций подключен к вторым входам элементов И группы, выходы ко торых являются третьим выходом блока управления.. . .. . На фиг.1 изображена блок-схема устррйства для реализации двухмерного быстрого преобразователя Фурье, на фиг.2 - блок-схема блока управления j на фиг.З - блок-схема арифметическрг.о блока. Устройство содержит арифметически блок 1, блоки постоянной 2 памяти -.и блок (оперативной) 3 памяти, блок управления 4, коммутатор 5, первьй 6 и второй 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, второй 2.9,; третий 30 ,и четвертый 31 арифметические узлы, первый 32, второй 33, третий 3 и-четвертый 3.5 регистры хранения. Пр.и обработке по строкам массива М-. N входных сданных (М - число выборок в строке, N - число выборок встолбце, ) разрядность первого .счетчика 11 определяется числом It) logjM, разрядность второго 10 счетчика-- 6 , разрядность третьего 9 счетчика - п logzN. При обработке по столбцам массива разрядность первого счетчика 11 опре деляется числом h-log N, второго 10 счетчика - К , третьего 9 счет чика -.т .iog2M. . . Число разрядов регистра 12 при об работке ,по. строкам .равно m , п:ри обработке по столбцам - ti . Число разрядов регистра итераций 15 равно m -1. Число элементов группы злементов И 16, первой 13 И второй 14 груп коммутаторов, равно соответственно т-1, п и m . 1 0 .6 Устройство для реализаций двумерного быстрого преобразования Фурье работает следующимОбразом. Информация в двоично-инверсном порядке, отдельно действительная и мнимая--чарть, -записана в блокпамяти 3. По кодам адресов, вырабатываемых блоком управления 4, в арифме.тичесу кий блок 1 записывается значение экс-. поненциальных множител.ей из постоянной памяти 2, а из блока памяти 3 значение двух, точек строки (столбца) матрицы М N входных данных, и в арифметическрм блоке .1 происходит .вычисление одной элемен.тарной-операции БПФ. Результат вычисления заносится во второй 7. и, через коммутатор 5, первый 6 регистры сдвига. Сигналы занесения информации поступают с.первого выхода блока 21 синхронизации Y4, причем первый операнд поступает в первый регистр 6., а второй 7 во второй регистр. 7. При этомна третьи упра.вляющие вх.оды первого регистра 6, коммутатора 5 и блока -3 с четвертого выхода Y3 блока у-правления 4 поступает сигнал О , причем блок 3 работает в режиме -.Считывание, регистры в режиме Запись со сдвигом на один разряд, а выход блока 1- через коммутатор5 подключается к входу первого регистра .6-. Дальше вьгчисление элементарных операций БПФ до полного завершения, одной итерации аналогично. После окончания первой итерации на третьи входы регистра 6, блока 3 и коммута-тора 5 поступает сигнал 1, причем блок 3 работает в режиме Запись, регистр 6 - в режиме Счигыва-ниесо сдвигом на один разряд, а через вход-коммутатора 5 выходвторого регистра 7 подключается к.входу первого 6 регистра сдвига, с выхода которого в арифметический блок 1 последовательно поступают операнды, хранящиеся в первом 6 и втором 7 регистрах сдвига. Происходит вторая итерация вычисления БПФ, причем- результат, вычислений заносится в блок памяти 3 на место выбранной при первой итерации информации. Дальнейший процесс обработки значений одной строки (столбца) матрицы входных данных аналогичен, т.е. во время четной итерации информация поступает в арифметический блок 1 из первого 6 и второго 7 регистров сдвига, а во время нечетной- из блока памяти 3. При .этом на вторые вховыхода тригге1эа ды регистров 8 поступает сигнал О,который ределяет разрядность регистров 6 равную М/2. После, завершения вычисления элементарных операдай БПФ по строкам (столбцам), происходит вычис ление БПФ- по столбцам (строкам) данных, причем на выходке триггера 8 появляется сигнал 1., по которому раз рядность регистров 6 и 7 у-станавлива ется равной N/2. Обработка по столбцам -данньгх .аналогична обработке по строкам данных.-.. Блок управления 4 устройства, работает следующим образом. В начале рабрты на выходе триггера 8 и вькодах разрядо.в счетчиков 9 10 и 11, реги.стра 12 и регистра итераций 15 устанавливается потенциал О. Генератор 2.t генерирует серии такто.вых импульсов, поступающие через дешифратор 20 на вход первого ра.зряда сче.тчика 11, Цри пере-ходе потенциала на выходе,Старшего разряда счетчика 11 из 1 в О в старший разряд регистра итераций 15 записывается 1 со сдвигом хранимойв реги.стре итераций 1-5 информации на один раз-ряд. Кроме того, импульсы поступаняцие на вход счетчика 10, делятСя в зависимости от числа требуемых итераций БПФ строки (столбца) матрицы входныхданных. 3-адний срез импульсов, поступающих через комму-, татор 18 с выхода е -го разряда второго счетчика 10, устанавливает, на .выходах разрядов регистра итераций потенциал О. Состоя.ние разрядов третьего счетчика 9 изменяется в зависимости от числа поступивших на его вход импульсов. Код с выходов разрядов счетчика 9 через- коммутатор 13 подается на адресные входы блока 3, определяя номер обрабатываемой строки массива данньгх, а код с. выхрдов разрядов, счетчика -11 поступает в регистр 12, где преобразуется в зависимости от режима работы регистра 12 (режим работы задается потен1ц алом на третьем выходе счетчика 10), и через коммутатор 14 подается на адресные входы блока 3, определяя но мера пары ячеек в строке, с .которых считывается информация (нечетная ите рация) или в которые записываются операнды после обработки в блоке 1 (четная итерация). Коды адресов выборки информации из блока 2 опреде10 ляются в зависимости от номера итерации состоянием разрядов регистра. итераций 15 и счетчика .11, причем выход разрядов регистра итер-аций 15 управляет прохождением информации через группу элементов И 16. При. .поступлении на вход-триггера 8 через коммутатор 17 заднего среза импульса- с выхода П-го разряда счетчика 9 начинается обработка по столбцам массиваданных. При этом-на выходе триггера 8 появляется сиг.нал 1,.. счетчики- 11, 10 и .9 перестраиваются (т.е. изменяется их разрядность), а входы коммутаторов 13 и 14 подключаются к выходам разрядов соответст- . венно регистра 12 и счетчика 9, причем состоя-ние на выходах разрядов счетчика .9 определяет номер обрабатьшаемого столбца, а состояние на выходах разрядов регистра номера пары ячеек в столбце, где хранятся(либо куда поступают) операнды,участвующие в элеме.нт.арном преобразова- НИИ БПФ при кечетной(либо четной) итерации соответственно. Порядок выборки информации из блока 2 сохраняется, тем же, причем считываемые значения .экспоненциальных множителей соответствуют изменившемуся размеру графа БПФ -(всего N/2 значений половины периода косинуса) . Работ.а блока управления 4 при вычислении БПФ по столбцам данных аналогична работе при вычислении БПФ по строкам данньгх. Арифметический блок 1 устройства работает следующим образом. При вычислении элементарных операций БПФ блок 1 управляется тактовыми импульсамиj поступающими с второго выхода 4 блока управления 4.. Входы XI и Х2 входных регистров 22 и, 23 являются соответственно входами действительной и мнимой ча.сти операндов, выбираемых из блока 3 или первого 6 и второго 7 регистров сдвига. Арифметический блок 1 вычисляет коэффициенты согласно с алгоритмом. F,4i (J)F-Cj)+F;(k)-W; .F,,, (k)F,(j)-P-(k)-W. Приведенный алгоритм реализуется в арифметическом блоке з.а два шага. Первый шаг. В первом 22 и втором 23 входных регистрах хранится инфорация о действительной и мнимой часи операндов, выбираемых из блока 9 - 11 3, или первого 6 и второго 7 регистров сдвига (при нечетной итерации вычисления БПФ одной строки (столбца) матрицы входных данных информация в блок 1 поступает из блока 3, а причетной - из первого 6 и второго 7 регистров сдвига). В регистрах синуса 24 и косинуса 25 хранится информация, выбираемая из блока 2. Операнды из первого 22 и второго 23 входных регистров через первый 26 и второй -27 коммутаторы параллельно поступают на первые входы первого 28, второго 29, третьего 30 и чётвертого 31 арифметических логических узлов соответственно. Выходы младших разрядов регистров синуса 24 и косинуса 25 соединены с управляющими входами первого 28, третьего 30, второго 29 и четвертого 31 узлов соответственно. Регистры синуса 24 и косинуса 25 работают в режиме сдвига в сторону младших разрядов, а выход младшего разряда управляет режимом работы узлов 28, 29, 30 и 31. При сигнале 1 на выходе разряда регистра синуса в зависимости от знака функции узлы 28, 29, 30 и 31 выполНЯК1Т операции либо А+В,- либо А-В. При сигнале О осуществляется перезапись со сдвигом информации через. АЛУ в регистры хранения. Для выполнения комплексного умножения F- (k).- (k) необходимо выполнить операции умно30жения вещественных чисел, одно сложение .и одно вычитание. Формирование действительной : R,F;.(k)RpF, (k)-R,(k). . и мнимой (k) R(k).-i4J+i i( . частей F/ (k) производится: путем переключения комт утаторов 21 и 22.. Затем происходит вычисление величин . ; . . . F-;,(j)F;(j)+F;:(k)i .: Fui(k)F-(j)-F;,-(k). Второй шаг. Результат вычисления с выходов Y8 и Y7 арифметического блока 1 поступает на информационные входы либо блока, либо первого 6 и второго 7 регистров сдЕ;ига(во время нечетной итерации информация поступает в первый 6 и второй 7 регистры сдвига, а во время- четной - в блок памяти 3), а на входы Х2, Х1 поступает информация, выбираемая из блока 3 (при нечетной итерации), или первого 6 и второго 7 регистров сдвига (при четной итерации). На входы Х4 и ХЗ поступает информация, выбираемая из блока ПП (2). Описан один цикл вычисления элементарной олерацИи БПФ, дальнейшая работа арифметического блока 1 аналогична.. . Предлагаемое устройство позволяет сократить время вычисления коэффициентов Фурье. ..

А

. I

ф1/г.

IV м