Efficient implementation of DSP algorithms

Description:

Modern DSP algorithms usually involve a large number of multiplications, which take a large amount of resources, in term of chip area (DSP, FPGA and VLSI chips) and power. A simple method to reduce the complexity is to quantize the coefficients to be multiplied to some simple numbers (e.g., -2, -1, -0.5, 0, 0.5, 1, 2), which do not require multiplications. Of course, this method does not guarantee that the performances of the resultant DSP algorithms have the same performances as the original versions. But in some cases, (e.g., frame synchronization in IEEE 802.11a systems using simple correlator), extensive simulations show that with the right combination of quantization, the loss in performances is small. Then this approach worth pursuing.

A more sophisticated method is to quantize the original coefficients into sum-of-power-of-two (SOPOT) expressions. The basic idea is best illustrated by an example. If we want to calculate 7x, where x is an input signal, then this can be implemented as 8x-x. In this case we only need to shift x three bits to the left and minus x. In general, all the fixed multiplications can be implemented efficiently using limited number of hard-wired shifters and adders only. The implementation complexity can be further reduced by using the concept of multiplier block. For example, we need to calculate two multiplications 7x and 21x. Direct SOPOT implementation results in (8-1)x and (16+4+1)x, this requires three shifts and three additions. On the other hand, 21x can be realized as 7(2+1)x, then the result 7x calculated from (8-1)x can be reused. This approach only requires two shifts and two additions, which results in 1/3 reduction in complexity. Of course, performing such optimization for a large set of numbers simultaneously requires a computer program.

Representative Publications:

Carson K.S. Pun, Y.C. Wu, S.C. Chan, and K.L. Ho, “On the design and efficient implementation of the farrow structure,”

Kun-Wah Yip, Yik-Chung Wu
and Tung-Sang Ng, “Design of Multiplierless Correlators for
Timing Synchronization in IEEE 802.11a Wireless LANs" *IEEE
Transactions on Consumer Electronics*, vol. 29, pp. 107-114, Feb.
2003. [PDF]