Polyphase Structure of FilterEfficient FIR Filtering for DecimationEfficient FIR Filtering for Interpolation1/39Polyphase Structure of FilterNote: “Polyphase Filters” is often incorrectly taken to mean some special kindof filter…instead, it is merely a special structurethat is handy when using filters in multirate settings2/39Polyphase FiltersPolyphase is a way of doing sampling-rate conversion that leads to very efficient implementations.But more than that, it leads to very general viewpoints that areuseful in building filter banks.Before we delve into the math we can see a lot just by looking at the structure of the filtering….……… Of course, we WILL need to do the math, too, though.3/39Efficient FIR Filtering for Decimation∑−=iinhixnx ][][][ˆ :Filteringi = 0x[i]1234567891011h[4 – i]]4[ˆx∑−==↓iMinMhixnMxnx][][][ˆ][ˆ :Decimation)(M = 3h[5 – i]]5[ˆxh[6 – i]]6[ˆxh[7 – i]]7[ˆxh[8 – i]]8[ˆx]3[ˆxh[3 – i]]1[ˆ)3(↓x]2[ˆ)3(↓xDon’t ComputeDon’t Compute4/39Efficient FIR Filtering for DecimationM = 3x[i]h[9 – i]h[6 – i]i = 0 1234567891011x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] x[8] x[9] x[10] x[11]h[12 – i]]2[ˆ)3(↓x]3[ˆ)3(↓xOriginal Filter……gets split into M=3 subfilters:… x[3] x[6] x[9] x[12] …… x[1] x[4] x[7] x[10] …… x[2] x[5] x[8] x[11] …Σ…Polyphase Form of FIR DecimationAdvantage: “Decimate” then Filter]2[ˆ)3(↓x]3[ˆ)3(↓xx[12]12]4[ˆ)3(↓xh[0] h[3]h[0] h[1] h[2] h[3] h[4] h[5]h[1] h[4]h[2] h[6]…5/39x[0] x[3] x[6] x[9] …0 x[1] x[4] x[7] …0 x[2] x[5] x[8] …ΣPolyphase Form of FIR Decimationh[0] h[3]h[1] h[4]h[2] h[6]h[0] h[1] h[2] h[3] h[4] h[5]↓3x[0] x[1] x[2] ……]0[ˆ)3(↓x]1[ˆ)3(↓x0 0 x[0] x[1] x[2] …Direct Form of FIR DecimationOutputsare the SameInefficientEfficient…]0[ˆ)3(↓x]1[ˆ)3(↓x6/39Consider Length-10 Filter w/ M=4i:0123456789101112h[i]: h[0] h[1] h[2] h[3] h[4] h[5] h[6] h[7] h[8] h[9] 0 0 0 ….Length of Polyphase Filters: ceil{length/M} = ceil{10/4} = 3i′: 0 1 2p0[i′]: h[0] h[4] h[8]p1[i′]: h[1] h[5] h[9]p2[i′]: h[2] h[6] 0p3[i′]: h[3] h[7] 0x0[n]: x[0] x[4] x[8] x[12] x[16] ….x1[n]: x[-1] x[3] x[7] x[11] x[15] ….x2[n]: x[-2] x[2] x[6] x[10] x[14] ….x3[n]: x[-3] x[1] x[5] x[9] x[13] ….Example of Polyphase Filters for Decimation7/39Matlab Code% Create input signal and filterx=1:21;h=[1 2 3 4 5 6 7 8 9 10 0 0];% %%%%%% Direct Form (Inefficient) %%%%%%y=filter(h,1,x); % Compute filter outputy_dec=y(1:4:end) % Throw away unneeded output samples% %%%%%% Polyphase Form (Efficient) %%%%%%% Select polyphase filters p0=h(1:4:end) p1=h(2:4:end)p2=h(3:4:end)p3=h(4:4:end)% Select polyphase signalsx0=x(1:4:end)x1=[0 x(4:4:end)]x2=[0 x(3:4:end)]x3=[0 x(2:4:end)]% filter each polyphase component and add togethery_poly_dec=filter(p0,1,x0)+filter(p1,1,x1)+filter(p2,1,x2)+filter(p3,1,x3)Example of Polyphase Filters for Decimation (pt. 2)Pad zeros to make length equal to integer multiple of MPut a zero in front to provide the x[-3], x[-2], and x[-1] terms8/39Efficient FIR Filtering for Interpolationi = 01234567891011∑−=↑↑iLLinhixnx ][][][ˆ :ionInterpolat)()(x(↑3)[i]h[6 – i]h[7 – i]h[8 – i]h[9 – i]h[10 – i]L = 3x[0] x[1] x[2] x[3]00 00 00 00]6[ˆ)3(↑x]7[ˆ)3(↑x]8[ˆ)3(↑x]9[ˆ)3(↑x]10[ˆ)3(↑xh[10 – i]]11[ˆ)3(↑x9/39∑−=↑iLLinhixnx ][][][ˆ :ionInterpolat)(Efficient FIR Filtering for Interpolationi = 0 1 2 3x[i]L = 3x[0] x[1] x[2] x[3]]6[ˆ)3(↑x]7[ˆ)3(↑x]8[ˆ)3(↑x]9[ˆ)3(↑x]10[ˆ)3(↑x]11[ˆ)3(↑x10/39Efficient FIR Filtering for InterpolationL = 3Original Filter…… gets split into L = 3 subfilters:The output comes fromalternating between thesubfilter outputsThe input goesinto each subfilterPolyphase Form of FIR InterpolationAdvantageFilter thenInterpolateh[0] h[1] h[2] h[3] h[4] h[5]h[0] h[3]h[1] h[4]h[2] h[5]]6[ˆ)3(↑x]7[ˆ)3(↑x]8[ˆ)3(↑x]9[ˆ)3(↑x]10[ˆ)3(↑x]11[ˆ)3(↑x………………x[0] x[1] x[2] x[3] …11/39Multirate Identities – “The Noble Identities”These provide analysis “tricks” useful when dealing with mathematical analysis of multirate systems.The question in general is: How can we interchange the order of filtering w/ decimation/expansion?Decimation IdentityThis identity asserts equality between the following 2 systems:Can prove this either in the Time-Domain or Z-Domain↓MHz(z)x[n] y[n]Hz(zM)↓Mx[n] y[n]=12/39TD Proof of Decimation Identity∑∑−=−==kkMknxkhknwkhnhnwny])[(][][][][*][][↓MHz(z)x[n] y[n]w[n] = x[nM]For the first system:For the second system:Gz(z) = Hz(zM)↓Mx[n] y[n]v[n]⎩⎨⎧===↑otherwise0,integer/if],/[][][)(MnMnhnhngMBy Eq. (12.15)()13/39TD Proof of Decimation Identity (cont.)Then…∑−==kMknxkhnMvny])[(][][][Same as for System #1 Î Proved!!!Thus…∑∑−=−==klkMnxkhlnxlgngnxnv][][][][][*][][Use ()14/39ZD Proof of Decimation IdentityFor the second system:Gz(z) = Hz(zM)↓MXz(z)Vz(z)Yz(z))()()(MzzzzHzXzV =()where…Now…zWzWzjemMMMmMM===−−1/12)(πBut…∑∑−=−−−=−↓===10/1/110/1)())(()(1)(1)}({)(MmMmMMzmMMzMmmMMzMzzWzHWzXMWzVMzVzYUse ()By ZT Result for Decimation15/39ZD Proof of Decimation Identity (cont.){})(10/110/1)()()(1)()()(1)(MzzMmmMMzzMmzmMMzzzXzHWzXMzHzHWzXMzY↓−=−−=−=⎥⎥⎦⎤⎢⎢⎣⎡==∑∑Which is clearly the same thing that the first system gives:↓MHz(z)Xz(z){Xz(z)}(↓M)Yz(z)=Hz(z){Xz(z)}(↓M)16/39Expansion IdentityThis identity asserts equality between the following 2 systems:↑LHz(zL)x[n] y[n]Hz(z)↑Lx[n] y[n]Will give only Z-Domain proof here.=w[n]v[n]17/39ZD Proof of Expansion IdentityHz(z)↑Lx[n] y[n]w[n]First system gives:)()()( zHzXzWzzz=)()()()()()(LzLzLzzLzzHzXzWzWzY===↑Then…v[n]Second system gives:↑LHz(zL)x[n] y[n])()()()(LzzLzzXzXzV ==↑)()()()()(LzLzLzzzzHzXzHzVzY==Then…Same!18/39Polyphase Representation of DecimationNow we re-visit this topic and do it mathematically…Basic Math Idea: Re-write convolution sum’s index & manipulate to get “parallel” filters:Recall Decimation:Hz(z)↓Mx[n] y[n]Output given by (12.17) as…∑−=iinMxihny ][][][()Counts Blocks Counts Samples Inside a BlockWrite sum’s index in “block form” – a common “trick”:⎩⎨⎧−≤≤=′+′=1m0integerMimMiiM = Block Size19/39Polyphase Rep of Dec (cont.)Block-Based Indexing:######""""######"13221222122111210012111210−++−++−−−+−−−−′MMMMMMMMMMMMimEach row is indexed