Rate-changing appears expensive computationally, since for both decimation and interpolation the lowpass filter is implemented at the higher rate. However, this is not necessary.

Interpolation For the interpolator, most of the samples in the upsampled signal are zero, and thus require no computation. ()

For m L m L m L and p m L , x 1 m m N 1 N 2 h L p m y m k N 1 L N 2 L g p k x 0 m L k g p n h L n p Pictorially, this can be represented as in .

These are called polyphase structures, and the g p n are called polyphase filters. Computational cost If h m is a length-N filter: No simplification: N T 1 L N T 0 computations sec Polyphase structure: L L N 1 T 0 o computations sec N T 0 where L is the number of filters, N L is the taps/filter, and 1 T 0 is the rate. Thus we save a factor of L by not being dumb. For a given precision, N is proportional to L, (why?), so the computational cost does increase with the interpolation rate. Can similar computational savings be obtained with IIR structures?

Efficient Decimation Structures We only want every Mth output, so we compute only the outputs of interest. () x 1 m k N 1 N 2 x 0 L m k h k

Polyphase Decimation Structure The decimation structures are flow-graph reversals of the interpolation structure. Although direct implementation of the full filter for every Mth sample is obvious and straightforward, these polyphase structures give some idea as to how one might evenly partition the computation over M cycles.

Efficient L/M rate changers Interpolate by L and decimate by M ().

Combine the lowpass filters ().

We can couple the lowpass filter either to the interpolator or the decimator to implement it efficiently ().

Of course we only compute the polyphase filter output selected by the decimator. Computational Cost Every T 1 M L T 0 seconds , compute one polyphase filter of length N L , or N L T 1 N L M L T 0 N M T 0 multiplies second However, note that N is proportional to L M .