Blogs

An Efficient Full-Band Sliding DFT Spectrum Analyzer

Rick LyonsApril 1, 20215 comments

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.

This article is available in PDF format for easy printing

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 ≤ kN/2. This even-N network has N/2+1 parallel paths that compute the complex-valued X0, X1, X2,..., XN/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 X0, X1, X2,..., 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 Xk[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 Xk[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.


[ - ]
Comment by JProvidenzaApril 9, 2021

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


John P

[ - ]
Comment by Rick LyonsApril 9, 2021

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

[ - ]
Comment by JProvidenzaApril 11, 2021

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

[ - ]
Comment by JProvidenzaApril 13, 2021

Rick -


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


Thanks!

John P

[ - ]
Comment by Rick LyonsApril 14, 2021

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) kth bin output of a N-point DFT. (The X_k[n] output is the kth 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 kth bin of an N-point DFT in real time.

sdft-i_99879.jpg

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

sdft-ii_65965.jpg

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.

Sign up

I agree with the terms of use and privacy policy.

Try our occasional but popular newsletter. VERY easy to unsubscribe.
or Sign in