Method and signal processor for frequency analysis of time domain signals

A processor for processing N discrete samples of a quantized time domain signal to determine the frequency content thereof comprising:

• a first data memory stage for storing the discrete samples of the quantized time domain signal and for retrieving said stored samples in a predetermined order in which component positions are circularly rotated by a predetermined number of positions from the order of storage thereof;
• an L-point computational stage receiving the retrieved samples of the quantized time domain signal from said first data memory stage and calculating real and imaginary output signals representing the solution to an L-point Discrete Fourier Transform;
• a second data memory stage for storing and retrieving the real and imaginary output signals from said L-point computational stage;
• and
• an M-point computational stage, where N=LM and L and M are relatively prime numbers, receiving the retrieved real and imaginary output signals from said second data memory stage and calculating real and imaginary output signals representing the solution to an LM point Discrete Fourier Transform.

A method for processing a time domain signal to determine the frequency content thereof, comprising the steps of:

• (a) quantizing the time domain signal to produce N discrete input data samples a.sub.i (i=0,1,2 . . . ,N-1) having real components a.sub.iR and imaginary components a.sub.iI ;
• (b) calculating and storing sums and differences of the real components of the input data samples;
• (c) calculating and storing sums and differences of the imaginary components of the input of data samples;
• (d) retrieving the stored sums and differences of the real and imaginary components in accordance with a first predetermined order of retrieval;
• (e) multiplying the retrieved sums and differences of the real and imaginary components, in the order of retrieval, by predetermined constant values and summing the products with at least some of the retrieved sums and differences to produce partial sums of the real and imaginary components;
• (f) storing the partial sums as they are produced;
• (g) retrieving the stored partial sums in accordance with a second predetermined order of retrieval in order to separately retrieve the partial sums of the real and imaginary components;
• and
• (h) calculating the sums and differences of the retrieved partial sums of the real components and the retrieved partial sums of the imaginary components to produce real and imaginary output data representing the frequency content of the time domain signal.

A processor for processing N discrete samples of a quantized time domain signal to determine the frequency content thereof comprising:

• a first data memory stage for storing the discrete samples of the quantized time domain signal and for retrieving said stored samples in a first predetermined order in which component positions are circularly rotated by a predetermined number of positions from the order of storage thereof;
• an L.sub.1 -point computational stage receiving the retrieved samples of the quantized time domain signal from said first data memory stage and calculating real and imaginary output signals representing the solution to an L.sub.1 -point Discrete Fourier Transform;
• a second data memory stage for storing the real and imaginary output signals from said L.sub.1 -point computational stage and for retrieving said stored signals in a second predetermined order in which component positions are circularly rotated by a predetermined number of positions from the order of storage thereof;
• an L.sub.2 -point computational stage receiving the retrieved signals from said second data memory stage and calculating real and imaginary output signals representing the solution to an L.sub.1 .multidot.L.sub.2 -point Discrete Fourier Transform;
• a third data memory stage for storing and retrieving the real and imaginary output signals from said L.sub.2 -point computational stage;
• an L.sub.3 -point computational stage receiving the retrieved real and imaginary output signals from said third data memory stage and calculating real and imaginary output signals representing the solution to an L.sub.1 .multidot.L.sub.2 .multidot.L.sub.3 -point Discrete Fourier Transform;
• and
• a fourth data memory stage for storing and retrieving the real and imaginary output signals from said L.sub.3 -point computational stage;
• wherein N=L.sub.1 .multidot.L.sub.2 .multidot.L.sub.3 and further wherein L.sub.1, L.sub.2 and L.sub.3 are relatively prime numbers.

A processor for processing input data comprising three discrete samples a.sub.0, a.sub.1, a.sub.2 of a quantized time domain signal having real components a.sub.0R, a.sub.1R, a.sub.2R and imaginary components a.sub.0I, a.sub.1I, a.sub.2I in order to determine the frequency components A.sub.0, A.sub.1, A.sub.2 of the Discrete Fourier Transform of said input data, said processor comprising:

• first, second, third, fourth, fifth and sixth adders;
• first and second inverters;
• first and second programmable read-only memories;
• first, second and third registers;
• and
• a counter;
• said first adder selectively receiving the real and imaginary components of said sample a.sub.0 and receiving output signals from said second adder;
• and
• said first register receiving output signals from said first adder, the output of said first register being the frequency component A.sub.0 ;
• said second adder selectively receiving the real and imaginary components of said samples a.sub.1, a.sub.2 ;
• said first programmable read-only memory receiving output signals from said second adder;
• said second register receiving output signals from said first programmable read-only memory;
• said fourth adder receiving output signals from said first and second registers;
• and
• said fifth adder receiving output signals from said fourth adder and from said third register, the output from said fifth adder being the frequency component A.sub.1 ;
• said first inverter selectively receiving the real and imaginary components of said sample a.sub.2 ;
• said third adder selectively receiving the real and imaginary components of the sample a.sub.1, said third adder receiving output signals from said first inverter, and said third adder receiving a constant;
• said second programmable read-only memory receiving output signals from said third adder;
• said third register receiving output signals from said second programmable read-only memory and from said counter;
• said second inverter receiving output signals from said third register;
• and
• said sixth adder receiving a constant and receiving output signals from said second inverter and from said fourth adder, the output of said sixth adder being the frequency component A.sub.2.

A processor for processing input data comprising five discrete samples a.sub.i, i=0,1,2,3,4, of a quantized time domain signal having real components a.sub.iR and imaginary components a.sub.iI in order to determine frequency components of the Discrete Fourier Transform of said input data, said processor comprising:

• seventeen adders;
• seven inverters;
• five programmable read-only memories;
• six registers;
• and
• one counter;
• wherein a first adder selectively receives the real and imaginary components of said sample a.sub.o and receives output signals from a third adder;
• and
• wherein a first register receives output signals from said first adder, the output of said first register being frequency components A.sub.OI, A.sub.OR ;
• wherein a second adder selectively receives the real and imaginary components of said samples a.sub.1, a.sub.4 ;
• wherein said third adder receives output signals from said second adder and from a sixth adder;
• wherein a first programmable read-only memory receives output signals from said third adder;
• wherein a second register receives output signals from said first programmable read-only memory;
• wherein a ninth adder receives output signals from said first and second registers;
• wherein a tenth adder receives output signals from said ninth adder and from a fourth register;
• and
• wherein an eleventh adder receives output signals from said tenth adder and from a twelfth adder, the output of said eleventh adder being frequency components A.sub.4I, A.sub.1R ;
• wherein a first inverter selectively receives the real and imaginary components of said sample a.sub.4 ;
• wherein a fourth adder selectively receives the real and imaginary components of said sample a.sub.1, receives a constant and receives output signals from said first inverter;
• wherein a fifth adder receives output signals from said fourth adder and from an eighth adder;
• wherein a second programmable read-only memory receives output signals from said fifth adder;
• wherein a third register receives output signals from said second programmable read-only memory and from said counter;
• wherein said twelfth adder receives output signals from said third register and from a sixth register;
• wherein a fifth programmable read-only memory receives output signals from said fourth adder;
• wherein said sixth register receives output signals from said counter and from said fifth programmable readonly memory;
• wherein a second inverter receives output signals from said twelfth adder;
• and
• wherein a thirteenth adder receives output signals from said tenth adder and from said second inverter, the output of said thirteenth adder being frequency components A.sub.1I, A.sub.4R ;
• wherein said sixth adder selectively receives the real and imaginary components of said samples a.sub.2, a.sub.3 ;
• wherein a third inverter receives output signals from said sixth adder;
• wherein a seventh adder receives a constant and receives output signals from said third inverter;
• wherein a third programmable read-only memory receives output signals from said seventh adder;
• wherein said fourth register receives output signals from said third programmable read-only memory;
• wherein a fourth inverter receives output signals from said fourth register;
• wherein a fourteenth adder receives a constant and receives output signals from said ninth adder and said fourth inverter;
• and
• wherein a fifteenth adder receives output signals from said fourteenth adder and from a sixteenth adder, the output of said fifteenth adder being frequency components A.sub.3I, A.sub.2R ;
• wherein a fifth inverter selectively receives the real and imaginary components of said sample a.sub.3 ;
• wherein said eighth adder selectively receives the real and imaginary components of said sample a.sub.2, receives a constant and receives output signals from said fifth inverter;
• wherein a fourth programmable read-only memory receives output signals from said eighth adder;
• wherein a fifth register receives output signals from said counter and from said fourth programmable read-only memory;
• wherein a sixth inverter receives output signals from said fifth register;
• wherein said sixteenth adder receives a constant and receives output signals from said third register and said sixth inverter;
• wherein a seventh inverter receives output signals from said sixteenth adder;
• and
• wherein a seventeenth adder receives a constant and receives output signals from said fourteenth adder and said seventh inverter, the output of said seventeenth adder being frequency components A.sub.2I, A.sub.3R.

A processor for processing input data comprising eight discrete samples a.sub.i, i=0,1,2, . . . ,7, of a quantized time domain signal having real components a.sub.iR and imaginary components a.sub.iI in order to determine frequency components of the Discrete Fourier Transform of said input data, said processor comprising:

• twenty-six adders;
• thirteen inverters;
• first and second programmable read-only memories;
• eight registers;
• and
• one counter;
• wherein a first adder selectively receives the real and imaginary components of said samples a.sub.0, a.sub.4 ;
• wherein a second adder receives output signals from said first adder and from a fourth adder;
• wherein a first register receives output signals from said second adder;
• and
• wherein a fifteenth adder receives output signals from said first register and from a fifth register, the output of said fifteenth adder being frequency components A.sub.0I, A.sub.0R ;
• wherein a first inverter selectively receives the real and imaginary components of said sample a.sub.4 ;
• wherein a third adder selectively receives the real and imaginary components of said sample a.sub.0, receives a constant and receives output signals from said first inverter;
• wherein a second register receives output signals from said third adder;
• wherein a sixteenth adder receives output signals from said second register and from a fourth register;
• and
• wherein a seventeenth adder receives output signals from said sixteenth adder and from a twenty-second adder, the output of said seventeenth adder being frequency components A.sub.7I, A.sub.1R ;
• wherein said fourth adder selectively receives the real and imaginary components of said samples a.sub.2, a.sub.6 ;
• wherein a second inverter receives output signals from said fourth adder;
• wherein a fifth adder receives a constant and receives output signals from said first adder and said second inverter;
• wherein a third register receives output signals from said fifth adder;
• and
• wherein an eighteenth adder receives output signals from said third register and from an eighth register, the output of said eighteenth adder being frequency components A.sub.6I, A.sub.2R ;
• wherein a third inverter selectively receives the real and imaginary components of said sample a.sub.6 ;
• wherein a sixth adder selectively receives the real and imaginary components of said sample a.sub.2, receives a constant and receives output signals from said third inverter;
• wherein said fourth register receives output signals from said sixth adder;
• wherein a fourth inverter receives output signals from said fourth register;
• wherein a nineteenth adder receives a constant and receives output signals from said second register and from said fourth inverter;
• and
• wherein a twentieth adder receives output signals from said nineteenth adder and from a twenty-fourth adder, the output of said twentieth adder being frequency components A.sub.1I, A.sub.7R ;
• wherein a seventh adder selectively receives the real and imaginary components of said samples a.sub.1, a.sub.7 ;
• wherein an eighth adder receives output signals from said seventh adder and from an eleventh adder;
• wherein said fifth register receives output signals from said eighth adder;
• wherein a fifth inverter receives output signals from said fifth register;
• and
• wherein a twenty-first adder receives a constant and receives output signals from said first register and said fifth inverter, the output of said twenty-first adder being frequency components A.sub.4I, A.sub.4R ;
• wherein a sixth inverter selectively receives the real and imaginary components of said sample a.sub.7 ;
• wherein a ninth adder selectively receives the real and imaginary components of said sample a.sub.1, receives a constant and receives output signals from said sixth inverter;
• wherein a tenth adder receives output signals from said ninth adder and from a thirteenth adder;
• wherein said first programmable read-only memory receives output signals from said tenth adder;
• wherein a sixth register receives output signals from said first programmable read-only memory and from said counter;
• wherein said twenty-second adder receives output signals from said sixth register and from a seventh register;
• wherein a seventh inverter receives output signals from said twenty-second adder;
• and
• wherein a twenty-third adder receives a constant and receives output signals from said sixteenth adder and said seventh inverter, the output of said twenty-third adder being frequency components A.sub.3I, A.sub.5R ;
• wherein said eleventh adder selectively receives the real and imaginary components of said samples a.sub.3, a.sub.5 ;
• wherein an eighth inverter receives output signals from said eleventh adder;
• wherein a twelfth adder receives a constant and receives output signals from said seventh adder and said eighth inverter;
• wherein said second programmable read-only memory receives output signals from said twelfth adder;
• wherein said seventh register receives output signals from said second programmable read-only memory;
• wherein said twenty-fourth adder receives a constant and receives output signals from said seventh register and from a thirteenth inverter, said thirteenth inverter receiving output signals from said sixth register;
• wherein a ninth inverter receives output signals from said twenty-fourth adder;
• and
• wherein a twenty-fifth adder receives a constant and receives output signals from said nineteenth adder and said ninth inverter, the output of said twenty-fifth adder being frequency components A.sub.5I, A.sub.3R ;
• wherein a tenth inverter selectively receives the real and imaginary components of said samples a.sub.5 ;
• wherein said thirteenth adder selectively receives the real and imaginary components of said sample a.sub.3, receives a constant and receives output signals from said tenth inverter;
• wherein an eleventh inverter receives output signals from said thirteenth adder;
• wherein a fourteenth adder receives a constant and receives output signals from said ninth adder and said eleventh inverter;
• wherein said eighth register receives output signals from said fourteenth adder;
• wherein a twelfth inverter receives output signals from said eighth register;
• and
• wherein a twenty-sixth adder receives a constant and receives output signals from said third register and from said twelfth inverter, the output of said twenty-sixth adder being frequency components A.sub.2I, A.sub.6R.

A method for processing a time domain signal to determine the frequency content thereof, comprising the steps of:

• (a) quantizing the time domain signal to produce N discrete input data samples a.sub.n (n=0,1,2, . . . ,N-1) having real components a.sub.nR and imaginary components a.sub.nI such that N=L.sub.1 .multidot.L.sub.2 .multidot.L.sub.3 where L.sub.1, L.sub.2 and L.sub.3 are relatively prime numbers;
• (b) storing said discrete samples in a first data memory stage and retrieving said stored samples in a first predetermined order in which component positions are circularly rotated by a predetermined number of positions from the order of storage thereof;
• (c) receiving the retrieved samples in said first predetermined order in an L.sub.1 -point computational stage and calculating real and imaginary output signal representing the solution to an L.sub.1 -point Discrete Fourier Transform;
• (d) storing the real and imaginary output signals of the L.sub.1 -point computational stage in a second data memory stage and retrieving said stored signals in a second predetermined order in which component positions are circularly rotated by a predetermined number of positions from the order of storage thereof;
• (e) receiving the retrieved signals in said second predetermined order in an L.sub.2 -point computational stage and calculating real and imaginary output signals representing the solution to an L.sub.1 .multidot.L.sub.2 -point Discrete Fourier Transform;
• (f) storing the real and imaginary output signals of the L.sub.2 -point computational stage in a third data memory stage and retrieving said stored signals;
• (g) receiving the retrieved signals from said third data memory stage in an L.sub.3 -point computational stage and calculating real and imaginary output signals representing the solution to an L.sub.1 .multidot.L.sub.2 .multidot.L.sub.3 -point Discrete Fourier Transform;
• and
• (h) storing the real and imaginary output signals of the L.sub.3 -point computational stage in a fourth data memory stage.