Книга по ЦОС в формате pdf

Добавил:

Studfiles2 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Предмет:

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

Файл:

определяет сигнал y3 реверсивный

3 = 4, Nν = N3 = 1, p = 0; l = 0, 1, 2, 3.

.pdf

Скачиваний:

220

Добавлен:

01.05.2014

Размер:

598.54 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 85 6 7 8 > Следующая >>>

Замечание 14.2. Отметим, что коэффициенты разложения (14.3) содержатся в таблице {xν (k)}, построенной по формулам (12.3). Таким образом, в процессе вычисления коэффициентов Фурье мы попутно вычис• ляем коэффициенты Хаара.

Формулы (14.6) допускают ображение:

ζν−1(2p) =	1	[ζν (p) + ζν (p + Nν )],

	2
ζν−1(2p + 1) =	1	(14.8)
		[ζν (p) − ζν (p + Nν )],
	2

p 0 : Nν − 1, ν = s, s − 1, . . . , 1.

При этом x(p) = ζ0(p), p 0 : N − 1. Получаем быстрый алгоритм восста• новления отсчетов сигнала x, представленного в виде (14.7), на основном периоде.

15.Прореживание по частоте

Если у всех сигналов ортогональной системы сделать одинаковую пе• рестановку аргумента, то преобразованные сигналы останутся попарно ор• тогональными. Это простое соображение позволяет строить новые ортого• нальные базисы в пространстве CN .

Пусть N = 2s и f0, f1, . . . , fs ортогональные базисы, определенные соотношениями (11.1) или (11.2). Положим

gν (k; j) = fν (rev s(k); rev s(j)),	ν 0 : s.
Согласно (11.5)
gs(k, j) = ωNrev s(k)j .	(15.1)

Очевидно, что при каждом ν 0 : s сигналы gν (0), gν (1), . . . , gν (N − 1) попарно ортогональны и kgν (k)k2 = 2ν при k 0 : N − 1.

Для новых базисов gν можно вывести формулы, аналогичные соотно• шениями (11.1) или (11.2).

Теорема 15.1. Справедливы рекуррентные соотношения

		g0(k) = δ(· − k), k 0 : N − 1;
g (2lN	ν	+ p) = g	ν−1	(lN	+ p) + ωrev s(2l)g	ν−1	(lN	ν−1	+ N	ν	+ p),
ν				ν−1	N
gν ((2l + 1)Nν + p) = gν−1				(lNν−1	+ p) − ωNrev s(2l)gν−1		(lNν−1		+ Nν + p),
		p 0 : Nν − 1,			l 0 : ν − 1, ν = 1, 2, . . . , s.

(15.2)

Рекуррентные соотношения (15.2) можно записать одной строкой

gν ((2l + σ)Nν + p) = gν−1(lNν−1 + p) + (−1)σ ωNrev s(2l)gν−1(lNν−1 + Nν + p).

(15.3) при тех же ограничениях на индексы p, l и ν, что и в соотношениях (15.2).

Для произвольного сигнала y CN при N = 2s можно получить его разложение по любому базису gν аналогично представлению (12.1)

1		N −1
y =		X
y =	2ν	yν (k)gν (k).	(15.4)
		k=0

Здесь yν (k) = hy, gν (k)i. Опираясь на (15.2), обычным путем приходим к рекуррентным соотношениям для коэффициентов yν (k) разложений (15.4)

y0(k) = y(k), k 0 : N − 1;

(2lN

+ p) = y

ν−1

(lN

ν−1

+ p) + ωrev s(2l)y

ν−1

(lN

ν−1

+ N

+ p),

yν ((2l + 1)Nν + p) = yν−1(lNν−1 + p) − ωNrev s(2l)yν−1(lNν−1 + Nν + p),

p 0 : Nν − 1,

l 0 :

ν − 1,

ν = 1, 2, . . . , s.

(15.5)

При ν = s согласно (15.1) получаем

N −1

ys(k) =

y(j)

(k; j) =

y(j)ωN− rev s(k)j = Y (rev s(k)).

gν

j=0

Отсюда следует, что для компонент спектра Фурье Y сигнала y справедли• ва формула

Y (k) = ys(rev s(k)), k 0 : N − 1.

Схема (15.5) называется алгоритмом Кули-Тьюки с прореживанием по частоте для вычисления дискретного преобразования Фурье .

Формулы (15.5) допускают обращение:
ys(k) = Y (rev s(k)), k 0 : N − 1;
yν−1(lNν−1 + p) =	1	(yν (2lNν + p) + yν ((2l + 1)Nν + p)) ,

	2
	1	rev s(2l)
yν−1(lNν−1 + Nν + p) =		ωN	(yν (2lNν + p) − yν	((2l + 1)Nν + p)) ,
	2
p 0 : Nν − 1, l 0 : ν − 1,				ν = s, s − 1, . . . , 1.

(15.6)

При этом y(k) = y0(k) при k 0 : N − 1. 42

Пример 15.1. Рассмотрим работу схемы (15.5) для s = 3, т. е. вычисление БПФ для N = 8 алгоритмом Кули-Тьюки с прореживанием по частоте.

При ν = 1 : ν = 1 = 1, Nν = N1 = 4, p = 0, 1, 2, 3; l = 0. Получаем

”бабочки“

		y1(0) = y0(0) + y0						(4),	y1(4)			= y0(0)				− y0(4),
		y1(1) = y0(1) + y0						(5),	y1(5)			= y0(1)				− y0(5),
		y1(2) = y0(2) + y0						(6),	y1(6)			= y0(2)				− y0(6),
		y1(3) = y0(3) + y0						(7),	y1(7)			= y0(3)				− y0(7).
При ν = 2 :		ν =			2 = 2, Nν = N2 = 2, p = 0, 1; l = 0, 1. Имеем
y2(0)			= y1(0) +			y1		(2),	y2(2)			= y1(0)				−	y1		(2),
y2(1)			= y1(1) +			y1		(3),	y2(3)			= y1(1)				−	y1		(3),
y	2	(4)	=	y	1(4) +	ω−2y	1	,	y	2	(6)	=	y	1	(4)	−	ω−2y	1	,
						8		(6)									8		(6)
y	2	(5)	=	y	1(5) +	ω−2y	1	,	y	2	(7)	=	y	1	(5)	−	ω−2y	1	,
						8		(7)									8		(7)

где ω8−2 = cos	2π	− i sin	2π

	8		8

Последний этап, при ν = спектр сигнала y. Имеем Тогда

√√


y3		(0)		= y2(0)					+		y2		(1),			y3(1)			= y2(0) −					y2		(1),
y	3	(2)		=	y	2	(2)		+	ω−2y		2	(3)	,		y	3	(3)	=	y	2		(2) −	ω−2y	2	,
										8														8		(3)
y	3	(4)		=	y	2	(4)		+	ω−1y		2	(5)	,		y	3	(5)	=	y	2		(4) −	ω−1y	2	,
										8														8		(5)
y	3	(6)		=	y	2(6)			+	ω−3y		2	(7)	,		y	3	(7)	=	y	2		(6) −	ω−3y	2	,
										8														8		(7)
где ω8−1 = cos			π					π	, ω8−3						3π				3π
				− i sin							= cos					− i sin						.
			8					8						8						8

При этом

Y (0) = y3(0), Y (1) = y3(4), Y (2) = y3(2), Y (3) = y3(6),

Y (4) = y3(1), Y (5) = y3(5), Y (6) = y3(3), Y (7) = y3(7).

Приведенные действия легко представить в виде графа, аналогичного

графу из примера 12.1

(0)

//y1

(0)

//y2

(0)

•

(1)

//y

(1)

•

//y

(1)

•

?•

•

•?

•

(2)

//y1

(2)

(−1)

•

//y2

(2)

•

y0(3)

///

•

(−1)

//y1(3)

//y2(3)

////

///

////

/////

////

y0(4)

//(−1)

//y1(4)

//y2(4)

•

−

•

(ω

)

•

(5)

(−1)

///

//y1

(5)

•

//y2

(5)

•

?•

•?

−

•?

•

(ω

)

•

−2

•

(6)

(−1)

///

//y1

(6) (−ω8

)

•

//y2

(6)

•

y0(7)

(−1)

//y1(7)

(−ω8−2)

//y2(7)

//y3

(0)

(−1)

//y3

(1)

//y3

(2)

(ω8−2)

−(ω8−2)

//y3

(3)

//y3

(4)

(ω8−1)

−(ω8−1)

//y3

(5)

//y3

(6)

(ω8−3)

−(ω8−3)

//y3(7)

//Y (0)

//Y (4)

//Y (2)

//Y (6)

//Y (1)

//Y (5)

//Y (3)

//Y (7)

16.Базисы Уолша.

Построим еще одну последовательность ортогональных базисов

	wν = {wν (k; j)}kN=0−1, ν = 0, 1, . . . , s
с помощью рекуррентных соотношений
	w0(k) = δ(· − k), k 0 : N − 1;
wν (l + p	ν+1) = wν−1(l + 2p	ν ) + wν−1(l + (2p + 1)Δν ),	(16.1)
wν (l + ν + p	ν+1) = wν−1(l + 2p	ν ) − wν−1(l + (2p + 1)Δν ),
	p 0 : Nν − 1,	l 0 : ν − 1, ν = 1, 2, . . . , s.

Эти формулы отличаются от (11.1) только тем, что коэффициент ωl

ν+1

заменен на единицу. Как и ранее переход от базиса wν−1 к базису wν можно записать одной строкой

wν (l + σ ν + p ν+1) = wν−1(l + 2p ν ) + (−1)σ wν−1(l + (2p + 1)Δν ) (16.2)

при тех же ограничениях на индексы p, l и ν, что и в соотношениях (16.1). В частности, при ν = 1

w1(σ + 2p) = w0(2p) + (−1)σ w0(2p + 1), p 0 : N − 1, σ 0, 1.					(16.3)
Что представляют собой сигналы ws(k; j)? Для ответа на этот вопрос
нам понадобятся некоторые дополнительные сведения.
Введем последовательность матриц
1	1	Aν−1	Aν−1
A1 = 1 −1 ;		Aν = Aν−1	−Aν−1 ,	ν = 2, . . . , s.	(16.4)
Матрица Aν называется матрицей Адамара. Это квадратная матрица по•
рядка ν+1.	ν+1−1, k = (kν−1, kν−2, . . . , k0)2, j = (jν−1, jν−2, . . . , j0)2.
Пусть k, j 0 :
Положим			ν−1
			ν−1
		{k, j}ν = kαjα.
			α
			X
Теорема 16.1. Для элементов матрицы Адамара справедлива фор•
мула			k, j 0 :	ν+1 − 1.
Aν [k, j] = (−1){k,j}ν ,			k, j 0 :	ν+1 − 1.	(16.5)
Доказательство. При ν = 1 утверждение очевидно, поскольку
		A1[k, j] = (−1)kj , k, j 0, 1.
Сделаем индукционный переход от ν − 1 к ν.
Возьмем k, j 0 :		ν+1 − 1 и представим их в виде
k = kν−12ν−1 + l,	j = jν−12ν−1 + q, где kν−1, jν−1 0, 1, l, q 0 :				ν − 1.
Согласно (16.4)	Aν [k, j] = (−1)kν−1jν−1 Aν−1[l, q].
	Aν [k, j] = (−1)kν−1jν−1 Aν−1[l, q].				(16.6)

Принимая во внимание индукционное предположение, получаем

Aν [k, j] = (−1)kν−1jν−1+{l,q}ν−1 = (−1){k,j}ν .

Теорема 16.2. Имеет место представление

Xν+1−1

wν (l + p	ν+1) =	Aν [l, q]w0(q + p	ν+1),	(16.7)
	q=0
где p 0 : Nν − 1, l 0 :	ν+1 − 1, ν = 1, . . . , s.
При ν = s формула (16.7) принимает вид
N −1
X			l, j 0 : N − 1.
ws(l, j) = As[l, q]δN (j − q) = As[l, j] = (−1){l,j}s ,			l, j 0 : N − 1.
q=0
Функции		k, j 0 : N − 1,
vk(j) = (−1){k,j}s ,		k, j 0 : N − 1,
называются дискретными функциями Уолша. Таким образом
ws(k, j) = vk(j),		k, j 0 : N − 1.		(16.8)
Замечание 16.1. Функции Уолша принимают только два значения
+1 и −1.
Теорема 16.3. При каждом v 1 : s сигналы
wν (0), wν (1), . . . , wν (N − 1)				(16.9)

попарно ортогональны и kwν (k)k2 = 2ν при всех k 0 : N − 1.

Таким образом при каждом ν 0 : s сигналы (16.9) образуют ортого• нальный базис в пространстве CN .

Пример 16.1. Рассмотрим базис Уолша при s = 3. Для удобства составим таблицу значений {k, j}3. Oчевидно, что {k, j}s = {j, k}s.

k/j	0	1	2	3	4	5	6	7

0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0	1
2	0	0	1	1	0	0	1	1
3	0	1	1	2	0	1	1	2
4	0	0	0	0	1	1	1	1
5	0	1	0	1	1	2	1	2
6	0	0	1	1	1	1	2	2
7	0	1	1	2	1	2	2	3

Тогда
v0 = {1, 1, 1, 1, 1, 1, 1, 1},	v1 = {1, −1, 1, −1, 1, −1, 1, −1},
v2 = {1, 1, −1, −1, 1, 1, −1, −1},	v3 = {1, −1, −1, 1, 1, −1, −1, 1},
v4 = {1, 1, 1, 1, −1, −1, −1, −1},	v5 = {1, −1, 1, −1, −1, 1, −1, 1},
v6 = {1, 1, −1, −1, −1, −1, 1, 1},	v7 = {1, −1, −1, 1, −1, 1, 1, −1}.

17.Быстрое преобразование Уолша

Возьмем сигнал x CN . При каждом ν 0 : s его можно разложить по базису (16.9)

1		N −1
x =		X
x =	2ν	xν (k)wν (k).	(17.1)
		k=0

Здесь xν (k) = hx, wν (k)i. На основании (16.1) приходим к рекуррентным соотношениям для последовательного вычисления коэффициентов разло• жения (17.1):

xν (l + p xν (l + ν + p

x0(k) = x(k), k 0 : N − 1;
ν+1) = xν−1(l + 2p	ν ) + xν−1(l + (2p + 1)Δν ),	(17.2)
ν+1) = xν−1(l + 2p	ν ) − xν−1(l + (2p + 1)Δν ),
p 0 : Nν − 1,	l 0 : ν − 1, ν = 1, 2, . . . , s.

При ν = s получаем согласно (16.8) разложение сигнала x по базису Уолша

1		N −1
x =		X
x =	N	xs(k)vk.	(17.3)
		k=0

Схема (17.2) называется быстрым преобразованием Уолша, связан• ным с прореживанием по времени. Эта схема использует только сложения в количестве N log2 N операций.

Соотношения (17.2) допускают обращение

xν−1(l + 2p ν ) = 2 (xν (l + p

xν−1(l + (2p + 1)Δν ) = 2 (xν (l + p p 0 : Nν − 1,

ν+1) + xν (l +	ν + p ν+1) ,
ν+1) − xν (l +	ν + p ν+1)) ,
l 0 : ν − 1,	ν = s, s − 1, . . . , 1.
	(17.4)

При этом x(k) = x0(k), k 0 : N − 1. Получаем быстрый алгоритм восста• новления отсчетов сигнала x, представленного в виде (17.3), на основном периоде.

18.Элементарная теория вероятностей

18.1.Основные определения

Введем в рассмотрение конечное множество элементарных событий S, его элементы считаются равноправными, равновероятными. Любое со• бытие A считается подмножеством S и состоит из элементарных событий. Отношение |A|/|S| называется вероятностью события A и обозначается че• рез P (A).

Событие, вероятность которого равна 1 называется достоверным – оно наступает всегда.

Событие, вероятность которого равна 0 называется невозможным – оно не наступает никогда.

При сопоставлении событий требуется также, чтобы вероятность собы• тия A, содержащегося в другом событии B, имела вероятность не превос• ходящую вероятности B (события это множества и они могут содержаться одно в другом).

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

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

Пример 18.1. При бросании двух игральных костей вероятность по•

лучить не менее 11 очков равна 36, так как всего имеется 36 равновоз•

можных исходов и 3 из них благоприятны – (5,6),(6,5),(6,6).

Было бы неверным считать, что так как может выпасть от 2 до 12 очков и благоприятными являются 2 исхода из этих 11, то искомая

вероятность равна 11. Исходы типа ”числа выпавших очков“ не явля•

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

Упражнение 18.1. Найдите вороятность того, что на первой ко•

сти выпадет очков больше, чем на второй. Ответ: 36.

Событие, которое составлено из элементарных событий, входящих од• новременно в события A и B, называется совмещением этих событий. Та• ким образом множество элементарных событий, входящих в совмещение,

– это пересечение соответствующих множеств. Очевидно, что вероятность совмещения событий не превосходит вероятности каждого из этих событий.

Оба этих определения легко переносятся на несколько событий. Разбиение множества элементарных событий S на несовместные собы•

тия S1, S2, . . . , Sm называется полной системой событий. Каждое событие A можно представить, как объединение несовместных событий – совмеще• ние A с элементами разбиения Si. Очевидно, что

P (A) = P (A ∩ Si).	(18.1)
i=1

Эта формула называется формулой полной вероятности.

Введем понятие независимых событий. События A и B называются независимыми, если вероятность их совмещения равна произведению их вероятностей:

P (A ∩ B) = P (A) × P (B).

В случае нескольких событий A1, A2, . . . , Ak следует различать попар• ную независимость этих событий и их независимость в совокупности. В первом случае

P (Ai ∩ Aj ) = P (Ai) × P (Aj ) при i 6= j,

во втором случае (более жесткое требование)

P (A1 ∩ A2 ∩ · · · ∩ Ak) = P (A1) × P (A2) × · · · × P (Ak).

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

Пример 18.2. Рассмотрим игральную кость в виде правильного тет• раэдра6. Одна грань этого тетраэдра выкрашена в белый цвет W, вторая в черный B, третья – в красный R, а окраска четвертой грани – смешанная M, в ней есть все три цвета. При каждом бросании кость равновероятно ложится какой-то стороной вниз. Вероятность того, что на этой гра• ни окажется белый, красный или черный цвет равна, очевидно, 1/2, так

6Пример предложен С.Н.Бернштейном

как для этого события благоприятны два исхода из четырех возможных. Вероятность выпадения двух цветов сразу, например, красного и черного равна 1/4 и не зависит от набора цветов. Таким образом для событий выпал красный цвет и выпал церный цвет имеем:

P (R ∩ B) = P (R) × P (B),

и по определению эти два события независимы. С другой стороны веро• ятность выпадения трех цветов

P (R ∩ B ∩ W ) =	1		1
		6= P (R) × P (B) × P (W ) =		,
	4		8

и независимости в совокупности нет.

18.2.Условные вероятности и формула Байеса

При работе с зависимыми случайными событиями необходимо учиты• вать их взаимное влияние на вероятностное поведение. Это влияние про• является в том, что осуществление одного события, может изменить веро• ятности других событий и приходится говорить о вероятностях событий в тех или иных условиях. Введем следующее определение.

Пусть A – некоторое событие, имеющее положительную вероятность (то есть не невозможное событие). Определим для события B условную вероятность B при условии A как отношение

P (B|A) = P (B ∩ A).

P (A)

Замечание 18.1. Очевидно, что таким образом определенные услов• ные вероятности обладают всеми свойствами обычных вероятностей: они меняются от 0 до 1, возрастают с расширением события, условная вероятность объединения несовместных событий равна сумме их услов• ных вероятностей.

Используя понятие условной вероятности можно по другому опреде• лить понятие независимости событий: события A и B независимы, если

P (B|A) = P (B).

В терминах условной вероятности можно по другому записать форму• лу полной вероятности (18.1):

P (A) = P (A\|Si)P (Si).	(18.2)
i=1

<<< < Предыдущая 1 2 3 45 / 85 6 7 8 > Следующая >>>

Соседние файлы в предмете Цифровая обработка сигналов

#
01.05.2014351.23 Кб30Введение в компрессию сигнальной информации.doc
#
01.05.20141.75 Mб31Введение в компрессию формата MPEGAUDIO.doc
#
01.05.20142.68 Mб285Вейвлет-преобразование в задачах цифровой обработки сигналов.doc
#
01.05.20142.43 Mб44Дельта-модуляция.DOC
#
01.05.201499.84 Кб128Дискретное преобразование Фурье.doc
#
01.05.2014598.54 Кб220Книга по ЦОС в формате pdf.pdf
#
01.05.20141.09 Mб23Компрессия данных.DOC
#
01.05.2014352.77 Кб55Компьютерное аудио - форматы аудио-файлов и методы компрессии.doc
#
01.05.2014441.34 Кб74Компьютерный синтез речи. Realspeak Solo Katerina.doc
#
01.05.2014749.57 Кб39Лабораторная работа №6.doc
#
01.05.2014364.03 Кб29Лабораторная работа №61.doc

k/j	0	1	2	3	4	5	6	7

0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0	1
2	0	0	1	1	0	0	1	1
3	0	1	1	2	0	1	1	2
4	0	0	0	0	1	1	1	1
5	0	1	0	1	1	2	1	2
6	0	0	1	1	1	1	2	2
7	0	1	1	2	1	2	2	3

k/j	0	1	2	3	4	5	6	7

0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0	1
2	0	0	1	1	0	0	1	1
3	0	1	1	2	0	1	1	2
4	0	0	0	0	1	1	1	1
5	0	1	0	1	1	2	1	2
6	0	0	1	1	1	1	2	2
7	0	1	1	2	1	2	2	3

k/j	0	1	2	3	4	5	6	7

0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0	1
2	0	0	1	1	0	0	1	1
3	0	1	1	2	0	1	1	2
4	0	0	0	0	1	1	1	1
5	0	1	0	1	1	2	1	2
6	0	0	1	1	1	1	2	2
7	0	1	1	2	1	2	2	3