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

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоввтскмяСоцмалмстмчвскмкРвсиублмк щ 926668(22) Заявлено 21.11,79 (21) 2860477/18-24с присоединением заявки ие(5)М. е(л. 0 06 Е 15332 Ьаударетееаай квинтет СИР аа лелем азебретенка и аткрытва( 72 ) Автор изобретения У В, Д. Гусев Специальное конструкторское бюро Производственного оВъдинения,.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ФУРЬЕ Изобретение относится к автоматике.и вы. числительной технике и может быль использовано для измерения спектров случайных функций и решения задач технической диагностики.Известен специализнрованньщ процессор 11, выполняющий быстрое преобразование Фурье (БПФ) и содержащий с целью ускорения анализа регистры сдвига вместо обычных оперативных запоминающих устройств с произвольной выборкой 11.Известное устройство - громоздкое, много- , секционное, насьпценное коммутацией, сложность которого обусловлена использованием рекуррентного алгоритма (с замещением).Наиболее близким к предлагаемому является устройство для вычисления коэффициентов Фурье содержащее арифметический блок, блок деформирования тригонометрических функций, триггер, инвесторэлемент И, ИЛИ, регистры сдвига и блок управления. В этом устройстве применен алгоритм Стокхэма, что позволило сделать схему односекционной с неболЬшими аппаратурными затратами и с небольшим числом коммутаций. Граф Стокхэма является лучшим из известных длярегистров анализатора с точки зрения постоянства. структуры и нормальности порядка входных и выходных отсчетов 2.В устройстве осуществляется обработка одновременно лишь одной пары отсчетов, всвязи с чем обеспечивается анализ сигналовв реальном времени для частот не выше20 кГц. Граф не расслаивается на идентичныечасти: для каждой пары операндов базовойоперации требуется своя синусно-косинуснаяпара, Выполнение алгоритма с одновременной обработкой 4-х отсчетов связано с усложнением генератора тригонометрических функций и блока управленияЦель изобретения - повышение быстродействия устройства для вычисления коэффицн.ентов Фувье.Поставленная цель достигается тем, чтоустройство для вычисления коэффициентовФурье, содержащее первый арифметическийблок, блок формирования тригонометрическихфункций, триггер, элемент НЕ, восемь эле926668 ментов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элементов И и через элемент НЕ - к первым входам третьего и четвертого элементов И, второй выход блока управления подключен к первым входам пятого и шестого элементов И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления - к счетному входу триггера, выходы номеров итераций блока управления подключены ко входам блока формирования тригонометрических функций, выход которого подключен ко входу тригонометрической функции первого арифметического блока, прямой выход триггера подключен ко вторым входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера - ко вторым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход -го элемента ИЛИ ( = 1, ., 8) подключен к тактовому входу 1-го регистра сдвига, содержит второй арифметический блок, причем выход блока формирования тригонометрических функций подключен ко входу тригонометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и второго элемента ИЛИ, выход второго элемента И - к первым входам третьего и четвертого элементов ИЛИ, выход третьего элемента И - к первым входам пятого и шестого элементов ИЛИ, выход четвертого элемента И - к. первым входам седьмого и восьмого элементов ИЛИ, выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И - ко вторым входам первого и пятого элементов ИЛИ, выход седьмого элемента И - ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И - ко вторым входам второго и шестого элементов ИЛИ, прямой выход триггеров подключен к управляющим входам третьего, четвертого, седьмого, восьмого регистров сдвига, инверсный выход триггера - к управляющим входам первого, второго, пятого, шестого регистров сдвига, первые и вторые выходы второго, четвертого, шестого, восьмого регистров сдвига подключены соответственно к первой и второй, группе входов первого арифметического блока, первые и вторые выходы первого, третьего, пятого, седьмого регистров сдвига подключены соответственно к первой и второй 5 1 О 15 20 25 ЗО 3 40 45 5 О 4группе входов второго арифметического блока, выходы арифметических блоков являются выходами устройства, причем первые вы.ходы первого и второго арифметических блоков подключены соответственно к первым ивторым входам пятого, шестого, седьмого,восьмого регистров сдвига, вторые выходыпервого и второго арифметических блоков подключены соответственно к первым и вторымвходам первого, второго, третьего, четвертого регистров сдвига,На фиг. 1 представлена функциональнаясхема предлагаемого устройства для вычисления коэффициентов Фурье", на фиг, 2 и 3 -графы быстрого преобразования Фурье (БПФ) .Устройство содержит арифметические блоки 1 и 2, блок 3 формирования тригонометрических функций, блок 4 управления, триггер 5, элементы И 6 - 13, элемент НЕ 14,регистры 15 - 22 сдвига, элемент ИЛИ 23 - 30,выходы 31 - 34 устройства, арифметическийузел 35, блок 36 тактирования,Блок 4 управления представлен выходами37 - 39, счетчиком 40, регистром 41 сдвига,элементами И 42 - 45, элементом ИЛИ 46,выходами 47 - 49 номеров итераций.Устройство работает по новому алгоритмув соответствии с графом БПФ (фиг. 2),Это регулярный постоянный граф без замещения с временной децимацией, нормальнымпорядком входных и выходных отсчетов, регулярной сменой тригонометрических коэффициентов, допускающий расслоение ка два идентичных подграфа, в результате чего возможноих совмещение и переход к четырехточечнымбазовым операциям, При этом для одновременной обработки четырех отсчетов массиватребуется лишь одна синусно-косинусная пара.Исходный, конечный и промежуточные массивы на графе показаны на черными точками,светлыми кружками выделены базовые операции, причем каждое комплексное число изображается линией, связывающей соседние точку и кружок. Числа исходного и конечногомассива пронумерованы (граф показан длямассива М = 16), при этом приведена лишьполовина выходного массива, так как привычислении автоспекторов вторая половинане информативна, и поэтому не вычисляется.Однако ее необходимо вычислять при анализе взаимных спектров и отдельных спектров по двум независимым каналам. Дляэтих случаев нумерация второй половины дана на графе параллельно первой, Так сделано для того, чтобы подчеркнуть то некоторое неудобство вычислений, возникающее напоследней итерации алгоритма, которое свойственно всем, графам без исключения, и которое устраняется при переходе к четырех 926668Одновременно в каждой из групп тактиру.ются лишь по два регистра,Устройство работает следующим образом.В исходном состоянии в первую группурегистров в естественном порядке занесенисходный массив данных, Для И=16 массиврасположится следующим образом: в регистр15 запишутся 0-8 и 1 - 9 отсчеты, в регистрсоответственно 2 - 10 и 3 - 11, в регистр 19 -отсчеты 4 - 12 и 5 - 13 и в регистр 20 - отсчеты 6 в 14 и 7 - 15, Триггер 5 устанавлива.ется в нулевое состояние, в регистре 41 блока 4 управления в старшем разряде записывается единичный потенциал, клапанирующийпо выходу 49 элемент И 45, При этом счет. 15чик 40, установленный в "ноль", прямымвходом старшего разряда запирает элементИ 45, значит и элемент ИЛИ 46, в результате чего на выходе инвертора 14 появляетсяразрешение для прохождения тактовых импульсов ТИ через элемент И 13 и далее через элементы ИЛИ 23 и 27 на тактовыевходы регистров 15 и 19, на управляющихвходах которых задан нулевой потенциал -запрет записи и разрешение выдачи. Одновременно по нулевому выходу 38 старшего разряда счетчика 40 (по второму выходу блока4 управления) задано разрешение на прохож.дение тактовых импульсов через элемент И 9и далее через элемент ИЛИ 25 и 26 на тактовые входы регистров 17 и 18. При прохождении первого тактового импульса изрегистров 15 и 19 в арифметические блоки1 и 2 будут выданы для обработки числа0 - 8 и 4 - 12. В каждом из арифметическихблоков 1 и 2 выполняется базовая операцияА + ФВ, где А, В - пара операндов. Результаты записываются в регистры 17 и 18 всоответствии с графом фиг, 3, После второго тактового импульса будут обработанысоответственно пары чисел 1 - 9 и 5 - 13 сзаписью результатов в регистры 17 и 18,После этого в старший регистр счетчика40 блок 4 управления, считающего тактовыеимпульсы, запишется "единица" (счетчик име 45ет объем Я 4), в результате чего числа будут "выталкиваться" из регистров 16 и 20(тактовые импульсы пройдут через элементИ 12), а записываться в регистры 21 и22 (ТИ пройдут через элемент И 8), Этопары чисел 2 - 10, 6 - 14, 3 - 11, 7 - 15, На пер 50вой итерации блок 3 формирования тригонометрических функций выдает значения (уф;В ) для всех пар чисел, После переполне.ния счетчика 40 единичный потенциал перепишется в первый разряд регистра 41 (появится на шине 47), а триггер 5 поменяетсостояние на "единичное". В результате этоговторая группа регистров перейдет в режим считывания, а первая группа - в режим записи, Первый тактовый импульс пройдет через элемент И 11 и далее через элементы ИЛИ 26 и 29 на тактовые входы регистров 17 и 21, из которых будут выданы две па.ры чисел, полученные в качестве результата на первом и (иИ+ 1) тактах первой итерации. Результат запишется в регистры 15 и 16, После первого тактового импульса первый разряд счетчика 40 изменит состояние на единичное, в результате чего на втором такте числа будут вызваны из регистров 18 и 22 (тактовый импульс пройдет через элемент И 10), а записаны по-прежнему в регистры 15 и 16 (ТИ проходят через элемент И 7), После этого в старшем разряде счетчика появится единичный потенциал, что приведет к записи двух последующих результа.тов в регистры 19 и 20, так как ТИ пройдут через элемент И 6, При этом вызов произойдет вначале из регистров 17 и 21, а затем - из 18 и 22, Блок 3 по сигналу на шине 47 выдаст в блоки 1 и 2 коэффициенты в соответствии с графом фиг, 2 и фиг. 3, На последующих итерациях процессы вызова - записи будут аналогичны рассмотренным, причем режим записи будет повто-.ряться в точности, а режим вызова - с учетом изменения разрядных весов счетчика 40, На последней итерации единичный потен циал регистра 41 вновь будет записан в его старший разряд, При этом повторится режим считывания, и блок 3 выдаст в блоки 1 и 2 весь спектр своих коэффициентов. Резуль/таты анализа будут сняты непосредственно с выходов арифметических блоков, а в регистры группы записи будет введен новый массив данных, причем этому режиму будет соответствовать наличие единичного потенциала в старшем разряде регистра 41,Увеличение быстродействия в предлагаемом устройстве обусловлено одновременной обработкой четырех отсчетов по сравнению с двумя отсчетами в известном устройстве.Формула изобретенияУстройство для вычисления коэффициентов Фурье, содержащее первый арифметический блок, блок формирования тригонометрических функщй, триггер, элемент НЕ, восемь элементов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элементов И и через элемент НЕ - к первым входам третьего и четвертого элементов И, второй выход блока управления подключен к первымвходам пятого и шестого элементов26668 9 9 И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления - к счетному входу триггера, выходы номеров итерации блока управления подключены к входам блока формирования тригонометрических функций, выход которого подключен к входу тригонометрической функции первого арифметического блока, прямой выход триггера подключен ко вторым входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера - ко вторым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход .го элемента ИЛИ (1 = 1, , 8) подключен к тактовому вхо. ду -Го регистра сдвига, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия, оно содержит второй арифметический блок, причем выход блока фор. мирования тригонометрических функций поц. ключен к входу тригонометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и второго элементов ИЛИ, выход второгоэлемента И - к первым входам третьего и четвертого элементов ИЛИ, выход третьего элемента И - к первым вхо. дам пятого и шестого элементов ИЛИ, выход четвертого элемента И - к первым входам седьмого и восьмого элементов ИЛИ, выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И - ко вторым входам первого и пятого элементовИЛИ, выход седьмого элемента И - ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И - ковторым входам второго и шестого элементов ИЛИ, прямой выход триггеров подключен к управляющим входам третьего, четвертого, седьмого, восьмого регистров сдвига, инверсный выход триггера - к управляющим 1 О входам первого, второго, пятого, шестого ре.гистров сдвига, первые и вторые выходы вто.рого, четвертого, шестого, восьмого регистровсдвига подключены соответственно к первойи второй группе входов первого арифмети ческого блока, первые и вторые выходы пер.ного, третьего, пятого, седьмого регистров сдвига подключены соответственно к первой ивторой группе входов второго арифметического блока, выходы арифметических блоков яв.ляются выходами устройства, причем первыевыходы первого и второго арифметическихблоков подключены соответственно к первыми вторым входам пятого, шестого, седьмого,восьмого регистров сдвига, вторые выходыпервого и второго арифметических блоков под.ключены соответственно к первым и вторымвходам первого, второго, третьего, четвертогорегистров сдвига. Источники информации,принятые во внимание при экспертизе 1. Патент США У 3899667, кл, 235-156,опублик. 1975,2. Авторское свидетельство СССР й". 699525,кл. 6 06 Е 1534, 1977 (прототип),,5-47 -М -7-Я Р Г О 74 уе Р Составитель В. БайковТехред М, Рейвес Корректор А. Гриценк едактор М. Ткач Заказ 2983 42 лиал ХХ 0;Ю Р;Я Г;Ю ДГ Тираж 732 Подписно ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Москва, Ж - 35, Раушская наб,; д. 4/5