Circuit for calculating the discrete Fourier transform

Claim 2

A circuit for calculating the discrete Fourier transform, comprising means (190) for providing time discrimination including a multiplier (41), having a pair of inputs (53, 107) and an output, and a first adder (42) having a pair of inputs, a first one (59) of which is connected to said multiplier output, and a second one (68) of which is connected to a data stream (55) not passing through said multiplier (41), and a second adder (43) having a pair of inputs, a first one (56) of which is connected directly to said multiplier output, and a second one (57) of which is connected to a buffer memory (63), said buffer memory (63) being coupled to said multiplier output, said connections of said first and second adders thereby defining a butterfly data stream configuration, means (500, 124-131) for breaking up calculation of the transform over N points into a succession of independent Fourier transform calculations over groups of N i terms, where N is greater than N i , and including address processor means (125,128) for supplying continuous streams of data (51, 100) to said time discrimination means (190).

Claim 3

The calculation circuit as claimed in claim 1, wherein discrete Fourier transform groups have the same number of terms.

Claim 4

The calculation circuit as claimed in claim 1, comprising at least one random access memory (130, 131) connected to an output of said address processor means (128).

Claim 5

The circuit as claimed in claim 3, further comprising an input/output processor managing the data exchanges between an internal memory and an external memory.

Claim 6

The circuit as claimed in claim 3, wherein said random access memory is divided into two blocks (130,131) each acting alternately as calculation memory and as input-output memory.

Claim 7

The circuit as claimed in claim 5, wherein said circuit is constructed in the form of an integrated circuit.

Claim 8

The circuit as claimed in claim 6, wherein said circuit is constructed from gallium arsenide.

Claim 9

The circuit as claimed in claim 1, further comprising a permanent memory (126) connected to an output of said address processor means.

Claim 10

The circuit as claimed in claim 8, wherein said permanent memory is a read only memory (ROM).

Claim 11

The circuit as claimed in claim 9, wherein said permanent memory comprises at least one of a programmable read only memory (PROM), an eraseable programmable read only memory (EPROM), and an electrically eraseable programmable read only memory (EEPROM).

Claim 12

The circuit as claimed in claim 1, wherein each of said address processor means (125, 128) comprises a binary counter.

Claim 13

The circuit as claimed in claim 1, wherein the address processor means for a coefficient memory generates the same most significant bits for the discrete Fourier transform calculations independently of the number of points.

Claim 14

The circuit as claimed in claim 1, further comprising control means (127) having respective outputs connected to and controlling said address processor means (125,128) and said adders (42, 43), controlling the synchronization of clock signals (162) applied to other circuit elements, and controlling switching (149-161, 163) for carrying out the calculation.

Claim 15

The circuit as claimed in claim 1, further comprising a control device (127) which is a programmable logic array (PLA) and has respective outputs connected to and controlling said address processor means (125, 128) and said adders (42, 43).

Claim 16

The circuit as claimed in claim 1, wherein said circuit is constructed in the form of at least one integrated circuit.

Claim 17

The circuit as claimed in claim 15, wherein said integrated circuit is constructed from gallium arsenide.

Claim 18

A circuit for calculating the discrete Fourier transform, comprising means (190) for providing time discrimination including a multiplier (41), having a pair of inputs (53, 107) and an output, and a first adder (42) having a pair of inputs, a first one (59) of which is connected to said multipler output, and a second one (68) of which is connected to a data stream (55) not passing through said multiplier (41), and a second adder (43) having a pair of inputs, a first one (56) of which is connected directly to said multiplier output, and a second one (57) of which is connected to a buffer memory (63), said buffer memory (63) being coupled to said multiplier output, said connections of said first and second adders thereby defining a butterfly data stream configuration, means (500, 124-131) for breaking up calculation of the transform over N points into a succession of independent Fourier transform calculations over groups of N i terms, where N is greater than N i , and including address processor means (125,128) for supplying continuous streams of data (51, 100) to said time discrimination means (190), and input/output processor means (129), within said breaking up means (124-131), for managing data exchange (100,155) between an internal memory (130,131) and an external memory (646,647), and wherein said internal memory is divided into two blocks (130,131) each acting alternately as calculation memory and as input-output memory.

Claim 19

A circuit for calculating the discrete Fourier transform, comprising means (190) for providing time discrimination including a multiplier (41), having a pair of inputs (53, 107) and an output, and a first adder (42) having a pair of inputs, a first one (59) of which is connected to said multipler output, and a second one (68) of which is connected to a data stream (55) not passing through said multiplier (41), and a second adder (43) having a pair of inputs, a first one (56) of which is connected directly to said multiplier output, and a second one (57) of which is connected to a buffer memory (63), said buffer memory (63) being coupled to said multiplier output, said connections of said first and second adders thereby defining a butterfly data stream configuration, means (500, 124-131) for breaking up calculation of the transform over N points into a succession of independent Fourier transform calculations over groups of N i terms, where N is greater than N i , and including address processor means (125,128) for supplying continuous streams of data (51, 100) to said time discrimination means (190), and input/output processor means (129), within said breaking up means (124-131), for managing data exchange (100,155) between an internal memory (130,131) and an external memory (646,647), and wherein said internal memory is divided into two blocks (130,131) each acting alternately as calculation memory and as input-output memory.