Cryptography Reference
In-Depth Information
One of the major results of information theory is the so-called
fundamental
theorem of information theory
. It basically says that it is possible to transmit
information through a noisy channel at any rate less than channel capacity with an
arbitrarily small error probability. There are many terms (e.g., “information,” “noisy
channel,” “transmission rate,” and “channel capacity”) that need to be clarified
before the theorem can be applied in some meaningful way. Nevertheless, an inital
example may provide some preliminary ideas about the fundamental theorem of
information theory.
Imagine a source of information that generates a sequence of bits at the rate
of one bit per second. The bits 0 and 1 occur equally likely and are generated
independently from each other. Suppose that the bits are communicated over a noisy
channel. The nature of the noisy channel is unimportant, except that the probability
that a particular bit is received in error is 1
/
4 and that the channel acts on successive
inputs independently. The statistical properties of the corresponding noisy channel
are illustrated in Figure 5.2. We further assume that bits can be transmitted over the
channel at a rate not to exceed one bit per second.
1*4
*4
*4
1*4
Figure 5.2
The statistical properties of a noisy channel.
If an error probability of 1
/
4 is too high for a specific application, then one
must find ways of improving the reliability of the channel. One way that immediately
comes to mind is transmitting each source bit over the noisy channel more than once
(typically an odd number of times). For example, if the source generated a zero, then
one could transmit a sequence of three zeros, and if the source generated a one, then
one could send a sequence of three ones. At the destination, one receives a sequence
of three bits for each source bit (i.e., bit generated by the source). Consequently, one
faces the problem of how to properly decode each sequence (i.e., make a decision,
for each sequence received, as to the identity of the source bit). A reasonable way to
decide is by means of a majority selector, meaning that there is a rule that if more
ones than zeros are received, then the sequence is decoded as a one, and if more
zeros than ones are received, then the sequence is decoded as a zero. For example,
if the source generated a one, then a sequence of three ones would be transmitted
over the noisy channel. If the first and third bits were received incorrectly, then the
