Устройство для вычисления коэф-фициентов фурье

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистическик

Республик

К АВТОВО(ОМУ СВМДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву

Р2) Заявлено 280379 Р1) 2743465/18-24 (51) М. КЛ. с присоединением заявки Ио

G 06 F 15/332

Государственный комитет

СССР по делам изобретений н открытий (23) Приоритет

Опубликовано 1-5.0381, Бюллетень Ж 10

Дата опубликования описания 15.0381 (53) УДЫ 681, 14 (088. 8) Г б В ° (72) Автор изобретения

В.Д.Гусев

Специальное конструкторское бюро - BHe;porIPH6op производственного Объединения "Виброприбрр" (71) Заявитель (5 4) УСТРОЙСТВО ДЛЯ ВИЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ

ФУРЬЕ

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

Однако данные процессоры сложны и громоздки. Их громоздкость определяется многосекционностью и обилием коммутаций, которые, в свою очередь, вызваны использованием алгоритма Кули-Тычки — самого неудобного для регистрового исполнения процессора, Наиболее близким по техническому решению к предлагаемому является устройство для вычисления коэффициентов Фурье, содержащее арифметический .блок, управляющий вход которого соединен с выходом генератора тригонометрических функций, блок управления, N-разрядные регистры сдвига, триггер, элементы 11 записи, элемент

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

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

813447 ственно с выходами второго, четвер-. того, первого и третьего элементов

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

И записи соединены с информационными входами N/2+1 разрядов соот-. ветствующих регистров сдвига, счетный вход триггера соединен со вторым выходом блока управления, третья группа выходов которого соединена с управляющими входами генератора тригонометрических функций.

В устройстве заложен алгоритм Стокхэма-Санди, что позволило: резко сократить схему и выполнить ее односекционной. Это стало возможным благодаря полупостоянству структуры графа Стокхэма, в каждом участке которого, характеризующем соответствующую итерацию, операнды пар результатов базовых операций располагаются с расстоянием в пол-массива друг от друга: И этот порядок не меняется от итерации к итерации (2).

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

Нужно отметить, что рисунок,ле. вых сторон участков графа Стокхэема идентичен в той же части алгорйтму

Кули-Тычки (с децимацией по времени), поэтому если применить для регисзгрового БПФ алгоритм с полностью. постоянной структурой участка его графа, то устройство неизбежно окажется проще, чем известное. Таким алгоритмом является алгоритм

Синглетона, представляющий собой полную противоположность алгоритму

Кули-Тычки. Если структура участков графа Кули-Тычки абсолютна непостоянна, и поэтому лучшей реализацией алгоритма является процессор с ОЗУ произвольной выборки, то для

t0

$0

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

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

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

И подключен к первым входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен ко вторым входам третьего и четвертого элементов ИЛИ и управляющим входам первого и второго регистров сдвига, а выход четвертого элемента И соединен со вторыми входами первого и

S 813447 6 второго элементов ИЛИ и управляющими входами третьего и четвертого регистров сдвига.

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

В связи с тем, что в однородном графе

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

На фиг.l приведена схема устройства; на фиг.2 — пример алгоритма

Синглетрна.

Устройство содержит.п-разрядные регистры 1,2,3 и 4 сдвига (n=n/2), выходы 5 и 6,регистров и соответственно первый и второй входы арифметического блока 7, арифметический блок 7, выходы 8 и 9 арифметического блока и соответственно входы записи первых (шнна 8) и - - +1 (шина 9) разрядов регистров, тактовые входы

10,11,12 и 13 регистров и соответственно выходы узла 14 тактирования, узел 14 тактирования, формирователь тригонометрических коэффициентов, выход 16 формирователя 15 и соответственно третий вход блока 7, итерационный регистр 17, тактовый вход .

18 итерационного регистра 17 и соответственно выход сигнала смены .состояния счетчика 19, счетчик 19 с количеством разрядов log N выход

20 итерационного регистра и соответственно шина окончания цикла БПФ, управляющие входы 21 и 22 регистров, выходы 23 и 24 старшего разряда счетчика (прямой и инверсный); выходы 25 и 26 младшего разряда счетчИса (прямой и инверсный) элементы

27,28,29 и 30 И узла тактирования, элементы 31 32 33 и 34 ИЛИ узла тактирования.

На фиг.2 показан пример алгоритма Синглетона для массива чисел объемом N=8. Здесь входной массив чисел представляется в двоично-инверсном виде, причем в регистре 1, куда за. б5 переталкивает единичный сигнал регистра 17 в его следующий разряд.

Описанный расклад потенциалов .соответствует нулевому состоянию старшего разряда счетчика 19. При его единичном состоянии потенциальная писывается первая половина массива, сосредотачиваются все четные отсчеты, а в регистре 2, куда подается вторая половина массива - все нечетные, Эти полумассивы формируются во входном устройстве процессора (не показано) g вводятся в устройство одновременно с выводом из него ре зультата обработки предйдущего массива. Номера итераций на графе

1< обозначены вверху римскими цифрами. Контурные (толстые) линии обозначают умножение соответствующего числа на единицу а тонкие линии— е

Мак умножение числа на коэффициент W где Ю=ехр(-. 2)Г/Щ, la (A

Устройство работает следующим образом.

25 B исходном состоянии счетчик 19 сброаээн в 0, в первый разряд обнуленного-перед этим итерационного регистра 17 записана l, а в регистры 1 и 2 занесен исходный

3() числовой массив. Единичный потенциал шины 24 дает разрешение для непрерывного тактирования регистров

1 и 2 (тактовые импульсы через элемент 30 И и элементы 31 и 32 ИЛИ проходят на тактовые входы 10 и ll) и разрешение записи в регистры 3 и

4 (единичный потенциал приходит науправляющий вход 22 регистров 3 и 4).

В то же время нулевой потенциал шины 22 запрещает по управляющему входу

4() 21 режим записи в регистры 1 и 2 и составляет возможность тактирования регистров 3 и 4 в зависимости от состояния младшего разряда (шины

25 и 26) счетчика 19. В итоге регист45 ры 1 и 2 тактируются непрерывно, выталкивая в блок 7 пары операндов до полного своего опустошения.

Регистры 3 и 4 тактируются выборочно, работая лишь на запись, так как пе5О ред началом итерации они были пустыми. Запись s регистр происходит лишь при,наличии потенциала на. его управляющем входе и импульса на тактовом входе. Время итерации определяется промежутком между соседними сменами состояния старшего разряда счетчика

19г ноля на единицу, либо единицы на ноль . Каждая такая смена сопровождается выделением на шину 18 импульса, который

813447 формирователь тригонометрических коэффициентов, итерационный регистр, счетчик, узел тактирования, состоящий из четырех элементов И и четырех элементов ИЛИ, причем первые входы элементов И объединены и являются первым тактовым входом устройства, тактовый вход счетчика является вторым тактовым входом устройства, выход счетчика соединен со входом итерационного регистра., первый выход которого подключен ко входу формирователя тригонометрических коэффициентов, выход которого соединен со входом задания коэффициентов арифметического блока, первый и второй выходы которого соединены со вхоцами соответственно первых п/2 и последних n/2 разрядов четырех регистров сдвига, выходы первого и третьего регистра сдвига объединены, под2О ключены к первому входу арифметического блока и являются первым выходом устройства, выходы второго и четвертого регистра сдвига объединены, подключены ко второму входу арифметического блока и являются вторым выходом устройства, тактовые входы регистров сдвига соединены с выходами соответствующих элементов

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

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

4 тактирования, выход первого элемента И подключен к первым входам второго и четвертого элемента ИЛИ, выход второго элемента И подключен к первым входам первого и третьего элементов ИЛИ, выход третьего элемента И подключен ко вторым входам третьего и четвертого элементов ИЛИ и управляющим входам первого и второго регистров сдвига, а выход четвертого элемента И соединен со вто55 рыми входами первого и второго элементов ИЛИ и управляющими входами третьего и четвертого регистров сдвига. регистра сдвига, арифметический блок, картина устройства меняется на противоположную. Пара регистров 1 и 2 и пара, 3 и 4 меняются ролями. Каждая итерация продолжается N/2 тактов.

На тактовые входы регистровой пары, находящейся в режиме выдачи, приходит за итерацию N/2 импульсов, а на входы регистров занесения — n/2 импульсов каждому. Но так как записывается сразу по 2 числа, то к моменту окончания итерации регистры занесения оказываются полностью заполненными. При этом регистры выдающей пары работают одновременно, а регистры принимающей пары работают по оче реди, сменяясь с каждым тактом. Например, первым (от исходного состояния) тактовым импульсом по переднему фронту в арифметический блок 7 выталкивается первая пара операн» дов для базовой операции, выполняемой в течение времени импульса. Результаты базовой операции (по шинам

8 и 9 заносятся в регистр 3 по заднему фронту этого импульса, так как он, будучи пропущенным через элемент 28 И, приходит на тактовый вход

12. Одновременно по заднему фронту происходит переключение младшего разряда счетчика 19 в единицу, в результате чего на шине 25 появляется потенциал 1, а на шине 26 0, и. второй импульс приходит уже на тактовый вход 13 регистра 4, куда записывается очередная пара результатов. При этом регистр 3 не изменяет состояния. Третий импульс вновь приходит на тактовый вход 12, передвигает прежний результат в соседние разряды регистра 3 по направлению к выходу, а на их месте записывает новую пару и т.д.

Формирователь 15 тригонометрических коэффициентов выдает на шину 16 поток коэффициентов W"

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

N/2 тактов одновременно с нанесением в регистры нового исходного массива чисел, Формула изобретения

Устройство для вычисления коэффициентов Фурье, содержащее четыре

Источники информации, принятые во внимание при экспертизе

1. Патент CltlA Р 3816729, кл. 235-152; 1974.

2. Авторское свидетельство СССР по заявке 9 2516246,кл.G 06 F 15/37, 28,02,78 (прототип).

813447

Корректор Г. Реа етник

Филиал ППП Патент, г.Уигород, ул.Проектная, 4

Составители А.Варанов

Редактор A.Наурсков Йехред И.Табакозич

4ь 7 у

Заказ 775/б 3 Тираа 745 Подписное

ВИНИПИ ГосУЩарственйого комитета СССР по делам изобретений и отк ыти3

113035, Москва, %-35, Раумская наб., д.4/5