Безруков А.В. ОСНОВЫ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

7.2.1. Прямая структура

Прямая структура (рисунок 7.9) определяется передаточной функцией H (z) , представленной в виде рациональной функции

N 1

H (z) bi z i

i 0

и отображает разностное уравнение

N 1

y(n) bi X (n i)

i 0

7.2.2 Каскадная структура

Каскадная структура определяется передаточной функцией H (z) , представленной в виде произведения множителей второго порядка:

k1	k1
H (z) H i (z) (b0i		b1i z 1 b2i z 2 ) ,
i 1	i 1

где b0i , b1i , b2i — вещественные коэффициенты, а k1 — количество звеньев второго порядка аналогично п. 7.1.5.

ПФ (7.22) соответствует система РУ нерекурсивных звеньев 2-го порядка (см. п. 7.1.3)

		(n) b		X (n) b x(n 1) b x(n 2);
	1	01					11			21
		(n) b			1	(n) b		1	(n 1) b		1	(n 2);
	2		02				12			22					,
...
y(n) b						k 1	(n) b			(n 1) b				k 1	(n 2)
		0,k 1						1,k 1 k 1				2,k 1

отображаемая каскадной структурой (см. рисунок 7.6), где каждое звено имеет прямую структуру (рисунок 7.10).

61

8. Спектральный анализ

СПЕКТРАЛЬНЫМ АНАЛИЗОМ называется обработка сигналов, связанное с анализом их спектров.

В современных информационно–вычислительных комплексах (ИВК) кроме обработки во временной области всѐ шире используется обработка и анализ входной информации в частотной области. Цифровая обработка в частотной области предполагает наличие в ИВК специализированного устройства или программой реализации алгоритма дискретного преобразования Фурье (ДПФ). В радиолокационных системах многоканальный спектральный анализ по доплеровским частотам применяется для измерения скорости воздушных целей. Спектральный анализ широко используется также в различных системах распознавания (например, речи), в системах обнаружения, в системах сжатия речевых сигналов и т.д.

О некоторых аспектах спектрального анализа и идѐт речь в данном разделе. Прежде всего, мы рассмотрим дискретное преобразование Фурье (ДПФ) – разновидность преобразования Фурье, специально предназначенную для работы с дискретными сигналами. Далее обсудим идеи, которые лежат в основе алгоритмов быстрого преобразования Фурье, позволяющие значительно ускорить вычисления.

8.1. Спектр дискретного сигнала

Традиционным способом представления дискретного сигнала является представление в виде дельта-функции с соответствующими множителями и задержками:

X (kT) x(t) (t kT) ,	(8.1)

k

Где T – период дискретизации, x(t) – аналоговый исходный сигнал.

Применив к выражению (8.1) обычное преобразование Фурье, получим выражение для спектра дискретного сигнала.

62

S Д ( ) x(t)

(t kT) e j t dt ,		(8.2)
k

Поскольку преобразование Фурье линейно (спектр их сигналов равен сумме их спектров), спектра дельта функции равен единице, а задержка сигнала во времени приводит к умножению спектра на комплексную экспоненту, окончательно получаем

S Д ( ) X (kT) e j t ,	(8.3)

k

Из этой формулы видно главное свойство дискретного сигнала: спектр его является периодическим и его период равен f Д 1/ T , поскольку комплексная

экспонента принимает значения, равное 2π всякий раз, когда f Tn n f Д .

Таким образом, спектр дискретизированного сигнала представляет собой бесконечный ряд сдвинутых копий спектра исходного непрерывного сигнала x(t) (рис. 8.1). Расстояния между копиями спектра равно частоте дискретизации f Д 1/ T

( Д 2 f Д , 2 ).

Рисунок 8.1 наглядного демонстрирует и способ восстановления непрерывного сигнала по дискретным отсчетам. Для этого необходимо пропустить дискретный сигнал через идеальный фильтр нижних частот (ФНЧ) с частотой среза, раной половине частоты дискретизации. АЧХ такого фильтра показана на рис. 8.1 пунктиром.

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

Д B ,	(8.4)
63

Что полностью соответствует теореме Котельникова.

8.2 Дискретное преобразование Фурье

Как известно, непрерывная периодическая функция времени (аналоговый периодический сигнал) xa (t) с периодом TS , удовлетворяющая в

пределах периода условиям Дирихле, может быть представлена в виде ряда Фурье

xa (t) X a (k) e jk t ,

t

(8.5)

k

где Δω – период дискретизации

2

;

TS

X a (k) - коэффициенты Фурье

T

/ 2

X a

(t)

1

S xa (k) e jk t dt ,

(8.6)

TS

TS / 2

k – номер коэффициента Фурье, соответствующий частоте kΔω, т.е.

X a (k) X a (k ) ,

(8.7)

Множество коэффициентов Фурье X a (k) ряда

(8.5) называют

спектром непрерывной

периодической xa (t) ,

а

сами

коэффициенты –

комплексными гармониками на частотах k k

2

,

k

T

S

Периодическую дискретную последовательность xg (nT )

с периодом NT

(N – количество дискретных значений сигнала в одном его периоде, Т –

интервал между дискретными значениями),

2 NT , xg (nT ) xg (nT mNT ) ,

n=0,1,…,(N-1), m=…,-1,0,1,2,…

можно

представить

в

виде ряда,

аналогичного (8.5)

xg (nT ) X g (k) e jk nT ,

k ,

(8.8)

k

1

N 1

j

2

nk

где X (k) X (k )

X g (nT ) e

N

,

(8.9)

NT n 0

коэффициенты Фурье, k – номер коэффициента. Очевидно, что такое представление последовательности xg (nT ) ИЗБЫТОЧНО. Действительно, как

мы убедились в разделе 8.1 спектр дискретного сигнала представляет собой бесконечный ряд сдвинутых копий исходного аналогового сигнала. При этом для восстановления спектра исходного сигнала необходимо пропустить дискретный сигнал через идеальный ФНЧ.

С математической точки зрения прохождение дискретной последовательности через ФНЧ эквивалентно отказу от бесконечного суммирования по индексу k в (8.8), (рис. 8.2).

64

Рисунок 8.2 Бесконечная последовательность интервалов

Однако в пределах одного периода исходного сигнала находится N значений дискретного сигнала xg , тогда из (8.8) получаем соотношение

N 1	N 1	2
xg (nT) X (k) e jk nT X (k) e jk		N	n , n=0,1,…, (N-1),	(8.10)
k 0	k 0

Которое получило название дискретного ряда Фурье для последовательности во временной области.

Учитывая симметричность теоремы Котельникова относительно временной и частотной областей можно получить дискретный ряд Фурье для последовательности в частотной области. Иными словами, до сих пор мы рассматривали сигналы со спектром, ограниченными значениями верхней частоты fB . Аналогичные рассуждения для дискретной последовательности ограниченной во времени (например, числом N дискретных значений) приводят к дискретному ряду Фурье для последовательности в частотной области:

N 1	2
X (k) X (k) e jk	N	n , k=0,1,…,(N-1).	(8.11)

k 0

Сравнивая дискретные ряды (8.10) и (8.11) легко убедиться в их симметричности. Ряды Фурье (8.10) и (8.11) будут взаимно однозначными, если в один из них добавить коэффициент 1/N. Как правило, коэффициент 1/N добавляют в (8.10)

		1	N 1	2
	xg (nT )		X (k) e jk	N	n ,	n=0,1,…,N-1.	(8.12)
		N k 0
	Покажем, что при	подстановке				X g (k) из (8.11) в (8.12)	равенство

обращается в тождество. При подстановке, во избежание путаницы заменим в (8.11) индекс n на l и для простоты положим Т=1 (т.е. переходим к нормированному времени).

N 1

N 1

2

kl

2

1

j

j

nk

X g (n)

xg

(l)e

N

e

N

,

(8.13)

N k 0

l 0

Изменим порядок суммирования

65

		1	N 1	N 1	2	k (n l ) ,
	X g (n)		xg (l) e j				(8.14)
					N
		N l 0		k 0

и вычислим внутреннюю сумму. Очевидно, что при l=n она равно N.

N 1

e j 0 N ,

k0

апри l n , согласно формуле для суммы конечной геометрической прогрессии

j

2

N (n l )

N 1

2

k (n l )

1 e

N

1 e

j 2 (n l )

e j

N

,

j

2

(n l )

j

2

(n l )

k 0

1 e

N

1 e

N

Она равна нулю, поскольку числитель дроби равен нулю (при l=n, раскрыв неопределѐнность типа 0/0, получим значение суммы, равное N). Так как внешняя сумма в (8.14) содержит только одно отличное от нуля слагаемое при l=n, равенство (8.14) обращается в тождество

xg (n) xg (l) n l

Подводя итог сказанному ДИСКРЕТНЫМ ПРЕОБРАЗОВАНИЕМ ФУРЬЕ (ДПФ) будем называть пару взаимно однозначных дискретных рядов Фурье для дискретных последовательностей во временной и частотной областях:

N 1	j	2
X (k) X g (n) e		N	nk	, k=0,1,…,(N-1).	(8.15)

k0

-обратное преобразование (ОДПФ)

	1	N 1	j	2	nk
xg (n)		X (k) e		N		, n=0,1,…,(N-1).	(8.16)

N k 0

В формулах (8.15) и (8.16) обычно принимают обозначение для комплексной экспоненты в виде

							2
			W nk	e j					nk ,	(8.17)
							N
			N
и W nk e j	2	nk
	N		- носит название поворачивающего множителя, поскольку
N
					j	2		nk
аргумент экспоненты										отображает угол поворота на единичной
				e			N

окружности комплексной плоскости. Тогда окончательно ДПФ называется пара взаимно-однозначных преобразований:

- ДПФ:

66

			N 1
		X (k) x(n) WNnk , k=0,1,…,(N-1).				(8.18)
			k 0
- ОДПФ:
		1	N 1
	x(n)		X (k) WN nk ,	n=0,1,…,(N-1).		(8.19)
		N k 0
где x(n),	n=0,1,…,N-1 – последовательность				во временной	области
(вещественная или комплексная).
X (k) ,	k=0,1,…,(N-1) –			дискретные	коэффициенты	Фурье

(вещественные или комплексные) – один период последовательности в частотной области.

Последовательности x(n) и X(k) в (8.18) и (8.19) называют N- точечными.

Пример. Найти ДПФ N-точечной последовательности x(n) an .

Решение. Подставив x(n) an в формулу ДПФ (8.18), получаем сумму конечной геометрической прогрессии:

N 1

j

2

nk

N 1

j

2

nk

N 1

j

2

k n

X (k) x(n) e

N

a

e

N

N

,

n

k 0

k 0

k 0

равную

		j		2		k N
	1 a e			N
X (k)
	j		2		k

1 e	N

	1 eN				, k=0,1,…,N-1.
			2
	1 e	j		k
			N

и представляющую собой N-точечную ДПФ.

8.3 Свойства ДПФ

Перечислим (без доказательств) свойства ДПФ. Доказательства данных свойств могут быть выполнены самостоятельно.

1.Периодичность

N-точечное ДПФ является периодической последовательностью по

определению.

2.Линейность

Если N-точечная последовательность равна линейной комбинации N- точечных последовательностей

X (k) a1x1(n) a2 x2 (n) ...

то еѐ N-точечная ДПФ равна линейной комбинации N-точечных ДПФ данных последовательностей

67

X (k) a1 X1(k) a2 X 2 (k) ...

Если в линейной комбинации (8.20) у последовательностей разные длины N1, N2 , N3 ,... , то перед вычислением N-точечного ДПФ исходные

последовательности необходимо привести к одинаковой длине N, дополнив нулями N max{ N1 , N2 , N3 ,...} .

3. Сдвиг (смещение) N-точечного ДПФ:

Умножение N-точечной последовательности на поворачивающий

2

множетель WN k0 N e j N k0n приводит к сдвигу N-точечного ДПФ по оси k вправо на величину k0 , что символически удобно записать следующим образом:

x(n) X (k) x(n)WN k0 n X (k k0 )

Аналогично умножение N-точечного ДПФ по сои k влево на величину k0 , что символически удобно записать следующим образом:

x(n) X (k) x(n)WNk0 n X (k k0 )

4.Равенство (теорема) Парсеваля Равенство Парсеваля принимает вид:

N 1

где x(n)

	n 0
1	N 1
			X (k)		2
N k 0

	N 1			1	N 1
		x(n)	2				X (k)	2 ,
				N k 0
	n 0

2- энергия сигнала, вычисляемая о временной области;

-та же энергия, вычисленная в частотной области.

8.4 Быстрое преобразование Фурье

Математической основой спектрального анализа является ДПФ

N 1
X (k ) WNnk , k=0,1,…,N-1.	(8.20)

n 0

Оценим вычислительную сложность алгоритма ДПФ (8.20). При фиксированном значении k для значений n=0,1,…,(N-1) требуется выполнить N операций умножения и (N-1)≈N операций сложения, всего 2N операций. В целом же при k=0,1,…,(N-1) необходимо выполнить N 2N 2N 2 арифметических операций с комплексными числами. Таким образом, порядок вычислительной сложности алгоритма ДПФ (8.20) оценивается как O(N 2 ) , что при больших N весьма существенно. Для снижения порядка вычислительной сложности были разработаны алгоритмы быстрого вычисления ДПФ.

Быстрым преобразованием Фурье (БПФ) называют не ещѐ одну разновидность преобразования Фурье, а целый набор алгоритмов,

68

предназначенных для быстрого вычисления ДПФ: алгоритм БПФ с основанием 2, алгоритм БПФ с основанием 4, алгоритм Винограда и т.д. Наибольшее распространение получили алгоритм БПФ с основанием 2, известный как алгоритм БПФ Кули-Тьюки (по имени разработчиков) впервые опубликованный в 1965 г. в США. Существуют два эквивалентных по эффективности алгоритма БПФ с основанием 2: с прореживанием по времени и с прореживанием по частоте. В любом из них длина N исходной последовательности должна быть равной

N 2

где ν – целое положительное число.

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

8.4.1 Алгоритм БПФ с прореживание по времени

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

Начальные условия нормируются в результате однократного разбиения исходной N-точечной последовательности на две N/2-точечные. (рис. 8.3)

четных [x(0), x(2), …,x(N-2)] отсчѐтов					(8.21)
нечетных [x(1), x(3), …,x(N-1)] отсчѐтов					(8.22)
Начальная расстановка отсчѐтов производится по правилу:
N/2 чѐтных отсчѐтов;		N/2 нечѐтных отсчѐтов;
x(0), x(2), …,x(N-2);			x(1), x(3), …,x(N-1).
Это позволяет разбить сумму ДПФ (8.20) на две:
N 2		1		N 2 1
X (k) x(2n) WN2nk x(2n 1) WN(2n 1)k
	n 0			n 0
N 2 1				N 2 1
x(2n) WN2nk WNk x(2n 1) WN2nk
n 0				n 0
k=0,1,…,(N-1),					(8.23)
где x(2n) и x(2n+1) – N/2 – точечные последовательности чѐтных и
нечѐтных отсчѐтов соответственно.
Представим поворачивающий множитель WN2nk					в виде
W 2nk e j	2	nk e j	2
	N		N / 2	nk W nk	(8.24)
N				N / 2

Каждая из сумм представляет собой N/2 – точечное ДПФ: первая сумма

– ДПФ последовательности чѐтных отсчѐтов, а вторая – нечѐтных. Причѐм

69

каждое из N/2 – точечных ДПФ определяется		при k=0,1,…,N-1. Введѐм
обозначение
X 0 (k) X (k) ;		(8.25)
	N / 2 1
X 0 1 (k)	x(2n)WNnk/ 2 ;	(8.26)
	n 0
	N / 2 1
X1 1 (k )	x(2n 1)WNnk/ 2 ,	(8.27)

n 0

где верхний индекс указывает кратность ДПФ определяемого на данном этапе алгоритма. Кратность соответствует кратности ДПФ и начинается с ν с последующим убыванием на единицу.

БПФ, а нижний - номер ДПФ, чѐтный и нечѐтный. С учѐтом введѐнных обозначений перепишем БПФ (8.23):

N – точечное ДПФ определяется как комбинация двух N/2 – точечных

чѐтного X 0 1 (k) и нечѐтного X1 1 (k) :
X (k) X 1		(k) W k X 1 (k) , k=0,1,…,N-1.		(8.28)
0	0	N	1
Принимая во внимание,			что N/2 – точечное ДПФ X 0 1 (k) и	X1 1 (k) -

переодические функции переменной k с периодом N/2, нет необходимости определять их при k=0,1,…,N/2-1, а затем повторять при k=N/2, N/2+1,…,N- 1, т.е.

	X 0 (k) X 0 1 (k	N	) ,	k=0,1,…,N/2-1	(8.29)
		2
	X1 (k) X1 1 (k	N	) ,	k=0,1,…,N/2-1	(8.30)
		2

Поворачивающий множитель при k=N/2, N/2+1,…,N-1 равен

70