Information Technology Reference
In-Depth Information
Figure 2.6
A balanced binary tree circuit that combines elements with an associative operator.
2.5.1 Logical Operations
Logical operations are not only building blocks for more complex operations, but they are
at the heart of all central processing units. Logical operations include “vector” and “asso-
ciating” operations. A
vector operation
is the component-wise operation on one or more
ve
ctor
s.
For exa
m
pl
e,
the vector
NOT
on the vector
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
is the vector
x
=(
x
n−
1
,
...
,
x
1
,
x
0
)
. Other vector operations involve the application of a two-input func-
tion to corresponding components of two vectors. If
is a two-input function, such as
AND
or
OR
,and
x
=
(
x
n−
1
,
...
,
x
1
,
x
0
)
and
y
=(
y
n−
1
,
...
,
y
1
,
y
0
)
are two
n
-tuples, the vector
operation
x
y
is
x
y
=(
x
n−
1
y
n−
1
,
...
,
x
1
y
1
,
x
0
y
0
)
An
associative operator
A
satisfies the condition
(
a
b
)
c
=
a
(
b
c
)
for all
over a
a
,
b
,
c
∈A
.A
summing operation
on an
n
-tuple
x
with an associative two-input operation
produces the “sum”
y
defined below.
x
0
An efficient circuit for computing
y
is shown in Fig.
2.6
. It is a binary tree whose leaves are
associated with the variables
x
n−
1
,
...
,
x
1
,
x
0
. Each level of the tree is full except possibly
the last. This circuit has smallest depth of those that form the associative combination of the
variables, namely
y
=
x
n−
1
···
x
1
log
2
n
.
2.5.2 Shifting Functions
Shifting functions can be used to multiply integers and generally manipulate data. A cyclic
shifting function rotates the bits in a word. For example, the left cyclic shift of the 4-tuple
(
1, 0, 0, 0
)
by three places produces the 4-tuple
(
0, 1, 0, 0
)
.
The
cyclic shifting function
f
(
n
)
n
+
log
2
n
→B
n
takesasinputan
n
-tuple
x
=
cyclic
:
B
(
x
n−
1
,
...
,
x
1
,
x
0
)
and cyclically shifts it left by
|
s
|
|
s
|
places, where
is the integer associated
with the binary
k
-tuple
s
=(
s
k−
1
,
...
,
s
1
,
s
0
)
,
k
=
log
2
n
,and
k−
1
s
j
2
j
|
s
|
=
j
=
0
The
n
-tuple that results from the shift is
y
=(
y
n−
1
,
...
,
y
1
,
y
0
)
, denoted as follows:
y
=
f
(
n
)
cyclic
(
x
,
s
)
Search WWH ::
Custom Search