Digital Signal Processing Reference
In-Depth Information
The probability of each state can be found by solving the
probability equations:
P(0)
0.4
Both methods can output a zero (meaning to arrive at state
¼
P(0)
P(0
j
0)
þ
P(1)
P(0
j
1)
¼
P(0)
0.8
þ
P(1)
¼
0
circle), either starting from state zero or one.
P(1)
0.2
Both methods can output a one (meaning to arrive at state
¼
P(1)
P(1
j
1)
þ
P(0)
P(1
j
0)
¼
P(1)
0.6
þ
P(0)
¼
0
circle), either starting from state zero or one.
By definition P(0)
þ
¼
1
From this, we can solve for P(0) and P(1):
P(0)
P(1)
¼
{2 / 3}
{1 / 3}
Now we can solve for the entropy associated with each state
circle.
For state zero and state one:
Entropy
0
¼
P(1)
¼
0.8
log
2
(1 / 0.8)
þ
0.2
log
2
(1 / 0.2)
¼
0.258
þ
0.464
0.722 bits
Entropy
1
¼
¼
0.6
log
2
(1 / 0.6)
þ
0.4
log
2
(1 / 0.4)
¼
0.442
þ
0.529
0.971 bits
The entropy of the Markov source or system is then given by:
P(0)
¼
Entropy
0
þ
P(1)
Entropy
1
¼
1/3
0.722
þ
2/3
0.971
¼
0.888 bits
11.4 Predictive Coding
Finding the sequence “HAWAII” is a form of predictive coding.
The probabilities of any Markov source, such as language, can be
mapped in multi-letter sequences with an associated probability.
These in turn can be encoded using Huffman coding methods, to
produce a more efficient representation (fewer number of bits) of
the outcome sequence.
This same idea can be applied to images. As we have previ-
ously seen, video images are built line by line, from top to bottom,
and pixel by pixel, from left to right. Therefore, for a given pixel,
the pixels above and to the left are available to help predict the
next pixel. For our purposes, let us assume an RGB video frame,
with eight bits per pixel and color. Each color can have a value
from 0 to 255.
The unknown value pixel, for each color, can be predicted
from the pixels immediately left, immediately above, and diago-
nally above. Three simple predictors are given in
Figure 11.2
.
The entire frame could be iteratively predicted from just three
initial pixels, but this is not likely to be a very useful prediction.
