Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341:DISCRETE-TIME SIGNAL PROCESSING OpenCourse Ware 2006 Lecture 22 Modulated Filter Bank Reading:Review Section 4.7 of OSB;also carefully study the figures in this handout. In this lecture,we will tie together some relationships between modulated filter banks(MFB) for time-dependent Fourier transform(TDFT),polyphase structure,and performing the discrete Fourier transform(DFT)through the fast Fourier transform(FFT). Similarity between the general form of a branch of the MFB and the decimation filter suggests that a polyphase implementation of the MFB is possible.As a first step,consider a single filter-downsampler pair in the parallel structure: holn] ↓R voln] xn] hkin] ↓R vhin] hw-i(n] ↓R UN-1[n] A typical modulated filter bank. Recall that a possible polyphase decomposition of an impulse response hn]is to downsample successively advanced (rather than delayed)versions of it: 1
Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.341: Discrete-Time Signal Processing OpenCourseWare 2006 Lecture 22 Modulated Filter Bank Reading: Review Section 4.7 of OSB; also carefully study the figures in this handout. In this lecture, we will tie together some relationships between modulated filter banks (MFB) for time-dependent Fourier transform (TDFT), polyphase structure, and performing the discrete Fourier transform(DFT) through the fast Fourier transform(FFT). Similarity between the general form of a branch of the MFB and the decimation filter suggests that a polyphase implementation of the MFB is possible. As a first step, consider a single filter-downsampler pair in the parallel structure: A typical modulated filter bank. Recall that a possible polyphase decomposition of an impulse response h[n] is to downsample successively advanced (rather than delayed) versions of it: 1
n hn。hn IR eon ↑R ioln,h包 2-1 h[m-1 IR eiln] ↑R hiin] elm] hin-2 IR e2[n] R h2in] 心 e2[n] hin-R+1] IR eR-1in] ↑R An-iin] Polyphase decomposition of hn] Written analytically,such a decomposition applied to the prototype filter Ho(z)and the mod- ulated filters Hk(z)is: hon]Ho(z)=Hoo(R)+Ho(R)+...+(R-1)Ho(R-1)(2R) R-1 PHp(eR) p=0 R-1 sm=台s()=Ho(e装)=∑e-2Hp(e-2装2A) p=0 R-1 =∑PH(e, p=0 where Hop(z)is the p-th polyphase component of Ho()and Hp()=Hop(e) is the p-th polyphase component of Hk(z).This decomposition suggests implementing the k-th filter of the MFB with the following polyphase structure: cin] Hxo(zR) IR rn] R xon】 Hxo(z) 味切 Hg1(2R) tIin] Hx(2) · HkR-e用 ER-1n Hk(R-1)(2） Polyphase implementation of the k-th branch of the MFB 2
Polyphase decomposition of h[n] Written analytically, such a decomposition applied to the prototype filter H0(z) and the modulated filters Hk(z) is: h0[n] ⇔ H0(z) = H00(zR) + zH01(zR) + . . . + z(R−1)H0(R−1)(zR) = R �−1 p=0 zpH0p(zR) hk[n] = ejωknh0[n] ⇔ Hk(z) = H0(ej 2πk N z) = R �−1 p=0 e−j 2πkp N zpH0p(e−j 2πkR N zR) = R �−1 p=0 zpHkp(zR) , where H0p(z) is the p-th polyphase component of H0(z) and Hkp(zR) = e−j 2πkp N H0p(e−j 2πkR N zR) is the p-th polyphase component of Hk(z). This decomposition suggests implementing the k-th filter of the MFB with the following polyphase structure: Polyphase implementation of the k-th branch of the MFB 2
The output V(z)of the k-th branch is a linear combination of intermediate signals rkn] Xk(z),0≤k≤R-1: R-1 Vi(z)=>Xp(=)Hkp(),Hkp(z)=e Hop(e 2). p=0 Observe that xo[n],x1[n],...,R-n]are the polyphase components of the input sequence x[n]. Because they are common to each parallel branch of the MFB,we can share them at the input to obtain the following amalgamated structure: MIMO system R-inputs N-outputs tn IR coln] voln] IR n +h[n] H IR xaln] +2[n] IR ZR-1[n] UN-1[n] Polyphase implementation of the MFB In this system: Filter bank output rate N No.of filter bank channels =N. Filter bank input rate R The transfer function matrix H satisfies Xo(z) 6(z) X1(z) (z） XR-1(2) VN-1(2) Hp()=eop(ej特z). Such a polyphase implementation is preferred over the direct implementation of the MFB because it is more efficient in terms of computational complexity.To see why this is true, assume our system operates with complex arithmetic.In the original system: 3
� The output Vk(z) of the k-th branch is a linear combination of intermediate signals xk[n] Xk(z),0 ≤ k ≤ R − 1: ⇔ R−1 p=0 Observe that x0[n], x1[n], . . . , xR−1[n] are the polyphase components of the input sequence x[n]. Because they are common to each parallel branch of the MFB, we can share them at the input to obtain the following amalgamated structure: Polyphase implementation of the MFB In this system: Filter bank output rate = N No. of filter bank channels = N, . Filter bank input rate R The transfer function matrix H satisfies Hkp(z) = e−j 2πkp H0p(e−j 2πk V N N k(z) = Xp(z)Hkp(z) , z) . ⎡ ⎢ ⎢ ⎢ ⎢ ⎧ ⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎩ ⎡ ⎢ ⎢ ⎢ ⎢ ⎤ ⎥ ⎥ ⎥ ⎥ X0(z) X1(z) ⎡ ⎢ ⎢ ⎢ ⎢ ⎤ ⎥ ⎥ ⎥ ⎥ V0(z) V1(z) ⎤ ⎥ ⎥ ⎥ Hkp ⎥ N (z) . = . . . ⎣ ⎣⎦ . ⎦ ⎣ . ⎦ XR−1(z) VN−1(z) Hkp(z) = e−j 2πkp H0p(e−j 2πk N N z) . Such a polyphase implementation is preferred over the direct implementation of the MFB because it is more efficient in terms of computational complexity. To see why this is true, assume our system operates with complex arithmetic. In the original system: 3
Input x[n]clocked at 1 sample/unit time total of LN Each modulated filter hkn]is of length L complex multiplies/input sample N modulated filters he[n]in the MFB In the polyphase implementation: Input subsequence xk[n]clocked at sample/unit time Each polyphase component filterp is of length ())(R)(N)= R polyphase components for each modulated filter hknl multiplies/input sample N modulated filters hkn]in the MFB A polyphase structure hence gives reduction in the required number of multiplications.To take one step further,let's consider in more detail the R-input,N-output MIMO structure on the previous page.If we let R=N,each polyphase component filter simplifies to Hkp(z)=e Hop(), 0≤k≤N-1,0≤p≤R-1=N-1. Such a system is said to be critically sampled.Its outputs are N N- V(z)= ∑Xa(e)(ee-g-∑xlap(ew7, 0≤k≤N-1. p=0 p=0 Gp(z)÷gpn Looks familiar?This is the N-point DFT of gpn].It gives rise to the following structure: NxN N zon] Hoo(z) goln] →o[ml N zin gin Ho1(2) -viIn] w N t2n g2 n Ho2(2) +2[m N TN-1n gw-in] w-1(2 vN-1[n] N-point DFT Polyphase implementation of the MFB using DFT/FFT N-1 vn]=gpln]W=N-point DFT of gpln]at each n p=0 4
� � � �� � � Input x[n] clocked at 1 sample/unit time Each modulated filter hk[n] is of length L N modulated filters hk[n] in the MFB In the polyphase implementation: ⎭ ⇒ ⎫ ⎪⎬ ⎪ total of LN complex multiplies/input sample ⎫ ⎪⎪⎪⎬ ⎪⎪⎪⎭ ( 1 R)(R)(N) = LN R)( L ⇒ R multiplies/input sample Input subsequence xk[n] clocked at 1 sample/unit time R L Each polyphase component filter hkp[n] is of length R R polyphase components for each modulated filter hk[n] N modulated filters hk[n] in the MFB 1 A polyphase structure hence gives R reduction in the required number of multiplications. To take one step further, let’s consider in more detail the R-input, N-output MIMO structure on the previous page. If we let R = N, each polyphase component filter simplifies to Hkp(z) = e−j 2πkp N H0p(z) , 0 ≤ k ≤ N − 1 , 0 ≤ p ≤ R − 1 = N − 1 . Such a system is said to be critically sampled. Its outputs are N−1 N−1 p=0 p=0 Xp(z)H0p(z)e−j 2πkp N Xp(z)H0p(z) Gp(z)⇔gp[n] Wkp N Vk(z) = = , 0 ≤ k ≤ N − 1 . Looks familiar? This is the N-point DFT of gp[n]. It gives rise to the following structure: Polyphase implementation of the MFB using DFT/FFT N−1 p=0 4 Wkp N vk[n] = gp[n] = N-point DFT of gp[n] at each n
The N-point DFT in this system can be efficiently computed using the FFT.With both the polyphase structure and the FFT in place: Input [n]clocked at sample/unit time 卡mul/input sample Each polyphase component filteris of length → to compute gp[n], N channels in the MFB 0≤p≤N-1 gpl[n,0≤p≤N-l,clocked at录sample/unit time l0g2 N mul/input sample Nlog2 N multiplies for the FFT for the FFT This yields a total of+log2 N multiplications/input sample.Clearly the polyphase structure with FFT gives a large efficiency improvement in comparison to the direct implementation of MFB.Summarizing,the total number of multiplications required by each implementation is: Direct implementation (LN) multiplies/input sample Polyphase implementation ( multiplies/input sample Polyphase,N=R,FFT (+log2 N)multiplies/input sample As a conclusion to our discussion on the polyphase implementation of the MFB with FFT, here are two special cases of the system we have derived: Special Case 1:L=N=R L length of the window,length of the prototype filter N desired number of modulated filters, sampling rate of the TDFT in the frequency domain R amount of shift by the window at each time step, down sampling rate of the TDFT in the time domain Assume the prototype filter has the following impulse response: hon -N+1 0 Its polyphase decomposition is hooln]=hoolδ[ml,.,hop[m=ho-pδml. 5
� The N-point DFT in this system can be efficiently computed using the FFT. With both the polyphase structure and the FFT in place: ⎭ ⇒ ⎫ ⎪⎬ ⎪ Input xk[n] clocked at 1 sample/unit time N L mul/input sample N L Each polyphase component filter hkp[n] is of length N to compute gp[n], N channels in the MFB 0 ≤ p ≤ N − 1 [n], 0 ≤ p ≤ N − 1, clocked at 1 sample/unit time N N log2 N multiplies for the FFT log2 N mul/input sample ⇒ for the FFT gp L This yields a total of N +log2 N multiplications/input sample. Clearly the polyphase structure with FFT gives a large efficiency improvement in comparison to the direct implementation of MFB. Summarizing, the total number of multiplications required by each implementation is: Direct implementation (LN) multiplies/input sample Polyphase implementation ( LN R ) multiplies/input sample Polyphase, N = R, FFT ( L N + log2 N) multiplies/input sample As a conclusion to our discussion on the polyphase implementation of the MFB with FFT, here are two special cases of the system we have derived: Special Case 1: L = N = R L length of the window, length of the prototype filter N desired number of modulated filters, sampling rate of the TDFT in the frequency domain R amount of shift by the window at each time step, down sampling rate of the TDFT in the time domain Assume the prototype filter has the following impulse response: Its polyphase decomposition is h00[n] = h0[0]δ[n], . . . , h0p[n] = h0[−p]δ[n] . 5
The polyphase FFT implementation is then Polyphase implementation of the MFB with FFT,L=N=R Special Case 2:L=2N=2R Here the polyphase components are 2-points long.Since L =2R,time aliasing occurs when the N-point DFT is performed through FFT. hin-p hop(n]ho[-pl6(n]ho[-p-N]6[n +1] cn] IN ho[0]6[n]ho[-N]6[n+1] voln] IN ho[-16nl+ho-N-1]6n+1] viin] 2 N-point DFT ho[-216(n]ho[-N-216[n+1] +2[nl ↓N hol-N+1]8[n+ho[-2N+1]6n+1] →UN-[n windowing and time-aliasing Polyphase implementation of the MFB with FFT,L=2N =2R 6
FFT implementation is then Polyphase implementation of the MFB with FFT, L = N = R Case 2: L = 2N = 2R polyphase components are 2-points long. Since L = 2R, time aliasing occurs when the N-point DFT is performed through FFT. The polyphase Special Here the Polyphase implementation of the MFB with FFT, L = 2N = 2R 6