Databases Reference
In-Depth Information
A
0
1
C
0
0
B
Cloning
1
0
A
C
0
1
0
B
C'
0
F I GU R E 6 . 4
The cloning process.
represent it. In order to avoid this, instead of counting from zero, we start the count of 1s and
0s with a small number
c
and estimate the probabilities as
n
0
+
c
P
(
0
|
V
)
=
n
0
n
1
+
+
2
c
n
1
+
c
(
|
)
=
P
1
V
n
0
n
1
+
+
2
c
Whenever we have two branches leading to a state, it can be cloned. And, theoretically,
cloning is never harmful. By cloning we are providing additional information to the encoder.
This might not reduce the rate, but it should never result in an increase in the rate. However,
cloning does increase the complexity of the coding, and hence the decoding, process. In order
to control the increase in the number of states, we should only perform cloning when there
is a reasonable expectation of a reduction in rate. We can do this by making sure that both
paths leading to the state being considered for cloning are used often enough. Consider the
situation shown in Figure
6.4
. Suppose the current state is
A
and the next state is
C
. As there
are two paths entering
C
,
C
is a candidate for cloning. Cormack and Horspool suggest that
C
be cloned if
n
0
T
1
and
n
0
T
2
, where
T
1
and
T
2
are threshold values set by the user. If
there are more than three paths leading to a candidate for cloning, then we check that both the
number of transitions from the current state is greater than
T
1
and the number of transitions
from all other states to the candidate state is greater than
T
2
.
Finally, what do we do when, for practical reasons, we cannot accommodate any more
states? A simple solution is to restart the algorithm. In order to make sure that we do not start
from ground zero every time, we can train the initial state configuration using a certain number
of past inputs.
>
>
