A prime-factor fast algorithm is proposed for the computation of the multidimensional forward and inverse discrete cosine transform (DCT). By using an example of two-dimensional (2-D) DCT, it shows that an r-dimension...
详细信息
A prime-factor fast algorithm is proposed for the computation of the multidimensional forward and inverse discrete cosine transform (DCT). By using an example of two-dimensional (2-D) DCT, it shows that an r-dimensional DCT can be obtained from a 2r dimensional DCT with a post-processing stage. Efficient method for input/output mapping is reported to substantially reduce the computational overhead associated with the prime-factoralgorithm.
A new method for the self-calibration of divided circles is presented which is based on a known prime factor algorithm for the discrete Fourier transform (DFT). The method, called primefactor division (PFD) calibrati...
详细信息
A new method for the self-calibration of divided circles is presented which is based on a known prime factor algorithm for the discrete Fourier transform (DFT). The method, called primefactor division (PFD) calibration, is of interest in angle metrology specially for self-calibrating angle encoders, and generally for a significant shortening of the cross-calibration between two divided circles. It requires that the circular division number N can be expressed as a product N = R x S, whereby the factors R and S are relatively prime integer numbers. For the self-calibration of a divided circle, N difference measurements between R angle positions in a regular distribution and one reference angle position determined by S are evaluated by a two-dimensional DFT, yielding the N absolute division errors. The factor R is preferably chosen small, down to a minimum of R = 2, whereas the factor S may be as large as appropriate for the division number N of interest. In the case of a cross-calibration between two divided circles, the PFD method reduces the number of measurements necessary from N-2 to (R + 1) x N. Experimental results are demonstrated for the calibrations of an optical polygon with 24 faces (primefactor product 3 x 8) and a gearwheel with 44 teeth (primefactor product 4 x 11).
In this brief contribution, an efficient pipeline architecture is proposed for the realization of the prime factor algorithm (PFA) for digital signal processing. By using the extended diagonal feature of the Chinese R...
详细信息
In this brief contribution, an efficient pipeline architecture is proposed for the realization of the prime factor algorithm (PFA) for digital signal processing. By using the extended diagonal feature of the Chinese Remainder Theorem (CRT) mapping, we show that the input data sequence tan be directly loaded into a multidimensional array for the PFA computation without any permutation. Short length modules are modified such that an in-place and in-order computation is allowed. The computed results can then he directly restored back to the memory array without the need for further reordering. More importantly, the CRT mapping ran also be used to represent the output data, hence we can utilize the extended diagonal feature of the CRT mapping to directly send the computed results to the outside world. As compared to the previous approaches, the present approach requires no shifting or rotation during the data loading and retrieval processes. In the case of multidimensional PFA computation, it does not require the computation to be split up into a number of two-dimensional computations. Hence, the overhead required for data loading and retrieval in each two-dimensional stage can be saved.
This brief proposes an efficient prime factor algorithm for the discrete cosine transform. In the proposal, we formulate the decomposition directly, by using the proposed input and output mapping, a novel in-place add...
详细信息
This brief proposes an efficient prime factor algorithm for the discrete cosine transform. In the proposal, we formulate the decomposition directly, by using the proposed input and output mapping, a novel in-place address generation scheme for input index mapping is derived, while the formulations in the literature require a table to store the index mapping. Besides, our approach requires one output index mapping only while the conventional algorithms require two index mapping. Hence, by using the proposed mappings and address generation techniques, less temporary storage is required, such that a reduction on memory requirement can be achieved during the implementation. A comparison of the address generation time between our approach and the conventional approach is also shown.
This letter describes fixed-point implementations of the Winograd and primefactor FFT algorithms in which multiplications are replaced by additions, subtractions and shifts. Methods are described for minimizing the n...
详细信息
This letter describes fixed-point implementations of the Winograd and primefactor FFT algorithms in which multiplications are replaced by additions, subtractions and shifts. Methods are described for minimizing the number of additions and subtractions, while achieving a required level of accuracy. VLSI implementation of the resulting FFTs could achieve very high speed and/or power efficiency. The method can be used to provide any chosen accuracy;examples are presented for 12 to 20 bit accuracy.
A prime factor algorithm for computing the discrete Hartley transform (DHT) is presented. It is shown that the short length DHTs used by the prime factor algorithm can be nested to lead to the Winograd Hartley transfo...
详细信息
A prime factor algorithm for computing the discrete Hartley transform (DHT) is presented. It is shown that the short length DHTs used by the prime factor algorithm can be nested to lead to the Winograd Hartley transform algorithm.
This paper presents an efficient memory-based fast Fourier transform processor including 35 different working sizes for LTE systems. A factorization method named high-radixsmall-butterfly combined with a conflict-free...
详细信息
ISBN:
(纸本)9781479953417
This paper presents an efficient memory-based fast Fourier transform processor including 35 different working sizes for LTE systems. A factorization method named high-radixsmall-butterfly combined with a conflict-free address scheme for 2(p)3(q)5(r) point memory-based FFT processor is proposed. The processor can not only provide conflict-free concurrent data access from different memory banks but also continuous-flow working mode. Moreover, we exploit prime factor algorithm to decrease the multiplications and twiddle factor storage. In addition, a unified Winograd Fourier transform algorithm butterfly core was designed for the small 2, 3, 4, 5-point DFTs. The FFT processor was implemented in a SMIC 55nm CMOS process with core area 1:063mm(2). The chip consumes 40.8mW at 122.88MHz operating frequency with 1.08V voltage supply.
Fast Fourier transform algorithms rely upon the choice of certain bijective mappings between the indices of the data arrays. The two basic mappings used in the literature lead to Cooley-Tukey algorithms or to prime fa...
详细信息
Fast Fourier transform algorithms rely upon the choice of certain bijective mappings between the indices of the data arrays. The two basic mappings used in the literature lead to Cooley-Tukey algorithms or to prime factor algorithms. But many other bijections also lead to FFT algorithms, and a complete classification of these mappings is provided. One particular choice leads to a new FFT algorithm that generalizes the prime factor algorithm. It has the advantage of reducing the floating point operation count by reducing the number of trigonometric function evaluations. A certain equivalence relation is defined on the set of bijections that lead to FFT algorithms, and its connection with isomorphism classes of group extensions is studied. Under this equivalence relation every equivalence class contains bijections leading to an FFT algorithm of the new type.
An efficient algorithm for computing the discrete cosine transform (DCT) is presented. It is based on an index mapping which converts an odd-length DCT to a real-valued DFT of the same length using permutations and si...
详细信息
An efficient algorithm for computing the discrete cosine transform (DCT) is presented. It is based on an index mapping which converts an odd-length DCT to a real-valued DFT of the same length using permutations and sign changes only. The real-valued DFT can then be computed by efficient real-valued FFT algorithms such as the prime factor algorithm. The algorithm is more efficient than an earlier one because no postmultiplications are required.
A fast Fourier transform algorithm for computing N=N(1)xN(2)-point DFT, where both factors N-1 and N-2 are smaller positive integer, said to be a double factors algorithm(DFA), is developed. The DFA subdivides a DFT o...
详细信息
ISBN:
(纸本)9781424439867
A fast Fourier transform algorithm for computing N=N(1)xN(2)-point DFT, where both factors N-1 and N-2 are smaller positive integer, said to be a double factors algorithm(DFA), is developed. The DFA subdivides a DFT of length N=N(1)xN(2) into smaller transforms of length N-1 and N-2 and takes the following steps:(1) computes N1N2-point DFTs, (2) multiplies the values of DFT by twiddle factors, (3) computes N2N1-point DFTs. The structure of the DFA is similar to those of the most simple PFA and WFTA, but N-1 and N-2 are not necessarily relatively prime. When N=2(M) or 4(M), the total number of computations of DFT in the DFA is less than those in the radix-2 and radix-4 FFT algorithm but slightly more than that in the split-radix FFT algorithm. When N is other values, the total number of computations of DFT in the DFA is less than those in the PFA and WFTA.
暂无评论