Strength reduction leads to a reduction in hardware complexity by exploiting substructure sharing and leads to less silicon area or power consumption in a VLSI ASIC implementation or less iteration period in a programmable DSP implementation. Strength reduction enables design of parallel FIR filters with a lessthan-linear increase in hardware. | Chapter 9: Algorithmic Strength Reduction in Filters and Transforms Keshab K. Parhi Outline • Introduction • Parallel FIR Filters – Formulation of Parallel FIR Filter Using Polyphase Decomposition – Fast FIR Filter Algorithms • Discrete Cosine Transform and Inverse DCT – Algorithm-Architecture Transformation – Decimation-in-Frequency Fast DCT for 2M-point DCT Chapter 9 2 Introduction • Strength reduction leads to a reduction in hardware complexity by exploiting substructure sharing and leads to less silicon area or power consumption in a VLSI ASIC implementation or less iteration period in a programmable DSP implementation • Strength reduction enables design of parallel FIR filters with a lessthan-linear increase in hardware • DCT is widely used in video compression. Algorithm-architecture transformations and the decimation-in-frequency approach are used to design fast DCT architectures with significantly less number of multiplication operations Chapter 9 3 Parallel FIR Filters Formulation of Parallel FIR Filters Using Polyphase Decomposition • An N-tap FIR filter can be expressed in time-domain as N −1 y ( n ) = h ( n ) ∗ x ( n ) = ∑ h (i ) x ( n − i ) , n = 0,1, 2 ,⋅ ⋅ ⋅, ∞ i =0 – where {x(n)} is an infinite length input sequence and the sequence {h (n )} contains the FIR filter coefficients of length N – In Z-domain, it can be written as ∞ N −1 −n Y ( z) = H ( z) ⋅ X ( z) = ∑ h(n) z ⋅ ∑ x( n) z −n n =0 n= 0 Chapter 9 4 • The Z-transform of the sequence x(n) can be expressed as: X (z) = x(0) + x(1) z −1 + x(2) z −2 + x(3) z −3 + ⋅ ⋅ ⋅ [ ] [ ] = x(0) + x(2)z − 2 + x(4)z −4 + ⋅ ⋅ ⋅ + z −1 x(1) + x(3)z −2 + x(5) z −4 + ⋅ ⋅ ⋅ = X 0 (z 2 ) + z −1 X1(z 2 ) – where X0(z2) and X 1(z2), the two polyphase components, are the ztransforms of the even time series {x(2k)} and the odd time-series {x(2k+1)}, for {0≤k<∞}, respectively • Similarly, the length-N filter coefficients H(z) can be decomposed as: H ( z ) = H 0 ( z 2 ) + z
