Block Error-Correcting Codes 2003
Block Error-Correcting Codes 2003
A computational primer
on
BLOCK ERROR-CORRECTING CODES
January 2003
January 2003
c Sebastià Xambó i Descamps
Departament de Matemàtica Aplicada II
Universitat Politècnica de Catalunya
email: [Link]@[Link]
Preface
In this book, the mathematical aspects in our presentation of the basic theory
of block error-correcting codes go together, in mutual reinforcement, with
computational discussions, implementations and examples of all the relevant
concepts, functions and algorithms. We hope that this approach will facilitate
the reading and be serviceable to mathematicians, computer scientists and
engineers interested in block error-correcting codes.2
In this hypertex pdf version, the examples can be run with just a mouse
click. Moreover, the examples can be modified by users and saved to their
local facilities for later work.
The program that handles the computations in the examples, together
with the interface that handles the editing (mathematics and text), here will
be called WIRIS/cc. More specifically, WIRIS stands for the interface, the
(remote) computational engine and the associated language, and cc stands
for the extension of WIRIS that takes care of the computational aspects that
are more specific of error-correcting codes.
WIRIS/cc is an important ingredient in our presentation, but we do not
presuppose any knowledge of it. As it is very easy to learn and use, it is
introduced gradually, according to the needs of our presentation. A succint
description of the functions used can be found in the Index-Glossary at the
end. The Appendix is a summary of the main features of the system.
This book represents the author’s response to the problem of teaching a
one-semester course in coding theory under the circumstances that will be
explained in a moment. Hopefully it will be useful as well for other teachers
1
Cognitive Research Center at the Universitat Autònoma de Barcelona, interviewed by
Lluís Amiguet in “la contra”, LA VANGUARDIA, 22/08/2002.
2
A forerunner of this approach was outlined in [34].
Preface iii
Acknowledgements
students and colleagues for the everyday give-and-take that certainly has in-
fluenced a lot the final form of this text. Joan Bruna, for example, suggested
an improvement in the implementation of the Meggitt decoder that has been
included in Section 3.4.
Part of the material in this text, and especially the software aspects, were
presented and discussed in the EAGER school organized by Mina Teicher
and Boris Kunyavski from the Emmy Noether Institute (German Minerva
Center) at Eilat (Israel, January 12-16, 2003). I am grateful to the organiz-
ers for this opportunity, and to all the participants for their eager inquiring
about all aspects of the course. In particular, I have to thank Shmulik Ka-
plan for suggesting an improvement of the alternant decoder implementation
presented in Section 4.3.
Grateful thanks are due to Thomas Hintermann for sharing his enlight-
ening views on several aspects of writing, and especially on English writing.
They have surely contributed to improve this work, but of course only the au-
thor is to be found responsible for the mistakes and blunders that have gone
through undetected.
And thanks to my wife, Elionor Sedó. Without her enduring support
and love it would not have been possible to dedicate this work to her on the
occasion of our thirtieth wedding anniversary, for it would hardly have been
finished.
The author
L’Escala
20/1/03
Introduction
Assume that you are asked to make sense of a ‘sentence’ like this: “Coding
theary zs bodh wntelesting and challenning” (to take a simpler example than
the Chinese saying in the quotation).
3
“While his incredible inventive mind enriched many fields, Claude Shannon’s enduring
fame will surely rest on his 1948 paper A methematical theory of Communication and the on-
going revolution in information technology it engendered” (Solomon W. Golomb, in “Claude
Elwood Shannon (1916-2001)”, Notices of the AMS, volume 49, number 1, p. 8).
2 Introduction
You realize that this proposed text has mistakes and after a little inspec-
tion you conclude that most likely the writer meant “Coding theory is both
interesting and challenging”.
Why is this so? Look at ‘challenning’, for example. We recognize it is
a mistake because it is not an English word. But it differs from the English
word ‘challenging’ in a single letter. In fact, we do not readily find other
English words that differ from ‘challenning’ in a single letter, and thus any
other English word that could be meant by the writer seems much more
unlikely than ‘challenging’. So we ‘correct’ ‘challenning’ to ‘challenging’.
A similar situation occurs with the replacement of ‘theary’ by ‘theory’. Now
in ‘bodh’, if we were to change a single letter to get an English word, we
would find ‘bode, ‘body” or ‘both’, and from the context we would choose
‘both’, because the other two do not seem to make sense.
There have been several implicit principles at work in our correction pro-
cess, including contextual information. For the purposes of this text, how-
ever, the main idea is that most English words contain redundancy in the
sense that altering one letter (or sometimes even more) will usually still al-
low us to identify the original word. We take this word to be the correct one,
because, under reasonable assumptions on the source of errors, we think that
it is the most likely.
Similar principles are the cornerstones of the theory and practice of error-
correcting codes. This can be illustrated with a toy example, which, despite
its simplicity, has most of the key features of channel coding.
Suppose we have to transmit a stream of bits u1 u2 u3 · · · (thus ui ∈
{0, 1} for all i) through a ‘noisy channel’ and that the probability that one
bit is altered is p. We assume that p is independent of the position of the bit
in the stream, and of whether it is 0 or 1. This kind of channel is called a
binary symmetric channel with bit-error rate p.
In order to try to improve the quality of the information at the receiving
end, we may decide to repeat each bit three times (this is the redundancy we
add in this case). Since for each information bit there are three transmission
bits, we say that this coding scheme has rate 1/3 (it takes three times longer
to transmit a coded message than the uncoded one). Thus every information
bit u is coded into the code word uuu (or [u u u] if we want to represent
it as a vector). In particular, we see that there are two code words, 000
and 111. Since they differ in all three positions, we say that the minimum
distance of the code is 3. The fact that the code words have 3 bits, that each
corresponds to a single information bit, and that the two code-words differ in
Introduction 3
p0 = 3p2 (1 − p) + p3 ,
we see that p0 /p, which can be called the error-reduction factor of the code,
is equal to
3p(1 − p) + p2 = 3p − 2p2 = 3p(1 − 32 p)
1/2
0 0.19 1/2
0 1/2 1
Figure 2: Graph of the capacity C(p), p ∈ [0, 1], for a binary symmetric channel
ber less than the capacity C of a binary symmetric channel (so 0 < R < C),
and ε is any positive real number, then there are ‘codes’ with rate at least R
and with a probability of code-error less than ε (we refer to [29], [15] or [24]
for details).
Shannon’s theorem shows that in theory it is possible to transmit infor-
mation with sufficient confidence and with a transmission time increase by
a factor that can be as close to 1/C as desired. Unfortunately, his methods
only show the existence of such codes, but do not produce them, nor their
coding and decoding, in an effective way. It can be said that the main motiva-
tion of the theory of error-correcting codes in the last half century has been,
to a great extent, to find explicit codes with good rates, small code-error
probabilities and with fast coding and decoding procedures.
Let us return to the Rep(3) example in order to explain how we are going
to deal with the algorithmic and computing issues. In this case we would like
to define two functions, say f and g, that express, in a computational sense,
the coding and the decoding we have been discussing. The result could be
as in 1 The code Rep(3) (click on this label). In this case it is a Library, with a
Library Area (the area inside the rectangle below the title) and a Computation
Area (the area below the Library Area).
The syntax and semantics of the expressions is explained in more detail
in the Appendix, but it should be clear enough at this point. The relevant
comment to be made here is that labels such as The code Rep(3) are linked
to suitable files. When we click on a label, the corresponding file is displayed
on an WIRIS screen, and at that moment all the power of WIRIS/cc is available
to the user.
There are two main kinds of tasks that we can do.
One is modifying the code in the Library area. This is illustrated in
2 An alternative decoder for Rep (3): we have added the function h, which is
WIRIS/cc
As indicated before, we use WIRIS/cc for all the algorithmic and program-
ming aspects. It may be thought of as the conjunction of the general purpose
language of WIRIS and the special library cc for the treatment of block error-
correcting codes. This language has been designed to be close to accepted
mathematical practices and at the same time encompass various program-
ming paradigms. As with the mathematics, its features will be described
when they are needed to understand the examples without assuming pro-
gramming skills on the part of the reader.
As an illustration, let us look at the decoder function g for the Rep(3)
code which, for the reader’s convenience, we reproduce in the link 4 Decoder
for Rep(3). The formal parameter of g is a length 3 vector [a b c]. Since
the components of this vector are named symbolically, and the names can be
used in the body of the function (that is, the code written after :=), we see
that WIRIS supports ‘pattern-matching’. In this case, the body of the function
is an if ... then ... else ... end expression. The value of this expression is a
when a and b are equal or when a and c are equal, and it is b when b and c
are equal.
Of course, WIRIS can be used for many purposes other than codes. Figure
2 on page 4, for example, has been generated as indicated in the link 5 The
capacity function. 5
The goal of this text is to present the basic mathematical theory of block
error-correcting codes together with its algorithmic and computational as-
5
The graph is generated by evaluating the expressions that appear on the WIRIS screen
when we click on this link.
Introduction 7
pects. Thus we will deal not only with the mathematics involved, but also
with the related algorithms and with effective ways of programming these
algorithms. This treatment has been illustrated already in the case of the
repetition code Rep(3) above: we have listed there, after explaining the con-
cepts of coder and decoder, a translation of them as algorithms (the functions
f and g) and programs (in this case, the fact that f and g can be loaded and
run by a computer).
The book has four chapters. The first is a broad introduction to the subject
of block error-correcting codes. After a first section devoted to the presen-
tation of the basic concepts, we study linear codes and the basic computa-
tional issues of the syndrome-leader decoder. The third section is devoted to
Hadamard codes, which in general are non-linear, and in the fourth section
we study the more outstanding bounds on the parameters of codes.
The second chapter is an independent introduction to finite fields and
their computational treatment to the extent that they are needed later. Usually
it is prefarable to cover its contents as the need arises while working on the
material of the last two chapters.
Chapter 3 is devoted to cyclic codes, and to one of their practical decod-
ing schemes, namely the Meggitt decoder. This includes a presentation of
the two Golay codes, including its Meggitt decoding. The important Bose–
Chaudhuri–Hocquenghem codes, a subfamily of the cyclic codes, are also
considered in detail.
Chapter 4 is the culmination of the text in many respects. It is de-
voted to alternant codes, which are generally not cyclic, and to their main
decoders (basically the Berlekamp–Massey–Sugiyama decoder, based on
the Euclidean division algorithm, and the Peterson–Gorenstein–Zierler al-
gorithm, based on linear algebra, as well as some interesting variations of
the two). It is to be noted that these decoders are applicable to the classi-
cal Goppa codes, the Reed–Solomon codes (not necessarily primitive), and
the Bose–Chaudhuri–Hocquenghem codes (that include the primitive Reed–
Solomon codes).
Chapter summary
• We have introduced the repetition code Rep(3) for the binary sym-
metric channel, and Shannon’s celebrated formula for its capacity,
C = 1 + p log2 (p) + (1 − p) log2 (1 − p), where p is the bit-error
rate of the channel.
• Assuming p is small, the quotient of the code-error rate p0 of Rep(3)
over the bit-error rate p is aproximately 3p. Hence, for example, if
8 Introduction
there is one bit error per thousand bits transmited (on average), then
using the code will amount to about three bit errors per million bits
transmitted (on average).
• There is a paper version of this book in which all the links are ex-
panded into suitable listings.
• The goal of this text is to present in the simplest possible terms, and
covering systematically the most relevant computational aspects, some
of the main breakthroughs that have occurred in the last fifty years in
the quest of explicit codes, and efficient procedures for coding and
decoding them, that approach Shannon’s theoretical limit ever more
closely.
Exercises and Problems. They are labeled E.m.n and P.m.n, respectively,
where n is the n-th exercise or problem within chapter m. Problems are
grouped in a subsection at the end of each section, whereas exercises are
inserted at any place that seems appropriate.
Mathematics and WIRIS/cc. In the text, the expression of mathematical
objects and the corresponding WIRIS/cc expression are written in different
types. This translation may not be done if the mathematical and WIRIS syn-
taxes are alike, especially in the case of symbolic expressions. For example,
we do not bother in typesetting a..b or x|x’ for the WIRIS/cc expressions of
the mathematical range a..b or the concatenation x|x0 of the vectors x and x0 .
Introduction 9
Note that there may be WIRIS/cc objets (like Range, a type) that are not
assigned an explicit formal name in the mathematical context.
The ending symbol . In general this symbol is used to signal the end
of a block (for example a Remark) that is followed by material that is not
clearly the beginning of another block. An exception is made in the case of
proofs: we always use the symbol to denote the end of a proof, even if after
it there is a definite beginning of a new block. On the other hand, since the
end of theorems without proof is always clear, the symbol is never used in
that case.
Quality improvement. We would be very appreciative if errors and sugges-
tions for improvements were reported to the author at the following email
address: [Link]@[Link].
1 Block Error-correcting Codes
The goal of this chapter is the study of some basic concepts and construc-
tions pertaining to block error-correcting codes, and of their more salient
properties, with a strong emphasis on all the relevant algorithmic and com-
putational aspects.
The first section is meant to be a general introduction to the theory of
block error-correcting codes. Most of the notions are illustrated in detail
with the example of the Hamming [7,4,3] code. Two fundamental results on
the parameters of a block code are proved: the Hamming upper-bound and
the Gilbert lower-bound.
In the second section, we look at linear codes, also from a general point
of view. We include a presentation of syndrome decoding. The main exam-
ples are the Hamming codes and their duals and the (general) Reed–Solomon
codes and their duals. We also study the Gilbert–Varshamov condition on the
parameters for the existence of linear codes and the MacWilliams identities
between the weight enumerators of a linear code and its dual.
Special classes of non-linear codes, like the Hadamard and Paley codes,
are considered in the third section. Some mathematical preliminairies on
Hadamard matrices are developed at the beginning. The first order Reed–
Muller codes, which are linear, but related to the Hadamard codes, are also
introduced in this section.
The last section is devoted to the presentation of several bounds on the
parameters of block codes and the corresponding asymtotic bounds. Sev-
eral procedures for the construction of codes out of other codes are also
discussed.
1.1. Basic concepts 11
Essential points
• The definition of block code and some basic related notions (code-
words, dimension, transmission rate, minimum distance, equivalence
criteria for block codes).
• The definition of decoder and of the correcting capacity of a decoder.
• The minimum distance decoder and its error-reduction factor.
• The archtypal Hamming code [7,4,3] and its computational treatment.
• Basic dimension upper bounds (Singleton and Hamming) and the no-
tions of MDS codes and perfect codes.
• The dimension lower bound of Gilbert.
Introductory remarks
The fundamental problem of communication is that of repro-
ducing at one point either exactly or approximately a message
selected at another point.
C. E. Shannon 1948, [25].
channel) in some physical form that need not concern us here.1 As a result, a
stream of symbols chosen from T arrives at the receiving end of the channel.
The channel is said to be noiseless if the sent and received symbols al-
ways agree. Otherwise it is said to be noisy, as real channels almost always
are due to a variety of physical phenomena that tend to distort the physical
representation of the symbols along the channel.
The transfer from the source to the sending end of the channel requires
an encoder, that is, a function f : S → T ∗ from the set of source symbols
into the set T ∗ of finite sequences of transmission symbols. Since we do not
want to loose information at this stage, we will always assume that encoders
are injective. The elements of the image of f are called the code-words of
the encoder.
In this text we will consider only block encoders, that is, encoders with
the property that there exists a positive integer n such that C ⊆ T n , where
C = f (S) is the set of code words of the encoder. The integer n is called the
length of the block encoder.
For a block encoding scheme to make sense it is necessary that the source
generates the symbols at a rate that leaves enough time for the opperation of
the encoder and the channel transmission of the code-words. We always
will assume that this condition is satisfied, for this requirement is taken into
account in the design of communications systems.
Since for a block encoder the map f : S → C is bijective, we may con-
sider as equivalent the knowledge of a source symbol and the corresponding
code word. Generally speaking this equivalence holds also at the algorithmic
level, since the computation of f or of its inverse usually can be efficiently
managed. As a consequence, it will be possible to phrase the main issues
concerning block encoders in terms of the set C and the properties of the
channel. In the beginning in next section, we adopt this point of view as a
general starting point of our study of block codes and, in particular, of the
decoding notions and problems.
1.1 Remarks. The set {0, 1} is called the binary alphabet and it is very
widely used in communications systems. Its two symbols are called bits.
With the addition and multiplication modulo 2, it coincides with the field Z2
of binary digits. The transposition of the two bits (0 7→ 1, 1 7→ 0) is called
negation. Note that the negation of a bit b coincides with 1 + b.
Block codes
If C is a code of length n, we will set kC = logq (|C|) and we will say that
kC is the dimension of C. The quotient RC = kC /n is called transmission
rate, or simply rate, of C.
1.3 Remarks. These notions can be clarified in terms of the basic notions
explained in the first subsection (Introductory remarks). Indeed, logq (|T n |) =
logq (q n ) = n is the number of transmission symbols of any element of T n .
So kC = logq (|C|) = logq (|S|) can be seen as the number of transmis-
sion symbols that are needed to capture the information of a source symbol.
Consequently, to send the information content of kC transmission symbols
(which, as noted, amounts to a source symbol) we need n transmission sym-
bols, and so RC represents the proportion of source information contained
in a code word before transmission. An interesting and useful special case
occurs when S = T k , for some positive integer k. In this case the source
symbols are already resolved explicitely into k transmission symbols and we
have kC = k and RC = k/n.
If C has length n and dimension k (respectively |C| = M ), we say that
C has type [n, k] (respectively type (n, M )). If we want to have q explicitely
in the notations, we will write [n, k]q or (n, M )q . We will often write C ∼
[n, k] to denote that the type of C is [n, k], and similar notations will be used
for the other cases.
14 Chapter 1. Block Error-correcting Codes
Minimum distance
Virtually all research on error-correcting codes has been based
on the Hamming metric.
W.W. Peterson and E.J. Weldon, Jr., [19], p. 307.
where |x| is the number of non-zero entries of x (it is called the weight of x)
and x · y = (x1 y1 , · · · , xn yn ).
We will set d = dC to denote the minimum of the distances hd (c, c0 ), where
c, c0 ∈ C and c 6= c0 , and we will say that d is the minimum distance of C.
Note that for the minimum distance to be defined it is necessary that |C| > 2.
For the codes C that have a single word, we will see that it is convenient to
put dC = n + 1 (see the Remark 1.12).
We will say that a code C is of type [n, k, d] (or of type (n, M, d)), if
C has length n, minimum distance d, and its dimension is k (respectively
|C| = M ). If we want to have q explicitely in the notations, we will write
[n, k, d]q or (n, M, d)q . In the case q = 2 it is usually omitted. Sometimes
we will write C ∼ [n, k, d]q to denote that the type of C is [n, k, d]q , and
similar notations will be used for the other cases.
The rational number δC = dC /n is called relative distance of C.
E.1.3. Let C be a code of type (n, M, d). Check that if k = n, then d = 1.
Show also that if M > 1 (in order that d is defined) and d = n then M 6 q,
hence kC 6 1.
1.1. Basic concepts 15
1.4 Example (A binary code (8,20,3)). Let C be the binary code (8, 20) con-
sisting of 00000000, 11111111 and all cyclic permutations of 10101010,
11010000 and 11100100. From the computation in the link 6 Cyclic shifts of
a vector it is easy to infer that dC = 3. Thus C is a code of type (8, 20, 3).
1.5 Remark. A code with minimum distance d detects up to d − 1 errors, in
the sense that the introduction of a number of errors between 1 and d − 1 in
the transmission gives rise to a word that is not in C. Note that d − 1 is the
highest integer with this property (by definition of d).
Equivalence criteria
We will say that two codes C and C 0 of length n are strictly equivalent if
C 0 can be obtained by permuting the entries of all vectors in C with some
fixed permutation. This relation is an equivalence relation on the set of all
codes of length n and by definition we see that it is the equivalence relation
that corresponds to the natural action of Sn on T n , and hence also on subsets
of T n .
In the discussion of equivalence it is convenient to include certain per-
mutations of the alphabet T in some specified positions. This idea can be
formalized as follows. Let Γ = (Γ1 , . . . , Γn ), where Γi is a subgroup of per-
mutations of T , that is, a subgroup of Sq (1 6 i 6 n). Then we say that two
codes C and C 0 are Γ-equivalent if C 0 can be obtained from C by a permuta-
tion σ ∈ Sn applied, as before, to the entries of all vectors of C, followed by
permutations τi ∈ Γi of the symbols of each entry i, i = 1, . . . , n. If Γi = Sq
for all i, instead of Γ-equivalent we will say Sq -equivalent, or simply equiv-
alent. In the case in which T is a finite field F and Γi = F − {0}, acting on F
by multiplication, instead of Γ-equivalent we will also say F-equivalent, or
F∗ -equivalent, or scalarly equivalent.
Note that the identity and the transposition of Z2 = {0, 1} can be repre-
sented as the operations x 7→ x+0 and x 7→ x+1, respectively, and therefore
the action of a sequence τ1 , . . . , τn of permutations of Z2 is equivalent to the
addition of the vector τ ∈ Zn2 that corresponds to those permutations.
In general it is a relatively easy task, given Γ, to obtain from a code C
other codes that are Γ-equivalent to C, but it is much more complicated to
16 Chapter 1. Block Error-correcting Codes
Decoders
The essential ingredient in order to use a code C ⊆ T n at the receiving end
of a channel to reduce the errors produced by the channel noise is a decoding
function. In the most general terms, it is a map
g : D → C, where C ⊆ D ⊆ T n
such that g(x) = x for all x ∈ C. The elements of D, the domain of g, are
said to be g-decodable. By hypothesis, all elements of C are decodable. In
case D = T n , we will say that g is a full decoder (or a complete decoder).
We envisage g working, again in quite abstract terms, as follows. Given
x ∈ C, we imagine that it is sent through a communications channel. Let
y ∈ T n be the vector received at the other end of the channel. Since the
channel may be noisy, y may be different from x, and in principle can be any
vector of T n . Thus there are two possibilities:
• if y ∈ D, we will take the vector x0 = g(y) ∈ C as the decoding of y;
• otherwise we will say that y is non-decodable, or that a decoder error
has occurred.
Note that the condition g(x) = x for all x ∈ C says that when a code
word is received, the decoder returns it unchanged. The meaning of this is
that the decoder is assuming, when the received word is a code-word, that it
was the transmitted code-word and that no error occurred.
If we transmit x, and y is decodable, it can happen that x0 6= x. In this
case we say that an (undetectable) code error has occurred.
Correction capacity
We will say that the decoder g has correcting capacity t, where t is a positive
integer, if for any x ∈ C, and any y ∈ T n such that hd (x, y) 6 t, we have
y ∈ D and g(y) = x.
1.1. Basic concepts 17
1.6 Example. Consider the code Rep(3) and its decoder g considered in the
Introduction (page 2). In this case T = {0, 1}, C = {000, 111} and D =
T 3 , so that it is a full decoder. It corrects one error and undetectable code
errors are produced when 2 or 3 bit-errors occur in a single code-word.
1.7 Remark. In general, the problem of decoding a code C is to construct D
and g by means of efficient algorithms and in such a way that the correcting
capacity is as high as possible.
1.8 Remarks. The usefulness of the minimum distance decoder arises from
the fact that in most ordinary situations the transmissions x 7→ y that lead to
a decoder error (y 6∈ D), or to undetectable errors (y ∈ D, but hd (y, x) > t)
will in general be less likely than the transmissions x 7→ y for which y is
decodable and g(y) = x.
To be more precise, the minimum distance decoder maximizes the like-
lihood of correcting errors if all the transmission symbols have the same
probability of being altered by the channel noise and if the q − 1 possible
errors for a given symbol are equally likely. If these conditions are satis-
fied, the channel is said to be a (q-ary) symmetric channel. Unless otherwise
declared, henceforth we will understand that ‘channel’ means ‘symmetric
channel’.
18 Chapter 1. Block Error-correcting Codes
Note that the columns of R are the binary vectors of length 3 whose weight is
at least 2. Writing Ir to denote the identity matrix of order r, let G = I4 |RT
and H = R|I3 (concatenate I4 and RT , and also R and I3 , by rows). Note
that the columns of H are precisely the seven non-zero binary vectors of
length 3.
Let S = K 4 (the source alphabet) and T = K (the channel alphabet).
Define the block encoding f : K 4 → K 7 by u 7→ uG = u|uRT . The image
of this function is C = hGi, the K-linear subspace spanned by the rows of
G, so that C is a [7, 4] code. Since
RT
GH T = (I4 |RT ) = RT + RT = 0,
I3
because the arithmetic is mod 2, we see that the rows of G, and hence the
elements of C, are in the kernel of H T . In fact,
C = {y ∈ K 7 | yH T = 0},
as the right-hand side contains C and both expressions are K-linear sub-
spaces of dimension 4. From the fact that all columns of H are distinct,
it is easy to conclude that dC = 3. Thus C has type [7, 4, 3]. Since |C| ·
vol (7, 1) = 24 (1 + 7) = 28 = |K 8 |, we see that DC = K 7 .
As a decoding function we take the map g : K 7 → C defined by the
following recipe:
1.1. Basic concepts 19
Error-reduction factor
Assume that p is the probability that a symbol of T is altered in the transmis-
sion. The probability that j errors occur in a block of length n is
n j
p (1 − p)n−j .
j
Therefore
n t
X n j n−j
X n j
Pe (n, t, p) = p (1 − p) =1− p (1 − p)n−j [1.1]
j j
j=t+1 j=0
gives the probability that t + 1 or more errors occur in a code vector, and
this is the probability that the received vector is either undecodable or that
an undetectable error occurs.
20 Chapter 1. Block Error-correcting Codes
which we will call the error reduction factor of the code, is an upper bound
for the average number of errors that will occur in the case of using cod-
ing per error produced without coding (cf. E.1.8). For p small enough,
ρ(n, t, p) < 1 and the closer to 0, the better error correction resulting from
the code. The value of ρ(n, t, p) can be computed with the function erf(n,t,p).
E.1.3). In fact, the goal of this section, and of later parts of this chapter, is
to establish several non trivial restrictions of those parameters. In practice
these restrictions imply, for a given n, that if we want to improve the rate
then we will get a lower correcting capability, and conversely, if we want to
improve the correcting capability, then the transmission rate will decrease.
1.11 Proposition (Singleton bound). For any code of type [n, k, d],
k + d 6 n + 1.
Proof: Indeed, if C is any code of type (n, M, d), let us write C 0 ⊆ T n−d+1
to denote the subset obtained by discarding the last d − 1 symbols of each
vector of C. Then C 0 has the same cardinal as C, by definition of d, and so
q k = M = |C| = |C 0 | 6 q n−d+1 . Hence k 6 n − d + 1, which is equivalent
to the stated inequality.
MDS codes. Codes that satisfy the equality in the Singleton inequality are
called maximum distance separable codes, or MDS codes for short. The
repetition code Rep(3) and the Hamming code [7,4,3] are MDS codes. The
repetition code of any length n on the alphabet T , which by definition is
Repq (n) = {tn | t ∈ T }, is also an MDS code (since it has q elements, its
dimension is 1, and it is clear that the distance between any two distinct
code-words is n).
Values of A2 (n, d)
n d=3 d=5 d=7
5 4 2 —
6 8 2 —
7 16 2 2
8 20 4 2
9 40 6 2
10 72–79 12 2
11 144–158 24 4
12 256 32 4
13 512 64 8
14 1024 128 16
15 2048 256 32
16 2720–3276 256–340 36–37
as claimed.
The lemma shows that the cardinal of B(x, r) only depends on n and r,
and not on x, and we shall write vol q (n, r) to denote it. By the preceeding
lemma we have
r
X n
vol q (n, r) = |B(x, r)| = (q − 1)i . [1.2]
i
i=0
Proof: Let C be a code of type (n, M, d)q . Taking into account that the
balls of radius t = b(d − 1)/2c and center elements of C are pair-wise dis-
joint (this follows from the definitionPt and the triangular inequality of the
Hamming distance), it turns out that |B(x, t)| 6 |T n | = q n .
x∈C
On the other hand we know that
and hence
qn >
P
|B(x, t)| = M · vol q (n, t).
x∈C
Now if we take C optimal, we get
Aq (n, d)vol q (n, t) 6 q n ,
which is equivalent to the inequality in the statement.
1.15 Remark. The Hamming upper bound is also called sphere-packing up-
per bound, or simply sphere upper bound.
(see the link 10 The sphere upper bound).
E.1.13. Let m and s be integers such that 1 6 s 6 m and let c1 , . . . , cm ∈
Fn , where F is a finite field with q elements. Show that the number of vectors
that are linear combinations of at most s vectors from among c1 , . . . , cm is
bounded above by vol q (m, s).
Perfect codes
In general DC is a proper subset of T n , which means that there are elements
y ∈ T n for which there is no x ∈ C with hd (y, x) 6 t. If DC = T n , then
C is said to be perfect. In this case, for every y ∈ T n there is a (necessarily
unique) x ∈ C such that hd (y, x) 6 t.
Taking into account the reasoning involved in proving the sphere-bound,
we see that the necessary and sufficient condition for a code C to be perfect
is that
t
X n
(q − 1)i = q n /M (= q n−k ),
i
i=0
where M = |C| = qk (this will be called the sphere or perfect condition).
The total code T n and the binary repetion code of odd length are exam-
ples of perfect codes, with parameters (n, q n , 1) and (2m + 1, 2, 2m + 1),
respectively. Such codes are said to be trivial perfect codes. We have also
seen that the Hamming code [7,4,3] is perfect (actually this has been checked
in Example 1.9).
E.1.14. In next section we will see that if q is a prime-power and r a positive
integer, then there are codes with parameters
[(q r − 1)/(q − 1), (q r − 1)/(q − 1) − r, 3]).
Check that these parameters satisfy the condition for a perfect code. Note
that for q = 2 and r = 3 we have the parameters [7,4,3].
1.1. Basic concepts 25
E.1.15. Show that the parameters [23, 12, 7], [90, 78, 5] and [11, 6, 5]3 satisfy
the perfect condition.
E.1.16. Can a perfect code have even minimum distance?
E.1.17. If there is a perfect code of length n and minimum distance d, what
is the value of Aq (n, d)? What is the value of A2 (7, 3)?
E.1.18. Consider the binary code consisting of the following 16 words:
d and with a greater cardinal than |C|, contradicting the optimality of C. This
means that the union of the balls of radius d − 1 and with center the elements
of C is the whole T n . From this it follows that Aq (n, d)· vol q (n, d−1) > q n .
Thus we have proved the following:
1.17 Theorem (Gilbert lower bound). The function Aq (n, d) satisfies the fol-
lowing inequality:
qn
Aq (n, d) > .
vol q (n, d − 1)
What is remarkable about the Gilbert lower bound, with the improvement
we will find in the next chapter by means of linear codes, is that it is the
only known general lower bound. This is in sharp contrast with the variety
of upper bounds that have been discovered and of which the Singleton and
sphere upper bounds are just two cases that we have already established.
(See the link 11 Gilbert lower bound).
1.18 Remark. The Hamming and Gilbert bounds are not very close. For
example, we have seen that 7 6 A2 (8, 3) 6 28, 12 6 A2 (9, 3) 6 51,
19 6 A2 (10, 3) 6 93 and 31 6 A2 (11, 3) 6 170. But in fact A2 (8, 3) =
20 (we will get this later, but note that we already have A2 (8, 3) > 20 by
E.1.4), A2 (9, 3) = 40 and the best known intervals for the other two are
72 6 A2 (10, 3) 6 79 and 144 6 A2 (11, 3) 6 158 (see Table 1.1).
E.1.19. The sphere upper bound for codes of type (6, M, 3) turns out to be
M 6 9 (check this), but according to the table 1.1 we have A2 (6, 3) = 8,
so that there is no code of type (6, 9, 3). Prove this. Hint: assuming such a
code exists, show that it contains three words that have the same symbols in
the last two positions.
Summary
Problems
P.1.1 (Error-detection and correction). We have seen that a code C of type
(n, M, d) can be used to detect up to d − 1 errors or to correct up to t =
b(d − 1)/2c errors. Show that C can be used to simultaneously detect up to
s > t errors and correct up to t errors if t + s < d.
P.1.2 Prove that A2 (8, 5) = 4 and that all codes of type (8, 4, 5)2 are equiv-
alent. Hint: by replacing a binary optimal code of length 8 and minimum
distance 5 by an equivalent one, we may assume that 00000000 is a code
word and then there can be at most one word of weight > 6.
P.1.3. Show that for binary codes of odd minimum distance the Hamming
upper bound is not worse than the Singleton upper bound. Is the same true
for even minimum distance? And for q-ary codes with q > 2?
P.1.4 Prove that A2 (n, d) 6 2A2 (n − 1, d). Hint: if C is an optimal binary
code of length n and minimum distance d, we may assume, changing C into
an equivalent code if necessary, that both 0 and 1 appear in the last position
of elements of C, and then it is useful to consider, for i = 0, 1, the codes
Ci = {x ∈ C | xn = i}.
P.1.5 (Plotkin construction, 1960). Let C1 and C2 be binary codes of types
(n, M1 , d1 ) and (n, M2 , d2 ), respectively. Let C be the length 2n code whose
words have the form x|(x + y), for all x ∈ C1 and y ∈ C2 . Prove that
C ∼ (2n, M1 M2 , d), where d = min(2d1 , d2 ).
28 Chapter 1. Block Error-correcting Codes
P.1.6 Show that A2 (16, 3) > 2560. Hint: use Example E.1.4 and the Plotkin
construction.
P.1.7 If C ∼ (n, M, 7) is a perfect binary code, prove that n = 7 or n = 23.
Hint: use the sphere upper bound.
P.1.8. Show that there is no code with parameters (90, 278 , 5). Hint: Ex-
tracted from [9], proof of Theorem 9.7: if C were a code with those param-
eters, let X be the set of vectors in C that have weight 5 and begin with two
1s, Y the set of vectors in Z90
2 that have weight 3 and begin with two 1s, and
D = {(x, y) ∈ X × Y | S(y) ⊂ S(x)}, and count |D| in two ways (S(x) is
the support of x, that is, the set of indices i in 1..90 such that xi = 1).
1.2. Linear codes 29
Essential points
Introduction
The construction of codes and the processes of coding and decoding are
computationally intensive. For the implemetation of such opperations any
additional structure present in the codes can be of much help.
In order to define useful structures on the codes, a first step is to enrich
the alphabet T with more structure than being merely a set. If we want, for
example, to be able to add symbols with the usual properties, we could use
the group Zq as T . Since this is also a ring, the alphabet symbols could
also be multiplied.2 If we also want to be able to divide symbols, then we
are faced with an important restriction, because division in Zq by nonzero
elements is possible without exception if and only if q is prime.
We will have more room in that direction if we allow ourselves to use
not only the fields Zp , p prime, but also all other finite fields (also called
Galois fields). As we will see in the next chapter in detail, there is a field of
q elements if and only if q is a power of a prime number, and in that case the
2
For an interesting theory for the case T = Z4 , see Chapter 8 of [29].
30 Chapter 1. Block Error-correcting Codes
simply write Mnk (F) to denote the matrices of type k × n with coefficients
in F. Instead of Mkk (F) we will write Mk (F).
The usual scalar product of x, y ∈ Fn will be denoted hx|yi:
hx|yi = xy T = x1 y1 + . . . + xn yn .
Weights
We will let | | : Fn → N denote the map x 7→ d(x, 0). By definition, |x| is
equal to the number of non-zero symbols of x ∈ Fn . We will say that |x|,
which sometimes is also denoted wt (x), is the weight of x.
E.1.20. The weight is a norm for the space Fn : for all x, y, z ∈ Fn , |0| = 0,
|x| > 0 if x 6= 0, and |x + y| 6 |x| + |y| (triangle inequality).
If C is a linear code, then the minimum weight of C, wC , is defined as
the minimum of the weights |x| of the non-zero x ∈ C.
1.20 Proposition. The minimum weight of C coincides with the minimum
distance of C: dC = wC .
Proof: Let x, y ∈ C. If C is linear, then x − y ∈ C and we have hd (x, y) =
|x − y|. Since x − y 6= 0 if and only if x 6= y, we see that any distance
between distinct elements is the weight of a nonzero vector. Conversely,
since |x| = hd (x, 0), and 0 ∈ C because C is linear, the weight of any
nonzero vector is the distance between two distinct elements of C. Now the
claimed equality follows from the definitions of dC and wC .
1.21 Remark. For a general code C of cardinal M , the determination of dC
involves the computation of the M (M − 1)/2 Hamming distances between
its pairs of distinct elements. The proposition tells us that if C is linear then
the determination of dC involves only the computation of M − 1 weights.
This is just an example of the advantage of having the additional linear struc-
ture.
It is important to take into account that the norm | | and the scalar product
h | i are not related as in Euclidean geometry. In the geometrical context we
have the formula |x|2 = hx|xi (by definition of |x|), while in the present
context |x| and hx|xi have been defined independently. In fact they are quite
unrelated, if only because the values of the norm are non-negative integers
and the values of the scalar product are elements of F.
E.1.21. Let C be a linear code of type [n, k] over F = Fq . Fix any integer
j such that 1 6 j 6 n. Prove that either all vectors of C have 0 at the
j-th position or else that every element of F appears there in precisely q k−1
vectors of C.
32 Chapter 1. Block Error-correcting Codes
E.1.22. Given a binary linear code C, show that either all its words have
even weight or else there are the same number of words with even and odd
weight. In particular, in the latter case |C| is even.
Generating matrices
Given a code C of type [n, k], we will say that a matrix G ∈ Mnk (F) is a
generating matrix of C if the rows of G form a linear basis of C.
Conversely, given a matrix G ∈ Mnk (F) the subspace hGi ⊆ Fn gener-
ated by the rows of G is a code of type [n, k], where k is the rank of G. We
will say that hGi is the code generated by G.
E.1.23. The elements x ∈ Fn+1 such that s(x) = 0 form a code C of type
[n + 1, n] (it is called the zero-parity code of length n + 1, or of dimension
n). Check that the matrix (In |1Tn ) is a generating matrix of C.
Coding
It is clear that if G is a generating matrix of C, then the map
f : Fk → Fn , u 7→ uG
Parity-check matrices
If H is a generating matrix of C ⊥ (in which case H is a matrix of type
(n − k) × n) we have that
The relation
C = {x ∈ Fn |xH T = 0}
can also be interpreted by saying that C is the set of linear relations satisfied
by the rows of H T , that is, by the columns of H. In particular we have:
1.25 Proposition. If any r − 1 columns of H are linearly independent, then
the minimum distance of C is at least r, and conversely.
1.26 Example (The dual of an RS code). Let C = RS α1 ,...,αn (k), where α =
α1 , . . . , αn are distinct nonzero elements of a finite field K. Then we know
that G = Vk (α1 , . . . , αn ) is a generating matrix of C (Example 1.24). Note
that the rows of G have the form (α1i , . . . , αni ), with i = 0, . . . , k − 1.
Now we are going to describe a check matrix H of C, that is, a generating
matrix of C ⊥ . Recall that if we define D(α1 , . . . , αn ) as the determinant of
the Vandermonde matrix Vn (α1 , . . . , αn ) (Vandermonde determinant), then
Y
D(α1 , . . . , αn ) = (αj − αi ).
i<j
(remark that in the last product there are precisely i − 1 factors with the
indices reversed, namely the αj − αi with j < i). Then the matrix
is a check matrix of C.
To see this, it is enough to prove that any row of G is orthogonal to any
row of H because H has clearly rank n − k. Since the rows of H have the
form (h1 α1j , . . . , hn αnj ), with j = 0, . . . , n − k − 1, we have to prove that
n
αli+j hl = 0 if 0 6 i 6 k−1 and 0 6 j 6 n−k−1. Thus it will be enough
P
l=1
n
αls hl = 0 (0 6 s 6 n − 2). Multiplying throughout by the
P
to prove that
l=1
nonzero determinant D(α1 , . . . , αn ), and taking into account the definition
of hl , we wish to prove that
n
αls (−1)l−1 D(α1 , . . . , αl−1 , αl+1 , . . . , αn ) = 0.
P
l=1
36 Chapter 1. Block Error-correcting Codes
But finally this is obvious, because the left hand side coincides with the
determinant
α1s ... αns
1 ... 1
α1 . . . αn
.. ..
. .
α1n−2 . . . αnn−2
(developed along the first row), and this determinant has a repeated row.
As we will see in Chapter 4, the form of the matrix H indicates that
RS α (k) is an alternant code, and as a consequence it will be decodable with
any of the fast decoders for alternant codes studied in that chapter (sections
4.3 and 4.4).
E.1.27. Check that the dual of an RS (n, k) code is scalarly equivalent to an
RS (n, n− k). In particular we see that the dual of a RS code is an MDS
code.
Let us consider now the question of how can we obtain a check matrix from
a generating matrix G. Passing to an equivalent code if necessary, we may
assume that G = (Ik |P ) and in this case we have:
1.27 Proposition. If G = (Ik |P ) is a generating matrix of C, then H =
(−P T |In−k ) is a generating matrix of C ⊥ (note that −P T = P T in the
binary case).
Proof: Indeed, H is a matrix of type (n − k) × n and its rows are clearly
linearly independent. From the expressions of G and H it is easy to check
that GH T = 0 and hence hHi ⊆ C T . Since both terms in this inclusion
have the same dimension, they must coincide.
1.28 Example. In the binary case, the matrix H = (1k |1) is a check matrix
of the parity-check code C ∼ [k + 1, k], which is defined as the parity ex-
Pk+1 of the total code of dimension k. The only check equation for C is
tension
i=1 xi = 0, which is equivalent to say that the weight |x| is even for all x.
For the repetition code of length n relative to an arbitrary finite field F,
the vector 1n = (1|1n−1 ) is a generating matrix and H = (1Tn−1 |In−1 ) is a
check matrix. Note that the check equations corresponding to the rows of H
are xi = x1 for i = 2, . . . , n.
1.29 Example. If H is a check matrix for a code C of type [n, k], then
1n 1
H=
H 0Tn−k
is a check matrix of C.
Indeed, as seen in Example 1.26, there is a check matrix Q of C that has
the form Vn−k (α1 , . . . , αn )diag (h1 , . . . , hn ), with hi = 1/ j6=i (αj − αi ),
and in the present case we have hi = αi (as argued in a moment), so that
V1,n−k (α1 , . . . , αn ) = Vn−k (α1 , . . . , αn )diag (α1 , . . . , αn ) is a check ma-
trix of C.
Q
To see that hi = αi , first note that j6=i (αj − αi ) is the product of all
the elements of F∗ , except −αi . Hence hi = −αi /P , where P is the product
of all the elements of F∗ . And the claim follows because P = −1, as each
factor in P cancels with its inverse, except 1 and −1, that coincide with their
own inverses.
Remark that the dual of RS α1 ,...,αn (k) is not an RS α1 ,...,αn (n − k), be-
cause H = V1,n−k (α1 , . . . , αn ) is not Vn−k (α1 , . . . , αn ). But on dividing
the j-th column of H by αj we see that the dual of RS α1 ,...,αn (k) is scalarly
equivalent to RS α1 ,...,αn (n − k).
E.1.29. In Proposition 1.27 the matrix Ik occupies the first k columns, and
P the last n − k. This restriction can be easily overcome as follows. Assume
that Ik is the submatrix of a matrix G ∈ Mnk (F) formed with the columns
k (F) be the matrix left from G after remov-
j1 < · · · < jk , and let P ∈ Mn−k
ing these columns. Show that we can form a check matrix H ∈ Mnn−k (F) by
placing the columns of −P T successively in the columns j1 , . . . , jk and the
columns of In−k successively in the remaining columns. [For an illustration
of this recipe, see the Example 1.36]
E.1.30. We have seen (E.1.27; see also Example 1.30) that the dual of an
RS code is scalarly equivalent to a RS code. Since RS codes are MDS, this
leads us to ask whether the dual of a linear MDS code is an MDS code.
Prove that the answer is affirmative and then use it to prove that a linear code
[n, k] is MDS if and only if any k columns of a generating matrix are linearly
independent.
38 Chapter 1. Block Error-correcting Codes
Syndrome decoding
Let C be a code of type [n, k] and H a check matrix of C. Given y ∈ Fn ,
the element
yH T ∈ Fn−k
is called the syndrome of y (with respect to H). From what we saw in the last
subsection, the elements of C are precisely those that have null syndrome:
C = {x ∈ Fn | xH T = 0}.
More generally, given s ∈ Fn−k , let Cs = {z ∈ Fn | zH T = s} (hence
C0 = C). Since the map σ : Fn → Fn−k such that y 7→ yH T is linear,
surjective (because the rank of H is n − k) and its kernel is C, it follows that
Cs is non-empty for any s ∈ Fn−k and that Cs = zs + C for any zs ∈ Cs .
In other words, Cs is a class modulo C (we will say that it is the class of the
syndrome s).
The notion of syndrome is useful in general for the purpose of minimum
distance decoding of C (as it was in particular for the Hamming [7,4,3] code
in example 1.9). The key observations we need are the following. Let g be
the minimum distance decoder. Let x ∈ C be the transmitted vector and y
the received vector. We know that y is g-decodable if and only if there exists
x0 ∈ C such that hd (y, x0 ) 6 t, and in this case x0 is unique and g(y) = x0 .
With these notations we have:
1.32 Lemma. The vector y is g-decodable if and only if there exists e ∈ Fn
such that yH T = eH T and |e| 6 t, and in this case e is unique and g(y) =
y − e.
Proof: If y is g-decodable, let x0 = g(y) and e = y − x0 . Then eH T =
yH T − x0 H T = yH T , because the syndrome of x0 ∈ C is 0, and |e| =
d(y, x0 ) 6 t.
Conversely, let e satisfy the conditions in the statement and consider the
vector x0 = y − e. Then x0 ∈ C, because x0 H T = yH T − eH T = 0 (by the
first hypothesis on e) and d(y, x0 ) = |e| 6 t. Then we know that x0 is unique
(hence e is also unique) and that g(y) = x0 (so g(y) = y − e).
1.2. Linear codes 39
Leaders’ table
The preceeding considerations suggest the following decoding scheme. First
precompute a table E = {s → es }s∈Fn−k with es ∈ Cs and in such a way
that es has minimum weight among the vectors in Cs (the vector es is said
to be a leader of the class Cs and the table E will be called a leaders’ table
for C). Note that es is unique if |es | 6 t (exercise E.1.31); otherwise we will
have to select one among the vectors of Cs that have minimum weight. Now
the syndrome decoder can be described as follows:
2) look at the leaders’ table E to find es , the leader of the class corre-
sponding to s;
3) return y − es .
s, because
eH T = yH T − xH T = s.
Since es has minimum weight among the vectors of syndrome s, |es | 6 |e| 6
t. So e = es (E.1.31) and g(y) = y − es = y − e = x, as claimed.
1.35 Remarks. With the syndrome decoder there are no docoder errors, for
the table E = {s → es } is extended to all s ∈ Fn−k , but we get an unde-
tectable error if and only if e = y − x is not on the table E.
For the selection of the table values es the following two facts may be
helpful:
a) Let e0s be any element with syndrome s. If the class e0s + C contains
an element e such that |e| 6 t, then e is the only element in Cs with
this property (E.1.31) and so es = e.
b) If the submatrix of H formed with its last n−k columns is the identity
matrix In−k (note that this will happen if H has been obtained from
a generating matrix G of C of the form (Ik |P )), then the element
e0s = (0k |s) has syndrome s and hence the search of es can be carried
out in Cs = e0s + C. Moreover, it is clear that for all s such that |s| 6 t
we have es = e0s .
1.36 Example. See the link 16 A binary example of sydrome decoding for
how the computations have been arranged. Let C = hGi, where
1 1 0 0 1
G = 0 0 1 0 1 ∈ M53 (Z2 ).
1 0 0 1 1
min_weights, which yields, given a list of vectors, the list of those that have
minimum weight in that list. We get:
M = {[0, 0] → {[0, 0, 0, 0, 0]}, [0, 1] → {[0, 0, 0, 0, 1], [0, 0, 1, 0, 0]},
[1, 0] → {[1, 0, 0, 0, 0]}, [1, 1] → {[0, 0, 0, 1, 0], [0, 1, 0, 0, 0]}}.
[0, 1], [0, 2], [1, 0], [1, 1], [2, 0], [2, 2]
while
C[1,2] = {[0, 0, 0, 1, 2], [0, 0, 2, 0, 2], [0, 1, 0, 1, 0], [0, 1, 2, 0, 0],
[1, 0, 0, 0, 1], [1, 2, 0, 0, 0], [2, 0, 0, 2, 0], [2, 0, 1, 0, 0]}
(C[2,1] is obtained by multiplying all the vectors in C[1,2] by 2). With all this,
it is immediate to set up the syndrome-leader table E. The link contains the
example of decoding the vector y = [1, 1, 1, 1, 1].
Complexity
Assuming that we have the table E = {es }, the decoder is as fast as the
evaluation of the product s = yH T and the looking up on the table E. But
42 Chapter 1. Block Error-correcting Codes
where ai is the number of code vectors that have weight i (1 6 i 6 n). What
is the probability of retransmission when this code is used in incomplete
decoding?
= (1 + (q − 1))d−2 = q d−2 ,
Hamming codes
Hamming codes were discovered by Hamming (1950) and Go-
lay (1949).
R. Hill, [9], p. 90.
agrees with the observation made in E.1.33. It also follows by induction from
the fact that Pr−1 = P(Fr ) is the disjoint union of an affine space Ar−1 ,
whose cardinal is q r−1 , and a hyperplane, which is a Pr−2 .
It is clear that two Hamming codes of the same codimension are scalarly
equivalent. We will write Hamq (r) to denote any one of them and Ham∨q (r) to
denote the corresponding dual code, that is to say, the code generated by the
check matrix H used to define Hamq (r). By E.1.33, it is clear that Hamq (r)
has dimension k = n − r = (q r − 1)/(q − 1) − r. Its codimension, which
is the dimension of Ham∨q (r), is equal to r.
1.40 Example. The binary Hamming code of codimension 3, Ham2 (3), is
the code [7, 4] that has
1 0 0 1 1 0 1
H = 0 1 0 1 0 1 1
0 0 1 0 1 1 1
as check matrix. Indeed, the columns of this matrix are all non-zero binary
vectors of length 3 and in the binary case two non-zero vectors are linearly
independent if and only if they are distinct.
E.1.34. Compare the binary Hamming matrix of the previous example with
a binary normalized Hamming matrix of codimension 3, and with the matrix
H of the Hamming [7, 4, 3] code studied in the Example 1.9.
1.41 Proposition. If C is any Hamming code, then dC = 3. In particular,
the error-correcting capacity of a Hamming code is 1.
Proof: If H is a check matrix of C, then we know that the elements of C are
the linear relations satisfied by the columns of H. Since any two columns
of H are linearly independent, the minimum distance of C is at least 3. On
the other hand, C has elements of weight 3, because the sum of two columns
of H is linearly independent of them and hence it must be proportional to
another column of H (the columns of H contain all non-zero vectors of Fr
up to a scalar factor).
1.42 Proposition. The Hamming codes are perfect.
Proof: Since Hamq (r) has type [(q r − 1)/(q − 1), (q r − 1)/(q − 1) − r, 3],
we know from E.1.14 that it is perfect. It can be checked directly as well:
the ball of radius 1 with center an element of Fn contains 1 + n(q − 1) = q r
elements, so the union of the balls of radius 1 with center an element of C is
a set with q n−r q r = q n elements.
1.43 Proposition. If C 0 = Ham∨q (r) is the dual of a Hamming code C =
Hamq (r), the weight of any non-zero element of C 0 is q r−1 . In particular, the
distance between any pair of distinct elements of C 0 is q r−1 .
46 Chapter 1. Block Error-correcting Codes
a1 x1 + . . . + ar xr = 0.
Since {P1 , . . . , Pn } = Pr−1 (cf. Remark 1.39), it follows that the number of
non-zero components of z is the cardinal of the complement of a hyperplane
of Pr−1 . Since this complement is an affine space Ar−1 , its cardinal is q r−1
and so any non-zero element of C 0 has weight q r−1 .
Codes such that the distance between pairs of distinct elements is a fixed
integer d are called equidistant of distance d. Thus Ham∨q (r) is equidistant
of distance q r−1 .
E.1.35. Find a check matrix of Ham7 (2), the Hamming code over F7 of codi-
mension 2, and use it to decode the message
3523410610521360.
Weight enumerator
n
X
A(t) = Ai t i ,
i=0
for the term ti appears in this sum as many times as the number of solutions
of the equation |x| = i, x ∈ C.
Note that A0 = 1, since 0n is the unique element of C with weight 0.
On the other hand Ai = 0 if 0 < i < d, where d is the minimum distance
of C. The determination of the other Ai is not easy in general and it is one
of the basic problems of coding theory.
1.2. Linear codes 47
MacWilliams identities
A situation that might be favorable to the determination of the weight enu-
merator of a code is the case when it is constructed in some prescribed way
from another code whose weight enumerator is known. Next theorem (7),
which shows how to obtain the weight enumerator of C ⊥ from the weight
enumerator of C (and conversely) is a positive illustration of this expectation.
Remark. In the proof of the theorem we need the notion of character of
a group G, which by definition is a group homomorphism of G to U (1) =
{z ∈ C | |z| = 1}, the group of complex numbers of modulus 1. The constant
map g 7→ 1 is a character, called the unit character. A character different
from the unit character is said to be non-trivial and the main fact we will
need is that the additive group of finite field Fq has non-trivial characters.
Actually any finite abelian group has non-trivial characters. Let us sketch
how this can be established.
It is known that any finite abelian group G is isomorphic to a product of
the form
Zn1 × · · · × Znk ,
with k a positive integer and n1 , . . . , nk integers greater than 1. For example,
in the case of a finite field Fq , we have (if q = pr , p prime),
Fq ' Zrp
since Fq is vector space of dimension r over Zp . In any case, it is clear that if
we know how to find a non-trivial character of Zn1 then we also know how to
find a non-trivial character of G (the composition of the non-trivial character
of Zn1 with the projection of Zn1 × · · · × Znk onto Zn1 gives a non-trivial
character of G). Finally note that if n is an integer greater than 1 and ξ 6= 1
is an n-th root of unity then the map χ : Zn → U (1) such that χ(k) = ξ k is
well defined and is a non-trivial character of Zn .
E.1.36. Given a group G, the set G∨ of all characters of G has a natural
group structure (the multiplication χχ0 of two characters χ and χ0 is defined
by the relation (χχ0 )(g) = χ(g)χ0 (g)) and with this structure G∨ is called
the dual group of G. Prove that if n is an integer greater than 1 and ξ ∈ U (1)
is a primitive n-th root of unity, then there is an isomorphism Zn ' Z∨n ,
m 7→ χm , where χm (k) = ξ mk . Use this to prove that for any finite abelian
group G there exists an isomorphism G ' G∨ .
1.44 Theorem (F. J. MacWilliams). The weight enumerator B(t) of the dual
code C ⊥ of a code C of type [n, k] can be determined from the weight enu-
merator A(t) of C according to the following identity:
∗ n 1−t
k
q B(t) = (1 + q t) A , q ∗ = q − 1.
1 + q∗t
48 Chapter 1. Block Error-correcting Codes
and χ(γ) 6= 1.
Now consider the sum
X X
S= χ(x, y)t|y| ,
x∈C y∈Fn
If y ∈ C ⊥ , thenP
hx|yi = 0 for all x ∈ C and so χ(x, y) = 1 for all x ∈ C,
and in this case x∈C χ(x, y) = |C|. If y 6∈ C ⊥ , then the map C → F such
that x 7→ hx|yi takes each value of F the same
P number of times (because
Pis an F-linear map) and hence, using that α∈F χ(α) = 0, we have that
it
x∈C χ(x, y) = 0. Putting the two cases together we have that
X
S = |C| t|y| = q k B(t).
y∈C ⊥
On the other hand, for any given x ∈ C, and making the convention, for
all α ∈ F, that |α| = 1 if α 6= 0 and |α| = 0 if α = 0, we have
X X
χ(x, y)t|y| = χ(x1 y1 + . . . + xn yn )t|y1 |+...+|yn |
y∈Fn y1 ,...,yn ∈F
X n
Y
= χ(xi yi )t|yi |
y1 ,...,yn ∈F i=1
Yn X
= χ(xi α)t|α| .
i=1 α∈F
P
because α∈F∗ χ(α) = −1. Consequently
|x|
X
|α| ∗ n 1−t
χ(xi α)t = (1 + q t)
1 + q∗t
α∈F
1−t
S = (1 + q ∗ t)n A ,
1 + q∗t
as stated.
which yields
i6n/2
X n 2i
B(t) = t .
2i
i=0
Note that this could have been written directly, for the binary zero-parity
code of length n has only even-weight words and the number of those having
n
weight 2i is 2i .
or
A(t) = 1 + 7t3 + 7t4 + t7 .
This means that A0 = A7 = 1, A1 = A2 = A5 = A6 = 0 and A3 = A4 =
7. Actually it is easy to find, using the description of this code given in the
example 1.40 (see also the example 1.9) that the weight 3 vectors of Ham(3)
are
[1, 1, 0, 1, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 0]
and the weight 4 vectors are
[1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0], [0, 1, 1, 1, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0],
[0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1]
Note that the latter are obtained from the former, in reverse order, by inter-
changing 0 and 1.
(See the link 20 Weight enumerator of the Hamming code and MacWilliams
identities).
Summary
1.2. Linear codes 51
Problems
P.1.9 The ISBN code has been described in the Example 1.19. Prove that
this code:
If instead of the ISBN weighted check digit relation we used the the relation
P10
i=1 xi ≡0 (mod 11),
1. Show that this code is linear and express each of the five bits of the
code words in terms of the information bits.
2. Find a generating matrix and a check matrix.
3. Write the coset classes of this code and choose a leaders’ table.
4. Decode the word 11111.
P.1.14 Let n = rs, where r and s are positive integers. Let C be the binary
code of length n formed with the words x = a1 a2 . . . an such that, when
arranged in an r × s matrix
a1 ··· ar
ar+1 ··· a2r
.. ..
. .
a(s−1)r+1 · · · asr
the sum of the elements of each row and of each column is zero.
1. Check that it is a linear code and find its dimension and minimum
distance.
2. Devise a decoding scheme.
3. For r = 3 and s = 4, find a generating matrix and a check matrix
of C.
x5 = x2 + x3 + x4
x6 = x1 + x2 + x3
x7 = x1 + x2 + x4
x8 = x1 + x3 + x4
Find a check matrix for C, show that dC = 4 and calculate the weight enu-
merator of C.
P.1.16 (First order Reed–Muller codes). Let Lm be the vector space of poly-
nomials of degree 6 1 in m indeterminates and with coefficients in F. The
elements of Lm are expressions
a0 + a1 X1 + . . . + am Xm ,
Such codes are called (first order) Reed–Muller codes and will be denoted
RM x m x
q (m). In the case n = q , instead of RM q (m) we will simply write
RM q (m) and we will say that this is a full Reed–Muller code. Thus RM q (m) ∼
(q m , m + 1, q m−1 (q − 1)).
1.47 Remark. There are many references that present results on the decod-
ing of RM codes. The following two books, for example, include a lucid and
elementary introduction: [1] (Chapter 9) and [31] (Chapter 4).
1.3. Hadamard codes 55
The first error control code developed for a deep space appli-
cation was the nonlinear (32, 64) code used in the Mariner ’69
mission.
S.B. Wicker, [32], p. 2124.
Essential points
Hadamard matrices
A Hadamard matrix of order n is a matrix of type n × n whose coefficients
are 1 or −1 and such that
HH T = nI.
Note that this relation is equivalent to say that the rows of H have norm
√
n and that any two of them are orthogonal. Since H is invertible and
H T = nH −1 , we see that H T H = nH −1 H = nI and hence H T is also
a Hadamard matrix. Therefore H is a Hadamard matrix if and only if its
√
columns have norm n and any two of them are orthogonal.
If H is a Hadamard matrix of order n, then
det(H) = ±nn/2 .
In particular we see that Hadamard matrices satisfy the equality in the Hada-
mard inequality
n X n
Y 1/2
| det(A)| 6 a2ij ,
i=1 i=1
56 Chapter 1. Block Error-correcting Codes
then H (n) is a normalized Hadamard matrix of order 2n for all n (see the
link 21 Computation of the matrices H (n) ).
It is also easy to check that if H and H 0 are Hadamard matrices of orders
n and n0 , then the tensor product H ⊗ H 0 is a Hadamard matrix of order nn0
(the matrix H ⊗ H 0 , also called the Kronecker product of H and H 0 , can be
defined as the matrix obtained by replacing each entry aij of H by the matrix
aij H 0 ). For example, if H is a Hadamard matrix of order n, then
(1) H H
H ⊗H =
H −H
E.1.38. Check that the function tensor defined in the link 22 Tensor product
of two matrices yields the tensor or Kronecker product of two matrices.
1.48 Proposition. If H is a Hadamard matrix of order n > 3, then n is a
multiple of 4.
1.3. Hadamard codes 57
(1r | − 1r )
and that the third row (which exists because n > 3) has the form
with
s + t = s0 + t0 = r.
Since the third row contains r times 1 and r times −1, we also have that
s + s0 = t + t0 = r.
(1s | − 1t |1t | − 1s ).
Finally the condition that the second and third row are orthogonal yields that
2(s − t) = 0 and hence s = t, r = 2s and n = 4s.
E.1.39. For n = 4 and n = 8, prove that any two Hadamard matrices of
order n are equivalent.
χ : F∗ → {±1}
1) S1Tq = 0Tq 2) 1q S = 0q
3) SS T = qIq − U 4) S T = (−1)(q−1)/2 S.
is −1 for all y 6= 0. To this end, we can assume that the sum is extended
to all elements x such that x 6= 0, −y. We can write x + y = xzx , where
zx = 1 + y/x runs through the elements 6= 0, 1 when x runs the elements
6= 0, −y. Therefore
X X
s= χ(x)2 χ(zx ) = χ(z) = −1.
x6=0,−y z6=0,1
and the preceeding proposition implies that this matrix is equal to nIn . Note
that 1 · 1T = q and 1T · 1 = Uq . We have shown the case +S; the case −S
is analogous.
(see the link 25 Hadamard matrix of a finite field with q + 1 = 0 mod 4).
60 Chapter 1. Block Error-correcting Codes
1.53 Remark. The Hadamard matrices H (2) , H (3) , H (4) , H (5) have orders
4, 8, 16, 32. Theorem 1.51 applies for q = 7, 11, 19, 23, 27, 31 and yields
Hadamard matrices H8 , H12 , H20 , H24 , H28 and H32 . The second part of
the exercise E.1.42 yields Hadamard matrices H 12 , H 20 , H 28 from the fields
F5 , F9 and F13 .
It is conjectured that for all positive integers n divisible by 4 there is a
Hadamard matrix of order n. The first integer n for which it is not known
whether there exists a Hadamard matrix of order n is 428 (see [30] or [2]).
The matrices H (3) and H8 are not equal, but we know that they are
equivalent (see E.1.39). The matrices H12 and H 12 are also equivalent (see
P.1.19). In general, however, it is not true that all Hadamard matrices of the
same order are equivalent (it can be seen, for example, that H20 and H 20 are
not equivalent).
For more information on the present state of knowledge about Hadamard
matrices, see the web page
[Link]
Hadamard codes
One of the recent very interesting and successful applications
of Hadamard matrices is their use as co-called error-correcting
codes.
J.H. van Lint and R.M. Wilson, [30], p. 181.
mit pictures of Mars (this code turns out to be equivalent to the linear code
RM 2 (5); see P.1.21). Each picture was digitalized by subdividing it into
small squares (pixels) and assigning to each of them a number in the range
0..63 (000000..111111 in binary) corresponding to the grey level. Finally
the coding was done by assigning each grey level to a code-word of C in a
one-to-one fashion. Hence the rate of this coding is 6/32 and its correcting
capacity is 7. See figure 1.1 for an upper-bound of the error-reduction factor
of this code. Decoding was done by the Hadamard decoder explained in the
next subsection. For more information on the role and most relevant aspects
of coding in the exploration of the solar system, see [32].
0.0005
0.0004
0.0003
0.0002
0.0001
in columns rather than in rows). Note that for q = 9 we obtain a (9, 20, 4)
code, hence also an (8, 20, 3) code (cf. E.1.4).
Summary
Problems
P.1.17. Compare the error-reduction factor of the binary repetition code of
length 5 with the Hadamard code (32, 64, 16).
P.1.18. Prove that the results in this section allow us to construct a Hadamard
matrix of order n for all n 6 100 divisible by 4 except n = 92.
P.1.19. Prove that any two Hadamard matrices of order 12 are equivalent.
P.1.20. Fix a positive integer r and define binary vectors u0 , . . . , ur−1 so that
where bi (k) is the i-th bit in the binary representation of k. Show that H (r)
coincides with the 2r × 2r matrix (−1)hui |uj i . For the computations related
to this, and examples, see the link 31 Bit-product of integers and Hadamard
matrices.
P.1.21. As seen in P.1.16, the code RM 2 (m) has type (2m , 2m+1 , 2m−1 ).
Prove that this code is equivalent to the Hadamard code corresponding to
the Hadamard matrix H (m) . Thus, in particular, RM 2 (5) is equivalent to the
Mariner code. Hint: If H is the control matrix of Ham2 (m), then the matrix
He obtained from H by first adding the column 0m to its left and then the
row 12m on top is a generating matrix of RM 2 (m).
1.4. Parameter bounds 65
Essential points
Introduction
The parameters n, k (or M ) and d of a code satisfy a variety of relations.
Aside from trivial relations, such as 0 6 k 6 n and 1 6 d 6 n, we know
the Singleton inequality
d6n−k+1
(Proposition 1.11), the sphere upper bound
M 6 q n /vol q (n, t)
then there exists a linear code of type [n, k, d0 ] with d0 > d and hence that
A(n, d) > q k (Theorem 1.38). Moreover, it is not hard to see that this bound
is always equal or greater than the Gilbert bound (see P.1.22).
66 Chapter 1. Block Error-correcting Codes
In this section we will study a few other upper bounds that provide a bet-
ter understanding of the function Aq (n, d) and the problems surrounding its
determination. We include many examples. Most of them have been chosen
to illustrate how far the new resources help (or do not) in the determination
of the values on Table 1.1.
ρz : Fn → Fn−d
the linear map that extracts, from each vector in Fn , the components whose
index is not in S(z). Then we have a linear code ρz (C) ⊆ Fn−d (we will say
that it is the residue of C with respect to z).
If G is a generating matrix of C, then ρz (C) = hρz (G)i, where ρz (G)
denotes the matrix obtained by applying ρz to all the rows of G (we will also
say that ρz (G) is the residue of G with respect to z). Since ρz (z) = 0, it is
clear that dim (ρz (C)) 6 k − 1.
1.57 Lemma. The dimension of ρz (C) is k − 1 and its minimum distance is
at least dd/qe.
Proof: Choose a generating matrix G of C whose first row is z, and let G0 be
the matrix obtained from ρz (G) by omiting the first row (which is ρz (z) =
0). It will suffice to show that the rows of G0 are linearly independent.
To see this, let us assume, to argue by contradiction, that the rows of G0
are linearly dependent. Then there is a non-trivial linear combination x of
the rows of G other than the first such that xi = 0 for i 6∈ S(z) (in other
words, S(x) ⊆ S(z) and hence |x| 6 |z| = d). Since the rows of G are
linearly independent, we have both x 6= 0 and λx 6= z for all λ ∈ F. But
1.4. Parameter bounds 67
Taking into account E.1.47, the last term turns out to be Gq (k, d) − d and
from this the stated relation follows.
68 Chapter 1. Block Error-correcting Codes
Using this inequality recursively, we have proved that Nq (k, d) > Gq (k, d).
There are two main uses of this inequality. One is that if a code [n, k, d]q
exists, then Gq (d, k) 6 n, and hence Gq (d, k) yields a lower bound for the
length n of codes of dimension k and miminum distance d. In other words,
to search for codes [n, k, d]q , with k and d fixed, the tentative dimension to
2
start
with is n = Gq (k, d). For example, G2 (4, 3) = 3 + d3/2e + 3/2 +
3/23 = 3 + 2 + 1 + 1 = 7 and we know that there is a [7, 4, 3] code, so
N2 (4, 3) = 7, that is, 7 is the minimum length for a binary code of dimension
4 with correcting capacity 1. For more examples, see 1.61.
The other use of the Griesmer inequality is that the maximum k that
satisfies Gq (k, d) 6 n, for fixed n and d, yields an upper bound q k for the
function Bq (n, d) defined as Aq (n, d), but using only linear codes instead of
general codes. Note that Aq (n, d) > Bq (n, d).
We refer to 32 Griesmer bound for implementations and some examples.
The function griesmer(k,d,q) computes Gq (k, d), which we will call Gries-
mer function, and ub_griesmer(n,d,q) computes the upper bound on Bq (n, d)
explained above.
1.61 Examples. According to the link Griesmer bound, and Remark 1.60,
we have B2 (8, 3) 6 32, B2 (12, 5) 6 32, B2 (13, 5) 6 64, B2 (16, 6) 6 256.
As we will see below, none of these bounds is sharp.
The first bound is worse than the Hamming bound (A2 (8, 3) 6 28), and
in fact we will see later in this section, using the linear programming bound,
that A2 (8, 3) = 20 (which implies, by the way, that B2 (8, 3) = 16)).
The bound B2 (13, 5) 6 64 is not sharp, because if there were a [13, 6, 5]
code, then taking residue with respect to a weight 5 code vector would lead
to a linear code [8, 5, d] with d > 3 (as dd/2e = 3) and d 6 4 (by Singleton),
but both [8, 5, 4] and [8, 5, 3] contradict the sphere bound.
Let us see now that a (16, 256, 6) code cannot be linear. Indeed, if we had
a linear code [16, 8, 6], then there would also exist a [15, 8, 5] code. Selecting
now from this latter code all words that end with 00, we would be able to
1.4. Parameter bounds 69
construct a code [13, 6, 5] that we have shown not to exist in the previous
paragraph.
The fact that the bound B2 (12, 5) 6 32 is not sharp cannot be settled
with the residue operation, because it would lead to a [7, 4, 3] code, which
is equivalent to the linear Ham(3). The known arguments are much more
involved and we omit them (the interested reader may consult the references
indicated in [19], p. 124, or in [29], p. 52).
The last expresion in the same link says that B3 (14, 9) 6 4, but it is not
hard to see that this is not sharp either (cf. [29], p. 53, or Problem P.1.23).
In the listing we also have that G2 (5, 7) = 15, G2 (12, 7) = 22 and
G(6, 5, 3) = 11. The techniques developed in Chapter 3 will allow us to
construct codes [15, 5, 7] (a suitable BCH code) and [11, 6, 5]3 (the ternary
Golay code). This implies that N2 (5, 7) = 15 and N3 (6, 5) = 11. On the
other hand, there is no [22, 12, 7] code, because these parameters contradict
the sphere bound, but in Chapter 3 we will construct a [23, 12, 7] code (the
binary Golay code) and therefore N2 (12, 7) = 23.
1.62 Remark. If we select all words of a code C whose i-th coordinate is
a given symbol λ, and then delete this common i-th coordinate λ from the
selected words, we get a code C 0 ∼ (n − 1, M 0 , d), with M 0 6 M . We
say that this C 0 is a shortening of C (or the λ-shortening of C in the i-th
coordinate). If C is linear, a 0-shortening is also linear, but a λ-shortening
of a linear code is in general not linear for λ 6= 0. In the previous examples
we have used this operation twice in the argument to rule out the existence
of linear codes [16, 8, 6].
But
X X
M2 = ( mλ )2 6 q m2λ ,
λ∈F λ∈F
M (M − 1)d 6 nβM 2 ,
1.65 Example. For the dual Hamming codes the Plotkin inequality is an
equality. Indeed, if C = Ham∨q (r), we know that C 0 has type [n, r, d], with
d = q r−1 and n = (q r − 1)/(q − 1). Since βn = q r−1 − q −1 < q r−1 = d,
Plotkin’s upper bound can be applied. As d/(d − βn) = q r , which is the
cardinal of C,
q r − 1 r−1
Aq ( , q ) = qr .
q−1
This formula explains the entries A2 (6, 3) = A2 (7, 4) = 8 and A2 (14, 7) =
A2 (15, 8) = 16 on the Table 1.1. Another example: with q = 3 and r = 3
we find A3 (13, 9) = 27.
1.4. Parameter bounds 71
E.1.49 (Improved Plotkin bound). For binary codes, β = 1/2, and the
Plotkin upper bound, which is valid if 2d > n, says that
Johnson’s bound
Let us just mention another approach, for binary codes, that takes into ac-
count the distribution of distances. This is done by means of the auxiliary
function A(n, d, w) that is defined as the greatest cardinal M of a binary
code (n, M ) with the condition that its minimum distance is > d and all its
vectors have weight w (we will say that such a code has type (n, M, d, w)).
1.70 Remark. Since the Hamming distance between two words of the same
weight w is even, and not higher than 2w, we have A(n, 2h − 1, w) =
1.4. Parameter bounds 73
Ai = | {(x, y) ∈ C × C | d(x, y) = i} |.
A0 = M, a0 = 1; [1.3]
Ai = ai = 0 for i = 1, . . . , d − 1; [1.4]
2
A0 + Ad + · · · + An = M , a0 + ad + · · · + an = M. [1.5]
1.73 Remark. For some authors the distance distribution of a code is the
sequence A0 , . . . , An .
E.1.53. Given x ∈ C, let Ai (x) denote the number of words x0 ∈ C such that
hd (x, x0 ) = i. Check that Ai =
P
x∈C Ai (x). Show that Ai (x) 6 A(n, d, i)
and that ai 6 A(n, d, i).
E.1.54. Show that if C is linear then the distance distribution of C coincides
with the weight enumerator.
and hence
n
X
bj = ai Kj (i) [1.6]
i=0
for j = 0, . . . , n. Note that
j
X x n−x
s
Kj (x) = (−1) (q − 1)j−s [1.7]
s j−s
s=0
1.4. Parameter bounds 75
can be rewritten as X n
n
bj = + ai Kj (i). [1.8]
j
i=d
36 Krawtchouk polynomials
The next proposition yields another interpretation of the expressions Kj (i).
1.74 Proposition (Delsarte’s lemma). Let ω ∈ C be a primitive q-th root of
unity and T = Zq . For i = 0, . . . , q, let Wi be the subset of T q whose
elements are the vectors of weight i. Then, for any given x ∈ Wi ,
X
ω hx|yi = Kj (i).
y∈Wj
X X X
ω hx|yi = ··· ω xν1 yν1 +···+xνj yνj
y∈Wj (ν) yν1 ∈T 0 yνj ∈T 0
X X
= (q − 1)j−s ··· ω xν1 yν1 +···+xνs yνs
yν 1 ∈T 0 yν s ∈T 0
s
Y X
= (q − 1)j−s ω xν ` y
`=1 y∈T 0
= (−1)s (q − 1) j−s
.
For the last equality note that the map χa : T → C such that y 7→ ω ay ,
where a ∈ T Pis fixed, is a characterPof the additive group of T , and hence,
for a 6= 0, y∈T χa (y) = 0 and y∈T 0 χa (y) = −χa (0) = −1 (cf. the
beginning
of the proof of Theorem 7). Now the result follows, because there
are si n−i
j−s ways to choose ν.
Delsarte’s theorem
ai > 0 (d 6 i 6 n)
and
Xn
n
+ ai Kj (i) > 0 for j ∈ {0, 1, . . . , n},
j
i=d
1.76 Remark. In the case of binary codes and d even, we may assume that
ai = 0 for odd i. Indeed, from a code (n, M, d) with d even we can get a code
(n −1, M, d −1) (as in E.1.12) and the parity extension of the latter is a code
(n, M, d) which does not contain vectors of odd weight. The link 37 Linear
programming bound contains an implementation of the linear programming
bound for the binary case, basically following [14], Ch. 17, §4. Notice that in
the case the constrained maximum is odd, then the function LP goes through
a second linear programming computation that decreases the linear terms
n
j of the relations. For this clever optimization (due to Best, Brouwer,
MacWilliams, Odlyzko and Sloane, 1977), see [14], p. 541.
(see the link 37 Linear programming bound).
1.77 Remark. The expression a$$i in the link Linear programming upper
bound constructs an identifier by appending to the identifier a the integer i
regarded as a character string. For example, a$$3 is the identifier a3.
1.4. Parameter bounds 77
Since we know that there are codes (8, 20, 3) (Example 1.4, or E.1.46),
we conclude that A2 (8, 3) = 20.
The linear programming bound also gives, without any additional rela-
tion, the values 128 and 256 (for d = 5) and 32 (for d = 7) on Table 1.1.
Asymptotic bounds
k d 1
R= 61− + .
n n n
d
If we now keep δ = fixed and let n go to infinity, then we see that α(δ) 6
n
1 − δ, where α(δ) = lim sup R is the asymptotic rate corresponding to δ.
Thus we see that the Singleton bound gives rise to the bound α(δ) 6 1 − δ
of the asymptotic rate, and this inequality is called the asymptotic Singleton
bound.
In general we may define the asymptotic rate α(δ), 0 6 δ 6 1, as
lim supn→∞ logq Aq (n, bδnc)/n and then there will be a bound of α(δ),
given by some function α0 (δ), corresponding to each of the known bounds
of Aq (n, d). These functions α0 (δ) are called asymptotic bounds. For exam-
ple, α0 (δ) = 1 − δ in the case of the Singleton bound.
78 Chapter 1. Block Error-correcting Codes
Below we explain the more basic asymptotic bounds (for the correspond-
ing graphs, see figure 1.2). We also provide details of how to compute them.
We will need the q-ary entropy function Hq (x), which is defined as fol-
lows (0 6 x 6 1):
The importance of this function in this context stems from the fact that for
0 6 δ 6 β, β = (q − 1)/q, we have
E.1.55 (Gilbert asymptotic bound). Use the formula [1.9] and the Gilbert
bound (Theorem 1.17) to prove that
for 0 6 δ 6 β.
dj kj
> δ, > 1 − Hq (δ) − ε
nj nj
for all j > jε . Any family of codes with this property is said to meet the
Gilbert–Varshamov bound. The family is said to be asymptotically good if it
satisfies the following weaker property: there exist positive real numbers R
and δ such that kj /nj > R and dj /nj > δ for all j. A family which is not
asymptotically good is said to be asymptotically bad, and in this case either
kj /nj or dj /nj approaches 0 when j → ∞.
Long ago it was conjectured that α(δ) would coincide with 1−Hq (δ), but
this turned out to be incorrect. Indeed, in 1982 Tsfasman, Vladut and Zink
proved, using modern methods of algebraic geometry, that the bound can be
improved for q > 49. For lower values of q, however, and in particular for
binary codes, the Gilbert bound remains the best asymptotic lower bound.
1.4. Parameter bounds 79
α(δ) 6 1 − Hq (δ/2),
for 0 6 δ 6 1.
E.1.57 (Plotkin asymptotic bound). Show that the Plotkin bound (Proposi-
tion 1.63) implies that
α(δ) 6 1 − δ/β if 0 6 δ 6 β
α(δ) = 0 if β 6 δ 6 1.
Note that the second part is known from the Plotkin asymptotic bound.
worse than the Hamming bound. In any case, this bound was established
directly by van Lint using fairly elementary methods of linear programming
(see [29] (5.3.6)).
For a further discussion on “perspectives on asymptotics”, the reader can
consult Section 4, Lecture 9, of [26].
(see the link 38 Computation of the asymptotic bounds).
1 S=Singleton
H=Hamming
P=Plotkin
E=Elias
L=van Lint
L M=McEliece
G=Gilbert
E
H
P
G M
0 0.5
Summary
• Griesmer bound: if [n, k, d] are the parameters of a linear code, then
k−1
X d
6 n.
qi
i=0
This gives an upper bound for Bq (n, d), the highest cardinal q k for a
linear code [n, k, d]q .
1.4. Parameter bounds 81
βnM
• Plotkin bound: for any code C of type (n, M, d), d 6 , which
M −1
to M (d −βn) 6 d. As a consequence, if d > βn, then
is equivalent
d
Aq (n, d) 6 . For binary codes this can be improved to
d − βn
A2 (n, d) 6 2 bd/(2d − n)c.
• Computations and examples related to the Elias, Johnson and linear
programming upper bounds.
• Computations related to the asymptotic bounds.
Problems
P.1.22. Let C ⊆ Fnq be a linear code [n, k, d] and assume k is maximal (for
n and d fixed). Show that |C| > q n /vol q (n, d − 1), which proves that the
Gilbert lower bound can always be achieved with linear codes when q is a
primer power. Show also that the Gilbert–Varshamov lower bound is never
worse than the Gilbert bound. Hint: If it were |C| < q n /vol q (n, d − 1), then
there would exist y ∈ Fnq such that hd (y, x) > d for all x ∈ C, and the linear
code C + hyi would have type [n, k + 1, d].
P.1.23. Show that there does not exist a binary linear code [14, 4, 5]3 (34 =
81 is the value of the Griesmer bound for n = 14 and d = 5). Hint: Forming
the residue with respect to a word of weight 9, and using the Singleton bound,
we would have a [5, 3, 3]3 code, and this cannot exist as can be easily seen
by studying a generating matrix of the form I3 |P , where P is a ternary 3 × 2
matrix.
P.1.24 (Johnson, 1962). Prove that
hn
A(n, 2h, w) 6 ,
hn − w(n − w)
provided hn > w(n − w). Hint: First notice that if x, y ∈ Zn2 satisfy
|x| = |y| = w and hd (x, y) > 2h then |x·y| 6 w−h; next, given a code C ∼
(n, M, 2h, w) with M = A(n, 2h, w), bound above by (w − h)M (M − 1)
the sum S of all |x · x0 | for x, x0 ∈ C, x 6= x0 ; finally P
note that if mi is the
number of 1s in position i for all words of C, then S = ni=1 m2i − wM and
S > wM (wM/n − 1).
P.1.25 (The Best code, 1978). We know that A2 (8, 3) = 20, hence A2 (9, 3) 6
2A2 (8, 3) = 40. In what follows we will construct a code (10,
40, 4).Con-
0 1 1
sider the matrix G = M |M , where M = I3 |RT and R = . Let
1 1 0
82 Chapter 1. Block Error-correcting Codes
E=Elias
M=McEliece
G=Gilbert
G M
0 0.5
L=van Lint
L M=McEliece
G=Gilbert
G M
0 0.5
2 Finite Fields
During the last two decades more and more abstract algebraic
tools such as the theory of finite fields and the theory of poly-
nomials over finite fields have influenced coding.
R. Lidl and H. Niederreiter, [12], p. 305.
This chapter is devoted to the presentation of some of the basic ideas and re-
sults of the theory of finite fields that are used in the theory of error-correcting
codes. It is a self-contained exposition, up to a few elementary ideas on rings
and polynomials (for the convenience of the reader, the latter are summarized
below). On the computational side, we include a good deal of details and ex-
amples of how finite fields and related objects can be constructed and used.
2.1 Zn and Fp
Essential points
Let n be a positive integer. Let Zn denote Z/(n), the ring of integers modulo
n. The elements of this ring are usually represented by the integers a such
that 0 6 a 6 n − 1. In this case the natural quotient map Z → Zn is given
by x 7→ [x]n , where [x]n is the remainder of the Euclidean division of x by
n. This remainder is also denoted x mod n and it is called the reduction of
x modulo n. The equality [x]n = [y]n is also written x ≡ y (mod n) and it
is equivalent to say that y − x is divisible by n. The operations of sum and
product in Zn are the ordinary operations of sum and product of integers, but
reduced modulo n.
For example, if n = 11 we have 3+7 ≡ 10, 3·7 ≡ 10, 52 ≡ 3 (mod 11).
See 39 Examples of ring and field computations. For the notations see A.6
and A.5 (p. 181). The function geometric_series(a,r) returns the vector
[1, a, . . . , ar−1 ].
The decision of whether an integer x does or does not have an inverse
modulo n, and its computation in case such an inverse exists, can be done
efficiently with a suitable variation of the Euclidean division algorithm. This
algorithm is implemented in the WIRIS function bezout(m,n), which returns,
given integers m and n, a vector [d, a, b] of integers such that d = gcd (m, n)
and d = am + bn. In case d = 1, a is the inverse of m (mod n), and
this integer is the value returned by inverse(m,n). The function inverse(m),
where m ∈ Zn , returns the same value, but considered as an element of Zn ,
rather than as an integer. See 40 More examples of ring computations. The
function invertible?(a) returns true or false according to whether a is or is not
2.1. Zn and Fp 87
an invertible element (in the ring to which it belongs). Note that if we ask
for 1/a and a is not invertible, than the expression is returned unevaluated
(as 1/(7:A) is the link).
The invertible elements of Zn form a group, Z∗n . Since an [x]n ∈ Zn is
invertible if and only if gcd (x, n) = 1, the cardinal of Z∗n is given by Euler’s
function ϕ(n), as this function counts, by definition, the number of integers
x in the range 1..(n − 1) such that gcd (x, n) = 1. In particular we see that
Zn is a field if and only if n is prime. For example, in Z10 the invertible
elements are {1, 3, 7, 9} (hence ϕ(10) = 4) and 3−1 ≡ 7 (mod 10), 7−1 ≡
3 (mod 10), 9−1 ≡ 9 (mod 10). On the other hand, in Z11 all non-zero
elements are invertible (hence ϕ(11) = 10) and Z11 is a field.
If p > 0 is a prime integer, the field Zp is also denoted Fp .
2.1 Proposition. The value of ϕ(n) is determined by the following rules:
1) If gcd (n1 , n2 ) = 1, then ϕ(n1 n2 ) = ϕ(n1 )ϕ(n2 ).
2) If p is a prime number and r a positive integer, then
Proof: The map π : Z → Zn1 × Zn2 such that k 7→ ([k]n1 , [k]n2 ) is a ring
homomorphism and its kernel is (n1 )∩(n2 ) = (m), where m = lcm(n1 , n2 ).
Since n1 and n2 are coprime, we have m = n1 n2 and hence there exists an
injective homomorphism Z/(m) = Zn1 n2 → Zn1 × Zn2 . But this homo-
morphism must be an isomorphism, as the cardinals of Zn1 n2 and Zn1 × Zn2
are both equal to n1 n2 .
For part 2, observe that the elements which are not invertible in Zpr are
2.2 Remark. Since ϕ(p) = p − 1 for p prime, and since there are in-
finitely many primes, the quotient ϕ(n)/n can take values as close to 1 as
wanted. On the other hand, ϕ(n)/n can be as close to 0 as wanted (see P.2.1).
42 Small values of ϕ(n)/n.
P
2.3 Proposition. For each positive integer n, d|n ϕ(d) = n (the sum is
extended to all positive divisors of n).
88 Chapter 2. Finite Fields
Summary
Problems
P.2.1. For k = 1, 2, 3, ..., let pk denote the k-th prime number and let
Nk = (p1 − 1)(p2 − 1) · · · (pk − 1), P k = p 1 p 2 · · · pk .
2.1. Zn and Fp 89
Prove that the minimum of ϕ(n)/n in the range (Pk ) ·· (Pk+1 −1) is Nk /Pk .
Deduce from this that in the range 1..(2 × 1011 ) we have ϕ(n) > 0.1579n.
P.2.2. Prove that lim inf n→∞ ϕ(n)/n = 0.
P.2.3. Show that the values of n for which Z∗n has 6 elements are 7, 9, 14, 18.
Since any abelian group of order 6 is isomorphic to Z6 , the groups Z∗7 , Z∗9 ,
Z∗14 , Z∗18 are isomorphic. Find an isomorphism between Z∗7 and Z∗9 .
P.2.4. Show that the values of n for which Z∗n has 8 elements are 15, 16, 20,
24, 30. Now any abelian group of order 8 is isomorphic to Z8 , Z2 × Z4 or
Z32 . Show that Z∗24 ' Z32 and that the other four groups are isomorphic to
Z2 × Z4 .
90 Chapter 2. Finite Fields
Essential points
Ruffini’s rule
Let us begin with two elementary propositions and some examples. Recall
that if K is a field, X an indeterminate and f ∈ K[X] a polynomial of
degree r > 0, then f is said to be irreducible if it cannot be expressed as a
product f = gh with g, h ∈ K[X] and deg (g), deg (h) < r (otherwise it is
said to be reducible).
2.4 Proposition (Ruffini’s rule). Let K be a field. Given a polynomial f ∈
K[X], an element α ∈ K is a root of f (that is, f (α) = 0) if and only if f is
divisible by X − α. In particular we see that if f ∈ K[X] is irreducible and
deg (f ) > 1, then f has no roots in K.
2.2. Construction of finite fields 91
2.8 Proposition. If F is a finite field, then its cardinal has the form pr , where
p is a prime number and r is a positive integer. Moreover, p coincides with
the characteristic of F .
Proof: If p is the characteristic of F , then p is a prime number and F has a
subfield isomorphic to Zp . Thus we can regard F as Zp -vector space. Since
2.2. Construction of finite fields 93
F : K → K such that x 7→ xp
satisfies
(x + y)p = xp + y p and (xy)p = xp y p
for all x, y ∈ K and
λp = λ for all λ ∈ Zp
(for this relation use E.2.6). If K is finite, then F is an automorphism of
K/Zp (it is called the Frobenius automorphism of K).
E.2.11 (Relative Frobenius automorphism). Let L be a field of characteristic
p and K ⊆ L a finite subfield. If q = |K|, show that the map
FK : L → L such that x 7→ xq
satisfies
(x + y)q = xq + y q and (xy)q = xq y q
for all x, y ∈ L and
λq = λ for all λ ∈ K
(for this relation use E.2.6). If L is finite, then FK is an automorphism of
L/K (it is called the Frobenius automorphism of L relative to K).
If K has cardinal q, the function frobenius(K) yields the map x 7→ xq ,
that is, the Frobenius map relative to K. When applied to an element x,
frobenius(x) is equivalent to the Frobenius map relative to the prime field of
the field of x. For examples, see the link 45 Frobenius automorphisms .
{1, x, . . . , xr−1 }
2.9 Remark. In the points 1-3 above, K can be replaced by any commuta-
tive ring and f by a monic polynomial (a polynomial f is monic if its the
coefficient of its highest degree monomial is 1). Then K 0 is a ring, and a free
module over K with basis {1, x, . . . , xr−1 }. In other words, assuming that
the ring K has already been constructed, that x is a free identifier (this can
be achieved, if in doubt, with the sentence clear x) and that f (x) is a monic
polynomial over K, then K 0 can be constructed as shown in 47 The function
extension(K,f) also works for rings .
We end this subsection with a result that establishes a useful relation between
the field K 0 = K[X]/(f ), f ∈ K[X] irreducible, and any root of f .
2.10 Proposition. Let L be a field and K a subfield. Let f ∈ K[X] be a
monic irreducible polynomial, and set r = deg (f ), K 0 = K[X]/(f ). If
β ∈ L is a root of f , and x is the class of X modulo f , then there exists a
unique K-homomorphism K 0 → K[β] such that x 7→ β (K-homomorphism
means that it is the identity on K). This homomorphism is necessarily an
isomorphism. Hence K[β] is a field and therefore K[β] = K(β).
Proof: Since the image of α0 + α1 x + · · · + αr−1 xr−1 ∈ K 0 by a K-
homomorphism such that x 7→ β is α0 + α1 β + · · · + αr−1 β r−1 , uniqueness
is clear. For the existence, consider the map K[X] → L such that h 7→
h(β). It is a ring homomorphism with image K[β] and its kernel contains
the principal ideal (f ), because f (β) = 0 by hypothesis. Hence there is an
induced homomorphism K 0 → L such that
Splitting fields
α1 , . . . , αr ∈ L
such that
r
Y
f= (X − αj ) and L = K(α1 , . . . , αr ).
j=1
E.2.15. Given a finite field L such that |L| = pr , the cardinal of any subfield
is ps , where s|r (E.2.9). Prove that the converse is also true: given a divisor
s of r, there exists a unique subfield of L whose cardinal is ps .
In this section we will establish a formula for the the number Iq (n) of monic
irreducible polynomials of degree n over a finite field K of q elements.
where Irr K (d) is the set of monic irreducible polynomials of degree d over K.
Consequently,
X
qn = dIq (d).
d|n
2.2. Construction of finite fields 99
P
2.22 Example. Since for any positive integer n we have n = d|n ϕ(d)
(Proposition 2.3), the Möbius inversion formula tells us that we also have
X n
ϕ(n) = µ(d) .
d
d|n
55 Inversion
formula: an example
If we apply the Möbius inversion formula to the relation q n = d|n dIq (d)
P
in Corollary 2.20, we get:
2.23 Proposition. The number Iq (n) of irreducible polynomials of degree n
over a field K of q elements is given by the formula
1X
Iq (n) = µ(d)q n/d .
n
d|n
2.24 Corollary. For all n > 0, Iq (n) > 0. In other words, if K is a finite
field and q = |K|, then there are irreducible polynomials over K of degree
n for all n > 1.
Proof: Since for d > 1 we have µ(d) > −1, it is easy to see that the formula
in Proposition 2.23 implies that nIq (n) > q n − (q n − 1)/(q − 1) > 0.
56 ComputingIq (n)
n
If we apply
Q Q the Möbius multiplicative inversion formula to the relation X q −
X = d|n f ∈Irr K (d) f in Corollary 2.20, we get:
2.25 Proposition. The product PK (n) of all monic irreducible polynomials
of degree n over K is given by the formula
n/d
Y
PK (f ) = (X q − X)µ(d) .
d|n
Summary
Problems
P.2.5 (Finding isomorphisms between finite fields). Let L be a finite field
and K ⊆ L a subfield. Set q = |K| and let r be the positive integer such that
|L| = q r . Assume that we have a monic irreducible polynomial f ∈ K[X]
and that we can find β ∈ L such that f (β) = 0. Show that there is a unique
K-isomorphism K[X]/(f ) ' L such that x 7→ β, where x is the class of X
modulo f . Prove also that the K-isomorphisms between K[X]/(f ) and L
are in one-to-one correspondence with the roots of f in L.
P.2.6. The polynomials f = X 3 +X +1, g = X 3 +X 2 +1 ∈ Z2 [X] are irre-
ducible (as shown in Example 2.21 they are the only irreducible polynomials
of degree 3 over Z2 ). Use the previous problem to find all the isomorphisms
between Z2 [X]/(f ) and Z2 [X]/(g).
P.2.7. Use P.2.5 to find all the isomorphisms between the field described in
E.2.14 and the field Z2 (x, y) defined in Example 2.13.
P.2.8. A partition of a positive integer n is a set of pairs of positive in-
tegers λ = {(r1 , m1 ), . . . , (rk , mk )} such that r1 , . . . , rk are distinct and
n = m1 r1 + . . . + mk rk . The partition {(n, 1)} is said to be improper, all
others are said to be proper. Let now K be a finite field of q elements. Use
the uniqueness (up to order) of the decomposition of a monic f ∈ K[X] as
a product of monic irreducible factors to prove that
k
Y Iq (ri ) + mi − 1
Pq (λ) =
mi
i=1
gives the number of monic polynomials in K[X] that are the product of mi
P polynomials of degree ri , i = 1, . . . , k. Deduce from this
irreducible monic
that Rq (n) = λ Pq (λ), where the sum ranges over all proper partitions of
n, is the number of polynomials in K[X] that are reducible, monic and of
degree n. Finally show that Rq (n) + Iq (n) = q n and use this to check the
formula for Iq (n) obtained in Proposition 2.23 for n in the range 1..5.
2.3. Structure of the multiplicative group of a finite field 103
Essential points
Order of an element
If K is a finite field and α is a nonzero element of K, the order of α, ord (α),
is the least positive integer r such that αr = 1 (in E.2.4 we saw that this r
exists). Note that ord (α) = 1 if and only if α = 1.
2.28 Example. in Z5 we have ord (2) = 4, because 2 6= 1, 22 = 4 6= 1,
23 = 3 6= 1 and 24 = 1. Similarly we have ord (3) = 4 and ord (4) = 2.
2.29 Proposition. If the cardinal of K is q and α ∈ K ∗ has order r, then
r|(q − 1).
Proof: It is a special case of E.2.4.
2.30 Remark. This proposition implies that αq−1 = 1 for all nonzero ele-
ments α ∈ K, a fact that was already established in E.2.6. On the other hand,
if q − 1 happens to be prime and α 6= 1, then necessarily ord (α) = q − 1.
More generally, r is the least divisor of q − 1 such that αr = 1.
2.31 Examples. 1) In the field Z2 (x) of example 2.11 we have, since q−1 =
3 is prime, ord (1) = 1, ord (x) = 3 and ord (x + 1) = 3. Note that in 2.11 we
had already checked this from another perspective.
104 Chapter 2. Finite Fields
P
Note finally that these formulae imply that a∈K a = Q 0 if K 6= Z2 (as
X q − X has no term of degree q − 1 if q 6= 2) and that a∈K ∗ a = −1 (See
also Example 1.30, where this fact was proved in a different way).
Primitive elements
A nonzero element of a finite field K of cardinal q = pr is said to be a
primitive element of K if ord (α) = q − 1. In this case it is clear that
a0 , a1 , . . . , ar−1 ∈ K,
106 Chapter 2. Finite Fields
a0 + a1 α + · · · + ar−1 αr−1 = 0.
Primitive polynomials
If f is an irreducible polynomial of degree r over Zp , p prime, then Zp (x) =
Zp [X]/(f ) is a field of cardinal pr , where x is the class of X modulo f . We
know that x may be a primitive element, as in the case of the field Z2 (x)
of example 2.11, or it may not, as in the case of the field Z7 (x) studied in
the example 2.15 (cf. the examples 2.33). If x turns out to be a primitive
element, we say that f is primitive over Zp . It is interesting, therefore, to
explore how to detect whether or not a given polynomial is primitive. First
see 61 Example of a primitive polynomial (of degree 4 over Z3 ).
E.2.21. Let K be a finite field and f ∈ K[X] be a monic irreducible polyno-
mial, f 6= X. Let x be the class of X in K[X]/(f ). If m = deg (f ), show
that the order of x is the minimum divisor d of q m −1 such that f |X d −1. For
the computation of this order, which is also called the period (or exponent)
of f , see the link 62 The function period(f,q) .
Consider now Table 2.1. The column on the right contains the coeffi-
cients of tk , k = 0, 1, ..., 14, with respect to the basis 1, t, t2 , t3 . For exam-
ple, t8 ≡ t2 + 1 ≡ 0101. The first column contains the coefficients with
respect to 1, t, t2 , t3 of the nonzero elements x of Z2 (t) ordered as the inte-
gers 1, ..., 15 written in binary, together with the corresponding log (x). For
example, 5 ≡ 0101 ≡ t2 + 1, and its index is 8.
2.37 Remark. Index tables are unsuitable for large fields because the corre-
sponding tables take up too much space. They are also unsuitable for small
fields if we have the right computing setup because the field operations of
a good implementation are already quite efficient. As an illustration of the
contrast between pencil and machine computations, see 64 Examples of Lidl–
Niederreiter (cf. [12], p. 375).
108 Chapter 2. Finite Fields
Summary
Problems
P.2.9. Let K be a finite field, α, β ∈ K ∗ , r = ord (α), s = ord (β). Let
t = ord (αβ), d = gcd (r, s), m = lcm(r, s) and m0 = m/d. Prove that m0 |t
and t|m. Hence ord (αβ) = rs if d = 1. Give examples in which d > 1 and
t = m0 (repectively t = m).
Essential points
E.2.22. Show that there exits a unique K-isomorphism K[X]/(pα ) ' K[α]
such that x 7→ α, where x is the class of X.
E.2.25. With the same notations as in the Proposition 2.38, prove that r =
deg (p) is the first positive integer r such that αr ∈ h1, α, ..., αr−1 iK . As a
result, r is also the first positive integer such that K[α] = h1, α, ..., αr−1 iK .
2.39 Example. Let us find the minimum polynomial, p, over Z2 of the ele-
ment y of Z2 (x, y) introduced in the example 2.13 (cf. The function min-
imum_polynomial). We have y 2 = xy + 1. Hence y 2 ∈ h1, yiZ2 (x) , a
fact that is nothing but a rediscovery that the minimum polynomial of y over
Z2 (x) is Y 2 + xY + 1. But y 2 6∈ h1, yiZ2 , and so p has degree higher than 2.
We have y 3 = xy 2 + y = x2 y + x + y = xy + x and, as it is easy to see, y 3 6∈
h1, y, y 2 iZ2 . Now y 4 = xy 2 +xy = x2 y +x+xy = y +x = y 3 +y 2 +y +1,
and therefore p = Y 4 + Y 3 + Y 2 + Y + 1. As ord (y) = 5, p is not a primitive
polynomial.
66 Examples of minimum polynomial .
2.4. Minimum polynomial 113
2.40 Proposition. Let K be a finite field and q = |K|. Let L be a finite field
extension of K and α ∈ L. If Cα is the set of conjugates of α over K, then
the minimum polynomial pα of α over K is given by the expression
Y
pα = (X − β).
β∈Cα
K 0 and hence f has a root α0 ∈ K 0 . Now Proposition 2.10 says that there
is a unique isomorphism Zp [X]/(f ) ' Zp [α0 ] = K 0 such that x 7→ α0 ,
where x is the class of X modulo f . But there is also a unique isomorphism
Zp [X]/(f ) ' Zp [α] = K and so there exists a unique isomorphism K ' K 0
such that α 7→ α0 .
2.42 Remark. The proof above actually shows that there are precisely r dis-
tinct isomorphisms between K and K 0 .
E.2.26. The polynomials X 3 + X + 1, X 3 + X 2 + 1 ∈ Z2 [X] are the two
irreducible polynomials of degree 3 over Z2 . Construct an explicit isomor-
phism between the fields Z2 [X]/(X 3 + X + 1) and Z2 [X]/(X 3 + X 2 + 1).
68 Isomorphisms between two F .
8
E.2.27. Prove that x2 +x+4 and x2 +1 are irreducible polynomials over the
field F11 and construct an explicit isomorphism between F11 [x]/(x2 +x+4)
and F11 [x]/(x2 + 1).
Definitions
Let α ∈ L. Then we can consider the map mα : L → L such that x 7→ αx.
This map is clearly K-linear and we define the trace and the norm of α with
respect to K, denoted Tr L/K (α) and NmL/K (α) respectively, by the formulae
Let us recall that the right hand sides are defined as the sum of the diagonal
elements and the determinant, respectively, of the matrix of mα with respect
to any basis of L as a K-vector space.
E.2.28. Check that Tr L/K : L → K is a K-linear map and that Tr L/K (λ) =
mλ for all λ ∈ K.
E.2.29. Similarly, check that NmL/K : L∗ → K ∗ is a homomorphism of
groups and that NmL/K (λ) = λm for all λ ∈ K.
Qr
with respect to K (α1 = α), then we know that pα = i=1 (X − αi ). In
particular we have that
we have that
0 −cr
..
1 . −cr−1
..
A=
. .. ..
. .
1 0 −c2
1 −c1
and so
trace(mα ) = s trace(A) = s(−c1 ) = sσ(α),
and
det(mα ) = (det(A))s = ((−1)r cr )s = π(α)s ,
as stated.
If L and K are constructed fields, then Tr L/K (α) is returned by Tr(α,L,K),
or trace(α,L,K). If K is not specified, it is taken as the prime field of L. And
if neither K nor L are specified, it is assumed that L is the field of α and K
its prime field. Similar notations and conventions hold for NmL/K (α) and
Nm(α,L,K), or norm(α,L,K). 69 Trace examples . 70 Norm examples .
Summary
Problems
P.2.13. Let K be a finite field and q = |K|. Let f ∈ K[X] be monic and
irreducible and r = deg (f ). Show that K 0 = K[X]/(f ) is the splitting field
of f .
P.2.14. Find the trace of a0 +a1 t+a2 t2 +a3 t3 +a4 t4 ∈ Z2 [T ]/(T 5 +T 2 +1),
where t is the class of T .
P.2.15. Let K = Z2 [X]/(X 4 + X + 1) and α = [X]. Compute the matrix
M = Tr (αi αj ) for 0 6 i, j 6 3 and show that det(M ) = 1. Deduce that
there exists a unique Z2 -linear basis β0 , β1 , β2 , β3 of K such that Tr (αi βj ) =
δij (0 6 i, j 6 3).
P.2.16. Let K = Z3 , L = K[X]/(X 2 + 1) and β = α + 1, where α is the
class of X. Find Nm(β i ) for 0 6 i 6 7.
117
3 Cyclic Codes
Cyclic codes are linear codes that are invariant under cyclic permutations
of the components of its vectors. These codes have a nice algebraic structure
(after reinterpreting vectors as univariate polynomials) which favors its study
and use in a particularly effective way.
More specifically, we will see that cyclic codes of length n over a finite
field K are in one-to-one correspondence with the monic divisors g of
X n − 1 ∈ K[X],
3.1 Generalities
During the last two decades more and more algebraic tools
such as the theory of finite fields and the theory of polynomi-
als over finite fields have influenced coding.
Lidl–Niederreiter, [12], p. 470.
Essential points
a1 + a2 x + . . . + an xn−1 ,
the product xa is
a1 x + a2 x2 + . . . + an−1 xn−1 + an xn .
Since xn = 1, we have
xa = an + a1 x + a2 x2 + . . . + an−1 xn−1 ,
Dimension of Cg
Given a monic divisor g of X n − 1, the elements of Cg are, by definition, the
polynomials that have the form aḡ, where a ∈ F[x]n is an arbitrary element.
In other words, the map µ : F[X] → Cg such that u 7→ ūḡ is surjective.
On the other hand, we claim that ker (µ) = (b g ). Indeed, ūḡ = 0 if and
n
only if (X − 1)|ug. But X − 1 = gbn g and gcd (g, gb) = 1, so (X n − 1)|ug
if and only if gb|u, that is, if and only if u ∈ (b
g ).
Hence we have that
where k = deg (b
g ). Thus we have proved:
3.4 Proposition. The dimension of Cg coincides with the degree of the con-
trol polynomial gb of Cg :
Generating matrices
With the same notations as in the preceeding subsection, the polynomials
ui = {xi ḡ}06i<k form a basis of Cg . Therefore, if
g = g0 + g1 X + · · · + gn−k X n−k ,
xn−k+j = qj g + rj ,
vj = xn−k+j − rj
Cg⊥ = C
fgb, [3.4]
where Cfge is the image of Cgb by the map a 7→ ea (cf. [3.2]). Indeed, since
both sides have dimension n − k, it is enough to see that
fgb ⊆ Cg⊥ .
C
gb = h0 + h1 X + · · · + hk X k ,
124 Chapter 3. Cyclic Codes
then
hk hk−1 · · · h0 0 0 ··· 0
0
h k h k−1 · ·· h0 0 ··· 0
.. . .. . .. . .. .. .. .. .
H= . ··· . . .
0 ··· 0 hk hk−1 · · · h0 0
0 ··· ··· 0 hk hk−1 · · · h0
g = X5 − X3 + X2 − X − 1
Thus the code C = hGi is selfdual and in particular the weight of any vector
of C is a multiple of 3. Since the rows G have weight 6, the minimum
distance of C is either 3 or 6. But each row of G has exactly one zero in the
first 6 columns, and the position of this 0 is different for the different rows,
so it is clear that a linear combination of two rows of G has weight at least
2 + 2, hence at least 6. Since the weight of this combination is clearly not
more than 12 − 4 = 8, it has weight exactly 6. In particular, for each such
combination there appear exactly two zeros in the first 6 positions. Now a
linear combination of 3 rows will have weight at least 1+3, and so at least 6.
All other linear combinations of rows of G have weight at least 4, and so at
3.1. Generalities 125
least 6. So C has type [12, 6, 6] and as a consequence C has type [12, 6, 5].
It is a perfect code. It is known (but rather involved) that all codes of type
(11, 36 , 5) are equivalent to C (cf. [14]) and any such code will be said to be
a ternary Golay code.
E.3.11. Find all binary cyclic codes of length 7. In each case, give the gener-
ating and control polynomials, a normalized generating matrix and identify
the dual code.
Summary
Problems
P.3.1 Consider two linear codes C1 and C2 of the same length and with
control matrices H1 and H2 .
1) Check that C1 ∩ C2 is a linear code and find a control matrix for it in
terms of H1 and H2 .
2) Prove that if C1 and C2 are cyclic with generating polynomials g1 and
g2 , then C1 ∩ C2 is cyclic. Find its generating polynomial in terms of
g1 and g2 .
P.3.2. Let G = I6 |( S155 ), where S5 is the Paley matrix of Z5 . Prove that hGi
is a ternary Golay code.
Essential points
Introduction
In the previous section we learnt that the generator polynomials g of cyclic
codes of length n over Fq are, assuming gcd (n, q) = 1, the monic divisors
of X n − 1 and that if f1 , . . . , fr are the distinct monic irreducible factors
of X n − 1 over Fq then g has the form g = fi1 · · · fis , with 0 6 s 6 r,
1 6 i1 < · · · < is 6 r.
The goal of this section is to explain an algorithm that supplies the factors
f1 , . . . , fr in an efficient way. It is basically the method behind the function
factor(f,K). 79 Examples of factorization illustrates how it works.
h = X2 + X + 1
factor, f 6= f12 and f 6= f22 ). Finally, this relation is easily checked and so
we have that X 7 − 1 = (X − 1)f1 f2 is the factorization we were seeking.
Now let us consider an indirect approach. It consists in trying to find
a finite field extension F0 /F (here F = Fq = Z2 ) that contains all roots of
X 7 − 1. If F0 exists, it contains, in particular, an element of order 7. If q 0 is
the cardinal of F0 , we must have that q 0 −1 is divisible by 7. But q 0 = q m , for
some positive integer m, and hence m must satisfy that q m − 1 is divisible
by 7. As q = 2, the first such m is 3, and so it is natural to try F0 = F8 .
Now the group F∗8 is cyclic of order 7, and hence
Y
X7 − 1 = (X − α).
α∈F∗8
The root 1 corresponds to the factor X −1. Of the other 6 roots, 3 must be the
roots of f1 and the other 3 the roots of f2 . The actual partition depends, of
course, on the explicit construction of F0 . Since [F0 : F] = 3, we can define
F0 as the extension of F by an irreducible polynomial of degree 3, say f1 :
F0 = F/(X 3 + X + 1). If we let u = [X] (to use the notation in Examples
of factorization), then u is a root of f1 . Being in characteristic 2, u2 and
u4 = u2 + u are the other roots of f1 and f1 = (X − u)(X − u2 )(X − u4 ).
So u3 = u + 1, (u + 1)2 = u2 + 1 and (u2 + 1)2 = u4 + 1 = u2 + u + 1 are
the roots of f2 and f2 = (X −(u+1))(X −(u2 +1))(X −(u2 +u+1)).
The ideas involved in the last two paragraphs of the preceeding example
can be played successfully to find the factorization of X n − 1 over Fq for all
n and q (provided gcd (n, q) = 1), as we will see in the next subsection.
The condition gcd (n, q) = 1 says that [q]n ∈ Z∗n and hence we may consider
the order m of [q]n in that group. By definition, m is the least positive integer
such that q m ≡ 1 (mod n). In other words, m is the least positive integer such
that n|(q m −1) and we will write en (q) to denote it. For example, e7 (2) = 3,
because 23 = 8 ≡ 1 (mod 7). The value of en (q) can be obtained with the
function order(q,n). 80 Examples of the order of an integer modulo n .
Let now h ∈ F[X] be any monic irreducible polynomial of degree m =
en (q) and define F0 = Fqm as F[X]/(h). Let α be a primitive element of
F0 (if h were a primitive polynomial, we could choose α = [X]h ). Then
ord (α) = q m − 1 is divisible by n, by definition of m. Let r = (q m − 1)/n
and ω = αr .
3.2. Effective factorization of X n − 1 129
Cyclotomic classes
To proceed further we need the notion of cyclotomic classes. Given an inte-
ger j in the range 0..(n − 1), the q-cyclotomic class of j modulo n is defined
as the set
Cj = {j, qj . . . , q r−1 j} (mod n),
where r is the least positive integer such that q r j ≡ j (mod n). For example,
C0 = {0} always, and if n = 7 and q = 2, then C1 = {1, 2, 4} and
C3 = {3, 6, 5}. If n = 11 and q = 3, then C1 = {1, 3, 9, 5, 4} and C2 =
{2, 6, 7, 10, 8}.
E.3.12. Show that if Cj ∩ Ck 6= ∅ then Cj = Ck . So the distinct cyclotomic
classes form a partition of Zn .
The function cyclotomic_class(j,n,q) yields the cyclotomic class Cj . In the
case q = 2 we can use cyclotomic_class(j,n). 81 Examples of cyclotomic
classes .
The function cyclotomic_classes(n,q) yields the list of q-cyclotomic classes
modulo n. In the case q = 2 we can use cyclotomic_classes(n). 82 Examples
of the list of cyclotomic classes .
This means that aq = a for all coefficients a of fC and we know that this
happens if and only if a ∈ F.
3.11 Theorem. The correspondence C 7→ fC is a bijection between the set
of q-cyclotomic classes modulo n and the set of monic irreducible factors of
X n − 1 over Fq .
Proof: The factorization of X n − 1 over F0 established in lemma 3.8 and the
fact that the q-cyclotomic classes modulo n form a partition of Zn imply that
Y
Xn − 1 = fC ,
C
where the product runs over all q-cyclotomic classes modulo n. Thus it
is enough to prove that fC ∈ F[X] is irreducible. To see this, note that
{ω j | j ∈ C} is the conjugate set of any of its elements and so fC is, by
proposition 2.40, the minimum polynomial over F of ω j for any j ∈ C.
Therefore fC is irreducible.
E.3.13. If n is divisible by p (the characteristic of F), the factorization of
X n − 1 can be reduced easily to the case gcd (n, q) = 1. Indeed, if n = n0 ps ,
0 s
where p is prime and gcd (n0 , p) = 1, show that X n − 1 = (X n − 1)p .
Consequently the number of distinct irreducible factors of X n − 1 coincides
with the number of q-cyclotomic classes modulo n0 and each such factor has
multiplicity ps .
Summary
Problems
P.3.5. Show that a q-ary cyclic code C of length n is invariant under the
permutation σ such that σ(j) = qj (mod n).
P.3.6. We have seen that over Z3 we have X 11 − 1 = (X − 1)g0 g1 , where
g0 = (X 5 − X 3 + X 2 − X − 1) and g1 = (X 5 + X 4 − X 3 + X 2 − 1).
132 Chapter 3. Cyclic Codes
(this polynomial has degree ϕ(n) and is called the n-th cyclotomic polyno-
mial over Fq ). Prove that:
1) X n − 1 = d|n Qd .
Q
for all n > 1, where the product is extended over the set M (q, n) of all
divisors m > 1 of q n − 1 for which n is the multiplicative order of q modulo
m (see 86 Computation of the set M(q,n) . Hint: First show that the roots of
Pq (n, X) are the elements of degree n in Fqn .
3.12 Remark (On computing cyclotomic polynomials). The procedure ex-
plained in P.3.7 to find the n-th cyclotomic polynomial involves cumbersome
computations for large n. For example, if n = 11! then Q(n, X) is a poly-
nomial of degree ϕ(n) = 8294400 with 540 terms (the number of divisors
of n) and it took 45 seconds to evaluate in a Compaq Armada E500. For-
tunately there is a better scheme based on P.3.9. It is presented in Efficient
computation of cyclotomic polynomials and is the one implemented in
the internal function cyclotomic_polynomial(n,T).
For the key mathematical properties of the cyclotomic polynomials on which
this function is based, see P.3.9.
With the internal function, and n = 11!, Q(n, X) was obtained in 0.23 sec-
onds, while the same function coded externally (the last quoted listing) took
0.25 seconds. If we want to calculate a list of cyclotomic polynomials, the
direct method may be much better, because it does not have to factor and
find the divisors of many integers.
87 Efficient computations of cyclotomic polynomials
P.3.9. Let Qn (X) be the n-th cyclotomic polynomial (n > 1). Prove that:
1) Qmn (X) divides Qn (X m ) for any positive integers m and n.
2) Qmn (X) = Qn (X m ) if every prime divisor of m also divides n.
3) For any n, Qn (X) = Qr (X n/r ), where r is the product of the prime
divisors of n.
134 Chapter 3. Cyclic Codes
Essential points
Introduction
Let C be the cyclic code of length n and let g be its generating polynomial.
By definition, the roots of C = Cg are the roots of g in the splitting field
F0 = Fqm of X n − 1 over Fq . If ω ∈ Fqm is a primitive n-th root of unity
and we let Eg denote the set of all k ∈ Zn such that ω k is a root of g, then
we know that Eg is the union of the q-cyclotomic classes corresponding to
the monic irreducible factors of g.
Let Eg0 ⊆ Eg be a subset formed with one element of each q-cyclotomic
class contained in Eg . Then we will say that M = {ω k | k ∈ Eg0 } is a
minimal set of roots of Cg .
3.13 Proposition. If M is a minimal set of roots of a cyclic code C of length
n, then
C = {a ∈ F[x]n | a(ξ) = 0 for all ξ ∈ M }.
Proof: If a ∈ C, then a is a multiple of ḡ, where g is the generating polyno-
mial of C, and hence it is clear that a(ξ) = 0 for all ξ ∈ M . So we have the
inclusion
C ⊆ {a ∈ F[x]n | a(ξ) = 0 for all ξ ∈ M }.
Now let a ∈ F[x]n and assume that aX (ξ) = a(ξ) = 0 for all ξ ∈ M .
By definition of M , there is j ∈ Eg0 such that ξ = ω j , and so ω j is a root
3.3. Roots of a cyclic code 135
ξ = ξ1 , . . . , ξr ∈ Fqm
are n-th roots of unity, then the polynomials a ∈ F[x]n such that a(ξi ) = 0,
i = 1, . . . , r, form an ideal Cξ of F[x]n , which will be called the cyclic code
determined by ξ. If gi is the minimum polynomial of ξi over Fq , then Cξ =
Cg , where g is the lcm of the polynomials g1 , . . . , gr . This observation will
be used below for the construction of codes with predetermined properties.
BCH codes
An important class of cyclic codes, still used a lot in practice,
was discovered by R. C. Bose and D. K. Chaudhuri (1960) and
independently by A. Hocquenghem (1959).
J. H. van Lint, [29], p. 91.
Let ω ∈ Fqm be a primitive n-th root of unity. Let δ > 2 and ` > 1 be
integers. Write BCH ω (δ, `) to denote the cyclic code of length n generated
by the least common multiple g of the minimal polynomials gi = pω`+i ,
i ∈ {0, . . . , δ − 2}. This code will be said to be a BCH code (for Bose–
Chaudhuri–Hocquenghem) with designed distance δ and offset `. In the case
` = 1, we will write BCH ω (δ) instead of BCH ω (δ, 1) and we will say that
these are strict BCH codes. A BCH code will be said to be primitive if n =
q m − 1 (note that this condition is equivalent to say that ω is a primitive
element of Fqm ).
3.15 Theorem (BCH bound). If d is the minimum distance of BCH ω (δ, `),
then d > δ.
Proof: First note that an element a ∈ F[x]n belongs to BCH ω (δ, `) if and
only if a(ω `+i ) = 0 for all i ∈ {0, . . . , δ − 2}. But the relation a(ω `+i ) = 0
is equivalent to
and therefore
(1, ω `+i , ω 2(`+i) , . . . , ω (n−1)(`+i) )
is a control vector of BCH ω (δ, `). But the matrix H whose rows are these
vectors has the property, by the Vandermonde determinant, that any δ − 1 of
its columns are linearly independent. Indeed, the determinant of the columns
j1 , . . . , jδ−1 is equal to
3.16 Example. The minimum distance of a BCH code can be greater than
the designed distance. Let q = 2 and m = 4. Let ω be a primitive element
of F16 . Since ω has order 15, we can apply the preceeding results in the
case q = 2, m = 4 and n = 15. The 2-cyclotomic classes modulo n are
{1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}. This shows, if we write
Cδ = BCH ω (δ) and dδ = dCδ for simplicity, that C4 = C5 , hence d4 = d5 >
5, and C6 = C7 , hence d6 = d7 > 7. Note that the dimension of C4 = C5 is
15 − 2 · 4 = 7, and the dimension of C6 = C7 is 15 − 2 · 4 − 2 = 5.
3.17 Example. This example is similar to the previous one, but now q = 2
and m = 5. Let ω be a primitive element of F32 . The 2-cyclotomic classes
modulo 31 are
{1, 2, 4, 8, 16}, {3, 6, 12, 24, 17}, {5, 10, 20, 9, 18},
{7, 14, 28, 25, 19}, {11, 22, 13, 26, 21}, {15, 30, 29, 27, 23}
pi = pω`+i , i = 1, . . . , ` − 1,
and deg (pω`+i ) 6 [Fqm : Fq ] = m, it is clear that deg (g) 6 m(δ − 1), and
this clearly implies the stated inequality.
138 Chapter 3. Cyclic Codes
Now the first equality tells us that BCH ω (2t + 1) = BCH ω (2t), so that it is
enough to consider, among the binary BCH codes in the strict sense, those
that have odd designed distance.
3.19 Proposition. In the binary case, the dimension k of a binary code
BCH ω (2t + 1) of length n and designed distance δ = 2t + 1 satisfy the
following inequality:
k > n − tm,
where m = ord n (2).
Proof: Let g be the polynomial [3.5]. Since the first expression of g in
[3.5] is the generating polynomial of BCH ω (2t + 1), we know that k = n −
deg (g). But looking at the third expression of g in [3.5] we see that deg (g)
is not higher than the sum of the degrees of p1 , p3 , . . . , p2t−1 and therefore
deg (g) 6 tm because the degree of each pi is not higher than m.
Table 3.1: Strict BCH binary codes of length 15 and 31, where pi1 ,...,ir =
p i1 · · · p i r .
δ g k d
δ g k d 1 1 31 1
1 1 15 1 3 p1 26 3
3 p1 11 3 5 p1,3 21 5
5 p1,3 7 5 7 p1,3,5 16 7
7 p1,3,5 5 7 9,11 p1,3,5,7 11 11
9–15 X 15 − 1 0 – 13,15 p1,3,5,7,9 6 15
17–31 X 31 − 1 0 –
The Golay code is probably the most important of all codes, for
both practical and theoretical reasons.
F.J. MacWilliams, N.J.A. Sloane, [14], p. 64.
3.21 Example (The binary Golay code). Let q = 2, n = 23 and m = ord n (2)
= 11. So the splitting field of X 23 − 1 ∈ Z2 [X] is L = F211 . The 2-
cyclotomic classes modulo 23 are as follows:
C0 = {0}
C1 = {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}
C5 = {5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14}.
g = (X − ω)(X − ω 2 ) · · · (X − ω δ−1 ),
Summary
Problems
P23 i
P.3.10 (Weight
P24 enumerator of the binary Golay code). Let a = i=0 ai z
and ā = i=0 āi z i be the weight enumerators of the binary Golay code C
and its parity completion C̄, respectively.
3.3. Roots of a cyclic code 141
Use the MacWilliams identities for C̄ to show that ā8 = 759, ā10 = 0
and ā12 = 2576.
3) Show that a7 + a8 = ā8 , a9 = a10 = 0 and a11 = a12 = ā12 /2.
4) Use the MacWilliams identities for C to prove that a7 = 253 and
a8 = 506. Hence the weight enumerator of C is
X 23 − 1 = (X − 1)g0 g1 .
where g0 and g1 have degree 11. The binary Golay code C has been defined
as Cg0 .
1) With the notations of the example 3.21, show that the roots of g0 (g1 )
have the form ω j , where j is a nonzero quadratic residue (a quadratic
non-residue) of Z23 .
2) Using that k = −1 is not a quadratic residue modulo 23, check that
π−1 is the map a 7→ e a that reverses the order of vectors. In partic-
ular we have ge0 = g1 (this can be seen directly by inspection of the
factorization of X 23 − 1 over Z2 ).
P.3.13. For n = 15 and n = 31, justify the values of g, k and d on the table
3.1 corresponding to the different values of δ.
P.3.14 Find a control matrix for a binary BCH code of length 31 that corrects
2 errors.
142 Chapter 3. Cyclic Codes
Essential points
Syndromes
Let g ∈ F[x] be the generating polynomial of a cyclic code C of length n
over F. We want to implement the Meggitt decoder for C (as presented,
for example, in [18], Ch. XVII). In this decoder, a received vector y =
[y0 , . . . , yn−1 ] is seen as a polynomial y0 +y1 x+· · ·+yn−1 xn−1 ∈ F[x]n and
by definition the syndrome of y, S(y), is the remainder of the Euclidean divi-
sion of y by g (in computational terms, remainder(y,g). The vectors with zero
syndrome are, again by definition, the vectors of C. Note that since g divides
X n − 1, S(y) coincides with the n-cyclic reduction of remainder(y(X),g(X).
In the sequel we will not distinguish between both interpretations.
3.23 Proposition. We have the identity S(xy) = S(xS(y)).
Proof: By definition of S(y), there exists q ∈ F[x]n such that y = qg+S(y).
Multiplying by x, and taking residue mod g, we get the result.
3.24 Corollary. If we set S0 = S(y) and Sj = S(xj y), j = 1, . . . , n − 1,
then Sj = S(xSj−1 ).
Summary
3.4. The Meggitt decoder 145
S(axn−1 + e) → axn−1 + e,
Problems
P.3.19. Consider the Hamming code Ham2 (r), regarded as the cyclic code
Cα , where α is a primitive root of F2r . What is the Megitt table in this case?
For r = 4, with α4 = α + 1, decode the vector 15 |010 with the Meggitt
algorithm.
P.3.20. Let α be a primitive element of F16 such that α4 = α + 1 and let
g(x) = x10 + x8 + x5 + x4 + x2 + x + 1
be the generating polynomial of a binary BCH code of type [15, 5]. Assuming
that we receive the vector
v = 000101100100011,
find the nearest code vector and the information vector that was sent.
P.3.21 Let C = BCH α (5), where α ∈ F32 is a root of the irreducible polyno-
mial X 5 + X 2 + 1 ∈ Z2 [X]. Thus C corrects two errors. What is the dimen-
sion of C? Assuming that the received vector has syndrome 1110011101,
and that at most two errors have occurred, find the possible error polynomi-
als.
P.3.22 Let C = BCH α (7), where α ∈ F32 is a root of X 5 +X 2 +1 ∈ F2 [X].
1) Find the generating polynomial of C.
2) Decode the vector 0000000111101011111011100010000.
146 Chapter 4. Alternant Codes
4 Alternant Codes
Essential points
We will also need (in the decoding processes studied in sections 2-4) the
vector
β = [β1 , . . . , βn ], where βi = 1/αi (i = 1, . . . , n),
which of course is defined only if all the αi are not zero. The computation
of this vector is done with the function invert_entries, which yields, when
applied to a vector v, the result of mapping the pure function x → 1/x to all
components of v (see 93 Inverting the entries of a vector).
Alternant codes
equal to
and let C be the alternant binary code associated to H. Let us see that C ≡
[7, 3, 4], so that d = 4 > 3 = r + 1.
First the minimum distance d of C is > 4, as any three columns of H are
linearly independent over F2 . On the other hand, the first three columns and
the column of α5 are linearly dependent, for α5 = α2 + α + 1, and so d = 4.
Finally the dimension of C is 3, because it has a control matrix of rank 4
over F2 , as the link 97 Computing the dimension of alternant codes shows.
4.1. Definitions and examples 151
Reed–Solomon codes
Given distinct elements α1 , . . . , αn ∈ K, we know from Example 1.26 that
the Reed–Solomon code C = RS α1 ,...,αn (k) ⊆ K n (see Example 1.24) has
a control matrix of the form
with Y
hi = 1/( (αj − αi )). [4.3]
j6=i
Hence
RS α1 ,...,αn (k) = AK (h, α, n − k),
where h = (h1 , . . . , hn ) is given by [4.3]. Note that in this case K = K,
hence m = 1, and that the alternant bounds are sharp, because we know that
the minimum distance of C is n − k + 1 = r + 1, where r is the number
of rows of H, and k = n − r. The idea that Reed–Solomon codes can be
defined as a special case of alternant codes is implemented in the function
call RS(α,k) defined in 98 General RS codes.
4.4 Remark (Generalized Reed–Solomon codes). The vector h in the def-
inition of the code RS α1 ,...,αn (k) as an alternant code is obtained from α
(formula [4.3]). If we allow that h can be chosen possibly unrelated to α,
but still with components in K, the resulting codes AK (h, α, n − k) are
called Generalized Reed–Solomon codes, and we will write GRS (h, α, k) to
denote them. See 99 GRS codes for an implementation. It should be clear at
this point that GRS (h, α, k) is scalarly equivalent to RS α (k).
Note that by definition of alternant codes, we have the following relation:
n
if K is a finite field, r a positive integer and h, α ∈ K , the linear code over
K defined by the alternating control matrix H of order r associated to h and
α is the generalized Reed–Solomon code GRS (h, α, r) and
prove that the dual of GRS (h, α, r) is GRS (h0 , α, n − r). This result can
be seen as a generalization of the formula for the control matrix of a Reed–
Solomon code.
152 Chapter 4. Alternant Codes
BCH codes
BCH codes are of great practical importance for error correc-
tions, paticularly if the expected number of errors is small com-
pared with the length.
F. MacWilliams and N. J. A. Sloane, [14], p. 257.
αl α2l α(n−1)l
1 ...
1 α(l+1) α2(l+1) . . . α(n−1)(l+1)
H = .
. .
. .
. ..
. . . .
1 α(l+d−2) α2(l+d−2) . . . α(n−1)(l+d−2)
Primitive RS codes
Beside serving as illuminating examples of BCH codes, they
are of considerable practical and theoretical importance.
F. MacWilliams and N. J. A. Sloane, [14], p. 294.
E.4.3. Show that if α is a primitive element of a finite field F , then the matrix
Vn (α, . . . , αn−k )T is a control matrix for RS (F, k).
E.4.4. Let ρ be a real number such that 0 < ρ < 1 and t a positive integer.
If K denotes an arbitrary finite field, show that the minimum q = |K| such
that the code RS (K, k) has rate at least ρ and corrects t errors satisfies
2t
q >1+ .
1−ρ
Vk (1, ω, . . . , ω n−1 ).
4.5 Proposition (Strict BCH codes are Goppa codes). If ω is a primitive el-
ement of K = Fqm and δ is an integer such that 2 6 δ 6 n, then the code
C = BCH ω (δ) coincides with C 0 = Γ(X δ−1 , α), where
α = (1, ω −1 , . . . , ω −(n−1) ).
the i-th row of H 0 is equal to (1, ω δ−i , . . . , ω (δ−i)(n−1) ). Thus we see that
H 0 is the control matrix H that defines C, but with the rows in reversed order
(note that the number of rows of H 0 is deg (X δ−1 ) = δ − 1).
4.6 Example (A non-strict BCH code that is not Goppa ). Let C be the binary
cyclic code of length 15 generated by g = x2 + x + 1. Let α ∈ F16 be such
that α4 = α + 1. Then the roots of g in F16 are β = α5 and β 2 = α1 0 and
hence C = Cβ = BCH α (2, 5) (the designed distance is 2 and the offset is 5).
The (generalized) control matrix of this code is [1, β, β 2 , . . . , 1, β, β 2 ]. This
cannot have the form [1/g(α0 ), . . . , 1/g(α14 )], with the αi distinct and f a
linear polynomial g with coefficients in F16 . Hence C is not a Goppa code.
Summary
Problems
P.4.4. By the alternant bound, the minimum distance distance d of the Goppa
code defined in the link Constructing Goppa codes satisfies d > 7. Prove
that d = 8.
156 Chapter 4. Alternant Codes
P.4.5 (Examples of Goppa codes that are not cyclic). Let n be a positive
divisor of q − 1 (q a prime power), α ∈ Fq a primitive n-th root of unity
and a = [1, α, . . . , αn−1 ]. Let C = Γ(g, a) be the Goppa code over F
associated to a monic polynomial g ∈ F[X] of degree r and the vector a
(hence we assume g(αi ) 6= 0 for i = 0, . . . , n − 1).
1) Show that G = (αijg(αj )), for 0 6 i 6 n − r − 1 and 0 6 j 6 n − 1,
is a generating matrix of C.
2) Deduce that the elements of C have the form
with f ∈ F[X]n−r .
3) Prove that if C is cyclic then g = X r , and hence that C is a BCH code.
Hint: If C is cyclic, the vector [g(αn−1 ), g(1), . . . , g(αn−1 )] has to
coincide with vf , for some f , but this can only happen if f is constant
and from this one can deduce that g = X r .
In this problem we will see that the code defined by this formula is indeed
Γ(g, α).
1) Given α ∈ K̄ such that g(α) 6= 0, show that x−α is invertible modulo
g and that
1 1 g(x) − g(α)
=− mod g
x−α g(α) x−α
(note that (g(x) − g(α))/(x − α) is a polynomial of degree < r with
coefficients in K̄).
ai
2) Show that the condition ni=0
P
≡ 0 mod g in the definition
x − αi
[4.4] is equivalent to
n
X ai g(x) − g(α)
= 0.
g(αi ) x−α
i=1
4.1. Definitions and examples 157
3) Use the relation in 2 to prove that the code defined by [4.4] has a
control matrix of the form
P.4.7 (Improved minimum distance bounds for binary Goppa codes). With
the same notations as in the preceeding problem, let ḡ be the square closure
of g (ḡ is the lowest degree perfect square that is divisible by g and can be
obtained from g by replacing each odd exponent in the irreducible factoriza-
tion of g by its even successor). We will see (cf. [14], Ch. 12,§3) that if
K = Z2 , then Γ(g, α) = Γ(ḡ, α) and hence that d > r̄ + 1, where d is the
minimum distance of Γ(g, α) and r̄ the degree of ḡ. In particular we will
have d > 2r + 1 if g has r distinct roots.
ai
1) Let a ∈ K n satisfy ni=0
P
≡ 0 mod g and set S = S(a)
x − αi
Q the support of a, so that |S| = s is the weight of a. Let
to denote
fa = i∈S (X − αi ). Show that
X 1
fa = fa0
X − αi
i∈S
(the derivative of fa ).
2) Use the fact that fa and fa0 have no common factors to show that
1
≡ 0 mod g if and only if g|fa0 .
P
i∈S
X − αi
3) Show that fa0 is a square and hence that g|fa0 if and only if ḡ|fa0 . Con-
clude from this that Γ(g, α) = Γ(ḡ, α), as wanted.
Essential points
• Basic concepts: error locators, syndrome (vector and polynomial forms),
error locator polynomial and error evaluator polynomial.
• Basic results: Forney’s formula and the key equation.
• Main result: the solution of the key equation (Berlekamp–Massey–
Sugiyama algorithm).
Basic concepts
Let C be the alternant code associated to the alternant matrix H of order r
constructed with the vectors h and α (their components lie in K 0 = Fqm ).
Let t = br/2c, that is, the highest integer such that 2t 6 r. Note that if we
let t0 = dr/2e, then t + t0 = r (we will use the equivalent equality r − t = t0
in the proof of Lemma 4.12).
Let x ∈ C (sent vector) and e ∈ Fn (error vector, or error pattern). Let
y = x + e (received vector). The goal of the decoders that we will present
in this chapter is to obtain x from y and H when s = |e| 6 t.
Let M = {m1 , . . . , ms } be the set of error positions, that is, m ∈ M
if and only if em 6= 0. Let us define the error locators ηi , i = 1, . . . , s, by
the relation ηi = αmi . Since the αj are different, the knowledge of the error
locators is equivalent to the knowledge of the error positions (given the α’s).
Define the syndrome vector S = (S0 , . . . , Sr−1 ) by the formula
(S0 , . . . , Sr−1 ) = yH T .
Note that S = eH T , as xH T = 0. Consider also the syndrome polynomial
S(z) = S0 + S1 z + · · · + Sr−1 z r−1 .
Since S = 0 is equivalent to saying that y is a code vector, henceforth we
will assume that S 6= 0.
4.2. Error location, error evaluation and the key equation 159
Ps j
E.4.7. Check that Sj = i=1 hmi emi ηi (0 6 j 6 r − 1).
E.4.8. Assuming S 6= 0, prove that the least j such that Sj 6= 0 satisfies
j < s, hence also j < t. Since gcd (z r , S(z)) = z j , gcd (z r , S(z)) has
degree strictly less than s, hence also stricly less than t. Similarly, prove that
deg (S(z)) > t. Hint: If it were j > s we would have S0 = · · · = Ss−1 = 0
and the expressions for Sj in E.4.7 would imply a contradiction.
The error locator polynomial σ(z) is defined by the formula
s
Y
σ(z) = (1 − ηi z).
i=1
Thus the roots of σ are precisely the inverses of the error locators.
We also define the error evaluator polynomial by the formula
s
X s
Y
(z) = hmi emi (1 − ηj z).
i=1 j=1,j6=i
Basic results
4.8 Proposition (Forney’s formula). For k = 1, . . . , s we have
ηk (ηk−1 )
emk =− ,
hmk σ 0 (ηk−1 )
4.9 Theorem (key equation). The polynomials (z) i σ(z) satisfy the con-
gruence
(z) ≡ σ(z)S(z) mod z r .
But
s s
X hmi emi X X
= hmi emi (ηi z)j
1 − ηi z
i=1 i=1 j>0
s
X r−1
X
≡ hmi emi (ηi z)j mod z r
i=1 j=0
r−1 X
s
hmi emi ηij z j
X
=
j=0 i=1
r−1
X
= Sj z j = S(z),
j=0
4.10 Remark. The key equation implies that deg (gcd (z r , S)) < t, because
gcd (z r , S) divides (cf. the first part of E.4.8).
E.4.9. In the case of the code BCH ω (δ, l) over Fq , prove that the syndromes
S0 , . . . , Sδ−2 are the values of the received polynomial (or also of the error
polynomial) on ω l , . . . , ω l+δ−2 . Deduce from this that Sqj = (Sj )q if j, qj ∈
{l, . . . , l + δ − 2}.
4.2. Error location, error evaluation and the key equation 161
The key equation shows that there exists a unique polynomial τ (z) such that
This equation is equivalent to the key equation and one of the main steps in
the decoding of alternant codes is to find its solution (σ and ) in terms of z r
and S(z).
Here we are going to consider the approach based on a modification of
the Euclidean algorithm to find the gcd of two polynomials. This modifica-
tion is usually called Sugiyama’s algorithm (for classical Goppa codes it was
published for the first time in [27]).
Main results
We keep using the notations introduced in the description of Sugiyama’s
algorithm. Recall also that t0 = dr/2e and that r − t = t0 .
4.12 Lemma. Let ¯ = rj , τ̄ = uj , σ̄ = vj . Then
deg (vi ) = deg (qi ) + deg (vi−1 ) (deg (vi−2 < deg (vi−1 )) by induction)
= deg (ri−2 ) − deg (ri−1 ) + r − deg (ri−2 )
= r − deg (ri−1 )
(in the second step we have used the definition of qi and the induction hy-
pothesis). In particular we have
which yields the first inequality. The second inequality is obvious, by defi-
nition of j and ¯.
E.4.11. With the same notations as in Lemma 4.12, use induction on i to
show that
ui vi−1 − vi ui−1 = (−1)i ,
i = 1, . . . , j, and deduce from it that gcd (ui , vi ) = 1. In particular we obtain
that gcd (τ̄ , σ̄) = 1.
4.2. Error location, error evaluation and the key equation 163
4.13 Theorem. With the notations as in Lemma 4.12, there exists ρ ∈ F∗qm
such that σ = ρσ̄ and = ρ¯
.
Proof: Multiplying the key equation (Theorem 4.9) by σ̄, the equality in
Lemma 4.12 by σ, and subtracting the results, we obtain the identity
and
deg (σ¯
) ) 6 t + t − 1 6 r − 1.
= deg (σ) + deg (¯
Since the right hand side of the identity contains the factor z r , we infer that
Therefore
σ|σ̄, σ̄|τ̄ σ.
Since gcd (σ, ) = 1, for no root of σ is a root of , and gcd (τ̄ , σ̄) = 1, by
E.4.11, we get that σ|σ̄ and σ̄|σ, and hence σ = ρσ̄ and = ρ¯ for some
∗
ρ ∈ Fq m .
4.14 Remark. Theorem 4.13 shows that σ̄ and σ have the same roots, so
we can use σ̄ instead of σ in order to find the error locators. In addition,
Forney’s formula proves that we can use σ̄ and ¯ instead of σ and to find
the error values, because it is clear that
ηk ¯(ηk−1 ) ηk (ηk−1 )
= .
hmk σ̄ 0 (ηk−1 ) hmk σ 0 (ηk−1 )
Summary
• The error-locator polynomial σ(z) can also be defined so that its roots
are the error-locators (rather than the inverses of the error locators).
If we do so, and adopt suitable definitions of S(z) and (z), we still
get a Forney’s formula for error-correction and a key equation (z) ≡
σ(z)S(z) mod z r that can be solved with the Sugiyama algorithm
(P.4.9).
Problems
(ηk )
emk = − .
hmk ηkr σ 0 (ηk )
Note that if we let {¯ , σ̄} be the pair returned by sugiyama(zr ,S,t), then the
zeros of σ̄ give the error locators, and the alternative Forney’s formula with
¯ and σ̄ finds the error values.
4.2. Error location, error evaluation and the key equation 165
P.4.10. With the notations introduced in P.4.6, prove that the syndrome Sy∗
with respect to the control matrix H ∗ = U · H = U · Vr (α) · diag (h) of the
received vector y corresponds to the polynomial
n−1
X yi g(z) − g(αi )
Sy∗ (z) = ,
g(αi ) z − αi
i=0
Show also that Sy∗ (z) = Se∗ (z), where e is the error vector.
P.4.11. Continuing Qswith the previous problem, define an error-locator poly-
∗
nomial σ (z) = − ηi ) (as in P.4.9) and an error-evaluator polyno-
P i=1 (zQ
mial ∗ (z) = si=1 emi j6=i (z − ηi ). Then deg (σ ∗ ) = s, deg (ε∗ ) < s
and gcd (σ ∗ , ε∗ ) = 1. Prove that emi = ∗ (ηi )/σ ∗ 0 (ηi ) (the form taken by
Forney’s formula in this case) and the following key equation:
P.4.12. Modify Sugiyama’s algorithm to solve the key equation in the pre-
ceeding problem.
166 Chapter 4. Alternant Codes
Essential points
Introduction
It is fairly clear that the deepest and most impressive result in
coding theory is the algebraic decoding of BCH-Goppa codes.
R.J. McEleice, [15], p. 264.
S = s0 + s1 z + · · · + sr−1 z r−1 .
Implementing BMS
Given an alternant code C, we wish to be able to call alternant_decoder(C)
and have it return the pure function y 7→ x0 , where x0 is the result of applying
the BMS algorithm for the code C to y. If this were the case, we could set
g=alternant_decoder(C) and then apply g to the various vectors y that we
need to decode.
168 Chapter 4. Alternant Codes
Auxiliary functions
To work out this plan, we first explain two auxiliary functions. The first,
zero_positions(f,a), returns, given a univariate polynomial f and a vector a,
the list of indices j for which aj is a root of f . It goes through all the aj
and retains the j for which the value of f is 0 (this is often referred to as the
Chien search).
108 The function zero_positions(f,a)
We will also need flip(v,L). This function replaces, for all j in the list L, the
value vj of the vector v by 1 − vj . In fact, v can also be a list, in which case
the value of flip is a list, and in either case L can be a vector.
109 The function flip(v,L)
Random list of given length of elements of a finite field. For a finite field
(or ring) K of cardinal q, the function element(j,K) returns the j-th element
of K, where 0 6 j 6 q − 1, with a built-in natural order (for example, in the
range j = 0, . . . , p − 1, p the characteristic of K, element(j,K) is the residue
class of j mod p in Zp ⊆ K). Hence we can generate a random element of K
by picking j at random in the range 0 6 j 6 q − 1. Similarly, we can choose
a nonzero element of K by choosing j at random in the range 1 6 j 6 q − 1.
(hence x0 = 0), there has been a decoder error and then we simply return the
matrix [x, e].
118 The function decoder_trial
Examples
In this subsection we will look at a few examples of RS codes that show how
the machinery developed in this section works.
First we will consider RS codes of the form C = RS (K, r), where K is
a finite field and r is a positive integer less than n = q − 1, q = |F | (see
E.4.3). Recall that C has type [n, n − r, r + 1] and that it corrects br/2c
errors. We will also consider an example of the form RS (a, k), where k is
the dimension and a ∈ K n .
Example: RS[12,6,7]
Suppose we want an RS code with rate at least 1/2 which can correct 3 errors.
The table in the listing after E.4.4 tells us that the least possible q is 13. So let
us take q = 13, hence n = 12. Since t = 3, the least possible codimension
is r = 6, thus k = 6.
We can construct this code with the function call RS(Z13 ,6), and we can
observe its working by means of calls to decoder_trial for diverse s, as illus-
trated in the next example.
119 Decoding trials of RS[12,6,7]
Example: RS[26,16,11]
Suppose now that we want an RS code with rate at least 3/5 which can
correct at least 5 errors. This time the table in the listing after E.4.4 tells us
that the least possible q is 27. So let us set q = 27, thus n = 26. Since t = 5,
the least possible codimension is r = 10 and so k = 16.
The construction of this code, and also the observation of its working
by means of calls to decoder_trial(s), is illustrated in the next example for
various s. Note that we use the shorthand notation given by the ind t table.
Note that up to 5 errors it behaves as expected, but that in the case of 6 errors
it lead to a decoder error.
120 Decoding trials of RS[26,16,11]
4.3. The Berlekamp–Massey–Sugiyama algorithm 171
Example RS[80,60,21]
Suppose we want a RS code with rate 3/4 and correcting 10 errors. Then
d = 21, hence k = n − 20. On the other hand k = 3n/4 and so n =
80. We could take K = F81 , but since Z83 has simpler arithmetic, we can
choose this latter field as K and use only 80 of its nonzero elements. We
can let n = 80 and a = (a1 , . . . , an ), where aj = [j]n and use the code
RS (a, 60). Happily, this code is alternant (and in general such codes are
neither Goppa nor BCH ) and hence that can be decoded with the AD decoder.
In the following example we have indicated a decoder trial of 10 errors, but
we have not displayed the result because of its length.
121 RS with rate 3/4 that corrects 10 errors
Summary
Problems
P.4.13. Find a RS code that has rate 3/5 and which corrects 25 errors. What
are its parameters? Which is the field with smallest cardinal that can be used?
Estimate the number of field operations needed to decode a vector with the
AD decoder.
Essential points
• Finding the number of errors by means of the matrices A` (formula
[4.6]).
• Finding the error-locator polynomial by solving a system of linear
equations.
• The algorithm of Peterson–Gorenstein–Zierler (PGZ).
We will present another algorithm for decoding alternant codes. Let us use
the notations introduced at the beginning Section 4.2, but define the error-
locator polynomial σ as:
s
Y
σ(z) = (z − ηi ), [4.5]
i=1
Proof: Let M 0 = {m01 , ..., m0` } ⊆ {0, ..., n − 1} be any subset such that
M ⊆ M 0 . For i = 1, ..., `, set ηi = αm0i . As we have seen, for j =
0, . . . , r − 1 we have
s `
hm0k em0k ηkj
X X
j
Sj = hmk emk αm k
=
k=1 k=1
Let
D = diag (hm01 em01 , ..., hm0` em0` ),
so that it is clear that det(D) 6= 0 if ` = s and that det(D) = 0 if ` > s. Let
us also write
W = V` (η1 , ..., η` ),
where V` (η1 , ..., η` ) is the Vandermonde matrix of ` rows associated with the
elements ηi . Note that in particular we have det(W ) 6= 0. We also have
W DW T = A` ,
since the i-th row of W (i = 0, ..., ` − 1) is (η1i , ..., η`i ), the j-th row of
DW T (j = 0, ..., ` − 1) is (hm01 em01 η1j , ..., hm0` em0` η`j )T , and their product is
P` i+j
k=1 hm0k em0k ηk = Si+j .
Thus we have det(A` ) = det(D) det(W )2 , which vanishes if ` > s (in
this case det(D) = 0), and is nonzero if ` = s (in this case det(D) 6= 0 and
det(W ) 6= 0).
Proof: Since det As 6= 0, we only have to show that the relation is satisfied.
Substituting z by ηi in the identity
s
Y
(z − ηi ) = z s + a1 z s−1 + ... + as
i=1
ηis + a1 ηis−1 + · · · + as = 0,
where i = 1, ..., s. Multiplying by hmi emi ηij and adding with respect to i,
we obtain the relations
Sj+s + a1 Sj+s−1 + · · · + as Sj = 0,
where j = 0, ..., s − 1, and these relations are equivalent to the stated matrix
relation.
Algorithm PGZ
Putting together Lemma 4.16 and Proposition 4.17 we obtain an algorithm to
decode alternant codes. In essence this algorithm is due to Peterson, Goren-
stein and Zierler (see [19]). In detail, and with the same conventions as in
the BMS algorithm concerning the meaning of Error, we have:
1) Calculate the syndrome vector, yH T = (S0 , ..., Sr−1 ). If S = 0,
return y.
2) Thus we can assume that S 6= 0. Starting with s = t, and while
det(As ) is zero, set s = s − 1. At the end of this loop we still have
s > 0 (otherwise S would be 0) and we assume that s is the number
of errors.
3) Solve for a in the matrix equation As a = −b (see Proposition 4.17).
After this we have a1 , ..., as , hence also the error-locator polynomial σ.
4) Find the elements αj that are roots of the polynomial σ. If the number
of these roots is < s, return Error. Otherwise let η1 , ..., ηs be the
error-locators corresponding to the roots and set M = {m1 , . . . , ms },
where ηi = αmi .
5) Find the error evaluator (z) by reducing the product
(1 + a1 z + · · · + as z s )S(z)
6) Find the errors emi using Forney’s formula with the error-locator poly-
nomial 1 + a1 z + · · · + as z s and the error-evaluator ε(z). If any of the
error-values is not in K, return Error. Otherwise return y − e.
Summary
• Assuming that the received vector has a nonzero syndrome, the num-
ber of errors is determined as the first ` in the sequence t, t − 1, ... such
that det(A` ) 6= 0, where A` is the matrix [4.6].
• The error-locator polynomial [4.7] is found by solving a system of
linear equations As a = −b defined in Proposition 4.17.
• The error values are obtained by finding the error evaluator polyno-
mial via the key equation, and then applying Forney’s formula, or by
solving the system of linear equations in Remark 4.20.
• The three steps above summarize the PGZ algorithm.
178 Chapter 4. Alternant Codes
Problems
P.4.17. We have explained the PGZ algorithm under the assumption that
s 6 t. If the received vector is such that s > t, analyze what can go wrong
at each step of the algorithm and improve the algorithm so that such errors
are suitably handled.
P.4.18. Let α be a primitive root of F16 satisfying α4 = α + 1 and consider
the code C = BCH α (5). Decode the vector 100100110000100.
1) with the Euclidean algorithm;
2) with the PGZ algorithm.
4.21 Remark. Most of the books cited in the bibliography contain a good
deal of exercises and problems. One reference to take into account in that
regard, and also for many other topics not presented here, is [21]. For a book
exclusively devoted to exercises and problems on error-correcting codes, and
related topics, the reader is referred to [20].
Appendix: The WIRIS/cc system
A.1 (User interface). The WIRIS user interface has several palettes and each
palette has several icons. Palette icons are useful to enter expressions that
are typeset on the screen according to standard mathematical conventions.
In the Operations palette, for example, we have icons for fractions, pow-
ers, subindices, roots, and symbolic sums and products. Here is a sample
expression composed with that palette: 125 Some WIRIS expressions .
In addition to the above style (WIRIS or palette style) the WIRIS interface
also supports a keyboard style, which only requires the keyboard to compose
expressions. In some cases the keyboard style is indistinguishable from the
palette style, as for example the = operator, but generally it is quite different,
as a.i for the subindex expression ai , or Zn(n) for Zn (the ring of integers
modulo n).
A.2 (Blocks and statements). At any given moment, a WIRIS session has one
or more blocks. A block is delimited by a variable height ‘[’. Each block con-
tains one or more statements. A statement is delimited by a variable length
|. A statement is either an empty statement or an expression or a succession
of two or more expressions separated by semicolons. The semicolon is not
requiered if next expression begins on a new line. An expression is either
a formula or an assignment. A formula is a syntactic construct intended to
compute a new value by combining operations and values in some explicit
way. An assignment is an expression that binds a value to a variable (see A.5
for more details).
The active block (active statement) displays the cursor. Initially there is
just one empty block (that is, a block that only contains the null statement).
Blocks can be added with the [| icon in the Edit palette (the effect is a new
empty block following the active block, or before the first if the cursor was at
180 Appendix
the beginning of the first block). Pressing the Enter key adds a null statement
just before or just after the current statement according to whether the cursor
is or is not at the beginning of that statement.
A.3 (Evaluation). The evaluation of all the statements in the active block
is requested with either Ctrl+Enter or by clicking on the red arrow. The
value of each statement in the block is computed and displayed next to it
with the red arrow in between (the value of a statement is the value of its last
expression). After evaluation, the next block, if there is one, becomes the
active block; otherwise an empty block is appended.
In the following we will typeset input expressions in a sans serif font,
like in a+b, and the output values in the usual fonts for mathematics, like in
a + b, if this distinction may possibly be helpful to the reader.
A.4. Integers, like 314, and operations with integers, like (2 + 3) · (11 − 7)
or 264 , are represented in the usual way: 126 Integers .
In the link above there are two text lines. These lines were entered in
the usual way and converted to text with the T icon in the Edit menu. In
general, this icon converts the active statement into text and vice versa. Text
is not evaluated and retains all its typographical features. In particular, all
the services for composing expressions are available while editing it. Finally
note that text is not delimited by a variable height | in the way statements
are.
An identifier that has not been bound to a value is said to be a free iden-
tifier (or free variable). Otherwise it is said to be a bound identifier (or a
bound variable).
Syntactic constructs that have the form x=e, x:=e or let x=e are called
assignments, or assignment expressions.
127 Assignment examples
A.6 (Modular arithmetic and finite prime fields). The construction of the ring
Zp of integers modulo the positive integer p is performed by the function
Zn(p), in keyboard style, and with the subindex operation to the symbol Z in
WIRIS style. If we put A=Zn(p) and n is an integer, then the class of n mod
p is the value of the expression n:A (for more details on this construct, see
A.15). Operations in the ring A are denoted in the usual way: 128 Z35 . Note
that the inverse of 22 mod 35 is 8, and that the inverse of 7 mod 35 does not
exist (this is why 1/x is left unevaluated and an error message is reported).
Note also that WIRIS does not display the value of a statement which ends
with a semicolon. The reason for this is that in this case the last expression
of the statement actually is null (cf. A.2).
For j = 0, . . . , n − 1, the value of element(j,Zn ) is the class [j]n .
The ring Zp is a field if and only if p is prime. Note, in particular, that
Zn(2) constructs the field of binary integers. 129 Z7 .
A.7 (Construction of field and ring extensions). Suppose K is a ring and that
f∈ K[x] is a monic polynomial of degree r. Then the function extension(K,f),
which can be also called with the expression K[x]/(f), constructs the ring K 0 =
K[x]/(f ). The variable x is assigned the class of x mod f and K is a subring
of K 0 . The name of K[x]/(f) is still K[x], but here x is no longer a variable,
but an element of K 0 that satisfies the relation f (x) = 0. When K is finite
with q elements, then K 0 is finite with q r elements. If K is a field and f is
irreducible over K, then K 0 is a field. If we want to use a different name
for the variable x of the polynomials and the variable α to which its class
modulo f is bound, we can use extension(K,α,f).
If R is a finite ring, cardinal(R) yields the number of elements of R and
characteristic(R) yields the minimum positive number n such that n:R is
zero. If n is the cardinal of R, the elements of R can be generated with
element(j,R), for j in the range 0..(n-1).
To test whether a ring K is a finite field, we can use the Boolean function
Finite_field(K), or its synonym GF(K), which is defined as the expression
is?(K,Field) & (cardinal(K)<infinity)?
130 The call extension(K,a,f)
A.8 (Sequences). Sequences are generated with the comma operator ‘,’. The
only sequence with 0 terms is null. If s and t are sequences with m and n
182 Appendix
domain(P). In the case of divisors, we get the same value with support(P).
Pairings have a functional charater. To see this, let us consider each
flavor separately. If R is a relation (respectively a table) and a is an object
(an identifier), the value of the expression R(a) is the sequence (possibly the
null sequence) formed with the values b such that a→b (a=b) is a term in R.
The value of R is the relation (table) R whose terms have the form a → R(a)
(a = R(a)) where a runs over domain(R).
131 Relation examples
A.11 (Lists and vectors). Aggregates delimited by braces (brakets) and which
184 Appendix
For a list or a range x, vector(x) returns the vector formed with the ele-
ments of x (this is the same as [x] if x is a range; when x is a list, however,
[x] is a vector with x as unique component). On the other hand, list(x) yields
the list with the same elements as x when x is a vector, and just a list whose
only element is x when x is a range. More generally, if x is a sequence of
ranges, then [x] is the vector formed with the elements of all the ranges in x,
while {x} is just the list of the ranges in the sequence.
To append an object a to a list or vector x, we have the function ap-
pend(x,a). It can also be obtained with x|{a} if x is a list or x|[a] if x is a
vector.
137 Append examples
A.13 (Matrices). Structurally, matrices are vectors whose entries are vectors
of the same length. So if we set A=[[1,2],[2,-3]], then A is a 2×2 matrix whose
rows are the vectors [1,2] and [2,-3]. Writing matrices and working with them
can be done quickly using the Matrices palette 140 Matrix expressions ).
The expression dimensions(A), A a matrix, gives a sequence m, n such
that m and n are the number of rows and columns of A, respectively. The in-
tegers m and n can also be obtained separately as the values of the functions
n_rows(A) and n_columns(A), which are abbreviations of number_of_rows(A)
and number_of_columns(A). The transpose of A is AT (or transpose(A)).
If A is a matrix, x is a vector, and the number of columns (rows) of A is
equal to the length of x, then the values AxT (respectively xA) are obtained
with the expressions A·x (respectively x·A). In the expression A·x the vector
x is automatically interpreted as a column vector. Similarly, if A and B are
matrices, and the number of columns of A is equal to the number of rows of
B, then A·B computes the product AB.
The element in row i column j of A can be obtained with the expression
Ai,j (or A.i.j in keyboard form). On the other hand, if I and J are lists, AI forms
a matrix with the intersections of the rows of A specified by I (if these rows
exist) and AI,J forms a matrix with the intersections of the rows and columns
of A specified by I and J, respectively (provided these rows and columns
exist).
If A and B are matrices with the same number of rows (columns), then the
A
matrix A|B (respectively ) is the value of the expression A|B (respectively
B
A&B).
The expression identity_matrix(r) (or also Ir in WIRIS) yields Ir , the iden-
tity matrix of order r. Another basic constructor is constant_matrix(m,n,a),
which yields an m × n matrix with all entries equal to a. The expression
constant_matrix(n,a) is equivalent to constant_matrix(n,n,a).
In the case of square matrices A, its determinant is given by |A| (or de-
terminant(A)). Similarly, trace(A) returns the trace of A. If |A| = 6 0, then A−1
(or inverse(A)) gives the inverse of A.
A.14 (Boolean expressions). The basic Boolean values are true and false. In
general, a Boolean expression (a Boolean function in particular) is defined as
any expression whose value is true or false.
If a and b are Boolean expressions, then not a (or not(a)) is the negation
of a, and a&b, a|b are the conjunction and disjunction of a and b, respec-
186 Appendix
tively. The negation of a is true if and only if a is false. Similarly, the con-
junction (disjunction) of a and b is true (false) if and only if both expressions
are true (false).
Another way of producing Boolean expressions is with the question mark
(?) placed after a binary relation, as for example 3>2 ?, whose value is true,
or 3==2?, whose value is false. Since ? is considered a literal character,
and hence it can be used to form identifiers, the space before ? is required
if, appended to the preceeding token, it would form a valid identifier. If in
doubt, use parenthesis to surround the binary relation. On the other hand, ?
may be omitted when the binary relation is used in a context that expects a
Boolean expression, as for example in the if field of a conditional expression.
There are a few Boolean functions whose identifiers end with a question
mark. For example:
even?(n)
Yields true if the integer n is even and false otherwise.
invertible?(x)
For a ring element x, it yields true when x is invertible in its ring, and false
otherwise.
irreducible?(f,K)
For a field K and a polynomial f with coefficients in K, tests whether f is
irreducible over K or not.
is?(x,T)
Tests whether x has type T (see page 187)
monic?(f)
Decides whether a polynomial f is monic or not.
odd?(n)
Yields true if the integer n is odd and false otherwise.
prime?(n)
Decides whether the integer n is prime or not.
zero?(x)
For a vector x, it returns true if x is the zero vector and false otherwise.
A.15 (Functions). A WIRIS function f (where f stands for any identifier) with
argument sequence X is defined by means of the syntax f(X) := F, where F
(the body of the function) is the expression of what the function is supposed
Appendix 187
to do with the parameters X. The same name f can be used for functions that
have a different number of arguments.
Often the value of a function is best obtained through a series S of con-
secutive steps. Formally we take this to mean that S is a statement (see A.2,
page 179). But a statement S with more than one expression is not con-
sidered to be an expression and hence cannot by itself form the body of a
function. To make an expression out of S we have the construct begin S end.
if b then S end
Evaluate S in case the value of b is true.
if b then S else T end
Evaluate of S or T according to whether the value of the Boolean expression
b is true or false.
while b do S end
Keep evaluating S as long as b evaluates to true.
repeat S until b
Evaluate S once and keep doing it so long as the value of b is false.
for x in X do S end
Evaluate S for any x running over the items of X.
for I; b; U do S end
Start evaluating I, which must be a sequence of expressions. Then evaluate
S and U (U must also be a sequence of expressions) as long as b evaluates to
true.
continue
The presence of this directive somewhere in the S of a while, repeat or for
iterators skips the evaluation process of the remaining expressions of S and
continues from there on.
break
The presence of this directive somewhere in the S of a while, repeat or for
iterators exits the iteration and continues as if it had been completed.
with, such_that
The expression {e with x in X such_that b } groups with braces the expres-
sions e that satisfy b, where the Boolean expressionn b depends on x, which
in turn runs over the terms of X. The expression {x in X such_that b } groups
with braces the terms x of X that satisfy b. There are similar constructions
using brakets instead of braces. The directives such_that and where are syn-
omyms.
return R
Exit a function with the value of the expression R.
If b isP
a Boolean expression, then sigma e with i in r such_that b yield a
sum like i∈r e(i), but restricted to the i ∈ r such that b(i) is true. In palette
Y
style, e (to get a new line for the condition b, press Shift-Enter). The
i in r
b
case of products works similarly.
143 Sum and product examples
190 Bibliography
Bibliography
[14] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-correcting Codes.
Number 6 in Mathematical Library. North-Holland, 1977.
[15] R.J. McEliece. The Theory of Information and Coding: A Mathematical
Framework for Communication. Number 3 in Encyclopedia of Mathematics
and its Applications. Addison-Wesley, 1977.
[16] R.J. McEliece. Finite Fields for Computer Scientists and Engineers. Kluwer
Academic Publishers, 1987.
[17] A.J. Menezes, editor. Applications of finite fields. Kluwer Academic Publish-
ers, 1993.
[18] O. Papini and J. Wolfmann. Algèbre discrète et codes correcteurs. Springer-
Verlag, 1995.
[19] W.W. Peterson and E.J. Weldon. Error-correcting codes. MIT Press, 1972.
2nd edition.
[20] A. Poli. Exercices sur les codes correcteurs. Masson, 1995.
[21] A. Poli and LL. Huguet. Codes correcteurs, théorie et applications. Number 1
in LMI. Masson, 1989.
[22] O. Pretzel. Error-Correcting Codes and Finite Fields. Oxford Appl. Math.
and Computing Sci. Series. Calrendon Press · Oxford, 1992.
[23] J.G. Proakis and M. Salehi. Communications Systems Engineering. Prentice
Hall, 2nd edition edition, 2002.
[24] S. Roman. Coding and Information Theory. Number 134 in Graduate Texts in
Mathematics. Springer-Verlag, 1992.
[25] C.E. Shannon. A mathematical theory of communication. Bell System Tech.
J., 27:379–423,623–656, 1948.
[26] M. Sudan. Algorithmic Introduction to Coding Theory. MIT/Web, 2002.
[27] Y. Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa. A mehod for
solving the key equation for decoding goppa codes. Information and Control,
27:87–99, 1975.
[28] M. Tsfasman and S. Vladut. Algebraic-geometric codes. Kluwer, 1991.
[29] J.H. van Lint. Introduction to Coding Theory. Number 82 in GTM. Springer-
Verlag, 1999. 3rd edition.
[30] J.H. van Lint and R.M. Wilson. A course in combinatorics. Cambridge Uni-
versity Press, 1992.
[31] S.A. Vanstone and P.C. van Oorschot. An Introduction to Error Correcting
Codes with Applications. The Kluwer Intern. Ser. in Engineering and Com-
puter Science. Kluwer Academic Publishers, 1989.
[32] S.B. Wicker. Deep space applications. In V.S. Pless and W.C. Huffman, edi-
tors, Handbook of Coding Theory, volume II, pages 2119–2169. Elsevier Sci-
ence B.V., 1998.
192 Bibliography
[33] S.B. Wicker and V.K. Bhargava, editors. Reed-Solomon codes and their ap-
plications. The Institute of Electrical and Electronics Engineers, 1994.
[34] S. Xambó-Descamps. O MEGA : a system for effective construction, cod-
ing and decoding of block error-correcting codes. Contributions to Science,
1(2):199–224, 2001. An earlier version of this paper was published in the
proceedings of the EACA-99 (Fifth “Encuentro de Algebra Computacional y
Applications” (Meeting on Computational Algebra and Applications), Santa
Cruz de Tenerife, September 1999).
Index of Symbols
n
k n!/k!(n − k)! (binomial number)
bxc Greatest integer that is less than or equal x
dxe Smallest integer that is greater than or equal x
tn Vector [t, ..., t] of length n. Examples used often: 0n and 1n
x|y Concatenation of x and y (x and y may be vectors or lists)
hx|yi x1 y1 + . . . + xn yn (scalar product of vectors x and y)
|X| Number of elements of a set X
A∗ Group of invertible elements of the ring A
A[X] Ring of polynomials in X with coefficients in A
Zn Ring of integers modulo n
Fq , GF (q) Field of q elements (q must be a prime power)
F∗q Group of nonzero elements of Fq
[L : K] Degree of a field L over a subfield K
Ir Identity matrix of order r
Mnk (A) Matrices of type k × n with entries in A
Other than the general mathematical notations explained above, we list sym-
bols that are used regularly in the book, followed by a short description and,
enclosed in parenthesis, the key page number(s) where they appear. We do
not list symbols that are used only in a limited portion of the text.
The table below includes the basic WIRIS/cc expressions explained in the Ap-
pendix which might be non-obvious. The first field contains the expression
in a keyboard style, optionally followed by the same expression in palette
style (A.1, page 179). The second field is a brief description of the expres-
sion. The WIRIS/cc functions used in the text are included in the alphabetical
index.
Index of Symbols 195
= Assignment operator
:=, =: Delayed assignment operator
==, = Binary operator to create equations
−>, → Operator to create pairs in a relation or divisor
!=, 6= Not equal operator
>=, > Greater than or equal operator
<=, 6 Less than or equal operator
=>, ⇒ Operator to create pairs in a substitution or rule
$$ Operator to create compound identifiers (76)
| Disjunction (and concatenation) operator (185)
& Boolean conjunction operator (185)
Zn(p), Zp Ring of integers mod p, Fp if p is prime (181)
n:A Natural image of n in A (181)
x=e Bounds the value of e to x (180)
a..b..d {x ∈ [a, b] | x = a + jd, j ∈ Z, j > 0} (182)
a..b Usually a..b..1 (182)
[x1 , · · · , xn ] Vector whose components are x1 , · · · , xn (184)
{x1 , · · · , xn } List of the objects x1 , · · · , xn (184)
A-1 The inverse of an invertible matrix A (185)
AT The transpose of a matrix A (185)
|A| The determinant of a square matrix A (185)
A|B If A and B are matrices with the same number of rows,
the matrix obtained by concatenating each row of A
with the corresponding row of B (185)
A&B Matrix A stacked on matrix B (A.13, page 185)
x·y, hx,yi The scalar product of vectors x and y (A.12, page 185)
Alphabetic Index, Glossary and Notes
The entries of the index below are ordered alphabetically, with the convention that
we ignore blanks, underscores, and the arguments in parenthesis of functions. Each
entry is followed by information arranged in two fields. The first field, which is op-
tional, consists of the page number or numbers, enclosed in parenthesis, indicating
the more relevant occurrences of the entry. The second field may be a pointer to
another index entry or a brief summary of the concept in question.
There are two kinds of of entries: those that refer to mathematical concepts,
which are typeset like alphabet, and those that refer to WIRIS/cc constructs, which
are typeset like aggregate. Those entries that do not refer directly to a concept
introduced in the text (see, for example, covering radius or Fermat’s little theorem)
constitute a small set of supplementary notes.
In the summaries, terms or phrases written in italics are mathematical entries.
Acronyms are written in italic boldface, like BSC. Terms an phrases typeset as ag-
gregate refer to WIRIS/cc entries.
A
active block (179) In a WIRIS session, the block that displays the blinking cursor (a
thick vertical bar).
active statement (179) In a WIRIS session, the statement that displays the blinking
cursor (a thick vertical bar).
AD(y,C) (168) Equivalent to alternant_decoder(y,C).
additive representation (106) [of an element of a finite field with respect to a subfield]
The vector of components of that element relative to a given linear basis of the field
with respect to the sufield. Via this representation, addition in the field is reduced to
vector addition in the subfield.
aggregate (182) A range, list, vector or pairing.
alphabet A finite set. See source alphabet and channel alphabet. See also binary
alphabet.
alternant bounds (149) For an alternant code C, dC > r + 1 (alternant bound for the
minimum distance) and n−r > kC > n−rm (alternant bounds for the dimension),
where r is the order on the alternant control matrix H ∈ Mnr (K̄) that defines C and
m = [K̄ : K].
alternant codes (149) An alternant code over a finite field K is a linear code of the
form {x ∈ K n | xH T = 0}, where H ∈ Mnr (K̄) is an alternant control matrix
defined over a finite field K̄ that contains K. General RS codes and BCH codes are
alternant codes (see page 151 for RS codes and page 152 for BCH codes).
alternant_code(h,a,r) (149) Creates the alternant code associated to the matrix con-
trol_matrix(h,a,r).
alternant control matrix (148) A matrix H of the form H = Vr (α)diag (h) ∈
Mnr (K̄), where r is a positive integer (called the order of the control matrix) and
h, α ∈ K̄ n (we say that H is defined over K̄).
alternant_decoder(y,C) (168) Decodes the vector y according to the BMS decoder for
the alternant code C.
Index-Glossary 197
B
Bassalygo–Elias bound See Elias bound.
BCH Acronym for Bose–Chaudhuri–Hocquenghem.
BCH(α,d,l) (152) Creates the code BCH α (d, l) of designed distance d and offset l
based on the element α.
BCH bounds See BCH codes.
BCH codes The BCH code of length n, designed distance δ and offset ` over Fq ,
which is denoted C = BCH ω (δ, `), is the cyclic code with roots ω `+i , for i =
0, . . . , δ − 2, where ω is a primitive n-th root of unity in a suitable extension of
Fq . The minimum distance of C is at least δ (BCH bound of the minimum distance,
Theorem 3.15). The dimension k of C satisfies n − (δ − 1) > k > n − m(δ − 1),
where m is the degree of ω over Fq (BCH bounds of the dimension, Proposition
3.18). In the binary case, the dimension lower bound can be improved to k > n−mt
if δ = 2t + 1 (Proposition 3.19). When ` = 1, we write BCH ω (δ) instead of
BCH ω (δ, 1) and we say that these are strict BCH codes. Primitive BCH codes are
BCH codes with n = q m − 1 for some m.
begin S end (187) This construct builds an expression out of statement S.
BER Acronym for bit error rate.
Berlekamp algorithm [for factoring a polynomial over Fq ] In this text we have only
developed a factorization algorithm for X n −1 (page 130). There are also algorithms
for the factorization of arbitrary polynomials. For an introduction to this subject,
including detailed references, see [17], Chapter 2.
bezout(m,n) This function can be called on integers or univariate polynomials m, n.
It returns a vector [d, a, b] such that d = gcd (m, n) and d = am + bn (Bezout’s
identity). In fact a and b also satisfy |a| < |n| and |b| < |m| in the integer case, and
deg (a) < deg n and deg (b) < deg m in the polynomial case.
binary alphabet (12) The set {0, 1} of binary digits or bits. Also called binary num-
bers.
binary digit (2,12) Each of the elements of the binary alphabet {0, 1}. With addition
and multiplication modulo 2, {0, 1} is the field Z2 of binary numbers.
binary symmetric channel (2) In this channel, the symbols sent and received are bits
and it is characterized by a probability p ∈ [0, 1] that a bit is altered (the same for
198 Index-Glossary
0 and 1). Since p denotes the average proportion of erroneous bits at the receiving
end, it is called the bit error rate (BER ) of the channel.
bit (2, 12) Acronym for binary digit. It is also the name of the fundamental unit of
information.
bit error rate (2) See binary symmetric channel.
block (179) In a WIRIS session, each of the sets of statements delimited by a variable
height ‘[’. Each statement in a block is delimited with a variable height ‘|’.
block code (13) If T is the channel alphabet and q = |T |, a q-ary block code of
length n is a subset C of T n .
block encoder (12) An encoder f : S → T ∗ such that f (S) ⊆ T n for some n (called
the length of the block encoder).
blow(h,F) (150) For a finite field F=K[x]/(f) and a vector h with entries in F, it creates
a vector with entries in K by replacing each entry of h by the sequence of its com-
ponents with respect to the basis 1, x, . . . , xr−1 of F as a K-vector space. If H is a
matrix with entries in F, then blow(H,F) is the result of replacing each column h of
H by blow(h,F).
BMS (166) Acronym for Berlekamp–Massey–Sugiyama.
BMS algorithm (167) A decoding algorithm for alternant codes based on Sugiyama’s
method for solving the key equation and on Forney’s formula for the determination
of the error values.
Boolean expression (185) An expression whose value is true or false.
Boolean function (185) An function whose value is true or false.
BSC Acronym for binary symmetric channel.
C
capacity (4) It measures the maximum fraction of source information that is available
at the receiving end of a communication channel. In the case of a binary symmet-
ric channel with bit error probability p, it is a function C(p) given by Shannon’s
formula C(p) = 1 + p log2 (p) + (1 − p) log2 (1 − p).
cardinal(R) (181) The cardinal of a ring R.
Cauchy matrix (157) A matrix of the form (1/(αi − βj )), where α1 , . . . , αn and
β1 , . . . , βn belong to some field and αi 6= βj for 1 6 i, j 6 n.
cauchy_matrix(a,b) Given vectors a and b, this function constructs the Cauchy matrix
(1/(ai − bj )), provided that ai 6= bj for all i, j with i in range(a) and all j in
range(b).
channel Short form of communication channel.
channel alphabet (11) The finite set T of symbols (called channel symbols) with
which the information stream fed to the communication channel is composed. It is
also called transmission alphabet. Although we do make the distinction in this text,
let us point out that in some channels the input alphabet may be different from the
output alphabet.
channel coding theorem (4) If C is the capacity of a BSC, and R and ε are positive
real numbers with R < C, then there exist block codes for this channel with rate at
least R and code error rate less than ε.
channel symbol See symbol.
characteristic [of a ring or field] See characteristic homomorphism.
characteristic(R) (181) The characteristic of a finite ring R.
Index-Glossary 199
D
decoder A decoding function.
decoder error (16) It occurs when the received vector is non-decodable.
decoder_trial(C,s,K) (170) For a code C over a finite field K and a positive integer s,
this function generates a random vector x of C, a random error vector e of weight
s, and calls alternant_decoder(x+e,C). If the result x0 coincides with x, [x, e, x +
e] is returned. If x0 6= x, but otherwise is a vector, [x, e, x + e, x0 ] is returned.
202 Index-Glossary
dual Hamming code (45) Denoted Ham∨ a (r), it is the dual of the Hamming code
Hamq (r). It is equidistant with minimum distance q r−1 (Proposition 1.43). These
codes satisfy equality in the Plotkin bound (Example 1.65).
E
Element(Field) The type of objects that happen to be an element of some field.
element(j,R) (181) For a finite ring R of cardinal n, this function yields the elements
of R when j runs over the range 0..(n-1).
elias(x) (79, 80) Computes the asymptotic Elias upper bound.
Index-Glossary 203
error vector (158) Also called error pattern, it is defined as the difference y − x
between the sent code vector x and the received vector y.
Euler’s function ϕ(n) (87) For an integer n > 1, ϕ(n) counts the number of integers
k such that 1 6 k 6 n − 1 and gcd (k, n) = 1. It coincides with the cardinal of the
group Z∗n . The value of ϕ(1) is conventionally defined to be 1.
evaluate(f,a) Yields the value of a polynomial f at a. Here a is a list with as many
terms as the number of variables of f, as in evaluate(x3 +y5 ,{3,2}). In the case of
a single variable, the braces surrounding the unique object can be omitted (thus
evaluate(x3 +x5 ,{17}) and evaluate(x3 +x5 ,17) are equivalent).
evaluation (180) In a WIRIS session, the action and result of clicking on the red ar-
row (or by pressing Ctrl+Enter). The value of each statement of the active block
is computed and displayed, preceeded by a red arrow icon, to the right of the state-
ment.
even?(n) (186) This Boolean function tests whether the integer n is even.
exponent [of a monic irreducible polynomial] See primitive polynomial.
exponential representation (106) The expression x = αi of a nonzero element x of
a finite field L as a power of a given primitive element α. The exponent i is called
the index (or discrete logarithm) of x with respect to α, and is denoted ind α (x). If
we know i = ind α (x) and j = ind α (y), then xy = αk , where k = i + j mod q − 1
(q the cardinal of L). This scheme for computing the product, which is equivalent
to say that ind α (xy) = ind α + ind α (y) mod q − 1, is called index calculus (with
respect to α). In practice, the index calculus is implemented by compiling a table,
called an index table, whose entries are the elements x of L (for example in additive
notation) and whose values are the corresponding indices ind α (x).
expression (179) A formula or an assignment (see statement).
extension(K,f) (95, 181) Given a ring K and a polynomial f∈K[x] whose leading co-
efficient is invertible (a monic polynomial in particular), then extension(K,f), or the
synomym expression K[x]/(f), constructs the quotient K[x]/(f ) and assigns the class
of x to x itself (thus the result is equivalent to the ring K[x], with f (x) = 0. If we
want another name α for the class of x, then we can use the call extension(K,α,f).
F
factor(f,K) Given a field K and a polynomial f with coefficients in K, finds the factor-
ization of f into irreducible factors.
factorization algorithm (130) When gcd (q, n) = 1, the irreducible factors of the
polynomial X n − 1 ∈ Fq [X] are fC = j∈C (X − ω j ), where C runs over the
Q
q-cyclotomic classes mod n and ω is a primitive n-th root of unity in Fqm , m =
ord n (q).
false (185) Together with true forms the set of Boolean values.
Fermat’s little theorem It asserts that if p is a prime number and a is any integer
not divisible by p, then ap−1 ≡ 1 (mod p). This is equivalent to say that any
nonzero element α of the field Zp satisfies αp−1 = 1. We have established two
generalizations of this statement: one for the group Z∗n (see E.2.5) and another for
the multiplicative group of any finite field (see E.2.6).
Field (187) The type associated to fields.
field (84) A commutative ring for which all nonzero elements have a multiplicative
inverse.
Index-Glossary 205
field(a) Assuming a is an element of some field F, this function returns F. For exam-
ple, the value of field(2/3) is Q, and the value of field(5:Z11 ) is Z11 .
filter (187) Any Boolean expression F, which may include types, used in the form x:F
to check that an argument x of a function has the required properties.
Finite_field(K) (181) This Boolean function, or its synonym GF(K), tests whether K
is a Galois field.
finite fields (92) A finite field (also called a Galois field) is a field K whose cardinal
is finite. If q = |K|, then q must be a prime power (Proposition 2.8): q = pr , p
the characteristic of K and r a positive integer. Conversely, if p is a prime number
and r a positive integer, then there is a finite field of pr elements (Corollary 2.18).
Furthermore, any two fields whose cardinal is pr are isomorphic (Theorem 2.41).
This field is denoted Fq , or GF (q). Note that Fp = Zp , the field of integers mod p.
For any divisor s of r there is a unique subfield of Fpr whose cardinal is ps , and
these are the only subfields of Fpr (E.2.15).
flip(x,I) The components xi of the vector x indicated by the elements i of the list I are
replaced by 1 − xi . For a binary vector this amounts to complement the bits at the
positions indicated by I. We remark that I can be a range or a vector. On the other
hand, flip(x) is equivalent to flip(x,1..n), n the length of x.
Float (187) The type of decimal numbers.
formula (179) See statement.
formula expression (179) See statement.
Forney’s formula (159) Expression for the error values in terms of the error-locator
and error-evaluator polynomials (Proposition 4.8).
Frobenius automorphism (93) 1 If L is a finite field of characteristic p, the map
L → L such that x 7→ xp (absolute Frobenius automorphism of L). 2 If K is a
subfield of L with |K| = q, the map L → L such that x 7→ xq is an automorphism
of L over K (Frobenius automorphism of L over K).
frobenius(x) (93) If x lies in a field of characteristic p, the value xp . The call frobe-
nius(K,x), where K is a finite field of q elements, yields xq .
full decoder (16) A decoder g : D → C such that D = T n (hence all length n
vectors are decodable).
Function (187) The type associated to functions, in the sense of A.15, page 186.
G
gcd(m,n) The greatest common divisor of two integers (or of two univariate polyno-
mials) m and n.
geometric_progression See (geometric_series).
geometric_series(x,n) (86) Given expression x and a non-negative integer f, returns
the vector [1, x, . . . , xn−1 ] (note that n is its length). The call geometric_series(a,x,n),
where a is an expression, is equivalent to a·geometric_series(x,n). Synonym: geo-
metric_progression.
gilbert(x) (78, 80) Computes the asymptotic Gilbert lower bound.
g -decodable See decoding function.
Galois field (29) See finite fields.
Gauss algorithm (109) A fast procedure for finding a primitive element of a finite
field (P.2.10).
206 Index-Glossary
H
Hadamard codes (61) If H is a Hadamard matrix of order n, the binary code CH ∼
(n, 2n, n/2) formed with the rows of H and −H after replacing −1 by 0 is the
Hadamard code associated to H. A Hadamard (32, 64, 16) code, which is equivalent
to the Reed–Muller code RM 2 (5), was used in the Mariner missions (1969-1972).
For the decoding of Hadamard codes, see Proposition 1.55 (page 62).
hadamard_code(H) (61) Returns the Hadamard code associated to the Hadamard
matrix H.
hadamard_code(n) (61) For positive integer n, this function returns the Hadamard
code associated to the Hadamard matrix H (n) .
hadamard_code(F) (61) For a finite field F of odd cardinal, we get the Hadamard
code associated to the Hadamard matrix of F.
Hadamard matrix (55, 60) A square matrix H whose entries are ±1 and such that
HH T = nIn , where n is the order of H.
hadamard_matrix(n) (56) The 2n × 2n Hadamard matrix H (n) .
hadamard_matrix(F) (60) The Hadamard matrix of a finite field F of odd cardinal.
Hadamard decoder (63) The decoder for Hadamard codes based on Proposition 1.55.
Index-Glossary 207
I
icon (179) Each of the choices in a palette menu of the WIRIS user interface, often
represented with an ideogram.
ideal (85) An additive subgroup I of a commutative ring A such that a · x ∈ I for all
a ∈ A and x ∈ I.
identifier (180) A letter, or a letter followed by characters that can be a letter, a digit,
an underscore or a question mark. Capital and lower case letters are distinct. Iden-
tifiers are also called variables.
identity_matrix(r) (185) The identity matrix of order r, Ir .
if b then S end (188) Evaluates statement S when the value of the Boolean expression
b is true, otherwise it does nothing.
if b then S else T end (188) Evaluates statement S when the value of the Boolean
expression b is true, otherwise evaluates statement T.
incomplete decoding (42) A correction-detection scheme for linear codes used when
asking for retransmission is possible. It corrects error-patterns of weight up to the
error-correcting capacity and dectects all error-patterns of higher weight which are
not code vectors.
index(a,x) (184) For a vector or list x, 0 if the object a does not belong to x, otherwise
the index of first occurrence of a in x.
index calculus See exponential representation.
index table See exponential representation.
208 Index-Glossary
ind_table(a) (107) Given an element a of a finite field, it returns the relation {aj →
j}06j6n−1 , n the order of a. In order to incluce 0, we also add the pair {0→_} (here
we use the underscore character, but often the symbol ∞ is used instead).
infimum(f,r) (80) For a function f and a range r, it returns the minimum of the values
f(t) when t runs over r. If f is continuous on a closed interval [a, b], we can approx-
imate the minimum of f in [a, b], as closely as wanted, by choosing r=a..b..ε with ε
small enough.
information source (11) The generator of messages in a communication system. A
(source) message is a stream of source symbols.
inner distribution (74) For a a code C ∼ (n, M )q , the set of numbers ai = Ai /M ,
i = 1, . . . , n, where Ai is the set of pairs (x, y) ∈ C × C such that hd (x, y) = i. In
the case of a linear code it coincides with the weight distribution.
input alphabet See channel alphabet.
Integer (187) The type associated to integers. Denoted Z in palette style.
inverse(x) 1 The inverse, x−1 or 1/x, of an invertible ring element x. 2 If R is a
relation, the relation formed with all pairs b→a such that a→b is a pair of R.
invert_entries(x) (149) Gives the vector whose components are the inverses of the
components of the vector x.
invertible?(x) (186) For a ring element x, it yields true when x is invertible in its ring,
and false otherwise.
is?(x,T) (187) Tests whether x has type T or not. Takes the form x∈T in palette style.
ISBN (30) Acronym for International Standard Book Number (see Example 1.19).
is_prime_power?(n) (30) For an integer n, decides whether it is a prime power or
not.
irreducible?(f,K) (186) For a field K and a polynomial f with coefficients in K, tests
whether f is irreducible over K or not.
irreducible_polynomial(K,r,T) (100) Given a finite field K, a positive integer r and a
variable T, returns a monic irreducible polynomial of degree r in the variable T and
with coefficients in K. Since it makes random choices, the result may vary from
call to call.
item(i,s) (182) The i-th term of a sequence s.
J
Jacobi logarithm See Zech logarithm.
Johnson’s upper bound (73, 73) An upper bound for binary codes which improves
Hamming’s upper bound (Theorem 1.72, and also Proposition 1.71).
join(x,y) (183) The concatenation of x and y (both vectors or both lists). It coincides
with x|y.
K
keyboard style (179) Conventions for representing the action of palette icons by
means of a keyboard character string. For example, the symbol Z for the ring of
integers that can be input from the Symbol palette has the same value as Integer.
Similarly, the fraction a composed by clicking the fraction icon in the Operations
b
menu has the same value as a/b.
key equation (160) For alternant codes defined by an alternant matrix of order r,
the error-evaluator polynomial (z) is, modulo z r , the product of the error-locator
Index-Glossary 209
As shown by Delsarte, these polynomials play a fundamental role in the linear pro-
gramming bound (cf. Propostion 1.74 and Theorem 1.75).
L
n
lb_gilbert(n,d,q) (26) The value of dq /vol (n, d − 1, q)e, which is the Gilbert lower
bound for Aq (n, d). The expression lb_gilbert(n,d) is defined to be lb_gilbert(n,d,2).
lb_gilbert_varshamov(n,d,q) (26) The value q k , where k is the highest positive in-
teger such that vol q (n − 1, d − 2) < q n−k (Gilbert–Varshamov condition). The
expression lb_gilbert_varshamov(n,d) is defined to be lb_gilbert_varshamov(n,d,2).
lcm(m,n) The least common multiple of two integers (or of two univariate polynomi-
als) m and n.
leaders’ table (39) A table E = {s → es }s∈Fn−k formed with a vector es ∈ Fn q
q
of syndrome s with respect to a check matrix H of a code [n, k]q and which has
minimum weight with that condition. The vector es is called a leader of the set of
vectors whose H-syndrome is s.
Legendre character (57, 58) Given a finite field F of odd cardinal q, the map
χ : F∗ → {±1}
such that χ(x) = 1 if x is a square (also called a quadratic residue) and χ(x) = −1
if x is not a square (also called a quadratic non-residue). Conventionally χ(0) is
defined to be 0.
left_parity_extension(G) See parity_extension(G).
legendre(a,F) (58) Yields the Legendre charater of the element a of a finite field F.
length (12) 1 The length of a vector, word, or list is the number of its elements. 2 The
length of a block encoder or of a block code is the length of any of its words.
length(x) (183) The length of x (an aggregate).
let (180) The sentence let x=e binds the value of e to x and assigns the name x to this
value.
linear codes (30) A code whose alphabet T is a Galois field and which is a linear
subspace of T n .
linear encoding (32) If G is a generating matrix of a linear code C over Fq , the
encoding Fkq → Fnq given by u 7→ uG.
linear programming bound (76) Aq (n, d) is bounded above by the maximum of the
linear function 1 + ad + · · · + an subject to the constraints ai > 0 (d 6 i 6 n) and
Xn
n
+ ai Kj (i) > 0 for j ∈ {0, 1, . . . , n},
j
i=d
list(x) (184) If x is a range or vector, the list whose components are the elements of x.
The expression {x} is, in both cases, a list of length 1 with x as its only element.
local X (187) A directive to insert at the beginning of a statement a sequence X of
local variables for that statement. These variables do not interfere with homonym
variables defined outside the statement. The variables introduced with the local
directive can be assigned values, as in local x, y=0 (x is left free, while y is assigned
the value 0).
LP(n,d) (76, 76) Computes the linear programming bound of Aq (n, d). The three-
argument call LP(n,d,X), with X a list of inequalities, finds a constrained maximum
like LP(n,d), but with the Delsarte constraints (see Theorem 1.75) enlarged with the
inequalities X.
M
macwilliams(n,k,q,A,T) (50) The polynomial q −k (1 + (q − 1)T )n A(T
e ), where A(T
e )
is the expression obtained after substituting the variable T in A by (1 − T )/(1 +
(q − 1)T ). The call macwilliams(n,k,A,T) is equivalent to macwilliams(n,k,2,A,T).
MacWilliams identities (50) These determine the weight enumerator of the dual of a
linear code C in terms of the weight enumerator of C (see Theorem 7).
main problem (22) See optimal code.
Mariner code (61) See also Hadamard codes.
Matrix (187) The type associated to matrices. If R is a ring, Matrix(R) is the type of
the matrices whose entries are in R.
Mattson–Solomon matrix (153) A matrix of the form M = (αij ), 0 6 i, j 6 n − 1,
where α is an element of a finite field with ord (α) = n. The map x 7→ xM is called
a Mattson–Solomon transform.
mattson_solomon_matrix(α) (153) Creates the Mattson–Solomon matrix on the ele-
ment α.
Mattson–Solomon transform (153) See Mattson–Solomon matrix.
maximum distance separable (21) Codes [n, k, d]q that satisfy equality (k + d =
n + 1) in the Singleton bound (k + d 6 n + 1).
mceliece(x) (79, 80) Computes the McEliece, Rodemich, Rumsey and Welsh asymp-
totic linear programming upper bound.
MDS Acronym for maximum distance separable.
Meggitt algorithm (144) A decoding algorithm for cyclic codes based on a Meggitt
table.
Meggitt decoder (144) A decoder for cyclic codes that implements the Meggitt algo-
rithm.
meggitt(y,g,n) (144) For a positive integer n and a polynomial y=y(x) of degree < n
representing the received vector, this function returns the result of decoding y with
the Meggitt decoder of the cyclic code defined by the monic divisor g of xn − 1. It
presupposes that a Meggitt table E is available.
Meggitt table (144) Given a cyclic code of length n over Fq , the table E = {s →
axn−1 + e}, where a is any nonzero element of Fq , e is any polynomial of degree
< n − 1 and weight < t, where t is the error correcting capacity of the code, and s
is the syndrome of axn−1 + e.
min(x) (184) For a range, list or vector x, the minimum among its terms.
Index-Glossary 211
min_weight(X) (41) Given a list of vectors X, the minimum among the weights of the
vectors in X.
min_weights(X) (41) The sublist of a list of vectors X whose weight is min_weight(X).
minimum distance (14) Given C ⊆ T n , where T is a finite set, the minimum distance
of C is
dC = min{hd (x, x0 ) | x, x0 ∈ C, x 6= x0 },
N
n_items(s) (181) The number of terms of the sequence s.
n_columns(A) (185) Abreviation of number_of_columns(A). Yields the number of
columns of the matrix A.
n_rows(A) (185) Abreviation of number_of_rows(A). Yields the number of rows of
the matrix A.
Nm(α,L,K) (115) For an element a and a subfield K of a finite field L, this function
returns NmL/K (α). The call Nm(α,L) is equivalent to Nm(α,L,K) is with K the prime
field of L. The call Tr(α) is equivalent to Tr(α,L) with L=field(α).
noiseless channel (12) A channel that does not alter the symbols sent through it.
noisy channel (12) A channel that is not noiseless (symbols sent through it may thus
be altered).
non-decodable (16) Given a decoder, said of a vector that is not in the domain of this
decoder.
norm (31, 114) 1 The weight is a norm on Fnq (E.1.20). 2 The norm of a finite
field L over a subfield K is the homomorphism NmL/K : L∗ → K ∗ such that
212 Index-Glossary
O
odd?(n) (186) This Boolean function tests whether the integer n is odd.
offset See BCH codes.
optimal code (21) For a given length n and minimum distance d, the highest M such
that there exists a code (n, M, d)q . This M is denoted Aq (n, d). The determination
of the function Aq (n, d) is often called the main problem of coding theory.
order (103) 1 The order of an element α of a finite group G is the least positive
integer r such that αr = e (e the identity element of G). If n = |G|, then r|n. 2 In
the case of the multiplicative group K ∗ of a finite field K, the order of α, denoted
ord (α), divides q − 1. Conversely, if r divides q − 1, then there are exactly ϕ(r)
elements of order r in K (Proposition 2.34). 3 If n > 1 is an integer, and a is
another integer such that gcd (a, n) = 1, the order of α = [a]n in the group Z∗n ,
denoted en (q) (or also ord n (a)), divides ϕ(n). 4 The order of an alternant control
matrix is the number of rows of this matrix.
order(a) (104) If a is a nonzero element of a finite field, it computes the order of a.
order(q,n) (128) The order of the integer q in the group of invertible elements modulo
the positive integer n, provided q and n are relatively prime.
output alphabet See channel alphabet.
P
pad(a,r,t) (119) From a vector a, say of length n, a positive integer r and an expression
t, it constructs a vector of length r as follows. If n > r, the result is equivalent to
take(a,r). Otherwise it is equivalent to a|constant_vector(n-r,t). The call pad(a,r) is
equivalent to pad(a,r,0).
pairing (182) A relation, a table, a substitution or a divisor.
palette (179) Each of the icon menus of the WIRIS user interface. In this release
(November 2002) the existing palettes are, in alphabetical order, the following:
Analysis, Combinatorics, Edit, Format, Geometry, Greek, Matrix, Operations, Pro-
gramming, Symbols and Units.
palette style (179) The characteristic typographical features and conventions of input
expressions composed with palette icon menus. Designed to be as close as possible
to accepted mathematical practices and conventions, it is also the style in which
output expressions are presented.
Paley codes (63) See E.1.46.
Index-Glossary 213
paley_code(F) (63) Constructs the Paley code (E.1.46) associated to a Finite field.
Paley matrix (58) The Paley matrix of a finite field F = {x1 , . . . , xq }, q odd, is
(χ(xi − xj )) ∈ Mq (F), 1 6 i, j 6 q, where χ is the Legendre character of F.
paley_matrix(F) (58) This function computes the Paley matrix of a finite field F of odd
cardinal.
parity-check matrix See check matrix.
parity completion (124, 32) 1 The result of appending to each vector of a binary code
the binary sum of its component bits. Thus the parity completion of an (n, M ) code
is an (n + 1, M ) code with the property that the binary sum of the component bits
of each of its elements is zero. 2 More generally, the result of adding to each vector
of a code defined over a finite field the negative of the sum of its components. Thus
the parity extension of an (n, M )q code is an (n + 1, M )q code with the property
that the sum of the components of each of its vectors is zero.
parity_completion(G) (124) The argument G is assumed to be a matrix r × n and the
function returns a matrix r × (n + 1) whose last column is the negative of the sums
of the rows of G. The function left_parity_extension(G) is defined in the same way,
but the extra column is inserted at the beginning of G.
parity extension Parity completion.
perfect codes (24) Codes that satisfy equality in the Hamming upper bound. For a
review of what is known about these codes, see Remark 1.16, page 25.
period [of a monic irreducible polynomial] See primitive polynomial.
period(f,q) (106) Assuming f is a monic irreducible polynomial with coefficients in
field of q elements, this function computes the period (or exponent) of f.
PGZ Acronym for Peterson–Gorenstein–Zierler.
PGZ algorithm (176) A decoding scheme for alternant codes based on a solving a
linear system of equations (cf. Proposition 4.17, page 175) for the determination of
the error-locator polynomial.
phi_euler(n) (87) Computes Euler’s function ϕ(n).
plotkin(x) (79) Computes the asymptotic Plotkin upper bound.
Plotkin bound (69) If (n, M, d)q are the parameters of a code, then we have the
inequality d 6 βnM/(M − 1), or M (d − βn) 6 d, where β = (q − 1)/q. The dual
Hamming codes meet the Plotkin bound (Example 1.65). For improvements of the
Plotkin bound, see E.1.50 and, for binary codes, E.1.49.
Plotkin construction (27) See P.1.5.
polar representation Exponential representation.
Polynomial (187) The type of (possibly multivariate) polynomials.
polynomial(a,X) (118) Given a vector a and an indeterminate X, returns a1 + a2 X +
· · · + an X n−1 (the polynomial in X with coefficients a).
prime?(n) (186) Test whether the integer n is prime or not.
prime ring / field See characteristic homomorphism.
primitive BCH codes see BCH codes.
primitive element (105) In a finite field Fq , any element of order q − 1. A primitive
element is also called a primitive root. In Fq there are exactly ϕ(q − 1) primitive
elements (Proposition 2.34).
primitive_element(K) (105) Returns a primitive element of the finite field K.
primitive polynomial (106) Any monic irreducible polynomial f ∈ K[X], where K
is a finite field, such that α = [X]f is a primitive element of the field K[X]/(f ).
214 Index-Glossary
Since the order of α coincides with the period (or exponent) of f (E.2.21), which by
definition is the least divisor d of q r − 1 such that f divides X d − 1 (r = deg (f )),
f is primitive if and only if f does not divide X d − 1 for any proper divisor d of
q r − 1.
primitive root See primitive element.
primitive RS codes See Reed–Solomon codes.
principal ideal (85) Given a ∈ A, A a ring, the set {xa | x ∈ A} is an ideal of A. It
is denoted (a)A , or just (a) if A can be understood, and is called the principal ideal
generated by a.
prune(H) (150) The result of dropping from the matrix H the rows that are linear
combination of the privious rows.
Q
q -ary See block code.
q -ary symmetric channel See symmetric channel.
QNR(F) (58) When F is a finite field of odd cardinal, it yields the list of quadratic
non-residues of F.
QR(F) (58) When F is a finite field of odd cardinal, it yields the list of quadratic
residues of F.
quadratic residue See Legendre character
quadratic non-residue See Legendre character
quotient(m,n) Given integers m and n (or univariate polynomials with coefficients in
a field), computes the quotient of the Euclidean division of m by n.
quotient_and_remainder(m,n) Given integers m and n (or univariate polynomials
with coefficients in a field), yields a list with the quotient and the remainder of the
Euclidean division of m by n.
R
Range (183, 187) The type associated to ranges.
range (182) A construct of the form a..b..d. It represents the sequence of real numbers
x in the interval [a, b] that have the form x = a + jd for some nonnegative integer
j. The construct a..b usually is interpreted as a..b..1, but it can be interpreted as
different sequence of values in the interval [a, b] when it is passed as an argument to
some functions.
range(x) (183) For a vector, list or pairing of length n, the range 1..n.
rank(A) Returns the rank of the matrix A.
rate (13) Short form of code rate.
Rational (187) The type associated to rational numbers. Denoted Q in palette style.
rd(K) (169) Picks an element at random from the finite field K. The call rd(s,K) picks
s elements at random from K.
rd_choice(X,m) (169) Given a set X of cardinal n and a positive integer m less than
n, makes a (pseudo)random choice of m elements of X. The call rd_choice(n,m),
where now n is an integer, chooses m elements at random of the set {1, . . . , n}.
rd_error_vector(n,s,K) (169) Produces a random vector of weight s in Kn .
rd_linear_combination(G,K) (169) Generates a random linear combination of the
rows of the matrix G with coefficients from the finite field K.
Index-Glossary 215
rd_nonzero(K) (169) Picks a nonzero element at random from the finite field K. The
call rd_nonzero(s,K) picks s nonzero elements at random from K.
Real (187) The type associated to real numbers. Denoted R in palette style.
Reed–Muller codes (54) The first order Reed–Muller codes are introduced in P.1.16.
They are denoted RM x q (m). This code is the result of evaluating the polynomials
of degree 6 1 in m variables X1 , . . . , Xm at n points x = x1 , . . . , xn ∈ Fm q
(q m−1 < n 6 q m ). The Reed–Muller codes of order s, which are not studied in
this book, are defined in a similar way, but using polynomials of degree 6 s in
X1 , . . . , Xm (see, for example, [29]).
Reed–Solomon codes (33) Introduced in Example 1.24, they are denoted RS α (k).
This code is the result of evaluating the polynomials of degree < k in one variable
X over Fq on n distinct elements α = α1 , . . . , αn of Fq . This code has type
[n, k, n − k + 1]q , and hence is MDS. If n = q − 1 and α1 , . . . , αn are the nonzero
elements of Fq , RS α (k) is said to be a primitive RS code. Primitive RS codes are
BCH codes (Proposition 3.22).
Relation (187) The type associated to relations.
relation (182) A WIRIS relation is a sequence of objects of the form a→b enclosed
in braces, where a and b are arbitrary objects. Relations can be thought as a kind of
functions. Indeed, if R is a relation and x any object, R(x) returns the sequence of
values y (which may be null) such that x→y appears in the definition of R.
relative distance (14) For a block code C of length n and minimum distance d, the
quotient δC = d/n.
remainder(m,n) Given integers m and n (or univariate polynomials with coefficients
in a field), computes the remainder of the Euclidean division of m by n.
Rep(3) (2) The binary repetition code of length 3, or Rep2 (3).
repetition code (21) The code Repq (n), of type [n, 1, n]q , that consists of the q con-
stant vectors tn , t ∈ T .
residue code (66) The residue of a linear code C ⊆ Fn q with respect to a z ∈ C is the
image of C under the linear map ρz : Fnq → Fn−s q which extracts, for each y ∈ Fnq ,
the n − s components whose index lies outside the support of z (hence s denotes
the length of this support).
reverse(x) (184) This yields, for a list or vector x, the list or vector with the objects
of x written from the end to the beginning. The call reverse(a..b..d) gives the range
b..a..-d.
reverse_print(b) (118) By default, polynomials are displayed by decreasing degree
of its terms. This order can be reversed with reverse_print(true). The command
reverse_print(false) restitutes the default order.
Ring (187) The type associated to rings.
ring (84) An abelian group (A, +) endowed with a product A×A → A, (x, y) 7→ x·y,
that is associative, distributive with respect to the sum on both sides, and with a unit
element 1A which we always assume to be different from the zero element 0A of the
group (A, +). If x · y = y · x for all x, y ∈ A we say that the ring is commutative.
ring(x) Returns the ring where the element x belongs.
ring homomorphism (85) A map f : A → A0 from a ring A to a ring A0 such that
f (x + y) = f (x) + f (y) and f (x · y) = f (x) · f (y), for all x, y ∈ A, and
f (1A ) = 1A0 .
RM Acronym for Reed–Muller codes.
216 Index-Glossary
roots (134) For a cyclic code C of length n over Fq , the roots of the generator poly-
nomial of C in the splitting field of X n − 1 over Fq .
roots(f,K) (114) For a univariate polynomial f and field K, it returns the list of roots of
f in K.
RS Acronym for Reed–Solomon codes.
RS(a,k) (151) Creates the Reed–Solomon code of dimension k associated to the vector
a.
Ruffini’s rule (90) A polynomial f ∈ K[X], K a field, is divisible by X − α if and
only if f (α) = 0. It follows that f has a factor h ∈ K[X] of degree 1 if and only if
f has a root in K.
Rule The type of rules. See Substitution.
S
say(t) This command displays a text t at the message window at the bottom of the
WIRIS screen. The text string correspending to an expression e can be obtained
with string(e). It may be useful to note that if t is a string and e an expression, then
t|e is equivalent to t|string(e).
scalarly equivalent codes (15) See equivalent codes.
sequence(x) (181) If x is a range, list or vector, the sequence formed with the com-
ponents of x.
set(L) (184) From a list L, it forms an ordered list with the distinct values of the terms
of L (repetitions are discarded).
Shannon (4) Claude Elwood Shannon (1916-2001) is considered the father of the
Information Age. One of his fundamental results is the celebrated channel coding
theorem. “Look at a compact disc under a microscope and you will see music repre-
sented as a sequence of bits, or in mathematical terms, as a sequence of 0’s and 1’s,
commonly referred to as bits. The foundation of our Information Age is this trans-
formation of speech, audio, images and video into digital content, and the man who
started the digital revolution was Claude Shannon” (from the obituary by Robert
Calderbank and Neil J. A. Sloane).
shortening (71) If T is a q-ary alphabet and λ ∈ T , the code {x ∈ T n−1 | (x|λ) ∈ C}
is said to be the λ-shortening of the code C ⊆ T n with respect to the last position.
Shortenings with respect to other positions are defined likewise.
shorthand(X,E) (170) Represents the entries of the vector or matrix X by the corre-
sponding indices on table E (Zech logarithms). The element 0 is represented by the
underscore character.
Singleton bound (21) A code [n, k, d]q satisfies k + d 6 n + 1 (Proposition 1.11,
page 21).
source alphabet (11) The finite set S, whose elements are called source symbols,
used to compose source messages. A source message is a stream s1 , s2 , . . . with
si ∈ S (cf. information source).
source symbol See symbol.
sphere-packing upper bound The Hamming’s upper bound.
sphere upper bound The Hamming’s upper bound.
splitting field (97) If K is a field and f ∈ K[X] a polynomial of degree r, there exists
Qr
a field L that contains K and elements α1 , . . . , αr ∈ L such that f = i=1 (X −αi )
and L = K(α1 , . . . , αr ). This field L is the splitting field of f over K. It can be
Index-Glossary 217
T
Table (187) The type of tables.
table (182) A WIRIS table is a sequence of objects of the form x=a enclosed in
brakets (braces are also allowed), where x is an identifier and a is any object. Tables
can be thought as a kind of functions. Indeed, if x is any identifier, T(x) returns the
sequence of values a such that x=a is on T.
tail(x) (183) Equivalent to x,n-1 if x is a list, vector or range of length n.
take(x,k) (183) If x is a list or vector of length n, and k is in the range 1..n, the list or
vector formed with the first k terms of x. If instead of k we write -k, we get the list
or vector of the last k terms of x. This function also makes sense when x is a range,
and in this case it yields the list of the first k terms of x (or the last k for the call
take(x,-k)).
tensor(A,B) (56) Returns the tensor product of the matrices A and B.
Tr(α,L,K) (115) For an element a and a subfield K of a finite field L, this function
returns Tr L/K (α). The call Tr(α,L) is equivalent to Tr(α,L,K) with K the prime field
of L. The call Tr(α) is equivalent to Tr(α,L) with L=field(α).
trace (114) The trace of a finite field L over a subfield K is the K-linear map
Tr L/K : L → K such that Tr L/K (α) = Tr (mα ), where mα : L → L is the multi-
plication by α (the K-linear map x 7→ αx). For an expression of Tr L/K (α) in terms
of the conjugates of α, see Theorem 2.43.
trace(A) (185) Assuming A is a square matrix, the trace of A (the sum of its diagonal
entries).
transmission alphabet See channel alphabet.
transmission rate See code rate.
transpose(A) (185) The matrix obtained by writing the rows of A as columns. De-
noted AT .
trivial perfect codes (24) The total q-ary codes T n , the one-word codes and the odd-
length binary repetion codes.
true (185) Together with false, they form the set of Boolean values.
ub_elias(n,d,q) (72) Gives the Elias upper bound for Aq (n, d).
ub_griesmer(n,d,q) (67, 68) The Griesmer upper bound for the function Bq (n, d).
This bound has the form q k , where kis the
highest non-negative integer such that
Pk−1 d
Gq (k, d) 6 n and Gq (k, d) = i=0 (the Griesmer function).
qi
ub_johnson(n,d) (73) Gives the Johnson upper bound for A2 (n, d). There is also the
call ub_johnson(n,d,w), which computes the upper bound introduced in Proposition
1.71 for the function A(n, d, w). This function is, by definition, the maximum M
for binary codes (n, M, d) all whose words have weight w.
ub_sphere(n,d,q) (24) The value of bq n /vol (n, t, q)c, t = b(d − 1)/2c, which is the
sphere-packing upper bound for Aq (n, d). The expression ub_sphere(n,d) is defined
to be ub_sphere(n,d,2).
Index-Glossary 219
V
Vandermonde determinant (35) The determinant, denoted D(α1 , . . . , αn ), of a square
Vandermonde matrix Vn (α1 , . . . , αn ).
Vandermonde matrix (33) The Vandermonde matrix of r rows on the elements α =
α1 , . . . , αn is (αji ), with 0 6 i 6 r − 1 and 1 6 j 6 n. It is denoted Vr (α).
vandermonde_matrix(a,r) (148) Creates the Vandermonde matrix of order r associ-
ated to the vector a.
vanlint(x) (79, 80) Computes the asymptotic van Lint upper bound.
variable Identifier.
variable(f) Retrieves the variable of a univariate polynomial.
variables(f) Retrieves the list of variables of a polynomial.
Vector (187) The type of vectors. If R is a ring, the type of the vectors with compo-
nents in R is Vector(R).
vector See code word.
vector(x) (184) If x is a range or list, the vector whose components are the elements
of x. In the case in which x is a range, vector(x) is the same as [x]. When x is a list,
however, [x] is a vector of length 1 with x as its only component.
vector(p) (118) If p is a univariate polynomial a1 + a2 X + · · · + an X n−1 , the vector
[a1 , . . . , an ]. Pr n
i
volume(n,r,q) (23) The value of i=0 i (q − 1) (for a q-ary alphabet, this is the
number of length n vectors that lie at a Hamming distance at most r of any given
length n vector. The value of volume(n,r) coincides with volume(n,r,2).
W
weight (14, 31) Given a vector x, the number of nonzero components of x. It is
denoted |x| or wt (x).
weight(x) (184) Yields the weight of the vector x. Synomym expression: wt(x).
weight distribution See weight enumerator.
weight enumerator (46) Given a linear code C of length n, the polynomial a(t) =
Pn
i=0 ai ti , where ai is the number of vectors in C which have weight i. The se-
quence a0 , a1 , . . . , an is called the weight distribution of the code.
where Synonym of such_that.
WIRIS/cc (ii, 6) The general mathematical system used to carry out the computations
sollicited by the examples in this book. It includes the interface that takes care of
the editing (mathematics and text). It is introduced gradually along the text. For a
summary, see the Appendix. The examples in this book can be accessed and run at
[Link]
with (188) A directive to make a variable or variables run over an aggregate or list of
aggregates. For more details see A.17.
word See code word.
wt(x) Synonym of weight, yields the weight of the vector x.
Z
220 Index-Glossary