TAILIEUCHUNG - Lecture VLSI Digital signal processing systems: Chapter 15, 16 - Keshab K. Parhi

Lecture VLSI Digital signal processing systems, chapter 15, 16 includes contents: Multiple constant multiplication (MCM), linear transformations, polynomial evaluation, sub-expression sharing in digital filters, using 2 most common sub-expressions in CSD representation. | Chapter 15: Numerical Strength Reduction Keshab K. Parhi • Sub-expression elimination is a numerical transformation of the constant multiplications that can lead to efficient hardware in terms of area, power and speed. • Sub-expression can only be performed on constant multiplications that operate on a common variable. • It is essentially the process of examining the shift and add implementations of the constant multiplications and finding redundant operations. • Example: a × x and b × x, where a = 001101 and b = 011011 can be performed as follows: – a × x = 000100 × x + 001001 × x – b × x = 010010 × x + 001001 × x = (001001 × x) << 1 + (001001 × x). – The term 001001 × x needs to be computed only once. – So, multiplications were implemented using 3 shifts and 3 adds as opposed to 5 shifts and 5 adds. Chap. 15 2 • • • • • Multiple Constant Multiplication(MCM) The algorithm for MCM uses an iterative matching process that consists of the following steps: Express each constant in the set using a binary format (such as signed, unsigned, 2’s complement representation). Determine the number of bit-wise matches (nonzero bits) between all of the constants in the set. Choose the best match. Eliminate the redundancy from the best match. Return the remainders and the redundancy to the set of coefficients. Repeat Steps 2-4 until no improvement is achieved. Chap. 15 3 Example: Constant Value Unsigned a 237 11101101 b 182 10110110 c 93 01011101 Binary representation of constants Constant Unsigned Rem. of a 10100000 b 10110110 Rem. of c 00010000 Red. of a,c 01001101 Updated set of constants 1st iteration Chap. 15 Constant Unsigned Rem. of a 00000000 Rem. of b 00010110 Rem. of c 00010000 Red. of a,c 01001101 Red. of Rem a,b 10100000 Updated set of constants 2nd iteration 4 Linear Transformations • A general form of linear transformation is given as: y =T*x where, T is an m by n matrix, y is length-m vector and x is a length-n vector. It can also be written as: yi =

• Điện - Điện tử
• VLSI Digital signal processing systems
• Digital signal
• Digital signal processing
• DSP systems
• Numerical strength reduction
• Multiple constant multiplication
• FIR Digital Filters
• Parallel processing
• Loop bound
• DSP programs
• Retiming formulation
• Applications of retiming
• Algorithm for unfolding
• Applications of unfolding
• Retiming for folding
• Systolic architecture design
• Projection vector
• Cook toom algorithm
• Fast convolution
• Algorithmic strength reduction
• Parallel FIR filters
• Adaptive filters
• Parallel pecursive
• Round off noise
• State variable description
• Bit level arithmetic architectures
• Parallel multipliers
• Redundant arithmetic
• Redundant number representations
• Low power design
• Programmable DSPs
• DSP applications