Information Technology Reference
In-Depth Information
y
7
y
6
y
5
y
4
y
3
y
2
y
1
y
0
Shift by 2
2
s
2
Shift by 2
1
s
1
Shift by 2
0
s
0
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
Figure 2.7
Three stages of a cyclic shifting circuit on eight inputs.
A convenient way to perform the cyclic shift of
x
by
|
s
|
|
s
|
places is to represent
as a sum
1, shift
x
left cyclically by
s
j
2
j
places, that is, by either 0 or 2
j
places depending on whether
s
j
=
0 or 1. For example,
consider cyclically shifting the 8-tuple
u
=(
1, 0, 1, 1, 0, 1, 0, 1
)
by seven places. Since 7 is
represented by the binary number
(
1, 1, 1
)
,thatis,7
=
4
+
2
+
1, to shift
(
1, 0, 1, 1, 0, 1, 0, 1
)
by seven places it suffices to shift it by one place, by two places, and then by four places. (See
Fig.
2.7
.)
For 0
of powers of 2, as shown above, and for each 0
≤
j
≤
k
−
1, the following formula defines the value of the
r
th output,
y
r
,ofa
circuit on
n
inputs that shifts its input
x
left cyclically by either 0 or 2
j
places depending on
whether
s
j
=
0or1:
≤
r
≤
n
−
y
r
=(
x
r
∧
s
j
)
∨
(
x
(
r−
2
j
)mod
n
∧
s
j
)
2
j
)mod
n
Thus,
y
r
is
x
r
inthefirstcaseor
x
(
r−
2
j
)mod
n
in the second. The subscript
(
r
−
2
j
)
after division by
n
. For example, if
n
=
4,
r
=
1, and
is the positive remainder of
(
r
−
2
j
)=
j
=
1, then
(
r
1, which is 3 modulo 4. That is, in a circuit that shifts by either 0
or 2
1
places,
y
1
is either
x
1
or
x
3
because
x
3
moves into the second position when shifted left
cyclically by two places.
A circuit based on the above formula that shifts by either 0 or 2
j
places depending on
whether
s
j
=
0or1isshowninFig.
2.8
for
n
=
4. The circuit on
n
inputs has 3
n
+
1gates
and depth 3.
It follows that a circuit for cyclic shifting an
n
-tuple can be realized in
k
=
−
−
stages
each of which has 3
n
+
1 gates and depth 3, as suggested by Fig.
2.7
. Since this may be neither
the smallest nor the shallowest circuit that computes
f
(
n
)
log
2
n
n
+
log
2
n
, its minimal circuit
cyclic
:
B
size and depth satisfy the following bounds.
Search WWH ::
Custom Search