Digital Signal Processing Reference
In-Depth Information
decimation if passed as 0, or by bit reversal if passed as 1. The test signal is the ramp 0:1:
L
1, which
makes evaluation/visualisation of the decimation easy. Figure 3.21, for example, shows the result from
the call
−
LV_FF T(8,0)
Since the test signal's sample values are the same as their respective (original) indices, plot (c)'s
amplitude values are the same as the test sequence's original index values. Thus, we see that the sequence
0:1:7, shown at (a), has been properly decimated into the sequence [0,4,2,6,1,5,3,7], shown at (c).
A butterfly routine, compact in terms of number of lines of code, can easily be written in m-code
(see exercises below) in accordance with Eqs. (3.18) and (3.19). However, a less-efficient looking, but far
more efficient in practice routine to compute the butterflies from the decimated-in-time sequence is as
follows:
Rx = real(x); Ix = imag(x);
M = log2(length(x)); LenSig = length(x);
for L = 1:1:M
LE = 2ˆL; LE2 = LE/2;
uR=1;uI=0;
sR = cos(pi/LE2); sI = -sin(pi/LE2);
for J = 1:1:LE2
Jmin1 = J-1;
for I = Jmin1:LE:LenSig - 1
Ip=I+LE2;
tR = Rx(Ip+1)*uR - Ix(Ip+1)*uI;
tI = Rx(Ip+1)*uI + Ix(Ip+1)*uR;
Rx(Ip+1) = Rx(I+1) - tR;
Ix(Ip+1) = Ix(I+1) - tI;
Rx(I+1) = Rx(I+1) + tR;
Ix(I+1) = Ix(I+1) + tI;
end
tR = uR;
uR = tR*sR - uI*sI;
uI = tR*sI + uI*sR;
end
end
x=Rx+j*Ix;
3.14.5 OTHER ALGORITHMS
Beside the DIT algorithm, there are
Decimation-In-Frequency
(
DIF
) algorithms. For both types of
these two basic algorithms, there are many variations as to whether or not the samples input to the
butterfly routine are in natural or bit-reversed order. There are algorithms in which the input is presented
in natural order and the output is in correct bin order, without any explicit bit-reversal-like reordering.
There are also algorithms that do not require that the signal length be a power of two, such as relative
prime factor algorithms, for example.
Reference [1] gives a very succinct explanation of the radix-2 decimation-in-time algorithm; [2]
and [3] present many butterfly diagrams and discussions covering both DIT and DIF algorithms; [4]
