3-point DFT with two multiplications

Question

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?

Answer 1

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.