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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 3342 9) 51)5 С 06 Г 15 Е чск СТРОГ еский институтрьской К. Клименкргиенко во СССР 32, 1986.СССР32, 1987. ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕК АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Киевский политехничим. 50-летия Великой Октябсоциалистической революци(54) УСТРО ПРЕОБРАЗОВ (57) Изобрете ной технике и ния систем ци основанных на го преобразов ния упроше цель достигае тав устроиств памяти, мульт кий блок 4, кл 6, регистр 7 ч ЙСТВО ДЛЯ БЪ О АНИЯ ФУРЬЕние относится к вычислительпредназначено для построефровой обработки сигналов, выполнении алгоритма быстроания Фурье. Цель изобретение устройства. Поставленная тся за счет того, что в соса входят блок 1 регистровой иплексоры 2, 3, арифметичесюч 5, двунаправленный ключ исла, регистр 8 коэффициен1633425 та, умножитель 9, регистр 1 О произведения, регистр1 результата, регистр 12 адреса, блок 13 постоянной памяти, шифратор4, регистр 15 порядка, мультиплекИзобретение относится к вычислительной технике и предназначено для построения систем цифровой обработки сигналов, основанных на выполнении алгоритма быстрого преобразования Фурье.Целью изобретения является упрощение устройства.Устройство иредназначе о для выполнения базовой операции быстрого преобразования ФурьеС=А+В(В, ЦО=А - В Ц +В Ф,С, =А+ВЦ +В, Ц;где С, С, 0, О, действительные и мнимые части иреобразова и н ы х отс чето в с оотнетстненно;А, А, В, В - действительные и мнимые части исходных отсчетов;Й(, Ж - действительная и мии.мая части весового коэффи циеита.Вычисление модуля и фазы ироизнодится и формулампа)А = Я+А;А ) =с гс(д(А /Л )На фиг.показана структурная схема устройства для быстрого преобразования Фурье; на фиг. 2 - структурная схема синхронизатора; иа фиг. 3 структурная схема генератора адреса.Устройство для быстрого преобразования Фурье (фиг.) содержит блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунапранлеиный ключ 6, регистр 7 числа, регистр 8 коэффициента, умножитель 9, регистрО произведения, регистр 1 результата, регистр 12 адреса, блок 3 постоянной памяти коэффициентов, шифратор 14, регистр 15 порядка, мультиплексор 16, блок 17 сравнения, блок 8 постоянной памяти констант, входной регистр 9, информационный нход 20, информационный выход 21, генератор 22 адреса, адресный выход 23, шины 24, 25 и синхронизатор 26.Синхронизатор 26 (фиг. 2) содержит счетчик 27 адреса, мультиплексор 28 адреса, узел 29 памяти, выходы 30 59 и нходы 60 - 65 синхронизатора.Генератор 22 адреса (фиг. 3) содержит счетчик 66 базовых операций и формиронатели 67, 68 адреса. 15 20 25 30 35 40 45 50 55 сор 6, блок 7 сравнения, блок 18 постоянной памяти констант, входной регистр 19, генератор 22 адреса, синхронизатор 26.3 ил. Работа устройства начинается при подаче сигнала на шину 60 начальной установки в нулевом такте. При этом по коду на шине 61 начального адреса микропро. граммы, соответствующей заданному режиму работы, выбирается из узла 29 памяти микрокоманд первая микрокоманда микропрограммы выполнения этого режима, по которой н счетчик 27 адреса микрокоманд записывается начальный адрес микрокоманды. После выполнения текущей микрокоманды в конце такта содержимое счетчика 27 увеличивается или заменяется новым из узла 29 памяти в случае безусловного перехода при единичном состоянии шины 62 признака ири условном переходе. При снятии сигнала на шине 60 устройство выполняет микрокоманды, выбираемые из узла 29 памяти микрокоманд ио адресу из счетчика 27 адреса микрокоманды.Генератор 22 адреса обеспечивает генерацию адресов считывания и записи данных и считывания весовых коэффициентов в соотнтстнии с алгоритмом быстрого преобразования Фурье с замещением и ирореживаиием но времени. Счетчик 66 в начале выполнения алгоритма устанавливается в нулевое состояние сигналом на входе 60 и увеличинает свое состояние на единицу с приходом сигнала на шину 58 в конце каждои базовой операции. Старшие разряды счетчика 66, начиная с п.го (где 2" размс р быстрого преобразования Фурье), сютнетстнуют номеру К итерации алгоритма. Формирователь 67 ирсдстанляет собой мультиплексор, который в зависимости от кода (ОООО 1) на входе 59 и номера итерации и роиускает на выход 23 соотнетствуюгци м образом цикличе ки иерставленные разряды ныхода счетчика 66 и тем самым формиру- т адрес опера ндон ААт,В,В(;,Ст,йд,0 Формирователь 68 ио коду 100 на выходе 59 выдает на выход 23 разряды счетчика 66, маскированные кодом.Условимся, что ири подаче кода 00 на входы 64 и 65 р кима синхронизатора 26 будет выполнять.я ба озая операция быстрого преобразования с(урь, ири подаче кода 01 выцислеиис модуля и фазы, при подаче кода 1 О - вычисление логарифма.Рассмотрим работу устройства ири выполнении базовой операции быстрого преобразования Фурье,И нулевом такте ио сигналу на входе 60 генератор 22 адреса устанавливается в на 16334255 10 15 20 чальное состояние нулевой базовой операции. По коду 100 на входе 59 генератор 22 адреса выдает на вход 23 ноль-адрес весового коэффициента Фо, который, пройдя через вход мультиплексора 3, записывается в регистр 12 адреса. На информационный вход 20 поступает операнд Вя, .В первом такте по коду 000 на вход 59 генератор 22 адреса выдает на адресный выход 23 устройства адрес операнда В, по которому внешним ЗУ с произвольйой выборкой считывается из блока 13 постоянной памяти коэффициентов, по нулевому адресу выбирается коэффициент Ж =1, который через шину 25 записывается в регистр 8 коэффициентов. Операнд Вя, нулевой базовой операции поступает во входной регистр 19.Во втором такте генератор 22 адреса по коду 001 на входе 59 выдает на адресный выход 23 адрес операнда В . В этомдотакте операнд В, поступает через вход 20 в регистр 19, операнд Вя из которого, пройдя мультиплексор 2 и блок 4, переписывается в нулевой регистр блока 1 регистровой памяти и, пройдя ключ 5, записывается в регистр 7. В третьем такте в умножителе 9 происходит умножение Вя, Ж результат которого поступает в регйстр 10 произведений. В регистр 8 коэффициентов из блока 13 памяти коэффициентов записывается Йдо в регистр 7 числа через коммутатор 2, блок 4, ключ 5 из регистра 19 переписывается операнд ВВ четвертом такте произведение ВЯ, Фя, пройдя через мультиплексор 2 и блок 4, поступает в первый регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение ВФ, результат котодорого поступает в регистр 10 произведений. В регистр 8 записывается коэффициент ФЯВ пятом такте произведение В Ждо поступает в блок 4, где происходит вычитание выражения - В Ж +Вя йя, подо до яо яо ступившего туда с первого регистра блока 1 регистрации памяти В, Ф . В умножителе 9 происходит умножеййе В, Ж и результат записывается в регистр0 произведений.В шестом такте генератор адреса по коду 010 выдает адрес операнда АяЯорезультат вычитания Во, Кя, - Вд йдо записывается в первый регистр блокарегистровой памяти. На информационный вход 20 поступает операнд Аяо, который записывается в регистр 19. Вя пересылается из нулевого регистра блока 1 регистровой памяти 1 через блок 4 и ключ 5 в регистр 7, из блока 13 памяти коэффициен. тов коэффициент к 1 записывается в регистр 8.В седьмом такте операнд Ая, из входного регистра 19 поступает в блок 4, где 25 30 35 40 45 50 55 он суммируется с содержимь 1 м перв 1 нрегистра блока 1 регистровой памя 1 и Ая +Вя Й 1 - Вд ф Ся 11 пе вь 1 и результат Сяо, пройдя ключ 5, 1 аписын;1 с 1 ся в регистр 11 результатаВ восьмом такте генератор адреса и коду 000 выдает адрес результата, и результат СЯ выдается из регистра 11 реозультата на выход 21. В блоке 4 вычисляется выражение Аяо - ВЯ Йя - В Ф )=0 Я, который, пройдя клк 1 ч О, задо о описывается в регистр 11.В девятом такте генератор 010 адреса выдает адРес РезУльтата и Ояо постУиает на информационный выход устрйства 21 Произведение В ЙЯ , пройдя через блок 4,То Яопоступает в первый регистр б,п 1 ка 1 регистровой памяти. В умножителс 9 присходит умножение В, Й, резллы аг котоЯо Дорого записывается в регистр 10 произве- дений В десятом такте генератор 22 адреса по коду 001 выдает адрес Лд , Операнд Адо поступает в регистр 19. В б, п 1 кс 4 про. исходит суммирование В Й +Ля Й"оо о 1 орезультат которого записьп 1 абтся в 11 е 1 вый регистр блока .В одиннадцатом такте А, поступает вфоблок 4, где Он суммируется с содержимым первого регистра блока 1 регистровойуо +Вдо Йяо +Вя Йдо -- С 11 ре зультат записывается в регистр 11.В двенадцатом такте генерат 1 р а;1 реса выдает адрес С, и в регистр 11 записы. вается операнд С . В блоке 4 присх- дит вычитание А - 1 В Йя +Ля Й 1 -тодо Яа о доВ тринадцатом такте генератор апре 11 выдает адрес О и на инфрм,1 пини ь 1 й выход устройства 21 1 п 1 ступ 111 пслсдний результат Од, . На тактовыи гегцра 1 р 22 адрса поступает ил 111 уль для вычпс,1 ения адресов следующей базовй ОперацииВ четырнадцатом такге из генератра 22 адреса адрес нового коэффициента Й", через мультиплексор 3 записываегся в р- гистр 12 адреса, и вычисления п 1111 тряк 1 тся с периодом 14 тактовРассмотрим работу при вычислении м. дуля и фазы комплексного числа.В нулевом такте число 0,5 вы,ц 1 ется из блока 18 памяти констант и здписы 1111 ется в четвертый регистр блока 1 регистровой памяти. В первом такте число 0,5 из четвертого регистра блока 1 регистровой памяти поступает в блок 4, где суммирлегся с ним же, и в пятый регистр блка 1 регистровой памяти записывается число 1. Числаи 0,5 соответс 1 вуют фазам 1-)=180 и 11=Ю и неооходимы для к 11 ррс кции результата вычисления фазы. Через информационный вход 20 устройства во вхднй регистр 19 поступает реальная часть Ая ВО втором такге через информацинный ихд5 10 15 устройства 20 во входной регистр 9 поступает мнимая часть операнда А , с вход 1 оного регистра 19 реальная часть А проходит мультиплексор 2, блок 4, запйсывается в нулевой регистр блока 1 регистровой памяти 1, а также, пройдя ключ 5, мультиплексор 3, записывается в регистр 2 адреса. При этом следующая микро- команда выбирается в учетом знака Аопоступающего ио входу 61 в синхронизатор 26. В гретьем такте мнимая часть операнда А, с входного регистра 19 через блок 4 поступает в первый регистр блока 1 регистровой памяти и в регистр 12 адреса. Порядок К, т. е. число незначащих цифр справа перед значащей цифрой операнда А, поступающего из регистра 12 адреса, церез шифратор 14 записывается в регистр 15 порядка. Гледуюгцая микро- команда также выбирается из узла 29 памяти с учетом знака А , и так образутоются четыре ветви микропрограммы, каждая из которых выбирается в зависимости от комбинации знаков исходных данных А, и А11 усть Л, )О и А )О, тогда дальиейшук) работу устройство продолжает следующим образом. В четвертом такте порядок К числа Ад с выхода регистрао12 адреса через шифратор 14 и порядок К цисла А, с выхода регистра 15 порядка поступают на входы блока 17 сравнения и мультиплексора 6 порядка, блок 17 сравнения анализирует порядки К и К и иод его управлением мультиплексор 16 порядка ио сигналу 63 пропускает минимальный из порядков К=минК,К ) на адресный вход б.пока 18 памяти констант, считанный из него коэффициент 2" - 16 записывается в ре.истр 8 коэффициентов. При этом порядок К ранен числу разрядов, на которое необходимо сдвинуть влево А и Ато для их нормализации,В третий регистр блока 1 регистровой памяти из блока 4 записывается поправка -)=О". В пятом такте из нулевого регистра блока 1 регистровой памяти через блок 4 и ключ 5 н регистр 7 числа поступает Хо=А. В шестом такте из первого регистра блока 1 регистровой памяти через блок 4 и ключ 5 в регистр 7 поступает Уо=А . В умножителе 9 происходит умножение Ло 2 г, результат которого записывается в регистр 10 произведений. В седьмом такте из регистраО произведение, равное Хо 2, поступает в регистр 7 числа, через ключ 6 в регистр 8 коэффициентов, а через вход мультиплексора 3 в регистр 12 адреса. В умиожителе 9 происходит умножение Уо 2 и записывается в регистр 1 О произведения. В восьмом такте из регистра 1 О млад. шие разряды произведения, равного Уо 2, пересылается в регистр 7 числа и через 20 25 30 35 40 45 50 55 ключ 6 - в регистр 8 коэффициентов. В умножителе 9 происходит умножение операндов и произведение Хо - 2 записывается в старшие разряды регистра 10 произведения. В девятом такте из блока 13 памяти весовых коэффициентов по адресу из регистра 12 адреса выбирается коэффициент, равный 1/Х 2", который записывается в регистр 8. Из первого регистра блока 1 регистровой памяти операнд Уо=А через1 о ключ 5, мультиплексор 3 принимается в регистр 12 адреса. В этом такте в блок 13 памяти весовых коэффициентом по адресу, составленному из старших разрядов числа Хо 2 выбирается значение 1/(Ко 2), которое записывается в регистр 8 коэффициентов. В десятом такте из старших разрядов регистра 10 произведение Хо 2 фф пересылается через мультиплексор 2 и блок 4 во второй регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение Уо2 и результат его записывается в старшие разряды регистра 10 произведения. В одиннадцатом такте произведение Уо 2", поступившее с регистра 10, в сумматоре-вычитателе складывается с содержимым первого регистра блока 1 регистровой памяти, и квадрат нормализованного модуля Ао2=2=2(Л+ Уо) записывается во второй регистр блока 1 регистровой памяти и через ключ 5, мультиплексор 3 - в регистр 12 адреса. В этом такте в умножителе 9 происходит умножение о 2" 1/(Хо 2") содержимых регистров числа 7 и коэффициентов 8, результат Уо/Хо которого записывается в младшие разряды регистра 10 произведений. Регистр 16 порядка пропускает на адресный вход блока 18 памяти констант минимальный порядок К чисез Уо и Хо и блок 8 памяти констант по адресу К выдает константу 2 ", которая записывается в регистр 8.В двенадцатом такте из блока 3 памяти весовых коэффициентов ио адресу, определяемому старшими разрядами сла А, 2 выбирается значение Ао 2"= Ао 2, которое, пройдя ключ 6, принимается в регистр 7 числа. В тринадцатом такте значение Ао 2=/А 2" поступает в умножитель 9 для денормализации путем умножения на коэффициент 2 ". Из регистра 8 коэффициентов результат умножения записывается в старшие разряды регистраО произведений. В этом такте с младших разрядов регистра 10 произведения через мультиплексор 3 в регистр 12 адреса записывается Уо/Ло. В четырнад атом такте искомое значение эпос(Ао)= А +Аофо оЛ+У со старших разрядов регистраО произведения через блок 4 и ключ 5 записывается в регистр 1 результата. В пятнадцатом такте на информационный выход 21 поступает гпофАо). В этом такте по ад 1633425ресу, соответствующему числу Ув/Х из блока 18 памяти весовых коэффициентов выбирается число агс 1 ф Уо/Хо), которое записывается в регистр 8 коэффициентов, из пятого регистра блока 1 регистровой памяти через сумматор-вычитатель 4 и ключ 5 коэффициент 1 записывается в регистр 7. В шестнадцатом такте число агс 1 ф Уо/Хо), умноженное на единицу, записывается в регистр О. В семнадцатом такте число из регистра 1 О произведения поступает на вход блока 4, на другой вход которого из третьего регистра блокарегистровой памяти поступает угол коррекции Н=О, и их сумма ф(Ао) =Йо+агс 1 д( Уо/Хо), равная углу вектора Ао относительно оси абсцисс, как результат записывается в регистр 1 результата. В регистр 19 записывается АВ восемнадцатом такте на информационный выход устройства 21 поступает фАп), а в нулевой регистр блока 1 регистровой памяти записывается новый операнд А, из входного регистра 19. Далее вычисления продолжаются с периодом шестнадцать тактов. Причем в случае, если А ( )О, А (О, то Х= - А, У=А, 1) = - 0,5; если А (О, А )О, то Х=Ау, У= - А,ц, Н=0,5 и если А 1 (О, А (О, то Л= - А, У=А, Ч= - . При этом при постоянной загрузке входного регистра 19 исходными данными А А . на информационный выход устройства 21 выдают каждые шестнадцать тактов результаты водА, и ц(А,). 51015 20 25 30 35 40 45 50 55 Вычисление логарифма числа в устройстве производится следуюгцим образом. В нулевом такте исходный операнд Л с информационного входа 20 принимается во входной регистр 19. В первом такте операнд Хо с выхода регистра 19 поступает в нулевой регистр блокарегистровой памяти, а также через ключ 5 и вход мультиплексора 3 записывается в регистр 12 адреса. Во втором такте шифратор 4 выдает порядок К числа Хо, который, записывается в регистр5 порядка. В третьем такте мультиплексор 16 порядка с выхо. да регистра 15 порядка пропускает порядок К, который является адресом для блока 18 памяти контакта, который выдает коэффициент 2" " в регистр 8 коэффициентов. В этом же такте Х из нулевого регистра блока 1 регистровой памяти переписывается в регистр 7 числа. В четвертом такте умножитель 9 вычисляет произведение Хо 2и нормализованный 1 аким образом операнд Х" 2" " записывается в регистр 10. В пятом такте операнд, равный Хо 2, пересылается из младших разрядов регистра 10 произведения в регистр 12 адреса. В шестом такте по старшим разрядам числа Хв 2, как по адресу из блока 3 памяти весовых коэффициентов выбирается и выдается коэффициент 1/16 од 2(Хо 2")=(Ф+ +од 2 Хо)/16, в котором пять старших разрядов являются логической единицей. Одновременно по адресу К, блок 18 памяти выдает константу К/16, одиннадцать младших разрядов которой являются логической единицей. Таким образом, поскольку выходы блока 8 памяти констант и блока 13 памяти весовых коэффициентов выполнены с открытым коллектором, коды, выдаваемые этими блоками одновременно, объединяются по монтажному ИЛИ и получаем результат од.Хв/16= (одМЛ 2) - й)/16, который поступает в регистр 11 результата. Новый операнд Х поступает из входного регистра 19 в нулевой регистр блокарегистровой памяти. Дальнейшая работа происходит аналогично. Вычисления продолжаются с периодом пять тактов.формула изобретенияУстройство для быстрого преобразования Фурье, содержащее входной регистр, блок регистровой памяти, три мультиплексора, арифметический блок, ключ, регистр числа, регистр коэффициента, умножитель, регистр результата, синхронизатор, генератор адреса, регистр адреса, блок постоянной памяти коэффициентов, двунаправленный ключ, шифратор, регистр порядка и блок сравнения, причем выход входного регистра подключен к первому информационному входу первого мультиплексора, выход которо. го подключен к первому информационному входу арифметического блока, выход которого подключен к информационным входач блока регистровой памяти и ключа, выход ко. торого по,включен к информационному входу регистра числа, выход которого подключеи к первому информационному входу умножителя, второй информационный вход которого подключен к выходу регистра коэффициента, выход генератора адреса яв. ляется адресным выходом устройства и подключен к первому информационному входу второго мультиплексора, выход которого подключен к информационному входу регистра адреса, выход которого подключен к адресному входу блока постоянной памяти коэффициентов, выход шифратора подключен к первому информационному входу третьего мультиплексора, первому входу блока сравнения и информационному входу регистра порядка, выход которого подключен к второму информационному входу третьего мультиплексора и второму входу блока сравнения, выход которого подключен к управляющему входу третьего мультиплексора, выход регистра результата является информационным выходом устройства, информационным входоч которого является информационный вход входного регистра, выходы синхронизатора с первого по третий подключены соответственно к первому, второму и третьему входам кода операцииарифметического блока, выходы синхронизатора с четвертого по шестой подключены соответственно к первому, второму входам кода адреса и входу управления записью- считыванием блока регистровой памяти, седьмой и восьмой выходы синхронизатора подключены соответственно к первому и второму управляющим входам первого мультиплексора, выходы синхронизатора с девятого по шестнадцатый подключены ссютветственно к управляющему входу второго мультиплексора, тактовым входам регистра числа, регистра коэффициента, регистра адреса, регистра результара, управляющему входу ключа, управляющему входу двунаправленного ключа, входу синхронизации умно- жителя, выходы синхронизатора с семнадцатого по двадцатый подключены ссютветственно к с первого по четвертый входам кода адреса блока постоянной памяти коэффициентов, выходы синхронизатора с двадцать первого по двадцать пятый подключены соответственно к входу выбора направления двунаправленного ключа, тактовым входам регистра порядка и входного регистра, первому и второму тактовым входам генератора адреса, установочный вход которого соединен с установочным входом синхронизатора и является установочным входом устройства, первым входом кода режима которого является первый вход кода режима синхронизатора, первый и второй выходы блока регистровой памяти подключены к вторым информационным входам соответственно арифметического блока и первого мультиплексора, отличающееся тем, что, с целью упрощения, оно содержит регистр произведения и блок постоянной памяти констант, выход которого подключен к инфор мационному входу регистра коэффициента ипервому информационному входу-выходу двунаправленного ключа, выход ключа соединен с выходом младших разрядов регистра произведения и подключен к информационному входу регистра результата, второму информационному входу второго мультиплексора и второму информационному входу-выходу двунаправленного ключа, выход старших разрядов регистра произведения подключен к третьему информационному входу 15 первого мультиплексора, выход регистраадреса подключен к входу шифратора, выход третьего мультиплексора подключен к адресному входу блока постоянной памяти констант, выход блока постоянной памяти коэффициентов подключен к информационному входу регистра коэффициента, выходы синхронизатора с двадцать шестого по тридцатый подключены соответственно к входу разрешения записи и входу разрешения чтения регистра произведения, первому, вто рому и третьему входам кода адреса блока постоянной памяти констант, знаковый выход арифметического блока и выход бло.ка сравнения подключены соответственно к второму и третьему входам кода режима синхронизатора, четвертый и пятый входы кода режима которого являются соответственно вторым и третьим входами кода режима устройства.Гоставитель А. БарановРедактор В. Данко Техред А. Кравчук Корректор А ОбручарЗаказ 619 Тираж 409 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ (Х.Р113035, Москва, Ж - 35, Раушская наб., д 4 5Производственно-издательский комбинат Патент, г Ужгород, ул. Гагарина, 1 О 1