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)    y1, y2, y3, and y4 in binary format where the bit positions represent the presence or absence of the product expressions. Apply the iterative matching algorithm to y1, y2, y3, and y4 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 ...

Get VLSI Digital Signal Processing Systems: Design and Implementation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.