Цифровая обработка сигналов: Справочник - Гольденберг Л.М.
Скачать (прямая ссылка):
ДПФ на многомерное (см. 1.3.3).
Пример 1.10. Рассмотрим случай N=6. Пусть Ni=3; N3=2. Сеглаено (1.34)
положим:
п = /zx * ^ "I- ^21 к = &х • 2 -|- k%;
?х, лх = 0,1,2; ^2."П2 = 0,1.
Из Si-3= 1 (mod 2); si<2; s2-2=l(mod3); s2<3 найдем: sx= 1; s2=2. Получим
элементы вектора x{nT) из x(tiT) перестановкой (1.35)
Х(0)
I
а
х(0!
и элементы выходного вектора X{k) из X (к) перестановкой (1.36)
XW)
1
ХЮ1
Х(5)
1
Х(5)
Согласно (1.39)
Х(йх.2 + ад = 2 (]? *("1-2 + л^^2*п") Щ'*1.
"1=0 \п2=0 /
Соответствующий направленный граф изображен на рис. 1.12.
Рис. 1.12 20
Вычисление /-мерного ДПФ (см. 1.3.3) сводится к вычислению Nit N-2, Л';-
точечных ДПФ, для реализации которых могут быть использованы алгоритмы
БПФ.
1.4. ДИСКРЕТНАЯ СВЕРТКА И ЕЕ ВЫЧИСЛЕНИЕ
1.4.1. Круговая свертка
Пусть х(пТ) и h(nT) -две периодические последовательности с периодами по
N отсчетов.
Круговой (периодической или циклической) сверткой таких
последовательностей называется последовательность у{пТ), определяемая
соотношением
N-1
г/("7') = 2 h(lT)x((n-/) Т). 1=о
Запись (1.40) эквивалентна записи
N- 1
у(пт)=2 *тщп-1) т). 1=0
(1.40)
(1.41)
Последовательность у(пТ) также является периодической с периодом в N
отсчетов, поэтому достаточно вычислять ее на одном периоде, например при
п- = 0,..., N-1.
Соотношения (1.40) и (1-41) справедливы и для конечных
последовательностей х(пТ), h(nT) (п=0,...............N-1), если
рассматривать их как один период
соответствующих нм периодических последовательностей. Круговая свертка
конечных последовательностей будет также конечной.
В матричной форме круговая свертка имеет вид
у=Нх или y = Xh, (1-42).
где у, h, х - Лт-мерные векторы;
У = [г/(0), у(Т),..., y((N- 1)Т)]т; Ь = [Л(0), h((N- 1) Т) h(T)]h
х = [# (0), х ((N-I) T),..., х(Т)]т,
а Н и X - циклические матрицы размера NXN:
'h(0)h(T)...h((N-\)T) h(T)h(2T)...h(0)
Н= h (2Т) h (ЗГ). • .h (Т) J; (1.43)
X
_h((N-l)T)...h((N-2)T) x(0)x(T)...x((N-l)T) -
x(T)x(2T)...x(0) x (2T) x (3T).. .x (T)
(1.44>
L* ((A-l)T)...x ((N-2) T)_
Пример 1.11. Вычислить круговую свертку последовательностей х(пТ) длины
Л7 и h(nT)=&((n-tic)T), п0>0.
Представим h(nT) в виде последовательности длины N:
21
h(nT) =
0 прн 0^п<п0;
1 при п = По;
,0 при -!•
На рис. 1.13 приведена графическая иллюстрация вычисления круговой
свертки по формуле (1.40) для N=4 и n0= 1. Здесь исходные конечные
последовательности периодически продолжены с периодом N отсчетов
(пунктиром), чтобы показать, как получается круговой сдвиг. Звездочками
обозначены выборки, составляющие у(пТ). Результирующая последовательность
у[пТ) представляет собой последовательность х(пТ), сдвинутую на "о
отсчетов вправо.
| ?? 111?
Х(1Т)
? 9
9 I
I i I | I |
M
?1 ill
с
? I 0 1 I 9
i
X(U-UT)
9 о
?! i
I I 9
¦ i .1 i I .
? 9 I ? 9
? I I I ? I !
i ?л ? I ? 111 ? I
? ? ?
9 I T 9 1
II?! 19 i 1 i i 1. 1..I .
<?
! 9 i
X((3~L)T) I *
9 I i i 9
.. i i i i I
?
9 ? 9 j "
i 9 i I 9 I I ? I
9 I I 1 ? I I I 9 i I 1
i i i i i i i i i I i I
у CnT)
i
Puc. 1.18
Дискретная свертка является одним из способов вычисления выходного
сигнала цифрового фильтра по заданному входному сигналу и известной
импульсной характеристике фильтра (см. 2.3.3).
1.4.2. Использование ДПФ для вычисления круговой свертки
Круговая свертка двух последовательностей х(пТ) и h(nT) может быть
вычислена в результате выполнения следующих действий:
22
1. Вычисления ДПФ последовательности х{пТ):
N-1
X(k)='2 x(nT)WnNk, А -0....................-1. (1.45)
п=О
2. Вычисления ДПФ последовательности h(tiT):
N-1
H(k) = h{nT)Wf, k = 0,..., N-l. (1.46}
n=0
3. Перемножения коэффициентов полученных ДПФ:
Y(k) = X(k)'H(k), й=0 N-l. (1.47)
4. Вычисления ОДПФ последовательности Y(k):
1
IV-1
у (пТ) = - У! У (к) Щпкг п = 0,...., N- 1. (1.48)
N k=0
Последовательность у(пТ) есть искомая свертка.
Пример 1.12. Решить пример 1.11 с использованием ДПФ.
Пусть ДПФ последовательности х(пТ) равно X(k). Из (1.19) ДПФ по*
следовательности h{tiT) равно H(k) = , k=0, ..., N-I. Перемножим
X(к)
и H(k): Y(k)=X(k)Wx°k, k=0........... N-1. Согласно свойству сдвига (см.
1.3.2) ОДПФ последовательности Y(k) равно х ((я-До) Т). (Сравните с
результатом примера 1.11.)
1.4.3. Линейная свертка
Линейной (апериодической) сверткой двух конечных последовательностей
х{пТ) и h{nT) по N1 н N2 отсчетов соответственно называется
последовательность у(пТ), определяемая соотношением
y(nT)^j]h(lT)x((n- 1)Т), д = 0............. Nx + Nz-2, (1.49)
1=0
или
y(nT) = j]x(lT)h((n - 1)Т), п= О,..., N-l + Nz-2.
Z=o
Последовательность у(пТ) является также конечной и имеет длину Л^+Л^-1
отсчетов.
Сформируем последовательности Х\{пТ) и hi (пТ) длиной по Nt+N2-1
отсчетов:
х <пТ) = 1Х{пГ) ПрИ " = Nl~1; /1 5оу
1 (О при n = N1,..., Nx-^Nz-2;
hi(nT)==fh(nT) при " = 0..... JV.-1: (Ш>
Хо при n = N2,..., N-i-\-Nz-2.
Тогда линейная свертка последовательностей х(пТ) и h(nT) будет равна
(A'i+ +N2-1)-точечной круговой свертке последовательностей Х\{пТ) и
