Information Technology Reference
In-Depth Information
f
(
n
)
cyclic
x
f
(
2
n
)
shift
x
Figure 2.10
The function
f
(
n
)
cyclic
is obtained by computing
f
(
2
n
)
shift
on
xx
and truncating the
n
low-order bits.
LEMMA
2.5.2
The function
f
(
2
n
)
cyclic
contains
f
(
n
)
shift
as a subfunction and the function
f
(
2
n
)
con-
shift
tains
f
(
n
)
cyclic
as a subfunction.
Proof
The first statement follows from the above argument concerning
f
(
n
)
shift
.Thesecond
statement follows by noting that
f
(
2
n
)
x
,
s
)
f
(
n
)
cyclic
(
x
,
s
)=
π
(
n
)
shift
(
x
·
H
where
π
(
n
)
H
deletes the
n
low-order components of its input.
This relationship between logical and cyclic shifting functions clearly holds for variants
of such functions in which the amount of a shift is specified with some other notation. An
example of such a shifting function is integer multiplication in which one of the two arguments
is a power of 2.
2.5.3 Encoder
The
encoder function
f
(
n
)
encode
2
n
n
has 2
n
inputs, exactly one of which is 1. Its
output is an
n
-tuple that is a binary number representing the position of the input that has
value 1. That is, it encodes the position of the input bit that has value 1. Encoders are used in
CPUs to identify the source of external interrupts.
Let
x
=(
x
2
n
−
1
,
...
,
x
2
,
x
1
,
x
0
)
represent the 2
n
:
B
→B
inputs and let
y
=(
y
n−
1
,
...
,
y
1
,
y
0
)
represent the
n
outputs. Then, we write
f
(
n
)
encode
(
x
)=
y
.
When
n
=
1, the encoder function has two inputs,
x
1
and
x
0
,andoneoutput,
y
0
,whose
value is
y
0
=
x
1
because if
x
0
=
1, then
x
1
=
0and
y
0
=
0 is the binary representation of
the input whose value is 1. Similar reasoning applies when
x
0
=
0.
When
n
2, we observe that the high-order output bit,
y
n−
1
, has value 1 if 1 falls among
the variables
x
2
n
−
1
,
...
,
x
2
n
−
1
+
1
,
x
2
n
−
1
.Otherwise,
y
n−
1
=
0. Thus,
y
n−
1
can be computed
as the
OR
of these variables, as suggested for the encoder on eight inputs in Fig.
2.11
.
The remaining
n
≥
−
1outputbits,
y
n−
2
,
...
,
y
1
,
y
0
, represent the position of the 1 among
variables
x
2
n
−
1
1
,
...
,
x
2
,
x
1
,
x
0
if
y
n−
1
=
0orthe1amongvariables
x
2
n
−
1
,
...
,
x
2
n
−
1
+
1
,
x
2
n
−
1
if
y
n−
1
=
1. For example, for
n
=
3if
x
=(
0, 0, 0, 0, 0, 0, 1, 0
)
,then
y
2
=
0and
−
Search WWH ::
Custom Search