Cryptography Reference
In-Depth Information
Asystematicblockcode
C
(
n, k
)
with minimum distance
d
min
can be short-
ened by setting
s<k
data symbols to zero. We thus obtain a systematic linear
code
C
(
n
s
)
.Ofcoursethe
s
symbols set to zero are not transmitted,
but they are retained in order to calculate the
(
n
−
s, k
−
k
)
redundancy symbols. The
minimum distance of a shortened code is always higher than or equal to the
distance of code
C
(
n, k
)
.
−
4.1.5 Product codes
A product code is a code with several dimensions built from elementary codes.
To illustrate these codes, let us consider a product code built from two systematic
block codes
C
1
(
n
1
,k
1
)
and
C
2
(
n
2
,k
2
)
.
Let there be a table with
n
2
rows and
n
1
columns. The
k
2
first rows are
filled with codewords of length
n
1
generated by the code
C
1
(
n
1
,k
1
)
.There-
maining
(
n
2
−
k
2
)
rows are filled by the redundancy symbols generated by the
code
C
2
(
n
2
,k
2
)
;the
k
2
symbols of each of the
n
1
columns being the informa-
tion bits of the code
C
2
(
n
2
,k
2
)
. We can show that the
(
n
2
−
k
2
)
rows of the
table are codewords of code
C
1
(
n
1
,k
1
)
. It results that all the rows of the table
are codewords of
C
1
(
n
1
,k
1
)
and all the columns of the table are codewords of
C
2
(
n
2
,k
2
)
.
The parameters of the two-dimensional product code
C
(
n, k
)
with minimum
distance
d
min
are equal to the product of the parameters of the elementary codes.
d
min
=
d
1
min
d
2
min
n
=
n
1
n
2
k
=
k
1
k
2
where
d
1
min
and
d
2
min
are the minimum distances of codes
C
1
(
n
1
,k
1
)
and
C
2
(
n
2
,k
2
)
respectively.
A two-dimensional product code can be seen as a double serial concatenation
of two elementary codes (see Chapter 6). An encoder
C
1
is fed with
k
2
data
blocks of length
k
1
and it produces
k
2
codewords of length
n
1
that are written
in rows in a matrix. The matrix is read column-wise and produces
n
1
blocks
of symbols of length
k
2
that feed an encoder
C
2
. The latter in turn produces
n
1
codewords of length
n
2
. Figure 4.1 illustrates the implementation of a two-
dimensional product code built from two systematic block codes.
4.1.6 Examples of binary block codes
Parity check code
This code uses a redundancy binary symbol (
n
=
k
+1
) determined in such a
way as to ensure the nullity of the modulo
2
addition of the symbols of each
codeword.
k−
1
c
=
d
0
c
n−
1
d
1
···
d
k−
2
d
k−
1
with
c
n−
1
=
d
j
j
=0
