Chapter 4
Linear Block Codes
4.1 Introduction
As usual, in this chapter we consider that p denotes a prime number, q is a prime
power and F q is the finite field with q elements. We begin by defining the general
concept of a code over F q ; after this, we present the concept of a linear code that is
the more important class of codes in coding and information theory due to its vector
space structure. In this subsection, the vectors are written in bold.
Definition 4.1.1 Assume that F
n
q is the vector space (over F q ) of all n-tuples in F q .
Then an (n, M) code C over F q is a subset of F
n
q of size M. If c = (a 1 , a 2 , . . . , a n ) ∈
F
n
q is such that c ∈ C, then the vector c is called codeword of C.
To work with codes without structures is really hard. In this book, we only deal
with linear codes, i.e., codes with a vector space structure.
Definition 4.1.2 A linear code C over F q of length n and dimension k is a kdimensional F q -subspace of F
n
q . Such codes are denoted by [n, k]. We say that n
and k are the parameters of the code.
Since the dimension of C is equal to k and because the field F q has q elements,
it follows that the number of codewords of (a linear code) C is equal to q
k .
There exist two usual ways of defining a linear code: by means of generator
matrices or based on parity check matrices.
Definition 4.1.3 Let C be a linear code over F q with parameters [n, k]. A generator
matrix G for C is a k × n matrix with entries in F q such that the rows of G form a
basis for C.
In general, a generator matrix of a linear code is not unique. However, in the case
below one has the uniqueness.
Definition 4.1.4 Let C be a linear code over F q with parameters [n, k]. If the first
k coordinates form an information set, then C has a unique generator matrix of the
© Springer Nature Switzerland AG 2020
G. G. La Guardia, Quantum Error Correction, Quantum Science and Technology,
https://doi.org/10.1007/978-3-030-48551-1_4
43
Linear Block Codes
4.1 Introduction
As usual, in this chapter we consider that p denotes a prime number, q is a prime
power and F q is the finite field with q elements. We begin by defining the general
concept of a code over F q ; after this, we present the concept of a linear code that is
the more important class of codes in coding and information theory due to its vector
space structure. In this subsection, the vectors are written in bold.
Definition 4.1.1 Assume that F
n
q is the vector space (over F q ) of all n-tuples in F q .
Then an (n, M) code C over F q is a subset of F
n
q of size M. If c = (a 1 , a 2 , . . . , a n ) ∈
F
n
q is such that c ∈ C, then the vector c is called codeword of C.
To work with codes without structures is really hard. In this book, we only deal
with linear codes, i.e., codes with a vector space structure.
Definition 4.1.2 A linear code C over F q of length n and dimension k is a kdimensional F q -subspace of F
n
q . Such codes are denoted by [n, k]. We say that n
and k are the parameters of the code.
Since the dimension of C is equal to k and because the field F q has q elements,
it follows that the number of codewords of (a linear code) C is equal to q
k .
There exist two usual ways of defining a linear code: by means of generator
matrices or based on parity check matrices.
Definition 4.1.3 Let C be a linear code over F q with parameters [n, k]. A generator
matrix G for C is a k × n matrix with entries in F q such that the rows of G form a
basis for C.
In general, a generator matrix of a linear code is not unique. However, in the case
below one has the uniqueness.
Definition 4.1.4 Let C be a linear code over F q with parameters [n, k]. If the first
k coordinates form an information set, then C has a unique generator matrix of the
© Springer Nature Switzerland AG 2020
G. G. La Guardia, Quantum Error Correction, Quantum Science and Technology,
https://doi.org/10.1007/978-3-030-48551-1_4
43