Real time fast fourier transform processor with sequential access memory

Claim 2

A real-time Fast Fourier tranform processor with sequential access memory wherein the discrete Fourier transform coefficieNts of electrical signals are calculated by iterative processing known as Fast Fourier Transform, (FFT), said processor comprising: sampling means A converting analog input signals (E) applied thereto into N 2n complex signal samples and producing two temporal sequences relative to the real R and the imaginary I parts, respectively, of said complex signal samples, a calculating means C receiving said sequences and comprising two computation sections C1, C2 for processing respectively, one, the said real part and, the other, said imaginary part, each section including a pair of sequential access data shifting memory elements 51, 52, a synthetizer means 8 generating complex binary reference numbers, a complex number multiplier means 7 connected at the output of each said sections and to the output of said synthetizer, a plurality of controlled switching means 40-48 to selectively switch over the circuit elements, including said memory elements 51, 52 in accordance with each successive iterative processing step, and wherein the pair of memory elements of one of said computation sections has N words capacity each, the shift frequency 2f rate of one said memory element being twice that of the other f during one iterative cycle of processing and the shift frequency rate f of said one memory element being one-half that of the other 2f during the next iterative cycle, and each. said computation sections C1, C2 providing at the end of n iterations output signals corresponding to the real (A1 (k)) and the imaginary (A2(k)) parts respectively of the N looked for Fourier coefficients.

Claim 3

Apparatus according to claim 1, wherein said pair of sequential access memory elements 51, 52 is formed by two/shift registers of N words capacity, the N stages of each said shift registers having a first input at the first stage position, a middle-length input at the N/2 stage position, a first output at the N-1 stage position and a second output at the N stage position; and said calculating means further comprises shift control means effecting shifting of the contents of said registeres at different rates, the shift frequency of one of said registers (for example, 51 2f) being twice that of the other (then: 52 f) and including first switch-over means 40 alternatingly, for successive iterations H2, connecting said shift registers to be shifted at the higher rate, and the lower rate, respectively; connection means B1; 41 connecting and applying N samples in binary order inverse with respect to their natural order to the shift register 51 having the higher shifting (2f) rate; the synthesizer means forming a signal generator 8 generating a binary reference number signal; the complex number multiplier means 7 having the signal from the first output of the N-1 stage position Y and said reference number signal W applied thereto; an adder circuit 61 connected to receive during one iterative cycle the group of bits from the second N output of one of said shift register and to receive continuously the output from said multiplier to add said multiplier output and said second output from the N stage position; a subtraction circuit 62 connected to receive during an iterative cycle the group of bits from said second output N of one said shift register and to receive continuously the output from said multiplier to subtract said multiplier output from said group of bits from the shift register second output N; said controlled switching means comprising means interconnecting the output of said adder 61 to the middle length N/2 input of the other register 52; means interconnecting the output of said subtraction circuit 62 to the first input of the other register 52; commutator means 42, 49, 410, 411 switching in synchronism H2 with said first switch-over means 40 and interchanging the relative connections of said multiplier, adder and subtraction circuits with said registers; and clock means H2 controlling the sequence of switching of said switch-over means, the last sample filled register, at the termination of n successive iterations and upon n operations of said switch-over means, containing the N Fourier coefficients A(k) arranged in their natural order.

Claim 4

A processor according to claim 1 wherein connection means between said sampling means and one said calculating means comprise a circulating sequential access memory means for storage and time compression of said complex signal samples.

Claim 5

Apparatus according to claim 1, wherein said sequential access memory elements 51, 52 comprise a pair of shift registers of N stage capacities, each register having first and second terminals at one end, a third terminal at the other end, and a half-length terminal at the N/2 stage position; and said calculating means further comprises shift control means affecting shifting of the contents of said registers, at different rates, related by a factor of two whereby the shift frequency 2f of one of said registers, e.g., 51 is twice that of the other 52, said shift control means including first switch-over means 40 alternately, for successive iterations H2 connecting said shift registers to be shifted at the higher, or lower rate, respectively; an adder means 61; a subtraction means 62; a synthesizer signal generator 8 generating a binary reference signal W; a multiplier circuit 7 having said binary reference signal W applied thereto as one input; interconnecting means interconnecting outputs from one of said shift registers to the adder means, the subtraction means and to the second input of said multiplier; additional switch-over means 42, 43, 44, 45, 46, 47, 49, 410, 411 interchanging the interconnections of said interconnection means with the respective shift register 51 or 52 in synchronism with the switch-over of said first switch-over means 40 upon each successive iteration; the last register, at the termination of N successive iterations, and upon N operations of said switchover means, containing the N Fourier coefficients A(k) in adjacent address position; and second switch-over means 41 applying a sample signal from said memory means 3 to one shift register for the first iteration and, after said first iteration, recycling a signal containing, as a factor, said reference signal and derived from said multiplier means, to the other shift register 52.

Claim 6

A processor according to claim 4, wherein the means interconnecting output from the shift register is shifted at the higher rate ; and the said second switch-over means 41 applying the sample signals to said memory means apply said signal to the shift register having the higher shifting rate.

Claim 7

A processor according to claim 4, including sequencing circuit means comprising a word counter 93 ; an address counter 95 ; a circulating memory 3 and a comparator 94 ; said comparator being connected to said word counter and said address counter and comparing the output of said counters and supplying an output signal when an inverse binary match between said counters is detected ; and means storing an information signal in said circulating memory connected to the output from said comparator upon detection of said match.

Claim 8

A processor according to claim 1 wherein the: pair of memory elements of each computation section C1, C2 is formed by two shift registers 51, 52 of N stages, each having a first and a second input corresponding respectively to a first and a second stage position, a half length output at the N/2 stage position and an output at the final N stage position; each of the computation sections further comprises an arithmetic element means for adding 61 and subtracting 62 sequences alternatively provided at the outputs of said registers, a cyclical control signals H1, H2, H3 source operating said switching means 40-48 in accordance with predetermined successive steps of operation, and wherein said switching means comprise a first switch-over means 40 applying the shift frequency signal of one shift rate f to one register and of double rate 2f to the other during one cycle of operation and in reversed rate during the next, a second switch-over means 41 connected to a third switch-over means 42 so as to apply an input sample, respectively, to the said first input of register operating at said rate f, and then to apply, respectively to the said first input of register operating at said double rate 2f the sequence resulting from adding 61, subtracting 62 and complex multiplication 7 operations, a fourth switch-over means 43 applying to the said second input of the register operating at said double rate the sum X + Y of samples provided by said half length output and by said final output of the register operating at said rate, a first pair of switch-over mans 44,46 with inputs connected in parallel and connected to the said half length outputs N/2 respectively switchable to one input of an adder and of a subtractor 62 of said arithmetic means, a second pair of switch-over means 45, 47 of same configuration as the first, switching said final outputs N to the other input of said adder and subtractor, the adder element 61 output being connected to said fourth switch 43 and to a first input terminal h of an output switch-over means 48 of said computation section, the subtractor 62 output providing the difference X- Y signal being connected to said complex multiplier 7 further receiving weighting factor W values from said synthetizer means 8, the complex multiplier output being connected to said second switch 41 and to a second input terminal g of said output switch 48, and the real and imaginary parts of the discrete Fourier transform coefficients being provided at the output terminal of said output switch.

Claim 9

A processor according to claim 7, including a sequencing circuit means D1 connected to receive the output of the N Fourier coefficients A(k) in binary order inversely with respect to their natural order from said computation section C, said sequencing circuit means comprising a shift register 90 storing said coefficients; a circulating memory 92; commutator means 91 connected to transfer information from said shift register 90 to the circulating memory element 92; a pair of counters 93, 95 of n capacity, each, the comparator 94 being connected to receive the outputs of said counters and supplying an output signal when an inverse binary match is detected; first clock means H5 connected to step one of said counters 95 and said shift register 90 in synchronism; and second clock means H4 connected to step the other of said counters 93 and said circulating memory element in synchronism; said commutator means being controlled by the output of said comparator 94 upon detection of said inverse binary match of the bits being delivered by said counter.

Claim 10

Processor according to claim 7, wherein the said two shift registers 51, 52 are common to both said computation sections C1, C2 of the said calculating means, one calculating means delivering Fourier coefficients arranged in their natural order, and the other calculating means therein delivering Fourier coefficients arranged in their inverse order.

Claim 11

A processor according to claim 7 wherein said output switch is a three-position commutator actuated by a signal from said cOntrol source and having a first position corresponding to said first input terminal, a second position corresponding to said second input terminal and a third unconnected OFF position, said second and first positions being assumed in sequence after the occurrence of detection of n-1 iterations, the output terminal of the commutator providing N Fourier coefficients.

Claim 12

A processor according to claim 7 wherein said second switch-over means is a commutator actuated by another signal from said control source and connected to the output of a circulating sequential access memory means and to said complex multiplier, said commutator being effective to connect new samples from said memory means to the register having the higher shifting rate during one iteration and then to connect the output of said multiplier to said register having the shifting rate at other times.