Method and signal processor for frequency analysis of time domain signals

• US 4,293,921 A
• Filed: 06/15/1979
• Issued: 10/06/1981
• Est. Priority Date: 06/15/1979
• Status: Expired due to Term

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Martin Marietta Corporation
• Inventors: Smith, Winthrop W. Jr.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/048,810
• Time in Patent Office: 844 Days
• Field of Search: 364/726
• US Class Current: 708/405
• CPC Class Codes: G06F 17/144 Prime factor Fourier transforms, e.g. Winograd transforms, number theoretic transforms

Abstract

A signal processor and method for processing N discrete samples of a quantized time domain signal to determine the frequency content or frequency spectrum of the time domain signal. Real and imaginary components of the quantized signal are processed in accordance with a decomposition technique that eliminates considerable hardware and reduces processing time. In a multiple stage processor, interstage multipliers are eliminated. One such disclosed processor includes a first data memory stage for storing the discrete samples of the quantized time domain signal and for retrieving the 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 receives the retrieved samples of the quantized time domain signal and calculates real and imaginary output signals representing the solution to an L-point discrete Fourier transform. A second data memory stage stores the real and imaginary output signals from said L-point computational stage. An M point computational stage, where N=LM and L and M are relatively prime numbers, receives the retrieved output signals and calculates real and imaginary output signals representing the solution to an LM point discrete Fourier transform.

Claims

1. A processor for processing input data comprising N discrete samples a_i (i=0,1,2, . . . , N-1) of a quantized time domain signal having real components a_iR and imaginary components a_iI in order to determine the frequency content thereof, said processor having a computational stage comprising:

means connected to receive signals representing the real and imaginary components for calculating sums and differences of the real components of the input data and for calculating sums and differences of the imaginary components of the input data;

first data storage means for storing said sums and differences of the real and imaginary components of the input data and for retrieving the stored sums and differences of the real and imaginary components in a first predetermined order;

means connected to receive said retrieved sums and differences of the real and imaginary components, in said first predetermined order, for multiplying the retrieved sums and differences by predetermined constant values and for summing the products with at least some of the retrieved sums and differences to produce partial sums of the real and imaginary components;

second data storage means for storing the partial sums as they are produced and for 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, respectively; and

means for calculating the sums and differences of the partial sums of the real components and the imaginary components of the data retrieved from said second storage means to produce real and imaginary output data representating the frequency content of the time domain signal.

2. The processor of claim 1:

wherein the N discrete samples are processed by L and M points transforms, where L and M are relatively prime numbers having a product equal to N;

wherein said computational stage is an M-point computational stage; and

wherein said processor further comprises;

an L-point computational stage; and

third data storage means for receiving output data from said L-point computational stage and for supplying the real and the imaginary components of the quantized time domain signal to the means for calculating the sums and differences of the input data of said M-point computational stage in a third predetermined order in which the component positions are circularly rotated by a predetermined numbers of positions.

3. The processor of claim 2 wherein said third data storage means comprises a first selectively addressable memory, and controller means for selectively addressing said first selectively addressable memory to retrieve the real and imaginary components in said third predetermined order wherein the order of the data has been circularly rotated by q positions where q is a solution to the equation q L-b M+1=0 and where b is representative of the reordering of the real and imaginary output data of the N point transform.

4. The processor of claim 1 wherein said first data storage means comprises a first selectively addressable memory, and controller means for selectively addressing said first selectively addressable memory to retrieve the sums and differences of the real and imaginary components of the input data in said first predetermined order.

5. The processor of claim 1 wherein said second data storage means comprises a second selectively addressable memory, and controller means for selectively addressing said second memory to separately retrieve the partial sums of the real and imaginary components in said second predetermined order.

6. The processor of claim 1:

wherein N is an odd integer, and

wherein said sums of the real components of the input data include sums ##EQU47## wherein said differences of the real components of the input data include differences S^-_iR =a_iR -a.sub.(N-i)R, i=1,2, . . . ,N-1/2;

wherein said sums of the imaginary components of the input data include sums ##EQU48## wherein said differences of the imaginary components of the input data include differences S^-_iI =a_iI -a.sub.(N-i)I, i=1,2, . . . ,N-1/2; and

wherein said partial sums include sums T_bR, T_bI, U_bR, U_bI, b=1,2, . . . ,N-1/2, when;

##EQU49##

7. The processor of claim 6 wherein said first predetermined order comprises the sequence S⁺_0R, S⁺_iR, S^-_iR, S⁺_0I, S⁺_iI, S^-_iI.

8. The processor of claim 6:

wherein said means for calculating the sums and differences of the input data comprises;

a plurality of data channels arranged in parallel with respect to each other, said plurality of data channels including;

a first data channel for calculating the sums of the real and imaginary components of the input data S⁺_iR, S⁺_iI for i=1,2, . . . ,N-1/2;

a second data channel for calculating the differences of the real and imaginary components of the input data S^-_iR, S^-_iI for i=,1,2, . . . ,N-1/2; and

a third data channel for calculating the sums of the amplitudes of the real and imaginary components of the input data S⁺_0R, S⁺_0I ;

wherein said first data storage means includes a selectively addressable memory having 2 N storage locations;

wherein said means for multiplying the retrieved sums and differences and for summing the products to produce partial sums includes N-1/2 data channels arranged in parallel with respect to each other;

wherein said second data storage means includes a selectively addressable memory having 2 N storage locations; and

wherein said means for calculating the sums and differences of the partial sums to produce the output data includes two data channels arranged in parallel with respect to each other.

9. The processor of claim 8 wherein each of said first, second and third data channels comprises:

a summing circuit receiving input signals;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuit; and

a second register receiving output signals from said first register and applying input signals to said first data storage means.

10. The processor of claim 8 wherein each of said N-1/2 data channels comprises:

a multiplier receiving said retrieved sums and differences of the real and imaginary components retrieved from said first data storage means in said first predetermined order;

a summing circuit receiving output signals from said multiplier;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuit; and

a second register receiving output signals from said first register and applying partial sums to said second data storage means.

11. The processor of claim 10 wherein said first predetermined order comprises the sequence S⁺_0R ;

S⁺_iR, i=1,2, . . . ,N-1/2;

S^-_iR, i=1, 2, . . . ,N-1/2;

S⁺_0I ;

S⁺_iI, i=1,2, . . . ,N-1/2;

S^-_iI, i=1,2, . . . ,N-1/2.

12. The processor of claim 8 wherein each of said two data channels comprises:

a summing circuit receiving the data retrieved from said second data storage means in said second predetermined order;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuit; and

a second register receiving output signals from said first register and producing output signals.

13. The processor of claim 12 wherein said second predetermined order comprises the sequence T_bR, U_bR, b=1, 2, . . . ,N-1/2;

U_bI, T_bI, b=1,2, . . . ,N-1/2.

14. The processor of claim 1:

wherein N=2^R, r≧

2; and

wherein said sums of the real components of the input data include sums S⁺_0R =a_0R +a_N/2R ;

S⁺_iR =a_iR +a.sub.(N-i)R, i=1,2, . . . ,N/2-1;

wherein said differences of the real components of the input data include differences S^-_0R =a_0R -a_N/2R ;

S^-_iR =a_iR -a.sub.(N-i)R, i=1,2, . . . ,N/2-1;

wherein said sums of the imaginary components of the input data include sums S⁺_0I =a_0I +a_N/2I ;

S⁺_iI =a_iI +a.sub.(N-i)I, i=1,2, . . . ,N/2-1;

wherein said differences of the imaginary components of the input data include differences S^-_0I =a_0I -a_N/2I ;

S^-_iI =a_iI -a.sub.(N-i)I, i=1,2, . . . ,N/2-1; and

wherein said partial sums include sums ##EQU50## where T.sub.(N/4)R °

=0;

T^E_0I =0;

T^E.sub.(N/4)I =0;

T°

_0I =0;

U°

.sub.(N/4)I =0;

U^E_0R =0 and

U^E.sub.(N/4)I =0.

15. The processor of claim 14 wherein said first predetermined order comprises the sequence S⁺_0R, S^-_0R, S⁺_iR, S^-_iR, S⁺_0I, S^-_0I, S⁺_iI, S^-_iI.

16. The processor of claim 10:

wherein said means for calculating the sums and differences of the input data comprises;

a plurality of data channels arranged in parallel with respect to each other, said plurality of data channels including;

a first data channel for calculating the sums of the real and imaginary components of the input data S⁺_iR, S⁺_iI for i=0,1, . . . ,N/2-1; and

a second data channel for calculating the differences of the real and imaginary components of the input data S^-_iR, S^-_iI for i=0,1,2, . . . , N/2-1;

wherein said first data storage means includes a selectively addressable memory having 2 N storage locations;

wherein said means for multiplying the retrieved sums and differences and for summing the products to produce partial sums includes N/4+1 data channels arranged in parallel with respect to each other;

wherein said second data storage means includes a selectively addressable memory having 2 N storage locations; and

wherein said means for calculating the sums and differences of the partial sums to produce the output data includes four data channels arranged in parallel with respect to each other.

17. The processor of claim 16 wherein each of said first and second data channels comprises:

a summing circuit receiving input signals;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuit;

a second register receiving output signals from said first register and applying input signals to said first data storage means.

18. The processor of claim 16 wherein each of said N/4+1 data channels comprise:

a multiplier receiving said retrieved sums and differences of the real and imaginary components retrieved from said first data storage means in said first predetermined order;

a summing circuit receiving output signals from said multiplier;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuit; and

a second register receiving output signals from said first register and applying partial sums to said second data storage means.

19. The processor of claim 18 wherein said first predetermined order comprises the sequence S⁺_0R ;

S^-_0R ;

S⁺_iR, i=1,2, . . . ,N/2-1;

S^-_iR, i=1,2, . . . ,N/2-1;

S⁺_0I ;

S^-_0I ;

S⁺_iI, i=1,2, . . . ,N/2-1;

S^-_iI, i=1,2, . . . ,N/2-1.

20. The processor of claim 16 wherein each of said four data channels comprises:

a summing circuit receiving the data retrieved from said second storage means in said second predetermined order;

a first register receiving output signals from said summing circuit and applying input signals to said summing circuits; and

a second register receiving output signals from said first register and producing output signals.

21. The processor of claim 9, 12, 17 or 20 wherein said summing circuit comprises:

a controllable data signal control circuit receiving input signals, said input signals including an add/subtract control signal; and

a first summing circuit receiving output signals from said controllable data signal control circuit and from said first register;

wherein when said summing circuit is to calculate a difference said controllable data signal control circuit selectively inverts input data in response to said add/subtract control signal; and

wherein when said summing circuit is to calculate a sum said controllable data signal control circuit selectively does not invert input data in response to said add/subtract control signal.

22. The processor of claim 9, 12, 17 or 20 wherein said summing circuit comprises:

a programmable read-only memory receiving input signals, said input signals including an add/subtract control signal and output signals from said first register; and

wherein said programmable read-only memory selectively adds and subtracts input signals in response to said add/subtract control signal.

23. The processor of claim 9, 12, 17 or 20 wherein said summing circuit and said first register comprise an integrated add/subtract accumulator.

24. The processor of claim 10 or 18:

wherein said multiplier includes first and second input terminals, said first input terminal receiving said retrieved sums and differences and said second input terminal receiving said predetermined constant values;

wherein said summing circuit comprises;

a controllable data signal control circuit receiving input signals, said input signals including output signals from said multiplier and an add/subtract control signal; and

a first summing circuit receiving output signals from said controllable data signal control circuit and from said first register;

wherein when said summing circuit is to calculate a difference said controllable data signal control circuit selectively inverts input data in response to said add/subtract control signal; and

wherein when said summing circuit is to calculate a sum said controllable data signal control circuit selectively does not invert input data in response to said add/subtract control signal.

25. The processor of claim 24 wherein said summing circuit and said first register comprise an integrated add/subtract accumulator.

26. The processor of claim 10 or 18:

wherein said multiplier comprises a first programmable read-only memory receiving input signals, said predetermined constant values being stored in said first programmable read-only memory;

wherein said summing circuit comprises a second programmable read-only memory receiving input signals, said input signals including an add/subtract control signal, output signals from said first programmable read-only memory, and output signals from said first register; and

wherein said second programmable read-only memory selectively adds and subtracts input signals in response to said add/subtract control signal.

27. The processor of claim 10 or 18 wherein said multiplier, said summing circuit and said first register comprise an integrated multiply/accumulator.

31. The method of claim 7 wherein N is an odd integer, and:

wherein the step of calculating and storing sums and differences of the real components of the input data samples includes the steps of;

calculating and storing sums ##EQU51## calculating and storing differences S^-_iR =a_iR -a.sub.(N-i)R, i=1,2, . . . ,N-1/2;

wherein the step of calculating and storing sums and differences of the imaginary components of the input data samples includes the steps of;

calculating and storing sums ##EQU52## calculating and storing differences S^-_iI =a_iI -a.sub.(N-i)I, i=1,2, . . . ,N-1/2; and

wherein the step of producing partial sums of the real and imaginary components includes the step of producing partial sums T_bR, T_bI, U_bR, U_bI, b=1,2, . . . ,N-1/2, when;

##EQU53##

32. The method of claim 31 wherein the step of retrieving the stored sums and differences of the real and imaginary components in accordance with a first predetermined order of retrieval includes retrieving said stored sums and differences in the sequence S⁺_0R ;

S⁺_iR, i=1,2, . . . ,N-1/2;

S^-_iR, i=1,2, . . . ,N-1/2;

S⁺_0I ;

S⁺_iI, i=1,2, . . . ,N-1/2;

S^-_iI, i=1,2, . . . ,N-1/2.

33. The method of claim 31 wherein the step of retrieving the stored partial sums in accordance with a second predetermined order of retrieval includes retrieving the stored partial sums in the sequence T_bR, U_bR, b=1,2, . . . , N-1/2;

U_bI, T_bI, b=1,2, . . . ,N-1/2.

34. The method of claim 7 wherein N=2^r, r≧

2, and;

wherein the step of calculating and storing sums and differences of the real components of the input data samples includes the steps of;

calculating and storing sums S⁺_0R =a_0R +a_N/2R ;

S⁺_iR =a_iR +a.sub.(N-i)R, i=1,2, . . . ,N/2-1; and

calculating and storing differences S^-_0R =a_0R -a_N/2R ;

S^-_iR =a_iR -a.sub.(N-i)R, i=1,2, . . . ,N/2-1;

wherein the step of calculating and storing sums and differences of the imaginary components of the input data samples includes the steps of;

calculating and storing sums S⁺_0I =a_0I +a_N/2I ;

S⁺_iI =a_iI +a.sub.(N-1)I, i=1,2, . . . ,N/2-1; and

calculating and storing differences S^-_0I =a_0I -a_N/2I ;

S^-_iI =a_iI -a.sub.(N-i)I, i=1,2, . . . ,N/2-1; and

wherein the step of producing partial sums of the real and imaginary components includes the step of producing partial sums ##EQU54## where T°

_4/NR =0;

T^E_0I =0;

T^E.sub.(N/4)I =0;

T°

_0I =0;

U°

.sub.(N/4)I =0;

U^E_0R =0 and

U^E.sub.(N/4)I =0.

35. The method of claim 34 wherein the step of retrieving the stored sums and differences of the real and imaginary components in accordance with a first predetermined order of retrieval includes retrieving said stored sums and differences in the sequence S⁺_0R ;

S^-_0R ;

S⁺_iR, i=1,2, . . . ,N/2-1;

S^-_iR, i=1,2, . . . ,N/2-1;

S⁺_0I ;

S^-_0I ;

S⁺_iI, i=1,2, . . . ,N/2-1;

S^-_iI, i=1,2, . . . ,N/2-1.

36. The method of claim 7 wherein N=3 and:

wherein the step (b) includes calculating and storing sum

space="preserve" listing-type="equation">S.sup.+.sub.iR =a.sub.1R +a.sub.2R

and difference

space="preserve" listing-type="equation">S.sup.-.sub.iR =a.sub.iR -a.sub.2R ;

wherein the step (c) includes calculating and storing sums

space="preserve" listing-type="equation">S.sup.+.sub.1I =a.sub.1I +a.sub.2I

and difference

space="preserve" listing-type="equation">S.sup.-.sub.1I =a.sub.1I -a.sub.2I ;

wherein the step (b) further includes calculating and storing sum

space="preserve" listing-type="equation">S.sup.+.sub.0R =a.sub.1R +a.sub.2R +a.sub.0R ;

wherein the step (c) further includes calculating and storing sum

space="preserve" listing-type="equation">S.sup.+.sub.0I =a.sub.1I +a.sub.2I +a.sub.0I ;

wherein the step (e) includes calculating partial sums;

##EQU55## wherein the step (h) includes calculating frequency components;

space="preserve" listing-type="equation">A.sub.0R =S.sup.+.sub.0R

space="preserve" listing-type="equation">A.sub.0I =S.sup.+.sub.0I

space="preserve" listing-type="equation">A.sub.1R =T.sub.1R +S.sub.0R +U.sub.1R

space="preserve" listing-type="equation">A.sub.1R =-T.sub.1I +S.sup.+.sub.0R +U.sub.1I

space="preserve" listing-type="equation">A.sub.2R =T.sub.1R +S.sup.+.sub.0R -U.sub.1R

space="preserve" listing-type="equation">A.sub.2I =T.sub.1I +S.sup.+.sub.0I +U.sub.1I.

28. 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.

29. The processor of claim 28 wherein said first data memory stage comprises a real part for storing signals representing real components of the discrete samples and an imaginary part for storing signals representing imaginary components of the discrete samples;

and

wherein said second data memory stage comprises a real part for storing the real output signals from said L-point computational stage, and an imaginary part for storing the imaginary output signals from said L-point computational stage.

30. 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_i (i=0,1,2 . . . ,N-1) having real components a_iR and imaginary components a_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.

37. The method of claim 30 wherein N=5 and:

wherein the steps (b), (c) include calculating and storing sums and differences;

##EQU56## wherein the step (e) includes calculating partial sums;

##EQU57## wherein the step (h) includes calculating frequency components;

##EQU58##

38. The method of claim 30 wherein N=8 and:

wherein the steps (b), (c) include calculating sums and differences;

##EQU59## wherein the step (e) includes calculating partial sums;

##EQU60## wherein the step (h) includes calculating frequency components;

##EQU61##

39. 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₁ -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 the real and imaginary output signals from said L₁ -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₂ -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₁ ·

L₂ -point Discrete Fourier Transform;

a third data memory stage for storing and retrieving the real and imaginary output signals from said L₂ -point computational stage;

an L₃ -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₁ ·

L₂ ·

L₃ -point Discrete Fourier Transform; and

a fourth data memory stage for storing and retrieving the real and imaginary output signals from said L₃ -point computational stage;

wherein N=L₁ ·

L₂ ·

L₃ and further wherein L₁, L₂ and L₃ are relatively prime numbers.

40. The processor of claim 39 wherein each of said data memory stages includes a real part for storing real components of complex data and an imaginary part for storing imaginary components of complex data.

41. The processor of claim 40 wherein each of said real and imaginary parts of said data memory stages includes a first half and a second half such that data can be read into one of said first and second halves while data is being written out of the other of said first and second halves.

42. The processor of claim 40 wherein each of said data memory stages further includes:

a plurality of selectively addressable random access memories; and

controller means for selectively addressing said random access memories, said controller means including a plurality of programmable read-only memories and a plurality of binary counters, said programmable read-only memories being selectively addressed by said binary counters.

43. The processor of claim 40 further comprising:

a first input register included between said first data memory stage and said L₁ -point computational stage for synchronizing data fed to said L₁ -point computational stage from said first data memory stage;

a second input register included between said second data memory stage and said L₂ -point computational stage for synchronizing data fed to said L₂ -point computational stage from said second data memory stage; and

a third input register included between said third data memory stage and said L₃ -point computational stage for synchronizing data fed to said L₃ -point computational stage from said third data memory stage.

44. The processor of claim 43:

wherein said first input register comprises;

a first set of L₁ serially loaded multi-bit registers selectively receiving data from the real part of said first data memory stage;

a second set of L₁ serially loaded multi-bit registers selectively receiving data from the imaginary part of said first data memory stage;

a first set of L₁ parallel loaded multi-bit registers; and

a second set of L₁ parallel loaded multi-bit registers;

wherein when said first set of serially loaded registers is serially loaded so as to contain L₁ multi-bit data words, said L₁ data words are read in parallel into said first set of parallel loaded registers;

wherein when said second set of serially loaded registers is serially loaded so as to contain L₁ multi-bit data words, said L₁ data words are read in parallel into said second set of parallel loaded registers; and

further wherein data words contained in said first and second sets of parallel loaded registers are multiplexed from said parallel loaded registers to said L₁ -point computational stage;

wherein said second input register comprises;

a first set of L₂ serially loaded multi-bit registers selectively receiving data from the real part of said second data memory stage;

a second set of L₂ serially loaded multi-bit registers selectively receiving data from the imaginary part of said second data memory stage;

a first set of L₂ parallel loaded multi-bit registers; and

a second set of L₂ parallel loaded multi-bit registers;

wherein when said first set of serially loaded registers is serially loaded so as to contain L₂ multi-bit data words, said L₂ data words are read in parallel into said first set of parallel loaded registers;

wherein when said second set of serially loaded registers is serially loaded so as to contain L₂ multi-bit data words, said L₂ data words are read in parallel into said second set of parallel loaded registers; and

further wherein data words contained in said first and second sets of parallel loaded registers are multiplexed from said parallel loaded registers to said L₂ -point computational stage; and

wherein said third input register comprises;

a first set of L₃ serially loaded multi-bit registers selectively receiving data from the real part of said third data memory stage;

a second set of L₃ serially loaded multi-bit registers selectively receiving data from the imaginary part of said third data memory stage;

a first set of L₃ parallel loaded multi-bit registers; and

a second set of L₃ parallel loaded multi-bit registers;

wherein when said first set of serially loaded registers is serially loaded so as to contain L₃ multi-bit data words, said L₃ data words are read in parallel into said first set of parallel loaded registers;

wherein when said second set of serially loaded registers is serially loaded so as to contain L₃ multi-bit data words, said L₃ data words are read in parallel into said second set of parallel loaded registers; and

further wherein data words contained in said first and second sets of parallel loaded registers are multiplexed from said parallel loaded registers to said L₃ -point computational stage.

45. The processor of claim 40 further comprising:

a first output register included between said L₁ -point computational stage and said second data memory stage for synchronizing data fed to said second data memory stage from said L₁ -point computational stage;

a second output register included between said L₂ -point computational stage and said third data memory stage for synchronizing data fed to said third data memory stage from said L₂ -point computational stage; and

a third output register included between said L₃ -point computational stage and said fourth data memory stage for synchronizing data fed to said fourth data memory stage from said L₃ -point computational stage.

46. The processor of claim 45:

wherein said first output register comprises;

L₁ groups of registers selectively receiving L₁ multi-bit data words from said L₁ -point computational stage, said data words being selectively multiplexed from said L₁ groups of registers to the real part of said second data memory stage; and

L₁ groups of registers selectively receiving L₁ multi-bit data words from said L₁ -point computational stage, said data words being selectively multiplexed from said L₁ groups of registers to the imaginary part of said second data memory stage;

wherein said second output register comprises;

L₂ groups of registers selectively receiving L₂ multi-bit data words from said L₂ -point computational stage, said data words being selectively multiplexed from said L₂ groups of registers to the real part of said third data memory stage; and

L₂ groups of registers selectively receiving L₂ multi-bit data words from said L₂ -point computational stage, said data words being selectively multiplexed from said L₂ groups of registers to the imaginary part of said third data memory stage; and

wherein said third output register comprises;

L₃ groups of registers selectively receiving L₃ multi-bit data words from said L₃ -point computational stage, said data words being selectively multiplexed from said L₃ groups of registers to the real part of said fourth data memory stage; and

L₃ groups of registers selectively receiving L₃ multi-bit data words from said L₃ -point computational stage, said data words being selectively multiplexed from said L₃ groups of registers to the imaginary part of said fourth data memory stage.

47. A processor for processing input data comprising three discrete samples a₀, a₁, a₂ of a quantized time domain signal having real components a_0R, a_1R, a_2R and imaginary components a_0I, a_1I, a_2I in order to determine the frequency components A₀, A₁, A₂ 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₀ 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₀ ;

said second adder selectively receiving the real and imaginary components of said samples a₁, a₂ ;

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₁ ;

said first inverter selectively receiving the real and imaginary components of said sample a₂ ;

said third adder selectively receiving the real and imaginary components of the sample a₁, 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₂.

48. A processor for processing input data comprising five discrete samples a_i, i=0,1,2,3,4, of a quantized time domain signal having real components a_iR and imaginary components a_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_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_OI, A_OR ;

wherein a second adder selectively receives the real and imaginary components of said samples a₁, a₄ ;

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_4I, A_1R ;

wherein a first inverter selectively receives the real and imaginary components of said sample a₄ ;

wherein a fourth adder selectively receives the real and imaginary components of said sample a₁, 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_1I, A_4R ;

wherein said sixth adder selectively receives the real and imaginary components of said samples a₂, a₃ ;

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_3I, A_2R ;

wherein a fifth inverter selectively receives the real and imaginary components of said sample a₃ ;

wherein said eighth adder selectively receives the real and imaginary components of said sample a₂, 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_2I, A_3R.

49. A processor for processing input data comprising eight discrete samples a_i, i=0,1,2, . . . ,7, of a quantized time domain signal having real components a_iR and imaginary components a_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₀, a₄ ;

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_0I, A_0R ;

wherein a first inverter selectively receives the real and imaginary components of said sample a₄ ;

wherein a third adder selectively receives the real and imaginary components of said sample a₀, 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_7I, A_1R ;

wherein said fourth adder selectively receives the real and imaginary components of said samples a₂, a₆ ;

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_6I, A_2R ;

wherein a third inverter selectively receives the real and imaginary components of said sample a₆ ;

wherein a sixth adder selectively receives the real and imaginary components of said sample a₂, 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_1I, A_7R ;

wherein a seventh adder selectively receives the real and imaginary components of said samples a₁, a₇ ;

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_4I, A_4R ;

wherein a sixth inverter selectively receives the real and imaginary components of said sample a₇ ;

wherein a ninth adder selectively receives the real and imaginary components of said sample a₁, 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_3I, A_5R ;

wherein said eleventh adder selectively receives the real and imaginary components of said samples a₃, a₅ ;

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_5I, A_3R ;

wherein a tenth inverter selectively receives the real and imaginary components of said samples a₅ ;

wherein said thirteenth adder selectively receives the real and imaginary components of said sample a₃, 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_2I, A_6R.

50. 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_n (n=0,1,2, . . . ,N-1) having real components a_nR and imaginary components a_nI such that N=L₁ ·

L₂ ·

L₃ where L₁, L₂ and L₃ 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₁ -point computational stage and calculating real and imaginary output signal representing the solution to an L₁ -point Discrete Fourier Transform;

(d) storing the real and imaginary output signals of the L₁ -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₂ -point computational stage and calculating real and imaginary output signals representing the solution to an L₁ ·

L₂ -point Discrete Fourier Transform;

(f) storing the real and imaginary output signals of the L₂ -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₃ -point computational stage and calculating real and imaginary output signals representing the solution to an L₁ ·

L₂ ·

L₃ -point Discrete Fourier Transform; and

(h) storing the real and imaginary output signals of the L₃ -point computational stage in a fourth data memory stage.

51. The method of claim 50:

wherein the step (b) includes storing the real components of said samples in a real part of said first data memory stage and storing the imaginary components of said samples in an imaginary part of said first data memory stage;

wherein the step (d) includes storing the real output signals in a real part of said second data memory stage and storing the imaginary output signals in an imaginary part of said second data memory stage;

wherein the step (f) includes storing the real output signals in a real part of said third data memory stage and storing the imaginary output signals in an imaginary part of said third data memory stage; and

wherein the step (h) includes storing the real output signals in a real part of said fourth data memory stage and storing the imaginary output signals in an imaginary part of said fourth data memory stage.

52. The method of claim 51 wherein each of said real and imaginary parts of each of said data memory stages includes a first half and a second half;

wherein each of the steps (b), (d) and (f) include reading real data into one of said first and second halves of said real part while writing real data out of the other of said first and second halves of said real part; and

wherein each of the steps (b), (d) and (f) include reading imaginary data into one of said first and second halves of said imaginary part while writing imaginary data out of the other of said first and second halves of said imaginary part.

53. The method of claim 50 wherein each of the steps (b), (d) and (f) include selectively addressing a plurality of random access memories.

54. The method of claim 50:

wherein the step (a) includes quantizing the time domain signal to produce 120 discrete input data samples a_n, n=0,1,2, . . . ,119, and further wherein L₁ =8, L₂ =5, L₃ =3;

wherein the step (b) includes circularly rotating data sequence a_15m+i (m=0,1,2, . . . ,7) by i positions, i=0,1,2, . . . 14;

wherein the step (c) includes performing an 8-point computation on each of the rotated sequences i=0,1,2, . . . ,14;

wherein the step (d) includes circularly rotating data sequence G_3v+j.sup.(s) (v=0,1,2,3,4) by 3j positions, j=0,1,2 for each s=0,1,2, . . . ,7;

wherein the step (e) includes performing a 5-point computation on each of the rotated sequences j=0,1,2 for each s=0,1,2, . . . ,7;

wherein the step (f) includes retrieving the stored signals in data sequence H_j.sup.(p,s) (j=0,1,2), p=0,1,2,3,4;

s=0,1,2, . . . ,7; and

wherein the step (g) includes performing a 3-point computation on each of the sequences H_j.sup.(p,s), p=0,1,2,3,4 for each s=0,1,2, . . . ,7.