Cryptography Reference
In-Depth Information
1.1
Digital messages
A digital message is a sequence of characters or symbols taken from an alphabet
of finite size. Genetic information (DNA), to take a natural example, uses an
alphabet of four characters, denoted A, T, G and C, that stand for the initials
of their nitrogen bases (adenine, thymine, guanine, and cytosine). The first
digital transmission technique was Morse code (1832), with its two-character
audio alphabet:
TIT
or dot, a short tone lasting four hundredths of a second
and
TAT
or dash, a long tone lasting twelve hundredths of a second. Samuel
F. B. Morse could well have called these characters 0 and 1, which today are
the universal names used in any alphabet with two elements or binary alphabet.
The binary elements, 0 and 1, were first called
bits
by J. W. Tukey (1943), as a
contraction of
binary digit
, after rejecting
bigit
and
binit
. Shannon borrowed the
term when he wished to introduce the concept of unit of information. Today, it
is preferable to refer to this unit of information as the
Shannon
, to distinguish
it from the bit, which has acquired a more electronic meaning.
An alphabet having
M
symbols is called an
M
-ary alphabet. It can be
transcribed into a binary alphabet by representing each of the
M
symbols by a
word of
m
bits, with:
m
=
log
2
(
M
)
+1
if
M
is not a power of 2
(1.1)
or:
m
=log
2
(
M
)
if
M
is a power of 2
where
denotes the whole part of
x
. Multimedia messages (voice, music,
fixed and moving images, text etc.) transiting through communication systems
or stocked in mass memories, are exclusively binary. However, in this topic
we shall sometimes have to consider alphabets with more than two elements.
This will be the case in Chapter 4, to introduce certain algebraic codes. In
Chapters 2 and 10, which deal with modulations, the alphabets, which we then
more concretely call constellations, contain a number of symbols that are a power
of 2, that is, we have precisely:
m
=log
2
(
M
)
.
Correction coding techniques are only implemented on digital messages.
However, there is nothing against constructing a redundant analogue message.
For example, an analogue signal, in its temporal dimension, accompanied or fol-
lowed by its frequential representation obtained thanks to the Fourier transform,
performs a judiciously redundant coding. However, this technique is not very
simple and the decoder remains to be invented.
Furthermore, the digital messages that we shall be considering in what fol-
lows, before the coding operation has been performed, will be assumed to be
made up of binary elements that are mutually independent and taking the values
0 and 1 with the same probability, that is,
1
/
2
. The signals that are produced
by a sensor like a microphone or a camera, and then digitized to become bi-
nary sequences, do not generally satisfy these properties of independence and
x
