3
$\begingroup$

I was watching a youtube video for the duality property for continuous time Fourier transforms, which shows that if Fourier transform of $x(t)$ is $X(\omega)$ then Fourier transform of $X(t)$ is $2\pi x(-\omega)$

Then how will duality look like in the case of the DFT?

Will it look like below?

If DFT of $x[n]$ is $X[k]$ then DFT of $X[n]$ is $2\pi x[-k]$

$\endgroup$
3
  • $\begingroup$ You can check this answer : dsp.stackexchange.com/a/68103/49439 $\endgroup$
    – DSP Rookie
    Commented Jun 10, 2020 at 8:57
  • 3
    $\begingroup$ And, if DFT of $x[n]$ is $X[k]$, then DFT of $X[n]$ will be $Nx[N-k]$. You can derive this by replacing $X[n]$ by it's analysis expression in the equation : $\displaystyle Y[k] = \sum^{N-1}_{n=0}X[n]e^{-j\frac{2\pi}{N}nk}$. $\endgroup$
    – DSP Rookie
    Commented Jun 10, 2020 at 9:31
  • 1
    $\begingroup$ you should probably put this into an answer, Rook. maybe with the math that proves it. $\endgroup$ Commented Jun 10, 2020 at 15:34

2 Answers 2

4
$\begingroup$

Duality in DFT would mean that if $x[n]$ has DFT coefficients as $X[k]$, then DFT of $X[n]$ would be $Nx[(N-k) \mod N]$

Proof:

Given, $$X[k] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N}nk}, k=0,1,2,3,...,(N-1)$$ If we take DFT of the sequence $X[n]$, then what we get is the following : $$Y[k] = \sum^{N-1}_{n=0}X[n]e^{-j\frac{2\pi}{N}nk} = N \left(\frac{1}{N}\sum^{N-1}_{n=0}X[n]e^{j\frac{2\pi}{N}n(-k)} \right)$$ Notice that the expression between "()" is the synthesis expression with $k^{th}$ frequency index replaced by $(N-k \mod N)^{th}$ index. Because, in DFT expression, $k$ can only take indices $0,1,2,3,...,(N-1)$, hence, we cannot have $-k$ as frequency index, but rather, $((N-k) \mod N)$ $$Y[k] = N \left(\frac{1}{N}\sum^{N-1}_{n=0}X[n]e^{j\frac{2\pi}{N}n(N-k)} \right) = Nx[(N-k) \mod N]$$

So, the way to interpret this is, you get a scaled and inverted sequence back when you take DFT of DFT, but $x[0]$ remains at $0^{th}$ index.

So, DFT of DFT of time-domain $x[n]$ gives $\{Nx[0], Nx[N-1], Nx[N-2], ..., Nx[2], Nx[1]\}$

Scaling by $N$ is the consequence of not dividing by $\frac{1}{\sqrt{N}}$ when taking DFT and incorporating this factor into IDFT expression.

$\endgroup$
3
  • $\begingroup$ How do you handle/use ( Mod N) with Nx(N-k) $\endgroup$
    – DSP_CS
    Commented Jun 12, 2020 at 6:56
  • $\begingroup$ Since in math , Mod is what is left after division as remainder but i can not see any division in Nx(N-k) $\endgroup$
    – DSP_CS
    Commented Jun 12, 2020 at 6:59
  • 1
    $\begingroup$ @abtj N-k mod N means what's left as remainder when you divide N-k by N. For k=0, it's N mod N meaning 0, and hence when reversing, $x[0]$ remains at the same place whereas other k's switch places with N-k. $\endgroup$
    – DSP Rookie
    Commented Jun 12, 2020 at 10:43
3
$\begingroup$

Initial comment: duality refers to the strong similarity of mathematical expressions and properties in two different domains, here time and frequency. This is not only decorative or made to annoy learners. Duality helps a lot: one can derive results much faster, interpret classes of transformations more easily. To make this serious, you can check the Pontryagin duality with Fourier transforms.

Second comment: the classical continuous-time/continuous-frequency Fourier possesses some duality-related properties (on symmetry, shift, energy, convolution, etc.). By discretizing both time and frequency in the Discrete Fourier Transform (DFT), their developers have striven to keep, whenever possible, most of the initial properties. To me, the duality in the forward and inverse DFT is well-explained in the chapter The Discrete Fourier Transform (DFT). If you want to better observe duality between the indices, you can even modify the initial scaling factor. Thus, instead of a DFT normalized in amplitude, we can normalize it in energy. It can be useful to remark that we have two sequences $x[n]$ and $X[k]$ with the same length $K=N$. This is a bit artificial here, but we can rewrite the energy-normalization constant $\sqrt{N}$ as $\nu_{KN}=\nu_{NK}=(KN)^{1/4}$. Now, let $\omega_k = 2\pi \frac{k}{N}f_s$, then for $n=0,1,\ldots,N-1$, and $k=0,1,\ldots,K-1$ (with $K=N$)

$$X(\omega_k)=X[k] = \nu_{NK}\sum_{n=0}^{N-1}x[n]e^{-2\pi j \frac{n}{N}k}$$

and

$$x[n]= \nu_{KN}\sum_{k=0}^{K-1}X[k]e^{2\pi j \frac{k}{K}n}$$

where the duality in formulae is evident. The expression of a DFT of a DFT is already given by @DSP Rookie. The hidden message is that, when you have a formula or a code for the DFT, you also have one for the inverse DFT, provided you modify a bit the inputs and scaling, see for instance: Expressing the inverse DFT in terms of the DFT.

$\endgroup$
1
  • 1
    $\begingroup$ This is not only decorative or made to annoy learners :D $\endgroup$
    – Gilles
    Commented Sep 22, 2020 at 13:52

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.