1
$\begingroup$

I'm trying to understand DFT in the context of an integer ring (i.e. the number theoretic transform) and I was wondering how to reduce the number of multiplications by the twiddle factors.

Consider 3-point DFT:

X_0 = x_0 + x_1       + x_2
X_1 = x_0 + x_1 * w   + x_2 * w^2
X_2 = x_0 + x_1 * w^2 + x_2 * w^4

Which is the same as:

X_0 = x_0 + x_1       + x_2
X_1 = x_0 + x_1 * w   + x_2 * w^2
X_2 = x_0 + x_1 * w^2 + x_2 * w

and it needs 4 (modular) multiplications.

However, apparently it can be also written as:

X_0 = x_0 + x_1           + x_2
X_1 = x_0 + x_1 * w       - x_2 - x_2 * w
X_2 = x_0 - x_1 - x_1 * w + x_2 * w

which uses only 2 multiplications.

I just cannot figure out how to derive - x_2 - x_2 * w out of x_2 * w^2, could someone please fill in the details for me? Are there other ways to reduce the number of multiplications? Is it possible to use just one (or even zero) multiplication? Does similar trick work for larger transforms?

$\endgroup$
1
$\begingroup$

What you have to show is that

$$W_3^2+W_3+1=0\tag{1}$$

with $W_3=e^{-j2\pi/3}$. It's a straightforward exercise to prove $(1)$.

In general we have

$$\sum_{k=0}^{N-1}W_N^k=0,\qquad N>1\tag{2}$$

with $W_N=e^{-j2\pi/N}$. Eq. $(2)$ can be shown by using the formula for the geometric sum.

$\endgroup$
1

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.