PDSP16116
The butterfly operation
The butterfly operation is the arithmetic operation which is
repeated many times to produce an FFT. The PDSP16116- based
butterfly processor performs this operation in a low power high
accuracy chip set.
A new butterfly operation is commenced each cycle, requir-
ing a new set ot data for B, W, WTA and WTB. Five cycles later,
the corresponding results A′ and B′ are produced along with
their associated WTOUT. In between, the signals SFTA and
SFTR are produced and acted upon by the shifters in the
PDSP1601/A and PDSP16318/A. The timing of the data and
control signals is shown in Fig.6.
A
A′
The results (A′ and B′) of each butterfly calculation in a pass
must be stored to be used later as the input data (A and B) in
the next pass. Each result must be stored together with its as-
sociated word tag, WTOUT. Although WTOUT is common to
both A′ and B′, it must be stored separately with each word as
the words are used on different cycles during the next pass. At
the inputs, the word tag associated with the A word is known as
WTA and the word tag associated with the B word is known as
WTB. Hence, the WTOUTs from one pass will become the WTAs
and WTBs for the following pass. It should be noted that the first
pass is unique in that word tags need not be input into the but-
terfly as all data initially has the same weighting. Hence, during
the first pass alone, the inputs WTA and WTB are ignored.
A′ = A1BW
B′ = A2BW
W
B
B′
Fig. 5 Butterfly operation
CLK
BR, BI, WR, WI
n
n
n
n1
n1
n1
n2
n2
n2
n2
n2
n1
1
1
1
1
2
2
2
4
1
n
n
n
1
1
1
n
2
2
2
n
n
n
n
1
1
1
1
3
3
3
1
n1
n1
n1
n1
n1
n1
n1
n2
n2
4
4
4
2
1
1
1
1
1
n
n
n
n
n
n
n
1
1
1
1
1
1
1
n
4
4
4
3
2
2
2
WTA, WTB
AR, AI
n
2
2
2
2
2
2
2
3
3
3
5
5
SFTA
n
n
n
n
n
n2
n2
n2
n2
n2
1
1
1
3
3
n
n
n
SFTR
PR, PI
DAR, DAI
WTOUT
n2
2
2
n2
n
A′R, A′I, B′R, B′I
Fig. 6 Butterfly data and control signals
Control of the FFT
To enable the block floating point hardware to keep track of
the data, the following signals are provided:
be kept low as long as necessary; the next pass cannot com-
mence until it is brought high again. On the initial cycle of each
EOPSS
new pass, the signal
should be pulled high and it should
remain high until the final cycle of that pass, when it is pulled
low again.
SOBFP
EOPSS
- start of the FFT
- end of current pass
FFT Output Normalisation
These inform the PDSPl 6116/Awhen an FFT is starting and
when each pass is complete. Fig.7 shows how these signals
should be used and a commentary is provided below.
When an FFT system outputs a series of FFT results for
display, storage or transmission, it is essential that all results
are compatible, i.e. with the binary point in the same position.
However, in order to preserve the dynamic range of the data in
the FFT calculation, the PDSP1601/A employs a range of dif-
ferent weightings. Therefore, data must be re-formatted at the
end of the FFT to the pre-determined common weighting. This
can be done by comparing the exponent of given data word
with the pre-determined universal exponent and then shifting
the data word by the difference. The PDSP1601/A, with its
multifunction 16-bit barrel shifter, is ideally suited to this task.
According to theory, the largest possible data result from an
FFT is N times the largest input data. This means that the bi-
nary point can move a maximum of log2(N) places to the right.
Hence, if the universal exponent is chosen to be log2(N) this
should give a sufficient range to represent all data points faithfully.
EOPSS
To begin the FFT, the signal
(where it will remain for the duration of the pass).
should be set high
SOBFP
should
be pulled low during the initial cycle when the first data words
A and B are presented to the inputs of the butterfly processor.
SOBFP
The following cycle
must be pulled high where it should
remain for the duration of the FFT. New data is presented to the
processor each successive cycle until the end of the first pass
EOPSS
of the FFT. On the last cycle of the pass, the
should be
pulled low and held low for a minimum of five cycles, the time
required to clear the pipeline of the butterfly processor so that
all the results from one pass are obtained before beginning the
following pass.
Should a longer pause be required between passes – to ar-
EOPSS
range the data for the next pass, for example – then
may
10
MITEL [ MITEL NETWORKS CORPORATION ]
