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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 19) Щ) А 33 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ ДЕТЕПЬСТВ вои ислиз зоб ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(46) 07.07.88. Бюл. Иф 25 (71) Одесский политехнический инсти тут(56) Авторское свидетельство СССР У 1164730, кл. С 06 Р 15/332, 1985.Авторское свидетельство СССР У 114284, кл. С 06 Г 15/332, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ(57) Изобретение относится к цифро обработке сигналов и может быть пользовано для спектрального ана и фильтрации изображений. Цель и ретения - расширение области примыкания за счет вычисления преобразова"ний с произвольным соотношением первой н второй размерностей преобразования. Поставленная цель достигаетсяза счет того, что в состав устройства входят блок памяти 1, ари 4 иетической блок 2, блок постоянной памяти 3,коммутаторы 4, 5, регистр сдвигастрок 6, регистр сдвига столбцов 7,счетчик строк 8 и счетчик столбцов9, реверснвные счетчики 10, 11, триггеры 12-15, генератор тактовых импульсов 17, коммутаторы 18, 19, элемент И 20, триггер 21, элемент И 22,счетчик 23, элементы И 24, 25, регистры сдвига 26, 27, сумматор 28.1 з.п. ф-лы, 3 ил.17являются соответственно адресным вх дом и входом синхрониэации выдачи арифметического блока, тактовым вхо дом которого являются соединенные между собой первый вход элемента И и тактовый вход второго регистра,вт 1408442 8о- рой вход умножителя является входомкоэффициента арифметического блока, входом синхронизации вычислений которого являются соединенные между собой второй вход элемента И и управо. ляющий вход первого ключа.1408442 Редактор Заказ 3353/52 Производственно-полиграфическое предприятие, г, Угород, ул. Проектная, 4 ь Уфа Ь Составитель А.БарановЛ.Гратилло Техред А,Кравчук Корректор Л.Патай Тиэаа 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5где Х,и У- векторы размерЯ Мностью И Ю Х 1, составленные из столбцов соответственно матриц Х и У , т.е.л2 йХ,= (Х рх Х,ОХ Х Х Х (аналогично определяется вектор н нН Н 2н н ДЪ К 2На основе свойства кронекеровскогопроизведенияматрица Р(н"2 может быть записанав виде быстрого алгоритма видаН 2РГ 1 (11 ЭР 812. )Мф 2х (1Р, 1 - ) к,ИЭ,121-,91;.хМ 2 1 2 2 д Н 2 Ь12 д-+) (Э 2 д-"91, д- фОхОх 11 Й Ок Ч) . (2)22Хз+ Иэх Изобретение относится к цифровой обработке сигналов и может быть использовано для спектрального анализа и фильтрации изображений,Цель изобретения - расширение области применения за счет вычисления преобразования с произвольным соотношением первойи второй размерностей преобразования.В устройстве используется совмещенный быстрый алгоритм вычисления двумерного ДПФ И ХВ , основанный на следующей формуле вычислений:22 408442 г,лХ 202 ф,Й,Мо й,й Ч,К 2д 2 - к-Й диагональный элементкматрицы весовых коэффициентов40 о м 214)Аналогично на всех первых дп этапах происходят вычисления только постолбцам матрицы промежуточных данных 1 , при этом каждая базовая2операция соответствует обычной бабочке видах - х 1+ И х 3- 1 сХДалее д и-й этап:1 = 1дп дннн1,2днХ, 130Дд - к-й диагональный элементкматрицы весовых коэффициентовф 2 д.1 мдф)Начиная с (оп+1)-го этапа, вычисления выполняются одновременно и по З 5 столбцам; и по строкам. В этом случае базовая операция производитсяуже над четырьмя членами промежуточных данныхНа основе (2) получаем поэтапноследующую процедуру вычислений. Первый этап:дп где- знак поточечного произведенияматриц:0( б.,1 д, где д- М-й дйагональййй элемент матрицы весовых коэффициентов (021 я 12 );1 2Х3 йК,М 2 Н,Н 2Н 2 ф ,И Н,Н 2 н 2 ф 45 Для этапов Ьдп, и, имеем из (2) порядок вычислений дп + 1.п этап:2дн+дн+ л дПХ50 н,в НН 241 М 2лх Х м (Р 2 1 и у 2)д+1 - 1 с-й диагональный элементматрицы весовых коэффициентов, У ехр(-2 в/Я,),СО, М /1-1 1на первых апи - и этапах вычис лений и базовую операцию видаз Я Окончательноп -й этап:1- (м,ааааа) Х мм (ТиМД - Е-й диагональный элементкматрицы весовых коэффициентов (П, хх Р ),й При описанном способе вычисленийчисло операций умножения, требуемыхдля полного двумерного ДПФ, равно Отсюда экономия в числе умножений . для данного способа вычислений по сравнению с построчно-столбцовым . равна в зависимости от соотношений йи и (максимальный выигрыш по чис 2.лу умножений получается в случае 35квадратного ДПФ, т.е, Я, К ) .Другие характеристики эффективности,вычислений (число сложений, объемоперативной памяти, объем постояннойпамяти хранения весовых коэффициентов) остаются неизменными. Ка фиг. 1 изображена структурная;схема устройства (пример выполнения11Яф 45фиг, 2 - структурная схема арифметического блока; на фиг, 3 - временныедиаграммы работы устройства.Устройство двумерного быстрого преобразования Фурье (фиг. ) содержитблок 1 оперативной памяти, арифметический блок 2, блок 3 постоянной памяти, коммутатор 4 строк и коммутатор5 столбцов, регистр 6 сдвига строк ирегистр 7 сдвига столбцов, счетчик 8строк и счетчик 9 столбцов, реверсивные счетчики 10,и 11, триггеры 12-16,генератор 17 тактовых импульсов(ГТИ), коммутаторы 18 и 19, элементИ 20, триггер 2 1, второй элемент И 22,счетчик 23, элементы И 24 и 25, регистры 26 и 27 сдвига, сумматор 28.Арифтический блок (фиг. 2) состоитиз умножителя 29 комплексных чисел,узла 30 буферной памяти, накапливающего сумматора-вычитателя 31, ключа32, регистров 33 и 34 знака, элемента И 35, ключа 36.Устройство работает следующим об"разом,Исходный массив О,И з занесен вблок 1 оперативной памяти в двоичноинверсном порядке как по строкам,так и по столбцам.В начальном состоянии счетчик 8строк, счетчик 9 столбцов, а такжесчетчик 23 обнулены. В регистр 6сдвига строк и регистр 7 сдвига столбцов записаны коды первого этапа 0001, аналогичные коды записаны вреверсивные счетчики 1 О и 1 1.На входы коммутаторов 4 и 5 поступают коды с выходов соответственносчетчика 8 строк и счетчика 9 столбцов, на другие входы - коды данныхсчетчиков плюс коды номеров этаповсоответственно с выходов регистра 6сдвига строк и регистра 7 сдвигастолбцов,Арифметический блок устройствавычисляет базовую операцию видаОф 111 на остальных1 с ) д п (т,На данном э следовательно, (4, тогда И тическом блоке вида ний,и,). талах вычисл1 с "6 и+ 1 Ра первона 1 мотрим этапе. роцесс вы слений 1,1 1.111.1 + Х= Х Х,+, - 25Из приведенного выражения следуетпорядок адресации считывания-записиэлементов Х; из блока 1 оперативной1памяти, Рассмотрим порядок адресацииболее подробно. Начальные состояниясчетчика 8 строк и счетчика 9 столбцов нулевые. При этом на входы коммутаторов 4 и 5 поданы коды 0000строки и 0000 столбца, на другиевходы данных коммутаторов поданы этиже коды плюс коды с выхода регистра356 сдвига строк (код 0001). и ре"гистра 7 сдвига столбцов (код 0001). Таким образом, на вторые входы 1коммутаторов 4 и 5 подается в данном 40случае одинаковый код 0001. Записывая код строки и столбца через запятую, можно видеть, что на основании сигналов разрешения, поданных .накоммутаторы 4 и 5 соответственно свыходов триггеров на 8 и на 16 (фиг3,Р 8 и 016), считывание из блока 1 оперативной памяти выполняется по адресам 0,0; 1,0; О, 1; 1, 1, т.е. за первые 16 тактов от ГТИ 17 происходитсчитывание из блока 1 оперативной памяти, умножение на весовые коэффициенты и запись в узел ЗО буферной па"мяти четырех операндов Хо, Х,оХ , и Х . Запись в узел ЗО буфер 1ной памяти происходит по адресу свыхода счетчика 23, который на первых16 тактах ГПИ 17 имеет последовательную адресацию (фиг. 3, ХЗ(1, аи) или тапе имеет К = 1,и, при любом (из формулы,1, отсюда в арифмевыполняются операции ХЗ(ди, и,) . Кроме того, на первых и далее всех нечетных 16 тактах ГТИ 17 происходит формирование адресов блока 3 постоянной памяти для считывания соответствующих весовых коэффициентов У , Для формирования данных адресов используются элементы И 23 и 24, регистр 26 сдвига на ди, сумматор 11 и регистр 27 сдвига. На первых ди этапах элемент И 24 закрыт нулевым сигналом с выхода регистра 6 сдвига строк и, следовательно, на первых аи этапах происходит формирование адре сов весовых коэффициентов только по строкам. Регистр 27 сдвига сдвигает результат суммы с выхода. сумматора 28 на и, - К разрядов влево, где К- номер этапа, подаваемый на регистр 27 сдвига с выхода регистра 6 этапа строк. При этом все разряды, уходя-, щие при сдвиге за разрядную сетку, теряются, что соответствует вычислению адреса весового коэффициента по модулю В, . Если на выходе регистра 27 сдвига образуется нулевой код, то сигнал "0" по шине Х 5 переключает ключ 36 в арифметическом блоке 2 на другой выход и операнд Х .переда 1,1ется в узел 30 буферной памяти, ми- нуя умножитель 29, что ускоряет время вычислений.Таким образом, после первых (и каждых нечетных) 16 тактов ГТИ 17 в узле 30 буферной памяти последова1408442 7тельно записаны операнды Х . (11,4 = О, 1; 1 = О, 1), умноженные на соответствующие весовые коэффициенты.На вторых (и каждых четных) 16 тактах ГТИ 17 происходит выполнение базоной операции. На первой итерации первого этапа выполняются операциис вида1 О О,О 1.О 1 11 О,11сУмножения на И не происходит, так как в данном случае адрес весового коэффициента для операндов Х и Х. Ь,о1 постоянно нулевой, так как кроме элемента И 24 закрыт элемент И 25 нулевым сигналом по входу подаваемого с выхода делителя 4-16 на 8 (фиг.З, Р 8). Для операндов Хи Х 1, адрес имеется (так как элемент И 25 открыт), но он нулевой (код счетчика 8 строк равен 0).Иэ выражения (4) видно, что на первых бп этапах в накапливающий сум" 25 матор 31 необходимо сначала два раза считать операнды Х, . и Х;, (на1,. ФФ 1 Д первой итерации Хи Х, ), затем два раза считать операнды Х и, +1 Х; (на первой итерации х-, и Х ), Отсюда следует, что на пер 1,1вых дп этапах адресация счетчика 23 на вторых (и каждых четных) 16 тактах ГТИ 17 должна быть равна О, 1, О, 1, 2, 3, 2, 3 (фиг. 3, ХЗ(1, дп). При этом соблюдается правильный поря док считывания операндов иэ узла 30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно со слагаемыми в накапливающий сумма 40 тор-вычитатель 31 с выхода регистров 33 и 34 знака поступает знак операции + или - (сложение или вычитание), На первых этапах регистр 34 знака закрыт элементом И 35 и ключ 32 передает сигнал по выходу 2. В этом случае выполняется базовая операция. ,Сигнал Х 7, подаваемый в накапливающий сумматор-вычитатель 31 с выхода делителя импульсов 15, 16 на 4 (фиг.З, ,04), осуществляет очистку сумматора 50 после конца выполнения полной операции сложения. Одновременно после конца операции сложения результат с выхода накапливающего сумматора-вычитателя 31 по шине У передается на 55 вход записи блока 1 оператюной памяти и записывается в него по тем же адресам, по которым происходило счи 8тывание в первых 6 тактах. Это обеспечивается повторением управляющих сигналов на входах коммутаторов 4 и 5 (фиг. 3, 08 и О 6) при неизменном состоянии счетчика 8 строк и счетчика 9 столбцов. Таким образом, после вторых (и каждых четных) 16 тактов ГТИ 17 заканчиваются выполнение базовой операции и запись результата вычислений в блок 1 оперативной памяти. Полное выполнение первой (и каждой последующей) итерации осуществляется за 32 такта. На третьих 16 тактах ГТИ 17 начинается выполнение второй итерации первого этапа вычислений. При этом задним фронтом импульса с выхода триггеров 12-16 на 32 происходит переключение счетчика 8 строк в следующее состояние и реверсивного счетчика 10 на один такт, уменьшая его содержимое на единицу. Следующим состоянием счетчика 8 строк является код счетчика + 1, если после переключения код реверсивного счетчика 10 не равен О, или код счетчика + 1 + + код этапа, если после переключения код реверсивного счетчика 10 равен О. В данном случае до переключения код реверсивного счетчика 1 О равен коду первого этапа, т.е. 0001, после переключения код равен 0000, следующим состоянием счетчика 8 строк является код + 1 + код этапа00 .,00 + 000 + 00 01 = 00010 =2. При этом состояниесчетчика столбцов на данной итерации не изменяется. В реверсивный счетчик 10 после индикации кода 0000 опять записывается код этапа (в данном случае 0001).Таким образом, на третьих 16 тактах ГТИ 17 происходит считывание че" тырех операндов из блока 1 оперативной памяти уже по адресам 2,0; 3,0;2,1; 3,1, т.е. операндов Х ; Х Х, Х , которые, последовательнопроходя через умножитель 29 комплексных чисел или минуя его в случае нулевого кода на выходе регистра 27 сдвига, записываются в узел 30 буферной памяти.На четвертых 16 тактах выполняется базовая операция вида (4) для указанных операндов, т.е.ХХ + Х р уХХ + ХХф Х уф Х ХПосле второй итерации (4"16 тактов ГТИ 17) первого этапа происходитпереброс счетчика 8 строк по принципу, аналогичному на первой итерации:код строкикод строки + 1 + кодэтапа000010 + 0001 + 0001 " 000100 = 4, и далее на каждыйд-й итерации первого этапа счетчик 8строк увеличивает код на 2 (00010),Код счетчика столбцов не изменяется до тех пор, пока счетчик 8 строкне наберет код 3 (конец последней1строки), тогда в начале следующейитерации отрицательный перепад и-гостаршего разряда счетчика 8 строкперебрасывает (по тактовому входу)счетчик 9 столбцов в следующее состояние. Следующее состояние счетчика9 столбцов определяется аналогичносчетчику 8 строк, т.е. код счетчика9 столбцов при следующем тактовом импульсе равен:код счетчика 9 = код предыдущеготакта + 1, если код реверсивногосчетчика 11 Ф 0 первый вариант);код счетчика 9 = код предыдущегоэтапа + 1 + код номера этапа по столб . цам, если код реверсивного счетчика110 (второй вариант),Код номера этапа по столбцам поступает с выхода регистра 7 сдвигастолбцов и на первых ьп этапах равен0001. Исходя из определенного условия,после выполнения вычислений по всемстрокам нулевого и первого столбцовпроисходит переключение счетчика 9столбцов по второму варианту, таккак код реверсивного счетчика 11 после переключения равен О,Отсюда, код счетчика 9 = 00, 00 + 0001 + 0001 = 2. В этом случае на входы коммутатора 5 подаются соответственно коды 00010 и 00.011, следовательно, на следующих итерациях первого этапа выполняются базовые операции вида с Х ф Х + Х1.э 1,з 1 .зм 1,1;,о 11 2 ф 1+1,з у 1+,3. Аналогичный процесс нычислений продолжается до конца первого этапа.На последних итерациях первого этапавыполняется базовая операция по пос-,ледним двум столбцам матрицы данных,хранящейся н блоке 1 оперативнойпамяти, т,ем;2 1,х. +1 гоХ =Х -Х.10 1+1,И 1.2 1,-2 1+1,Ч-Я;Х + ХК -1 1+уН1+ 1,уф 15Конец первого (и каждого следующего этапа) определяется по состоянию старшего и -го разряда счетчикай9 столбцов.Началом второго (и каждого следующего) этапа вычислений являетсяпереход счетчиков 8 и 9 из состояний1111 н состояние 000, при этомзадним фронтом импульса старшегои -го разряда счетчика 9 столбцовГпроисходит сдвиг (по тактовому входу)регистров 6 и 7 сднигон на один разряд влево каждый, Причем на первыхьп этапах срабатывает тОлько регистр6 сдвига строк, так как регистр 7сдвига столбцов закрыт до появлениясигнала разрешения.Таким образом, на втором этапевычислений код регистра 7 сдвигастолбцов остается прежним (0001),а код регистра 6 сдвига строк станонится равным 00010, В этом случаережим переключения счетчика 9 столбцов остается прежним, как и на первом этапе, а режим работы счетчика408 строк несколько изменяется,,В начале второго этапа исходныйкод счетчика 8 строк равен 0000,реверсивного счетчика 10 - 0010.После выполнения первой итерацииреверсинный счетчик 10 переключается в код 00,01, который не равен О,отсюда счетчик 8 строк переключаетсяна 1 и его код равен 0001, Послевыполнения второй итерации реверсивный счетчик 10 переключается в код0000, отсюда счетчик 8 строк переключается на 1 + код этапа0001 + 0010 " 0011 и его,кодранен 00100 4,55 Таким образом, на втором этапе вычислений выполняется базовая операция вида (4) при К 2, т,е,+ 1,21 45 Аналогичным образом продолжаютсявычисления на всех ьп этапах. На .( а и + 1)-м этапе (и всех последующих) меняется вид базовой операции,В начале ( ьп+1) -го этапа регистр 6сдвига строк находится в состоянии01000 (1 на ап+1)-й позиции).С выхода 2 регистра 6 сдвига строкпоступает (до конца и -го этапа) сиг 1нал разрешения на входы регистра 7сдвига столбцов, элемента И 24, триггер 21, ключ 32 и элемент И 35. Состояние регистра 7 сдвига столбцовостается неизменным 0001, поэтому25режим переключения счетчика 9 столбцов и адреса с выхода коммутатора 5столбцов остается. таким же, как ина первых ап этапах. В реверсивныйсчетчик 10 записываешься код (ьп+1)-го 30этапа, отсюда режим переключениясчетчика 8 строк следующий:код счетчика 80,1,22 - 1+ 1 3 21 (смена режима -код счетчика 10 40 В этом случае код адреса номерастроки на выходе коммутатора 4 строкравен ььКод адреса номера строки0,2 , 50 1,2 ь"+ 1,. ,2 - 1,21 (смена режима), 2 3 2 ь" 1 2+ 1, 3 2 + 1,3 2 - 1,2 а"фНа (ьп+1)-м этапе выполняется базовая операция вида Х;= Х .+ И Х. д,+ Х + 1 з Г 114"7, 1,ф+ 1Для обеспечения правильного выполнения базовой операции (5) в устройстве на (ьп+1)-и этапе происходит переключение режимов счетчика 23, накапливающего сумматора-вычитателя 31,а также регистров 33 и 34 знака. На первых 16 тактах первой итерации (ьп+1)-го этапа происходит процесс считывания данных из блока 1 оперативной памяти, умножение на весовые коэффициенты и запись в узел 30 буферной памяти. Порядок вычислений и временные диаграммы аналогичны описанным на предыдущих этапах,Вторые 16 тактов первой итерации (ьп+1)-го этапа обеспечивают выпол" нение базовой операции. В этом случае триггер 21 заперт единичным сигналом по входу и счетчик 23 набирает последовательный код адреса, обеспечивая этим последовательное считывание операндов (фиг. 3, ХЗьп,п, с узла 30 буферной памяти в накапливающий сумматор-вычитатель 31. Одновременно в него подается код операции с выхода регистра 33 знака, При этом ключ 32 находится в положении 1 и за 16 так15 6 ЗО 40 50 товому в.оду третьего триггера, выход которого подключен к первомувходу первого элемента И, управляющему входу третьего коммутатора итактовому входу четвертого триггера,выход которого подключен к управляющему входу четвертого коммутатора,к первым входам второго и третьегоэлементов И и тактовому входу пятого триггера, выход которого подключенк управляющему входу второго коммутатора, счетным входам счетчикастрок и первого реверсивного счетчика и первому входу четвертого элемента И, выход которого подключен ктактовому входу арифметического блока и тактовому входу шестого триггера, выход которого подключен к входу обнуления счетчика и второму входувторого элемента И, выход которогоподключен к входу разрешения записисчетчика, информационный выход которого подключен к адресному входуарифметического блока, вход синхронизации приема которого соединен садресным входом блока постоянной памяти и подключен к выходу первого регистра. сдвига, информационный входкоторого подключен к выходу сумматора, первый вход которого подключенк выходу второго регистра сдвига,тактовый вход которого подключен квыходу третьего элемента И, второйвход которого соединен с входом синхронизации вычислений арифметического блока, управляющим входом первогокоммутатора, установочным входом шестого триггера, информационным входом регистра сдвига столбцов и подключен к выходу последовательной выдачи информации регистра сдвига строк, первый и второй информационные выходы которого подключены соответственно к первому и второму информационным входам третьего коммутатора, выход которого подключен к первому адресномувходу блока памяти, второй адресныйвход которого подключен к выходу четвертого коммутатора, первый информационный вход которого соединен с третьим входом третьего элемента И и подключен к информационному выходусчетчика столбцов, выход переноса которого подключен к тактовым входамрегистра сдвига строк и регистра сдвига столбцов, информационный выход которого подключен к второму информацинному входу четвертого коммутатора,входу обнуления счетчика столбцов и входу управления направлением счета второго реверсивного счетчика, информационный выход которого подключен к информационному входу счетчика столбцов, счетный вход которого соединен со счетным входом второго реверсивного счетчика, вторым входом первого элемента И и подключен к выходу переноса счетчика строк, информационный вход которого подключен к информационному выходу первого реверсивного счетчика, вход управления направлением счета которого соединен с входом обнуления счетчика строк, тактовым входом первого регистра сдвига и подключен к третьему информационному 1выходу регистра сдвига строк, выходы первого и третьего элементов И подключены соответственно к второму входу сумматора и тактовому входу второ" го регистра сдвига, выход первого коммутатора подключен к второму входу четвертого элемента И и второму информационному входу второго коммутатора, выход которого подключен к счет-, ному входу счетчика.2, Устройство по п. 1, о т л ич а ю щ е е с я тем, что арифметический блок содержит два ключа, умно- житель, узел буферной памяти, накапливающий сумматор-вычитатель, два регистра и элемент И, выход которого подключен к тактовому входу первого регистра, выход которого соединен с первым выходом первого ключа и подключен к информационному входу второго регистра, информационный выход которого подключен к управляющему входу накапливающего сумматора-вычитателя и информационному входу первого ключа, второй выход которого подключен к информационному входу первого регист" ра, первый выход второго ключа подключен к первому входу умножителя, выход которого соединен с вторым выходом второго ключа и подключен к информационному входу узла буферной памяти, выход которого подключен к информационному входу накапливающего сумматора"вычитателя, выход которого является выходом арифметического блока, входами операнда и синхронизации приема которого являются соответст-. венно информационный и управляющий входы второго ключа, адресный вход узла буферной памяти и тактовый вход накапливающего сумматора-вычитателя