Устройство для вычисления коэффициентов фурье
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Соввтскмя
Соцналмстмчвскна
Рвспублнн
6 06 F 15f332 Риуааратаааай кеннтат CCCP пв делан изабретенкй к вткрытвй Опубликовано 07 05.82. Бюллетень М 17 Дата опубликования описания 07.05.82 (53) УДК 681З (088.8) (72) Автор изобретения В. Д. Гусев Специальное конструкторское бюро Производственного оВъединения. "Вибропрнбор" . (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ФУРЬЕ Изобретение относится к автоматнке.и вычислительной технике н может быть использовано для измерения спектров случайных функций и решения задач технической диагностики. Известен специализированный процессор (1), выполняющий быстрое преобразование Фурье (БПФ) и содержащий с целью ускорения анализа регистры сдвига вместо обычных оперативных запоминающих устройств с произвольной выборкой (1) . Известное устройство — громоздкое, много. секционное, насьпценное коммутацией, сложность которого обусловлена использованием рекуррентного алгоритма (с замещением). Наиболее близким к предлагаемому является устройство для вычисления коэффициентов Фурье содержащее арифметический блок, блок деформирования тригонометрических функций, триггер, инвестор,,элемент И, ИЛИ, регистры сдвига и блок управления. В этом устройстве применен алгоритм Стокхэма, что позволило сделать схему односекционной с неболЬшими аппаратурными затратами и с небольшим числом коммутаций. Граф Стокхэма является лучшим из известных для регистров анализатора с точки зрения постоянства структуры и нормальности порядка входных и выходных отсчетов (2). В устройстве осуществляется обработка одновременно лишь одной пары отсчетов, в связи с чем обеспечивается анализ сигналов в реальном времени для частот не выше 20 кГц. Граф ие расслаивается на идентичные части: для каждой пары операндов базовой операции требуется своя синусно-косинусная пара. Выполнение алгоритма с одновременной обработкой 4-х отсчетов связано с усложнением генератора тригонометрических функций и блока управления. Цель изобретения — повышение быстродействия устройства для вычисления коэффициентов Фу)тье. Поставленная цель достигается тем, что № устройство для вычисления коэффициентов Фурье, содержащее первый арифметический блок, блок формирования тригонометрических функций, триггер, элемент НЕ, восемь эле926668 ментов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элементов И и через элемент НŠ— к первым входам третьего и четвертого элементов И, второй выход блока управления подключен к первым входам пятого и шестого элементов И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления — к счетному входу триггера, выходы номеров итераций блока управления подключены ко входам блока формирования тригонометрических функций, выход которого подключен ко входу тригонометрической функции первого арифметического блока, прямой выход триггера подключен ко вторым входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера — ко вторым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход i-ro элемента ИЛИ (i = 1, ..., 8) подключен к тактовому входу i-ro регистра сдвига, содержит второй арифметический блок, причем выход блока формирования тригонометрических функций подключен ко входу тригонометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и второго элемента ИЛИ, выход второго элемента И вЂ” к первым входам третьего и четвертого элементов ИЛИ, выход третьего элемента И вЂ” к первым входам пятого и шестого элементов ИЛИ, выход четвертого элемента И вЂ” к. первым входам седьмого и восьмого элементов ИЛИ, выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И вЂ” ко вторым входам первого и пятого элементов ИЛИ, выход седьмого элемента И вЂ” ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И вЂ” ко вторым входам второго и шестого элементов ИЛИ, прямой выход триггеров подключен к управляющим входам третьего, четвертого, седьмого, восьмого регистров сдвига, инверсный выход триггера — к управляющим входам первого, второго, пятого, шестого регистров сдвига, первые и вторые выходы второго, четвертого, шестого, восьмого регистров сдвига подключены соответственно к первой и второй . группе входов первого арифметического блока, первые и вторые выходы первого, третьего, пятого, седьмого регистров сдвига подключены соответственно к первой и второй t5 3$ 4 группе входов второго арифметического блока, выходы арифметических блоков являются выходами устройства, причем первые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам пятого, шестого, седьмого, восьмого регистров сдвига, вторые выходы первого и второго арифметических блоков одключены соответственно к первым и вторым входам первого, второго, третьего, четвертого регистров сдвига. На фиг. 1 представлена функциональная схема предлагаемого устройства для вычисления коэффициентов Фурье", на фиг. 2 и 3— графы быстрого преобразования Фурье (БПФ)Устройство содержит арифметические блоки 1 и 2, блок 3 формирования тригонометрических функций, блок 4 управления, триггер 5, элементы И 6 — 13, элемент HE 14, регистры 15 — 22 сдвига, элемент ИЛИ 23 — 30, выходы 31 — 34 устройства, арифметический узел 35, блок 36 тактирования. Блок 4 управления представлен выходами 37 — 39, счетчиком 40, регистром 41 сдвига, элементами И 42 — 45, элементом ИЛИ 46, выходами 47 — 49 номеров итераций. Устройство работает по новому алгоритму в соответствии с графом БПФ (фиг. 2). Это регулярный постоянный граф без замещения с временной децимацией, нормальным порядком входных и выходных отсчетов, регулярной сменой тригонометрических коэффициентов, допускающий расслоение ка два идентичных подграфа, в результате чего возможно их совмещение и переход к четырехточечным базовым операциям. При этом для одновременной обработки четырех отсчетов массива требуется лишь одна синусно-косинусная пара. Исходный, конечный и промежуточные массивы на графе показаны на черными точками, светлыми кружками выделены базовые операции, причем каждое комплексное число изображается линией, связывающей соседние точку и кружок. Числа исходного и конечного массива пронумерованы (граф показан для массива N = 16), при этом приведена лишь половина выходного массива, так как при вычислении автоспекторов вторая половина не информативна, и поэтому не вычисляется. Однако ее необходимо вычислять при анализе взаимных спектров и отдельных спектров по двум независимым каналам. Для этих случаев нумерация второй половины дана на графе параллельно первой. Так сделано для того, чтобы подчеркнуть то некоторое неудобство вычислений, возникающее на последней итерации алгоритма, которое свойственно всем, графам без исключения, и которое устраняется при переходе к четырех926668 55 точечным базовым операциям. Граф построен по следувшему новому итерационному соотношению алгоритма БПФ sifts(s,nÄ, =E 2 -i{a (Ki-(, д кр-0 ° 2.Р КР) eAPQ< (г. 1(,+ К;», ... LQI()2. l(01, де 4(I(i,0.,.„1- (, I(Ä-1 ...,5Inp, .п -,...п„„) — адрес выбираемого операнда для базовой операции на i-той итерации, причем и временный аргумент, k — частный аргумент; А"((-1, < i ) = К(К, + i+I )— Ар f2. Пр-«+...+2 (п 9 И, ))+ адрес результирующего операнда базовой операции i-той итерации. Очевидно, что тригонометрические коэффициенты в пределах итерации следуют в регулярной последовательности, которая повторяется 2 " раз и которая представляет собой геометрическую прогрессию с нулевым пер2 pL вым членом и знаменателем W Г, где 4 =е"Г (- ) . Зля N = 16 в рассматриваемом графе (фиг, 2) P = 4 (число итераций), итерации пронумерованы римскими цифрами, проставленными над соответствующими рядами светлых кружков. Линии, подходящие к кружкам сверху (от первой половины массива — чисел 0 ... 7), соответствуют числам, умножаемым на W = 1, что соответствует о значению Kp-- 0 в вышеприведенной формуле. Для чисел второй (нижней) половины массива тригонометрические коэффициенты примут такие значения: на 1 итерации для о IL каждого числа (W; W ), íà II итерации для каждого из чисел (8, 10, 12, 14) и р. Ь (9, 11, 13, 15) соответственно (W; В ) и (W4; W ), íà III итерации для каждого . из чисел (8, 12), (9,13), (10, 14); (11, 15) в, „, (уЧо. у). (щг,. що) (щ4. Wg, (W; W ). На IV итерации для каждого иэ чисел полумассива 8 ... 15 коэффициенты меняются соответственно от (W; W ) до (W""; W ) с возрастанием в W от предыдущих. При этом число умножается на первый коэффициент (с меньшим показателем степени) для результата базовой операции, показанного в виде линии, отходящей от светового кружка к ячейке с меньшим адресом (т.е. — верхней линии) и — на второй коэффициент для другого результата этой же базовой операции. Умножение нижней половины массива на тригонометрические коэффициенты, в общем случае не равные единице, соответствует значению I(p=t в вышеприведенной формуле. Из этой формулы явно следует, что описание графа в части адресов =1(Кс=(<) полностьв повторяет описание графа в части адресов и !(p=O(I(, и; 5 вследствие чего общее описание графа можно выполнить в адресах и I(p=O(I(<,0, т.е. совместить обе половины графа в одну и, таким образом, перейти к четырехточе шым базовым операциям. Этот переход для рассматриваемого случая (N = 16) показан на, фиг. 3. При этом итерационное соотношение принимает внд г,() „z(=(E (SL-1 ) А (К,-(, n )+Z I(p,). 15 ° Kp=II / о р" .exPE.-J g (< Ki Z I(<)Z. Кр1 Кр Кр-< =0,4 щ, Адреса выбираемых и результирующих операндов соответственно выглядят: A (к,,n, -(,x -,, «,, пР-< ... n,+, n(, „<)) е (. „г). - - (- + ) ) Занесенные в одну ячейку операнды различаются по индексам присвоенных им значений старшего разряда адреса развернутого (исходного) графа. Т. е. теперь„в ячейке находятрандыФ-, 4 — (S -I)p,- <, -(z о С учетом этой индексации описание совмещенного графа идентично описанию исходного графа. Сдвиговые регистры 15 — 22 одинаковы и в совокупности имеют объем памяти 2N„ что характерно для алгоритмов без замещения, Каждый регистр рассчитан на занесение последовательности из М/8 пар чисел, при- этом числа пары записываются и выдаются одновременно по двум входам и по двум выходам. Регистры делятся на две группы. Когда первая группа, состоящая иэ регистров 15, 16, 19, 20, находится в режиме выдачи, вторая (регистры 17, 18, 21, 22) работает в режиме занесения и — наоборот. Режимы определяются триггером 5. Например, нулевое состояние триггера соответствует считыванию из первой группы и занесению во вторую. При занесении на управляющий вход регистра подается единичный потенциал. На тактовый вход регистра поступают импульсы от соответствующего элемента ИЛИ 23 — 30. При занесении эти импульсы вырабатываются элементом И иэ числа 6 — 9, а при выдаче элементов И из числа l0--13. 926668 Одновременно в каждой из групп тактируются лишь по два регистра, Устройство работает следующим образом. В исходном состоянии в первую группу регистров в естественном порядке занесен исходный массив данных. Для N=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. При этом счетчик 40, установленный в "ноль", прямым входом старшего разряда запирает элемент И 45, значит и элемент ИЛИ 46, в результате чего на выходе инвертора 14 появляется разрешение для прохождения тактовых им- 20 пульсов ТИ через элемент И 13 и далее через элементы ИЛИ 23 и 27 на тактовые входы регистров 15 и 19, на управляющих входах которых задан нулевой потенциал— запрет записи и разрешение выдачи. Одновре- 25 менно по нулевому выходу 38 старшего разряда счетчика 40 (по второму выходу блока 4 управления) задано разрешение на прохождение тактовых импульсов через элемент И 9 и далее через элемент ИЛИ 25 и 26 на так- 30 товые входы регистров 17 и 18. При прохождении первого тактового импульса из регистров 15 и 19 в арифметические блоки 1 и 2 будут выданы для обработки числа 0 — 8 и 4 — 12. В каждом из арифметических блоков 1 и 2 выполняется базовая операция А + WB, где А,  — пара операндов. Результаты записываются в регистры 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, На nepS0 вой итерации блок 3 формирования тригонометрических функций выдает значения (W; W ) для всех пар чисел, После переполнения счетчика 40 единичный потенциал пере- ° пишется в первый разряд регистра 41 (появится на шине 47), а триггер 5 поменяет состояние на "единичное". В результате этого вторая группа регистров перейдет в режим считывания, а первая группа — в режим записи. Первый тактовый импульс пройдет через элемент И 11 и далее через элементы ИЛИ 26 и 29 на тактовые входы регистров 17 и 21, из которых будут выданы две пары чисел, полученные в качестве результата на первом и (и(4+ 1) тактах первой итерации. Результат запишется в регистры 15 и 16. После первого тактового импульса первый разряд счетчика 40 изменит состояние на единичное, в результате чего на втором такте числа будут вызваны из регистров 18 и 22 (тактовый импульс пройдет через элемент И 10), а записаны по-прежнему в регистры 15 и 16 (ТИ проходят через элемент И 7). После этого в старшем разряде счетчика появится единичный потенциал, что приведет к записи двух последующих результатов в регистры 19 и 20, так как ТИ пройдут через элемент И 6. При этом вызов произойдет вначале из регистров 17 и 21, а затем — из 18 и 22. Блок 3 по сигналу lm шине 47 выдаст в блоки 1 и 2 коэффи циенты в соответствии с графом фиг. 2 и фиг. 3, На последующих итерациях процессы вызова — записи будут аналогичны рассмотренным, причем режим записи будет повто-. ряться в точности, а режим вызова — с учетом изменения разрядных весов счетчика 40. На последней итерации единичный потенциал регистра 41 вновь будет записан в его старший разряд, При этом повторится режим считывания, и блок 3 выдаст в блоки 1 и 2 весь спектр своих коэффициентов. Резуль1 таты анализа будут сняты непосредственно с выходов арифметических блоков, а в регистры группы записи будет введен новый массив данных, причем этому режиму будет соответствовать наличие единичного потенциала в старшем разряде регистра 41, Увеличение быстродействия в предлагаемом устройстве обусловлено одновременной о6работкой четырех отсчетов по сравнению с двумя отсчетами в известном устройстве. Формула изобретения Устройство для вычисления коэффициентов Фурье, содержащее первый арифметический блок, блок формирования тригонометрических функщ й, триггер, элемент НЕ, восемь элементов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элементов И и через элемент HE — к первым входам третьего и четвертого элементов И, второй выход блока управления подключен к первым входам пятого и шестого элемент а 26668 9 9 И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления — к счетному входу триггера, выходы номеров итерации блока управления подключены к входам блока формирования тригонометрических функций, выход которого подключен к входу тригонометрической функции первого арифметического блока, прямой выход триггера подключен ко вторым входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера — ко вторым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход i-го элемента ИЛИ (i = 1, ..., 8) подключен к тактовому входу i-ro регистра сдвига, о т л и ч а ющ е е с я тем, что, с целью увеличения быстродействия, оно содержит второй арифметический блок, причем выход блока формирования тригонометрических функций поцключен к входу тригонометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и второго элементов ИЛИ,+ выход второго элемента И вЂ” к первым входам третьего и четвертого элементов ИЛИ, выход третьего элемента И вЂ” к первым входам пятого и шестого элементов ИЛИ, выход четвертого элемента И вЂ” к первым входам седьмого и восьмого элементов ИЛИ, выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И вЂ” ico вторым входам первого и пятого элементов ИЛИ, выход седьмого элемента И вЂ” ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И вЂ” ко вторым входам второго и шестого элементов ИЛИ, прямой выход триггеров подключен к управляющим входам третьего, четвертого. седьмого, восьмого регистров сдвига, инверсный выход триггера — к управляющим 10 входам первого, второго, пятого, шестого регистров сдвига, первые и вторые выходы второго, четвертого, шестого, восьмого регистров сдвига подключены соответственно к первой и второй группе входов первого арифметического блока, первые и вторые выходы первого, третьего, пятого, седьмого регистров сдвига подключены соответственно к первой и второй группе входов второго арифметического блока, выходы арифметических блоков являются выходами устройства, причем первые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам пятого, шестого, седьмого, восьмого регистров сдвига, вторые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам первого, второго, третьего, четвертого регистров сдвига. Источники информации, принятые во внимание при экспертизе 1. Патент США и 3899667, кл. 235-156, опублик. 1975. 2. Авторское свидетельство СССР Р 699525, кл. G 06 F 15/34, 1977 (прототип). 926668 - - 11 -ф- jg 5- 1,7 - - 14 -7-Я Редактор М. Ткач Заказ 2983/42 Х 2 г ф К Р У 1g 11 1g у ф Составитель В. Байков Техред М. Рейвес Корректор А. Гриценко Тираж 732 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 1)3035, Москва, Ж вЂ” 35, Раушская наб.; д. 4/5 Филиал ППП "Патент", г, Ужгород, ул. Проектная, 4
