Databases Reference
In-Depth Information
Notice that to generate the tag for the sequence 1 3 we did not have to generate a tag for
every other possible message. However, based on Equation (
4
) and Example
4.3.3
, we need
to know the probability of every sequence that is “less than” the sequence for which the tag
is being generated. The requirement that the probability of all sequences of a given length
be explicitly calculated can be as prohibitive as the requirement that we have codewords for
all sequences of a given length. Fortunately, we shall see that to compute a tag for a given
sequence of symbols, all we need is the probability of individual symbols, or the probability
model.
Recall that, given our construction, the interval containing the tag value for a given sequence
is disjoint from the intervals containing the tag values of all other sequences. This means that
any value in this interval would be a unique identifier for
x
i
. Therefore, to fulfill our initial
objective of uniquely identifying each sequence, it would be sufficient to compute the upper
and lower limits of the interval containing the tag and select any value in that interval. The
upper and lower limits can be computed recursively as shown in the following example.
Example4.3.4:
We will use the alphabet of Example
4.3.2
and find the upper and lower limits of the interval
containing the tag for the sequence 3 2 2. Assume that we are observing 3 2 2 in a sequential
manner; that is, first we see 3, then 2, and then 2 again. After each observation, we will
compute the upper and lower limits of the interval containing the tag of the sequence observed
to that point. We will denote the upper limit by
u
(
n
)
and the lower limit by
l
(
n
)
, where
n
denotes
the length of the sequence.
We first observe 3. Therefore,
u
(
1
)
=
l
(
1
)
=
F
X
(
3
),
F
X
(
2
)
We then observe 2, and the sequence is
x
=
32. Therefore,
F
(
2
)
X
F
(
2
)
X
u
(
2
)
=
l
(
2
)
=
(
32
),
(
31
)
We can compute these values as follows:
F
(
2
)
X
(
32
)
=
P
(
x
=
11
)
+
P
(
x
=
12
)
+···+
P
(
x
=
16
)
+
P
(
x
=
21
)
+
P
(
x
=
22
)
+···+
P
(
x
=
26
)
+
P
(
x
=
31
)
+
P
(
x
=
32
)
But,
i
=
6
i
=
6
P
(
x
=
ki
)
=
P
(
x
1
=
k
,
x
2
=
i
)
=
P
(
x
1
=
k
)
i
=
1
i
=
1
where
x
=
x
1
x
2
. Therefore,
F
(
2
)
X
(
32
)
=
P
(
x
1
=
1
)
+
P
(
x
1
=
2
)
+
P
(
x
=
31
)
+
P
(
x
=
32
)
=
F
X
(
2
)
+
P
(
x
=
31
)
+
P
(
x
=
32
)
