9

produces two results. These results are then stored in the

registers from which the data came. This type of implemen-

tation is referred to as an “in place” FFT algorithm.

The arithmetic processing unit performs an operation know as

the radix 2 butterfly which is shown graphically in Figure 6. In

this diagram the node in the center of the butterfly represents

summing point while the arrow represents a multiplication

point. The flow of an FFT computation is described by dia-

grams comprised of many butterflies as shown in Figure 7.

The FFT processing shown in Figure 7 consists of three

stages of radix 2 butterfly computation. The read/write

addressing, expressed in binary, for each stage is shown in

Table 5. The specialized addressing required here is pro-

duced by using the crosspoint switch to map the address bits

from the sequence generator to the chip output.

The mapping for the sequencer’s crosspoint switch is deter-

mined, by inspecting the addressing for each stage. For

example, the first stage of addressing is generated by con-

figuring the crosspoint switch so that bit 0 of the switch input

is mapped to bit 2 of the switch output, bit 1 of the switch

input is mapped to bit 0 of the output, and bit 2 of the switch

input is mapped to bit 1 of the switch output. The remainder

of the switch I/O map is configured 1:1, i.e., bit-3 of the

switch input is mapped to bit 3 of the switch output. Under

this

configuration,

a

sequence

generator

output

of

0,1,2,3,4,5,6,7 will produce a crosspoint switch output of

0,4,1,5,2,6,3,7. The switch maps for the other stages, as

well as a map for the bit-reverse addressing of the FFT

result is given in Table 5.

The serial count required as input for the crosspoint switch is

generated by configuring the sequence generator with the

following:

1.

Start Address

= 0

4. Step Size

= 1

2.

Block Size

= 8

5. Block Step Size

= 0

3.

Number of Blocks = 1

Under this configuration the sequence generator will pro-

duce a count from 0 to 7 in increments of 1. The FFT length

corresponds to the Block Size, in this case 8.

The serial count from the sequence generator is converted

into the desired addressing sequence by applying the appro-

priate map to the crosspoint switch. In this application, the

switch mapping changes for each stage of the FFT computa-

tion. Thus, while one address sequence is being completed,

the crosspoint switch is being configured for the next stage

of FFT addressing. When one stage of addressing is com-

plete, the new switch configuration is loaded into the current

state registers by an internal or externally generated start or

restart.

The crosspoint switch is configured for the first stage of

addressing by writing a 0 to switch output register 2, a 2 to

switch output register 1, and a 0 to switch output register 2.

These values are loaded by first writing the address of

switch output register 0 and then loading data using auto-

address increment mode (see Table 1). The remaining regis-

ters are assumed to be configured in 1:1 mode as a result of

a prior “RESET”. The second and third stages of addressing

are generated by reconfiguring the above three registers.

The Address Sequencer can be configured in dual

sequencer mode to provide both read and write addressing

for each butterfly. Since 2 independent 12-bit sequences can

be generated by the Address Sequencer, it can be used to

provide read/write addressing for FFT’s up to 4096 points.

The programmable delay between the MSW and LSW of the

Sequencer output is used to compensate for the pipeline

delay associated with the arithmetic processor.

TABLE 5. FFT ADDRESSING BY COMPUTATIONAL STAGE

STAGE 1

R/WADDR.

STAGE 2

R/W/ADDR.

STAGE 3

R/W/ADDR.

OUTPUT

ADDRESSING

000

000

000

000

100

010

001

100

001

001

010

010

101

011

011

110

010

100

100

001

110

110

101

101

011

101

110

011

111

111

111

111

SWITCH MAPPING

021

201

210

012

HSP45240