6

I am trying to understand the periodicity of the DFT. How can this property (both in time and frequency domain) be used and can be helpful while developing on a DSP?

It would be good to see some source code or pseudo code, in MATLAB preferably, where this property is exploited/demonstrated.

Peter K.
  • 25,714
  • 9
  • 46
  • 91
gpuguy
  • 1,370
  • 8
  • 17
  • 32
  • As you say right up front, what you really want is MATLAB code. This is definitely off-topic for dsp.SE. If you want to know why the DFT is periodic, then that would be a reasonable question to ask. – Dilip Sarwate Apr 02 '13 at 13:45

2 Answers2

4

If the expression that defines the DFT is evaluated for all integers $k$ instead of just for $k = 0, \dots, N-1$ , then the resulting infinite sequence is a periodic extension of the DFT, periodic with period $N$.

The periodicity can be shown directly from the definition:

$$ X_{k+N} \stackrel{\mathrm{def}}{=} \ \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} (k+N) n} = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} k n} \underbrace{e^{-2 \pi i n}}_{1} = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} k n} = X_k.$$

Similarly, it can be shown that the IDFT formula leads to a periodic extension.

Source: Wikipedia.

While the periodic property of DFT isn't very widely utilized, it often causes aliasing problems.

Source: http://www.dspguide.com/ch10/3.htm

Peter K.
  • 25,714
  • 9
  • 46
  • 91
Naresh
  • 748
  • 4
  • 20
0

In the time domain, the DFT is periodic by definition. While DFT stands for Discrete Fourier Transform, the operation is in fact a discrete fourier series. The signal to be analyzed is assumed to be periodic in the lenght of the signal. This periodic signal is decomposed into a series of periodic sequences. The DFT frequency bins are located at f = 1/T and its integer multiples, where T is the duration of the signal to be analyzed.

In the frequency domain, the DFT is periodic because the time domain signal being analyzed is sampled. Recall that any periodic sequence cannot be uniquely represented for frequencies above fs/2 where fs is the sampling frequency of the sequence (also known as the nyquist frequency). Above fs/2 all signal energy is reflected back into the frequency range 0-fs/2. Between fs/2 and fs, the reflection is in reverse order which gives rise to a DFT period equal to fs.

user2718
  • 2,188
  • 11
  • 10
  • 0down votefavorite

    "I am trying to understand the periodicity of the DFT." ... and this gets a down vote! Go figure.

     – user2718 Apr 03 '13 at 11:32
  • I didn't downvote your answer, but feel that the downvote is perfectly understandable. If someone is wanting to understand the periodicity of the DFT, saying that "the DFT is periodic by definition" is like a mother answering a child's "Why?" by "Because I say so." What is it in the definition of the DFT that gives it the property of periodicity since the typical definition does not make any mention of periodicity, though it is sometimes discussed right below the definition in a section called "Properties of the DFT"? – Dilip Sarwate Apr 03 '13 at 12:17
  • @Dilip You didn't understand my answer. The reason the DFT is periodic in the time domain is because it is a Fourier series, which by definition describes a periodic function. Do I have to explain why a sine wave is periodic? If you don't 'get' an answer, that isn't reason to down vote it. Just don't choose it as an answer you like. – user2718 Apr 03 '13 at 14:02
  • @DilipSarwate: The only answer that is justified to be down voted (given people take time out of their lives to offer up answers) is one that is incorrect or deliberately misleading. Just my opinion as a working professional. – user2718 Apr 03 '13 at 14:06
  • As I said right up front, I was not the one who voted your answer down. I do feel that it is a non-answer and that it is not particularly helpful or useful, and this last is indeed the official meaning of a downvote "This answer is not useful." – Dilip Sarwate Apr 03 '13 at 14:49
  • @Dilip - The concept that a DFT is a Fourier series and not a Fourier transform is fundamental to understanding exactly what a DFT is. The DFT assumes your data is periodic. I find many people don't get this, so I stress is all the time. Any practicing DSP engineer needs to understand the underlying assumptions of the tools they are using. If you have references that are supposed to explain what a DFT is and they don't mention the underlying assumption that the time domain waveform is assumed to be periodic, throw away those references as they are doing you a disservice. – user2718 Apr 03 '13 at 14:56
  • @Dilip - Not upvoting an answer means it isn't helpful. Down voting means the answer is incorrect or misleading. – user2718 Apr 03 '13 at 15:01

  • Down voting means the answer is incorrect or misleading. Not so. Try moving your pointer over a down-arrow and see what it shows as the meaning of a click on the down-arrow.

     – Dilip Sarwate Apr 03 '13 at 16:09
  • @Dilip Poor choice of behavior in my opinion. I find that interpretation to have a very negative impact on how the site operates. As I said, some of us on this site are working professionals and donate our time to provide help to others. I am probably in the minority with regard to my opinion here, but that won't stop me from promoting the use of a more constructive etiquette on the site. – user2718 Apr 03 '13 at 16:52
  • @BZ Your first para is clear to me. But in second para: "any periodic sequence cannot be uniquely represented for frequencies above fs/2 where fs is the sampling frequency of the sequence (also known as the nyquist frequency)" is this true only for periodic signals? – gpuguy Apr 04 '13 at 06:00
  • So with regard to a DFT, the universe is all periodic, which is why I only discussed periodic signals. This was the point of my down voted answer :-( but no matter. With regard to the representation of arbitrary signals by uniformly sampled equivalents (fs sampling rate), signal energy above fs/2 is folded back into the range 0-fs/2. It is still possible to uniquely represent the original signal if you have knowledge of its structure and the energy above the nyquist frequency folds back to regions of the nyquist band that are otherwise unoccupied. Signal recovery isn't so simple though. – user2718 Apr 04 '13 at 19:00
  • 1
    Wow - Aother down vote and the answer is essentially the same answer that gets 2 up votes. "The periodicity can be shown directly from the definition:" There must be some very stange visitors to this site. – user2718 Apr 10 '13 at 15:00
  • +1 because -1 looks bad. I do feel the other answer is better because it shows the periodicity from the definition, rather than just stating it (even if it is a direct copy from Wikipedia!). – Peter K. May 02 '13 at 11:52