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

 

УСТРОЙСТВО ДЛЯ ВЬГЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ФУРЬЕ, содержащее генератор тактовых импульсов, выход которого соединен с входом запуска генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход которого соединен с управляющим входом аналого-цифрового преобразователя, информационный вход которого является информационным входом устройства , блок памяти, первую и вторую группы сумматоров-вычитателей, первую и вторую группы регистров промежуточных коэффициентов, первый ч второй арифметические блоки, информационные выходы которых являются соответственно первым и вторым информационными выходами устройства, отличающееся тем, что, с целью повьппения быстродействия, в него введены регистр отсчетов, блок вьгчисления комбинаций отсчетов, первая и вторая группы регистров комбинаций по |Т1 (w П/К, где К - количество коэффициентов Фурье, обрабатываемых сумматором-вычитателем; п - количество с У I 1 ьь.. анализируемых частот входного сигнала ) в каждой, причем информационный выход аналого-цифрового преобразователя соединен с входом регистра отсчетов , выход которого подключен к входу блока вычисления комбинаций отсчетов, выход которого подключен к информационным входам i -х (,w) регистров комбинаций первой и второй групп, информационные выходы которых подключены к первым входам i-х сумматоров-вычитателей соответственно первой и второй групп, выходы которых соединены с информационными входами -X регистров промежуточных коэффициентов соответственно первой и второй групп, информационные выходы которых соединены с вторыми входами J -X сумматоров-вьЕчитателей соответственно первой и второй групп, информационными входами соответственно первого и второго арифметичаскиз: блоков и являются соответствен о третьим и четвертым информацион:0 Hbijm выходами устройства, j -е ( -1) (i f7rrt) и (i+m)-e выходы блока 05 СЛ СЛ памяти соединены с управляющими входами регистров комбинаций соответственно первой и второй групп, а (i+ +№)-е и (i+3m)-e выходы блока памяти подключены к управляющим входам 5 ьк сумматоров-вычитателей соответственно йервой и второй групп, причем блок вычисления комбинаций отсчетов содержит первый, второй, третий, четвертый и пятый регистры, первый, зторой и третий сумматоры-вычитатели, информационный выход первого регистра соединен с первым входом первого сумматоравычитателя , выход которого подключен

СООЗ СОВЕТСНИХ

ИМ

РЕСПУБЛИН

Qg) (И зов С 06 F 15/332! с !

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHGMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННИЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГПФ (21) 3566075/18-24 ,(22) t0.03.83

{46) 07.06.84. Вюл. № 21 (72) И.Я.Билинский, И.Б.itepниекс и А.К.Микелсон (71) Институт электроники и вычислительной техники АН Латвийской ССР (53) 681..32(088.8) (56) 1. Патент США ¹ 4058715, кл. G 06 F 15/332, 1976.

2. Авторское свидетельство СССР № 928363, кл. G 06 F 15/332, 1981 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ВЬИИСЛЕНИЯ

КОЭФФИЦИЕНТОВ ФУРЬЕ, содержащее генератор тактовых импульсов, выход которого соединен с входом запуска генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход KQÔoporo соединен с управляющим входом аналого-цифрового преобразователя, информационный вход которого является информационным входом устройст. ва, блок памяти, первую и вторую группы сумматоров-вычитателей, первую и вторую группы регистров промежуточных коэффициентов, первый И второй арифметические блоки, информационные выходы которых являются соответственно первым и вторым информационными выходами устройства, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия, в него введены регистр отсчетов, блок вычисления комбинаций отсчетов, первая и вторая группы регистров комбинаций по и (тй =

=и/К, где К вЂ” количество коэффициентов Фурье, обрабатываемых сумматором-вычитателем; и — количество анализируемых частот входного сигнала) в каждой, причем информационный выход аналого-цифрового преобразователя соединен с входом регистра отсчетов, выход которого подключен к входу блока вычисления комбинаций отсчетов, выход которого подключен к информационным входам 1 -х (< =1,m) регистров комбинаций первой и второй групп, информационные выходы которых подключены к первым входам s -х сумматоров-вычитателей соответственно первой и второй групп, выходы которых соединены с информационными входами < -х регистров промежуточных коэффициентов соответственно первой и второй групп, информационные выхо" ды которых соединены с вторыми входами 1 -х сумматоров-вычитателей соответственно первой и второй групп, информационными входами соответственно первого и второго арифметически:: блоков и являются соответственуо третьим и четвертым информационными выходами устройства, 1 -е (1=2i-1) (i =Г,v) и (i+m)-е выходы блока памяти соединены с управляющими входами регистров комбинаций соответственно первой и второй групп, а (» +

+й)-е и (+За)-е выходы блока памяти подключены к управляющим входам j -ых сумматоров-вычитателей соответственно первой и второй групп, причем блок вычисления комбинаций отсчетов содержит первый, второй, третий, четвертый и пятый регистры, первый, второй и третий сумматоры-вычитатели, информационный выход первого регистра соединен с первым входом первого сумматоравычитателя, выход которого подключен

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

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

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

Наиболее близким к предлагаемому является устройство для выполнения преобразования Фурье, содержащее генератор тактовых импульсов, выход которого соединен с входом генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход которого соединен с управляющим входом блока за30 дания входнбй информации, вход которого является входом устройства, блок памяти, две группы по q шифраторов, две группы по П сумматоров-вычитателей (П вЂ” количество частот анализа), два регистра промежуточных коэффициентов и два вычислительных блока, входы и выходы которых являются выхоаамн.устройства. Отсчеты стохастически дискретиэированного сигнала умножаются на отсчеты прямоугольных периодических функций, а полученные оценки в базисе этих функций пересчитываются чены соответственно к первому и второму входам третьего сумматора-вычитателя, выход которого является выходом блока, а второй вход первого сумматора-вычитателя обьединен с информационным входом первого регистра и является входом блока. в базис Фурье в вычислительных блоках (2) .

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

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем, что в устройство для вычисления коэффициентов Фурье, содержащее генератор тактовых импульсов, выход которого соединен с входом запуска генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход которого соединен с управляющим входом аналого-цифрового преобразователя, информационный вход которого является информационным входом устройства, блок памяти, первую и вторую группы сумматоров-вычитателей, первую и вторую группы регистров промежуточных коэффициентов, первый и второй арифметические блоки, информационные выходы которых являются соответственно первым и вторым информационными вьгходами устройства, введены регистр отсчетов, блок вычисления комбинаций отсчетов„ первая и вторая группы регистров комбинаций по tn urn = n К), где К вЂ” количество коэффициентов

Фурье, обрабатываемых сумматором-вычитателем; и — количество анализируемых частот входного сигнала) в каждой, причем информационный выход аналого-цифрового преобразователя соединен с входом регистра отсчетов,,о выход которого подключен к входу блока вычисления комбинаций отсчетов, 1096655 4 выход которого подключен к информационным входам j -х (=1,rn) регистров комбинаций первой и второй групп, информационные выходы которых подключены к первым ходам -х сумматороввычитателей соответственно первой и второй групп, выходы которых соединены с информационными входами -х регистров промежуточных коэффициентов соответственно первой и второй групп,1п информационные выходы которых соединены с вторыми входами -х сумматоров-вычитателей соответственно первой и второй групп, информационными входами соответственно первого и второго арифметических блоков и являются соответственно третьим и четвертым информационными выходами устройства, )-е(1=2j-<)(i =- f,w) и { 4 ) -е выходы блока памяти соединены с управляющими входами регистров комбинаций соответственно первой и второй групп, а(j ym) -е n(i 3 m) -е выходы блока памяти подключены к управляющим входам j -х сумматоров-вычитателей соответственно первой и второй групп, при этом блок вычисления комбинаций отсчетов содержит первый, второй, третий, четвертый и пятый регистры, первый, второй и третий сумматоры-вычитатели, информационный выход первого регистра соединен с первым входом первого сумматоравычитателя, выход которого подключен к информационным входам второго и третьего регистров, информационные

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

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

Предлагаемое устройство обеспечи- б вает более эффективный алгоритм вычисления промежуточных коэффициентов в базисе прямоугольных промежуточных функций, в отличие от алгоритма работы известного устройства, где каждый отсчет входного сигнала обрабатывает" ся непосредственно в 2п сумматорахвычитателях (Й вЂ” количество частот анализа) для накопления промежуточных коэффициентов. Алгоритм предлагаемого устройства включает вычисление частных сумм/разностей (комбинаций) групп по несколько отсчетов входного сигнала в блоке вычисления комбинаций отсчетов с последующей обработкой в сумматорах-вычитателях одной из этих комбинаций каждой группы для каждого обрабатываемого коэффициента. Это позволяет в несколько раз сократить количество операций суммирования-вычитания при вычислении промежуточных коэффициентов и, следовательно, повысить быстродействие устройства.

На фиг. 1 представлена функциональная схема устройства для вычисления коэффициентов Фурье, на фиг.2 — функциональная схема блока вычисления комбинаций отсчетов.

Устройство (фиг. 1) содержит генератор 1 тактовых импульсов, генератор

2 псевдослучайных чисел, формирователь 3 стробимпульсов, аналого-цифровой преобразователь 4, информационный вход 5, регистр 6 отсчетов, блок

7 вычисления комбинаций отсчетов, т регистров 8 комбинаций в каждой из двух идентичных групп 9, блок 10 памяти, п сумматоров-вычитателей 11 первой и второй групп 9, rn регистров

12 промежуточных коэффициентов первой и второй групп 9, арифметические блоки 13 первой и второй групп 9, информационные выходы 14 и 15.

Влок / вычисления комбинаций отсчетов (фиг.2) включает в себя вход

16, сумматор-вычитатель 17, регистр

18, регистры 19 и 20, сумматор-вычитатель 21, регистры 22 и 23, сумматор-вычитатель 24 и выход 25.

Устройство работает в два этапа.

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

Обработка данных в блоках обеих групп 9 производится идентично.

1096655

На втором этапе накопленные значения промежуточных коэффициентов с регистров 12 выводятся на арифметические блоки 13, где производится пересчет оценок промежуточных коэффициентов в коэффициенты Фурье. Одновременно производится этап накопления новых значений промежуточных коэффициентов в регистрах 12.

Исследуемый непрерывный сигнал поступает на аналоговый вход 5 устройства, который является ииформационным входом аналого-цифрового преобразователя 4. Последовательно соединенные генератор 1 тактовых импульсов, генератор 2 псевдослучайных чисел и формирователь 3 стробимпульсов формируют стробимпульсы, которые на временной оси образуют стационарный случайный поток с ограниченным после- 2 действием. Эти импульсы подаются на управляющий вход аналого-цифрового преобразователя 4 и с помощью этих импульсов производится стохастическая дискретизация входного сигнала. Кван- тованные значения входного сигнала в моменты дискретизации с выхода аналого-цифрового преобразователя 4 записываются в регистр 6 отсчетов. В блоках 7, 8, 11 и 12 эти отсчеты обрабатываются .группами по 2 (2=2,3, ...). Количество циклов обработки

М равно —, где я — объем выборки, крат ный g Каждый из этих циклов с о g5 держит вычисление 2 частных сумм разностей (комбинаций) в блоке 7, а также K последовательных тактов накопления значений промежуточных коэффициентов в регистрах 12. С выхо- 4о да регистра 6 отсчетов группа из 8 квантованных отсчетов входного сигнала считывается на вход блока 7, который вычисляет 2 комбинаций этих значений по формуле 45 г

= х + (.-5) 2 ° X

5=2 5 где С вЂ” г -я комбинация отсчетов

Рг 50 входного сигнала р -й груп. пы по f отсчетов, р =О, 1.

2,...,2 " -1;

" значение квантованного I -го

1 отсчета входного сигнала из р -й группы по Й отсчетов, () — целая часть выражения в скобках.

Например, если f=H, число вычисляемых комбинаций равно 2 =128 и

7 л л л л (< х лх,„+ х л л л и

Ср =Х 5-„,+х -х, +Х

2 1 6 7 pg> л л р = "р «хр -x -х и т.д. 1 6 Р7 РВ

Вычисленные комбинации с выхода блока 7 записываются в регистры 8 комбинаций. Для обработки каждого промежуточного коэффициента в одном цикле обработке К отсчетов необходима одна из этих комбинаций. В каждом такте накопления значений промежуточных коэффициентов каждого цикла обработки Я отсчетов на выходах блока 10 памяти, подключенных к управляющим входам регистров 8 комбинаций, появляются адреса комбинаций, необходимых для обработки соответствующих промежуточных коэффициентов. Считываемые с регистров 8 комбинации поступают на первые входы соответствуюших сумматоров-вычитателей 11. Одновременно с выходов соответствующих регистров 12 промежуточных коэффициентов поступают накопленные в предыдущих циклах обработки значения (в первом цикле обработки Й отсчетов выборки — нули), и сумматоры-вычитатели 11 выполняют операции суммирования или вычитания в зависимости от кодов, поступающих на их управляющие входы с соответствующих выходов блока 10 памяти. Результаты вычислений записываются обратно в ячейки обрабатываемых в текущем такте коэффициентов в регистрах 12. Аналзгичным образом для каждой группы по g отсчетов последовательно обрабатываются все коэффициенты в регистрах 12, число которых в каждом регистре равно К. После завершения обработки М отсчетов входного сигнала вычисл нные значения промежуточных коэффициентов становятся доступными для считывания на выходы регистров 12 и независимо от процесса их считывания производится этап накопления новых промежуточных коэффициентов в регистрах 12. Таким образом, после обработки 9 отсчетов сигнала на первом этапе работы устройства в регистрах 12 первой группы

9 накоплены промежуточные значения коэф-! фициентов а; для четных прямоугольных периодических функций, а в регистрах

12 второй груп77ы 9 — коэффициенты

10966-.=.

I для нечетных прямоугольных перио- дических функций по формулам

Е х Е х

2 х1Р

Е

"Р*1

1о1 (а) с Р

{%

1 .У С Ь) с. где h и 1, а) Ю

1Р принимают значения

+ 1 или — 1 в зависимости от того, с каким знаком соответствующая комбинация суммируется при вы— числении коэффициен1 1 I тов а ° и в. (,в со1 1 ответствии с этим с выхода блока 10 па— средняя

3S частота дискретизации, то Р Р 1 1 (Р- )Рл1 а Р С =."-" ;,.) г,, 56

) 1 где, — К-й момент дискретизации

К входного сигнала.

Вычисление коэффициентов Фурье через промежуточные коэффициенты а. I и Ь в блоках 13 производится по тем же принципам, что и в известном уст— ройстве. Например, если выбрать прямоугольные периодические функции вида если co5(2II1z f t) > 0 с — 1, Рс:. и CcI51,2il 15.11) (0 (5) 1, если 5In(2 igft) )Q

1 4й ) = — 1, есл1, e

I и во входном сигнале отсутствуют составляющие выше частоты nd<, значения коэффициентов Фурье а, и b; мяти поступает на управляющий вход сум1атора-вычитателя

b) 1 1 код 0 или 1}

С и C — комбинация из Р -й

1Р Р группы отсчетов, не в 25 обходимая для вычисления 1 -го коэффи1 l циента а; или Ь.

Если обозначить прямоугольные периодические функции, образующие базис ЗО промежуточных коэффициентов1 с(1,() (четные) и к (1ь 4,<) (нечетные функ

fg cp

1 ции), где х цср

pacсчи-.ываются через промежуточные значения коэффициентов а и Ъ в

1 1 базисе данных прямоугольных периодических функции x-qIpg,f ) и ; 1.{,1)в соответствии со следующими соотношениями:

Il а 1=Il ()11 1, n (===? а = 21 2 (-1)

K-1 - Кл1

Т1 а,.„„,, ), (6) и

Ь 1-I, — )«

1 ) (— — — ) п 1 2

2 1

Ь - .à — Ь . 1=<-),1

1 л 21 +<)11 Ъ

v, =1 - +1 ются на входы второго сумматора-вычитателя 21, который вычисляет частные л л л суммы — разности ),хр +, Р (ХР + Xp i, л л л 1 2 Ъ 4 (Xp,+XI1 )- (Xp i Xp ) и т.Д. Частные суммы-разности отсчетов Х Р, х „, Х p z u X p записываются в регистр

° 4

22, а частные суммы-разности х Р

ХРь . х Р и Хс I3 Регистр 23. С выходов påãèстрoB эти величиньI считываются на входы третьего сумматоравычитателя 24,который вычисляет суммыразности восьми отсчетов и подает где ) — целая часть выражения в скобках.

Глок 7 вычисления комбинаций отсчетов (фиг.2) обрабатывает отсчеты входногс сигнала группами по 8.

Первый сумматор-вычитатель 17 вычисляет частные суммы-разности пар отсчетов, второй сумматор-вычитатель

21 — частные суммы-разности четырех отсчетов, а третий сумматор-вычитатель 2- — суммы †разнос (комбинации) восьми отсчетов. На вход 16 блока 7 вычисления комбинаций отсчетов поступают отсчеты входного сигнала. Каждый отсчет р -й группы с нечетным порядковым номером записывается в первый регистр 18. После поступления следующего отсчета (с счетным номером) в сумматоре †вычитате 17 вычисляется сумма и разность между отсчетом, записанным в регистр 18, и отсчетом, поступающим на вход блока ?.

На выходе сумматора-вычитателя 17 л образуются частные суммы-разности х л л л л л л Р1

+ХР,xp,- р,хр 1 Р,Xp -х, и т.д. Частл ные суммы-разности пар X x и Х л Р2 Р5 хР записываются в регистр 19,а частные л л л сум ьы-разности пар X p X p < и X p л

З 1 4

КР— в perncTp 0. C вых

8 гистров 19 и 20 эти величины считыва1096655

evt !

mvz. г

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

Редактор О.Юрковецкая Техред А.Ач

Корректор И. Эрдейи

Заказ 3827/37 Тираж 699 Подписное

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

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

Филиал ППП "Патент, г.Ужгород, ул .Проектная, 4 их на выход 25 блока 7 вычисления комбинаций отсчетов.

Количество операций суммированиявычитания для вычисления 2 и промежуточных коэффициентов следовательно равно К

С=(«,„, f.—, ) где С„ — 1количество суммированийвычитаний при опредеЯении комбинаций отсчетов в блоке ?.

Величина Скомт зависит от 2, а также от алгоритма вычисления комбинаций 1 отсчетов. В предлагаемом бло) ке 7 вычисления комбинаций отсчетов н общее количество выполняемых операций суммирования-вычитания на первом этапе работы устройства

= (2 +152) (9)

В известном устройстве это количество равно

C„=-2 й, (10)

fO следовательно, предлагаемое устройство позволяет при количестве анализируемых частот от 128 до 512 уменьшить количество операций суммирования-вычитания на первом этапе работы

f5 устройства в 5-7 раз, что повышает быстродействие устройства при одинаковой элементной базе.