Cryptography Reference
In-Depth Information
By permuting the first two vectors of the canonical base of
F
2
, we obtain a new
generator matrix of the same parity check code:
G
=
011
101
In this example, we have just seen that the generator matrix of a block code is
not unique. By permuting the rows or the columns of a generator matrix or by
adding one or several other rows to a row, which means considering a new base
in
F
2
, it is always possible to write a generator matrix of a block code in the
following form:
⎡
⎣
⎤
⎦
10
···
0
p
0
,
1
···
p
0
,l
···
p
0
,n−k
01
···
0
p
1
,
1
···
p
1
,l
···
p
1
,n−k
G
=
I
k
P
=
(4.6)
.
.
.
.
.
.
···
···
···
00
...
1
p
k−
1
,
1
...
p
k−
1
,l
...
p
k−
1
,n−k
where
I
k
is the identity matrix
k
×
k
and
P
amatrix
k
×
(
n
−
k
)
used to calculate
the
(
n
k
)
redundancy symbols.
Written thus, the generator matrix
G
is in a reduced form and produces code-
words of the form:
−
c
=
dd
P
(4.7)
The code is therefore systematic. Following 4.7, the code is said to be systematic
when there exist
k
indices
i
0
,i
1
,...,i
k−
1
, such that for any data word
d
,the
associated codeword
c
satisfies the relation:
c
i
q
=
d
q
,
q
=0
,
1
,
···
,k
−
1
.
4.1.2 Dual code and parity check matrix
Before tackling the notion of dual code, let us define the orthogonality between
two vectors made up of
n
symbols. Two vectors
x
=[
x
0
···
x
j
···
x
n−
1
]
and
y
=[
y
0
···
y
j
···
y
n−
1
]
are orthogonal (
x
⊥
y
)
if their scalar product denoted
x
,
y
is null.
n−
1
x
⊥
y
⇔
x
,
y
=
x
j
y
j
=
0
j
=0
With each linear block code
C
(
n, k
)
, we can associate a dual linear block
code that verifies that any word of the dual code is orthogonal to any word of
the code
C
(
n, k
)
. The dual of code
C
(
n, k
)
is therefore a vector subspace of
F
2
made up of
2
n−k
codewords of
n
symbols. This vector subspace is the orthogonal
