Cryptography Reference
In-Depth Information
More elaborate coding involves transmitting the original message no longer
accompanied by the same word but by a synonym or an equivalent: "dark
dusk", for example. If we receive "dark dust" or "park dusk", correction is
possible by referring to a dictionary of equivalences. The decoding rule would
then be as follows: in the case of an error (if the two words received are not
directly equivalent) and if we can find two equivalent words by changing at
most one letter in the received message, then the correction is adopted, ("dust"
becomes "dusk") and the first of the two words ("dark") is accepted as the
original message. The same would be true if "park dusk" was received, where
the first word would now be corrected. Of course, if a large number of errors
alter the transmission and we receive "park dust", we will probably no longer
understand anything at all. So there is a limit to this error correction capability.
This is the famous
Shannon limit
, that in theory no correcting code can exceed.
Compared to simple repetition, coding by equivalence, which is more e-
cient, uses the
diversity
effect. In this analogy with conversation, this diver-
sity is expressed by a lexicographical property: two distinct words with a close
spelling (dark and lark) are unlikely to have two equivalents ("dusk" and "bird"
for example) that also have a close spelling. Diversity, as presented above, thus
involves constructing a redundant message in a way that minimizes any ambigu-
ity on reception. This is also called temporal diversity as equivalent words in the
message are transmitted at different instants and undergo perturbations of un-
equal intensities. For example, "dark" and "dusk" could be transmitted when a
motorbike or a bicycle, respectively, passed by. In telecommunications systems,
we can search for complementary diversity effects. Frequential diversity involves
cutting up and sending the message in frequency bands that are not perturbed at
the same instant in the same way. As for using several emission and/or reception
antennas, this offers spatial diversity as the paths between antennas do not have
the same behaviour. Jointly exploiting these three types of diversity: temporal,
frequential and spatial, leads to highly ecient communications systems.
Finally, the desire for
parsimony
, or economy, is imposed by the limitation
of resources, either temporal or frequential, of the transmission. The choice of
"dark dusk" is thus certainly more judicious, from the concision point of view,
than "dark night-fall". However, we sense that the latter message might be
more resistant to multiple errors because it is more redundant (the reception
and resolution of "dirk might-fall" is not problematic if we use the decoding law
mentioned above and extend the correction capability to two errors). Searching
for performance via the redundancy rate, and the parsimony constraint are
therefore in total opposition.
Redundant coding is generally simple to implement and the corresponding
software or hardware has low complexity. Decoding, however, requires compu-
tation techniques that can be costly, even if, in fact, the number of instructions
in the program (typically several hundred, in high level computing language) or
the silicon surface occupied (typically several square millimetres) remains low.
