Information Technology Reference
In-Depth Information
6.7.1 Commutative Rings*
Since the DFT is defined over commutative rings having an
n
th root of unity, we digress briefly
to discuss such rings. (Commutative rings are defined in Section
6.2
.)
DEFINITION
6.7.1
A commutative ring
R
=(
R
,
+
,
∗
,0,1
)
has a
principal
n
th root of unity
ω
if
ω
∈
R
satisfies the following conditions:
ω
n
=
1
(6.19)
n−
1
ω
lk
=
0foreach1
≤
l
≤
n
−
1
(6.20)
k
=
0
The elements
ω
0
,
ω
1
,
ω
2
,
...
,
ω
n−
1
are the
n
th roots of unity
and the elements
ω
0
,
ω
−
1
,
ω
−
2
,
...
,
ω
−
(
n−
1
)
are the
n
th inverse roots of unity
. (Note that
ω
−j
=
ω
n−j
is the multiplicative
inverse of
ω
j
since
ω
j
ω
n−j
=
ω
n
=
1
.)
Two commutative rings that have principal
n
th roots of unity are the complex numbers
and the ring
m
of integers modulo
m
=
2
tn/
2
+
1when
t
2and
n
=
2
q
,asweshow.
The reader is asked to show that
m
has a principal
n
th root of unity, as stated below. (See
Problem
6.24
.)
≥
LEMMA
6.7.1
Let
m
be the ring of integers modulo
m
when
m
=
2
tn/
2
+
1
,
t ≥
2
and
n
=
2
q
.Then
ω
=
2
t
is a principal
n
th root of unity.
An example of the ring
m
is given by
t
=
2,
n
=
4, and
m
=
2
4
+
1
=
17. In this
ring
ω
=
4 is a principal fourth root of unity. This is true because
ω
n
=
4
4
=
16
·
16
=
1
)+
1
=
1
mod (
16
+
1
)
and
n−
1
j
=
0
ω
pj
=((
4
p
)
n
1
)
/
(
4
p
(
16
+
1
)(
16
−
−
−
1
)mod(
17
)
=
((
4
n
)
p
1
)
/
(
4
p
1
)mod(
17
)=(
1
p
1
)
/
(
4
p
−
−
−
−
1
)mod(
17
)=
0
mod (
17
)
.
LEMMA
6.7.2
e
2
πi/n
=cos(
2
π/n
)+
i
sin(
2
π/n
)
is a principal
n
th root of unity over the
complex numbers where
i
=
√
−
1
is the “imaginary unit.”
Proof
The first condition is satisfied because
(
e
2
πi/n
)
n
=
e
2
πi
=
1. Also,
n−
1
k
=
0
ω
lk
=
(
ω
ln
1
)
/
(
ω
l
1for
ω
=
e
2
πi/n
.
−
−
1
)=
0if1
≤
l
≤
n
−
6.7.2 The Discrete Fourier Transform
The discrete Fourier transform has many applications. In Section
6.7.4
we see that it can be
used to compute the convolution of two sequences efficiently, which is the same as computing
the coefficients of the product of two polynomials. The discrete Fourier transform can also be
used to construct a fast algorithm (circuit) for the multiplication of two binary integers [
303
].
It is widely used in processing analog data such as speech and music.
The
n
-point
discrete Fourier transform
F
n
:
R
n
R
n
maps
n
-tuples
a
=(
a
0
,
a
1
,
...
,
a
n−
1
)
over
R
to
n
-tuples
f
=(
f
0
,
f
1
,
...
,
f
n−
1
)
over
R
;thatis,
F
n
(
a
)=
f
.Thecom-
ponents of
f
are defined as the values of the following polynomial
p
(
x
)
at the
n
th roots of
unity:
→
+
a
n−
1
x
n−
1
p
(
x
)=
a
0
+
a
1
x
+
a
2
x
2
+
···
(6.21)
Search WWH ::
Custom Search