4
$\begingroup$

I am studying about fast Fourier transform.

Assuming that $x_0$, $x_1, \ldots, x_{n-1}$ are complex numbers, the DFT is defined as follows.

$$f_j = \sum\limits_{k=0}^{n-1} x_k e^{-\frac{2\pi i}{n}jk},\quad j= 0,\ldots, n-1$$

In the definition, $$W = e^{-i2 \pi/n}$$ and reorganize it,

$$f_j = \sum\limits_{k=0}^{n-1} x_k W^{jk},\quad j= 0,\ldots, n-1.$$

At this time, I looked at the equation below and solved $W$

$$ \begin{align} W(j) &= e^{-2 * pi * i * j / n}\\ &= e^{ (\pi \cdot i) \cdot (-2 \cdot j / n)}\\ &= \left(e^{\pi \cdot i}\right)^{-2 \cdot j / n} & \text {and } {e^{\pi \cdot i}= -1 }\\ &\text{so}\\ &= (-1)^{-2 \cdot j / n}\\ &= \left( -1^{-2} \right)^{j / n}\\ &= 1^{j / n}\\ &= 1 \end{align}$$

I couldn't figure out where was wrong by solving the equation. Help me out on what part I did wrong.

$\endgroup$

2 Answers 2

3
$\begingroup$

$$e^{ (\pi \cdot i) \cdot (-2 \cdot j / n)} \color{red}{\ne} \left(e^{\pi \cdot i}\right)^{-2 \cdot j / n}$$

You can't just $e^{a\cdot b}= \left(e^a\right)^b$ for arbitrary complex $a,b$, because $e^a$ is not necessarily a positive real number .

$\endgroup$
4
$\begingroup$

Please recognise $N$-th root of unity (on the complex-plane):

$$ 1^{1/N} = e^{j \frac{2\pi}{N} k} ~~,~~ k = 0,1,...,N-1 $$

where $j$ is the imaginary unit in DSP notation. Hence $1^{1/N} = 1$ is true but incomplete, for you ignore the complex roots.

So in your derivation last two lines should follow as:

$$ 1^{m / N} = (1^{1/N})^m $$ $$ e^{j\frac{2\pi}{N} k m } $$

where $j$ is the imaginary unit and $k$ is an integer. (I've replaced $n$ with $N$ and $j$ with $m$ for consistency of notation)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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