Устройство для быстрого преобразования Фурье Советский патент 1991 года по МПК G06F15/332 

о со со

4 Ю СЛ

та, умножитель 9, регистр 10 произведения, регистр 11 результата, регистр 12 адреса, блок 13 постоянной памяти, шифратор 14, регистр 15 порядка, мультиплексор 16, блок 17 сравнения, блок 18 постоянной памяти констант, входной регистр 19, генератор 22 адреса, синхронизатор 26. 3 ил.

Изобретение относится к вычислительной технике и предназначено для построения систем цифровой обработки сигналов, основанных на выполнении алгоритма быстрого преобразования Фурье. Цель изобретения - упрощение устройства. Поставленная цель достигается за , что в состав устройства входят блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунаправленный ключ 6, регистр 7 числа, регистр 8 коэффициен

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

Целью изобретения является упрощение vci ройства

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

с; Аь+влчрц-вгчег,

Ц, Ал-Вц № + В Wz , С1 Аг+Вл Wt + ВТЩ, ; /} ЛГ-Я„« Г , ,

ые Сл, Cz , Оя , DJ - действительные и мнимые части преобразованных отсчетов соответственно;

А., А. , Вд , БТ - действительные и мнимые части исходных отсчетов,

Х и , Wj действительная и мнимая части весового коэффициента

Вычисление модуля и фаш производится по формулам., mo(M) vviJ-M; , (i/l arctg(/1z /Ац}

На фиг 1 показана структурная схема устройства для быстрого преобразования Фурье; на фиг 2 - структурная схема синхронизатора, на фиг 3 - структурная схема генератора адреса

Устройство для быстрого преобразования Фурье (фиг 1) содержит блок 1 регистровой памяти, мультиплексоры 2, 3, арифметический блок 4, ключ 5, двунаправленный ключ 6, регистр 7 числа, регистр 8 коэффициента, умножитель 9, регистр 10 произведения, регистр 11 результата, регистр 12 адреса, блок 13 постоянной памяти коэффициентов, шифратор 14, регистр 15 порядка, мультиплексор 16, блок 17 сравнения, блок 18 постоянной памяти констант, входной регистр 19, информационный вход 20, информационный выход 21, генератор 22 адреса, адресный выход 23, шины 24, 25 и синхронизатор 26

Синхронизатор 26 (фиг 2) содержит счетчик 27 адреса, мультиплексор 28 адреса, узел 29 памяти, выходы 30-59 и входы 60-65 синхронизатора.

Генератор 22 адреса (фиг. 3) содержит счетчик 66 базовых операций и формирователи 67, 68 адреса.

0

Работа устройства начинается при подаче сигнала на шину 60 начальной установки в нулевом такте. При этом по коду на шине 61 начального адреса микропрограммы, соответствующей заданному режиму работы, выбирается из узла 29 памяти микрокоманд первая микрокоманда микропрограммы выполнения этого режима, по которой в счетчик 27 адреса микрокоманд записывается начальный адрес микрокоман- 1.ы. После выполнения текущей микрокоманды в конце такта содержимое счетчика 27 увеличивается или заменяется новым из узла 29 памяти в случае безусловного перехода при единичном состоянии шины 62 признака при условном переходе. При сня5 тии сигнала на шине 60 устройство выполняет микрокоманды, выбираемые из узла 29 памяти микрокоманд по адресу из счетчика 27 адреса микрокоманды.

Генератор 22 адреса обеспечивает генерацию адресов считывания и записи данных

0 и считывания весовых коэффициентов в соответствии с алгоритмом быстрого преобразования Фурье с замещением и прореживанием но времени Счетчик 66 в начале выполнения алгоритма устанавливается в нулевое состояние сигналом на входе 60 и уве5 дичивает свое состояние на единицу с приходом сигнала на шину 58 в конце каждой базовой операции. Старшие разряды счетчика 66, начиная с п-го (где 2 - размер быстрого преобразования Фурье),

„ соответствуют номеру К итерации алгоритма. Формирователь 67 представляет собой мультиплексор, который в зависимости от кода (000 011) на входе 59 и номера итерации пропускает на выход 23 соответствующим образом циклически переставленные разряды

5 выхода счетчика 66 и тем самым формирует адрес операндов Ац ,ЛГ ,#„ ,BZ ,Сц ,Сг ,ОЯ ,DI. Формирователь 68 по коду ЮО на выходе 59 выдает на выход 23 разряды счетчика 66, маскированные кодом

Условимся, что при подаче кода 00 на

0 входы 64 и 65 режима синхронизатора 26 будет выполняться базозая операция быстрого преобразования Фурье, при подаче кода 01 - вычисление модуля и фазы, при подаче кода 10 вычисление логарифма. Рассмотрим работу строиства при вы5 полпенни базовой операции быстрого преобразования Фурье

В нулевом такте по сигналу на входе 60 генератор 22 адреса устанавливается в начальное состояние нулевой базовой операции. По коду 100 на входе 59 генератор 22 адреса выдает на вход 23 ноль-адрес весового коэффициента WQ, который, пройдя через вход мультиплексора 3, записывается в регистр 12 адреса. На информационный вход 20 поступает операнд В$о .

В первом такте по коду 000 на вход 59 генератор 22 адреса выдает на адресный выход 23 устройства адрес операнда ВЯо , по которому внешним ЗУ с произвольной выборкой считывается из блока 13 постоянной памяти коэффициентов, по нулевому адресу выбирается коэффициент W 1, который через шину 25 записывается в регистр 8 коэффициентов. Операнд Вца нулевой базовой операции поступает во входной регистр 19.

Во втором такте генератор 22 адреса по коду 001 на входе 59 выдает на адресный выход 23 адрес операнда В1д . В этом такте операнд В1о поступает через вход 20 в регистр 19, операнд В/ из которого, пройдя мультиплексор 2 и блок 4, переписывается в нулевой регистр блока 1 регистровой памяти и, пройдя ключ 5, записывается в регистр 7.

В третьем такте в умножителе 9 происходит умножение ВКд -Wft , результат которого поступает в регистр 10 произведений. В регистр 8 коэффициентов из блока 13 памяти коэффициентов записывается WIg , в регистр 7 числа через коммутатор 2, блок 4, ключ 5 из регистра 19 переписывается операнд В1о .

В четвертом такте произведение ВЯв , пройдя через мультиплексор 2 и блок 4, поступает в первый регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение В WI , результат которого поступает в регистр 10 произведений. В регистр 8 записывается коэффициент W/fc .

В пятом такте произведение В. ИЈ поступает в блок 4, где происходит выч°и- тание выражения - BIg Wrg + В„0 W , поступившего туда с первого регистра блока 1 регистрации памяти В/о Wlo . В умножителе 9 происходит умножение fi WJO и результат записывается в регистр 10 произведений.

В шестом такте генератор адреса по коду 010 выдает адрес операнда Ак , результат вычитания В#0 WKo -BIo Wlo писывается в первый регистр блока 1 регистровой памяти. На информационный вход 20 поступает операнд АЯо , который записывается в регистр 19. Вйо пересылается из нулевого регистра блока 1 регистровой памяти 1 через блок 4 и ключ 5 в регистр 7, из блока 13 памяти коэффициентов коэффициент W записывается в регистр 8.

В седьмом такте операнд Ац0 из входного регистра 19 поступает в блок 4, где

он суммируется регистра блока

с содержимым первою 1 регистровой памяти

АКп + ВЯо W. -BIo W. СЯо и первый Ре

-VMo

зультат СЯо , пройдя ключ о, описывается в регистр 11 результата

В восьмом такте генератор адреса по коду 000 выдает адрес результата, и результат СЛд выдается из регистра Ml результата на выход 21. В блоке 4 вычисляется выражение Айо -

-Bj tt ) который, пройдя ключ г, записывается в регистр 11.

В девятом такте генератор ОН) адреса выдает адрес результата и ОЛо поступает на информационный выход устройства 21

Произведение Вт Х Яо , пройдя через блок 4, поступает в первый регистр блока I регистровой памяти. В умножителе 9 происходит умножение WIo . реилыаг которого записывается в регистр К) произведений

0

В десятом такте генератор 22 адреса по коду 001 выдает адрес Ах , операнд А1о поступает в регистр 19. В блоке 4 происходит суммирование В Х Xj. . 5 результат которого записывается в первый регистр блока 1.

В одиннадцатом такте А{ поступает в блок 4, где он суммируется с содержимым первого регистра блока 1 регистровой памяти AIo + BJo УЛо + йДр U To CJfl , и ре- 0 зультат записывается в регистр 11.

В двенадцатом такте генератор адреса выдает адрес С1о , и в регистр 1 1 записывается операнд Cz . В блоке 4 происходит вычитание А, - (Вт Ч , U 1 пТоID опо ID

-LJJr,

5 В тринадцатом такте генератор адреса

выдает адрес DJ. и на информационный выход устройства 21 поступает последний результат О1о . На тактовый генератор 22 адреса поступает импульс для вычисления адресов следующей базовой операции

В четырнадцатом такте из генератора 22 адреса адрес нового коэффициента IV | через мультиплексор 3 записывается к регистр 12 адреса, и вычисления повторяются с периодом 14 тактов

5 Г3ассмотрим работу при вычислении модуля и фазы комплексного числа.

В нулевом такте число 0,5 выдается из блока 18 памяти констант и записывается в четвертый регистр блока 1 регистровой памяти. В первом такте число 0,5 из чет0 вертого регистра блока 1 регистровой памяти поступает в блок 4, где суммируется с ним же, и в пятый pei истр блока 1 регистровой памяти записывается число 1 Числа 1 и 0,5 соответствуют фазам и и необходимы для коррекции

5 результата вычисления фазы. Через информационный вход 20 устройства во входной регистр 19 поступает реальная часть А#с . Во втором такте через информационный вход

устройства 20 во входной регистр 19 поступает мнимая часть операнда А1о , с входною регистра 19 реальная часть АКо проходит мультиплексор 2, блок 4, записывается в нулевой регистр блока 1 регистровой памяти I, а также, пройдя ключ 5, мультиплексор 3, записывается в регистр 12 адреса При этом следующая микрокоманда выбирается в учетом знака Ад0 , поступающего по входу 61 в синхронизатор 26 В третьем такте мнимая часть операнда А1о с входного регистра 19 через блок 4 поступает в первый регистр блока 1 регистровой памяти и в регистр 12 адреса Порядок Кк , т е число незначащих цифр справа перед значащей цифрой операнда Ад , поступающего из регистра 12 адреса, через шифратор 14 записывается в регистр 15 порядка Следующая микрокоманда также выбирается из узла 29 памяти с учетом знака А , и так образуются четыре ветви микропрограммы, каждая us которых выбирается в зависимости от комбинации знаков исходных данных Ац и А.,

ПУСТЬ и А1о 0, тогда дальнейшую работ) устройство продолжает следующим обра юм В четвертом такте порядок A j числа AJ с выхода регистра 12 адреса через шифратор 14 и порядок Кц числа Адо с выхода регистра 15 порядка поступают на входы блока 17 сравнения и мультиплексора 16 порядка, блок 17 сравнения анализирует порядки Кк и Л. и под em управлением мультиплексор 16 порядка по сшналу 63 пропускает минимальный из поря IKOB Л миш Д д ,Aj ) на адресный вход блока 18 памяти констант, считанный из него коэффициент 2 - 16 записывается в ре- истр 8 коэффициентов При этом порядок Л равен числу разрядов, на которое необходимо сдвинуть влево Ад и AJ для их нормализации

В третий регистр блока 1 регистровой памяти из блока 4 описывается поправка H(h В пятом такте из нулевого регистра блока 1 регистровой памяти через блок 4 и ключ 5 в регистр 7 числа поступает В шестом такте из первого регистра блока 1 регистровой памяти через блок 4 и ключ 5 в регистр 7 поступает В умножителе 9 происходит умножение An-2 1П, результат которого записывается в регистр 10 произведений В седьмом такте из регистра 10 произведение, равное Ао-2, поступает в регистр

7числа, через ключ 6 - в регистр 8 коэффициентов, а через вход мультиплексора 3в регистр 12 адреса В умножителе 9 происходит умножение и записывается в регистр 10 произведения

8восьмом такте из регистра 10 младшие разряды произведения, равного Ко-2 пересылается в регистр 7 числа и через

ключ 6 - в регистр 8 коэффициентов. В умножителе 9 происходит умножение операндов и произведение Ло-22 записывается в старшие разряды регистра 10 произведения. В девятом такте из блока 13 памяти весовых коэффициентов по адресу из регистра 12 адреса выбирается коэффициент, равный 1/Х-2, который записывается в регистр 8. Из первого регистра блока 1 регистровой памяти операнд К0-ЛТо через ключ 5, мультиплексор 3 принимается в регистр 12 адреса В этом такте в блок 13 памяти весовых коэффициентом по адресу, составленному из старших разрядов числа АО-2 выбирается значение 1/(/0-2), которое записывается в регистр 8 коэффициентов

В десятом такте из старших разрядов регистра 10 произведение А0-2 пересылается через мультиплексор 2 и блок 4 во второй регистр блока 1 регистровой памяти. В умножителе 9 происходит умножение Ко-2 и результат его записывается в старшие разряды регистра 10 произведения. В одиннадцатом такте произведение Kfj-2 1, посту5 пившее с регистра 10, в сумматоре-вычи- тателе складывается с содержимым первого регистра блока 1 регистровой памяти, и квадрат нормализованного модуля Ло-22 2 NA o+ Ко) записывается во второй регистр блока 1 регистровой памяти и через ключ

0 5, мультиплексор 3 - в регистр 12 адреса. В этом такте в умножителе 9 происходит умножение (А 0-2) содержимых регистров числа 7 и коэффициентов 8, результат Ко/АО которого записывается в младшие разряды регистра 10 произве5 дений Регистр 16 порядка пропускает на адресный вход блока 18 памяти констант минимальный порядок К чисел Ко и А п и блок 18 памяти констант по адресу К выдает константу 2,

Q в регистр 8

В двенадцатом такте из блока 13 памяти весовых коэффициентов по адресу, определяемому старшими разрядами числа Ло-2 выбирается значение Л0-2 у/4о -2г, которое, пройдя ключ 6, принимается в ре5 гистр 7 числа В тринадцатом такте значение Ai,- 2 jAn-22k поступает в умножитель 9 для денормализации путем умножения на коэффициент 2 Из регистра 8 коэффициентов результат умножения записывается в старшие разряды регистра 10

0 произведений В этом такте с младших разрядов регистра 10 произведения через мультиплексор 3 в регистр 12 адреса записывается КО/АО В четырнадцатом такте искомое значение mod(/4o)V/4j-h / Ко со старших разрядов0 регистра 10 произведения через блок 4 и ключ 5 записывается в регистр 11 результата В пятнадцатом такте на информационный выход 21 поступает mod(Ao) В этом такте по адкоторая записывается

ресу, соответствующему числу J o/A из блока 18 памяти весовых коэффициентов выбирается число arctg(), которое записывается в регистр 8 коэффициентов, из пятого регистра блока 1 регистровой памяти через сумматор-вычитатель 4 и ключ 5 коэффициент 1 записывается в регистр 7. В шестнадцатом такте число arctgi Ко/Ао), умноженное на единицу, записывается в регистр 10 В семнадцатом такте число из регистра 10 произведения поступает на вход блока 4, на другой вход которого из третьего регистра блока I регистровой памяти поступает угол коррекции , и их сумма (p(/4o)eo+arctg( Ко/Ао), равная углу вектора АО относительно оси абсцисс, как результат записывается в регистр 11 результата В регистр 19 записывается Am

В восемнадцатом такте на информационный выход устройства 21 поступает ((А), а в нулевой регистр блока 1 регистровой памяти записывается новый операнд А из входного регистра 19 Далее вычисления продолжаются с периодом шестнадцать тактов Причем в случае, если Ая 0, Аг 0, то , ,5, если 0. , то , , ,5 и если Айо 0, А1о 0, то Х - А.. , При этом при постоянной загрузке входного регистра 19 исходными данными /V , А. на информационный выход устройства выдают каждые шест надцать тактов результаты mod/4, и q:(A)

Вычисление логарифма числа в устройстве производится следующим образом В нулевом такте исходный операнд Аи с ин формационного входа 20 принимается во входной регистр 19 В первом такте операнд АО с выхода регистра 19 поступает в нулевой регистр блока 1 регистровой памяти, а также чере ключ 5 и вход мультиплексора 3 записывается в регистр 12 адреса Во втором такте шифратор 14 выдает порядок К числа А0, который, записывается в регистр 15 порядка В третьем такте мультиплексор 16 порядка с выхода регистра 15 порядка пропускает порядок К, который является адресом для блока 18 памяти контакта, который выдает коэффициент в регистр 8 коэффициентов В этом же такте А о из нулевого регистра блока 1 регистровой памяти переписывается в регистр 7 числа В четвертом такте умножитель 9 вычисляет произведение и нормализованный таким образом операнд записывается в регистр 10 В пятом такте операнд, равный АО-2, пересылается из младших разрядов регистра 10 произведения в регистр 12 адреса В шестом такте по старшим разрядам числа АО-2, как по адресу из блока 13 памяти весовых коэффициентов выбирается и выдается коэффициент l/16log2((Ј + -Hog2A o)/16, в котором пять старших раз

рядов являются логической единицей Одновременно по адресу К, блок 18 памяти выдает константу К/16, одиннадцать младших разрядов которой являются логической

единицей Таким образом, поскольку выходы блока 18 памяти констант и блока 13 памяти весовых коэффициентов выполнены с открытым коллектором, коды, выдаваемые этими блоками одновременно, объединяются по монтажному ИЛИ и получаем результат log7Ao/16(log2(An-2k)- /г)/16, который поступает в регистр 11 результата Новый операнд AI поступает из входного регистра 19 в нулевой регистр блока I ре гистровой памяти Дальнейшая работа происходит аналогично Вычисления продолжаются с периодом пять тактов

Формула изобретения

0Устройство для быстрого преобразования Фурье, содержащее входной регистр, блок регистровой памяти, три мультиплексора, арифметический блок, ключ, регистр числа, регистр коэффициента, умножитель,

5 регистр результата, синхронизатор, генератор адреса, регистр адреса, блок постоянной памяти коэффициентов, двунаправленный ключ, шифратор, регистр порядка и блок сравнения, причем выход входного регистра подключен к первом) информационном) вхо0 ду первого мультиплексора, выход которого подключен к первом) информационном) вход) арифметического блока, выход которого подключен к информационным входам блока регистровой памяти и ключа, выход ко торого но лючен к информационном) вхо5 Д) регистра числа, выход которою подключен к первому информационном) вход умножителя, второй информационный вход которого подключен к выход) регистра ко эффициента, выход генератора адреса яв ляется адресным выходом устройства и подключен к первом) информационном) вхо ду второго мультиплексора, выход которого подключен к информационному вход) регист-- ра адреса, выход которого подключен к ад ресном) входу блока постоянной памяти ко

5 эффициентов, выход шифратора подключен к первому информационном) вход) третьего мультиплексора, первому входу блока срав нения и информационному входу регистра порядка, выход которого подключен к второму информационном) вход) третьего

0 мультиплексора и втором) входу блока сравнения, выход которого подключен к п равляющем) входу третьего мультиплексора, выход регистра результата является информационным выходом устройства, информа ционным входом которою является инфор5 мационный вход входного регистра, выхо ды синхронизатора с первого по третий подключены соответственно к первому, второму и третьему входам кода операции

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

6

Sit

5

0

5

0

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

61

27

V

29

o6V -о 63

v

V

X 59

Фиг 2

Фигз