# An Efficient Full-Band Sliding DFT Spectrum Analyzer

In this blog I present two computationally efficient full-band discrete Fourier transform (DFT) networks that compute the 0th bin and all the positive-frequency bin outputs for an *N*-point DFT in real-time on a sample-by-sample basis.

**An Even- N Spectrum Analyzer**

The full-band sliding DFT (SDFT) spectrum analyzer network, where the DFT size *N* is an even integer, is shown in Figure 1(a). The *x*[*n*] input sequence is restricted to be real-only valued samples. Notice that the only real parts of the delay elements’ complex-valued outputs are used to compute the feedback *P*[*n*] samples.

The Figure 1(a) network’s complex coefficients are defined by $e^{j2{\pi}k/N}$ where integer *k* defines the DFT bin index and is in the range 0 ≤ *k* ≤ *N*/2. This even-*N* network has *N*/2+1 parallel paths that compute the complex-valued *X*_{0}, *X*_{1}, *X*_{2},..., *X*_{N}_{/2} DFT bin output samples. The multiply by 1/2 can be implemented with a simple binary right shift by one bit.

The Figure 1(a) even-*N* network was inspired by the Figure 4 network in Reference [1]. However, for real-valued input samples I’ve simplified the Reference [1] network (which has *N* parallel paths) and reduced its computational complexity to develop the above proposed Figure 1(a) network.

**An Odd- N Spectrum Analyzer**

To compute real-time positive-frequency odd-*N*-point DFT spectral samples we use the network shown in Figure 1(b). This odd-*N* network has (*N*+1)/2 parallel paths that compute the *X*_{0}, *X*_{1}, *X*_{2},..., *X*_{(N-1)/2} DFT bin output samples. Again the *x*[*n*] input sequence is restricted to be real-only valued samples. The Figure 1(b) network’s complex coefficients are defined by $e^{j2{\pi}k/N}$ where integer *k* is 0 ≤ *k* ≤ (*N*-1)/2.

Two surprising properties of both Figure 1 networks are: 1) although they use recursive complex multiplications the networks are guaranteed stable, and 2) the networks compute sliding DFT samples without a comb delay-line section required by traditional sliding DFT networks! (The Reference [1] network also has those two noteworthy properties.)

**Implementation**

Both Figure 1 networks are implemented as follows:

1) Set the outputs of the delay elements and the *P*[0] feedback sample to zero.

2) Accept the first *x*[0] input sample and compute the *X** _{k}*[0] output samples for each parallel path.

3) Shift the data through the delay elements and compute the *P*[1] feedback sample.

4) Accept the second input sample and compute the *X** _{k}*[1] output samples for each parallel path.

5) Shift the data through the delay elements and compute the new *P*[2] feedback sample.

6) And so on.

**Computational Complexity Comparison**

In case you’re interested in the computational workload of the Reference [1] network and our two proposed Figure 1 networks, have a look at Table 1.

**Conclusion**

I presented computationally efficient full-band sliding DFT networks that compute the 0th bin and all the positive-frequency DFT bin outputs for both even- and odd-*N*-point DFTs in real-time on a sample-by-sample basis. (No taxpayer money was used and no animals were injured in the creation of this blog.)

**References**

[1] Z. Kollar, F. Plesnik, and S. Trumpf, “Observer-Based Recursive Sliding Discrete Fourier Transform,” IEEE Signal Proc. Mag., Vol. 35, No. 6, pp. 100-106, Nov. 2018.

- Comments
- Write a Comment Select to add a comment

I notice this is posted on April 1. Am I foolish to read it?

John P

Hi JProvidenza.

Ah ha. Such an interesting question. The answer is no, you would not be foolish to read it. (Perhaps I should have paid more attention to the date and posted this blog on April 2nd.)

Rick -

I couldn't resist the comment - it was too sweet a date!

Thanks for all your great posts. I have a couple of your books that I've used for study - my background is not DSP, but it's great to stretch my brain on topics I was not introduced to in college decades ago.

John P

Rick -

Could you add a little info on how to interpret the output?

Thanks!

John P

Hi JProvidenza.

Well, ...the traditional
sliding DFT, shown in the following diagram, is used to compute the real-time
(one output sample for each new input sample) *k*th bin output of a *N*-point
DFT. (The *X*_*k*[*n*] output is the *k*th bin output of a *N*-point
DFT for the current input sample and the previous *N*-1 input samples.) The
typical application of the traditional sliding DFT is to detect the presence,
or absence, of spectral energy centered at the *k*th bin of an *N*-point
DFT in real time.

If you wanted to simultaneously
compute the *k* = 3, *k* = 5, and *k* = 7 bins’ outputs you
would use the following network.

For real-valued *x*[*n*]
input sequences, my blog’s Figure 1 networks are used to compute the 0th bin
and all the positive-frequency bin outputs of an *N*-point DFT in
real-time (on a sample-by-sample basis). Notice in my blog’s Figure 1 that, unlike the traditional sliding DFT, no *N*-length delay line stage is needed.

I hope what I've written here makes sense.

Hi Rick,

I am not sure if my question is related to this exact article.

Could the sliding DFT be used to extract different bins of an OFDM signal which is not really like a sine wave. Also is it applicable on parallel samples?

Regards,

Tushar

Hello tushar_tyagi90

This blog presents an efficient way to compute the N complex output bin samples of an N-point DFT in real time. By “real time” I mean that that for each data input sample all N DFT bin complex spectral sample values are computed. The output samples of this scheme are not valid until the Nth input sample has been applied to the network. [The traditional DFT (or radix-2 FFT) provides outputs only for every N input samples--it’s not “real-time”.] The networks in this blog's Figure 1 are only valid for real-valued input samples.

A sliding DFT network, on the other hand, computes a ** single** complex output bin spectral sample of an N-point DFT in real time (one complex output spectral sample for each input sample).

I have no experience in OFDM processing, but if your OFDM processing requires you to compute all N output spectral samples of an N-point DFT in real time then one of the networks in this blog’s Figure 1 should achieve your goal.

If your OFDM processing requires you to compute, say 8, real time N-point DFT spectral samples (where N is greater than 8) then you merely need to implement 8 sliding DFT networks. That is, one comb section driving 8 separate resonator sections.

I must tell you, “traditional” sliding DFT networks can experience long-term stability problems. Several guaranteed-stable sliding DFT networks have been proposed in the literature but they’re more computationally intensive than the traditional sliding DFT. Last year I developed a guaranteed-stable sliding DFT network that is significantly more computationally efficient than the previously proposed guaranteed-stable sliding DFT networks.

My “new and improved” guaranteed-stable sliding DFT is described at:

"Improvements to the Sliding DFT Algorithm", DSP Tips & Tricks column, IEEE Signal Processing Magazine, Vol. 38, No. 4, July 2021.

I intend to write a blog at this dsprelated.com web site describing my new and improved sliding DFT network as soon as I have the time.

tushar_tyagi90, if you have any further questions for me please let me know.

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.