Cryptography Reference
In-Depth Information
equiprobability. It is the same with text (for example, the recurrence of "e" in
an English text is on average 5 times higher than that of "f"). The effects of
dependency or disparity in the original message, whether they be of physical,
orthographical or semantic origin or whatever, cannot be exploited by the digital
communication system, which transmits 0s and 1s independently of their con-
text. To transform the original message into a message fulfilling the conditions of
independence and equiprobability, an operation called source coding, or digital
compression, can be performed. Today, compression norms like JPEG, MPEG,
ZIP, MUSICAM, etc. are well integrated into the world of telecommunications,
the Internet in particular. At the output of the source encoder, the statistical
properties of independence and equiprobability are generally respected and the
compressed message can then be processed by the channel encoder, which will
add redundancy mathematically exploitable by the receiver.
1.2
A first code
Figure 1.1 shows an electronic circuit that performs a very simple, easily decod-
able correction encoding. The code implemented is an extended Hamming code,
which was used in teletext (one of the first digital communication systems),
which will also be presented in Chapter 4.
Figure 1.1 - Extended Hamming encoder: a simple, easily decodable code.
The encoder contains four identical operators performing the exclusive-or
function. The exclusive-or (XOR) of
k
binary values
b
0
,
b
1
, ...,
b
k−
1
is calculated
as:
k−
1
XOR
(
b
0
,b
1
, ..., b
k−
1
)=
b
0
⊕
b
1
⊕
...
⊕
b
k−
1
=
b
p
modulo 2
(1.2)
p
=0
It is therefore quite simply 0 if the number of logical 1s appearing in the input
sequence is even and 1 in the opposite case.
In the sequel, when modulo 2
