Digital Signal Processing Reference
In-Depth Information
(known as
typical sequences
) is given by:
N
st
=
p
Np
(1
− p
)
N
(1
−p
)
−
1
As:
log
2
p
−Np
(1
p
)
−N
(1
−p
)
=
−
−
Np
log
2
p
−
N
(1
−
p
)log
2
(1
−
p
)=
NH
(
X
)
and the total number of sequences is
L
X
, we find:
N
st
=2
NH
(
X
)
≤
L
X
=2
N
log
2
(
L
X
)
This simply means that, amidst all possible sequences, a certain number has a
probability of zero. It is useless to allow bits for coding sequences which are never
realized!
All of the results presented for
L
X
=2can be generalized when
L
X
>
2.
Equation [4.1] shows that the entropy of a discrete source is either positive or zero.
The entropy is zero when
X
(
n
) is almost certainly equal to a particular value
x
i
;
therefore, the source is totally predictable. The entropy is at a maximum value of
log
2
L
X
when the symbols are equiprobable. We have:
0
≤
H
(
X
)
≤
log
2
L
X
4.2.2.
Coding a source
4.2.2.1.
Definitions
In the previous chapters, the word coding has not been precisely defined. We have
simply said that it involves associating a number,
i
(
n
) or
i
(
m
)
,where
L
=
2
bN
and the parameter
b
specifies the number of bits per sample, with a scalar
x
(
n
) or
a vector
x
(
m
)=[
x
(
mN
)
∈{
1
···
L
}
1)]
t
. In this chapter, the information to
transmit or store, modeled by the random process
X
(
n
), takes its values from a finite
set, the input alphabet
A
X
, and we aim to represent (encode) the different elements of
this set in a way that is both adapted to the transmission channel characteristics and
efficient.
···
x
(
mN
+
N
−
Adapted to the transmission channel characteristics means that the representation
of each input symbol, a code word, can be constructed from elements of another
alphabet which is adapted to the channel. From here onward, assume that this alphabet
is composed of two elements
A
C
=
a
1
,a
2
}
{
, for example, the two usual binary
symbols 0 and 1.
In an efficient manner means that we aim to represent the source by using the least
number of bits, that is, minimizing the average length of the code words. Up until
