Information Technology Reference
In-Depth Information
if for each value of x the correct value of each output variable appears exactly
once on each path from the root to a leaf.
The time associated with a computation is the length of the path traversed by the computa-
tion. The computation time T of a branching program is the length of its longest path.
P
is computed by
In Fig. 10.11 the computation associated with the input values ( u 1 , u 2 , v 1 , v 2 )=( 2, 4, 1,
3 ) takes the right branch out of the root and produces the output value v 1 = 1, takes the left
branch at the next vertex and produces u 1 = 2, and takes the right branch at the last vertex
and produces v 2 = 3and u 2 = 4. The output of this computation is the sorted sequence
1, 2, 3, 4, as expected. This branching program merges the two sorted lists. Each sink vertex
corresponds to one of the four ways of merging the two lists. The computation time of this
branching program is 3.
Branching programs that compare elements at vertices are well suited to merging and sort-
ing but are not of the most general type.
DEFINITION 10.9.3 A general branching program P with input variables x over a finite set
A
has a query of the form x i =? associated with a variable x i at each vertex. It also has one edge
directed away from the vertex for each value of x i . A general branching program is non-redundant
if along each path from the root to a leaf a query x i =? appears at most once.
The general branching program is also known as a binary decision diagram (BDD) . BDD's
are widely used in the computer-aided design (CAD) of circuits for Boolean functions.
A general branching program that convolves two short binary sequences over the integers
is shown in Fig. 10.12 . (Convolution is defined in Section 6.7.4 .) A computation leaves the
left branch of a vertex when the associated variable has value 0 and the right branch when it
a 0 =?
c 0 = 0
0
1
a 1 =?
b 0 =?
01
0
1
c 0 = 0
c 1 = 0
c 0 = 1
b 0 =?
b 1 =?
a 1 =?
c 2 = 0
0
1
0
1
0
1
c 1 = 0
c 2 = 0
c 2 = 0
b 1 =?
b 1 =?
c 1 = 1
a 1 =?
b 1 =?
b 1 =?
c 1 = 0
c 1 = 1
0
0
1
0
1
0
1
0
1
1
c 2 = 0
c 1 = 0
c 1 = 1
c 1 = 2
c 2 = 1
c 2 = 1
Figure 10.12 A general branching program to compute the convolution of two sequences
( a 0 , a 1 ) and ( b 0 , b 1 ) .
 
Search WWH ::




Custom Search