Information Technology Reference
In-Depth Information
at the
n
roots of unity, the DFT of
c
(
x
)
canbedoneatthe2
n
roots of unity by evaluating
a
(
x
)
and
b
(
x
)
at the 2
n
roots of unity (that is, computing the DFTs of their coefficients
as if they had degree 2
n
1), multiplying their values together, and taking the 2
n
-point
inverse DFT, that is, performing the computation stated in the theorem.
−
The combination of the convolution theorem and the algorithm for the FFT provides a
fast straight-line program for convolution, as stated below. The directed acyclic graph for this
straight-line program is shown in Fig.
6.9
on page
269
.
THEOREM
6.7.3
Let
n
=
2
d
. The convolution function
f
(
n
,
n
)
:
R
2
n
R
2
(
n−
1
)
→
over a
conv
commutative ring
R
can be computed by a straight-line program over
R
with size and depth
satisfying the following bounds:
C
f
(
n
,
n
)
conv
≤
12
n
log
2
n
D
f
(
n
,
n
)
conv
≤
4
log
2
n
6.8 Merging and Sorting Networks
The
sorting problem
is to put into ascending or descending order a collection of items that
are drawn from a totally ordered set. A set is
totally ordered
if for every two distinct elements
of the set one is larger than the other. The
merging problem
is to merge two sorted lists into
one sorted list. Sorting and merging algorithms can be either straight-line or non-straight-line.
An example of a non-straight-line merging algorithm is the following:
Create a new sorted list from two sorted lists by removing the smaller item from the
two lists and appending it to the new list until one list is empty, at which point append
the non-empty list to the end of the new list.
The binary sorting function
f
(
n
)
n
described in Section
2.11
sorts a Boolean
n
-
tuple into descending order. The combinational circuit given there is an example of a straight-
line sorting network, a network realized by a straight-line program. When the set of elements
to be sorted is not Boolean, sorting networks can become quite a bit more complicated, as we
see below.
In this section we describe
sorting networks
, circuits constructed from comparator oper-
ators that take
n
elements drawn from a finite totally ordered set
n
sort
:
B
→B
A
and put them into sorted
2
2
with arguments
a
and
b
returns their maximum
⊗
:
A
→A
order. A
comparator function
(
a
,
b
)=(max(
a
,
b
)
,
min(
a
,
b
))
.
It is convenient to show a comparator operator as a vertical edge between two lines carrying
values, as in Fig.
6.10
(a).Thevaluesonthetwolinestotherightoftheedgearethevaluesto
its left in sorted order, the smaller being on the upper line. A sorting network is an example
of a
comparator network
, a circuit in which the only operator is a comparator. Input values
appear on the left and output values appear on the right in sorted order.
Shown in Fig.
6.10
(b) is an
insertion-sorting network
on five inputs that inserts an ele-
ment into a previously sorted sublist. Two inputs are sorted at the wavefront labeled A. Between
wavefronts A and B a new item is inserted that is compared against the previously sorted sublist
and inserted into its proper position. The same occurs between wavefronts B and C and after
⊗
and minimum; that is,
Search WWH ::
Custom Search