US3601592A — Fast fourier transform addressing system

Claim 1

Independent Claim 195 words

A method for generating sequences of addresses for the Danielson-Lanczos fast Fourier transform algorithm comprising the steps of: generating N/2 sequential first result addresses A during each pass P, where P is an integer from 0 to ((log2N)-1), said value of said integer P being increased by 1 after each pass has been completed, and where N is the number of data points being transformed; generating a second result address B for each of said first result addresses A by adding N/2 to said first result address A, where N is the number of data points being transformed; generating a binary signal N/2(P 1) for each pass P; generating an intermediate address V for each said address A by multiplying said binary signal N/2(P 1) by an integer portion of a fraction 4P (address A)/N; generating a first data address C for each of said first result addresses A, by adding said address A to said intermediate address V associated with said address A; generating a second data address D for each of said result addresses A by adding said first data address C associated with said address A to said binary signal N/2(P 1).

Claim 2

Independent Claim 195 words

A method for generating sequences of addresses for the Danielson-Lanczos fast Fourier transform algorithm comprising the steps of: generating N/2 sequential first result addresses A during each pass P, where P is an integer from 0 to ((log2N)-1), said value of said integer P being increased by 1 after each pass has been completed, and where N is the number of data points being transformed; generating a second result address B for each of said first result addresses A by adding N/2 to said first result address A, where N is the number of data points being transformed; generating a binary signal N/2(P 1) for each pass P; generating an intermediate address V for each said address A by multiplying said binary signal N/2(P 1) by an integer portion of a fraction 4P (address A)/N; generating a first data address C for each of said first result addresses A, by adding said address A to said intermediate address V associated with said address A; generating a second data address D for each of said result addresses A by adding said first data address C associated with said address A to said binary signal N/2(P 1).

Claim 3

Independent Claim 255 words

A method for generating a set of addresses for the Danielson-Lanczos fast Fourier transform algorithm comprising the steps of: generating a first result address A; generating a second result address B by adding a binary signal N/2 to said address A, where N is the number of data points being transformed; generating a binary signal N/2(P 1) where P is a pass number; generating an intermediate address V by multiplying said binary signal N/2(P 1) by an integer portion of a fraction 4P (address A)/N; generating a first data address C by adding said address A to said intermediate address V; generating a second data address D by adding said first data address C to said binary signal N/2(P 1); multiplying said intermediate address by M/N where M is an integer equal to a maximum value of N, to generate a first system constant address; complementing log2(M/4) least significant bits of said first system constant address to generate a second system constant address; selecting said log2(M/4) least significant bits of said first system constant address as a system constant real address and said second system constant address as a system constant imaginary address whenever a bit of significance log2(M/2) of said first system constant address is a binary zero; selecting said log2(M/4) least significant bits of said first system constant address as a system constant imaginary address and said second system constant address as a system constant real address whenever sAid bit of significance log2(M/4) of said first system constant address is a binary one.

Claim 4

Independent Claim 255 words

A method for generating a set of addresses for the Danielson-Lanczos fast Fourier transform algorithm comprising the steps of: generating a first result address A; generating a second result address B by adding a binary signal N/2 to said address A, where N is the number of data points being transformed; generating a binary signal N/2(P 1) where P is a pass number; generating an intermediate address V by multiplying said binary signal N/2(P 1) by an integer portion of a fraction 4P (address A)/N; generating a first data address C by adding said address A to said intermediate address V; generating a second data address D by adding said first data address C to said binary signal N/2(P 1); multiplying said intermediate address by M/N where M is an integer equal to a maximum value of N, to generate a first system constant address; complementing log2(M/4) least significant bits of said first system constant address to generate a second system constant address; selecting said log2(M/4) least significant bits of said first system constant address as a system constant real address and said second system constant address as a system constant imaginary address whenever a bit of significance log2(M/2) of said first system constant address is a binary zero; selecting said log2(M/4) least significant bits of said first system constant address as a system constant imaginary address and said second system constant address as a system constant real address whenever sAid bit of significance log2(M/4) of said first system constant address is a binary one.

Claim 5

Dependent Claim 217 words

A fast Fourier transform addressing system for generating the sequences of addresses required by the Danielson-Lanczos fast Fourier transform algorithm, comprising: a first address generator for generating a first result address A and a second result address B, N/2 times during each pass P; control means connected to said first address generator, for generating at its output a binary signal N/2(P 1) where P is an integer from 0 to ((log2n)-1), said integer P being 0 during a first of said passes, the value of said integer P being increased by 1 after each pass has been completed; an intermediate address generator connected to said control means, for generating an intermediate address whenever one of said first result addresses is generated, said intermediate address being equal to the output of said control means multiplied by the integer portion of 4P (address A)/N; a second address generator connected to said first address generator, to said intermediate address generator, and to said control means, for generating a first data address C and a second data address D whenever one of said first result addresses is generated by adding said first result memory address to said intermediate address thereby generating said first data address C and by adding said first data address C to the output of said control means.

Claim 6

Dependent Claim 217 words

A fast Fourier transform addressing system for generating the sequences of addresses required by the Danielson-Lanczos fast Fourier transform algorithm, comprising: a first address generator for generating a first result address A and a second result address B, N/2 times during each pass P; control means connected to said first address generator, for generating at its output a binary signal N/2(P 1) where P is an integer from 0 to ((log2n)-1), said integer P being 0 during a first of said passes, the value of said integer P being increased by 1 after each pass has been completed; an intermediate address generator connected to said control means, for generating an intermediate address whenever one of said first result addresses is generated, said intermediate address being equal to the output of said control means multiplied by the integer portion of 4P (address A)/N; a second address generator connected to said first address generator, to said intermediate address generator, and to said control means, for generating a first data address C and a second data address D whenever one of said first result addresses is generated by adding said first result memory address to said intermediate address thereby generating said first data address C and by adding said first data address C to the output of said control means.

Claim 7

Dependent Claim 115 words

The fast Fourier transform addressing system of claim 3 wherein said first address generator further comprises: a first counting means for sequentially generating said first result addresses A; a first adding means connected to said counting means for adding a binary signal N/2 to each of said first result addresses, said first adding means thereby generating said second result addresses B; and where said second address generator further comprises: a second adding means connected to said first counting means and to said intermediate address generator, for generating said first data addresses C; and a third adding means connected to said second adding means and to said control means, for generating said second data addresses D.

Claim 8

Dependent Claim 75 words

The fast Fourier transform addressing system of claim 4 wherein said control means further comprises: a first compare means connected to said first counting means, for providing a first reset signal whenever an address of said first result addresses is equal to said binary signal N/2; a control register means for storage of a binary signal N/2, said control register being shifted one position each time said first compare means provides said first reset signal.

Claim 9

Dependent Claim 64 words

The fast Fourier transform addressing system of claim 3 further comprising: a second compare means connected to said control register for generating an algorithm complete signal when the contents of said control register equals a multiplex code signal, said multiplex code signal being a value equal to an integer one-half of a number of multiplex data sets of said N data points being transformed.

Claim 10

Dependent Claim 114 words

The fast Fourier transform addressing system of claim 3 wherein said intermediate address generator further comprises: a second counting means for counting in synchronism with said first counting means; a second compare means connected to said control register and to said second counting means, for generating a second reset signal whenever the contents of said control register and said second counting means are equal; an address register for storing said intermediate address, said address register being cleared by said first reset signal; third adding means connected to said control register and to said address register, for generating said intermediate address, said intermediate address being loaded into said address register by said second reset signal.

Claim 11

Dependent Claim 188 words

The fast Fourier transform addressing system of claim 3 further comprising: a multiplication means connected to said intermediate address generator for generating a first system constant address which is a product of said intermediate address and M/N, where M is an integer equal to a maximum value of N; a complementing means connected to a log2(M/4) least significant outputs of said multiplication means, for generating a 2''s complement of a log2(M/4) least significant bits of said first system constant address, an output of said complementing means being a second system constant address; gating means for selecting said log2(M/4) least significant bits of said first system constant address as a system constant real address and said second system constant address as a system constant imaginary address, whenever a bit of significance log2(M/2) of said first system constant address is a binary zero, and selecting said second system constant address as said system constant real address and said log2(M/4) least significant bits of said first system constant address as said system constant imaginary address, whenever said bit of significance log2(M/2) of said first system constant address is a binary one.

Claim 12

Dependent Claim 59 words

The fast Fourier transform addressing system of claim 8 wherein said multiplication means further comprises: a multiplication shift register having an input connected to said address register and having an output connected to said complementing means, said multiplication shift register having a left shift input connected to a shift pulse generator for shifting said intermediate address left log2(M/N) times.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1974-08-23	1975-02-22	1975-08-24	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1978-08-23	1979-02-22	1979-08-24	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1982-08-23	1983-02-22	1983-08-24	$7700.00	Window Closed / Lapsed

Fast fourier transform addressing system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag