An Efficient Circulant MIMO Equalizer for CDMA Downlink: Algorithm and VLSI Architecture

EURASIP Journal on Applied Signal Processing

x

x

x

x

x

Figure 3: Reduced-state FFT butterfly tree.

by defining the input sequence to the FFT module as {x(i)} =
[0, emm(1),..., em,m(L), 0, ..., 0], we only need to compute
the real part FFT of the x(i) to get fmm(k). From the but-
terfly decomposition, we have the recursion for the real-part
FFT computation as

% ( X ( к )) = % ( X 1( к )) + % ( Wk_pX2( к )),
%{X{к + L₂p)) =%(X 1(к)) -%(WkpX2(к))

for к = 0, 1, ...,Lp/2 - 1. This reduces the complex multi-
plication and addition to only real multiplication and addi-
tion for one stage. The butterfly unit becomes a reduced-state
partial-butterfly-unit (PBFU) as the dotted line units shown
in Figure 3 for an example of 16-point FFT.

From the recursion, it can be shown that we can prune
the redundant computations by replacing the complex mul-
tiplication in the butterfly units for some portion of the FFT
BFU tree. Before considering the many zeros in the input
coefficients, the total number of PBFU is Lp - 1. Since the
total number of BFU is (Lp/2) log₂ Lp, the total number of
full-BFU (FBFU) is given by (Lp/2) log₂ Lp - Lp + 1. Con-
sidering that x(i) = 0onlyfori ∈ [1, L], L<Lp/2, we can
further truncate the computations related to the zero values.
After pruning all the unnecessary BFU branches, the FBFUs
and PBFUs only take effects from stage 3. The number of
FBFU is reduced to (L_p/2) * log₂ L_p - 2L_p + 6. This also
reduces the number of memory access and register files for
stage 1 and stage 2 as well as in the partial BFUs. The fi-
nal data flow is shown as the BFU tree in Figure 3. In the
figure, only the shaded portion has full-BFUs. Table 1 sum-
marizes the required operations in terms of the real mul-
tiplications/additions and memory read/write. In the table,
RS-FFT indicates the reduced-state FFT- and ZP-means zero
pruning. Although the saving diminishes when the length of
FFT increases to a very large number, the RS-FFT with ZP

<<   <   3   4   5   6   7   8   9   >   >>