Cryptography Reference
In-Depth Information
k
mod 7
1
2
3
4
5
6
s
k
0
0
0
0
0
0
0
1
6
3
5
4
2
7
2
4
7
3
1
5
6
3
2
4
6
5
7
1
4
7
5
2
6
1
3
5
1
6
7
2
3
4
6
3
2
1
7
4
5
7
5
1
4
3
6
2
Table 5.2 -
Table of the CRSC code with generator polynomials
[1
,
(1+
D
2
+
D
3
)
/
(1 +
D
+
D
3
)]
providing the circulation state as a function of
k
mod 7
(
k
being
the length of the frame at the input) and of the terminal state
s
k
obtained after
encoding initialized to state 0.
3. Calculate the circulation state
s
c
from the tables already calculated and
stored;
4. Initialize the encoder to state
s
c
;
5. Code the frame and transmit the redundancies calculated.
5.5.2 Puncturing
Some applications can only allocate a small space for the redundant part of the
codewords. But, by construction, the natural rate of a systematic convolutional
code is
m/
(
m
+
n
)
,where
m
is the number of input bits
d
i
of the encoder and
n
is the number of output bits. It is therefore maximum when
n
=1
and becomes
R
=
m/
(
m
+1)
. High rates can therefore only be obtained with high values
of
m
. Unfortunately, the number of transitions leaving any one node of the
trellis is
2
m
. In other words, the complexity of the trellis, and therefore of the
decoding, increases exponentially with the number of input bits of the encoder.
Therefore, this solution is generally not satisfactory. It is often avoided in favour
of a technique with a slightly lower error correction capability, but easier to
implement:
puncturing
.
The puncturing technique is commonly used to obtain high rates. It involves
using an encoder with a low value of
m
(1 or 2 for example), to keep a reasonable
decoding complexity, but transmitting only part of the bits coded. An example
is proposed in Figure 5.25. In this example, a
1
/
2
rate encoder produces outputs
d
i
and
r
i
at each instant
i
. Only 3 bits out of 4 are transmitted, which leads to
aglobalrateof
2
/
3
. The pattern in which the bits are punctured is called the
puncturing mask.
