Устройство для быстрого преобразования фурье
Изобретение относится к вычислительной технике и предназначено для построения систем цифровой обработки сигналов, основанных на выполнении алгоритма быстрого преобразования Фурье. Цель изобретения - упрощение устройства. Поставленная цель достигается за , что в состав устройства входят блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунаправленный ключ 6, регистр 7 числа, регистр 8 коэффициен
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51)5 G 06 F 15 332
< iдц1Д
1 к, ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (21) 4660801/24 (22) 10.03.89 (46) 07.03.91. Бюл. № 9 (7I ) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Ю. С. Каневский, М. К. Клименко, Л. М. Логинова и А. М. Сергиенко (53) 681.32 (088.8) (56) Авторское свидетельство СССР № 1206902, кл. G 06 Е 15/332, 1986.
Авторское свидетельство СССР № 1287175, кл. G 06 F 15/332, 1987.
ÄÄSUÄÄ 1633425 А 1
2 (54) УСТРОЙСТВО ДЛ Я БЪ|СТРОГО
ПРЕОБРАЗОВАНИЯ ФУРЬЕ (57) Изобретение относится к вычислительной технике и предназначено для построения систем цифровой обработки сигналов, основанных на выполнении алгоритма быстрого преобразования Фурье. Цель изобретения упрошение устройства. Поставленная цель достигается за счет того, что в состав устройства входят блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунаправленный ключ
6, регистр 7 числа, регистр 8 коэффициен1633425 та, умножитель 9, регистр 10 произведения, регистр 1 результата, регистр 12 адреса, блок 13 постоянной памяти, шифратор 4, регистр 15 порядка, мультиплекИзобретение относится к вычислительной технике и предназначено для построения систем цифровой обработки сигналов, основанных на выполнении алгоритма быстрого преобразования Фурье.
Целью изобретения является упрощение устройства.
Устройство иредназначе lo для выполнения базовой операции быстрого преобразования Фурье
CR As+BR A7R f3Z К
l)„=А„— BR Ц +В lY, С,=А,+В„Ц +В, lV; где <".„, (".,, D, D действительные и мнимые части иреобразова и н ы х отс чето в с оотнетстненно;
А, А . В„, Вд -- действительные и мнимые части исходных отсчетов; (1R « - !ействительная и мнимая части весового коэффи циеита.
Вычис.<ение модуля и фазы ироизнодится II<) формулам
murliA <= Ay+ A, ;
<(<41=<< r<- tg(4< /Л ).
На фиг. показана структурная схсма устройства для быстрого преобразования
Фурье; на фиг. 2 — структурная схема синхронизатора; иа фиг. 3 структурная схема генератора адреса.
Устройство для быстрого преобразования
Фурье (фиг. ) содержит блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунапранлеиный ключ 6, регистр 7 числа, регистр 8 коэффициента, умножитель 9, регистр 10 произведения, регистр 1! результата, регистр 12 адреса, блок 13 постоянной памяти коэффициентов, шифратор 14, регистр 15 порядка, мультиплексор 16, блок 17 сравнения, блок
18 постоянной памяти констант, входной регистр !9, информационный нход 20, информационный выход 21, генератор 22 адреса, адресный выход 23, шины 24, 25 и синхронизатор 26.
Синхронизатор 26 (фиг. 2) содержит счетчик 27 адреса, мультиплексор 28 адреса, узел 29 памяти, выходы 30 59 и нходы 60 — 65 синхронизатора.
Генератор 22 адреса (фиг. 3) содержит счетчик 66 базовых операций и формиронатели 67, 68 адреса.
55 сор 16, блок 17 сравнения, блок 18 постоянной памяти констант, входной регистр
19, генератор 22 адреса, синхронизатор 26.
3 ил.
Работа устройства начинается при подаче сигнала на шину 60 начальной установки в нулевом такте. При этом по коду на шине 61 начального адреса микропрограммы, соответствующей заданному режиму работы, выбирается из узла 29 памяти микрокоманд первая микрокоманда микропрограммы выполнения этого режима, по которой н счетчик 27 адреса микрокоманд записывается начальный адрес микрокоманды. После выполнения текущей микрокоманды в конце такта содержимое счетчика
27 увеличивается или заменяется новым из узла 29 памяти в случае безусловного перехода при единичном состоянии шины 62 признака ири условном переходе. При снятии сигнала на шине 60 устройство выполняет микрокоманды, выбираемые из узла
29 памяти микрокоманд ио адресу из счетчика 27 адреса микрокоманды.
Генератор 22 адреса обеспечивает генерацию адресов считывания и записи данных и считывания весовых коэффициентов в со<ти«тстнии с алгоритмом быстрого преобразования Фурье с замещением и ирореживаиием но времени. Счетчик 66 в начале выполнения алгоритма устанавливается в нулевое состояние сигналом на входе 60 и увеличинает свое состояние на единицу с приходом сигнала на шину 58 в конце каждои базовой операции. Старшие разряды счетчика 66, начиная с п-Io (где 2" размс р быстрого преобразования Фурье), соответствуют номеру К итерации алгоритма.
Формирователь 67 IIð«.k«òанляет собой мультиплексор, который в зависимости от кода (000...011) на входе 59 и номера итерации и роиускает на выход 23 соотнетствующи м образом цикличе< ки иер»ставленные разряды ныхода счетчика 66 и тем самым формиру «т dдрес опера ндон 4R Àz,ËR,В,,CR,Ñz,DR,D,.
Формирователь 68 ио коду 100 на выходе
59 выдает на выход 23 разряды счетчика 66, маскиронанныс ко.<ом.
Условимся, vT Рассмотрим работу устройства ири выполнении базовой <шерации бы Tpoko преобразования Фурье. В нулевом такте ио сигналу на входе 60 генератор 22 адреса устанавливается в на! 633425 20 чальное состояние нулевой базовой операции. По коду 100 на входе 59 генератор 22 адреса выдает на вход 23 ноль-адрес весового коэффициента >и, который, пройдя через вход мультиплексора 3, записывается в регистр 12 адреса. На информационный вход 20 поступает операнд В)4 . В первом такте по коду 000 на вход 59 генератор 22 адреса выдает на адресный выход 23 устройства адрес операнда В, по которому внешним ЗУ с произвольйой выборкой считывается из блока 13 постоянной памяти коэффициентов, по нулевому адресу выбирается коэффициент Ж„ = I, который через шину 25 записывается в регистр 8 коэффициентов. Операнд В)1, нулевой базовой операции поступает во входной регистр 19. Во втором такте генератор 22 адреса по коду 001 на входе 59 выдает на адресный выход 23 адрес операнда В . В этом до такте операнд В, поступает через вход 20 в регистр 19, операнд В из которого, пройдя мультиплексор 2 и блок 4, переписывается в нулевой регистр блока 1 регистровой памяти и, пройдя ключ 5, записывается в регистр 7. В третьем такте в умножителе 9 происходит умножение Во, . W«, результат которого поступает в регйстр 10 произведений. В регистр 8 коэффициентов из блока 13 памяти коэффициентов записывается и до в регистр 7 числа через коммутатор 2, блок 4, ключ 5 из регистра 19 переписывается операнд В В четвертом такте произведение Вд, IV пройдя через мультиплексор 2 и блок 4, поступает в первый регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение В ° W результат котоо рого поступает в регистр 10 произведений. В регистр 8 записывается коэффициент 1У В пятом такте произведение В Ф о поступает в блок 4, где происходит вычитание выражения — В W +В>1 йо, подо до ><о Оо ступившего туда с первого регистра блока 1 регистрации памяти В„, Ф . В умножителе 9 происходит умножеййе В, Ж и результат записывается в регистр 10 произведений. В шестом такте генератор адреса по коду 0IO выдает адрес операнда Ао 4о результат вычитания В>о, Кр, — Вд й<д, записывается в первый регистр блока регистровой памяти. На информационный вход 20 поступает операнд А«, который записывается в регистр 19. В) пересылается из нулевого регистра блока l регистровой памяти 1 через блок 4 и ключ 5 в регистр 7, из блока 13 памяти коэффициентов коэффициент wl записывается в регистр 8. В седьмом такте операнд Ао, из входного регистра 19 поступает в блок 4, где 55 он суммируется с содержимым перв(н о регистра блока 1 регистровой п„<÷я)u А +В К вЂ” В и =Ср, и первыи р«зультат С о, пройдя ключ 5, записын;)<<ся в регистр ll результата В восьмом такте генератор адреса по коду 000 выдает адрес р lbT3T3 зультат С,) выдается из регистра .11 рео зультата на выход 21. В блоке 4 вычисляется выражение Л>) —,В,д йд — В Ф )=0>, который, пройдя клк>ч о, 33до до о писывается в регистр 11. В девятом такте генератор 010 адреса выдает адрес результата и О о поступает на информационный выход устройства 21. Произведение В й<, пройдя через блок 4, до „o поступает в первый регистр блок» I регистровой памяти. В умножителе 9 происходит умножение В, и . p(.3),>û;Iã кото))о до рого записывается в регистр 10 произведений В десятом такте генератор 22 адреса по коду 001 выдает адрес Лд, операнд Ад о поступас T в регистр 19. В блоке 4 llpoисходит суммирование В и +Л) и оо о 1о „ Рс3)< . В одиннадцатом такте А поступает в о блок 4, где он суM÷èðóåòñÿ с содержиMblvI первого регистра блока 1 p< I I В двенадцатом такте генерат<)р адр» 3 выдает адрес С, и в регистр 11 запи<ывается операнд С . Б блоке 4 происход.т в.)ч.тан.е Ат — Вд k +В>3 до до до В тринадцатом такте генератор <3.1р< «;l выдает адрес 0 и 113 информ,)ц ионный выхо1 устройства 2! поступ<1(1 последний pе 3 v . В четырнадцатом такге из генератора 22 адреса адрес нового коэффици«нта й" через мультиплексор 3 записываегся <3 р»гистр 1 2 адреса, и вычисления II()I)ò<>p)lloòся с периодом 14 тактов. Рассмотрим работу при вычислении модуля и фазы комплексного числа. В нулевом такте число 0,5 вы.<ается из блока 18 памяти констант и .<апнсывается в четвертый регистр блока 1 регистровой памяти. В первом такте число 0,5 из четвертого регистра блока 1 регистровой Il<3мяти поступает в блок 4, г.lе сумм и рл е гся с ним же, и в пятый регистр блока 1 регистровой памяти записывается число I. Числа и 0,5 соответс)вуют фазам ()=181) и ()=90 и неооходимы для корр<. кции результата вычисления фазы. Через информационный вход 20 устройства во вхо.1ной регистр 19 поступает реальная часть .4g Во втором такге через информаци<>нный нх<>д 1633425 15 устройства 20 во входной регистр !9 поступает мнимая часть операнда А, с вход о ного регистра 19 реальная часть А проходит мультиплексор 2, блок 4, запйсывается в нулевой регистр блока 1 регистровой памяти l, а также, пройдя ключ 5, мультиплексор 3, записывается в регистр ! 2 адреса. При этом следующая микрокоманда выбирается в учетом знака А о поступающего ио входу 61 в синхронизатор 26. В гретьем такте мнимая часть операнда А, с входного регистра 19 через блок 4 поступает в первый регистр блока 1 регистровой памяти и в регистр 12 адреса. Порядок К, т. е. число незначащих цифр справа перед значащей цифрой операнда А, поступающего из регистра 12 адреса, через шифратор 14 записывается в регистр 15 порядка. Гледуюгцая микрокоманда также выбирается из узла 29 памяти с учетом знака А, и так образуто ются четыре ветви микропрограммы, каждая из которых выбирается в зависимости от комбинации знаков исходных данных А,( и А l lусть Л, )О и А )О, тогда дальнейшук> работу устройство продолжает следую<ням образом. В четвертом такте порядок К числа Ад с выхода регистра о 12 адреса через шифратор 14 и порядок К числа А,! с выхода регистра 15 порядка поступают на входы блока 17 сравнения и мультиплексора !6 порядка, блок 17 сравнения анализирует порядки kR и Кд и иод его управлением мультиплексор 16 порядка Il<> си< налу 63 пропускает минимальный из порядков k =v><>«k,К ) на адресный вход блока 18 памяти констант, считанный из него коэффициент 2" — 16 записывается в ре< истр 8 коэффициентов. При этом порядок К ранен чис.>у разрядов, на которое необходимо сдвинуть влево Ag и А О Т<> для и. нормализации. В третий регистр блока 1 регистровой памяти из блока 4 записывается поправка )=0 . В пятом такте из нулевого регистра блока 1 регистровой памяти через блок 4 и ключ 5 н регистр 7 числа поступает Л,=А . В шестом такте из первого регистра блока 1 регистровой памяти через блок 4 и ключ 5 в регистр 7 иосTóïàåò Yo:Az . В умножителе 9 происходит умножение Ли 2 г, результат которого записывается в регистр 0 произведений. В седьмом такте из регистра 0 произведение, равное Л<> 2", поступает в регистр 7 числа, через ключ 6 в регистр 8 коэффициентов, а через вход мультиплексора 3 в регистр 12 адреса. В умножителе 9 происходит умножение У<> 2 и записывается в регистр 10 произведения. В восьмом такте из регистра 10 младшие разряды произведения, равного Уи 2л, пересылается в регистр 7 числа и через 55 ключ 6 — в регистр 8 коэффициентов. В умножителе 9 происходит умножение операндов и произведение ХΠ— 2" записывается в старшие разряды регистра 10 произведения. В девятом такте из блока 13 памяти весовых коэффициентов по адресу из регистра 12 адреса выбирается коэффициент, равный 1/Х.2", который записывается в регистр 8. Из первого регистра блока 1 регистровой памяти операнд Yo=Aт через Уо ключ 5, мультиплексор 3 принимается в регистр 12 адреса. В этом такте в блок 13 памяти весовых коэффициентом по адресу, составленному из старших разрядов числа Х,> 2 выбирается значение 1/(Po 2 ), которое записывается в регистр 8 коэффициентов. В десятом такте из старших разрядов регистра 10 произведение ХО 2 пересылается через мультиплексор 2 и блок 4 во второй регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение Yoо ° 2 и результат его записывается в старшие разряды регистра 10 произведения. В одиннадцатом такте произведение Vo.2 ", поступившее с регистра 10, в сумматоре-вычитателе складывается с содержимым первого регистра блока 1 регистровой памяти, и квадрат нормализованного модуля Ao ° 2 = J/ 1 =2- (Л<>+ Vo) записывается во второй регистр блока 1 регистровой памяти и через ключ 5, мультиплексор 3 — в регистр 12 адреса. В этом такте в умножителе 9 происходит умножение У<>.2" 1/(Xo 2") содержимых регистров числа 7 и коэффициентов 8, резул ьтат Vo/Х<> которого з апис ываетс я в младшие разряды регистра 10 произведений. Регистр 16 порядка пропускает на адресный вход блока 18 памяти констант минимальный порядок К чисез У<> и Хо и блок !8 памяти констант по адресу К выдает константу 2 ", которая записывается в ре гист р 8. В двенадцатом такте из блока 13 памяти весовых коэффициентов ио адресу, определяемому старшими разрядами сла А<>.2- выбирается значение Ао 2"= А<1 2 ", которое, пройдя ключ 6, принимается в регистр 7 числа. В тринадцатом такте знаГ чение А > 2 =>/Ао 2" поступает в умножитель 9 для денормализации путем умножения на коэффициент 2 ". Из регистра 8 коэффициентов результат умножения записывается в старшие разряды регистра !О произведений. В этом такте с младших разрядов регистра 10 произведения через мультиплексор 3 в регистр 12 адреса записывается Yo/Ëo. В четырнад атом такте искомое значение mod(Ao)= А +А ° ) е Л >+ V<> со старших разрядов регистра ! 0 произведения через блок 4 и ключ 5 записывается в регистр 1! результата. В пятнадцатом такте на информационный выход 2l поступает mod(Ao). В этом такте по ад1633425 Формула изобретения ресу, соответствующему числу Yp/Xp из блока l8 памяти весовых коэффициентов выбирается число arctg(Yp/Х«), которое записывается в регистр 8 коэффициентов, из пятого регистра блока 1 регистровой памяти через сумматор-вычитатель 4 и ключ 5 коэффициент 1 записывается в регистр 7. B шестнадцатом такте число arctgi « «/Xp), умноженное на единицу, записывается в регистр 10. В семнадцатом такте число из регистра 10 произведения поступает на вход блока 4, на другой вход которого из третьего регистра блока регистровой памяти поступает угол коррекции Н=О, и их сумма В восемнадцатом такте на информационный выход устройства 21 поступает <т<(А«), а в нулевой регистр блока 1 регистровой памяти записывается новый операнд А, из входного регистра 19. Далее вычисления продолжаются с периодом шестнадцать тактов. Причем в случае, если А )0, А (О, то Х= — Ад, « =А), 8= — 0,5; если А (О Адо )О, то Х=Адо « = „о 1-)=0,5 и если А1, (0, Ад (О, то Х= — А . Y=A>, (9= — l. !1ðè этом ири постоянной загрузке входного регистра 19 исходными данными А<<<, А . на информационный выход устройства 21 выдают каждые шестнадцать тактов результаты modA, и <г(А,). Вычисление логарифма числа в устройстве производится следуюгцим образом. В нулевом такте исходный операнд Х< с информационного входа 20 принимается во входной регистр 19. В первом такте операнд Х«с выхода регистра 19 поступает в нулевой регистр блока регистровой памяти, а также через ключ 5 и вход мультиплексора 3 записывается в регистр 12 адреса. Во втором такте шифратор 4 выдает порядок К числа Х<>, который. записывается в регистр 15 порядка. В третьем такте мультиплексор 16 порядка с выхода регистра 15 порядка пропускает порядок К, который является адресом для блока 18 памяти контакта, который выдает коэффициент 2" " в регистр 8 коэффициентов. В этом же такте Х«из нулевого регистра блока 1 регистровой памяти переписывается в регистр 7 числа. В четвертом такте умножитель 9 вычисляет произведение Х«2 и нормализованный 1аким образом операнд Х" 2" " записывается в регистр 10. В пятом такте операнд, равный Хо 2", пересылается из младших разрядов регистра 10 произведения в регистр 12 адреса. В шестом такте по старшим разрядам числа Х«2, как по адресу из блока 13 памяти весовых коэффициентов выбирается и выдается коэффициент 1/16!од (Х«2")=(Ф+ +)ogqXp)/16, в котором пять старших раз20 55 рядов являются логической единицей. Одновременно по адресу К, блок 18 памяти выдает константу К/16, одиннадцать младших разрядов которой являются логической единицей. Таким образом, поскольку выходы блока 18 памяти констант и блока 13 памяти весовых коэффициентов выполнены с открытым коллектором, коды, выдаваемые этими блоками одновременно, объединяются по монтажному ИЛИ и получаем результат !од Х«/16= (!од<(Х«.2 ) — й)/16, который поступает в регистр 11 результата. Новый операнд Х< поступает из входного регистра 19 в нулевой регистр блока регистровой памяти. Дальнейшая работа происходит аналогично. Вычисления продолжаются с периодом пять тактов. Устройство для быстрого преобразования Фурье, содержащее входной регистр, блок регистровой памяти, три мультиплексора, арифметический блок, ключ, регистр числа, регистр коэффициента, умножитель, регистр результата, синхронизатор, генератор адреса, регистр адреса, блок постоянной памяти коэффициентов, двунаправленный ключ, шифратор, регистр порядка и блок сравнения, причем выход входного регистра подключен к первому информационному входу первого мультиплексора, выход которого подключен к первому информационному входу арифметического блока, выход которого подключен к информационным входач блока регистровой памяти и ключа. выход которого ио,<ключен к информационному входу регистра числа, выход которого подключеи к первому информационному входу умножителя, второй информационный вход которого подключен к выходу регистра коэффициента, выход генератора адреса является адресным выходом устройства и подключен к первому информационному входу второго мультиплексора, выход которого подключен к информационному входу регистра адреса, выход которого подключен к адресному входу блока постоянной памяти коэффициентов, выход шифратора подключен к первому информационному входу третьего мультиплексора, первому входу блока сравнения и информационному входу регистра порядка, выход которого подключен к второму информационному входу третьего мультиплексора и второму входу блока сравнения, выход которого подключен к управляющему входу третьего мультиплексора, выход регистра результата является информационным выходом устройства, информационным входоч которого является информационный вход входного регистра, выходы синхронизатора е первого по третий подключены соответственно к первому, второму и третьему входам кода операции l633425 30 59 Фиг 2 арифметического блока, выходы синхронизатора с четвертого по шестой подключены соответственно к первому, второму входам кода адреса и входу управления записьюсчитыванием блока регистровой памяти, седьмой и восьмой выходы синхронизатора подключены соответственно к первому и второму управляющим входам первого мультиплексора, выходы синхронизатора с девятого по шестнадцатый подключены ссютветственно к управляющему входу второго мультиплексора, тактовым входам регистра числа, регистра коэффициента, регистра адреса, регистра результара, управляющему входу ключа, управляющему входу двунаправленного ключа, входу синхронизации умножителя, выходы синхронизатора с семнадцатого по двадцатый подключены ссютветственно к с первого по четвертый входам кода адреса блока постоянной памяти коэффициентов, выходы синхронизатора с двадцать первого по двадцать пятый подключены соответственно к входу выбора направления двунаправленного ключа, тактовым входам регистра порядка и входного регистра, первому и второму тактовым входам генератора адреса, установочный вход которого соединен с установочным входом синхронизатора и является установочным входом устройства, первым входом кода режима которого является первый вход кода режима синхронизатора, первый и второй выходы блока регистровой памяти подключены к вторым информационным входам соответственно арифметического блока и первого мультиплексора, отличающееся тем, что, с целью упрощения, оно содержит регистр произведения и блок постоянной памяти констант, выход которого подключен к инфор5 мационному входу регистра коэффициента и первому информационному входу-выходу двунаправленного ключа, выход ключа соединен с выходом младших разрядов регистра произведения и подключен к информационному входу регистра результата, второму информационному входу второго мультиплексора и второму информационному входу-выходу двунаправленного ключа, выход старших разрядов регистра произведения подключен к третьему информационному входу 15 первого мультиплексора, выход регистра адреса подключен к входу шифратора, выход третьего мультиплексора подключен к адресному входу блока постоянной памяти констант, выход блока постоянной памяти коэффициентов подключен к информационному входу регистра коэффициента, выходы синхронизатора с двадцать шестого по тридцатый подключены соответственно к входу разрешения записи и входу разрешения чтения регистра произведения, первому, вто25 рому и третьему входам кода адреса блока постоянной памяти констант, знаковый выход арифметического блока и выход блока сравнения подключены соответственно к второму и третьему входам кода режима синхронизатора, четвертый и пятый входы кода режима которого являются соответственно вторым и третьим входами кода режима устройства. 1633425 Гоставитель А. Баранов Редактор В. Ланко Техред А. Кравчук Корректор А Обручар Заказ 619 Тираж 409 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ((.(.Р 113035, Москва, Ж вЂ” 35, Раушская наб., д. 4 5 Производственно-издательский комбинат «Патент», г Ужгород, ул. Гагарина, 101
