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

Изобретение относится к вычислительной технике, в частности к устройствам, выполняющим операцию быстрого преобразования Фурье (БПФ) .массива чисел размерностью Л, где Л 2, г 1,2,3,...

Целью изобретения является расширение области применения за счет вычисления преобразования произвольной размерности V ( 2).

На фиг. I приведена функциональная схема устройства; на фиг. 2 - схема формирователя адреса; на фиг 3 - схема арифметического блока.

Процессор (фиг 1) содержит формирователи 1 адреса, шин 2 входных данных, выход 3 формирователя 1 адреса, коммутатор 4 адреса, выход 5 формирователя 1 адреса, выход 6 ПЗУ управления, блок 7 постянной памяти (ПЗУ) управления, выход 8 коммутатора 4 адреса, блок 9 памяти, выход 10 ПЗУ управления, выход 11 смотчика 12, элемент ИЛИ 13, выход 14 ПЗУ управления, выход 15 формирователя 1 адресов, племен/ И 16, вход 17 дешифратора 1м, вход 19 формирователей адреса, элемент si 20. выход 21 ПЗУ управления, тактовый вход 22, ныход 23 формирователя 1 адреса, блок 24 постоянной памяти коэффициентов, выход 25 блока 24 постоянной памяти, pei истры 26 и 27, выход 28 формирователя I, рсмисгры 29-32, выход 33 дешифратора 18. выходы 34 и 35 ПЗУ управлении, входы 36 41 арифметического бло ка 42, выходы 43 и 44 ПЗУ управления, выход 45 дешифратора 18. регистры 46 -49, выходы )0 и 51 ПЗУ управления, выходы 52 - 55 арифмеш кчкою блока, информационный выход Г)6 процессора

Формирователь 1 адреса (фит 2) со- дер/киг LVMMamp 5Г, дешифратор 58, зел 59 постоянной памяти, регистры 60 и 61 и элемент И h2

Арифметический блок 42 (фиг 3) содержит коммутатор ()3 трип ер 64 знака, функциональный преобразователь 65 и сумма- тор 66

Процессор работает следующим образом

Исходное состояние устанавливается каждый раз пос те окончания цикла автоматически. В исходном состоянии регистры 60 и 61 формирователей 1 адреса и регистры 26. 27, 30 32, 46 -49 процессора установлены в нулевое состояние. На шину 2 входных данных поступают операнды т,п), .n), ,n), т де т - количество строк в матрице;

п количество элементов в строке;

/1 базовый адрес, | и смещение

На вход 22 поступают тактовые импульсы. Дешифратор 58 формирователя 1 адреса принимает код команды и выдает сиг- нал ра (решения на элементы И 62 формирователя 1 адреса и элемента И 16 процессора С выхода 21 блока 7 поступает

0

5

0

0

5

5

0

5

сигнал разрешения на элемент И 20, на входы 19 формирователей 1 адреса, и в регистры 61 этих формирователей соответственно записывается информация из входных операндов. С выхода регистра 61 информация (ш,п) поступает на входы соответствующих узлов 59 формирователей 1 адреса. На выходах 3, 5 и 23 формирователей 1 адреса появляются адреса первых элементов массивов (); (B-f-61); (). На вход элемента И 20 с выхода 21 блока 7 поступает сигнал запрещающего уровня. Адреса (/4-f-al), (B + b) с выходов 3 и 5 формирователей 1 адреса соответственно поступают в коммутатор 4 ад- реса. Адрес с выхода 23 формирователя 1 адреса поступает на вход блока 24 постоянной памяти. Коммутатор 4 адреса поочередно коммутирует адреса i 4+al| и в блок 9 памя.тц, с выхода которого комплексные числа А,В, соответствующие этим адресам, записываются в регистры 29, 30 и 31, 32, причем в регистры 30 и 32 записываются реальные части комплексных чисел, а в регистры 29 и 31 - мнимые. С выхода 25 блока 24 постоянной памяти комплексное число Q, соответствующее адресу , записывается в регистры 26 и 27. В регистр 27 - записывается реальная часть, а в регистр 26 - мнимая. На входы управления записью-сдвигом регистров 26, 27, 29 - 32 поступает код записи с выходов 35 и 34 блока 7, а на тактовый вход покупают тактовые импульсы с выхода 33 дешифратора 18. По окончании записи с выходов 35 и 34 блока 7 на регистры 26, 27, 29-32 поступает код сдвига, с выхода 33 дешифратора 18 - импульсы сдвига, количество которых равно разрядности числа Числа из регистров 26, 27, 29-32 последовательным кодом считываются одновременно в арифметический блок 42. На вход арифметического устройства поступает код операции (КОП) и маркер М - признак начала счета с выхода 43 блока 7, а на другой вход - сигнал разрешения записи КОП с выхода 45 дешифратора 18. Из знаковых разрядов регистров 26, 27, 29- 32 поступает сигнал знака на триггеры знака арифметического блока 42 по входам 36- 41. Арифметический блок 42 последовательно-параллельного типа, может быть произвольным по выполнению.

Существует два вида вычислителей базовой операции БПФ - с прореживанием по частоте схемы арифметического блока 42. Построение схемы может быть выполнено произвольно, включая оба вида обработки или один из них для универсального вычислителя и любой вид обработки для специализированного вычислителя. Арифметический блок, выполненный согласно фиг. 3, может одновременно обрабатывать три комплексных числа, выполняя базовую

операцию вычисления БПФ с прореживанием по частоте. С выходов 52-55 арифметического блока 42 результаты вычислений в виде комплексных чисел А и В последовательным кодом соответственно записываются в регистры 46-49, причем в регистры 46 и 49 записываются реальные части, а в регистры 47 и 48 - мнимые. Количество тактовых импульсов, необходимых для записи чисел А и В, равно разрядности этих чисел.

С приходом с выхода 10 блока 7 сигнала записи эти числа записываются поочередно в блок 9 памяти, число В за- цисывается по адресу (, затем число А - по адресу {/4+а1}. Затем с выхода 14 блока 7 поступает сигнал установки нуля и через элемент ИЛИ 13 устанавливает в ноль счетчик 12, а с выхода 21 блока 7 на элемент И 20 поступает сигнал разрешения и по следующему тактовому импульсу на выходах 3, 5 и 23 формирователей 1 адреса появятся адреса (А+а2, {В+Ь2 и {Q+q2. Цикл счета для /-Й итерации повторяется до тех пор, пока не вычислятся все элементы массива для данной итерации, и продолжается по всем итерациям.

Количество циклов в итерации и количество итераций определяются из данных операнда т,п. По окончании счета последнего элемента последней итерации на выходе 28 формирователя 1 адреса вырабатывается импульс конца программы и устанавливает в ноль регистры 60 и 61 формирователя 1 адреса, счетчик 12, регистра 26, 27, 29-32. Результаты вычислений накапливаются в блоке 9 памяти по адресам, заданным первым и вторым формирователями 1 адреса.

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике, в частности к устройствам, выполняющим быстрое преобразование Фурье массивов различной размерности. Цель изобретения - расширение функциональных возможностей за счет вычисления преобразования произвольной размерности. Цель достигается за счет того, что в состав процессора входят три формирователя 1 адреса, коммутатор 4, блок 24 постоянной памяти коэффициентов, блок 9 памяти, счетчик 12, элемент ИЛИ 13, элемент И 16, дешифратор 18, элемент И 20, блок 7 постоянной памяти, регистры 26, 27, 29-32, арифметический блок 42, регистры 46-49. 1 з. п. ф-лы, 3 ил. Ј / о со со ю о