Cryptography Reference
In-Depth Information
lower bounded by the limit obtained by a binary input and upper bounded by
a continuous input.
The first results were given by Shannon [3.4] and by the so-called sphere-
packing bound method which provides a lower bound on the error probability
of random codes on a Gaussian channel. We again assume maximum likelihood
decoding. A codeword of length n is a sequence of n whole numbers. Geometri-
cally, this codeword can be assimilated to a point in an n -dimensional Euclidean
space and the noise can be seen as a displacement of this point towards a neigh-
bouring point following a Gaussian distribution (see Section 3.1.4). Denoting P
the power of the emitted signal, all the codewords are situated on the surface of
a sphere of radius nP .
Observingthatwehaveacodewith 2 k points (codewords), each at a distance
nP from the origin in n -dimensional space, any two points are equidistant from
the origin, and consequently, the bisector of these two points (a hyperplane of
dimension n
1 ) passes through the origin. Considering the set of 2 k points
making up the code, all the hyperplanes pass through the origin and form pyra-
mids with the origin as the summit. The error probability, after decoding, is
i =1 Pr( e i ) ,where Pr( e i ) is the probability that the point associated
with the codeword i is moved by the noise outside the corresponding pyramid.
The principle of Shannon's sphere-packing bound involves this geometrical
vision of coding. However, it is very complex to keep the 'pyramid' approach
and the solid angle pyramid Ω i , around the codeword i , is replaced by a cone
with the same summit and the same solid angle Ω i (Figure 3.4).
2 k
Pr( e )= 2 k
Figure 3.4 - Assimilation of a pyramid with one cone in Shannon's so-called sphere-
packing approach.
It can be shown that the probability that the signal remains in the cone is
higher than the probability that it remains in the same solid angle pyramid.
Consequently, the error probability can be lower-bounded in the following way:
2 k
1
2 k
Q i )
Pr ( e )
(3.19)
i =1
denoting Q i ) the probability that the noise moves point i out of the solid
angle cone Ω i (therefore a decoding error is made on this point). We also observe
that, if we consider the set of codewords equally distributed on the surface of
Search WWH ::




Custom Search