Главная -> Книги

(0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ( 14 ) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29) (30) (31) (32) (33) (34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48) (49) (50) (51) (52) (53) (54) (55) (56) (57) (58) (59) (60) (61) (62) (63) (64) (65) (66) (67) (68) (69) (70) (71) (72) (73) (74) (75) (76) (77) (78) (79) (80) (81) (82) (83) (84) (85) (86) (87) (88) (89) (90) (91) (92) (93) (94) (95) (96) (97) (98) (99) (100) (14)

Инструкция, в зависимости от положения переключателя Р-ГРД-Г ввести 2л/т = РЕ или 3607т=РЕ; * = РД, x(0)=PX В/О С/П РХ=], ;с(1) = = РХ С/П РХ=2, jc(2)=PX С/П РХ = 3 ... РХ = л, д:(п)=РХ С/П РХ = = л+1=т, Р0 = Л1, Pl=Bi, Р2 = Л2, РЗ = В2, Р4 = Лз, Р5 = Вз, Р6 = Л4, Р7 = В4, Р8=Л5, Р9=В5, PA=i46, РВ = Вб; время обработки одного отсчета около 80 с.

Для проверки правильности выполнения программы можно воспользоваться данными примера к предыдущей программе, дополнив их значениями Аб = = 1,7653665, Вб = 0,35115187.

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

Л « = Us- icos (2лк/т) -Us-2+х (0); В к = u»-isin {2лк/т)

через вспомогательную функцию и«, вычисляемую по вводимым в обратном порядке отсчетам функции x(i) согласно рекуррентному соотиощеиию

Ui = 2ui-icos{2nk/m)-Uj-2+x{m-j), uo=0; щ = х{т-1)-х{п).

По этому алгоритму для вычисления выбранного множества значений Л* и В* достаточно один раз вычислить функции cos(2nk/m) и sin(2nk/m), что прн программной реализации алгоритма позволяет вынести эти операции за пределы многократно повторяемой части программы и соответственно сократить время вычислений.

При реализации алгоритма Герцеля иа входном языке ЯМК52 можно увеличить число несмежных значений спектральной функции до четырех, но в этом случае время счета заметно увеличивается.

Программа 35. Вычисление трех смежных или несмежных значений спектральной функции x(ikv)

П7 П8 П9 2 я X ИПО ~ ПД 1 ПП 86 П4 2 ПП 86 П5 3 ПП 86 П6 Сх ПА ПВ ПС КИПО КИПО ИПО С/П ПД ИПО х=0 57 ИП7 ИП4 X П4 ИП8 ИП5 X П5 ИП9 ИП6 X П6 ИП1 2 -г П1 ИП2 2 Ч- П2 ИПЗ 2 ПЗ ИПД ИПА -

ИП7 ПА ИП1 X -f П7 ИПД ИПВ - ИП8 ПВ ИП2 X + П8 ИПД ИПС - ИП9 ПС ИПЗ X -f П9 БП 26 ПА КИПА ИПД X sin Вх cos 2 X КПА В/О

Инструкция. Установить переключатель Р-ГРД-Г в положение Р; т=Р0, ki = Pl, Й2=Р2,*з=РЗ, х(п) = РХ В/О С/П РХ=п-1, 1)=РХ С/П РХ = л-2, х{п-2)=РХ С/П...РХ=], д:(1)=РХ С/П РХ=0, д:(0)=РХ С/П РХ=-99999999, Р7=Л, Р8=Л. Р9=Л, Р4=В , Р5=В,, , Р6=В; вычисления можно начинать с ввода последнего ненулевого отсчета; время обработки одного отсчета (кроме первого и последнего) около 15 с.

* Хэмминг Р. В. Численные методы: Пер. с англ. / Под. ред. Р. С. Гутера. - М.: Наука, 1968. - 268 с.



Для проверки правильности выполнения программы можно воспользоваться данными примеров к программам 32 и 33.

Трудоемкость спектрального анализа при вычислении q отсчетов функции )C(]k\) по т отсчетам решетчатой функции x{i) с помощью алгоритма Герцеля или непосредственно ДПФ пропорциональна mq, хотя коэффициент пропорциональности для алгоритма Герцеля примерно в 4 раза меньше, чем при непосредственном ДПФ. Однако при полном спектральном анализе q = m/2 и mq = m/2, поэтому с увеличением числа т отсчетов трудоемкость анализа быстро возрастает.

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

При выполнении алгоритмов БПФ в памяти ЭВМ приходится хранить до 2т текущих переменных. Поэтому реализация алгоритмов БПФ на ПМК ограничена относительно малой емкостью памяти н соответствеиио предельным значением т8 в общем случае. Однако ПМК полезны при нсследованик особенностей различных вариантов БПФ и изучении методов их программной реализации.

Алгоритмы БПФ в основном отличаются прореживанием [5] по времени с основной операцией для преобразования двух текущих переменных

~ Ч + >ч, 2 = Xl - хт и по частоте с основной операцией х\ - (хх 4- X2)w, х2 = {xx~x«w,

где а/"-поворачивающий множитель. В простейшем случае четырехточечного БПФ (при т = 4) w=\ и алгоритмы с прореживанием по времени (рис. 5, а) и по частоте (рис. 5, б) практически совпадают по выполняемым операциям и реализуются одной программой.

х(0)о


л (01 о.

х(3)о

x(J)o.

Х(и)9

>в2

х(3)о


Рис. 5



Программа 36. Четырехточечиое БПФ

П4 ПЗ-ь П2 П1 ИПЗ + П5

ИП2ИП4+ П6 - ПС ИП2ИП4 - ПВ ИП1ИПЗ- ПАИП5ИП6 + ПО С/П

Инструкция. л:(0)=РТ, x(l)=PZ, a:(2)=PY, х(3)=РХ В/О С/П РХ=РО=Ло, ру=РА=Л,, PB = Bi, РС=Л2.

Пример. Для x(i)=7; 5; 2; 1 получим Ло=15, Ai = b, Bi = 4, 2 = 3.

Алгоритм восьмиточечиого БПФ с прореживанием по времени, граф которого показан иа рис. 6, реализуется программой без условных переходов, что обеспечивает минимальные затраты времени.

Программа 37. Восьмиточечное БПФ с прореживанием по времени

П2 С/П П9 С/П П5 ПЗ Вх ИП2 + П2 ИП9 + П9 ИП5 С/П П5 ИП6 С/П - П7 - П6 ИП9 Вх + П7


Рис. 6

+ ИП7 ИП8

ИП9 -

/ -f-V ИП2 С/П

-f П9 ИП2 ИП5 П9 ИП2 + П7 П8 ИП4

С/П П6 ИП2 С/П ИП9 СП - П8 - П4 Вх ИП5 ИП6 + ИП9 ИП7 ИП8 + - П5 ИП2 Вх + П2 ИПЗ Вх -

П8 Вх ИПЗ ПЗ

-V П4 ИП8 Вх

Инструкция. 40) = РХВ/О С/П х(1) = РХ С/П л:(2) = РХ С/П х(3) = =РХ С/П t{4) = РХ С/П 45)=РХ С/П ;с(6)=РХ С/П = РХ С/П РХ=Р2=Л„ , РЗ = Ль Р4 = Si, Р5=Л2, Р6=В2, Р7 = Лз, Р8 = 5,, Р9 = Л* (/=18 с) при нулевом значении х{0 необходимо вводить оператор набора цифры О (даже если на индикаторе высвечивается 0), а ие Сх.

Пример. Для функции л:(1) =«(18) = 16; 9,752108; 5,943979; 3,622897; 2,20818; 1,3459; 0,8203356; 0,5 получим Ло = 40,1934, Л,= 17,5276, В,= 13,2759, Л2 = = 11,4438, fi2=6,9751(, Лз= 10,0559, Вз=3,02866, Л4=5,75159.

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

/()= 2 а; wal(t,8),

1 = 0

где wal(0, 8) = 1 при 0<8<1 и wal(0, е)=0 при других значениях 8.

Программа 38. Восьмиточечиое быстрое преобразование Уолша-Фурье



(0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ( 14 ) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29) (30) (31) (32) (33) (34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48) (49) (50) (51) (52) (53) (54) (55) (56) (57) (58) (59) (60) (61) (62) (63) (64) (65) (66) (67) (68) (69) (70) (71) (72) (73) (74) (75) (76) (77) (78) (79) (80) (81) (82) (83) (84) (85) (86) (87) (88) (89) (90) (91) (92) (93) (94) (95) (96) (97) (98) (99) (100)