Устройство для вычисления коэффициентов Фурье Советский патент 1982 года по МПК G06F17/14 

(54) УСТГОЙСТЮ ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФ№ ЩЕНТОВ ФУРЬЕ

1

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

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

Известное устройство - громоздкое, много. секционное, насьпценное коммутацией, сложность которого обусловлена использованием рекуррентного алгоритма (с замещением).

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

небольишм числом коммутаций. Граф Стокхэма является лучщим из известных для регистров анализатора с точки зрения постоянства структуры и нормальности порядка вх одных и выходных отсчетов 2.

В устройстве осуществляется обработка одHOBpeNfeHHO лищь одной пары отсчетов, в связи с чем обеспечивается анализ сигналов в реальном времени для частот не выше 20 кГц. Граф не расслаивается на идентичные

10 части: для каждой пары операндов базовой операции требуется своя синусио-косинусная пара. Вьшолнение алгоритма с одновременной обработкой 4-х отсчетов связано с усложнением генератора тригонометрических

IS функций и -блока управлешш.

Цель изобретения - повышение быстродействия устройства для вычисления коэффициентов Фурье.

Поставленная цель достигается тем, что

20 устройство для вычисления коэффициентов Фурье, содержащее первый . арифметический блок, блок формирования тригонометрических функций, триггер, элемент НЕ, восемь эле39ментов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элемен тов И и через элемент НЕ - к первым входам третьего и четвертого элементов И, второй выход блока управле1шя подключен к первым входам пятого и шестого элементов И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления - к счетному входу триггера, выходы номеров итераций блока управления подключены ко входам блока формирования тригонометрических функций, выход которого подключен ко входу тригонометрической функции первого арифметического блока, прямой выход триггера подключен ко вторым входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера - ко вторым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход i-ro элемента ИЛИ (1 1, ..., 8) подключен к тактовому входу i-ro регистра сдвига, содержит второй арифметический блок, причем выход блока формирования тригонометрических функгщк подключен ко входу триг нометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и вто рого элемента ИЛИ, выход второго элемента И - к первым входам третьего и четвертого элементов ИЛИ, выход третьего элемента И - к первым входам пятого и шестого элементов ИЛИ, выход четвертого элемента И - к первым входам седьмого. и восьмото элементов ИЛИ, выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И - ко вторым входам первого и пятого элементов ИЛИ, выход седьмого элемента И - ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И - ко вторым вхо дам второго и шестого элементов ИЛИ, пря мой выход триггеров подключен к управляю щим входам третьего, четвертого, седьмого, восьмого регистров сдвига, инверсный выход триггера - к управляющим входам первого второго, пятого, шестого регистров сдвига, первые и вторые выходы второго, четвертого, шестого , ВОСЬМОТО регистров сдвига под ключены соответственно к первой и второй группе входов первого арифметического бло ка, первые и вторые выходы первого, треть го, пятого, седьмого регистров сдвига подключены соответственно к первой и второй группе входов второго арифметического блока, выходы арифметических блоков являются выходами устройства, причем первые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам пятого, шестого, седьмого, восьмого регистров сдвига, вторые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам первого, второго, третьего, четвертого регистров сдвига. На фиг. 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). Это peryjmpHbm постоянный граф без замещения с временной децимацией, нормальным порядком входных и выходных отсчетов, регулярной сменой тригонометрических коэффициентов, допускающий расслоение на два идентичных подграфа, в результате чего возможно их совмещение и переход к четырехточечным базовым операциям. При этом для одновременной обработки четырех отсчетов массива требуется лишь одна синусно-косинусная пара. Исходный, конечный и промежуточные массивы на графе показаны на черными точками, светлыми кружками выделены базовые операции, причём каждое комплексное число изображается линией, связывающей соседние точку и кружок. Числа исходного и конечного массива пронумерованы (граф показан для массива N 16), при этом приведена лишь половина выходного массива, так как при вычислении автоспекторов вторая половина не информативна, и поэтому не вычисляется. Однако ее необходимо вычислять при анализе взаимных спектров и отдельных спект- ров по двум независимым каналам. Для этих случаев нумерация второй половины дана на графе параллельно первой. Так сделано для того, чтобы подчеркнуть то некоторое неудобство вычислений, возникающее на последней итерации алгоритма, которое свойственно всем, графам без исключения, и которое устраняется при переходе к четырех5точечным базовым операциям. Граф построен по следующему новому итерационному соотношению алгоритма БПФ Si{KiKL,ni.4)I SL-ilK KL-l .L 2..(z4t KLн..), где ЧК1,)Ки,Л1-1, ...,W, Пр, np-i,...ni.,J адрес выбираемого операнда для базовой операции на i-той итерации, причем п - временный аргумент: k - частный аргумент; 1(1-,п,} К(, - г 2пpti - npн..г -ЧnLt nO г адрес результирующего операнда базовой операции i-той итерации. Очевидно, что тригонометрические коэффициенты в пределах итерации следуют в регулярной последовательности, которая повторяется раз и которая представляет собой геометрическую прогрессию с нулевым первым членом и знаменателем W где / 7г V Для N 16 в рассматриваемом графе (фиг. 2) Р 4 (число итераций) итерации пронумерованы римскими цифрами, проставленными над соответствующими рядами светлых кружков. Линии, подходящие к кружкам сверху (от первой половины массива - чисел О ... 7), соответствуют числам, умножаемым на W ° 1, что соответствует значению Кр О в вышеприведенной формуле Дпя чисел второй (нижней) половины маесива тригонометрические коэффициенты примут такие значения: на 1 итерации для каждого числа (W ; W ), на II итерации . для каждого из чисел (8, 10, 12, 14) и (9, 11, 13, 15) соответственно (W°; W) и (, w), на 111 итерации для каждого . из чисел (8, 12), (9,13), (10,14); (И. 15) cooтвeтcтвeнн J (W°; W); ( W), (w; W, ( W ). Ha IV итерации для каждого из чисел полумассива 8 ... 15 коэффнщ енты меняются соответственно от (W; W) до (W, W с возрастанием в W от предыдущих. При этом число умножается на первый коэффициент (с меньшим показателем степени) для результата базовой операции, показанного в виде линии, отходящей от светового кружка к ячейке с меньшим адресом (т.е. - верхней линии) и - на второй коэффициент для другого результата этой же базовой операции. Умножение нижней половины массива на тригонометрические коэффициенты, в общем случае не равные единице, соответствует значению Ар-( в вышеприведенной формуле. Из этой формулы явно следует, что описание графа в части адресов Л l(, и полностью повторяет описание граф в части адресов ( вследствие чего общее описание графа можно выполнить в адресах (Нн,П(. , т.е. совместить обе половины графа в одну и, таким образом, перейти к четырехточещ1ым базовым операциям. Этот переход для рассматриваемого случая (N 16) показан на, фиг. 3. При зтом итерационное соотношение принимает вид , с-Л2)1-.гл/.N iSt JA (KL, ne,)-expL-J 1г(г 2,),, Кр-1 -ОИ Адреса выбираемых и результирующих операндов соответственно выглядят: ,пиО {| ч«1-ъ---1 . Р-Ь -0},,А-,. ,. - ДЧМи ) пр-г.... (nln П ); Занесенные в одну ячейку операнды различаются по индексам присвоенных им значений старшего разряда адреса развернутого (исходного) графа. Т. е. теперь, в ячейке находятся оцеранды:( У -(н) , (Sl-Ol, С учетом этой индексации описание совмещенкого графа идентично описанию исходного Сдвиговые регистры 15-22 одинаковы и в совокупности имеют объем памяти 2N, что характерно для алгоритмов без замещения. Каждый регистр рассчитан на занесение последовательности из N/8 пар чисел, при- этом числа пары записываются и выдаются одновременно по двум входам и по двум выходам. Регистры делятся на две группы. Когда первая группа, состоящая из регистров 15, 16, 19, 20, находится в режиме вьщачи, вторая (регистры 17, 18, 21, 22) работает в режиме занесения и - наоборот. Режимы определяются триггером 5. Например, нулевое состояние триггера соответствует считыванию из первой группы и занесению во вторую. При занесении на управляющий вход регистра подается единичный потенциал. На тактовый вход регистра поступают импульсы от соответствующего элемента ИЛИ 23-30. При занесении эти импульсы вырабатьшаются элементом И из числа 6-9, а при выдаче элементов И из числа 10-13.

Одновременно в каждой из групп тактируются пишь по два регистра.

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

В исходном состоянии в первую группу регистров в естественном порядке занесен исходный массив данных. Для массив расположится след5пощим образом: в регистр 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 появляется разрешение для прохрждения тактовых импульсов ТИ через элемент И 13 и далее через элементы ИЛИ 23 и 27 на тактовые входы регистров 15 и 19, на ртравляющих входах которых задан нулевой потенциал запрет заш1си и разрешение выдачи. Одновременно по нулевому выходу 38 старшего разряда счетчика 40 (по второму выходу блока 4 управления) задано разрешение на прохождение тактовых импульсов через злемент И 9 и далее через элемент ИЛИ 25 и 26 на тактовые входы регистров 17 и 18. При прохождении первого тактового импульса из регистров 15 и 19 в арифметические блоки 1 и 2 будут выданы для обработки числа 0-8 и 4-12. В каждом из арифметических блоков 1 и 2 вьшолняется базовая операция А ± WB, где А, В - пара операндов. Результаты записываются в регистры 17 и 18 в соответствии с графом фиг. 3. После второго тактового импульса будут обработаны соответственно пары чисел 1-9 и 5-13 с записью результатов в регистры 17 и 18.

После этого в старший регистр счетчика 40 блок 4 управления, считающего тактовые импульсы, запишется единица (счетчик имеет объем N/4)j в результате чего числа будут выталкиваться из регистров 16 и 20 (тактовые импульсы пройдут через элемент И 12), а записываться в регистры 21 и . 22 (ТИ пройдут через элемент ИВ). Это пары чисел 2-10, 6-14, 3-11, 7-15. На первой итерации блок 3 формирования тригонометрических функций выдает значения (W, W ) для всех пар чисел. После переполнения счетчика 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. На последующих итерациях процессы вызова - записи будут аналогичны рассмотренным, причем режим записи будет повто-. ряться в точности, а режим вызова - с учетом изменения разрядных весов счетчика

Увеличение быстродействия в предлагаемом устройстве обусловлено одновременной обработкой четырех отсчетов по сравнению с двумя отсчетами в известном устройстве.

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

Устройство для вычисления коэффициентов Фурье, содержащее первый арифметический блок, блок формирования тригонометрических функшай, триггер, элемент НЕ, восемь элементов И, восемь элементов ИЛИ, восемь регистров сдвига и блок управления, причем первый выход блока управления подключен к первым входам первого и второго элементов И и через элемент НЕ - к первым входам третьего и четвертого элементов И, второй выход блока управления подключен к первым входам пятого и шестого элементов 9 И, третий выход блока управления подключен к первым входам седьмого и восьмого элементов И, четвертый выход блока управления - к счетному входу триггера, выходы номеров итерации блока управления подключены к входам блока формирования тригонометрических функций, выход которого под ключен к входу тригонометрической функци первого арифметического блока, прямой выход триггера подключен ко вторьпй входам первого, третьего, пятого, седьмого элементов И, инверсный выход триггера - ко вто рым входам второго, четвертого, шестого, восьмого элементов И, третьи входы всех элементов И подключены к тактовому входу устройства, выход i-ro элемента ИЛИ (1 1, ..., 8) подключен к тактовому входу i-To регистра сдвига, отличающ е.е с я тем, что, с целью увеличения быстродействия, оно содержит второй арифметический блок, причем выход блока формирования тригонометрических функций подключен к входу тригонометрической функции второго арифметического блока, выход первого элемента И подключен к первым входам первого и второго элементов ИЛИ, выход второго элемента И - к первым вхо дам третьего и четвертого элементов ИЛИ, выход третьего элемента И - к первым вхо дам пятого и шестого элементов ИЛИ, выход четвертого элемента И - к первым входам седьмого и восьмого элементов ИЛИ выход пятого элемента И подключен ко вторым входам третьего и седьмого элементов ИЛИ, выход шестого элемента И - ко 8 вторым входам первого и пятого элементов ИЛИ, выход седьмого элемента И - ко вторым входам четвертого и восьмого элементов ИЛИ, выход восьмого элемента И - ко вторым входам второго и шестого элементов ИЛИ, прямой выход триггеров подключен к управляющим входам третьего, четвертого, седьмого, восьмого регистров сдвига, инверсный выход триггера - к управляюищу входам первого, второго, пятого, шестого регистров сдвига, первые и вторые выходы второго, четвертого, шестого, восьмого регистров сдвига подключены соответственно к первой и второй группе входов первого арифметического блока, первые и вторые выходы первого, третьего, пятого, седьмого регистров сдвига подключены соответственно к первой и второй i-pynne входов второго арифметического блока, выходы арифметических блоков являются выходами устройства, причем первые выходы первого и второго арифметических блоков подключены соответственно к первым и вторым входам пятого, шестого, седьмого, восьмого регистров сдвига, вторые выходы первого я второго арифметических блоков подключены соответственно к первым и вторым входам первого, второго, третьего, четвертого регистров сдвига. Источники информации, принятые во внимание при экспертизе 1.Патент США № 3899667, кл. 235-156, опублик. 1975. 2.Авторское свидетельство СССР N 699525, кл. G 06 F 15/34, 1977 (прототип).