## Abstract

The conventional method for spectrum analysis is the discrete Fourier transform (DFT), usually implemented using a fast Fourier transform (FFT) algorithm. However, certain applications require an online spectrum analysis only on a subset of M frequencies of an N-point DFT (M<N). In such cases, the use of single-bin sliding DFT (Sb-SDFT) is preferred over the direct application of FFT. The purpose of this chapter is to provide a concise overview of the Sb-SDFT algorithms, analyze their performance, and highlight advantages and limitations. Finally, a technique to mitigate the spectral leakage effect, which arises when using the Sb-SDFT in nonstationary conditions, is presented.

### Keywords

- discrete Fourier transform
- spectral leakage
- digital signal processing
- Cramér-Rao lower bound
- total vector error

## 1. Introduction

The estimation of frequency, amplitude and phase of single-frequency and multifrequency signals has applications in many fields of engineering. In general, estimation methods are based on Fourier analysis or parametric modeling. The advantage of Fourier-based methods is their computational efficiency, compared with the mathematical complexity of the parameters-based algorithms, which demand a high amount of computational resources. The standard method for Fourier analysis in digital signal processing is the discrete Fourier transform (DFT). For some real-time applications, the direct application of the conventional DFT may result in an excessive computational cost. However, certain applications require an online spectrum analysis only over a subset of

The chapter is organized as follows: Section 2 presents a brief review of Sb-SDFT. Section 3 evaluates and compares the four selected Sb-SDFT algorithms in diverse operational conditions, identifying the similarities between them. In order to mitigate the inaccuracies resulting from the spectral leakage effect, a scheme for coherent sampling based on VSPT is introduced in Section 4. Altogether a unified model is also presented to generalize this scheme to all Sb-SDFT along with simulation results. Finally, the conclusions of this chapter are drawn in Section 5.

## 2. Single-bin sliding discrete Fourier transform

The discrete Fourier transform (DFT) is a numerical approximation of the theoretical Fourier transform (FT) of a continuous and infinite duration signal. It represents the most common tool for engineers to extract the frequency content of a finite and discrete signal sequence, obtained from the periodic sampling of a continuous wave form in time domain.

Let us consider a continuous time signal

where _{,} and * n* is the time domain index [1].

If Eq. (1) is not properly designed and implemented, the DFT calculation in real-time might represent a considerable bottleneck when developing a DFT-based estimation algorithm, in terms of both measurement reporting latencies and achievable reporting rates. In this respect, in order to improve both latencies and throughput, several efficient techniques to compute the DFT spectrum have been proposed in literature, which can be classified as nonrecursive and recursive algorithms. Among the nonrecursive class, the fast Fourier transform (FFT) algorithm is extensively used for harmonic analysis over an extended portion of the spectrum. When, on the other hand, only a subset of the overall DFT spectrum is necessary to accomplish the desired estimate, the so-called single-bin sliding DFT (Sb-SDFT) turns out to be very effective.

The DFT can also be computed by recursive algorithms which are characterized by a minor number of operations to calculate a single DFT bin. Regardless of this advantage with respect to the class of nonrecursive algorithms, the performances of the two categories usually are not the same. Especially, most of the algorithms in the recursive category suffers of errors due to either the approximations made to perform the recursive update or the accumulation of the quantization errors related to a finite word-length precision [2, 3].

In what follows, four of the most efficient techniques to compute a portion of the DFT spectrum, namely the sliding discrete Fourier transform (SDFT), the sliding Goertzel transform (SGT), the Douglas and Soh algorithm (D&S), and the modulated sliding discrete Fourier transform (mSDFT) will be presented and described.

### 2.1. Sliding discrete Fourier transform

A very effective Sb-SDFT method for sample-by-sample DFT bin computation is the so-called sliding discrete Fourier transform (SDFT) technique [4]. Starting from Eq. (1), the DFT can be potentially updated every time-step * n*, based on the most recent set of samples within a sliding window

*bin of an*-

Based on this property, the SDFT can be recursively implemented to calculate Eq. (1) for a desired

where

where * k*th component as its amplitude (

SDFT is computationally efficient, as it only requires one (complex) multiplication and two additions per time instant. Nevertheless, the implementation of Eq. (2) as an infinite impulse response (IIR) filter in a system with finite word-length precision brings about a rounding error in the implementation of the

where * k*th bin of the SDFT is

The stable SDFT algorithm given by Eq. (5) leads to the filter structure shown in Figure 1(b). This structure is basically an IIR filter that comprises a comb filter followed by a complex resonator. The comb filter makes the transient response

### 2.2. Sliding Goertzel transform

The number of multiplications required in the SDFT can be reduced by creating a new pole/zero pair in its

The transfer function represented by Eq. (7) is commonly known as the sliding Goertzel transform (SGT). Because the poles are placed on the * z* domain unit circle, the SGT implementation is also potentially unstable. Once more a damping factor

*can be used in Eq. (7), to move the singularities inside the unit circle and to ensure the system stability.*r

This method can be implemented by the following pair of finite difference equations:

where

### 2.3. Douglas and Soh algorithm

The implementation of a SDFT or SGT requires a damping factor to guarantee the algorithm stability. The trade-off for the system stability is that the calculated value is no longer exactly equal to the * k*th-bin of an

*th time instant.*N

This technique is implemented by the following pair of finite difference equations:

The algorithm described by Eq. (9) will be referred to as the Douglas and Soh algorithm (D&S). The filter implementation of Eq. (9), shown in Figure 2(b), requires two multiplications and two additions as well as the control logics to determine when * n* mod

### 2.4. Modulated sliding discrete Fourier transform

There is an alternative way of avoiding the reduction in accuracy generated by the damping factor, without compromising stability. SDFT implementation in Eq. (2) is marginally stable, however, for the particular case of

The absence of the

where

If multiple DFT frequency bins are to be computed, the mSDFT in Eq. (11) requires a comb filter for each frequency bin. On the other hand, given the periodicity of

Whenever multiple DFT frequency bins are to be computed, Eq. (12) becomes a more efficient approach as only one comb filter is needed (Figure 3(b)).

## 3. Performance comparison

This section discusses the key features of each of the Sb-SDFT that were presented in Section 2. The aim of this analysis is to find underlying similarities and differences between these methods. To this end, a study on statistical efficiency and accuracy is presented in the following subsections. Finally, the section ends with a discussion over the limitations and inaccuracies of the Sb-SDFT inherited by every DFT-based method.

### 3.1. Statistical efficiency

It is common knowledge that the statistical efficiency and noise performance of estimators is determined by comparison with the Cramer-Rao lower bound (CRLB). The CRLB deals with the estimation of the quantities of interest from a given finite set of measurements that are noise corrupted. It assumes that the parameters are unknown but deterministic, and provides a lower bound on the variance of any unbiased estimation. The CRLB is useful because it provides a way to compare the performance of unbiased estimators. Furthermore, if the performance of a given estimator is equal to the CRLB, the estimator is a minimum variance unbiased (MVU) estimator [10].

Computer simulations have been performed to evaluate the performance of the SDFT, the SGT, the mSDFT and D&S algorithm for a single real sinusoid polluted with white Gaussian noise:

where * n* is the time domain index,

*] is a zero-mean white Gaussian noise of variance*n

Parameters were assigned to

Figure 4(a) and (b) shows the variance in the estimate of * Â* computed by the mSDFT remains on CRLB curve, so its performance corresponds to an MVU estimator.

This test was repeated for

The effect of the damping factor on the

Finally, the * N* at SNR = 30 dB are illustrated in Figure 4(d). As expected,

*increase, that is, the length of the sliding window reduces the variance of*N

*in the four methods. This is mainly because the estimations are computed in a larger sliding time window, that is, more samples are used for the estimation.*Â

### 3.2. Accuracy analysis

In this section, the accuracy of the Sb-SDFT methods on the estimation of a single-frequency signal, both in steady-state and dynamics conditions, is analyzed through simulations. The adopted accuracy index is the so-called total vector error (TVE) that combines the effect of magnitude, angle and time synchronization errors on the desired component estimation accuracy. The TVE is defined in the Standard IEEE C37.118.1-2011 [11] as

where

#### 3.2.1. Steady-state condition

At first, the analysis is assessed in steady-state conditions assuming an input signal equal to Eq. (13). Parameters were assigned to

#### 3.2.2. Dynamic condition

The accuracy under dynamic condition of the SDFT, the SGT, the mSDFT and D&S algorithm are evaluated through multiple simulations under the effect of various transient disturbances. The comparison is performed by means of the following test signal:

where

First, the step response of the Sb-SDFT estimators is evaluated. For this purpose, the parameters of Eq. (16) are set to: * Â*) and TVE values as a function of time when the amplitude step occurs in

*[*x

*]. Ignoring small differences, related to the damping factor effect, the dynamic response during the transient is the same for all the algorithms. This transient has a duration that is equal to the length of the sliding window for all the Sb-SDFT. After the transient, the TVE values provided by the Sb-SDFT estimators are equal to the steady-state values shown in Figure 5(e). Further, simulation results (not reported here for the sake of brevity) confirm that the TVE value in steady state, due to an amplitude step, is the same regardless of the value of*n

The accuracy of the considered estimators is analyzed in Figure 6(b), assuming that the waveform * x*[

*] is subjected to linear variation of its amplitude. Therefore, the parameters of Eq. (16) were adjusted as follows:*n

The effect of a modulating signal on the estimation accuracy is analyzed in Figure 6(c). Hence, the parameters of Eq. (16) were adjusted as follows: * Â*) and TVE values as a function of time when the amplitude modulation of 10% with a frequency of 1 Hz occurs in

*[*x

*]. As expected, the dynamic behavior displayed by the Sb-SDFT estimators is similar, with the mSDFT the most accurate of the reviewed algorithms. The curves in Figure 7(b) show the worst case TVE values returned by the four considered estimators as a function of*n

Finally, the influence of a simple static off-nominal frequency offset on the Sb-SDFT estimators’ performance is analyzed in Figure 7(d). The figure shows the maximum TVE values, in steady state, when the signal (Eq. 16) phase varies as a function of the off-nominal frequency offset

The similarities between the Sb-SDFT algorithms found through Figures 6 and 7 are explained by the fact that all implementations of this type of algorithms result from applying Fourier properties and mathematical operations to standard DFT definition (Eq. 1).

### 3.3. Sb-SDFT limitations

The direct application of Sb-SDFT may lead to inaccuracies due to aliasing and spectral leakage, common pitfalls inherited by every DFT-based method. Aliasing is generally corrected by employing anti-aliasing filters or increasing the sampling frequency to a value that satisfies the Nyquist sampling criterion. Instead, when the sampling is not synchronized with the signal under analysis, the DFT is computed over a noninteger number of cycles of the input signal which leads to the spectral leakage phenomenon [1]. Spectral leakage is typically reduced (not eliminated) by selection of the proper nonrectangular time domain windowing functions, to weigh the sequence data at a fixed sampling frequency [12]. This process increases the computational complexity and does not take advantage of the recursive nature of Sb-SDFT methods. Otherwise, spectral leakage can be avoided entirely by ensuring that sequence of samples is equal to an integer number of periods of the input signal [13].

## 4. Coherent sampling approach

In order to avoid the spectral leakage phenomenon, the sequence of samples within a sliding window of a Sb-SDFT must be equal to an integer number of fundamental periods of the input signal. An integer number of periods will be sampled if and only if the coherence criterion holds:

where * N* is the sampled sequence length and

*is an integer number. This is equivalent to ensuring that an integer number*m

*of sine periods is present in the data sample of length*m

*, and in that case there is no spectral leakage. If Eq. (17) holds,*N

A variable sampling period approach, named variable sampling period technique (VSPT), was developed by the authors to design synchronization methods that maintain a coherent sampling with the input signal fundamental frequency [14]. This technique has recently been adapted to dynamically adjust the sampling frequency in a harmonic measurement method based on mSDFT [15]. In Ref. [16], the VSPT is generalized so as to be used with any Sb-SDFT algorithm.

In this section, the technique of variable sampling period is briefly described, and a unified small-signal model, which allows to use the VSPT with any Sb-SDFT, is also presented.

### 4.1. Variable sampling period technique

VSPT allows to adapt the sampling frequency to be * N* times the fundamental frequency of a given input signal. This technique has proven to be efficient both in three-phase and in single-phase applications yielding a robust synchronization mechanism, whose effectiveness has been tested under different conditions and scenarios [14, 17].

Figure 8(a) illustrates the basic VSPT scheme for single-phase implementation, where the input signal is sampled and the input phase

The method achieves a null phase error (

### 4.2. Unified small-signal model

VSPT allows to adapt the sampling rate to a multiple of the fundamental frequency of a given input signal, so the coherence criterion holds, thereby preventing the DFT’s shortcomings when is used to analyze nonstationary signals. An error signal, related to the phase difference between the fundamental component of the input signal and the reference phase, is needed to adapt the sampling period. Based on this, phase error is feasible to develop a closed-loop control to synchronize the sampling period.

As mentioned in Section 3, when * k*th-bin of an

*-points DFT. Based on this concept, Figure 8(b) shows a phase error estimation scheme that employs an Sb-SDFT algorithm, which allows to estimate the phase difference between the fundamental component of the input signal and the reference phase. This scheme obtains the phase error signal from three basic operations, first an Sb-SDFT algorithm with*N

*-points DFT, from a given input sequence of samples (*N

*[*x

*]). Then the phase of the input signal (*n

Since all the Sb-SDFT methods are derived from Eq. (1), for small-signal condition, they are mathematically equivalent, and the system phase error (

### 4.3. Validation

The specifications and requirements to be met by the controller (_{c}(* z*)) are determined by the application. Several applications require zero phase error and frequency synchronization for normal operation. In these cases, the controller must be proportional integral to achieve zero phase error in steady state; the resulting system being a type II system.

Then the transfer function for the controller in the * z* domain is

As an example of design,

The estimations obtained by the Sb-SDFT algorithms with coherent sampling supplied by the VSPT, in situations where the input signal frequency deviates from its nominal value, are evaluated in two possible scenarios. The first simulation analyzes the effect of a frequency step of −0.5 Hz on the performance of the proposed method. Hence, the parameters of Eq. (16) were adjusted as follows:

To complete the evaluation of the accuracy of coherent sampling achieved by the VSPT, the influence of a simple static off-nominal frequency offset on the Sb-SDFT estimators performance is analyzed in Figure 9(b). The figure shows the maximum TVE values, in steady state, when fundamental frequency of Eq. (16) varies as a function of the off-nominal frequency offset * N*, and in that case, the Sb-SDFT avoids the spectral leakage phenomenon. Therefore, compared with the results shown in Figure 7(d), the TVE values do not worsen with

## 5. Conclusions

In this work, a comparative study of four Sb-SDFT algorithms is conducted. The comparison includes filter structure, stability, statistical efficiency, accuracy analysis, dynamic behavior and implementation issues on finite word-length precision systems limitations. Based on theoretical studies as well as on simulations, it is deducted that all reviewed Sb-SDFT techniques are equivalent, primarily due to the fact that they are derived from the traditional DFT, therefore in various applications can be applied indistinctly.

It proves that SDFT and SGT have identical performances, in regard to disturbance rejection and precision on spectral estimation. Both of these techniques are used extensively due to their straightforward implementation, although the two have an error in accuracy due to the use of a damping factor. For applications requiring greater precision, this error can be reduced by using the D&S algorithm. On the other hand, it can be eliminated by using mSDFT due to the absence of damping factor, resulting in better performance. The results of the study have shown that mSDFT is the best option when it comes to precision and noise rejection.

The direct application of a Sb-SDFT may lead to inaccuracies due to the spectral leakage phenomenon, common pitfall inherited by every DFT-based method. Spectral leakage arises when the sampling process is not synchronized with the fundamental tone of the signal under analysis and the DFT is computed over a noninteger number of cycles of the input signal. In this sense, a unified small-signal system model is presented, which can be used to design a generic adaptive frequency loop that is based on a variable sampling period technique. The VSPT allows to obtain a sampling frequency coherent with the fundamental frequency of the analyzed signal, avoiding the error introduced by the spectral leakage phenomenon.

## References

- 1.
Oppenheim A and Schafer R. Discrete-time Signal Processing . Prentice-Hall Signal Processing Series. Pearson, Upper Saddle River, New Jersey, US, 2009.ISBN: 9780131988422 . - 2.
Kim JH and Chang TG. “Analytic derivation of the finite wordlength effect of the twiddle factors in recursive implementation of the sliding-DFT”. In: IEEE Transactions on Signal Processing 48.5, Piscataway, New Jersey, US, (May 2000), pp. 1485–1488.ISSN : 1053-587X.DOI : 10.1109/78.839998. - 3.
Darwish HA and Fikri M. “Practical Considerations for Recursive DFT Implementation in Numerical Relays”. In: IEEE Transactions on Power Delivery 22.1, Piscataway, New Jersey, US, (Jan. 2007), pp. 42–49.ISSN : 0885–8977.DOI : 10.1109/TPWRD.2006.874642. - 4.
Lyons R. “The Sliding DFT”. In: IEEE Signal Processing Magazine 20.2 Piscataway, New Jersey, US, (Mar. 2003), pp. 74–80.ISSN : 1053–5888.DOI : 10.1109/MSP.2003.1184347. - 5.
Hartley R and Welles K. “Recursive Computation of the Fourier Transform”. In: Circuits and Systems, 1990, IEEE International Symposium on . Piscataway, New Jersey, US, (May 1990), pp. 1792–1795 vol.3.DOI : 10.1109/ISCAS. 1990.111983. - 6.
Chicharo JF and Kilani MT. “A sliding Goertzel algorithm”. In: Signal Processing 52.3 Piscataway, New Jersey, US, (1996), pp. 283–297.ISSN : 0165–1684.DOI : http://dx.doi.org/10.1016/0165-1684(96)00066-7. - 7.
Lyons RG. Streamlining Digital Signal Processing . Ed. by Lyons RG. Hoboken, NJ, USA: John Wiley & Sons, Inc. (June 2012).ISBN : 9781118316948.DOI : 10.1002/9781118316948. - 8.
Douglas SC and Soh JK. “A numerically-stable sliding-window estimator and its application to adaptive filters”. In: Conference Record of the Thirty-First Asilomar Conference on Signals, Systems & Computers, Piscataway, New Jersey, US, 1997 . Vol. 1. (Nov. 1997), pp. 111–115.DOI : 10.1109/ACSSC.1997.680039. - 9.
Duda K. “Accurate, Guaranteed Stable, Sliding Discrete Fourier Transform”. In: IEEE Signal Processing Magazine November Piscataway, New Jersey, US, (Nov. 2010), pp. 124–127.ISSN : 1053–5888.DOI : 10.1109/MSP.2010.938088. - 10.
Kay SM. Fundamentals of Statistical Signal Processing: Estimation Theory. Prentice-Hall, Inc., Upper Saddle River, New Jersey, US, 1993. ISBN : 0-13-345711-7. - 11.
“IEEE Standard for Synchrophasor Measurements for Power Systems”. In: IEEE Std C37.118.1-2011 (Revision of IEEE Std C37.118-2005) Piscataway, New Jersey, US, (Dec. 2011), pp. 1–61.DOI : 10.1109/IEEESTD.2011.6111219. - 12.
Lyons RG. Understanding Digital Signal Processing . 3rd ed. Pearson, Upper Saddle River, New Jersey, US, 2010.ISBN : 9780137028528. - 13.
Manolakis D and Ingle V. Applied Digital Signal Processing: Theory and Practice . Cambridge University Press, Shaftesbury Road, Cambridge CB2 8BS, UK, 2011.ISBN : 9781139495738. - 14.
Carugati I, Maestri S, Donato PG, Carrica D, and Benedetti M. “Variable Sampling Period Filter PLL for Distorted Three-Phase Systems”. In: IEEE Transactions on Power Electronics 27.1 Piscataway, New Jersey, US, (Jan. 2012), pp. 321–330.ISSN : 0885–8993.DOI : 10.1109/TPEL.2011.2149542. - 15.
Orallo CM, Carugati I, Maestri S, Donato PG, Carrica D, and Benedetti M. “Harmonics Measurement With a Modulated Sliding Discrete Fourier Transform Algorithm”. In: IEEE Transactions on Instrumentation and Measurement 63.4 Piscataway, New Jersey, US, (Apr. 2014), pp. 781–793.ISSN : 0018–9456.DOI : 10.1109/TIM.2013.2287801. - 16.
Orallo CM, Carugati I, Donato PG, and Maestri S. “Study on Single-bin Sliding DFT algorithms: Comparison, stability issues and frequency adaptivity”. In: Measurement 69, Radarweg 29, 1043 NX Amsterdam, The Netherlands, (2015), pp. 9–19.ISSN : 0263-2241.DOI : 10.1016/j.measurement.2015.03.011. - 17.
Carugati I, Donato P, Maestri S, Carrica D, and Benedetti M. “Frequency Adaptive PLL for Polluted Single-Phase Grids”. In: IEEE Transactions on Power Electronics 27.5 Piscataway, New Jersey, US, (May 2012), pp. 2396–2404.ISSN : 0885-8993.DOI : 10.1109/TPEL.2011.2172000.