2
$\begingroup$

In what ways does modular arithmetic plays a part in DFT? Why is it a so integral part of DFT?

$\endgroup$

2 Answers 2

1
$\begingroup$

You might find the answers to this related question pertinent as well: In case of Complex DFT spectrum, why the x axis range from N/2 to N point mean a negative frequency? (Check out my answer in particular.)

If you really want a different conceptual understanding of the DFT and its modular nature, read my blog article:

I think r b-j's answers to this are correct, but not as helpful to someone trying to learn it for the first time. He puts "outside the box" and "inside the box" all in one compact definition.

The key is understanding that the forward and reverse DFTs are essentially the same mathematically, and they operate on a finite domain with a finite range. In each case, if you extend the range of the operator "outside the box", by extending the underlying trigonometric functions, you get a repeat pattern. Thus, if I choose a segment of a signal, called a frame, and apply the DFT to it, I will get a set of complex values which Macleod calls the DFS (Discrete Fourier Spectrum). The repeat pattern in the frequency domain is associated with what are known as "Aliases" and is associated with (and proven to be a good description) by the sampling theorem.

Going in the other direction. If you take a DFS, and apply the inverse DFT, you will get your original signal frame back. If you extend the trigonometric functions in this case, the signal produced with be a repeat pattern of your sample frame. The only signals for which the repeat pattern matches the actual signal is for periodic signals where the frame size is a whole number of periods.

The repeat patterns are why modularity is inherent.


This blog article by Neil Robertson is specifically on this topic:

$\endgroup$
1
$\begingroup$

This answer to a differently worded question answers your question also.

And this answer is relevant.

And this answer and this answer.

I confess that I take great exception to anyone who denies that the Discrete Fourier Transform (and inverse DFT) fundamentally periodically extend the finite set of data presented to it. I'm a nazi about it. The DFT assumes that the $N$ samples of $x[n]$ passed to it are one period of a periodic sequence where $x[n+N]=x[n]$ for all integer $n$. And the inverse DFT does the same in that the $N$ samples of $X[k]$ passed to it are one period of a periodic sequence where $X[k+N]=X[k]$ for all integer $k$.

The modulo arithmetic done to the indices of $x[n]$ and $X[k]$ simply guarantee this periodicity while also guaranteeing that neither index, $n$ or $k$, go outside of the bounds of the finite sized arrays in memory representing $x[n]$ and $X[k]$. That is

$$ 0 \le n = \operatorname{mod}_N(n+mN) < N $$ and $$ 0 \le k = \operatorname{mod}_N(k+mN) < N $$

for any integer $m$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.