[PDF] A Pipelined FFT Architecture for Real-Valued Signals

View - Download A Pipelined FFT Architecture for Real-Valued Signals

Previous PDF

Next PDF

A Pipelined FFT Architecture for Real

Valued

Signals

Mario Garrido, Keshab. K. Parhi and Jesus Grajal

Journal Article

N.B.: When citing this work, cite the original article. ©2016 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any co pyrighted component of this work in other works must be obtained from the IEEE. Mario Garrido, Keshab. K. Parhi and Jesus Grajal, A Pipelined FFT Architecture for Real- Valued Signals, IEEE Transactions on Circuits and Systems Part 1, 2009. 56(12), pp.263 4 2643.
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS PART I: REGULAR PAPERS1

A Pipelined FFT Architecture for Real-Valued

Signals

Mario Garrido, Keshab. K. Parhi,Fellow, IEEE, and J. Grajal Abstract-This paper presents a new pipelined hardware architecture for the computation of the real-valued fast Fourier transform (RFFT). The proposed architecture takes advantage of the reduced number of operations of the RFFT with respect to the complex fast Fourier transform (CFFT), and requires less area while achieving higher throughput and lower latency. The architecture is based on a novel algorithm for the com- putation of the RFFT, which, contrary to previous approaches, presents a regular geometry suitable for the implementation of hardware structures. Moreover, the algorithm can be used for both the Decimation In Time (DIT) and Decimation In Frequency (DIF) decompositions of the RFFT and requires the lowest number of operations reported for radix 2. Finally, as in previous works, when calculating the RFFT the output samples are obtained in a different order. The problem of reordering these samples is solved in this paper and a pipelined circuit that performs this reordering is proposed. Index Terms-Fast Fourier Transform (FFT), Real-Valued Signals, Pipelined Architecture, Reordering Circuit, Decimation- in-Time, Decimation-in-Frequency, Memory Reduction

I. INTRODUCTIONT

HE fast Fourier transform (FFT) is one of the most important algorithms in the field of digital signal process- ing, used to efficiently compute the discrete Fourier transform (DFT). For the computation of the FFT, pipelined hardware architectures [1]-[9] are widely used because they offer high throughput and low latency as well as a reasonably low area and power consumption. This makes them attractive for a large variety of applications, specially when they present real-time requirements. Thus, in order to provide solutions to present and future applications, hardware designers keep improving the signal processing capabilities of pipelined architectures of the FFT. The FFT internally operates over complex numbers and previous works offer efficient designs for the computation of the FFT of complex input samples (CFFT). However, they are not optimized for the computation of the FFT of real input samples (RFFT). Indeed, when the input samples are real the spectrum of the FFT is symmetric [10] and approximately half of the operations are redundant [11]. The RFFT plays an important role in different real-time applications. In medical applications such as ECG (Electro- cardiography) [12] or EEG (Electroencephalography) [13], the power spectral density (PSD) of various real-valued signals Mario Garrido and J. Grajal are with the Department of Signal, Systems and Radiocommunications, Unversidad Polit

´ecnica de Madrid, 28040 Madrid,

Spain, e-mails: mgarrido@gmr.ssr.upm.es, jesus@gmr.ssr.upm.es Keshab K. Parhi is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA, e-mail: parhi@umn.eduhas to be estimated. This requires calculation of the RFFT repetitively on many overlapping windows of the signals, where a specialized hardware implementation can make use of a higher speed clock to meet real-time constraints. Moreover, in implantable or portable devices [12], [13], a dedicated hardware can save power consumption. On the other hand, the RFFT is a key element in technologies based on DMT (discrete multitone) modulation, such as ADSL (Asymetric Digital Subscriber Line) or VDSL (Very high bit-rate Digital Subscriber Line) [14], [15]. Nowadays, high signal process- ing capabilities are required for second-generation standards (ADSL2/2+ [16] and VDSL2 [17]). Moreover, DMT has been used at rates of 24 Gb/s in local area networks (LAN) [18]. Finally, very high performance is also necessary in digital wideband receivers [19], [20]. Currently, the RFFT has to be computed in real time over a dataflow of 2 GSamples/s [20]. Thus, in order to meet the increasing demand on real- time capabilities of new applications, much research has been carried out on pipelined architectures of the CFFT. On the other hand, for those applications with real input signals, a dedicated pipelined RFFT architecture can lead to savings in area and power consumption, while offering high signal processing capabilities. However, to the best of our knowledge no hardware-efficient pipelined architecture for the computa- tion of the RFFT based on the Cooley-Tukey algorithm [21] has been proposed yet. There exist only some pipelined architectures [22], [23] based on the Bruun algorithm [24]. However, the Bruun algorithm has not been widely adopted since it was demonstrated [25] that the noise is significantly higher than that in the Cooley-Tukey algorithm [21]. The lack of specific pipelined architectures for the RFFT is due to the fact that the specific algorithms proposed for the computation of the RFFT [11], [26]-[30], do not lead to regular geometries, which are necessary for designing pipelined architectures. These specific approaches describe programs based on removing the redundancies of the CFFT when the input is real, and can be used to efficiently compute the RFFT in a DSP (Digital Signal Processor) or in in-place architectures [31]. A memory-based or in-place architecture consists of a memory and a processing unit. The data are loaded, processed and stored again in the memory until all the operations of the algorithms are performed. This kind of architecture allows the design of circuits with low area and power consumption, but it is not suitable for real-time applications. There exist other techniques described in [32], [33], which take advantage of the CFFT to calculate the RFFT. On one hand, thedoubling algorithmuses the CFFT to compute IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS PART I: REGULAR PAPERS2 two RFFTs simultaneously. On the other hand, thepacking algorithmforms a complex sequence of lengthN=2taking the even and odd indexed samples of the real input sequence of lengthN, and calculates theN=2-point CFFT of the complex sequence. In these CFFT-based techniques, additional operations are necessary to obtain the final results from the outputs of the CFFT. The packing algorithm has been used to implement some in-place architectures [15], [34]. In these architectures the hardware of the CFFT can be reused for computing the post-processing stage. However, no pipelined architecture has been proposed, not only because some of the adders and multipliers saved in the CFFT need to be used for post-processing, but mainly because the samples need to be reordered before the post-processing stage [15], increasing the memory and complicating the control. Both in the specific algorithms for the computation of the RFFT and in the CFFT-based ones, the output samples are provided in different orders [27], which are different from the bit-reversal one of the CFFT [35]. The sorting of the outputs of the RFFT is also a problem not solved in the literature so far. In this work we propose the first pipelined architecture for the computation of the RFFT based on the Cooley- Tukey algorithm. It combines the advantages of the pipelined architectures with the reduction of operations achieved by the specific algorithms. This is possible due to the proposed algorithm for the computation of the RFFT which solves the irregularities of the RFFT. Moreover, this approach is valid for both Decimation In Time (DIT) and Decimation In Frequency (DIF) decompositions and is generalizable for any number of pointsN, which is power of2. Furthermore, the problem of the output order of the samples is solved and a pipelined circuit that performs the reordering is proposed. In the next section we briefly review the RFFT and the existing techniques to compute it. In Section III we develop the algorithm that allows the design of regular hardware architectures for the computation of the RFFT, and the novel proposed pipelined architecture is presented Section IV. Next, in Section V the architecture is evaluated and compared to previous approaches, and some conclusions are drawn in Section VI. Finally, the reordering of the output samples and the proposed solution are discussed in Appendix A.

II. THERFFT

TheN-point DFT of a sequencex[n]is defined as:

X[k] =N1X

n=0x[n]WnkN; k= 0;1;:::;N1(1) whereWnkN=ej2N nk. The RFFT considers the input sequence,x[n], to be a real sequence, i.e.,8n,x[n]2R. It is easy to demonstrate [10] that ifx[n]is real, then the outputX[Nk]is complex conjugate ofX[k]. Consequently, an RFFT can be considered a conventional FFT with the additional conditions:

Im(x[n]) = 0(2)

and X[Nk] =X[k](3)These two conditions that distinguish the CFFT and the RFFT do not lead, however, to a direct simplification of equation (1) for the RFFT, and the specific algorithms for the computation of the RFFT require complicated developments. Thus, other simpler techniques that use the CFFT to compute the RFFT are sometimes preferred. Next, these approaches are reviewed.

A. Computation of the RFFT using the CFFT

1) Direct use of the CFFT:The first idea when it is

necessary to compute an FFT over a real input signal is to use the CFFT. As the real numbers are a subset of the complex ones, the trivial solution is to set the imaginary part of the input to zero. Although this procedure does not make an efficient use of the resources, it is very simple and it is not necessary to modify the CFFT. Indeed, it is the solution adopted for many if not all real-time applications.

2) Doubling Algorithm:Another alternative is to take

advantage of the CFFT to simultaneously compute the FFT of two real signalsx1[n]andx2[n];n= 0;1;:::;N1 as it is explained in [32], [33]. This process requires to form the signaly[n] =x1[n] +jx2[n]and use an N-point CFFT to obtainY[k] =X1[k] +jX2[k]. It is important to notice that bothX1[k]andX2[k]are complex, so they cannot be obtained directly fromY[k]. Therefore,2(N1) additions are required to separate the outputs, in addition to the operations of the CFFT.

3) Packing Algorithm:Given a real signalx[m],m=

0;1;:::;M1it is also possible to compute the RFFT using

anM=2-point CFFT [32], [33]. This technique is sometimes calledpacking algorithmbecause it takes the odd and even indexed samples of the signal and form the complex signal y[n] =x[2n] +jx[2n+ 1],n= 0;1;:::;N1and

N=M=2. Then theN-point CFFT is applied to obtain

Y[k];k= 0;1;:::;N1. As in thedoubling algorithm,

2(N1)additions are required to separate the outputs of

the CFFT. Moreover, in thepacking algorithmit is necessary to include an additional stage to compute the outputs of the

RFFT, which requires4N1extra additions and4(N1)

multiplications. B. Specific Algorithms for the Computation of the RFFT The greater reduction in the number of operations is ob- tained by using the specific algorithms for the computation of the RFFT. Most of them are obtained from the CFFT by applying the properties of the RFFT in order to remove the redundant operations. The first proposed algorithms were de- fined for the DIT (Decimation In Time) decomposition of the FFT. The DIT FFT has the property that the samples at each intermediate stage can be computed using the conventional FFT [10]. Consequently, equation (3) can be applied at each stage, and only one half of the intermediate outputs must be calculated, whereas the rest can be obtained by conjugating those intermediate values. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS PART I: REGULAR PAPERS3 This is the basic idea of algorithms proposed for split- radix [11], [26], radix-2 [27], [30] and high radices [28]. These algorithms are, however, not valid for the DIF (Decimation In Frequency) decomposition of the FFT because it is not possible to apply the property (3) at each stage. On the other hand, it has been also demonstrated that it is possible to obtain the same savings for the DIF decomposition using an alternative algorithm [29] that makes use of linear-phase sequences. In general, the number of multiplications in all of these algorithms is reduced to half of that required for the CFFT, and the number of additions isN2less than half the additions of the CFFT. Likewise, only half of the memory is needed. Thus, there are only slight differences among all of them in the number of operations and in the order in which the computations are performed.

III. PROPOSEDALGORITHM FOR THECOMPUTATION OF

THERFFT

A. Basis of the algorithm

Figure 1 shows the flow graph of anN-point FFT for the case ofN= 16, radixr= 2, and decomposed according to the decimation in frequency (DIF) [10]. The graph is divided intologrN= 4stages and each of them consists of a set of butterflies and rotators. The numbers at the input and the output of the graph represent respectively the index of the input and output samples, whereas each number,, in between the stages indicates a rotation by: e j2N (4) If we consider that the inputs are complex, all the internal nodes and outputs of the graph are needed for the computation of the CFFT, and the regularity of the flow graph leads to efficient pipelined architectures [2]. On the other hand, if the inputs are real, it is possible to simplify the graph according to the properties of the RFFT, as explained next.

1.- The first simplification is to consider that in the real

FFTX[Nk] =X[k]. According to this,N=21

outputs of the FFT are redundant and can be removed. Most approaches [11], [27], [31] obtain either the frequencies with indexesk= [0;N=2]ork= [0;N=4][[N=2;3N=4]and, if necessary, calculate the rest of the frequencies by conjugating these results. However, considering thatk0=N=4k1for the indicesk;k0= 0;:::;N=41and using the property (3):

X[4k+ 3] =X[N4k3] =X[4k0+ 1](5)

leads to a more efficient architecture. Consequently, the set of frequenciesX[4k+ 3]can be obtained by conjugating frequenciesX[4k+1], as mentioned in [26] for the split-radix RFFT. According to Figure 1, samplesX[4k+3]are the last quarter of the outputs; so all the butterflies used exclusively to compute these samples may be removed, which are represented by the lower darkened region. The same concept can be applied to samplesX[8k+ 6], which can be computed by conjugating samplesX[8k+ 2].

Generalizing this idea, samplesX[2(4k+ 3)]can be

computed by conjugating the samplesX[2(4k+1)], whereFig. 1. Flow graph of a 16-point DIF FFT. The darkened regions and the

boxed components are considered in the simplifications of the new algorithm for the RFFT. k= 0;:::;N=(42)1, for all= 0;:::;log2N2. Thus, all the darkened regions in Figure 1 can be removed and only

N=21outputs of the FFT need to be computed.

2.- The second simplification refers to the fact that

Im(x[n]) = 0. According to this, every piece of data is real until it is rotated for the first time. In Figure 1, all the additions performed before the data reach the boxed components are real and, thus, the number of additions in that area is halved with respect to the CFFT. Once the data reach the first rotations, the data are necessarily complex until the end of the FFT.

3.- One further simplification of the boxed components may

be carried out. Let"s assume that the first stage of the FFT iss= 1and the last one iss=nlogrN, andXs are the outputs of stages. According to this and Figure 1, in the second stage it is not necessary to compute the data X

2[i+ 3N=4],i= 0;:::;N=41, and samplesX2[i+N=2]

are calculated as: X

2[i+N=2] =X1[i+N=2]ej2N

i+ +X1[i+ 3N=4]ej2N (i+N=4)(6) This calculation requires 2 rotations and 1 addition. How- ever, expanding the expression and taking into account that bothX1[i+N=2]andX1[i+3N=4]are real samples, we can obtain: X

2[i+N=2] =fX1[i+N=2]jX1[i+ 3N=4]g ej2N

i (7) The resulting expression only requires one rotation and no additions becauseX1[i+N=2]andX1[i+3N=4]are real and rotations by1,1,jandjare trivial, taking into account that they can be calculated by interchanging the real and imaginary

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS PART I: REGULAR PAPERS4Fig. 2. Simplified flow graph of a 16-point FFT for real input samples,

before a regular structure is obtained. parts and/or changing the sign of the data. This simplification can be extended to all the boxed components, which reduces even more the number of rotators and adders of the FFT. Figure 2 represents the flow graph of the RFFT once the explained simplifications have been carried out. All the data previous to the boxed components are real, and onlyquotesdbs_dbs14.pdfusesText_20

[PDF] complex numbers input fft

[PDF] complex time domain signal

[PDF] complexity of lu factorization

[PDF] composite can be classified based on

[PDF] composite materials can be classified based on

[PDF] composites can be classified based on

[PDF] composition géographie la france en ville

[PDF] compound statement example

[PDF] compound statement in symbolic form

[PDF] compound statement symbols

[PDF] compréhension écrite la nourriture

[PDF] comprehensive list of linux commands

[PDF] comprendre le langage corporel

[PDF] comprendre le langage corporel des chiens

[PDF] comprendre le langage corporel des femmes