VLSI Digital Signal Processing Systems: Design and Implementation

15.7    PROBLEMS

1. Assume that the multipliers a, b, c and d must multiply a common multiplicand x. Determine the number of shifts and additions required to implement a × x, b × x, c × x and d × x given the set of multiplier values (assume an unsigned binary representation):

   (a)    a = 54, b = 45, c = 43, d = 21

   (b)    a = 93, b = 59, c = 55, d = 73

2. Apply the MCM iterative matching algorithm to the multiplier set of Problem 1(a). For each iteration, find the number of bit-wise matches among all constant pairs in the set (see step 2). Determine the number of shifts and additions required after applying the algorithm. How many shifts and additions are saved?
3. Repeat Problem 2 for the multiplier set of Problem 1(b).
4. Apply subexpression elimination for computation y = Tx using linear transformation matrix:

   

   Assume an unsigned binary representation. Determine:

   (a)    the subexpressions required for each column;

   (b)    the unique product expressions;

   (c)    y₁, y₂, y₃, and y₄ in binary format where the bit positions represent the presence or absence of the product expressions. Apply the iterative matching algorithm to y₁, y₂, y₃, and y₄ Calculate the total number of shifts and adds required to realize T after subexpression elimination has been applied. How many shifts and additions have been saved compared to a realization of T that uses no sharing?

5. Repeat Problem 4 for the following linear ...