Fixed-point error analysis of radix-4 FFT

Radix-4 FFT requires less number of multiplications than radix-2 FFT of the same size, and for the same throughput, it requires less hardware. Hence, quite often, radix-4 structure is preferred to radix-2 structure. This paper evaluates the error performance of radix-4 FFT algorithms (the input quantization error and the coefficient inaccuracy is not considered). The analysis assumes fixed-point two's complement arithmetic, with rounding in the case of multiplication, and truncation in the case of scaling. The predicted results of output noise agree closely with the computer simulation results. The different schemes of scaling for preventing arithmetic overflow are compared from the noise-to-signal ratio point of view. In comparison with radix-2, the radix-4 FFT has got a marginally better error performance.     

A new split-radix FHT algorithm for length-q*2/sup m/DHTs

In this paper, a new split-radix fast Hartley transform (FHT) algorithm is proposed for computing the discrete Hartley transform (DHT) of an arbitrary length N=q*2/sup m/, where q is an odd integer. The basic idea behind the proposed FHT algorithm is that a mixture of radix-2 and radix-8 index maps is used in the decomposition of the DHT. This idea and the use of an efficient indexing process lead to a new decomposition different from that of the existing split-radix FHT algorithms, since the existing ones are all based on the use of a mixture of radix-2 and radix-4 index maps. The proposed algorithm reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FHT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in almost all cases, the same as that of the existing split-radix FHT algorithm for length- q*2/sup m/ DHTs. Since the proposed algorithm is expressed in a simple matrix form, it facilitates an easy implementation of the algorithm, and allows for an extension to the multidimensional case.     

Fast radix-3/9 discrete Hartley transform

An efficient algorithm for computing radix-3/9 discrete Hartley transforms (DHTs) is presented. It is shown that the radix-3/9 fast Hartley transform (FHT) algorithm reduces the number of multiplications required by a radix-3 FHT algorithm for nearly 50%. For the computation of real-valued discrete Fourier transforms (DFTs) with sequence lengths that are powers of 3, it is shown that the radix-3/9 FHT algorithm reduces the number of multiplications by 16.2% over the fastest real-valued radix-3/9 fast Fourier transform (FFT) algorithm     

Comparative performance of fast cosine transform with fixed-pointroundoff error analysis

Suitable scaling schemes are chosen for the Lee's and the Hou's (1984) fast DCT algorithms, and the relative fixed-point roundoff error analyses are carried out, respectively. The average output signal-to-noise ratio are then calculated, and it is shown that in DCT and for N>16 stage-by-stage scaling of Hou's algorithm has the best performance, whereas in inverse DCT, the global scaling of either algorithms has the best performance     

A Split Vector-Radix Algorithm for the 3-D Discrete Hartley Transform

In this paper, we propose a three-dimensional (3-D) split vector-radix fast Hartley transform (FHT) algorithm. The main idea behind the proposed algorithm is that the radix-2/4 approach is introduced in the decomposition of the 3-D discrete Hartley transform by using an appropriate index mapping and the Kronecker product. This provides an algorithm based on a mixture of radix-(2$,times,$2$,times,$2) and radix-(4$,times,$4$,times,$4) index maps and has a butterfly that is characterized by simple closed-form expressions. This algorithm offers substantial reductions in the numbers of multiplications, additions, data transfers, and twiddle factor evaluations or accesses to the look-up table, without a significant increase in the structural complexity compared to that of the existing 3-D vector radix FHT algorithm.     

一种按时间抽取的混合基实序列高效FFT算法

针对2N点实序列FFT的实现,分析了FFT运算的基本原理,并在基本原理的基础上介绍了一种按时间抽取的混合基FFT算法.此算法采用"包装"算法和基2-基4混合算法结合的方法进行运算.通过复杂度分析,显示了此算法与传统的单一基2或基4的FFT相比,大大减少了计算过程中所需的实加法的个数;当点数大于1024时,所需实乘法的个数也有所减少.这是一种实序列FFT的高效低复杂度算法.     

FPGA implementations of fast Fourier transforms for real-time signal and image processing

Applications based on the fast Fourier transform (FFT), such as signal and image processing, require high computational power, plus the ability to experiment with algorithms. Reconfigurable hardware devices in the form of field programmable gate arrays (FPGAs) have been proposed as a way of obtaining high performance at an economical price. However, users must program FPGAs at a very low level and have a detailed knowledge of the architecture of the device being used. They do not therefore facilitate easy development of, or experimentation with, signal/image processing algorithms. To try to reconcile the dual requirements of high performance and ease of development, the paper reports on the design and realisation of a high level framework for the implementation of 1D and 2D FFTs for real-time applications. A wide range of FFT algorithms, including radix-2, radix-4, split-radix and fast Hartley transform (FHT) have been implemented under a common framework in order to enable system designers to meet different system requirements. Results show that the parallel implementation of 2D FFT achieves linear speed-up and real-time performance for large matrix sizes. Finally, an FPGA-based parametrisable environment based on 2D FFT is presented as a solution for frequency-domain image filtering application.     

New radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) and radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) DIF FFT algorithms for 3-D DFT

In this paper, new three-dimensional (3-D) radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) and radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithms are developed and their implementation schemes discussed. The algorithms are developed by introducing the radix-2/4 and radix-2/8 approaches in the computation of the 3-D DFT using the Kronecker product and appropriate index mappings. The butterflies of the proposed algorithms are characterized by simple closed-form expressions facilitating easy software or hardware implementations of the algorithms. Comparisons between the proposed algorithms and the existing 3-D radix-(2/spl times/2/spl times/2) FFT algorithm are carried out showing that significant savings in terms of the number of arithmetic operations, data transfers, and twiddle factor evaluations or accesses to the lookup table can be achieved using the radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) DIF FFT algorithm over the radix-(2/spl times/2/spl times/2) FFT algorithm. It is also established that further savings can be achieved by using the radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) DIF FFT algorithm.     

Radix-2 FFT-pipeline architecture with reduced noise-to-signalratio

A radix-2 FFT-pipeline architecture has been developed which exhibits a two- to three-bit increase in accuracy for transform lengths N greater than 2¹⁰ if fixed-point arithmetic is utilised. The algorithm in use is a unification of the Cooley-Tukey radix-4 and radix-4+2 decompositions     

基于FPGA的专用信号处理器设计

用可编程门阵列(FPGA)实现了一个专用信号处理器,它以快速傅里叶变换(FFT)为核心工作单元,对四路零中频雷达回波依次进行去除直流分量、数据加窗、FFT、目标信号选大和相位参考信号检测等处理。各处理单元流水操作,保证了处理速度,提高了资源的利用效率。FFT算法为输入顺序输出位反序的D IT基2算法,采用递归结构实现,硬件共享设计节省了资源;同时,处理过程中采用块浮点算法,兼顾了定点的高速度与浮点的高精度;并对FFT结果进行了误差分析,给出了定点与块浮点两种算法时的均方误差上限。最后对整个设计进行了仿真验证,结果表明用FPGA实现专用信号处理器满足系统要求。     

AN IMPROVED DIGITAL-REVERSED PERMUTATION ALGORITHM FOR THE FAST FOURIER ANDHARTLEY TRANSFORMS

A more efficient permutation algorithm which has less computer operation and better structure is presented here for radix-2 FFT(FHT). It can fasten the FFT and FHT efficiently when N becomes large.     

MIMO协同中继系统中的最大似然合并解调算法

协同中继系统通过合并解调不同路径的信号副本,得到比非协同系统更优的误码性能。传统的合并解调算法将合并解调过程分开处理,性能较差。该文针对多输入多输出（MIMO）放大转发协同中继系统,基于最大似然（ML）准则,提出了在目的节点对来自源节点和中继节点的信号进行合并解调的新算法。该算法首先对来自源节点和中继节点的信号进行ML合并,然后采用传统的MIMO最大似然检测完成信号的解调。分析与仿真结果表明,与最大比合并（MRC）等算法相比,在不同调制方式和信道条件下,所提算法均获得了显著的性能增益,且高阶调制下的复杂度低。      

Fast decimation-in-time algorithms for a family of discrete sine and cosine transforms

Fast decimation-in-time (DIT) algorithms for the various discrete cosine transforms (DCT) and discrete sine transforms (DST) are systematically developed, based on a radix-2 factorization of the transformation matrix. The results indicate these to be attractive alternatives to existing algorithms in terms of computational complexity and structural simplicity.Supported, in part, by NSERC Grant #A3635.     

Fixed-point error analysis of two DCT algorithms

A fixed-point error analysis of two fast DCT algorithms proposed by Hou (1987) and Makhoul (1980) is presented. Expressions for error variances are derived and the results are compared with the simulation results. It is found that the simulation results and analysis results agree quite closely. This demonstrates the validity of the analysis. In addition, the two algorithms are compared in terms of their advantages and disadvantages     

FFT或FHT的一种改进的整序算法

本文提出一种适于基-2FFT或FHT的更为高效的整序算法,使以往算法的运算量、算法结构等性能都有明显改善,尤其当N较大时有很大优势,可以进一步提高FFT和FHT的运算效率。     

Fixed-point error analysis of discrete Wigner-Ville distribution

The Wigner-Ville distribution (WVD) has been a powerful signal processing tool for time-frequency signal analysis. Consequently, many algorithms have been proposed in the literature for computing the WVD in real-time applications. However, Boashash (1987) has proposed and showed that the evaluation of the analytic signal using the time-domain approach, and involving the Hilbert transformer, is the most efficient algorithm for real-time applications. A fixed-point error analysis of this algorithm has been carried out. The theoretical noise-to-signal ratio (NSR) is derived and verified through simulation. The results indicate that for this algorithm, the NSR increases by 0.5 bit/stage, whereas for the other algorithms, it increases by 1 bit/stage     

Analysis of LMS-Newton adaptive filtering algorithms with variableconvergence factor

An analysis of two LMS-Newton adaptive filtering algorithms with variable convergence factor is presented. The relations of these algorithms with the conventional recursive least-squares algorithm are first addressed. Their performance in stationary and nonstationary environments is then studied and closed-form formulas for the excess mean-square error (MSE) are derived. The paper deals, in addition, with the effects of roundoff errors for the case of fixed-point arithmetic. Specifically, closed-form formulas for the excess MSE caused by quantization are obtained. The paper concludes with experimental results that demonstrate the validity of the analysis presented     

Mixed-radix discrete cosine transform

Presents two new fast discrete cosine transform computation algorithms: a radix-3 and a radix-6 algorithm. These two new algorithms are superior to the conventional radix-3 algorithm as they (i) require less computational complexity in terms of the number of multiplications per point, (ii) provide a wider choice of the sequence length for which the DCT can be realized and, (iii) support the prime factor-decomposed computation algorithm to realize the 2^m3ⁿ-point DCT. Furthermore, a mixed-radix algorithm is also proposed such that an optimal performance can be achieved by applying the proposed radix-3 and radix-6 and the well-developed radix-2 decomposition techniques in a proper sequence     

Design and parallel computation of regularised fast Hartley transform

The paper describes the design and parallel computation of a regularised fast Hartley transform (FHT), to be used for computation of the discrete Fourier transform (DFT) of real-valued data. For the processing of such data, the FHT has attractions over the fast Fourier transform (FFT) in terms of reduced arithmetic operation counts and reduced memory requirement, whilst its bilateral property means it may be straightforwardly applied to both forward and inverse DFTs. A drawback, however, of conventional FHT algorithms lies in the loss of regularity arising from the need for two sizes of 'butterfly' for efficient fixed-radix implementations. A generic double butterfly is therefore developed for the radix-4 FHT which overcomes the problem in an elegant fashion. The result is a recursive single-butterfly solution, referred to as the regularised FHT, which lends itself naturally to parallelisation and to mapping onto a regular computational structure for implementation with algorithmically specialised hardware.     

An accurate error analysis model for fast Fourier transform

An error propagation model is proposed for the in-place decimation-in-time version of the radix-2 FFT algorithm. With the model, an accurate error expression and error variance for the computation of FFT are derived. This correspondence deals with fixed-point and block floating-point arithmetic. Simulation results agree closely with the theoretical predicted ones. We find that some roundoff errors at different stages correlate with each other. The density of correlations is closely associated with the round-off approach used in butterfly calculations