Patent US4519695A successfully refreshed from Google Patents.
US3584782A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast fourier transform method and apparatus
Assignee: AT&T Inc
•
Filing: 1968-07-01
•
Granted: 1971-06-15
•
Expires: 1988-07-01
Abstract
Abstract A method and apparatus is disclosed for performing fast Fourier transformations on real-valued input signals. A systematic procedure is followed in accessing operands on successive iterations, and a uniform set of operations are used at each such iteration. Reductions are realized in the number of redundant computations and the number of storage locations relative to the well-known complex-input transformation.
Inventors
- 👤 Glenn D Bergland
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 03:52
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/141; G06F17/142
Claims Analysis
Total Claims: 67
Claim 1
Independent Claim
240 words
The machine method of generating a sequence of signals which represent Fourier series coefficients of an input sequence of N real-valued signals comprising the steps of: 1. storing said input sequence of signals in a machine memory, 2. generating an ordered set of complex-valued signals, 3. selectively combining in a machine and according to a constant relation said stored signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another, 4. storing said new sequence of signals in said machine memory in place of said sequence of signals previously stored in said machine memory, and 5. iteratively performing steps (3) and (4) with the sequence generated by the immediately preceding iteration and said ordered set of signals entering as operands. 2. The method of claim 1 wherein said combining according to a constant relation comprises the steps of 1. forming product signals corresponding to the product of sets of said stored signals and selected ones of said ordered set of complex-valued signals; 2. adding said product signals to selected others of said sequentially stored signals; 3. generating first conjugate signals corresponding to the conjugate of said product signals; 4. generating second conjugate signals corresponding to the conjugate of said selected others of said sequentially stored signals; and 5. forming difference signals by subtracting selected ones of said conjugate signals from selected ones of said second conjugate signals.
Claim 2
Dependent Claim
7 words
generating an ordered set of complex-valued signals,
Claim 3
Dependent Claim
7 words
generating an ordered set of complex-valued signals,
Claim 4
Dependent Claim
12 words
adding said product signals to selected others of said sequentially stored signals;
Claim 5
Dependent Claim
12 words
adding said product signals to selected others of said sequentially stored signals;
Claim 6
Dependent Claim
68 words
iteratively selectively combining in a machine and according to a constant relation first operand signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another, said first operand signals Comprising said input signals upon the first iteration and said new sequence of signals generated at the immediately preceding iteration upon iterations other than the first.
Claim 7
Dependent Claim
68 words
iteratively selectively combining in a machine and according to a constant relation first operand signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another, said first operand signals Comprising said input signals upon the first iteration and said new sequence of signals generated at the immediately preceding iteration upon iterations other than the first.
Claim 8
Dependent Claim
66 words
means for iteratively selectively combining according to a constant relation first operand signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another, said first operand signals comprising said input signals upon the first iteration and said new sequence of signals generated at the immediately preceding iteration upon iterations other than the first.
Claim 9
Dependent Claim
66 words
means for iteratively selectively combining according to a constant relation first operand signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another, said first operand signals comprising said input signals upon the first iteration and said new sequence of signals generated at the immediately preceding iteration upon iterations other than the first.
Claim 10
Dependent Claim
23 words
means for operating on said first operand signals and said complex-valued signals in accordance with said constant relation to generate said new sequence.
Claim 11
Dependent Claim
23 words
means for operating on said first operand signals and said complex-valued signals in accordance with said constant relation to generate said new sequence.
Claim 12
Dependent Claim
27 words
means for algebraically adding selected ones of said product signals to corresponding ones of said first operand signals, thereby to form said new sequence of complex-valued signals.
Claim 13
Dependent Claim
27 words
means for algebraically adding selected ones of said product signals to corresponding ones of said first operand signals, thereby to form said new sequence of complex-valued signals.
Claim 14
Dependent Claim
10 words
means for applying said input sequences to said arithmetic means.
Claim 15
Dependent Claim
10 words
means for applying said input sequences to said arithmetic means.
Claim 16
Dependent Claim
23 words
means for operating on said first operand signals and said complex-valued signals in accordance with said constant relation to generate said new sequence.
Claim 17
Dependent Claim
23 words
means for operating on said first operand signals and said complex-valued signals in accordance with said constant relation to generate said new sequence.
Claim 18
Dependent Claim
27 words
means for algebraically addiNg selected ones of said product signals to corresponding ones of said first operand signals, thereby to form said new sequence of complex-valued signals.
Claim 19
Dependent Claim
27 words
means for algebraically addiNg selected ones of said product signals to corresponding ones of said first operand signals, thereby to form said new sequence of complex-valued signals.
Claim 20
Dependent Claim
71 words
generating an ordered set of complex-valued signals by performing the steps of A. forming an ordered sequence of exponent signals representing a sequence of integer values Cj,j 0,1,...,N/8; B. forming a first set of exponential signals corresponding to W j,j 0,1...,N/8; C. adding to said first set of exponential signals additional exponential signals formed by interchanging the real and imaginary parts of selected signals in said first set of exponential signals;
Claim 21
Dependent Claim
71 words
generating an ordered set of complex-valued signals by performing the steps of A. forming an ordered sequence of exponent signals representing a sequence of integer values Cj,j 0,1,...,N/8; B. forming a first set of exponential signals corresponding to W j,j 0,1...,N/8; C. adding to said first set of exponential signals additional exponential signals formed by interchanging the real and imaginary parts of selected signals in said first set of exponential signals;
Claim 22
Dependent Claim
17 words
forming a first set of exponential signals corresponding to W j, j 0,1,...,N/8, where W e2 i/N;
Claim 23
Dependent Claim
17 words
forming a first set of exponential signals corresponding to W j, j 0,1,...,N/8, where W e2 i/N;
Claim 24
Dependent Claim
168 words
forming a sequence of signals corresponding to W j, j 0,1, ...,m-1, where W e2 i/N. 6. The method of claim 5 wherein said step of forming an ordered sequence of exponent signals comprises the steps of I. sequentially generating signals representing the integers 0 and 1, thereby forming a base sequence of signals; II. forming a new sequence of signals thereby doubling the length of said base sequence by performing the steps of A. multiplying the second entry of said base sequence by 2; B. sequentially forming the additional even signals of said new sequence by subtracting in turn each nonzero signal of said base sequence from a signal representing twice said new second element; C. reordering the original ones of said base sequence of signals to be the odd ones of said new sequence; III. iteratively repeating step II, With said new sequence being used as the base sequence for the succeeding iteration, until said base sequence comprises the desired number m of said exponent signals.
Claim 25
Dependent Claim
18 words
accessing said ordered set of complex signals as they are required for performing step 3 in claim 1.
Claim 26
Dependent Claim
15 words
placing said new sequence of signals in the positions previously occupied by said destroyed signals.
Claim 27
Dependent Claim
15 words
placing said new sequence of signals in the positions previously occupied by said destroyed signals.
Claim 28
Dependent Claim
18 words
The method of claim 1 wherein said storing of said new sequence is accomplished by the steps of
Claim 29
Dependent Claim
12 words
generating first conjugate signals corresponding to the conjugate of said product signals;
Claim 30
Dependent Claim
12 words
generating first conjugate signals corresponding to the conjugate of said product signals;
Claim 31
Dependent Claim
47 words
forming a set of N/8-1 additional signals by sequentially performing on selected ones of said exponential signals the steps of A. generating a set of negated signals corresponding to selected ones of said exponential signals; and B. interchanging the real and imaginary components of said negated signals.
Claim 32
Dependent Claim
47 words
forming a set of N/8-1 additional signals by sequentially performing on selected ones of said exponential signals the steps of A. generating a set of negated signals corresponding to selected ones of said exponential signals; and B. interchanging the real and imaginary components of said negated signals.
Claim 33
Dependent Claim
27 words
selectively combining said stored signals and said complex-valued signals to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another;
Claim 34
Dependent Claim
27 words
selectively combining said stored signals and said complex-valued signals to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another;
Claim 35
Dependent Claim
37 words
selectively combining in a machine and according to a constant relation said stored signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another,
Claim 36
Dependent Claim
37 words
selectively combining in a machine and according to a constant relation said stored signals and said complex-valued signals, thereby to form a new sequence of complex-valued signals none of which bears a necessary conjugate relation to another,
Claim 37
Dependent Claim
24 words
storing said new sequence of signals in said machine memory in place of said sequence of signals previously stored in said machine memory, and
Claim 38
Dependent Claim
24 words
storing said new sequence of signals in said machine memory in place of said sequence of signals previously stored in said machine memory, and
Claim 39
Dependent Claim
23 words
storing said new sequence of signals in said machine memory in place of said sequence of signals previously stored in said machine memory;
Claim 40
Dependent Claim
23 words
storing said new sequence of signals in said machine memory in place of said sequence of signals previously stored in said machine memory;
Claim 41
Dependent Claim
18 words
generating second conjugate signals corresponding to the conjugate of said selected others of said sequentially stored signals; and
Claim 42
Dependent Claim
18 words
generating second conjugate signals corresponding to the conjugate of said selected others of said sequentially stored signals; and
Claim 43
Dependent Claim
20 words
The method of claim 1 wherein said step of generating said ordered set of complex-valued signals comprises the steps of
Claim 44
Dependent Claim
20 words
The method of claim 1 wherein said step of generating said ordered set of complex-valued signals comprises the steps of
Claim 45
Dependent Claim
19 words
forming difference signals by subtracting selected ones of said conjugate signals from selected ones of said second conjugate signals.
Claim 46
Dependent Claim
19 words
forming difference signals by subtracting selected ones of said conjugate signals from selected ones of said second conjugate signals.
Claim 47
Dependent Claim
24 words
iteratively performing steps (3) and (4) with the sequence generated by the immediately preceding iteration and said ordered set of signals entering as operands.
Claim 48
Dependent Claim
24 words
iteratively performing steps (3) and (4) with the sequence generated by the immediately preceding iteration and said ordered set of signals entering as operands.
Claim 49
Dependent Claim
42 words
iteratively performing steps (3) and (4) with the sequence generated by the immediately preceding iteration and said ordered set of signals entering as operands. 2. The method of claim 1 wherein said combining according to a constant relation comprises the steps of
Claim 50
Dependent Claim
20 words
The method of claim 1 wherein said step of generating said ordered set of complex-valued signals comprises the steps of
Claim 51
Dependent Claim
157 words
The method of claim 1 further comprising the steps of: A. generating a sequence of reference signals corresponding to a sequence of binary numbers each of which binary numbers represents the flipped binary equivalent of a Fourier harmonic number: B. generating a test signal having an initial value corresponding to a binary ''''1;'''' C. testing in order of increasing significance each bit of a given one of said reference signals except the most significant ''''1'''' for equivalence with said test signal; D. replacing each bit tested with a binary ''''1'''' when an equivalence is found upon said testing; E. replacing each bit tested with a binary ''''0'''' when no equivalence is found upon said testing; F. complementing said test signal each time an equivalence is found upon said testing; and G. selecting a result corresponding to the given reference signal from a location in storage specified by said reference signals as modified in steps (D) and (E).
Claim 52
Dependent Claim
33 words
The machine method of generating a sequence of signals corresponding to a sequence of numbers which signals represent Fourier series coefficients of an input sequence of N real-valued signals comprising the steps of:
Claim 53
Dependent Claim
33 words
The machine method of generating a sequence of signals corresponding to a sequence of numbers which signals represent Fourier series coefficients of an input sequence of N real-valued signals comprising the steps of:
Claim 54
Dependent Claim
27 words
The machine method for generating a sequence of signals which represent the Fourier series coefficients corresponding to an input sequence of real-valued signals comprising the steps of:
Claim 55
Dependent Claim
27 words
The machine method for generating a sequence of signals which represent the Fourier series coefficients corresponding to an input sequence of real-valued signals comprising the steps of:
Claim 56
Dependent Claim
21 words
Apparatus for generating a sequence of signals which represent Fourier series coefficients corresponding to an input sequence of real-valued signals comprising:
Claim 57
Dependent Claim
21 words
Apparatus for generating a sequence of signals which represent Fourier series coefficients corresponding to an input sequence of real-valued signals comprising:
Claim 58
Dependent Claim
19 words
Apparatus according to claim 11 wherein said means for combining comprises a plurality of ordered cascaded stages each comprising:
Claim 59
Dependent Claim
36 words
Apparatus according to claim 12 wherein said means for combining further comprises at each stage but the last, output means for applying said new sequence to the input means of the succeeding one of said stages.
Claim 60
Dependent Claim
11 words
Apparatus according to claim 13 wherein said means for operating comprises:
Claim 61
Dependent Claim
33 words
Apparatus according to claim 14 wherein said input sequence of real-valued signals comprises N 2m signals and wherein said plurality of ordered stages comprises m of said stages, m being a positive integer.
Claim 62
Dependent Claim
44 words
Apparatus for generating a sequence of signals which represent Fourier series coefficients in response to an applied input sequence of real-valued signals and an applied input sequence of ordered complex-valued signals, said Fourier coefficients representing the discrete Fourier transform of said real-valued signals, comprising:
Claim 63
Dependent Claim
44 words
Apparatus for generating a sequence of signals which represent Fourier series coefficients in response to an applied input sequence of real-valued signals and an applied input sequence of ordered complex-valued signals, said Fourier coefficients representing the discrete Fourier transform of said real-valued signals, comprising:
Claim 64
Dependent Claim
19 words
Apparatus according to claim 16 wherein said means for combining comprises a plurality of ordered cascaded stages each comprising:
Claim 65
Dependent Claim
36 words
Apparatus according to claim 17 wherein said means for combining further comprises at each stage but the last, output means for applying said new sequence to the input means of the succeeding one of said stages.
Claim 66
Dependent Claim
11 words
Apparatus according to claim 18 wherein said means for operating comprises:
Claim 67
Dependent Claim
33 words
Apparatus according to claim 19 wherein said input sequence of real-valued signals comprises N 2m signals and wherein said plurality of ordered stages comprises m of said stages, m being a positive integer.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-06-14 | 1974-12-14 | 1975-06-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-06-14 | 1978-12-14 | 1979-06-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-06-14 | 1982-12-14 | 1983-06-15 | $7700.00 | Window Closed / Lapsed |