Digital Signal ProcessingLecture 14Lattice StructuresTesheng Hsiao,Associate ProfessorThe lattice structure is a modular structure consisting of cascaded stages.Digital filters implemented by the lattice structure can be transformed into direct from and vice versa.In this lecture,we are going to investigate the implementation of the lattice form and the conversion between it and the direct form.1Recursive Lattice StructureFig.(1)is a single lattice stage.It is a two-input,two-output system consisting of two multipliers,two adders,and one delayelement.Figure 1:A single lattice stageThe constant κn is referred to as reflection coefficient .The input and output relation can be expressed in the z-domainU n (z )=U n +1(z )−κn z −1V n (z )(1)V n +1(z )=κn U n (z )+z −1V n (z )(2)Rearrange the equation and we have[U n +1(z )V n +1(z )]=[1κn z −1κn z −1][U n (z )V n (z )](3)The lattice structure of an N th order LTI digital filter is a cascade of N stages in the way shown in Fig.(2).Given the lattice structure of Fig.(2),we are going to answer the following questions:(1)how the input signal x propagates to the output signal y ,(2)what is the system function implemented by the lattice structure,and (3)how a system function can be converted to a lattice structure.Figure2:Recursive lattice structure•Lattice FilteringThe output of the lattice structure can be calculated in a recursive way.Assume that the system is at initial rest;hence v n[−1]=0,n=0,1,···,N−1.From Fig.(2),for each time step k≥0,we haveinitial conditions:v n[−1]=0,n=0,1,···,N−1for k=0,1,2,···u N[k]=x[k]for n=N−1to0u n[k]=u n+1[k]−κn v n[k−1]v n+1[k]=κn u n[k]+v n[k−1]endv0[k]=u0[k]y[k]=N∑n=0λn v n[k]end•The system function of the lattice structureLetP n(z)=U n(z)U0(z),Q n(z)=V n(z)V0(z),n=0,1,2,···,NHence,Eq.(3)can be rewritten as[P n+1(z) Q n+1(z)]=[1κn z−1κn z−1][P n(z)Q n(z)],n=0,1,2,···,N−1(4) =[1κnκn1][P n(z)z−1Q n(z)],n=0,1,2,···,N−1(5)Note thatU0(z)=V0(z),P0(z)=Q0(z)=1,X(z)U0(z)=P N(z),Y(z)U0(z)=N∑n=0λn Q n(z)Therefore the system function H (z )isH (z )=Y (z )X (z )=∑N n =0λn Q n (z )P N (z )(6)If we expand Eq.(4),we obtain [P n (z )Q n (z )]=[1κn −1z −1κn −1z −1]···[1κ0z −1κ0z −1][11],n =0,1,···,N (7)It is clear from Eq.(7)that P n (z )and Q n (z )are polynomials of z −1of order n .From Eq.(6),P N (z )is the denominator of H (z )while ∑N n =0λn Q n (z )is the numerator ofH (z ).Note that the number of parameters in the lattice structure (κn ,n =0,···N −1and λn ,n =0,···,N )is the same as the number of coefficients of an N th order rational function.In summary,the system function H (z )can be determined by applying Eq.(4)recur-sively to find P n (z )and Q n (z ),n =1,2,···,N ,given Q 0(z )=P 0(z )=1.Then use Eq.(6)to determine H (z ).•Convert the direct form to the lattice structureLet P n (z )=p n 0+p n 1z −1+···+p n n z−n and Q n (z )=q n 0+q n 1z −1+···+q n n z −n ;From Eq.(7),we have [P 1(z )Q 1(z )]=[1κ0z −1κ0z −1][11]=[1+κ0z −1κ0+z −1][P 2(z )Q 2(z )]=[1κ1z −1κ1z −1][1+κ0z −1κ0+z −1]=[1+(κ0+κ0κ1)z −1+κ1z −2κ1+(κ1κ0+κ0)z −1+z −2]...=...Hence we conclude by induction that p n n =κn −1and q n n =1for n =0,1,2,···,N .Moreover we have the following lemma.Lemma 1Q n (z )=z −n P n (z −1),n =0,1,···,NProof:This lemma can be proved by induction.The n =0case is trivialFor n =1,P 1(z )=1+κ0z −1and Q 1(z )=κ0+z −1.Thus the equality holds.Suppose that the equality holds for n =k ,i.e.Q k (z )=z −k P k (z −1).Equivalently,z −k Q k (z −1)=P k (z )For n =k +1,from Eq.(4)we haveP k +1(z )=P k (z )+κk z −1Q k (z )Q k +1(z )=κk P k (z )+z −1Q k (z )Thereforez −(k +1)P k +1(z −1)=z −k −1P k (z −1)+κk z −k Q k (z −1)=z −1Q k (z )+κk P k (z )=Q k +1(z )Thus,by mathematical induction Q n (z )=z −n P n (z −1)for n =0,1,···,NQ.E.D.Assume that κn =1for all n .If we inverse Eq.(5),we have[P n (z )z −1Q n (z )]=11−κ2n[1−κn −κn 1][P n +1(z )Q n +1(z )],n =0,1,···,N −1Hence,P n(z )=P n +1(z )−κn Q n +1(z )1−κ2n ,n =N −1,N −2,···,0(8)Let H (z )=B (z )A (z )=∑N n =0b n z −n 1−∑N n =1a n z −n ,where A (z )andB (z )are polynomials of z −1.Since p n n =κn −1for all n ,thereflection coefficients κn ’s can be determined recur-sively by first setting P N (z )=A (z )and Q N (z )=z −N P N (z −1).Then κN −1=p N N is determined.Applying Eq.(8)and Lemma 1recursively to find P n (z ),κn ’s can be determined successively.To determine λn ,we observe that the coefficient of z −N in the numerator must beλN since B (z )=∑Nn =0λn Q n (z )and q N N =1.Therefore λN =b N .We can removeλN Q N (z )from B (z ),resulting in a (N −1)th order polynomial,and determine λN −1by taking advantage of the property q n n =1for all n .The whole process continuous until all λn ’s are determined.In summaryP N =A (z ),S N =B (z ),λN =b Nfor n =N −1to 0κn =p n +1n +1Q n +1(z )=z −(n +1)P n +1(z −1)P n (z )=P n +1(z )−κn Q n +1(z )1−κ2nS n (z )=S n +1(z )−λn +1Q n +1(z )λn =s n nend•Stability of the Lattice Structure Form Eq.(4),we haveP 1(z )=1+κ0z −111is stable if and only if |κ0|<1.Since the lattice structure is a cascade of N similar stages,the stability of the filter can be verified easily as follows.Lemma 2The lattice structure in Fig.(2)is stable if and only if |κn |<1for all n .2All-pole SystemsAn all-pole system has no nonzero zeros,i.e.the system function is H (z )=1A (z ).In thelattice structure in Fig.(2),if λ0=1and λn =0for n >0,thenH (z )=∑N n =0λn Q n (z )P N (z )=1P N (z )Hence the all-pole system has a simpler lattice structure shown in Fig.(3).Figure 3:The lattice Structure for an all-pole systemOne interesting feature of the lattice structure in Fig.(3)is that the system function from x to v N is an all-pass system.This can be seen as follows.H all (z )=V N (z )X (z )=Q N (z )P N (z )=z −N P N (z −1)P N (z )If z 0is a pole of H all (z ),then 1/z 0must be a zero of H all (z )and vice versa.Due to the symmetry of poles and zeros,H all (z )is indeed an all-pass system.3Nonrecursive lattice structureIf H (z )=B (z ),i.e an FIR filter,the lattice structure becomes nonrecursive.We will explore its properties in this section.We would like to maintain the symmetric structure in Fig.(2)or Fig.(3)because previous results (e.q.Lemma 1)can be applied directly by doing so.In other words,Eq.(1)and Eq.(2)must hold for each stage.If H (z )is FIR,then G (z )=H −1(z )is an all-pole system.If we implement the all-pole system G (z )in the lattice form of Fig.(3),we haveG (z )=1H (z )=1P N (z )=U 0(z )U N (z )By exchanging its input and output,we get the desired FIR system.Note that in this FIR lattice structure,signals flow from u 0to u N .Hence Eq.(3)should be used to compute the signal propagation from stage to stage.The corresponding lattice structure is shown in Fig.(4).Notice that the structure is nonrecursive.The system function implemented by the nonrecursive lattice structure can be constructed in the same way as the recursive lattice structure:P 0(z )=Q 0(z )=1for n =1to N [P n (z )Q n (z )]=[1κn −1z −1κn −1z −1][P n −1(z )Q n −1(z )]endH(z)=P N(z)Figure4:Nonrecursive Lattice StructureTo convert from a system function to the nonrecursive lattice structure,the algorithm is similar to that of the recursive version:P N=B(z)=1+b1z−1+···+b N z−Nfor n=N to1κn−1=p nnQ n(z)=z−n P n(z−1)P n−1(z)=P n(z)−κn−1Q n(z)1−κ2n−1endNote that from Lemma1,p n0=q nn=1for all n.Therefore the coefficient of the constantterm in H(z),i.e.b0,must be1.If b0=1,an intuitive approach is to divide B(z)by b0. However,if b N=b0,as in the case of the linear phasefilter,this will result inκN−1=1, and again we will run into trouble in computing the reflection coefficients.A preferable way is to implement the FIR system H′(z)=1+(B(z)−b0)in a lattice structure and subtract 1−b0from its output.The idea is shown in Fig.(5)Figure5:Nonrecursive lattice structure for b0=1If we apply Lemma2to the nonrecursive lattice structure,we observe that B(z)is a minimum phase system if and only if|κn|<1for all n.If B(z)=P N(z)is a minimum phase system,then the system function from x=u0to v N,i.e.Q N(z),becomes a maximum phase system according to Lemma1,i.e.all its zeros are outside the unit circle.Afinal remark of this lecture:According to Lemma2,each stage of the stable(or minimum phase)lattice structure is an attenuator,i.e.it does not amplify the signals.Thisproperty gives the lattice structure great computational stability and this is the primary reason that the lattice structure is implemented.However,the price for this property is the complex computation of the signalflow.。
