Discrete Fourier transform over a ring explained

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.

Definition

Let be any ring, let

n\geq1

be an integer, and let

\alpha\inR

be a principal nth root of unity, defined by:[1]

(v0,\ldots,vn-1)

of elements of to another n-tuple

(f0,\ldots,fn-1)

of elements of according to the following formula:

By convention, the tuple

(v0,\ldots,vn-1)

is said to be in the time domain and the index is called time. The tuple

(f0,\ldots,fn-1)

is said to be in the frequency domain and the index is called frequency. The tuple

(f0,\ldots,fn-1)

is also called the spectrum of

(v0,\ldots,vn-1)

. This terminology derives from the applications of Fourier transforms in signal processing.

If is an integral domain (which includes fields), it is sufficient to choose

\alpha

as a primitive nth root of unity, which replaces the condition by:[1]

\alphak\ne1

for

1\leqk<n

Another simple condition applies in the case where n is a power of two: may be replaced by

\alphan/2=-1

.[1]

Inverse

The inverse of the discrete Fourier transform is given as:

where

1/n

is the multiplicative inverse of in (if this inverse does not exist, the DFT cannot be inverted).

Matrix formulation

Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:

\begin{bmatrix}f0\\f1\\\vdots\\fn-1\end{bmatrix} =\begin{bmatrix} 1&1&1&&1\\ 1&\alpha&\alpha2&&\alphan-1\\ 1&\alpha2&\alpha4&&\alpha2(n-1)\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\alphan-1&\alpha2(n-1)&&\alpha(n-1)(n-1)\\ \end{bmatrix} \begin{bmatrix}v0\\v1\\\vdots\\vn-1\end{bmatrix}.

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

\begin{bmatrix}v0\\v1\\\vdots\\vn-1\end{bmatrix} =

1
n

\begin{bmatrix} 1&1&1&&1\\ 1&\alpha-1&\alpha-2&&\alpha-(n-1)\\ 1&\alpha-2&\alpha-4&&\alpha-2(n-1)\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\alpha-(n-1)&\alpha-2(n-1)&&\alpha-(n-1)(n-1)\end{bmatrix} \begin{bmatrix}f0\\f1\\\vdots\\fn-1\end{bmatrix}.

Polynomial formulation

Sometimes it is convenient to identify an -tuple

(v0,\ldots,vn-1)

with a formal polynomial

pv(x)=v0+v1x+

2
v
2x

++vn-1xn-1.

By writing out the summation in the definition of the discrete Fourier transform, we obtain:

fk=v0+

k
v
1\alpha

+

2k
v
2\alpha

++vn-1\alpha(n-1)k.

This means that

fk

is just the value of the polynomial

pv(x)

for

x=\alphak

, i.e.,

The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the th roots of unity, which are exactly the powers of

\alpha

.

Similarly, the definition of the inverse Fourier transform can be written:

With

pf(x)=f0+f1x+

2
f
2x

++fn-1xn-1,

this means that

vj=

1
n
-j
p
f(\alpha

).

We can summarize this as follows: if the values of

pv(x)

are the coefficients of

pf(x)

, then the values of

pf(x)

are the coefficients of

pv(x)

, up to a scalar factor and reordering.[2]

Special cases

Complex numbers

If

F={C}

is the field of complex numbers, then the

n

th roots of unity can be visualized as points on the unit circle of the complex plane. In this case, one usually takes
-2\pii
n
\alpha=e

,

which yields the usual formula for the complex discrete Fourier transform:

fk=

n-1
\sum
j=0

vj

-2\piijk
n
e

.

Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor

1
\sqrt{n
} in both formulas, rather than

1

in the formula for the DFT and
1
n
in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that

\sqrt{n}

does not make sense in an arbitrary field.

Finite fields

If

F=GF(q)

is a finite field, where is a prime power, then the existence of a primitive th root automatically implies that divides

q-1

, because the multiplicative order of each element must divide the size of the multiplicative group of, which is

q-1

. This in particular ensures that

n=\underbrace{1+1+ … +1}n\rm

is invertible, so that the notation
1
n
in makes sense.

An application of the discrete Fourier transform over

GF(q)

is the reduction of Reed–Solomon codes to BCH codes in coding theory. Such transform can be carried out efficiently with proper fast algorithms, for example, cyclotomic fast Fourier transform.

Polynomial formulation without nth root

Suppose

F=GF(p)

. If

p\nmidn

, it may be the case that

n\nmidp-1

. This means we cannot find an

nth

root of unity in

F

. We may view the Fourier transform as an isomorphism
n-1)
F[C
n]=F[x]/(x

\congoplusiF[x]/(Pi(x))

for some polynomials

Pi(x)

, in accordance with Maschke's theorem. The map is given by the Chinese remainder theorem, and the inverse is given by applying Bézout's identity for polynomials.[3]
n-1=\prod
x
d|n

\Phid(x)

, a product of cyclotomic polynomials. Factoring

\Phid(x)

in

F[x]

is equivalent to factoring the prime ideal

(p)

in

Z[\zeta]=Z[x]/(\Phid(x))

. We obtain

g

polynomials

P1\ldotsPg

of degree

f

where

fg=\varphi(d)

and

f

is the order of

pmodd

.

As above, we may extend the base field to

GF(q)

in order to find a primitive root, i.e. a splitting field for

xn-1

. Now

xn-1=\prodk(x-\alphak)

, so an element
n-1
\sum
j=0

vjxj\inF[x]/(xn-1)

maps to
n-1
\sum
j=0

vjxj\mod(x-\alphak)\equiv

n-1
\sum
j=0

vj(\alphak)j

for each

k

.

When p divides n

When

p|n

, we may still define an

Fp

-linear isomorphism as above. Note that

(xn-1)=(xm-1)

ps
where

n=mps

and

p\nmidm

. We apply the above factorization to

xm-1

, and now obtain the decomposition

F[x]/(xn-1)\congoplusi

ps
F[x]/(P
i(x)

)

. The modules occurring are now indecomposable rather than irreducible.

Order of the DFT matrix

Suppose

p\nmidn

so we have an

nth

root of unity

\alpha

. Let

A

be the above DFT matrix, a Vandermonde matrix with entries

Aij=\alphaij

for

0\lei,j<n

. Recall that
n-1
\sum
j=0

\alpha(k-l)j=n\deltak,l

since if

k=l

, then every entry is 1. If

k\nel

, then we have a geometric series with common ratio

\alphak-l

, so we obtain
1-\alphan(k-l)
1-\alphak-l
. Since

\alphan=1

the numerator is zero, but

k-l\ne0

so the denominator is nonzero.

First computing the square,

2)
(A
ik

=

n-1
\sum
j=0

\alphaj(i+k)=n\deltai,-k

. Computing

A4=(A2)2

similarly and simplifying the deltas, we obtain
4)
(A
ik
2\delta
=n
i,k
. Thus,

A4=n2In

and the order is

4 ⋅ ord(n2)

.

Normalizing the DFT matrix

In order to align with the complex case and ensure the matrix is order 4 exactly, we can normalize the above DFT matrix

A

with
1
\sqrt{n
}. Note that though

\sqrt{n}

may not exist in the splitting field

Fq

of

xn-1

, we may form a quadratic extension
F
q2

\cong

2-n)
F
q[x]/(x
in which the square root exists. We may then set
U=1
\sqrt{n
}A, and
4=I
U
n
.

Unitarity

Suppose

p\nmidn

. One can ask whether the DFT matrix is unitary over a finite field. If the matrix entries are over

Fq

, then one must ensure

q

is a perfect square or extend to
F
q2
in order to define the order two automorphism

x\mapstoxq

. Consider the above DFT matrix

Aij=\alphaij

. Note that

A

is symmetric. Conjugating and transposing, we obtain
*
A
ij

=\alphaqji

.
*)
(AA
ik

=

n-1
\sum
j=0

\alphaj(i+qk)=n\deltai,-qk

by a similar geometric series argument as above. We may remove the

n

by normalizing so that

U=

1
\sqrt{n
}A and
*)
(UU
ik

=\deltai,-qk

. Thus

U

is unitary iff

q\equiv-1(modn)

. Recall that since we have an

nth

root of unity,

n|q2-1

. This means that

q2-1\equiv(q+1)(q-1)\equiv0(modn)

. Note if

q

was not a perfect square to begin with, then

n|q-1

and so

q\equiv1(modn)

.

For example, when

p=3,n=5

we need to extend to

q2=34

to get a 5th root of unity.

q=9\equiv-1(mod5)

.

For a nonexample, when

p=3,n=8

we extend to
F
32
to get an 8th root of unity.

q2=9

, so

q\equiv3(mod8)

, and in this case

q+1\not\equiv0

and

q-1\not\equiv0

.

UU*

is a square root of the identity, so

U

is not unitary.

Eigenvalues of the DFT matrix

When

p\nmidn

, we have an

nth

root of unity

\alpha

in the splitting field

Fq\cong

n-1)
F
p[x]/(x
. Note that the characteristic polynomial of the above DFT matrix may not split over

Fq

. The DFT matrix is order 4. We may need to go to a further extension

Fq'

, the splitting extension of the characteristic polynomial of the DFT matrix, which at least contains fourth roots of unity. If

a

is a generator of the multiplicative group of

Fq'

, then the eigenvalues are

\{\pm1,\pma(q'-1)/4\}

, in exact analogy with the complex case. They occur with some nonnegative multiplicity.

Number-theoretic transform

The number-theoretic transform (NTT)[4] is obtained by specializing the discrete Fourier transform to

F={Z}/p

, the integers modulo a prime . This is a finite field, and primitive th roots of unity exist whenever divides

p-1

, so we have

p=\xin+1

for a positive integer . Specifically, let

\omega

be a primitive

(p-1)

th root of unity, then an th root of unity

\alpha

can be found by letting

\alpha=\omega\xi

.

e.g. for

p=5

,

\alpha=2

\begin{align}21&=2\pmod5\\22&=4\pmod5\\23&=3\pmod5\\24&=1\pmod5\end{align}

when

N=4

\begin{bmatrix} F(0)\\ F(1)\\ F(2)\\ F(3)\end{bmatrix} = \begin{bmatrix} 1&1&1&1\\ 1&2&4&3\\ 1&4&1&4\\ 1&3&4&2\end{bmatrix} \begin{bmatrix} f(0)\\ f(1)\\ f(2)\\ f(3)\end{bmatrix}

The number theoretic transform may be meaningful in the ring

Z/m

, even when the modulus is not prime, provided a principal root of order exists. Special cases of the number theoretic transform such as the Fermat Number Transform, used by the Schönhage–Strassen algorithm, or Mersenne Number Transform[5] use a composite modulus.

Discrete weighted transform

The discrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involving weighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector. The Irrational base discrete weighted transform is a special case of this.

Properties

Most of the important attributes of the complex DFT, including the inverse transform, the convolution theorem, and most fast Fourier transform (FFT) algorithms, depend only on the property that the kernel of the transform is a principal root of unity. These properties also hold, with identical proofs, over arbitrary rings. In the case of fields, this analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field

F
1n

.

In particular, the applicability of

O(nlogn)

fast Fourier transform algorithms to compute the NTT, combined with the convolution theorem, mean that the number-theoretic transform gives an efficient way to compute exact convolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible to round-off error in finite-precision floating point arithmetic; the NTT has no round-off because it deals purely with fixed-size integers that can be exactly represented.

Fast algorithms

For the implementation of a "fast" algorithm (similar to how FFT computes the DFT), it is often desirable that the transform length is also highly composite, e.g., a power of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm,[6] that are efficient regardless of whether the transform length factors.

See also

References

  1. Martin Fürer, "Faster Integer Multiplication", STOC 2007 Proceedings, pp. 57 - 66. Section 2: The Discrete Fourier Transform.
  2. R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.
  3. https://github.com/jacksonwalters/dft-finite-groups
  4. Agarwal. R.. Burrus. C.. April 1974. Fast Convolution using fermat number transforms with applications to digital filtering. IEEE Transactions on Acoustics, Speech, and Signal Processing. en. 22. 2. 87–97. 10.1109/TASSP.1974.1162555. 0096-3518.
  5. Rader. C.M.. December 1972. Discrete Convolutions via Mersenne Transforms. IEEE Transactions on Computers. C-21. 12. 1269–1273. 10.1109/T-C.1972.223497. 1939809 . 0018-9340.
  6. [Yao Wang]

External links