50
4 Linear Block Codes
4.3.5 The (u|u + v) Construction
The (u|u + v) construction combines two linear codes of same length and defined
over the same field to produce a new linear code whose length is twice as the previous
one.
Definition 4.3.8 Let C 1 and C 2 be two linear codes both over F q with parameters
[n, k 1 , d 1 ] q and [n, k 2 , d 2 ] q , respectively. Define a code C as follows:
C = {(u, u + v)|u ∈ C 1 , v ∈ C 2 }.
The new linear code C has parameters [2n, k 1 + k 2 , min{2d 1 , d 2 }] q .
In order to simplify the notation, the code produced by applying the (u|u + v)
construction to the codes C 1 and C 2 is denoted by (C 1 |C 1 + C 2 ).
Suppose that C i has generator matrix G i and parity check matrix H i , for i = 1, 2.
Then (C 1 |C 1 + C 2 ) has a generator matrix G 1 |G 2 of the form
G 1 |G 2 =
G 1 G 1
0 G 2
and a parity check matrix H 1 |H 2 given by
H 1 |H 2 =
H 1 0
−H 2 H 2
.
We observe that the notations utilized here for a generator G 1 |G 2 and for a parity
check matrix H 1 |H 2 for C are not usual in the literature, but we decide to adopt them
to simplify the understanding of the text.
Exercise 4.3.4 Show that G 1 |G 2 and H 1 |H 2 are a generator and a parity check matrix
for C, respectively.
4.4 Cyclic Codes
In this part, we review the concept of cyclic and BCH codes. For more details, the
reader can consult the textbooks [67, 114].
We assume that q is a prime power and F q is the finite field with q elements. Cyclic
codes form an important class of linear codes. Throughout this book, we always
assume that gcd(q, n) = 1, where n is the code length. Recall that the multiplicative
order of q modulo n ord n (q) is the smallest positive integer m such that n|(q
m
− 1).
Definition 4.4.1 The minimal polynomial over F q of β ∈ F q m is the monic polynomial of smallest degree, M(x), with coefficients in F q such that M(β) = 0. If
4 Linear Block Codes
4.3.5 The (u|u + v) Construction
The (u|u + v) construction combines two linear codes of same length and defined
over the same field to produce a new linear code whose length is twice as the previous
one.
Definition 4.3.8 Let C 1 and C 2 be two linear codes both over F q with parameters
[n, k 1 , d 1 ] q and [n, k 2 , d 2 ] q , respectively. Define a code C as follows:
C = {(u, u + v)|u ∈ C 1 , v ∈ C 2 }.
The new linear code C has parameters [2n, k 1 + k 2 , min{2d 1 , d 2 }] q .
In order to simplify the notation, the code produced by applying the (u|u + v)
construction to the codes C 1 and C 2 is denoted by (C 1 |C 1 + C 2 ).
Suppose that C i has generator matrix G i and parity check matrix H i , for i = 1, 2.
Then (C 1 |C 1 + C 2 ) has a generator matrix G 1 |G 2 of the form
G 1 |G 2 =
G 1 G 1
0 G 2
and a parity check matrix H 1 |H 2 given by
H 1 |H 2 =
H 1 0
−H 2 H 2
.
We observe that the notations utilized here for a generator G 1 |G 2 and for a parity
check matrix H 1 |H 2 for C are not usual in the literature, but we decide to adopt them
to simplify the understanding of the text.
Exercise 4.3.4 Show that G 1 |G 2 and H 1 |H 2 are a generator and a parity check matrix
for C, respectively.
4.4 Cyclic Codes
In this part, we review the concept of cyclic and BCH codes. For more details, the
reader can consult the textbooks [67, 114].
We assume that q is a prime power and F q is the finite field with q elements. Cyclic
codes form an important class of linear codes. Throughout this book, we always
assume that gcd(q, n) = 1, where n is the code length. Recall that the multiplicative
order of q modulo n ord n (q) is the smallest positive integer m such that n|(q
m
− 1).
Definition 4.4.1 The minimal polynomial over F q of β ∈ F q m is the monic polynomial of smallest degree, M(x), with coefficients in F q such that M(β) = 0. If