2y ago

121 Views

9 Downloads

274.57 KB

32 Pages

Transcription

MULTIRATE SIGNAL PROCESSING1. APPLICATIONS2. THE UP-SAMPLER3. THE DOWN-SAMPLER4. RATE-CHANGING5. INTERPOLATION6. HALF-BAND FILTERS7. NYQUIST FILTERS8. THE NOBLE IDENTITIES9. POLYPHASE DECOMPOSITION10. EFFICIENT IMPLEMENTATION11. POLYNOMIALS AND MULTIRATE FILTERING12. INTERPOLATION OF POLYNOMIALSI. SelesnickEL 713 Lecture Notes1

APPLICATIONS1. Used in A/D and D/A converters.2. Used to change the rate of a signal. When two devices that operate at different rates are to be interconnected, it is necessaryto use a rate changer between them.3. Interpolation.4. Some efficient implementations of single rate filters are basedon multirate methods.5. Filter banks and wavelet transforms depend on multirate methods.I. SelesnickEL 713 Lecture Notes2

THE UP-SAMPLERThe up-sampler, represented by the diagram,x(n)- 2-y(n)is defined by the relation(x(n/2),y(n) 0,for n evenfor n odd.(1)The usual notation isy(n) [ 2] x(n).(2)The up-sampler simply inserts zeros between samples. For example,if x(n) is the sequencex(n) {. . . , 3, 5, 2, 9, 6, . . . }where the underlined number represents x(0), then y(n) is given byy(n) [ 2] x(n) {. . . , 0, 3, 0, 5, 0, 2, 0, 9, 0, 6, 0, . . . }.Given X(z), what is Y (z)? Using the example sequence above wedirectly writeX(z) · · · 3 z 5 2 z 1 9 z 2 6 z 3 · · ·(3)Y (z) · · · 3 z 2 5 2 z 2 9 z 4 6 z 6 · · ·(4)andI. SelesnickEL 713 Lecture Notes3

It is clear thatY (z) Z {[ 2] x(n)} X(z 2 ).(5)We can also derive this using the definition:XY (z) y(n) z n(6)n Xx(n/2) z n(7)n even Xx(n) z 2 n(8)n X(z 2 ).(9)How does up-sampling affect the Fourier transform of a signal?The discrete-time Fourier transform of y(n) is given byY (ejω ) X(z 2 )z ejωjω 2(10) X((e ) )(11)Y (ejω ) X(ej2ω ).(12)so we haveOr using the notation Y f (ω) Y (ejω ), X f (ω) X(ejω ), we haveY f (ω) DTFT {[ 2] x(n)} X f (2ω).(13)When sketching the Fourier transform of an up-sampled signal, it iseasy to make a mistake. When the Fourier transform is as shown inthe following figure, it is easy to incorrectly think that the Fouriertransform of y(n) is given by the second figure. This is not correct,because the Fourier transform is 2π-periodic. Even though it isusually graphed in the range π ω π or 0 ω π, outsideI. SelesnickEL 713 Lecture Notes4

this range it is periodic. Because X f (ω) is a 2π-periodic functionof ω, Y f (ω) is a π-periodic function of ω.The correct graph of Y f (ω) is the third subplot in the figure.Xf(ω)10.5Yf(ω) Xf(2ω)Xf(2ω) WRONG!0 1 0.50ω/π0.51 0.50ω/π0.51 0.50ω/π0.5110.50 110.50 1Note that the spectrum of X f (ω) is repeated — there is an ‘extra’copy of the spectrum. This part of the spectrum is called thespectral image.General case: An L-fold up-sampler, represented by the diagram,x(n)- L-y(n)is defined as(y(n) [ L] x(n) I. Selesnickx(n/L),when n is a multiple of L0,otherwise.EL 713 Lecture Notes5

(14)The L-fold up-sampler simply inserts L 1 zeros between samples.For example, if the sequence x(n)x(n) {. . . , 3, 5, 2, 9, 6, . . . }is up-sampled by a factor L 4, the result is the following sequencey(n) [ 4] x(n) {. . . , 0, 3, 0, 0, 0, 5, 0, 0, 0, 2, 0, 0, 0, 9, 0, 0, 0, 6, 0, . . . }.Similarly, we haveY (z) Z {[ L] x(n)} X(z L ),(15)Y (ejω ) X(ejLω ),(16)Y f (ω) DTFT {[ L] x(n)} X f (L ω).(17)The L-fold up-sampler will create L 1 spectral images. For example, when a signal is up-sampled by 4, there are 3 spectral imagesas shown in the following figure.Xf(ω)10.5Yf(ω) Xf(Lω)0 10ω/π0.51 0.50ω/π0.5110.50 1I. Selesnick 0.5EL 713 Lecture Notes6

Remarks1. No information is lost when a signal is up-sampled.2. The up-sampler is a linear but not a time-invariant system.3. The up-sampler introduces spectral images.I. SelesnickEL 713 Lecture Notes7

THE DOWN-SAMPLERThe down-sampler, represented by the following diagram,x(n)- 2-y(n)is defined asy(n) x(2 n).(18)The usual notation isy(n) [ 2] x(n).(19)The down-sampler simply keeps every second sample, and discardsthe others. For example, if x(n) is the sequencex(n) {. . . , 7, 3, 5, 2, 9, 6, 4, . . . }where the underlined number represents x(0), then y(n) is given byy(n) [ 2] x(n) {. . . , 7, 5, 9, 4, . . . }.Given X(z), what is Y (z)? This is not as simple as it is for theup-sampler. Using the example sequence above we directly writeX(z) · · · 7 z 2 3 z 5 2 z 1 9 z 2 6 z 3 4 z 4 · · · (20)andY (z) · · · 7 z 5 9 z 1 4 z 2 · · ·(21)How can we express Y (z) in terms of X(z)? Consider the sum ofX(z) and X( z). Note that X( z) is given byX( z) · · · 7 z 2 3 z 5 2 z 1 9 z 2 6 z 3 4 z 4 · · · . (22)I. SelesnickEL 713 Lecture Notes8

The odd terms are negated. ThenX(z) X( z) 2· · · · 7 z 2 5 9 z 2 4 z 4 · · · (23)orX(z) X( z) 2 · Y (z 2 )(24)or11X(z 2 ) X( z 2 )Y (z) Z {[ 2] x(n)} 2(25)How does down-sampling affect the Fourier transform of a signal?The discrete-time Fourier transform of y(n) is given by11X(z 2 ) X( z 2 )Y (e ) 2jω121 21 21 2 (26)z ejωωω · X(ej 2 ) X( ej 2 )ωω · X(ej 2 ) X(e jπ ej 2 ) j ω2j( ω2 π)· X(e ) X(e) f ωf ω 2π· X ( ) X ()22(27)(28)(29)(30) 1ωω 2πY f (ω) DTFT {[ 2] x(n)} · X f ( ) X f ()222(31)where we have used the notation Y f (ω) Y (ejω ), X f (ω) X(ejω ).Note that because X f (ω) is periodic with a period of 2π, the functions X f ( ω2 ) and X f ( ω 2π2 ) are each periodic with a period of 4π.I. SelesnickEL 713 Lecture Notes9

But as Y f (ω) is the Fourier transform of a signal, it must be 2πperiodic. What does Y f (ω) look like? It is best illustrated with anexample.1.21Xf(ω)0.80.60.40.20 3 2 10ω/π123 2 10ω/π123 2 10ω/π123 2 10ω/π1231.20.5 * Xf(ω/2)10.80.60.40.20 30.5 * Xf((ω 2π)/2)1.210.80.60.40.20 31.21Yf(ω)0.80.60.40.20 3Notice that while the two terms X f ( ω2 ) and X f ( ω 2π2 ) are 4πperiodic, because one is shifted by 2π, their sum is 2π-periodic, asa Fourier transform must be.Notice that when a signal x(n) is down-sampled, the spectrumX f (ω) may overlap with adjacent copies, depending on the specificshape of X f (ω). This overlapping is called aliasing. When aliasingoccurs, the signal x(n) can not in general be recovered after itI. SelesnickEL 713 Lecture Notes10

is down-sampled. In this case, information is lost by the downsampling. If the spectrum X f (ω) were zero for π/2 ω π,then no overlapping would occur, and it would be possible to recoverx(n) after it is down-sampled.General case: An M -fold down-sampler, represented by the diagram,x(n)- M-y(n)is defined asy(n) x(M n).(32)The M -fold down-sampler keeps only every M th sample. For example, if the sequence x(n)x(n) {. . . , 8, 7, 3, 5, 2, 9, 6, 4, 2, 1, . . . }is down-sampled by a factor M 3, the result is the followingsequencey(n) [ 3] x(n) {. . . , 8, 5, 6, 1, . . . }.Similarly, we haveM 111 XY (z) Z {[ M ] x(n)} X(W k z M )M(33)k 0where2πW ej M ,I. Selesnick(34)EL 713 Lecture Notes11

and M 1X1ω 2πkY f (ω) DTFT {[ M ] x(n)} Xf.MM(35)k 0Remarks1. In general, information is lost when a signal is down-sampled.2. The down-sampler is a linear but not a time-invariant system.3. In general, the down-sampler causes aliasing.I. SelesnickEL 713 Lecture Notes12

RATE-CHANGINGThe up-sampler and down-sampler are usually used in combinationwith filters, not by themselves. For example, to change the rate ofa signal, it is necessary to employ low-pass filters in addition to theup-sampler and down-sampler.The following system is used for interpolation.x(n)- L-H(z)-y(n)The combined up-sampling and filtering can be written asXy(n) ([ L] x(n)) h(n) x(k) h(n L k).(36)kThe filter fills in the zeros that are introduced by the up-sampler.Equivalently, it is designed to remove the spectral images. It shouldbe a low-pass filter with a cut-off frequency ωo π/L. In thiscontext, the low-pass filter is often called an interpolation filter.The following system is used for decimation.x(n)-H(z)- M-y(n)The combined filtering and down-sampling can be written asXy(n) [ M ] (x(n) h(n)) x(k) h(M n k).(37)kThe filter is designed to avoid aliasing. It should be a low-pass filterwith a cut-off frequency ωo π/M . In this context, the low-passfilter is often called an anti-aliasing filter.I. SelesnickEL 713 Lecture Notes13

A rate changer for a fractional change (like 2/3) can be obtainedby cascading an interpolation system with a decimation system.Then, instead of implementing two separate filters in cascade, onecan implement a single filter. Structure for rational rate changer:x(n)- L-H(z)- M-y(n)The filter is designed to both eliminate spectral images and to avoidaliasing. The cascade of two ideal low-pass filters is again a lowpass filter with a cut-off frequency that is the minimum of the twocut-off frequencies. So, in this case, the cut-off frequency shouldbenπ π oωo min,.L MI. SelesnickEL 713 Lecture Notes(38)14

INTERPOLATION EXAMPLE 1In this example, we interpolate a signal x(n) by a factor of 4,using the interpolation system described above. We use a linearphase Type I FIR lowpass filter of length 21 to follow the 4-fold upsampler. Note that because the filter is causal, a delay in introducedby the interpolation system. y(n) could be aligned with x(n) byshifting it.5140.6 Hf(ω) h(n)0.80.40.20321 40n506070801.21y(n)0.80.60.40.20I. Selesnick01020304050n6070EL 713 Lecture Notes809010015

INTERPOLATION EXAMPLE 2This time we use a filter of length 7,1h(n) · {1, 2, 3, 4, 3, 2, 1}.(39)4Note that this filter has the effect of implementing linear interpolation between the existing samples x(n). The result is rather poor— the signal y(n) is not very smooth. Similarly, quadratic interpolation can be implemented by using an appropriate filter h(n).5140.6 Hf(ω) h(n)0.80.40.20321 06070801.21y(n)0.80.60.40.2001020304050607080nI. SelesnickEL 713 Lecture Notes16

HALF-BAND FILTERSWhen interpolating a signal x(n), the interpolation filter h(n) willin general change the samples of x(n) in addition to filling in thezeros. It is natural to ask if the interpolation filter can be designedso as to preserve the original samples x(n).To be precise, ify(n) h(n) [ 2] x(n)then can we design h(n) so that y(2n) x(n), or more generally,so that y(2n no ) x(n) ?It turns out that this is possible. When interpolating by a factor of2, if h(n) is a half-band, then it will not change the samples x(n).A no -centered half-band filter h(n) is a filter that satisfies(1,for n noh(n) 0,for n no 2, 4, 6, . . .(40)That means, every second value of h(n) is zero, except for one suchvalue, as shown in the figure.A HALF BAND FILTER1.21h(n)0.80.60.40.20 0.20246810n1214161820In the figure, the center point is no 10. The definition of ahalf-band filter can be written more compactly using the Kroneckerdelta function δ(n). Half-band filter:h(2 n no ) δ(n),I. SelesnickEL 713 Lecture Notes(41)17

when no 0, we get simply:h(2 n) δ(n).(42)Note that the transfer function of a half-band filter (centered atno 0) can be written asH(z) 1 z 1 H1 (z 2 ).(43)Here H1 (z) contains the odd samples of h(n).NYQUIST FILTERSWhen interpolating a signal x(n) by a factor L, the original samplesof x(n) are preserved if the interpolation filter h(n) is a Nyquist-Lfilter. A Nyquist-L filter simply generalizes the notion of the halfband filter to L 2. A (0-centered) Nyquist-L filter h(n) is onefor whichh(L n) δ(n).(44)A Nyquist-4 filter is shown in the following figure.A NYQUIST 4 FILTER1.21h(n)0.80.60.40.20 0.20I. Selesnick51015nEL 713 Lecture Notes20253018

THE NOBLE IDENTITY FOR THE UP-SAMPLERThe two following equivalences are sometimes called the noble identities.Can you reverse the order of an up-sampler and a filter?Yes and no — it depends. There are two cases.1. If the up-sampler comes after the filter, then you can reversethe order of the filter and the up-sampler, but the filter needsto be modified as shown in the figure.2. If the up-sampler comes before the filter, then you can notreverse their order unless the filter is of the special form H(z L ).This can be summarized by the following figure.x(n)-H(z)- L-y(n)mx(n)- L-H(z L )-y(n)Equivalently:[ L] (h(n) x(n)) [ L] h(n) [ L] x(n)I. SelesnickEL 713 Lecture Notes19

THE NOBLE IDENTITY FOR THE UP-SAMPLERThis identity is most easily derived using the Z-transform and equation (15). In the following figure the intermediate signal v(n) isshown.x(n)-v(n)H(z)- L-y(n)Then, using the Z-transform, we haveV (z) H(z) X(z)Y (z) V (z L )andand therefore,Y (z) H(z L ) X(z L ).Now consider the system that we claim to be equivalent. In thefollowing figure the intermediate signal w(n) is shown.x(n)-w(n) L-H(z L )-y(n)Then, using the Z-transform, we haveW (z) X(z L )andY (z) H(z L ) W (z)and therefore,Y (z) H(z L ) X(z L ).This shows that the systems are equivalent.I. SelesnickEL 713 Lecture Notes20

THE NOBLE IDENTITY FOR THE DOWN-SAMPLERCan you reverse the order of an down-sampler and a filter?Yes and no — it depends. There are two cases.1. If the down-sampler comes before the filter, then you can reverse the order of the filter and the down-sampler, but thefilter needs to be modified as shown in the figure.2. If the down-sampler comes after the filter, then you can not reverse their order unless the filter is of the special form H(z M ).This can be summarized by the following figure.x(n)- M-H(z)-y(n)mx(n)-MH(z )- M-y(n)Equivalently:h(n) [ M ] x(n) [ M ] ([ M ] h(n) x(n))I. SelesnickEL 713 Lecture Notes21

THE NOBLE IDENTITY FOR THE DOWN-SAMPLERFor convenience, we prove it just for M 2. This identity is mosteasily derived using the Z-transform and equation (25). In thefollowing figure the intermediate signal v(n) is shown.x(n)- 2v(n)H(z)--y(n)Then, using the Z-transform, we have1111V (z) X(z 2 ) X( z 2 )22andY (z) H(z) V (z)and therefore,1111Y (z) H(z) X(z 2 ) H(z) X( z 2 )22Now consider the system that we claim to be equivalent. In thefollowing figure the intermediate signal w(n) is shown.x(n)-H(z 2 )w(n)- 2-y(n)Then, using the Z-transform, we haveW (z) H(z 2 ) X(z)and1111Y (z) W (z 2 ) W ( z 2 )22and therefore,1111Y (z) H(z) X(z 2 ) H(z) X( z 2 ).22This shows that the systems are equivalent.I. SelesnickEL 713 Lecture Notes22

POLYPHASE DECOMPOSITIONThe polyphase decomposition of a signal is simply the even and oddsamples,x0 (n) x(2 n)(45)x1 (n) x(2 n 1).(46)Then the Z-transform X(z) is given byX(z) X0 (z 2 ) z 1 X1 (z 2 )(47)where X0 (z) and X1 (z) are the Z-transforms of x0 (n) and x1 (n).For example, if x(n) is:x(n) {3, 1, 5, 6, 2, 4, 3, 7}then the polyphase components arex0 (n) {3, 5, 2, 3}(48)x1 (n) {1, 6, 4, 7}.(49)The Z-transforms for this example are given byX(z) 3 z 1 5 z 2 6 z 3 2 z 4 4 z 5 3 z 6 7 z 7X0 (z) 3 5 z 1 2 z 2 3 z 3X1 (z) 1 6 z 1 4 z 2 7 z 3 .In general, X0 (z) and X1 (z) can be obtained from X(z) as,1X0 (z 2 ) (X(z) X( z))(50)2zX1 (z 2 ) (X(z) X( z)) .(51)2The polyphase components x0 (n), x1 (n) can be obtained with thefollowing structure.I. SelesnickEL 713 Lecture Notes23

x(n)- 2 x0 (n)- 2 x1 (n)?zGeneral case: An M -component polyphase decomposition of x(n)is given byx0 (n) x(M n)(52)x1 (n) x(M n 1).(53)xM 1 (n) x(M n M 1).(54)(55)The Z-transform X(z) is then given byX(z) X0 (z M ) z 1 X1 (z M ) · · · z (M 1) XM 1 (z M )(56)where Xi (z) is the Z-transform of xi (n). The polyphase componentXi (z) can be found from X(z) withM 1z i X ikXi (z ) W X(W k z)MM(57)k 0where2πW ej M .I. Selesnick(58)EL 713 Lecture Notes24

EFFICIENT IMPLEMENTATIONThe noble identities and the polyphase decomposition can be usedtogether to obtain efficient structures. Consider again the systemfor interpolation: an up-sampler is followed by a filter. In thissystem, the up-sampler inserts zeros between the samples x(n).There are two disadvantages.1. Half the samples of the input to the filter are zero. That meansthe filter is doing unnecessary computations (multiplications byzero, adding zeros).2. The filter operates at the higher rate.A more efficient implementation can be obtained by writing thefilter in polyphase form, and then using the noble identities. Thisis done through the following transformation of the block diagram.x(n)x(n)-- 2 2 - H0 (z 2 ) x(n)- 2 -y(n)- z 1 H1 (z 2 )H0 (z 2 )-- l-y(n)y(n)6-I. SelesnickH(z)z 1 H1 (z 2 )EL 713 Lecture Notes25

EFFICIENT IMPLEMENTATIONx(n)--x(n) 2 H0 (z 2 ) 2 z 1 H1 (z 2 )-- l-y(n)6 2 H0 (z 2 )- l-y(n)z 1 - 2 x(n)-H0 (z)62H1 (z )- 2 - l 6y(n)z 1 6-H1 (z)- 2 Note that in the last block diagram, the filters operate at the slowerrate, and the filter inputs are not zero. Also note that the filtersh0 (n), h1 (n) are each half the length of the original filter h(n). Theadding node in the last diagram does not incur any actual additions— it implements an interleaving of the two branches.I. SelesnickEL 713 Lecture Notes26

HALF-BAND CASEIf h(n) is a half-band filter, then the polyphase component H0 (z)is 1 (assuming the half-band filter is centered at no 0). In thiscase, the block diagram becomes more simple as shown.x(n)- 2 - l 6y(n)z 1 6-I. SelesnickH1 (z)- 2 EL 713 Lecture Notes27

POLYNOMIAL SIGNALSA (discrete-time) polynomial signal x(n) is a signal of the formx(n) c0 c1 n c2 n2 · · · cd nd .The degree is d. The set of polynomial signals of degree d or lessis denoted by Pd .Consider a system described by the ruley(n) x(n) x(n 1).This system gives the first difference of the signal x(n). It has theimpulse responseh(n) δ(n) δ(n 1),and the transfer functionH(z) 1 z 1and so we can writey(n) h(n) x(n)or Y (z) 1 z 1 X(z).Clearly if x(n) is a constant signal (x(n) c, so we can writex(n) P0 ), then the first difference of x(n) is identically zero, Y (z) 1 z 1 X(z) 0 for x(n) P0 .Moreover, the first difference Y (z) is identically zero only if x(n)is a constant signal.I. SelesnickEL 713 Lecture Notes28

POLYNOMIAL SIGNALSSimilarly, if x(n) is a ramp signal (x(n) c0 c1 n, so we canwrite x(n) P1 ), then the first difference is a constant signal.Therefore the second difference, (defined as the first difference ofthe first difference), must be identically zero. Writing this usingthe Z-transform gives1 z 1 2X(z) 0 for x(n) P1 .Moreover, the second difference of x(n) is identically zero onlyif x(n) is of the form c0 c1 n. Therefore, the set of first degreepolynomial signals P1 is exactly the set of signals that is annihilatedby (1 z 1 )2 .Similarly, if x(n) is a polynomial signal of degree d, thenY (z) 1 z 1 d 1X(z) 0 for x(n) Pd .or equivalently,y(n) h(n) h(n) · · · h(n) x(n) 0 for x(n) Pd .{z} d 1 termsMoreover, y(n) 0 only if x(n) has the form x(n) c0 c1 n c2 n2 · · · cd nd .Therefore we have the following result.x(n) PdI. Selesnick 1 z 1EL 713 Lecture Notes d 1X(z) 029

INTERPOLATION OF POLYNOMIALSWe saw before that the interpolation of discrete-time signals canbe carried out by using an upsampler together with a filter. Forinterpolation by a factor of two (2X interpolation) we have thefollowing diagram.x(n)- 2 H(z)-y(n)Suppose x(n) is a polynomial signal of degree d. Then it is naturalto ask that y(n) also be a polynomial signal of degree d. Butfor just any filter h(n) that will not be the case. What conditionmust h(n) satisfy, to ensure that y(n) is also a polynomial signalof degree d?It turns out that if (1 z 1 )d 1 is a factor of H(z),H(z) Q(z) (1 z 1 )d 1then y(n) Pd whenever x(n) Pd . This can be verified using t

multirate signal processing 1.applications 2.the up-sampler 3.the down-sampler 4.rate-changing 5.interpolation 6.half-band filters 7.nyquist filters 8.the noble identities 9.polyphase decomposition 10.efficient implementation 11.polynomials and multirate filtering 12.interpolation of polynomials i. selesnick el 713 lecture notes 1

Related Documents: