Cryptography Reference
In-Depth Information
example) and that the software and/or hardware of this algorithm should not be
too complex. Furthermore, using soft inputs could be an imperative that might
not be simple to satisfy.
Other criteria like decoding speed (that fixes the throughput of the infor-
mation decoded), latency (the delay introduced by the decoding process) or
flexibility (the ability of the code to be defined for various word lengths and
coding rates) are also to be taken into account in the context of the application
targeted.
Finally, non-technical factors may also be very important. Technological
maturity (do applications and standards already exist?), the cost of components,
possible intellectual property rights, strategic preferences or force of habit are
elements that carry weight when choosing a coding solution.
1.7
Families of codes
Up until the last few years, codes were traditionally classified in two families that
were considered to be quite distinct due to their principles and their applications:
algebraic codes
(also called
block codes
)and
convolutional codes
. This distinction
was mainly based on three observations:
•
algebraic codes are appropriate for protecting blocks of data independent
one from the other whereas convolutional codes are suitable for protecting
continuous flows of data,
•
the coding rates of algebraic codes are rather close to unity, whilst convo-
lutional codes have lower rates,
•
block code decoding is rather of the hard input decoding type, and that
of convolutional codes is almost always soft input decoding.
Today, these distinctions are tending to blur. Convolutional codes can easily
be adapted to encode blocks and most decoders of algebraic codes accept soft
inputs. Via concatenation (Chapter 6), algebraic code rates can be lowered to
values comparable with those of convolutional codes. One difference remains,
however, between the two sub-families: the number of possible logical states of
algebraic encoders is generally very high, which prevents decoding by exhaustive
state methods. Decoding algorithms are based on techniques specific to each
code. Convolutional encoders have a limited number of states, 2 to 256 in
practice, and their decoding uses a complete representation of states, called
a trellis (Chapter 5). It is for this reason that the topic is structured in a
traditional manner, which, for the time being, makes the distinction between
algebraic codes and convolutional codes.
Modern coding requires concatenated or composite structures, which use sev-
eral elementary encoders and whose decoding is performed by repeated passages
