VLSI computation of the partial DFT for (de)modulation in multi-channel OFDM system

Efficient computation of partial DFT for comb spectrum evaluation is of essential importance for the emerging OFDM system. A new pruning algorithm has been proposed by He and M. Torkelson (see Proc. International Conf. on Digital Signal Processing, Limassol, Cyprus, 1995), which has a computational complexity of O(N+MlogM), instead of O(NlogM), that of previous approaches for general partial DFT computation. A straightforward lattice decomposition approach, which has a complexity of O(N+M²) but is more suitable for parallel processing, and a VLSI architecture with a linear systolic array implementation are presented. The application of distributed arithmetic to a pipelined bit-serial complex multiplier allows each multiplier in the processing elements to take an area equivalent to 2 real multipliers and the processor to be bit-level pipelined. A significant advantage over conventional implementation is that tuning to different channels can be easily accomplished by changing the coefficients without altering the data flow