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

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

Цель изобретения - повышение точности вычислений,

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

Устройство для быстрого преобразования Фурье содержит блок 1 регистровой памяти, умножитель 2, регистры 3 и 4 числа и коэффициента, первый и второй регистры 5 и 6 результата, первый и второй сумматоры-вычитате- ли 7 и 8,с первого по четвертый мультиплексоры 9-12, регистр 13 адреса, блок 14 памяти весовых коэффициентов блок 15 сдвига, блок 16 памяти значений арктангенса, ключи 17-19 с трехстабильным состоянием, ключ 20, шифратор 21 порядка, регистр 22 порядка, блок 23 сравнения, мультиплексор 24 порядка, синхронизатор 25, элемент И 26, элемент ИЛИ 27, инфор- мационные вход 28 и выход 29 устройства, адресный вход 30, вход-выход 3 порядка устройства, первую, вторую и третью общие шины 32-34.

Блок 15 сдвига (фиг,2) содержит регистр 35 операнда, выходной ключ 36, регистр 37 кода сдвига, сдвига- тель 38, Синхронизатор 25 (фиг,3) содержит счетчик 39 адреса микрокоманды, мультиплексор 40 адреса микрокоманды и узел 41 памяти микрокоманды, группы выходов которого с первой по четвертую 42 - 45 и выходы которого с первого по тридцатый. 46 - 75, вход 76 сброса, вход 77 установки, 78 запуска.

Работа устройства начинается при подаче сигнала на шину 76 начальной установки. При этом по коду на шине 77 начального адреса микропрограммы, соответствуюш1ей заданному режиму работы, выбирается из узла 41 памяти микрокоманд первая микрокоманда микропрограммы выполнения этого режима по которой в счетчик 39 адреса микро команд записывается начальный адрес микропрограммы. После выполнения текущей микрокоманды в конце такта содержимое счетчика 39 увеличивается

0

5 ,

5

0

5

0

или заменяется новым из узла 41 в случае безусловного перехода при единичном состоянии шины 78 признака при условном переходе. При снятии сигнала на шине 76 устройство выполняет микрокоманды, выбираемые из узла 41 памяти микрокоманд по адресу из счетчика 39 адреса микрокоманды.

Рассматривае.тс я работа устройства при выполнении базовой операции БПФ, В первом такте в регистр 13 адреса записывается ноль-адрес весового коэффициента нулевой базовой операции с шины 30, В этом же такте с умматор- вычитатель 8 выдает код единицы во всех разрядах, который соответствует числу 2 в прямом коде и записывается в третий регистр блока 1 регистровой памяти. Во втором такте из блока 14 памяти весовых коэффициентов по нулевому адресу выбирается коэффициент WP 1, которьш через, шину 32, ключ 20 записывается во второй регистр - блока 1 регистровой памяти, В третьем такте на шину 28 данных поступает операнд BQ нулевой базовой операции,

По

которьш, пройдя коммутатор, сумматор- вычитатель 8 и мультиплексор 10, записывается в нулевой регистр блока 1. , Ана логично в четвертом такте операнд Bj с шины 29 записывается в первый .регистр блока 1 , В этом же такте коэффициент W, записьгоается из блока 14 памяти весовых коэффициентов в регистр 4 коэффициента, а операнд В, из регистра Р1,0 .пересылается в регистр 3 числа через первый выход блока 1 регистровой памяти, В пятом такте происходит умножение с учетом знаков содержимого регистра 3 на содержимое регистра 4 в умножителе 2 и произведение В W , пройдя сумма- тор-вычитатель 7, записывается в первый регистр 5 результата, В этом же такте коэффициент Wj из блока 14 переписывается в регистр 4, а затем в регистр 3 из регистра Р1,1 пересылается операнд Bj , В шестом такте умножитель 2 получает произведение В/о Wr«, из которого вычитается на сумматоре-вычитателе 7 содержимое регистра 5 и результат В, W. В„ „

- о to о. ч

записывается в регистр 5, в регистр 3 из регистра Р1.2 пересылается число 1, а в регистр 4 через мультиплексоры 10 и 12, сумматор-вычитатель 8, ключ 20 поступает с входной шины 28

операнд А,

В седьмом такте из неиз312871

менного после умножения на 1 операн- да Арр вычитается на сумматоре-вычи- тателе 7 содержимое регистра 5 и первый результат нулевой базовой операции Сп А„ +В „ W - Bj. W. записывает-r

о Р-о о о to о ося в регистр 5, а в регистр 3 записывается из регистра 3 код числа 2. В восьмом такте А, умножается в прямом коде на число 2 на умножителе 2 и на первый вход сумматора-вычитате- ю ля 7 поступает код числа 2А. , из

которого вычитается число С, из регистра 5, и в регистр 5 записывается второй результат D к к о В, Wr , а результат Со через второй J5

о 0 .,°

вход мультиплексора 11 пересылается во второй регистр 6 результата. В этом же такте в регистр 3 записывается из блока 1 число Вр , а в регистр 4

К ft

записывается число W из блока 14. 20 Б девятом такте результат С. выдает о

ся В выходную шину 29, результат D,.

с

пересылается из первого регистра 5 результата во второй регистр 6 результата, произведение В. W, записьша- 25

г ° ° 1 /

ется в регистр 5, а в регистры J и 4 записываются операнды В, и Wj соответственно из блоков 1 и 14. В десятом такте полученная на умножителе 2 и сумматоре-вычитателе 7 30 сумма произведений В. W, +В, W

1,

«о

записывается в регистр 5,° результат Ьд выдается на выход 29, в регист р 3, записывается число 1, а в регистр 4 записыв ается операнд Aj , поступив- 35 ший с входной шины 28, В этом же такте в регистр 13 адреса записываются с шины 30 адреса весового коэффициента для новой базовой операции. В одиннадцатом такте А j складьгоается 40 на сумматоре-вычитателе 7 с содержимым регистра 5, в который в конце такта записывается третий результат С, А , + В„-У, +В, Wo в регистр

т -о Jo УО in lo 0 -

J из блока 1 пересылается число 2, 45 а в нулевой регистр блока 2 из входной шины 28 записывается новое данное Вр для следующей базовой операции. В двенадцатом такте умножитель 2 производит умножение в прямом коде one- 50 ранда А на число 2, из произведений 2Aj вычитается результат С. на сумматоре-вычитателе 7 и последн ий результат D А В W( -В.- W записывается в регистр §, Cj из ко°- 55 торого пересылается в регистр 6. В этом же такте регистры 3 и 4 записы-; вают новые операнды В H-W соответственно, а в первый регистр Р1.1

871

-r

ю

J5

я

20

25

30

35 40

45 . 5055

754

блока I записывается новое данное Bj , поступившее на вход 28 устройства. Далее работа устройства продолжается аналогично с периодом восемь тактов. При этом при ритмичном поступлении на вход 28 исходных данных Bjj ,3, , А, А;, а на вход 30 - адресов весовых коэффициентов W на выходе 29 появляются результаты соответственно С,. , Dg. , С , Dj.

Вычисление БПФ в устройстве для повышенной точности производится с -поблочно плавающей запятой. Для этого существует две микропрограммы для вычисления базовой операции БПФ, которые отличаются лишь тем, что в одной мультиплексор 10 пропускает операнды без сдвига, а во второй - со сдвигом на один разряд в сторону младших разрядов для уменьшения операнда вдвое. Первая микропрограмма задается в случае невозможности переполнения разрядной сетки в процессе вычисления, а иначе задается вторая микропрограмма. Для определения возможности переполнения результаты пре- дащущей итерации БПФ анализируются схемой, состоящей из шифратора 21 порядка, регистра 22 порядка, блока 23 сравнения, мультиплексора 24 порядка, элементов К 26 и ИЛИ 27 на наличие незначащих разрядов перед старшим значащим разрядом. Это происходит следующим образом. При поступлении Ср на выход 29 количество в нем незнач°ащих цифр (порядок) записывается в регистр 22 при единичном сигнале на шине 70 как начальное значение для сравнения. По мере поступления следующих результатов на выход 29 блок 23 сравнения сравнивает минимальный порядок, зафиксированный в регистре 22 с порядком текущего результата, и если текущий порядок меньше, он записывается в регистр 22 при единичном и нулевом сигналах на шинах 69 и 70 соответственно. В конце выполнения итераций БПФ в регистре 22 оказывается порядок максимального числа в массиве результатов, которьш указывает масштаб массива результатов и который по сигналу на шине выдается через мультиплексор 24 порядка на шину 31 входа- выхода порядка. В следующей- итерации, если зафиксирован нулевой порядок, задается микропрограмма базовой операции БПФ5 в которой мультиплексор 10 сдвигает исходные данные вправо.

5 , 12 Рассматривается работа устройства при вычислении модуля и фазы комп- . лексного числа. В первом такте в регистр 13 адреса записывается нулевой адрес, по которому во втором такте из блока 14 памяти весовых коэффициентов выбирается число 1, которое через ключ 20 записывается в четвертый регистр (Р1.4) блока 1 регистровой памяти, в третьем такте число 1 из регист ра Р1,4, пройдя сумматор-вычитатель 8, сдвигается вправо на мультиплексор 10 и полученное таким образом число 0., 5 записывается в третий регистр (Р1,3) блока 1. Числа 1 и 0,5 соответ ствуют фазам и и необходимы для коррекции результата вычисления фазы. В четвертом такте на вход 28 устройства поступает реальная част нулевого операнда А , которая про-

О

ходит мультиплексор 12, С5 матор-вы- читатель 8, мультиплексор 10 и записывается в нулевой регистр блока 1, а также, пройдя мультиплексор 11, записывается в регистр 6. При этом еле- дующая микрокоманда выбирается с учетом знака А. , поступающего по шине 78 в синхронизатор 25. В пятом такте мнимая часть операнда А с входа 28 поступает в первый регистр блока 1 и в регистр 6, порядок К., операнда А-

КK(j

поступающего на выход 26 из регистра 6, записывается в регистр 22 порядка. Следующая микрокоманда также выбирается из узла 41 с учетом знака А и таким образом, образуются четыре ветви микропрограммы, каждая из которых выбирается в зависимости от комбинации знаков исходных данных А и AJ . Пусть А g 0; А : О, тог- да устройство дальнейшую работу продолжает следующим образом. В шестом такте порядок К, числа А, с выхода

Lkg

регистра 6 и порядок К g числа А с выхода регистра 22 поступают на входы блока 23 сравнения и мультиплексора 24 порядка, который пропускает минимальный из порядков К, - (К-, К.) на вход регистра 37 парамет1

ра сдвига блока 15 сдвига, где он хранится до следующего цикла вычисления модуля и фазы. При этом порядок К равен числу разрядов, на которые необходимо сдвинуть влево А и AJ для их нормализации. В

такте Х. -А„ из регистра Р1.0 блока

ь 1 регистров, пройдя сумматор-вычитатель 8, мультиплексор 10, ключ 20, записывается в регистр 35 блока 15

75 6 сдвига. В девятом такте Х из регистра 35, пройдя сдвигатель 38 и ключ 36, выдается в шину 32 сдвинутым на К разрядов влево и число записывается в регистр 4, через ключ 18 - в регистр 3, а через вход мультиплексора 9 - в регистр 13. В этом же такте-коррекция записывается во второй регистр (Р1.2) блока 1. В десятом такте А, Y из регистра Р1.1 пересылаете в блок 15 сдвига. В одиннадцатом такте операнды из регистров 3 и 4 перемножаются на умноа г2,к

жителе 2 и произведение } -2 через сумматор-вычитатель 7 записывается в регистр 5. Уд 2 из блока 15 сдвига пересылается в регистры 3 и 4. В двенадцатом такте произведение Yg- 2 складывается с содержимым регистра 5 и квадрат нормализованного модуля А (Х + Y) записывается в регистр 5, в этом же такте из блока 14 памяти весовых коэффициентов по адресу, составленному из старших разрядов числа Х 2 выбирается значение 1/(Х 2 ), которое пересылается в регистр 4. Новый операнд А из шины 28 записывается в нулевой регистр блока 1 и в регистр 6. В тринадцатом такте из блока 16 памяти значений арктангенса по адресу, определяемому старшими разрядами числа АО 2 , выбирается значение А,-2 , которое загружается в блок 15 сдвига для денормализации путем сдвига вправо на К ра зрядов. В этом же такте новый операнд А записывается в первьш регистр блока 1 и в регистр 6. В четырнадцатом такте искомое значение mod(A) из блока сдвига пересылается в ре-

Iгистр 6 результата, а в регистр 37 параметра сдвига записывается новое значение К, произведение содержимого

регистров 3 и 4 Y, 2 1/(Х„ 2) записывается в регистр 5. В пятнадцатом такте по адресу, соответствующему числу X/Y из блока 16 значений арктангенса выбирается число arctg(), которое через ключ 18 поступает на первый вход сумматор Бычитателя 8, на второй вход которого из регистра Р1.2 поступает угол коррекции и их сумма 1(Ад)©„ +

Y- + arctR - ,

ЛА

равная угла комплексного

вектора. А относительно оси абсцисс, как результат записывается в регистр

71

6 результата. Далее вычисления про- должаются с периодом в восемь тактов Если А , О, AJ 0, то , -0,5, если Aft О, А , . О, то X А,, .Y -АИ, 0 и,5 и если , А i О,, то X -А, , . При этом при постоянной загрузке входной шины 28 исходными данными А , А на выходную шину 29 выдаются каждые восемь тактов результаты mod А и ССА.).

Вычисление логарифма числа в устройстве производится следующим образом. В первом такте исходньй операнд Хо с входной шиной поступает в нулевой регистр блока 1 регистров, а так же через первый вход мультиплексора 11 записывается в регистр 6. Во втором такте порядок К числа Х записывается в регистр 22 порядка. В третьем такте, поскольку на выходе 69 элемента И 26 нулевой сигнал, мультиплексор 24 с выхода регистра,22 пропускает порядок К,-который записывается в регистр 37 параметра сдвига блока 15 сдвига, а также через ключи 19 и 20 поступает в первый регистр блока 1 регистров.. В четвертом такте Хо из нулевого регистра блока 1 пересылается в блок 15 сдвига. В пятом такте сдвинутый операнд Хо 2 пересы лается из блока 15 сдвига в регистр 13 адреса, новый операнд X поступает с шины 28 в нулевой егистр блока 1.. В шестом такте по старшим разрядам числа Х 2 , как по адресу, из блока 14 выбирается коэффициент log (Хд 2 )K+Iog Х,который, пройдя ключ 18, поступает на первый вход сумматора-вычитателя 8, на второй вход которого поступает из первого регистра блока 1 число К, и после вычитания на выходе сумматора-вычитателя 8 получается результат log Х I.og( 2)-К, который через мультиплексоры 10 и 11 поступает во второй регистр результата, В этом же такте в регистр 22 записывается порядок нового операнда X и вычисления про- должаются с чшриодом четыре такта.

Вследствие масштабирования при

вычислении ПБФ с поблочно плавающей запятой массивы результатов, подлежащих дальнейшему усреднению, имеют различные порядки и поэтому ус- реднение следует также вести с поблочно плавающей запятой. В зависимости от соотношения порядков усредненного массива 1 и массива текуще175

го среднего А возможны две микропрограммы. При вычислении по первой миропрограмме порядок массива А оказывается меньшим порядка массива 1. В первом такте адресного входа 30 усройства в регистр 13 адреса записы- вается код текущего количества усренений т. Во втором такте по адресу га выбирается из блока 14 значение 1/т, которое пересылается в нулевой регистр блока 1 регистровой памяти, а в регистр 13 адреса записывается ноль. В третьем такте в регистре 37 параметра сдвига блока 15 сдвига с шины 31 входа-выхода порядка записывается разность порядков К массивов Аи 1. Из кода единицы, поступившего с выхода блока 14 через ключ 18 на первый вход сумматора-вычитателя 8, вычитается число 1/т, Хранящееся в нулевом регистре блока 1, и полученный коэффициент 1-1/т записывается в первый регистр блока 1. В четвертом такте с входа 28 устройства операнд А. через мультиплексоры 12 и 10, сумматор-вычитатель 8, ключ 20 поступает в блок 15 сдвига. В пятом такте в регистр 4 из блока 15 пересылается вправо сдвинутый операнд Ад 2 , а в регистр 3 пересылается из первого регистра блока 1 коэффициент 1-1/т. В шестом такте операнд 1 с шины 28 записывается в регистр 4, а в регистр 3 из нулевого регистра блока 1 пересылается коэффициент 1/т. В этом же такте полученное умножителем 2 произведение (1-1/т) записывается в первый регистр 5 результата, В седьмом такте сумматор-вычитатель 7 складывает содержимое регистра 5 с произведением , полученным умножителем 2, и результат (1-1/т)+1о/ш записывается в регистр. 5 а в блок 15 сдвига поступает новый операнд А . В восьмом такте результат Д пересылается из первого регистра 5 результата во второй регистр 6 результата, а в регистр 4 пересылается из блока 15 сдвига новый операнд A-J. 2 и дале вычисления продолжают с периодом в

три такта. 1

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

9.12

1/m, в пятом такте 1 с входа 28 поступает Б блок 15 сдвига, произведение Аа() записывается в регистр 3. В шестом такте в регистр 4 пересылается из блока 15 сдвига сдвипутый

-- „ - к

вправо операнд i i , а в регистр j записыйается коэффициент 1/m. В седьмом такте результата А.А ,(1-1/т) + +2 1„/т записывается в регистр, новый операнд А поступает в регистр 4 В седьмом такте результат А пересылается из регистра 5 в регистр 6 и вычисления повторяют аналогично с периодом три такта.

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

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

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

.

1112

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

15

7175

5012

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

25

35

77

25

- H uiJ-Vyj

иг.2

Устройство относится к области вычислительной техники и предназначено для построения систем цифровой обработки сигналов, основанных на вы- полнении быстрого преобразования Фурье. Цель изобретения - повьшение точности вычислений. Поставленная цель достигается за счет того, что устройство содержит блок 1 регистровой памяти, умножитель 2, регистр 3 числа, регистр 4 коэффициента, два регистра 5,6 результата, два сумматор а- в ычита те ля 7,8, мультиплексоры 9-12, регистр адреса, блок памяти ;весовых коэффициентов, блок сдвига, блок 16 памяти значений арктангенса, три трехстабильных ключа 17-19, ключ 20, шифратор 21 порядка, регистр 22 порядка, блок 23 сравнения, мультиплексор 24 порядка, синхронизатор, элемент И 26, элемент ИЛИ и соответ- -ствующие связи между узлами устройства. 4 ил. (Л to 00 сл Фт1 6)

59

37

J5

58

38

.61

3ff

60

33 Фиг.З

фиг.1