FFT pointer mechanism for FFT memory management

Details FFT pointer mechanism for FFT memory management FFT pointer mechanism for FFT memory management

2000-06-05

2004-07-06

Chaki, Kakali (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S400000, C708S404000

Reexamination Certificate

active

06760741

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to Digital Signal Processing (DSP) in general, and more particularly to methods and apparatus for improved “in-place” memory pointer management in support of Fast Fourier Transform (FFT) calculations.
BACKGROUND OF THE INVENTION
A Digital Signal Processor. (DSP) is a special-purpose computer that is designed to optimize digital signal processing tasks such as Fast Fourier Transformation (FFT), digital filtering, image processing, and speech recognition. DSP applications are typically characterized by real-time operation, high interrupt rates, and intensive numeric computations. In addition, DSP applications tend to be intensive in memory access operations and require the input and output of large quantities of data.
FFT data are made up of a sequence of N data points, where one data point comprises two data values, one real and one imaginary. The data points are grouped into N/2 “A” data points and N/2 “B” data points where each FFT butterfly operation as shown in
FIG. 1
operates on one A data point (A
R
,A
I
) and one B data point (B
R
,B
I
) together with various coefficients (W
R
,W
I
) to yield (X
R
,X
I
) and (Y
R
,Y
I
) which provide the A and B data points for the next stage of the FFT operation. The selection of data points as A and B data points for each FFT butterfly operation varies with each stage of the FFT.
The following table labeled Table 1—FFT (A,B) Groupings illustrates the (A,B) data point groupings required for each stage of an FFT having a sequence of 16 data points numbered
0
through
15
.
TABLE 1
FFT (A,B) GROUPINGS
Stage 0
Stage 1
Stage 2
Stage 3
0,8
0,4
0,2
0,1
1,9
1,5
1,3
2,3
2,10
2,6
4,6
4,5
3,11
3,7
5,7
6,7
4,12
8,12
8,10
8,9
5,13
9,13
9,11
10,11
6,14
10,14
12,14
12,13
7,15
11,15
13,15
14,15
The following table labeled Table 2—FFT A/B Dispositions illustrates the A/B disposition of each FFT data point at each stage of a 16-data point FFT:
TABLE 2
FFT A/B DISPOSITIONS
Data Point
Stage 0
Stage 1
Stage 2
Stage 3
0
A
A
A
A
1
A
A
A
B
2
A
A
B
A
3
A
A
B
B
4
A
B
A
A
5
A
B
A
B
6
A
B
B
A
7
A
B
B
B
8
B
A
A
A
9
B
A
A
B
10
B
A
B
A
11
B
A
B
B
12
B
B
A
A
13
B
B
A
B
14
B
B
B
A
15
B
B
B
B
In DSP architectures that perform FFT calculations data are read from and written to memory in several stages. Some DSP architectures employ separate memory spaces for input data and output data. In such a memory arrangement the results of one FFT stage may be written in the order of the A and B data point selection of the next stage, allowing for incremental advancing of pointers to the A and B data point memory addresses. The following table labeled Table 3—A/B Sort Order illustrates a theoretical FFT data point ordering that is pointer-optimized for each stage of a 16-data point FFT:
TABLE 3
A/B SORT ORDER
A/B
Stage 0
Stage 1
Stage 2
Stage 3
A
0
0
0
0
A
1
1
1
2
A
2
2
4
4
A
3
3
5
6
A
4
8
8
8
A
5
9
9
10
A
6
10
12
12
A
7
11
13
14
B
8
4
2
1
B
9
5
3
3
B
10
6
6
5
B
11
7
7
7
B
12
12
10
9
B
13
13
11
11
B
14
14
14
13
B
15
15
15
15
In order to reduce the amount of memory required for FFT, “in-place” memory management schemes have been developed whereby the FFT input data memory space is overwritten with the results of FFT calculations, thus eliminating the need for an additional memory space for storing the results at each stage of the FFT. Unfortunately, such a memory arrangement results in the data points being stored in memory in data point sort order as shown in Table 2 rather than in A/B sort order as shown in Table 3 for stages subsequent to stage 0, thus precluding incremental advancing of pointers to the A and B data point memory addresses. While memory address look-up tables or hard-coded memory addresses may be used, such approaches negate the memory efficiencies of “in-place” FFT.
SUMMARY OF THE INVENTION
The present invention seeks to provide methods and apparatus for improved “in-place” memory pointer management in support of Fast Fourier Transform (FFT) calculations.
There is thus provided in accordance with a preferred embodiment of the present. invention a method for advancing pointers in a memory including a sequence of N data points of a stage M of a Fast Fourier Transform (FFT) whose first stage is stage 0, the N data points including N/2 A data points and NV/2 B data points, the N data points are stored in the memory in 2
M
groupings of A data points, each of the groupings having 2
(Log
2
N)−1−M
data points, and each of the groupings is followed by a grouping of 2
(Log
2
N)−1−M
B data points, the method including the steps of a) setting a pointer index A
p
equal to the binary value of the data point memory index corresponding to the first A data point in the memory, b) setting a pointer index B
p
equal to the binary value of the data point memory index corresponding to the first B data point in the memory, c) setting a first binary bit mask value R
1
equal to 2
(Log
2
N)−1−M
+1, d) setting a second binary bit mask value R
2
equal to 2
(Log
2
N)−1−M
, e) advancing the B
p
pointer index to the data point memory index corresponding to the next B data point in the memory by e1) adding the A
p
pointer index value to R
1
, e2) ORing the results of step e1) with R
2
, and e3) setting the B
p
pointer index value equal to the results of step e2), and f) advancing the A
p
pointer index to the data point memory index corresponding to the next A data point in the memory by f1) adding the A
p
pointer index value to R
1
, f2) ANDing the results of step f1) with the bit-inverted value of R
2
, and f3) setting the A
p
pointer index value equal to the results of step f2).
Further in accordance with a preferred embodiment of the present invention the method further includes repeating steps e) and f) more than one time.
Still further in accordance with a preferred embodiment of the present invention the method further includes repeating steps e) and f) until the A
p
pointer index equals the data point memory index corresponding to the last of the A data points in the memory and the B
p
pointer index equals the data point memory index corresponding to the last of the B data points in the memory.
It is appreciated throughout the specification and claims that the term “data point” refers to a pairing of two data values, a real value and an imaginary value.
It is also appreciated throughout the specification and claims that the term “data point memory index” refers to the minimum number of addressing bits needed to uniquely identify one data point from another within a single memory space.


REFERENCES:
patent: 3617720 (1971-11-01), Gentleman
patent: 3662161 (1972-05-01), Bergland et al.
patent: 3673399 (1972-06-01), Hancke et al.
patent: 3704826 (1972-12-01), Constantin
patent: 3767905 (1973-10-01), Garde
patent: 3871577 (1975-03-01), Avellar et al.
patent: 3965342 (1976-06-01), Constant
patent: 4899301 (1990-02-01), Nishitani et al.
patent: 5091875 (1992-02-01), Wong et al.
patent: 5430667 (1995-07-01), Takano
patent: 5623621 (1997-04-01), Garde
patent: 5838377 (1998-11-01), Greene
patent: 6356926 (2002-03-01), Andre
patent: 6490672 (2002-12-01), Aizenberg et al.
Leena et al., Hardware Implementation of FFT-8086 Based System, 1989, IEEE, p. 507-510.*
Johnson, Conflict Free Memory Addressing for Dedicated FFT Hardware, 1992, IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing vol. 39, No. 5, pp. 312-316.*
Gabor et al., High-Performance FFT Processing Using Reconfigurable Logic, 2001, IEEE, p. 1353-1356.*
Yingtao et al., Twiddle-Factor-Based FFT Algorithm with Reduced Memory Access, 2002, IEEE: Proceedings of the International Parallel and Distributed Processing Symposium, (total 8 pages).*
Yutai, An Effective Memory Addressing Scheme for FFT Processors, 1999, IEEE Transactions on Signal Processing, vol. 47, No. 3, p. 907-911.*
Danny, Simplified Control of FFT Hardware, Dec. 1976, IEEE Transactions on Acoustics, Speech, and Signal Processing, p. 577-579.

Affiliated with

Also associated with

Rating

FFT pointer mechanism for FFT memory management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with FFT pointer mechanism for FFT memory management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FFT pointer mechanism for FFT memory management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3235794