Digital Signal Processing Reference
In-Depth Information
Fig. 2
KPNofJPEGdecoder
1.2
Preliminaries
We introduce some mathematical notation and preliminaries. We assume the reader
We u s e
(
X
,
)
to denote a CPO on the set
X
with partial order relation
⊆
X
×
X
to denote the corresponding partial order relation. We use
D
to denote the least
upper bound of a directed subset
D
of
X
. For convenience, we assume a universal,
countable, set
Chan
of channels and for every channel
c
∈
Chan
a corresponding
finite channel alphabet
to denote the union of all channel alphabets,
and
A
∗
(
A
ω
) to denote the set of all finite (and infinite) strings over alphabet
A
and
A
∗,
ω
=
Σ
c
.Weuse
Σ
A
∗
∪
A
ω
.
σ
and
τ
are strings,
σ
·
τ
denotes the usual concatenation
of the strings. If
.
A
history
of a channel denotes the sequence of data elements communicated
of a set
C
of channels is a mapping from channels
c
σ
τ
then
τ
−
σ
denotes the string
τ
without its prefix
σ
∈
C
to strings over
Σ
c
.Thesetof
all histories of
C
is denoted as
H
D
denotes the
history obtained from
h
by restricting the domain to
D
.If
h
1
is a history of
C
1
and
h
2
is a history of
C
2
, we write
h
1
(
C
)
.If
h
∈
H
(
C
)
and
D
⊆
C
,then
h
|
h
2
if
C
1
⊆
C
2
and for every
c
∈
C
1
,
h
1
(
c
)
h
2
(
c
)
.
The set of histories together with the relation
on histories form a complete partial
order with as bottom element the empty history 0. If
h
1
h
2
,then
h
2
−
h
1
denotes
the history which maps a channel
c
. Histories
h
1
and
h
2
are
called
consistent
if they share an upper bound, i.e., if there exists some history
h
3
such that
h
1
∈
C
1
to
h
2
(
c
)
−
h
1
(
c
)
h
3
and
h
2
h
3
.If
h
1
,
h
2
∈
H
(
C
)
, then the concatenation
h
1
·
h
2
is
the history such that
h
1
·
C
. A history is called finite
if it maps every channel in its domain to a finite string and only a finite number
h
2
(
c
)=
h
1
(
c
)
·
h
2
(
c
)
for all
c
∈
