Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-04-11
2004-03-09
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06704760
ABSTRACT:
BACKGROUND
The invention generally relates to discrete Fourier transforms (DFT). In particular, the invention relates to an apparatus and method using a prime factor algorithm (PFA) implementation of DFT components.
In CDMA wireless communications between a base station and a user equipment (UE), channel estimation is performed on the midamble section of the CDMA time slot. Depending on the system burst type, the period length Lm for a typical CDMA midamble is either 256 or 512 chips. However, a portion P of the midamble that is digitally processed for channel estimation is trimmed, such as to 192 or 456 chips respectively, to eliminate the potential bleeding of the adjacent data burst data into the midamble that would corrupt the channel estimation.
The Discrete Fourier Transform (DFT) is a popular mathematical tool that converts the input signal from the discrete time domain to the discrete frequency domain, defined by Equation 1:
X
(
n
)
=
∑
K
=
0
N
-
1
x
(
k
)
·
W
nk
Equation
1
where W
nk
=e
−j2&pgr;nk/N
represents a twiddle factor, with real and imaginary portions cos(2&pgr;nk/N) and sin(2&pgr;nk/N), respectively.
When N points are processed using DFT, the number of operations needed to complete the processing are of the order N
2
. Using a radix 2 Fast Fourier Transform (FFT) to process a digital signal with N points, the number of operations is considerably less at an order of N log (N). However, there is a drawback in taking advantage of the faster radix 2 FFT method, since the input must be padded with zeros for cases where the number N points to be processed is not of the order 2
N
(radix 2), such as for P=192 or 456. By artificially adding zeros to the input signal, the channel estimation becomes more of an approximation since the processing is then performed in a set of values that do not truly represent the signal.
A solution is to decompose the digital signal processing by using smaller matrices of sizes based on the prime factors of P, which results in a method with the accuracy of DFT and with significantly less operations closer to that of FFT method.
Minimizing memory hardware space is a primary concern within a CDMA receiver. Rather then gaining the benefit of operation efficiency through multiple parallel input/output ports, memory with a reduced number of ports such as single or dual port memory are commonly used instead. When data points are stored across a multitude of addresses, with limited input/output (I/O) ports, the hardware becomes the limiting factor for the data processing and retrieving the data to perform computations may require repeated memory accesses, which is inefficient. Thus, during the DFT process, it is desirable to perform as many operations as possible on a piece of data in order to retrieve it less often, with minimal hardware under the limited access constraints.
SUMMARY
An apparatus and method for DFT processing that uses prime factor algorithm (PFA) on a selected number P of midamble chip values received by a CDMA receiver, where P has a plurality M of relatively prime factors F, and the DFT process is divided into M successive F-point DFT processes. During each F-point DFT, the P data values are retrieved from a single port memory and selectively permuted by a controller into parallel caches to optimize factoring with associated twiddle factors stored in parallel registers. The permuted inputs are factored in two or more parallel PFA circuits that comprise adders and multipliers arranged to accommodate any size F-point DFT. The outputs of the PFA circuits are processed by consolidation circuitry in preparation for output permutation of the values which are sent to memory. Once all of the P values are processed for the first of M DFT cycles, the process is repeated for the remaining M cycles using the remaining F values. Operations and hardware are minimized by the input permutation which takes advantage of the inherent symmetries of twiddle factors.
REFERENCES:
patent: 4156920 (1979-05-01), Winograd
patent: 4604721 (1986-08-01), Gray
patent: 6351759 (2002-02-01), Moretti et al.
Becker Peter
Buchert Ryan Samuel
Shahrier Sharif M.
InterDigital Technology Corporation
Malzahn David H.
Volpe and Koenig P.C.
LandOfFree
Optimized discrete fourier transform method and apparatus... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimized discrete fourier transform method and apparatus..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized discrete fourier transform method and apparatus... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3197762