US4477878A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Discrete Fourier transform with non-tumbled output
Assignee: Gemalto Terminals Ltd
•
Filing: 1981-09-03
•
Granted: 1984-10-16
•
Expires: 2001-09-03
Abstract
Abstract A microprocessor is programmed to perform the DFT on data points read out from and written back into a RAM. In each of a plurality of levels of the transform the points are read out in small groups, subjected to a discrete Fourier transform and written back into different addresses in order to avoid jumbling the order of the points in the ultimate output. The read-out and write-in addresses are read out of a PROM in sequence for each group and added to a base address in a latch. A -N latch, adder and multiplexer ensure that the addition is modulo N. After each group, the base address is changed to a new value by adding another value read out of the PROM and all addresses are worked through in this way in each level. At the start of each level the microprocessor puts the correct PROM start address in a latch and the number of groups (m) in a counter which is decremented to count off the groups and signal the end of a level. The PROM thus stores address value sequences for each level, starting at different start addresses. Moreover there may be different sets of start addresses for different algorithms catering for different numbers of points and forward and inverse transforms.
Inventors
- 👤 Stephen N. Cope
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:45
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/141; G06F17/142
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
203 words
Apparatus for performing the discrete Fourier transform comprising: a data memory for storing data relating to groups of old points to be transformed and data relating to groups of new points which have been transformed; means coupled to the data memory for performing, in each of a succession of levels of transform, elementary discrete Fourier transforms on said groups of old points, thereby to form said groups of new points; and data memory addressing means coupled to the data memory including: an address memory for storing address values; first means for storing the number N of points to be transformed for each level; second means for storing the number m of groups of points; further addressing means for repeatedly addressing sequences of locations in said address memory to read out said address values; and address generating means responsive to said first and second storing means and to the output of said address memory for generating a predetermined series of addresses for reading out said old points from the data memory and writing back said new points into the data memory, wherein said series of addresses is non-sequential for at least one of said reading out and writing back operations performed on said points.
Claim 2
Dependent Claim
203 words
Apparatus for performing the discrete Fourier transform comprising: a data memory for storing data relating to groups of old points to be transformed and data relating to groups of new points which have been transformed; means coupled to the data memory for performing, in each of a succession of levels of transform, elementary discrete Fourier transforms on said groups of old points, thereby to form said groups of new points; and data memory addressing means coupled to the data memory including: an address memory for storing address values; first means for storing the number N of points to be transformed for each level; second means for storing the number m of groups of points; further addressing means for repeatedly addressing sequences of locations in said address memory to read out said address values; and address generating means responsive to said first and second storing means and to the output of said address memory for generating a predetermined series of addresses for reading out said old points from the data memory and writing back said new points into the data memory, wherein said series of addresses is non-sequential for at least one of said reading out and writing back operations performed on said points.
Claim 3
Dependent Claim
42 words
Apparatus according to claim 1, wherein said first and second storing means and said further addressing means include means for receiving values corresponding to a selected mode for performing different discrete Fourier transforms and for selecting corresponding portions of the address memory.
Claim 4
Dependent Claim
21 words
Apparatus according to claim 1, wherein the address memory stores different sequences of address values for read-out and write-in of data.
Claim 5
Dependent Claim
42 words
Apparatus according to claim 1, wherein said address generating means comprising means for storing a base address value and means for adding the address values from the address memory to the base address value to provide point addresses for the data memory.
Claim 6
Dependent Claim
12 words
Apparatus according to claim 4, wherein the adding means adds modulo N.
Claim 7
Dependent Claim
27 words
Apparatus according to claim 4, wherein the address memory further includes means for holding offset values which are periodically read out to modify the base address value.
Claim 8
Dependent Claim
58 words
Apparatus according to claim 6, wherein for each level in which n points at a time undergo the elementary discrete Fourier transform, the address memory includes means for holding in sequence, n address values for data read-out, n address values for data write-in, and an offset value which increments the base value after each elementary discrete Fourier transform.
Claim 9
Independent Claim
172 words
A method of performing the discrete Fourier transform upon a set of N data points in a succession of levels of the transform, comprising the steps of storing said N data points in a data memory, and, in each level: (a) generating a first set of address values; (b) reading out the data points in m groups, under the control of said first set of address values, and storing these groups of data points in said data memory; (c) subjecting each such stored group to an elementary discrete Fourier transform to form a group of new points; (d) generating a second set of address values; (e) writing back said new points into said data memory under the control of said second set of address values; and (f) generating non-sequential address values for at least one of said first and second sets of address values, including the steps of: (i) storing non-sequential address values in an address memory; and (ii) accessing locations of said address memory sequentially to provide said non-sequential address values.
Claim 10
Independent Claim
172 words
A method of performing the discrete Fourier transform upon a set of N data points in a succession of levels of the transform, comprising the steps of storing said N data points in a data memory, and, in each level: (a) generating a first set of address values; (b) reading out the data points in m groups, under the control of said first set of address values, and storing these groups of data points in said data memory; (c) subjecting each such stored group to an elementary discrete Fourier transform to form a group of new points; (d) generating a second set of address values; (e) writing back said new points into said data memory under the control of said second set of address values; and (f) generating non-sequential address values for at least one of said first and second sets of address values, including the steps of: (i) storing non-sequential address values in an address memory; and (ii) accessing locations of said address memory sequentially to provide said non-sequential address values.
References Cited (Backward Citations)
US3591784A
Cited
US3601592A
Cited
US3673399A
Cited
US3748451A
Cited
GB1407401A
Cited
US3812470A
Cited
US3871577A
Cited
GB1530050A
Cited
GB1546173A
Cited
US4156920A
Cited
US4138730A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-10-16 | 1988-04-16 | 1988-10-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-10-16 | 1992-04-16 | 1992-10-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-10-16 | 1996-04-16 | 1996-10-16 | $7700.00 | Window Closed / Lapsed |