Information Technology Reference
In-Depth Information
y
3
y
2
y
1
y
0
s
1
x
3
x
2
x
1
x
0
Figure 2.8
One stage of a circuit for cyclic shifting four inputs by 0 or 2 places depending on
whether
s
1
=
0or1.
LEMMA
2.5.1
The cyclic shifting function
f
(
n
)
n
+
log
2
n
n
cyclic
:
B
→B
can be realized by a
circuit of the following size and depth over the basis
Ω
0
=
{∧
,
∨
,
¬}
:
C
Ω
0
f
(
n
)
cyclic
≤
(
3
n
+
1
)
log
2
n
D
Ω
0
f
(
n
)
cyclic
≤
log
2
n
3
The
logical shifting function
f
(
n
)
n
+
log
2
n
n
shift
:
B
→B
shifts left the
n
-tuple
x
by
a number of places specified by a binary
-tuple
s
, discarding the higher-index com-
ponents, and filling in the lower-indexed vacated places with 0's to produce the
n
-tuple
y
,
where
log
n
y
j
=
x
j−|
s
|
for
|
s
|≤
j
≤
n
−
1
0
otherwise
REDUCTIONS BETWEEN LOGICAL AND CYCLIC SHIFTING
The logical shifting function
f
(
n
)
shift
:
n
on the
n
-tuple
x
is defined below in terms of
f
(
2
n
)
n
+
log
2
n
→B
B
cyclic
and the “projection”
function
π
(
n
)
L
n
that deletes the
n
high order components from its input 2
n
-tuple.
Here
0
denotes the zero binary
n
-tuple and
0
2
n
:
B
→B
·
x
denotes the concatenation of the two strings.
(See Figs.
2.9
and
2.10
.)
f
(
2
n
)
x
,
s
)
f
(
n
)
shift
(
x
,
s
)=
π
(
n
)
·
cyclic
(
0
L
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
0
0000
0
00
Figure 2.9
The reduction of
f
(
8
)
shift
to
f
(
8
)
·
x
cyclic
obtained by cyclically shifting
0
by three places
andprojectingouttheshadedcomponents.
Search WWH ::
Custom Search