Cryptography Reference
In-Depth Information
that the
i
-th information bit equals 1. In other words, the
k
markers are the
bases of a vector space of dimension
k
. The codeword is finally made up of the
concatenation of the
k
information bits and of the
n
k
redundancy bits. The
rate
R
of the code is
k/n
. This very simple construction of the codeword relies
on the linearity property of the addition and leads to high minimum distances
for suciently large values of
n
−
k
. Because two codewords are different by at
least one information bit and the redundancy is drawn at random, the average
minimum distance is
1+
n−
2
. However, the minimum distance of this code
being a random variable, its different realizations can be lower than this value.
A simple realistic approximation of the effective minimum distance is
−
n
−
k
4
.
A way to build an almost random encoder is presented in Figure 7.2. It is
a multiple parallel concatenation of circular recursive systematic convolutional
codes (CRSC, see Chapter 5) [7.12]. The sequence of
k
binary data is coded
N
times by
N
CRSC encoders, in a different order each time. The permutations
Π
j
are drawn at random, except the first one that can be the identity permutation.
Each elementary encoder produces
k
N
redundancy symbols (
N
being a divisor
of
k
), the global rate of the concatenated code being 1/2.
The proportion of input sequences of a recursive encoder built from a pseudo-
random generator with memory
ν
, initially positioned in state 0, which return
the register back to the same state at the end of the coding, is:
p
1
=2
−ν
(7.1)
since there are
2
ν
possible return states, with the same probability. These
sequences, called
Return To Zero
(RTZ) sequences,(see Chapter 5), are linear
combinations of the minimum RTZ sequence, which is given by the recursivity
polynomial of the generator (
1+
D
+
D
3
in the case of Figure 7.2).
The proportion of RTZ sequences for the multi-dimensional encoder is low-
ered to:
p
N
=2
−Nν
(7.2)
since the sequence must, after each permutation, remain RTZ for the
N
encoders.
The other sequences, with proportion
1
−
p
N
, produce codewords that have
adistance
d
satisfying:
k
2
N
d>
(7.3)
This worst case value assumes that a single permuted sequence is not RTZ
and that redundancy
Y
takes the value 1, every other time on average, on the
corresponding circle.
If we take
N
=8
and
ν
=3
for example, we obtain
10
−
7
and, for sequences to encode of length
k
= 1024
,wehave
d
min
=64
,
which is a sucient minimum distance if we refer to the curves of Figure 3.6.
Random coding can thus be approximated by using small codes and random
permutations. The decoding can be performed following the turbo principle,
describedinSection7.4for
N
=2
. The scheme of Figure 7.2 is, however, not
used in practice, for reasons linked to the performance and complexity of the
p
8
≈
