# 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.

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.