Research
Problem:
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,” IEEE Signal
Processing Letters, vol. 10, no. 7, pp.189-192, Jul. 2003.
[PDF]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]