Information Technology Reference
In-Depth Information
Note that, if
V>
1, the underlying dilution/mixing tree cannot be constructed and
hence the target is not reachable showing an
invalid
selection of elements in
R
,other-
wise the target is reachable. Moreover, if
V
=1,noextrabuffer(
D
) droplet is required
to achieve the target
CF
(i.e.,
C
D
=0), whereas if
V<
1,extrabuffer(
D
) is needed
(i.e.,
C
D
=0). Let
B
[
x.w
j
] represent the binary fraction for the contribution of
A
i
,
where
x
∈
R
and
x
=
W
[
i,j
]. The binary fraction for
C
D
can be represented as
[
x.w
j
]
(obtained by binary addition and subtraction). Let
ʲ
d
(
D
) be the number of 1sina
d
-bit binary fraction for buffer
D
, i.e.,
[
C
D
]=
1
−
∀x, x∈R
B
B
B
[
C
D
].
Problem Statement:
Find a subset
R
from the set
Q
(i.e.,
R
⊂
Q
), such that (
|
R
|
+
ʲ
d
(
D
)
) is minimized, where
T
=
∀x, x∈R
x
and
T
−
0
.
5
(i.e.,
T
=
T
0
.
5
)
.
We conjecture that this problem is computationally hard [18]. The subset-sum prob-
lem (SSP) [18] can be reduced to this problem, and we can obtain one or more so-
lution(s) by using the pseudo-polynomial time dynamic programming approach [16].
A solution (optimal or suboptimal) to this problem provides a dilution/mixing tree of
height
d
and the corresponding selection of
R
can be represented with a binary ma-
trix
|
T
|≤
±
(
d
+1),where
X
of size (
N
+1)
×
X
[
i,j
]
∈{
0
,
1
}
.If
W
[
i,j
] is selected in
R
,
[
i
] is a vector of
d
+1bits representing
the binary fraction for input
A
i
(with binary point between
X
[
i,j
]=1,otherwise
X
[
i,j
]=0. Hence,
X
X
[
i
][0] and
X
[
i
][1])and
X
[
C
D
]. The time complexity of an
algorithm to solve this problem depends on the size of input numbers, i.e.,
[
N
+1]represents the binary fraction for
C
D
, i.e.,
B
O
(
Nd.T
),
where
O
(
N.
(
d
+1))is the total number of elements in
Q
and
T
is the desired sum.
The total number of mix-split steps (
m
) in the dilution/mixing tree for a valid solution
(binary matrix) can be computed as
m
=
i
j
X
[
i,j
]
−
1
. However, more than one
valid solutions (binary matrices) can be obtained. Depending on the optimality criteria
(minimization of
m
,
d
or
M
lb
), several solutions (binary matrices) may be obtained.
Any one of them can be used to construct a dilution/mixing tree (by arbitrarily breaking
the ties). We present an algorithm (heuristic)
GDA
written as
Algorithm 1
to determine
the dilution/mixing tree for generalized dilution. Here, we use
Min-Mix
[6] in Step-19
to construct the dilution/mixing tree from the binary fractions obtained in Step-18 of
Algorithm 1
. However, other algorithms like
RMA
[9],
RSM
[12] or
MTCS
[15] may
also determine the tree from the target ratio after converting the binary fractions into a
ratio of decimal integers.
For the example
of Fig. 3(a), four different selections of
R
from
Q
and the corre-
sponding binary matrices are shown in Fig. 4. No tree can be constructed from the bi-
nary matrix of Fig. 4(b) indicating an invalid solution. The binary matrices of Fig. 4(c)
and 4(d) may yield the trees as shown in Fig. 3(d) and (e), respectively. The binary
matrix of Fig. 4(e) provides a suboptimal dilution tree with
d
=3and
m
=3.
W
3.3
Simulation Results
We have simulated the proposed algorithm for generalized dilution considering the tar-
get
CF C
A
within the range between 0 and max
i
{
i
(
i
= 1to
N
). The number of
input
CF
s (expect buffer
D
) is varied from 3 to 6 and the input
CF
s are represented as
b
i
=
B
i
b
i
}
,
∀
2
d
with different
d
(4 and 6), where
d
is the accuracy level of target
CF
. Hence,
C
A
is represented as
C
A
=
2
d
.Let
d
be the height of the dilution/mixing tree and
m
