Cryptography Reference
In-Depth Information
Chapter 1
Introduction
Redundancy, diversity and parsimony are the keywords of error correction cod-
ing. To these, on the decoding side, can be added eciency, that is, making the
most of all the information available. To illustrate these concepts, consider a
simple situation in everyday life.
Two people are talking near a road where there is quite heavy trac. The
noise of the engines more or less disrupts their conversation, with peaks of
perturbation noise corresponding to the vehicles going past. First assume that
one of the people regularly transmits one letter chosen randomly: "a", "b" ... or
any of the 26 letters of the alphabet, with the same probability (that is, 1/26).
The message does not contain any other information and there is no connection
between the sounds transmitted. If the listener doesn't read the speaker's lips,
he will certainly often be at a loss to recognize certain letters. So there will be
transmission errors.
Now, in another scenario, one of the two people speaks in full sentences, on a
very particular topic, for example, the weather. In spite of the noise, the listener
understands what the speaker says better that when he says individual letters,
because the message includes
redundancy
. The words are not independent and
the syllables themselves are not concatenated randomly. For example, we know
that after a subject we generally have a verb, and we guess that after "clou",
there will be "dy" even if we cannot hear properly, etc. This redundancy in the
construction of the message enables the listener to understand it better in spite
of the dicult transmission conditions.
Suppose that we want to improve the quality of the transmission even further,
in this conversation that is about to take an unexpected turn. To be sure of
being understood, the speaker repeats some of the words, for example "dark
dark". However, after the double transmission, the receiver has understood
"dark lark". There is obviously a mistake somewhere, but is it "dark" or "lark"
that the receiver is supposed to understand? No error correction is possible
using this repetition technique, except maybe to transmit the word more than
twice. "dark lark dark" can, without any great risk of error, be translated as
"dark".
