Digital Signal Processing Reference
In-Depth Information
Correspondence between DAG
o
s and a datastream
Figure 5.7.
D
EFINITION
5.1
A DAG
o
is
a DAG with the following restrictions:
1.
There is only one node, the source, with no incoming edges.
2. There is only one node, the sink, with no outgoing edges.
3. Each edge is assigned a data structure called its edge value. All edge
values in a given DAG, are of the same type.
Our basic data structure is similar to a polar DAG [Micheli, 1994], but
with
edge values.
When we refer to a DAG, in our DAG-coding appli-
cations, we assume a DAG with the restrictions in Definition 5.1. For a
specific example of a simple DAG coding, refer to Figure 5.6.
Macro-structures and their implied relations between the ordered
breaks create a representation with a DAG, in which every path from
source to sink represents a simple partitioning of the input datastream,
i.e., a partitioning with a linear order. A full correspondence between
a DAG
o
and a datastream is given in Figure 5.7. In a DAG
o
,
breaks
are represented by nodes, with the source as the start of the datastream
and the sink as the end of the datastream. The information contained
between two breaks is represented by an edge. Edge values of the graph
represent the datastream between two breaks under the assumption that
Search WWH ::
Custom Search