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

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

УСТРОЙСТВО ДЛЯ ВЬГЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ ФУРЬЕ, содержащее генератор тактовых импульсов, выход которого соединен с входом запуска генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход которого соединен с управляющим входом аналого-цифрового преобразователя, информационный вход которого является информационным входом устройства, блок памяти, первую и вторую группы сумматоров-вычитателей, первую и вторую группы регистров промежуточных коэффициентов, первый ч второй арифметические блоки, информационные выходы которых являются соответственно первым и вторым информационными выходами устройства, отличающееся тем, что, с целью повьппения быстродействия, в него введены регистр отсчетов, блок вьгчисления комбинаций отсчетов, первая и вторая группы регистров комбинаций по |Т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 ьк сумматоров-вычитателей соответственно йервой и второй групп, причем блок вычисления комбинаций отсчетов содер- жит первый, второй, третий, четвертый и пятый регистры, первый, зторой и третий сумматоры-вычитатели, информационный выход первого регистра соединен с первым входом первого сумматоравычитателя, выход которого подключен

Изобретение относится к автоматике и вычислительной технике и может быть использовано в радиотехнике, электросвязи и измерительной технике для определения.коэффициентов преобразования Фурье случайных сигналов в реальном масштабе времени. Известно устройство для последовательного выполнения быстрого преобразования Фурье (БПФ), содержащее одну или несколько последовательно соединенных арифметических групп,сос тоящих из сумматоров, умножителей и элементов задержки и , 1-J Недостатком устройства является низкое быстродействие, обусловленное необходимостью выполнения большого числа, операций перемножения многоразрядных чисел. Наиболее близким к предлагаемому является устройство для выполнения преобразования Фурье, содержащее генератор тактовых импульсов, выход ко торого соединен с входом генератора псевдослучайных чисел, выход которог подключен к входу блока формирования стробимпульсов, выход которого соединен с управляю1дим входом блока задания входной информации, вход которого является входом устройства, бло памяти, две группы по п шифраторов, две группы по п сумматоров-вычитателей ( П - количество частот анализа.), два регистра промежуточных коэффициентов и два вычислительных блока, входы и выходы которых являются выхо дами устройства. Отсчеты стохастичес ки дискретизированного сигнала умнож ются на отсчеты прямоугольных периодичееких функций, а полученные оценк в базисе этих функций пересчитьтаютс в базис Фурье в вычислительных блока.х 2j , Недостатком известного устройства является низкое быстродействие, обусловленное необходимостью вьшолнения большого числа операций суммированиявычитания для определения промежуточных коэффициентов. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что в устройство для вычисления коэффициентов Фурье, содержащее генератор тактовых импульсов, выход которого соединен с входом запуска генератора псевдослучайных чисел, выход которого подключен к входу блока формирования стробимпульсов, выход которого соединен с управляющим входом аналого-цифрового преобразователя, информационный вход которого является информационным входом устройства, блок памяти, первую и вторую группы сумматоров-вычитателей, первую и вторую группы регистров промежуточных ко:э(М ициентов, первый и второй арифметические блоки, информационные вькоды которых являются соответственно первым и вторым информадионньми вьгходами устройства, введены регистр отсчетов, блок вычисления комбинаций отсчетов, первая и вторая группы регистров комбинаций пот (), где К количество коэф4зициентов Фурье, обрабатываемых сумматором-вычитателем; п - количество аналнзируемьо: частот входного сигнала) в каждой, причем информационный выход аналого-цифрового преобразователя со€.динен с входом регистра отсчетов, о вьгаюд которого подключен к входу блока вычисления 5:омбинаций отсчетов. выход которого подключен к информационным входам i -X (,m) регистров комбинаций первой и второй групп информационные выходы которых подклю чены к первым йХодам i -х сумматороввычитателей соответственно первой и второй групп, выходы которых соедине ны с информационными входаьш -х регистров промежуточных коэффициенто соответственно первой и второй групп информационные выходы которых соединены с вторыми входами i -х сумматоров-вычитателей соответственно перво и второй групп, информационными входами соответственно первого и второго арифметических блоков и являются соответственно третьим и четвертым информационными выходами устройства, j|-e(} 2i-l)(i -- ГГп) и (А + т) -е выходы блока памяти соединены с управлающими входами регистров комбинаций соответственно первой и второй групп, a(ivm1 -е и( -е выходы блока памяти подключены к управляющим входам i-X сумматоров-вычитателей соответственно первой и второй групп, при этом блок вычисления комбинаций отсчетов содержит пер вый, второй, третий, четвертый и пятый регистры, первый, второй и третий сумматоры-вычитатели, информацио ный выход первого регистра соединен с первым входом первого сумматоравычитателя, выход которого подключен к информационным входам второго и третьего регистров, информационные выходы которых подключены соответственно к первому и второму входам второго сумматора-вычитателя, выход которого соединен с информационными входами четвертого и пятого регистров информационные выходы которых подклю чены сооЧ-ветственно к первому и второму входам третьего сумматора-вычитателя, выход которого является выхо дом блока, а второй вход первого сум матора-вычитателя объединен с информационным входом первого регистра и является входом блока. Предлагаемое устройство обеспечивает более эффективный алгоритм вычисления промежуточных коэффициентов в базисе прямоугольных промежуточных функций, в отличие от алгоритма рабо ты известного устройства, где каждый отсчет входного сигнала обрабатьшает ся непосредственно в 2п сумматорахвычитателях ( п - количество частот анализа) для накопления промежуточных коэффициентов. Алгоритм предлагаемого устройства включает вычисление частньсх сумм/разностей (комбинаций) групп по несколько отсчетов входного сигнала в блоке вычисления комбинаций отсчетов с последующей обработкой в сумматорах-вычитателях одной из этих комбинаций каждой группы для каждого обрабатываемого коэффициента. Это позволяет в несколько раз сократить количество операций суммирования-вычитания при вычислении промежуточных коэффициентов и, следовательно, повысить быстродействие устройства. На фиг.1 представлена функциональная схема устройства для вычисления коэффициентов Фурье, на фиг. 2 - функциональная схема блока вычисления комбинаций отсчетов. Устройство (фиг.1) содержит генератор 1 тактовых импульсов, генератор 2 псевдослучайных чисел, формирователь 3 стробимпульсов, аналого-цифровой преобразователь 4, информационный вход 5, регистр 6 отсчетов, блок 7 вычисления комбинаций отсчетов, in регистров 8 комбинаций в каждой из двух идентичных групп 9, блок 10 памяти, in сумматоров-вычитателей 11 первой и второй групп 9, m регистров 12 промежуточных коэффициентов первой и второй групп 9, арифметические блоки 13 первой и второй групп 9, информационные выходы 14 и 15. Блок 7 вычисления комбинаций отсчетов (фиг.2) включает в себя вход 16, сумматор7вьмитатель 17, регистр 18, регистры 19 и 20, сумматор-вычитатель 21, регистры 22 и 23, сумматор-вычитатель 24 и выход 25. Устройство работает в два этапа. На первом этапе в регистрах 12 накапливаются значения промежуточных коэффициентов в базисе прямоугольных периодических функций. Устройство позволяет на первом этапе работы определить значения промежуточных коэффициентов в базисе прямоугольных периодических функций, принимающих только значения +1 и -1. Вычисления промежуточных коэффициентов для четных прямоугольных периодических функций производятся в блоках первой группы 9, для нечетных - в блоках второй группы 9. Обработка данных в блоках обеих групп 9 производится идентично. На втором этапе накопленные значения промежуточных коэффициентов с регистров 12 выводятся на арифметические блоки 13, где производится пересчет оценок промежуточных коэффи циентов в коэффициенты Фурье. Одновременно производится этап накоплени новьЕХ значений промежуточных коэффициентов в регистрах 12. Исследуемый непрерывный сигнал поступает на аналоговый вход 5 устройства, который является информационным входом аналого-цифрового преоб разователя 4. Последовательно соединенные генератор 1 тактовых импульсов, генератор 2 псевдослучайных чисел и формирователь 3 стробимпульсов формируют стробимпульсы, которые на временной оси образуют стационарный случайный поток с ограниченным после действием. Эти импульсы подаются на управляющий вход аналого-цифрового преобразователя 4 и с помощью этих импульсов производится стохастическа дискретизация входного сигнала. Кван тованные значения входного сигнала в моменты дискретизации с выхода аналого-цифрового преобразователя 4 запи.сываются в регистр 6 отсчетов. В блоках 7, 8, 11 и 12 эти отсчеты обрабатываются группами по И (,3, ...). Количество циклов обработки равно - , где К - объем выборки, кратный . Каждый из этих циклов содержит вьпшсление частных сумм разностей (комбинаций) в блоке 7, а также К последовательных тактов накопления значений промежуточных коэффициентов в регистрах 12, С выхода регистра 6 отсчетов группа из t квантованных отсчетов входного сигна ла считывается на вход блока 7, кото 6 / рый вычисляет 2 комбинаций этих значений по формуле c,л,,l,.o -г-я комбинация отсчетов входного сигнала р -и груп пы по t отсчетов, р 0,1, 2 -I , . . . , л I, -значение квантованного j отсчета входного сигнала из р -и группы по отсче тов; целая часть выражения в скобках. Например, если 8, число вычисляемых комбинаций равно 2 128 и Cp,Xp,,,.Xpg(2) pg и т.д. Ра Вычисленные комбинации с выхода блока 7 записываются в регистры 8 комбинаций. Для обработки каждого промежуточного коэффициента в одном цикле обработке € отсчетов необходима одна из этих комбинаций. В каждом такте накопления значений промежуточных коэффициентов каждого цикла обработки отсчетов на выходах блока 10 памяти, подключенных к управляющим входам регистров 8 комбинаций, появляются адреса комбинаций, необходимых );ля обработки соответствующих промежуточных коэффици:ентов. Считываемые с регистров 8 комбинации поступают на первые входы соответствуюffljix сумматоров-вьгчитателей 1 1 . Одновременно с выходов соответствующих регистров 12 промежуточных коэффициентов поступают накопленные в предыдущих циклах обработки значения (а первом цикле обработки отсчетов выборки - нули)5 и сумматоры-вычитатели 1 1 вьшолняют операц11и суммирования или вычитания в зависимости от кодов, поступающих на их упранляющие входы с соответствующих выходов блока 10 памяти. Результаты вычислений записываются обратно в ячейка: обрабатываемых S текущем такте коэффициентов в регистрах 12. Аналогичным образом для каждой группы по f отсчетов последовательно обрабатываются все коэффициенты в регистрах 12, число которых в каждом регистре равно К. После завершения обработки V отсчетов входного сигнала вычисленные значения промежуточных коэффициентов становят,ся доступными для считывания на выходы регистров 12 и независимо от процесса их считывания производится этап накопления новых промежуточных коэффициентов в регистрах 12. Таким образом, после обработки N отсчетов сигнала на первом этапе работы устройства в регистрах 12 первой группы 9 накоплены промежуточные значения коэффициентов а,- для четных прямоугольных периодических функций, а в регистрах 12 второй rpynrfbi 9 - коэффициенты Ь; для нечетных прямоугольных перио дических функций по формулам Р 1 , в- I Q V.., V N р, ip ip Ь - т- ъ) 1 и С- л L . N ри 1р лр где и принимают значения -1-1 или -1 в зависимости от того, с ка ким знаком соответствующая комбинация суммируется при вычислении коэффициен тов 1Д и Ь. в СО 1 ответствии с этим с выхода блока 10 памяти поступает на управляющий вход сумматора-вычитател са) .tb) 1 °Д О - 1) С- n -комбинация из р-и группы отсчетов, не обходимая для вычис ления i -го коэффициента а или Ь. 1 Если обозначить прямоугольные периодические функции, образующие бази промежуточных коэффициентов R ( д1 Д) (четные) иRg(йi,t) (нечетные фун %ср 1ции), где л{ - - средняя S-.CP частота дискретизации, то , 4p-oe.,t,p.,,e,.V, ,,.,,e.,V,Uf,tp. где t-i - К-й момент дискретизации входного сигнала. Вычисление коэффициентов Фурье через промежуточные коэффициенты Я; и Ь в блоках 13 производится по тем же принципам, что и в известном устройстве. Например, если выбрать прямоугольные периодические функции вид Г 1, еслисо5()0 Ui,t , 1, ес. co5(2iiiAft)0 Г 1 , если (2 iiitl .0 .i,ib ,,,,,,,..,,0 и во входном сигнале отсутствуют сос тавляющие выше частоты nif , значения коэффициентов Фурье а, и Ь; рассчитываются через промежуточные значения коэффициентов Д; и Ь; в базисе данных прямоугольных периодических функций R-i,(ii,t) I 5(.iii,i)B соответствии со след ющими соотношениями: ««ч. ,Кг 1 -Vi-H / - целая часть выражения в скобках. Блок 7 вычисления комбинаций отсчетов (фиг.2) обрабатывает отсчеты входного сигнала группами по 8. Первый сумматор-вычитлтель 17 вычисляет частные суммы-разности пар отсчетов, второй сумматор-вычитатель 21 - част.1ые суммы-разности четь1рех отсчетов, а третий сумматор-вь(читатель - суммы-разности (комбинации) восьми отсчетов. На вход 16 блока 7 вычисления комбинаций отсчетов поступают отсчеты входного сигнала. Каждый отсчет р -и группы с нечетным порядковым номером записывается в первый регистр 18. После поступления следующего отсчета (с счетным номером) в cy iaтope-вычитaтeлe 17 вьмисляется сумма и разность между отсчетом, записанным в регистр 18, и отсчетом, поступающим на вход блока 7, На выходе сумматора-вычитателя 17 образуются частные суммы-разности Хр + и т.д. Частр2-,Хр,,+ (р ,РТ,Hbie суммы-разности пар Хр р иХр , Хр записываются в регистр 19,а частные суммы-разности пар X р - р ч Рг Хро в регистр 20. С выходов регистров 19 и 20 эти величины считываются на входы второго сумматора-вычитателя 21, которьм вычисляет частные суммь1-разности (J.p,+ (Xp,+ Хр , (Xp -t-Xp,, + ) и т.д. Частные сум Ь -разности отсчетов р ро X р .. 4 записываются в регистр 22, а частные cyм ы-paзнocти Хр , Хр( , РЭ регистр 23. С выходив регистров эти величины считываются на входы третьего сумматоравычитателя 24, который вычисляет суммыразности восьми отсчетов и подает

их на выход 25 блока 7 вычисления комбинаций отсчетов,

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

C42fl C OMTV 5 (7)

где количество суммирований- вьмитаний при определении комбинаций отсчетов в блоке 7.

зависит от €, а

Величина С

комт

также от алгоритма вычисления комбинаций f отсчетов. В предлагаемом блоке 7 вычисления комбинаций отсчетов

С,ом.2 +С,,,,

комт

(8) 152

и общее количество вьтолняемых операций суммирования-вычитания на первом этапе работы устройства

С,.... (2п-152)

(9)

WMT

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

Сг1-2п.М,(Q-j

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

5 - ; |- 22 17 гг 2

и лИ. U J -

/(

25

Фиг. 2