Цифровая обработка сигналов

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

На рис. 15. первый этап БПФ содержит только сложения и вычитания комплексных чисел. Даже на втором этапе используются только сложения и вычитания комплексных  чисел.

Фактически, как следует из направленного  графа на рис. 15., вместо ожидаемых 12 (т.е. ) достаточно выполнить всего 2 нетривиальных умножения.

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

Выигрыш по вычислительным операциям , где                  количество вычислительных операций при непосредственном вычислении ДПФ,

 количество вычислительных операций при непосредственном вычислении ДПФ с использованием алгоритмов БПФ.

Описанный выше алгоритм был назван алгоритмом с прореживанием по времени, поскольку на каждом этапе входная (т.е. временная) последовательность разделяется на две обрабатываемые последовательности меньшей длины, т.е. входная последовательность прореживается на каждом этапе.

 

2. Структурная схема и листинг программы вычисления прямого и обратного БПФ.

Алгоритм  вычисления ДПФ с использованием алгоритма БПФ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Текст программы на языке Бейсик вычисления прямого и обратного БПФ взят из книги Дьяконова В.П. «Справочник по алгоритмам и программам на языке Бейсик для персональных ЭВМ» Издательство «Наука», Москва, 1989.

10 PRINT "ПРЯМОЕ И ОБРАТНОЕ БЫСТРОЕ  ПРЕОБРАЗОВАНИЕ ФУРЬЕ"

20 INPUT "ДЛЯ N=2^M ВВЕДИТЕ M="M:LETN=INT(2^M+.1):DIM X(N-1),Y(N-1)

30 INPUT "ЗАДАЙТЕ -1 ПРИ ПРЯМОМ БПФ  И 1 ПРИ ОБРАТНОМ "D

40 FOR I=0 TO I1-I0:PRINT!3.0!"ДЛЯ I="I+I0

50 INPUT "ВВЕДИТЕ XI,YI    " X(I),Y(I):NEXT I

60 FOR L=1 TO M:LETE=INT(2^(M+1-L)+.1):LETF=E/2:LETU=1:LETU=0

70 LETZ=#PI/F:LETC=COS(Z):LETS=D*SIN(Z):FOR J=1 TO F

80 FOR I=J TO N STEP E:LETO=I+F-1:LETP=X(I-1)+X(0):LETQ=Y(I-1)+Y(0)

90 LETR=X(I-1)-X(0):LETT=Y(I-1)-Y(0):LETX(0)=R*U-T*U

100 LETY(0)=T*U+R*U:LETX(I-1)=P:LETY(I-1)=Q:NEXT I

110 LETW=U*C-V*S:LETV=V*C+U*S:LETU=W:NEXT J:NEXT L

120 LETJ=1:FOR I=1 TO N-1:IF I>=J THEN 150

130 LETJ1=J-1:LETI1=I-1:LETP=X(J1):LETQ=Y(J1):LETX(J1)=X(I1)

140 LETY(J1)=Y(I1):LETX(I1)=P:LETY(I1)=Q

150 LETK=N/2

160 IF K>=J THEN 180

170 LETJ=J-K:LETK=K/2:GOTO 160

180 LETJ=J+K:NEXT I

190 IF D=-1 THEN PRINT "РЕЗУЛЬТАТЫ ПРЯМОГО БПФ":GOTO 240

200 PRINT "РЕЗУЛЬТАТЫ ОБРАТНОГО БПФ":FOR K=0 TO N-1

210 LETX(K)=X(K)/N:LETY(K)=Y(K)/N

220 PRINT!3.0!"K="K;!F1.5!" X="X(K);"  Y="Y(K)

230 NEXT K:STOP

240 FOR K=0 TO N-1:LETA=SQR(X(K)*X(K)+Y(K)*Y(K))

250 LETQ=0:IF A=0 THEN 270

260 LETQ=ACS(X(K)/A):IF Y(K)<0 THEN LETQ=-Q

270 PRINT !3.0!"K="K;!F1.5!"  X="X(K);"  Y="Y(K);

280 PRINT "  M="A*2/N;"  Q="DEG(Q):NEXT K:END

3. Методом «быстрой свертки» с использованием алгоритмов прямого и обратного быстрого преобразования Фурье (БПФ) найти отклик цифрового фильтра

Свертка – основной процесс в обработке сигналов. Существует алгоритм вычисления свертки, основанный на теореме свертки.

Теорема свертки:

Свертка во временной области эквивалентна умножению в частотной области; умножение во временной области  эквивалентно свертке в частотной  области.

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

Алгоритм вычисления быстрой свертки

Сначала исходный сигнал длины N и ядро свертки длины M дополняются (справа) нулями до длины L (L – степень двойки), причем так, что Затем вычисляются ДПФ этих двух сигналов, при этом получаются комплексные спектры. Затем спектры сигналов необходимо перемножить (используется перемножение комплексных чисел), при этом получается новый спектр также состоящий из комплексных коэффициентов. Затем из полученного спектра с помощью обратного ДПФ вычисляется сигнал, состоящий из L точек. Этот сигнал и содержит результата свертки из точек, дополненный нулями до L точек.

 

 

 

 

 

 

 

 

 

1. Дополнение нулями

 

 

Чтобы число  отсчетов последовательности равнялось восьми , добавим . Таким образом, последовательности и будут иметь вид:

 

 

2. Вычисление прямого БПФ

 

 

3. Перемножение

 

4. Вычисление обратного БПФ

 

Результаты  расчетов отклика цифрового фильтра представлены в таблицах 7-9.

Таблица 7.

k	0	1	2	3	4	5	6	7
	36	-4	-4	-4	-4	-4	-4	-4
	0	9.657	4	1.657	0	-1.657	-4	-9.657
	0	-12828	-14	-7.172	-4	-7.172	-14	-12.828
	0	5.314	-14	17.314	0	-17.314	14	-5.314
	0	0	112	0	16	0	112	0
	0	-145.137	0	-81.137	0	81.137	0	145.137

 

Таблица 8.

n	0	1	2	3	4	5	6	7	8	9	10	11	12
	-9	-19	-23	-33	-42	-42	-42	-42	39	57	13	71	72

4. Вычислить отклик цифрового фильтра на последовательность непосредственно через уравнение свертки, сравнить полученные результаты.

 

 

Подставляя  в формулу значения соответственно, получим:

 

 

 

 

 

 

 

 

 

 

      

 

 

Таблица 9.

n	0	1	2	3	4	5	6	7	8	9	10	11	12
	-9	-19	-23	-33	-42	-42	-42	-42	39	57	13	71	72

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

 

Список используемой литературы

1. Сергиенко «Цифровая обработка сигналов»
2. Солонина А.И. «Основы цифровой обработки сигналов», 2изд.
3. Методические указания к курсовой работе Мишин Д.В.