Kỹ thuật viễn thông - Chapter 11: Scaling and round - Off noise

Chapter 11: Scaling and Round-off Noise Keshab K. Parhi Chapter 11 2 Outline • Introduction • Scaling and Round-off Noise • State Variable Description of Digital Filters • Scaling and Round-off Noise Computation • Round-off Noise Computation Using State Variable Description • Slow-Down, Retiming, and Pipelining Chapter 11 3 Introduction • In a fixed-point digital filter implementation, the overall input-output behavior is non-ideal. The quantization of signals and coefficients using finite word-lengths and propagation of roundoff noises to the output are the sources of noise. • Other undesirable behavior include limit-cycle oscillations where undesirable periodic components are present at filter output even in the absence of any input. These may be caused due to internal rounding or overflow. • Scaling is often used to constrain the dynamic range of the variables to a certain word-length • State variable description of a linear filter: provides a mathematical formulation for studying various structures. These are most useful to compute quantities that depend on the internal structure of the filter. Power at each internal node and the output round-off noise of a digital FIR/IIR filter can be easily computed once the digital filter is described in state variable form Chapter 11 4 Scaling and Round-off Noise • Scaling: A process of readjusting certain internal gain parameters in order to constrain internal signals to a range appropriate to the hardware with the constraint that the transfer function from input to output should not be changed • Illustration: – The filter in Fig.11.1(a) with unscaled node x has the transfer function – To scale the node x, we divide F(z) by some number b and multiply G(z) by the same number as in Fig.11.1(b). Although the transfer function does not change by this operation, the signal level at node x has been changed )()()()( zGzFzDzH += (11.1) Scaling Operation Chapter 11 5 Fig.11.1 (a) A filter with unscaled node x, (b) A filter with scaled node x’ IN OUT F(z) G(z) D(z) (a) IN OUT F(z)/b bG(z) D(z) (b) x x’ Chapter 11 6 – The scaling parameter b can be chosen to meet any specific scaling rule such as • where f(i) is the unit-sample response from input to the node x and the parameter d can be interpreted to represent the number of standard deviations representable in the register at node x if input is unit-variance white noise – If the input is bounded by , then • Equation (11.4) represents the true bound on the range of x and overflow is completely avoided by scaling in (11.2), which is the most stringent scaling policy ïî ï í ì =- =- å å ¥ = ¥ = 0 2 2 01 ,)(: ,)(: i i ifscalingl ifscalingl db b (11.2) 1)( £nu åå ¥= ¥ = £-= 00 )()()()( ii ifinuifnx (11.4) (11.3) 1l Chapter 11 7 – Input can be generally assumed to be white noise.For unit-variance white noise input, variance at node x is given by: • -scaling is commonly used because most input signals can be assumed to be white noise • (11.5) is a variance (not a strict bound). So, we can increase d in (11.3) to prevent possible overflow. But increasing d will decrease SNR (signal-to-noise ratio). Thus, there is a trade-off between overflow and round-off noise [ ] å¥== 0 22 )()( i ifnxE (11.5) 2l Chapter 11 8 Scaling and Round-off Noise(cont’d) Round-off Noise • Round-off Noise: Product of two W-bit fixed-point fractions is a (2W-1) bit number. This product must eventually be quantized to W-bits by rounding or truncation, which results in round-off noise. • Example: – Consider the 1st-order IIR filter shown in Fig. 11.2. Assume that the input wordlength W=8 bits, and the multiplier coefficient wordlength is also 8 bits. To maintain full precision in the output, we need to increase the output wordlength by 8 bits per iteration. This is clearly infeasible. Thus, the result needs to be rounded or truncated to its nearest 8-bit representation. This introduces a round-off noise e(n) (see Fig. 11.3). Chapter 11 9 a Fig.11.2 A 1ST-order IIR filter (W=8) Fig.11.3 Model of Round-off Error D a 8-bits15-bits 8-bits u(n) x(n) Du(n) x(n) e(n): round-off error Chapter 11 10 • Round-off Noise Mathematical Model: usually modeled as an infinite precision system with an external error input (see Fig.11.3) • Rounding is a nonlinear operation, but its effect at the output can be analyzed using linear system theory with the following assumptions about e(n) – 1.e(n) is uniformly distributed white noise – 2. e(n) is a wide-sense stationary random process (mean & covariance of e(n) are independent of the time index n) – 3. e(n) is uncorrelated to all other signals such as input and other noise signals • Let the wordlength of the output be W-bits, then the round-off error e(n) can be given by – The error is assumed to be uniformly distributed over the interval in (11.6), the corresponding probability distribution is shown in Fig.11.4, where D is the length of the interval and 2 2 )( 2 2 )1()1( ---- ££- WW ne (11.6) )1(2 --=D W Chapter 11 11 Pe(x) X 2 D- 2 D D 1 Fig.11.4 Error probability distribution • The mean and variance of this error function: – (11.8) can be rewritten as (11.9), where is the variance of the round- off error in a finite precision W-bit wordlength system [ ])(neE )]([ 2 neE [ ] [ ]ïï î ï ï í ì = D = D == = D == - D- D - D- D - ò ò D D D D 3 2 123 1 )()( 0 2 1 )()( 22 2 2 3 22 2 2 2 2 2 2 2 W e e x dxxPxneE x dxxxPneE (11.7) (11.8) 32 22 We -=s 2 es (11.9) Chapter 11 12 – The variance is proportional to , so, increase in wordlength by 1 bit decreases the error by a factor of 4. • Purpose of analyzing round-off noise: determine its effect at the output – If the noise variance at output is not negligible in comparison to the output signal level, the wordlength should be increased or some low-noise structure should be used. – We need to compute the SNR at the output, not just the noise gain to the output – In noise analysis, we use a double-length accumulator model: rounding is performed after two (2W-1)-bit products are added. Notice: multipliers are the sources for round-off noise W22- Chapter 11 13 State Variable Description of Digital Filters • Consider the signal flow graph (SFG) of an N-th order digital filter in Fig.11.5. We can represent it in the following recursive matrix form: – where x is the state vector, u is the input, and y is the output of the filter; x, b and c are N×1 column vectors; is N×N matrix; d, u and y are scalars. • Let be the unit-sample response from the input u(n) to the state and let be the unit-sample response from the state to the output . It is necessary to scale the inputs to multipliers in order to avoid internal overflow ïî ï í ì ×+×= ×+×=+ )()()( ),()()1( nudnxcny nubnxAnx T (11.10) (11.11) A { })(nfi )(nxi { })(ngi )(nxi)(nyi Chapter 11 14 • Signals x(n) are input to the multipliers in Fig11.5. We need to compute f(n) for scaling. Conversely, to find the noise variance at the output, it is necessary to find the unit-sample response from the location of the noise source e(n) to y(n). Thus g(n) represents the unit-sample response of the noise transfer function • From the SFG of Fig.11.15, we can write: A 1-z )(ne )( nu )(ny )(nx Tcb )1( +nx d Fig.11.5 Signal flow graph of IIR filter AzI zb zU zX ×- × = - - 1 1 )( )( (11.12) Chapter 11 15 • Then, we can write the z-transform of f(n), F(z) as, – We can compute f(n) by substituting u(n) by d(n) and using the recursion (11.15) and initial condition f(0)=0: – The unit-sample response g(n) from the state x(n) to the output y(n) can be computed similarly with u(n)=0. The corresponding SFG is shown in Fig.11.6, which represents the following transfer function G(z), .1,)( ,)()()()( 1 1221 ³×=Þ ×××+++== - --- nbAnf zbzAzAIzUzXzF n (11.13) (11.14) )()()1( nbnfAnf d×+×=+ (11.15) 0,)( ,)( 1 ³×=Þ ×- = - nAcng zAI c zG nT T (11.16) (11.17) Chapter 11 16 • State covariance matrix K: – Because X is an N×1 vector, K is an N×N matrix – K is a measure of error power at various states ( the diagonal element is the energy of the error signal at state due to the input white noise) 1-× zA STATE OUT Tc Fig.11.6 Signal flow graph of g(n) OUT Tc 1 1 -×- zAI ( ) ( ){ }nxnxEK T׺ (11.18) iiK ix STATE Chapter 11 17 • Express K in a form that reflects the error properties of the filter: – State vector X(n) can be obtained by the convolution of u(n) and f(n), by using (11.14) for f(n), we get: – Therefore – Assume u(n) is zero-mean unit-variance white noise, so we have: ( ) å ¥ = --×=*= ×××= 0 21 )1()()( )](,),(),([ l l T N lnubAnunf nxnxnxnx (11.19) (11.20) [ ]å å å å åå ¥ = ¥ = ¥ = ¥ = ¥ = ¥ = ----= þ ý ü î í ì ----= þ ý ü î í ì ----= 0 0 0 0 00 )()1()1( ))(1()1( ))(1()1()( l m Tml l m Tml m Tm l l bAmnulnuEbA bAmnulnubAE bAmnulnubAEK (11.21) î í ì ¹=- = 0,0)]()([ 1)]([ 2 kknunuE nuE (11.22) (11.23) Chapter 11 18 – Substituting (11.22) & (11.23) into (11.21), we obtain: – Finally, we get the Lyapunov equation: • If for some state , has a higher value than other states, then needs to be assigned more bits, which leads to extra hardware and irregular design. – By scaling, we can ensure that all nodes have equal power, and the same word-length can be assigned to all nodes. [ ] T K TKKT K TTKKT K TKKT l TllT l Tll l T l m Tm lm l AbAbAAbbAbAbAAbb bAbAbbbAbAbb bAbAlflfbAbAK ú û ù ê ë é ×+=×+= ×+=×+= ×==××= åå åå åååå ¥ = ¥ = ¥ = ++ ¥ = ¥ = ¥ = ¥ = ¥ = 00 0 11 1 000 0 )()( )()( )()()()(d (11.24) TT AKAbbK ××+×=Þ (11.25) ix ][ 2ixE ix Chapter 11 19 • Orthogonal filter structure: All internal variables are uncorrelated and have unit variance assuming a white-noise input, it satisfies the following: • The advantages of orthogonal filter structure: – The scaling rule is automatically satisfied – The round-off noise gain is low and invariant under frequency transformations – Overflow oscillations are impossible • Similarly, define the output covariance matrix W as follows: • Proceeding in a similar manner as before, we can get TT bbAAIK ×+×== (11.26) åå ¥ = ¥ = == 00 )()()( n nTTnT n T AcAcngngW (11.27) TT ccAWAW ×+××= (11.28) Chapter 11 20 Scaling and Round-off Noise Computation • The same word-length can be assigned to all the variables of the system only if all the states have equal power. This is achieved by scaling • The state vector is pre-multiplied by inverse of the scaling matrix T. – If we denote the scaled states by , we can write, – Substituting for x from (11.29) into (11.10) and solving for , we get Scaling Operation Sx )()()()( 1 nxTnxnxTnx SS ×=Þ×= - (11.29) Sx )()()1( )()()1( )()()1( 11 nubnxAnx nubTnxTATnx nubnxTAnxT SSSS SS SS ×+×=+Þ ××+×××=+Þ ×+××=+× -- (11.30) (11.31) (11.32) Chapter 11 21 – where • Similarly, the output equation (11.11) can be derived as follows • The scaled K matrix is given by • It is desirable to have equal power at all states, so the transformation matrix T is chosen such that the Ks matrix of the scaled system has all diagonal entries as 1. ( )bTbTATA SS ×=××= -- 11 , { }ddTcc nudnxc nudnxTcny S TT S SS T S S T =×=Þ ×+×= ×+××= , )()( )()()( (11.33) ( ) T S TTTTT SSS TKTK TxxETTxxTExxEK )( )(])([][ 11 1111 -- ---- ××=Þ ×=×=×= (11.34) Chapter 11 22 • Further assume T to be diagonal, i.e., – From (11.34) and (11.35) and let , we can obtain: • Conclusion: By choosing i-th diagonal entry in T to be equal to the square root of the i-th diagonal element of K matrix, all the states can be guaranteed to have equal unity power • Example (Example 11.4.1,pp.387) Consider the unscaled 2nd-order filter shown in Fig.11.7, its state variable matrices are (see the next page): T NN NN T ttt diagT tttdiagT )(] 1 , 1 , 1 [ ],,,[ 1 2211 1 2211 -- =××××××=Þ ××××××= (11.35) (11.36) 1)( =iiSK iiii ii ii iiS Kt t K K =Þ == ,1)( 2 (11.37) (11.38) Chapter 11 23 – Example (cont’d) – The state covariance matrix K can be computed using (11.25) as 21- )(nu )(ny 1 161 )(2 nx 1-z 1-z )(1 nx 161 Fig.11.7 An SFG of an unscaled 2nd-order filter 0,, 1 0 , 0 10 2 1 16 1 16 1 =ú û ù ê ë é - =ú û ù ê ë é =ú û ù ê ë é = dcbA ú û ù ê ë é + = ú û ù ê ë é +ú û ù ê ë é ×ú û ù ê ë é ×ú û ù ê ë é =ú û ù ê ë é 1 10 00 01 0 0 10 11256 1 1216 1 2116 1 22 16 1 2221 1211 16 1 2221 1211 KK KK KK KK KK KK Chapter 11 24 – Thus, we get: – For scaling with d=1, the transformation matrix is – Thus the scaled filter is described as below and is shown in Fig.11.8 – Note: the state covariance matrix Ks of the scaled filter is { }0, 21122552562211 ==== KKKK 2l ú ú û ù ê ê ë é = 255 16 255 16 0 0 T 0, , 0 , 0 10 255 8 255 1 16 255 1 16 1 1 = ú ú û ù ê ê ë é - =×= ú û ù ê ë é =×=ú û ù ê ë é =××= -- S T S SS dcTc bTbTATA ú û ù ê ë é = ú ú û ù ê ê ë é ú û ù ê ë é ú ú û ù ê ê ë é = 10 01 0 0 0 0 0 0 16 255 16 255 255 256 255 256 16 255 16 255 S K Chapter 11 25 1-z )(nu )(ny 1-z0.998 -0.501 -0.0626 1/16 )(2 nx )(1 nx Fig.11.8 A SFG of a scaled 2nd-order filter Chapter 11 26 • Computation: Let be the error due to round-off at state . Then the output round-off noise , due to this error, can be written as the convolution of the error input with the state-to-output unit-sample response : – Consider the mean and the variance of . Since is white noise with zero mean, so we have: )(nei Round-off Noise Computation Scaling and Round-off Noise Computation (cont’d) ix )(nyi )(nei )(ngi å ¥ = -=*= 0 )()()()()( l iiiii lnglengneny (11.39) )(nyi )(nei [ ] ,0)( =nyE i (11.40) [ ] ú û ù ê ë é --= åå m ii l iii mngmelngleEnyE )()()()()( 2 [ ]åå --= l m iiii mngmeleElng )()()()( [ ] [ ])(iancevar)(22 neneElet iie ==s Chapter 11 27 – (cont’d) – Expand W in its explicit matrix form, we can observe that all its diagonal entries are of the form : [ ] åå åå =-= -×-= n ie l ie l m ilmeii nglng mnglngnyE )()( )()()( 2222 22 ss ds (11.41) ån i ng )(2 ú ú ú ú ú û ù ê ê ê ê ê ë é ××× ×××××××××××× ××× ××× = ååå ååå ååå n Nn Nn N n Nnn n Nnn ngngngngng ngngngngng ngngngngng )()()()()( )()()()()( )()()()()( 2 21 2 2 212 121 2 1 [ ]åå ×××× ú ú ú û ù ê ê ê ë é ×××== n N N n T ngng ng ng ngngW )(,),( )( ),( )()( 1 1 (11.42) (11.43) Chapter 11 28 – Using (11.41), we can write the expression for the total output round-off noise in terms of trace of W: – Note: (11.44) is valid for all cases. But when there is no round-off operation at any node, then the corresponding to that node should not be included while computing noise power – (11.44) can be extended to compute the total round-off noise for the scaled system, which will simply be the trace of the scaled W matrix: – Replacing the filter parameters with the scaled parameters in (11.27), we can show: – Also, for a diagonal T we can write: noiseroundofftotal __ )()( 2 1 2 1 22 WTraceWng e N i iie N i n ie sss === åå å == (11.44) iiW )(2 Se WTraces=total round-off noise (scaled system) (11.45) TWTW T S ××= (11.46) ( ) ( ) ( )åå == ×== N i iiii N i iiSS WtWWTrace 1 2 1 (11.47) Chapter 11 29 – (11.47) can be rewritten as follows because – Conclusion: The round-off noise of the scaled system can be computed using (11.48), i.e., using • Example (Example 11.4.2, p.390) To find the output round-off noise for the scaled filter in Fig.11.8, W can be calculated using (11.28) as iiii Kt º ( ) ( ) Þ×= å = N i iiiiS WKWTrace 1 ( )å = ×= N i iiiie WK 1 2stotal round-off noise (scaled system) (11.48) { }iiii WK , 2l ú û ù ê ë é +- -+ = ú û ù ê ë é +ú û ù ê ë é ×ú û ù ê ë é ×ú û ù ê ë é =ú û ù ê ë é - - 255 64 11255 8 1216 1 255 8 2116 1 255 1 22256 1 255 64 255 8 255 8 255 1 16 1 2221 121116 1 2221 1211 0 10 01 0 WW WW WW WW WW WW Chapter 11 30 – Thus – The total output round-off noise for the scaled filter is – For the unscaled filter in Fig.11.7: – Thus ú û ù ê ë é - - =ú û ù ê ë é 2559.00332.0 0332.00049.0 2221 1211 WW WW ( ) 222211 2608.0 eeWW ss =×+ ú û ù ê ë é +- -+ = ú û ù ê ë é +ú û ù ê ë é ×ú û ù ê ë é ×ú û ù ê ë é =ú û ù ê ë é - - 4 1 1132 1 1216 1 32 1 2116 1 256 1 22256 1 4 1 32 1 32 1 256 1 16 1 2221 121116 1 2221 1211 0 10 01 0 WW WW WW WW WW WW ú û ù ê ë é - - =ú û ù ê ë é 2549.00333.0 0333.00049.0 2221 1211 WW WW Chapter 11 31 – The total output round-off noise for the unscaled filter is – Notice: The scaled filter suffers from larger round-off noise, which can also be observed by comparing the unscaled and scaled filter structure: • In the scaled filter, the input is scaled down by multiplying 0.998 to the input to avoid overflow (See Fig.11.8). Therefore, to keep the transfer functions the same in both filters, the output path of the scaled filter should have a gain which is 1/0.998 times the gain of the output path of the unscaled filter. Thus the round-off noise of the scaled filter is times that of the unscaled filter • The above observation represents the tradeoff between overflow and round-off noise: More stringent scaling reduces the possibility of overflow but increases the effect of round-off noise – Notice: (11.48) can be confirmed by: ( ) 222211 2598.0 eeWW ss =×+ 1 2608.0 2598.0 )(_ )(_ <= scalednoiseroundoff unscalednoiseroundoff 2998.01 ( ) ( )scaledunscaled WWWKWK 221122221111 2608.0)2549.00049.0(255 256 +==+=+ Chapter 11 32 Round-off Noise Computation Using State Variable Description Algorithms for Computing K and W • Parseval’s relation and Cauchy’s residue theorem are useful for finding signal power or round-off noise of digital filters. But, they are not useful for complex structures. • The power at each internal node and the output round-off noise of a complex digital filter can be easily computed once the digital filter is described in state variable form • Algorithm for computing K – Using (11.24), K can be computed efficiently by the following algorithm: (see it on next page) Chapter 11 33 • Algorithm for computing K (cont’d) – 1. Initialize: – 2. Loop: – 3. Computation continues until • Algorithm analysis: – After the 1st-loop iteration: – After the 2nd-loop iteration: TbbKAF ׬¬ , 2, FFFAFK T ¬×׬ 0=F ïî ï í ì = +××= 2 )( AF bbAbbAK TTT (11.49) ïî ï í ì = +++= 4 2233 ,)()( AF bbAbbAAbbAAbbAK TTTTTTT (11.50) Chapter 11 34 – Thus, each iteration doubles the number of terms in the sum of (11.24). The above algorithm converges as long as the filter is stable (because the eigen-values of the matrix A are the poles of the transfer function) – This algorithm can be used to compute W after some changes • Algorithm for Computing W – 1. Initialize: – 2. Loop: – 3. Computation continues until • Example (Example 11.6.1, p.404) Consider the scaled-normalized lattice filter in Fig.11.9. We need to compute the signal powers at node 1, 2 and 3: – Because there are 3 states (1—3), the dimensions of the matrix A, b, c and d are 3´3, 3´1, 3´1, and 1´1, respectively. From Fig.11.9, the state equations can be written as (see next page) TT ccWAF ׬¬ , 2, FFFWFW T ¬×׬ 0=F Chapter 11 35 ï ï î ï ï í ì +++= +=+ -+=+ ++-=+ )(0029.0)(3054.0)(1035.0)(0184.0)( )(9743.0)(2252.0)1( )(2093.0)(9054.0)(3695.0)1( ),(8467.0)(0443.0)(1915.0)(4944.0)1( 321 313 3212 3211 nunxnxnxny nxnxnx nxnxnxnx nunxnxnxnx Chapter 11 36 Fig.11.9 A 3rd-order scaled-normalized lattice filter (also see Fig.11.18, p.403, Textbook) )(nu 0029.0 0569.0 z-1 z-1z-1 )(ny 3209.0 532.0 9293.0 9293.0- 3695.0 3695.0 9743.0- 9743.0 2252.0 2252.0 323.0 9984.0 9471.0 1# 2# 3# 8467.0 Chapter 11 37 – From these equations, matrices A, b, c and d can be obtained directly. By substituting them into the K-computing algorithm, we get – Since , so no scaling is needed for nodes 1—3. In addition, the K matrix shows that the signals at nodes 1—3 are orthogonal to each other since all off-diagonal elements are zeros – By the W-computing algorithm, we obtain: • Conclusion: – Using state variable description method, we can compute signal power or round-off noise of a digital filter easily and directly. However, it can not be used on the nodes that are not connected to unit-delay branches because these nodes do not appear in the state variable description ú ú ú û ù ê ê ê ë é = 100 010 001 K }1{ 332211 === KKK }3096.0,2952.0,1455.0{ 332211 === WWW Chapter 11 38 Slow-Down, Retiming, and Pipelining Introduction • Many useful realizations contains roundoff nodes that are not connected to unit-delay branches. Thus these nodes (variables) do not appear in a state variable description and the scaling and roundoff noise computation methods can not be applied directly. • The SRP ( slow-down and retiming/pipelining) transformation technique can be used as a preprocessing step to overcome this difficulty – Slow-down: every delay element (Z) in the original filter is changed into M delay element (ZM) – Retiming and Pipelining (Please see Chapters 4 and 3 for details) Chapter 11 39 • Slow-down: Consider the filter in Fig.11.10(b) which is obtained by applying slow-down transformation (M=3) to the filter in Fig.11.10(a). By 3 slow down transformation, every Z-variable in Fig.11.10(a) is changed into Z3. Thus the transfer function of the transformed filter H’(Z) is related to the original transfer function H(Z) as (11.51): – Thus, if the unit-sample response from the input to the internal node x in Fig.11.10(a) is defined by: – Then, the unit-sample response from the input to the internal node x’ in Fig.11.10(b) is: – We can get: – Similarly it can be shown that: )()()()(')(')(' 333 zHzGzFzGzFzH === (11.51) },),2(),1(),0({)( ×××= fffnf (11.52) },,0,0),2(,0,0),1(,0,0),0({)(' ×××= fffnf (11.53) xx nn xx KnfnfK === åå 22 )()]('[' (11.54) xxxx WW =' (11.55) Chapter 11 40 Figure 11.10 (a) A filter with transfer function H(z)=F(Z)G(Z). (b) Transformed filter obtained by 3 slow-down transformation H’(Z)=F(Z3)G(Z3). F(Z) G(Z)IN OUT x (a) F’(Z)=F(Z3) G’(Z)=G(Z3)IN OUT x’ (b) Chapter 11 41 – The foregoing analysis shows that slow-down transformation does not change the finite word-length behavior • Pipelining: – Consider the filter in Fig.11.11(a), which has a non-state variable node x on the feed-forward path. It is obvious that the non-state variable node cannot be converted into the state variable node by slow-down transformation. – However, since x is on the feed-forward path, a delay can be placed on a proper cut-set location as shown in Fig.11.11(b). This pipelining operation converts the non-state variable node x into state variable node. The output sequence of the pipelined filter is equal to that of the original filter except one clock cycle delay. – So, the pipelined filter undergoes the same possibility of overflow and the same effect of round-off noise as in the original filter. Thus it is clear that pipelining does not change the filter finite word-length behavior Chapter 11 42 Fig.11.11 (a) A filter with a non-state variable node on a feed-forward path (b) Non-state variable node is converted into state variable node by pipelining c DD a b x u(n) y(n) (a) c DD a b u(n) y(n-1) D (b) Chapter 11 43 • Retiming: – In a linear array, if either all the left-directed or all the right-directed edges between modules carry at least 1 delay on each edge, the cut-set localization procedure can be applied to transfer some delays or a fraction of a delay to the opposite directed edges (see Chapter 4) — This is called retiming • SRP transformation technique is summarized as follows: – 1. Apply slow-down transformation by a factor of M to a linear array, i.e., replace Z by ZM. Also, apply pipelining technique to appropriate locations. – 2. Distribute the additional delays to proper locations such that non-state variable nodes are converted to state variable nodes – 3. Apply the scaling and noise computation method using state variable description • Example (Example 11.7.1, p.407) Consider the filter shown in Fig.11.12, same as the 3rd-order scaled-normalized lattice filter in Fig.11.9 except that it has five more delays. The SFG in Fig.11.12 is obtained by using a 2-slow transformation and followed by retiming or cut-set transformation. (cont’d) Chapter 11 44 Fig.11.12 A transformed filter of the 3rd-order scaled-normalized lattice filter in Fig.11.9 (also see Fig.11.21,pp.407) )(nu 0029.0 0569.0 z-1 z-1z-1 )(ny 3209.0 3# 8467.0 532.0 9293.0 9293.0- 3695.0 3695.0 9743.0- 9743.0 2252.0 2252.0 z-1 z-1 z-1 z-1 z-1 323.0 9984.0 9471.0 4#2#1# 5# 6# 7# 8# Chapter 11 45 – (cont’d) Notice that signal power or round-off noise at every internal node in this filter can be computed using state variable description since each node is connected to a unit delay branch. Since there are 8 states, the dimensions of the matrices A, b, c, and d are 8×8, 8×1, 8×1, and 1×1, respectively. From Fig.11.12, state equations can be written as follows: ï ï ï ï ï ï î ï ï ï ï ï ï í ì += +-=+ +=+ +=+ +=+ =+ +=+ -=+ +=+ )(0029.0)(323.0)( ),(2252.0)(9743.0)1( ),(3695.0)(9293.0)1( ),(9471.0)(3209.0)1( ),(9984.0)(0569.0)1( ),()1( ),(9743.0)(2252.0)1( ),(9293.0)(3695.0)1( ),(8467.0)(532.0)1( 5 428 817 426 615 34 423 812 71 nunxny nxnxnx nxnxnx nxnxnx nxnxnx nxnx nxnxnx nxnxnx nunxnx Chapter 11 46 – From the above equations, matrices A, b, c, and d can be obtained directly. Using the K-computing algorithm, we obtain , which means that every internal node is perfectly scaled. Similarly, we get – Thus, the total output round-off noise is: – Note: no round-off operation is associated with node 4 or state . Therefore, is not included in Trace(W) for round-off noise computation • Example (omitted, study at home) – For details, please see Example 11.7.2, p.408 of textbook }8,,2,1,1{ ×××== iKii }1912.0,0412.0 ,104.0,1043.0,3096.0,3096.0,2952.0,1455.0{,, 8811 =××× WW 22 191.1 e i iiiie WK ss == å 4x 44W