Math 422 Coding Theory & Cryptography: John C. Bowman University of Alberta

Math 422
Coding Theory & Cryptography
John C. Bowman
University of Alberta
Edmonton, Canada
October 15, 2015

c 2002–5
John C. Bowman
ALL RIGHTS RESERVED
Reproduction of these lecture notes in any form, in whole or in part, is permitted only for
nonprofit, educational use.
Contents
Preface 5
1 Introduction 6
1.A Error Detection and Correction . . . . . . . . . . . . . . . . . . . . . 7
1.B Balanced Block Designs . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.C The ISBN Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Linear Codes 23
2.A Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.B Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Hamming Codes 39
4 Golay Codes 44
5 Finite Fields 48
6 Cyclic Codes 57
7 BCH Codes 66
8 Cryptographic Codes 78
8.A Symmetric-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . 78
8.B Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . 81
8.B.1 RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . 81
8.B.2 Rabin Public-Key Cryptosystem . . . . . . . . . . . . . . . . . 86
8.C Discrete Logarithm Schemes . . . . . . . . . . . . . . . . . . . . . . . 86
8.C.1 Diffie–Hellman Key Exchange . . . . . . . . . . . . . . . . . . 86
8.C.2 Okamoto Authentication Scheme . . . . . . . . . . . . . . . . 87
8.C.3 Digital Signature Standard . . . . . . . . . . . . . . . . . . . . 89
8.C.4 Silver–Pohlig–Hellman Discrete Logarithm Algorithm . . . . . 90
8.D Cryptographic Error-Correcting Codes . . . . . . . . . . . . . . . . . 90
Bibliography 91
3
4 CONTENTS
Index 92
Preface
These lecture notes are designed for a one-semester course on error-correcting codes
and cryptography at the University of Alberta. I would like to thank my col-
leagues, Professors Hans Brungs, Gerald Cliff, and Ted Lewis, for their written
notes and examples, on which these notes are partially based (in addition to the
references listed in the bibliography) and also Professor Jochen Kuttler, for pointing
out several errors in an earlier version of these notes. The figures in this text were
drawn with the high-level vector graphics language Asymptote (freely available at
http://asymptote.sourceforge.net).
5
Chapter 1
Introduction
In the modern era, digital information has become a valuable commodity. For exam-
ple, the news media, governments, corporations, and universities all exchange enor-
mous quantities of digitized information every day. However, the transmission lines
that we use for sending and receiving data and the magnetic media (and even semi-
conductor memory devices) that we use to store data are imperfect.
Since transmission line and storage devices are not 100% reliable device, it has
become necessary to develop ways of detecting when an error has occurred and,
ideally, correcting it. The theory of error-correcting codes originated with Claude
Shannon’s famous 1948 paper “A Mathematical Theory of Communication” and has
grown to connect to many areas of mathematics, including algebra and combinatorics.
The cleverness of the error-correcting schemes that have been developed since 1948 is
responsible for the great reliability that we now enjoy in our modern communications
networks, computer systems, and even compact disk players.
Suppose you want to send the message “Yes” (denoted by 1) or “No” (denoted
by 0) through a noisy communication channel. We assume that there is a uniform
probability p < 1 that any particular binary digit (often called a bit) could be altered,
independent of whether or not any other bits are transmitted correctly. This kind
of transmission line is called a binary symmetric channel. (In a q-ary symmetric
channel, the digits can take on any of q different values and the errors in each digit
occur independently and manifest themselves as the q − 1 other possible values with
equal probability.)
If a single bit is sent, a binary channel will be reliable only a fraction 1 − p of the
time. The simplest way of increasing the reliability of such transmissions is to send
the message twice. This relies on the fact that if p is small, the probability p2 of two
errors occurring is very small. The probability of no errors occurring is (1 − p)2 . The
probability of one error occurring is 2p(1 − p) since there are two possible ways this
could happen. While reception of the original message
√ is more likely than any other
particular result if p < 1/2, we need p < 1 − 1/ 2 ≈ 0.29 to be sure that the correct
message is received most of the time.
6
1.A. ERROR DETECTION AND CORRECTION 7
If the message 11 or 00 is received, either 0 or 2 errors have occurred. Thus, we

would expect with conditional probability
(1 − p)2
(1 − p)2 + p2
that the sent message was “Yes” or “No”, respectively. If the message 01 or 10 is
received we know for sure that an error has occurred, but we have no way of knowing,
or even reliably guessing, what message was sent (it could with equal probability have
been the message 00 or 11). Of course, we could simply ask the sender to retransmit
the message; however this would now require a total of 4 bits of information to be sent.
If errors tend to occur frequently, it would make more sense to send three, instead of
two, copies of the original data in a single message. That is, we should send “111”
for “Yes” or “000” for “No”. Then, if only one bit-flip occurs, we can always guess,
with good reliability what the original message was. For example, suppose “111” is
sent. Then of the eight possible received results, the patterns “111”, “011”, “101”,
and “110” would be correctly decoded as “Yes”. The probability of the first pattern
occurring is (1 − p)3 and the probability for each of the next three possibilities is
p(1 − p)2 . Hence the probability that the message is correctly decoded is
(1 − p)3 + 3p(1 − p)2 = (1 − p)2 (1 + 2p) = 1 − 3p2 + 2p3 .
In other words, if p is small, the probability of a decoding error, 3p2 −2p3 , is very small.
This kind of data encoding is known as a repetition code. For example, suppose that
p = 0.001, so that on average one bit in every thousand is garbled. Triple-repetition
decoding ensures that only about one bit in every 330 000 is garbled.
1.A Error Detection and Correction

Despite the inherent simplicity of repetition coding, sending the entire message like
this in triplicate is not an efficient means of error correction. Our goal is to find
optimal encoding and decoding schemes for reliable error correction of data sent
through noisy transmission channels.
The sequences “000” and “111” in the previous example are known as binary
codewords. Together they comprise a binary code. More generally, we introduce the
following definitions.
Definition: Let q ∈ N. A q-ary codeword is a finite sequence of symbols, where each
symbol is chosen from the alphabet (set) Fq = {λ1 , λ2 , . . . , λq }. Typically, we will
. .
take Fq to be the set Zq = {0, 1, 2, . . . , q − 1}. (We use the symbol = to emphasize
a definition, although the notation := is more common.) The codeword itself can
be treated as a vector in the space Fqn = Fq × Fq × . . . Fq .
| {z }
n times
8 CHAPTER 1. INTRODUCTION
• A binary codeword, corresponding to the case q = 2, is just a finite sequence of 0s

and 1s.
• A ternary codeword, corresponding to the case q = 3, is just a finite sequence of

0s, 1s, and 2s.
Definition: A q-ary code is a set of M codewords, where M ∈ N is known as the size

of the code.
• The set of all words in the English language is a code over the 26-letter alphabet
{A, B, . . . , Z}.
One important aspect of all error-correcting schemes is that the extra information
that accomplishes this must itself be transmitted and is hence subject to the same
kinds of errors as is the data. So there is no way to guarantee accuracy; one simply
attempts to make the probability of accurate decoding as high as possible.
A good code is one in which the codewords have little resemblance to each other.
If the codewords are sufficiently different, we will soon see that it is possible not only
to detect errors but even to correct them, using nearest-neighbour decoding, where
one maps the received vector back to the closest nearby codeword.
• The set of all 10-digit telephone numbers in the United Kingdom is a 10-ary code of
length 10. It is possible to use a code of over 82 million 10-digit telephone numbers
(enough to meet the needs of the U.K.) such that if just one digit of any phone
number is misdialed, the correct connection can still be made. Unfortunately, little
thought was given to this, and as a result, frequently misdialed numbers do occur
in the U.K. (as well as in North America)!
Definition: We define the Hamming distance d(x, y) between two codewords x and y
of Fqn as the number of places in which they differ.
Remark: Notice that d(x, y) is a metric on Fqn since it is always non-negative and
satisfies
1. d(x, y) = 0 ⇐⇒ x = y,
2. d(x, y) = d(y, x) for all x, y ∈ Fqn ,
3. d(x, y) ≤ d(x, z) + d(z, y) for all x, y, z ∈ Fqn .
The first two properties are immediate consequences of the definition, while the third
property, known as the triangle inequality, follows from the simple observation that
d(x, y) is the minimum number of digit changes required to change x to y, whereas if
we were to change x to y by first changing x to z and then changing z to y, we would
require d(x, z) + d(z, y) changes. Thus d(x, y) ≤ d(x, z) + d(z, y). This important
inequality is illustrated in Fig 1.1.
Figure 1.1: Triangle inequality.
Remark: We can use property 2 to rewrite the triangle inequality as
d(x, y) − d(y, z) ≤ d(x, z) ∀x, y, z ∈ Fqn .
Definition: The weight w(x) of a q-ary codeword x is the number of nonzero digits
in x.
Remark: Let x and y be binary codewords in Zn2 . Then d(x, y) = w(x − y) =

w(x) + w(y) − 2w(xy). Here, x − y and xy are computed mod 2, digit by digit.
Remark: Let x and y be codewords in Znq . Then d(x, y) = w(x − y). Here, x − y is
computed mod q, digit by digit.
Definition: Let C be a code in Fqn . We define the minimum distance d(C) of the
code:
d(C) = min{d(x, y) : x, y ∈ C, x 6= y}.
Remark: In view of the previous discussion, a good code is one with a relatively
large minimum distance.
Definition: An (n, M, d) code is a code of length n, containing M codewords and

having minimum distance d.
• For example, here is a (5, 4, 3) code, consisting of four codewords from Z52 , which
are at least a distance 3 from each other:
 
0 0 0 0 0
0 1 1 0 1
C3 =  1 0 1 1 0 .

1 1 0 1 1
Upon considering each of the 42 = 4×3

2
= 6 pairs of distinct codewords (rows), we
see that the minimum distance of C3 is indeed 3. With this code, we can either
(i) detect up to two errors (since the members of each pair of distinct codewords
are more than a distance 2 apart), or (ii) detect and correct a single error (since,
if only a single error has occurred, the received vector will still be closer to the
transmitted codeword than to any other).
The following theorem (cf. Fig. 1.2) shows how this works in general.
Theorem 1.1 (Error Detection and Correction): In a symmetric channel with error-
probability p > 0,
(i) a code C can detect up to t errors in every codeword ⇐⇒ d(C) ≥ t + 1;
(ii) a code C can correct up to t errors in any codeword ⇐⇒ d(C) ≥ 2t + 1.
Figure 1.2: Detection of up to t errors in a transmitted codeword x requires that all

other codewords y lie outside a sphere S of radius t centered on x. Correction of up
to t errors requires that no sphere of radius t centered about any other codeword y
overlaps with S.
Proof:
(i) “⇐” Suppose d(C) ≥ t + 1. Let a codeword x be transmitted such that t or
fewer errors are introduced, resulting in a new vector y ∈ Fqn . Then d(x, y) =
w(x−y) ≤ t < t+1 ≤ d(C), so the received vector cannot be another codeword.
Hence t errors can be detected.
“⇒” Suppose C can detect up to t errors. If d(C) < t + 1, then there is some
pair of codewords x and y with d(x, y) ≤ t. Since it is possible to send the
codeword x and receive another codeword y by the introduction of t errors,
we conclude that C cannot detect t errors, contradicting our premise. Hence
d(C) ≥ t + 1.
(ii) “⇐” Suppose d(C) ≥ 2t + 1. Let a codeword x be transmitted such that t
or fewer errors are introduced, resulting in a new vector y ∈ Fqn satisfying
d(x, y) ≤ t. If x0 is a codeword other than x, then d(x, x0 ) ≥ 2t + 1 and the
triangle inequality d(x, x0 ) ≤ d(x, y) + d(y, x0 ) implies that
d(y, x0 ) ≥ d(x, x0 ) − d(x, y) ≥ 2t + 1 − t = t + 1 > t ≥ d(y, x).
Hence the received vector y is closer to x than to any other codeword x0 , making
it possible to identify the original transmitted codeword x correctly.
“⇒” Suppose C can correct up to t errors. If d(C) < 2t + 1, there is some
pair of distinct codewords x and x0 with distance d(x, x0 ) ≤ 2t. If d(x, x0 ) ≤ t,
let y = x0 , so that 0 = d(y, x0 ) < d(y, x) ≤ t. Otherwise, if t < d(x, x0 ) ≤ 2t,
construct a vector y by changing t of the digits of x that are in disagreement
with x0 to their corresponding values in x0 , so that 0 < d(y, x0 ) ≤ d(y, x) = t.
In either case, it is possible to send the codeword x and receive the vector y
due to t or fewer transmission errors. But since d(y, x0 ) ≤ d(y, x), the received
vector y cannot not be unambiguously decoded as x using nearest-neighbour
decoding. This contradicts our premise. Hence d(C) ≥ 2t + 1.
Corollary 1.1.1: If a code C has minimum distance d, then C can be used either (i)
to detect up to d − 1 errors or (ii) to correct up to b d−1
2
c errors in any codeword.
Here bxc represents the greatest integer less than or equal to x.
A good (n, M, d) code has small n (for rapid message transmission), large M (to
maximize the amount of information transmitted), and large d (to be able to correct
many errors. A primary goal of coding theory is to find codes that optimize M for
fixed values of n and d.
Definition: Let Aq (n, d) be the largest value of M such that there exists a q-ary
(n, M, d) code.
• Since we have already constructed a (5, 4, 3) code, we know that A2 (5, 3) ≥ 4. We

will soon see that 4 is in fact the maximum possible value of M ; i.e. A2 (5, 3) = 4.
To help us tabulate Aq (n, d), let us first consider the following special cases:
Theorem 1.2 (Special Cases): For any values of q and n,
(i) Aq (n, 1) = q n ;
(ii) Aq (n, n) = q.
Proof:
(i) When the minimum distance d = 1, we require only that the codewords be
distinct. The largest code with this property is the whole of Fqn , which has
M = q n codewords.
(ii) When the minimum distance d = n, we require that any two distinct codewords
differ in all n positions. In particular, this means that the symbols appearing in
the first position must be distinct, so there can be no more than q codewords.
A q-ary repetition code of length n is an example of an (n, q, n) code, so the
bound Aq (n, n) = q can actually be realized.
Remark: There must be at least two codewords for d(C) even to be defined. This
means that Aq (n, d) is not defined if d > n, since d(x, y) = w(x−y) ≤ n for distinct
codewords x, y ∈ Fqn .
Lemma 1.1 (Reduction Lemma): If a q-ary (n, M, d) code exists, with d ≥ 2, there
also exists an (n − 1, M, d − 1) code.
Proof: Given an (n, M, d) code, let x and y be codewords such that d(x, y) = d
and choose any column where x and y differ. Delete this column from all codewords.
Since d ≥ 2, the codewords that result are distinct and form a (n − 1, M, d − 1) code.
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 12 2
11 144 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
Table 1.1: Maximum code size A2 (n, d) for n ≤ 16 and d ≤ 7.
Theorem 1.3 (Even Values of d): Suppose d is even. Then a binary (n, M, d) code
exists ⇐⇒ a binary (n − 1, M, d − 1) code exists.
Proof:
“⇒” This follows from Lemma 1.1.
“⇐” Suppose C is a binary (n − 1, M, d − 1) code. Let Ĉ be the code of
length n obtained by extending each codeword x of C by adding a parity
bit w(x) mod 2. This makes the weight w(x̂) of every codeword x̂ of Ĉ
even. Then d(x, y) = w(x) + w(y) − 2w(xy) must be even for every pair
of codewords x and y in Ĉ, so d(Ĉ) is even. Note that d − 1 = d(C) ≤
d(Ĉ) ≤ d. But d − 1 is odd, so in fact d(Ĉ) = d. Thus Ĉ is a (n, M, d)
code.
Corollary 1.3.1 (Maximum Code Size for Even d): If d is even, then A2 (n, d) =
A2 (n − 1, d − 1).
This result means that we only need to calculate A2 (n, d) for odd d. In fact, in
view of Theorem 1.1, there is little advantage in considering codes with even d if the
goal is error correction. In Table 1.1, we present values of A2 (n, d) for n ≤ 16 and for
odd values of d ≤ 7.
As an example, we now compute the value A2 (5, 3) entered in Table 1.1, after
establishing a useful simplification, beginning with the following definition.
Definition: Two q-ary codes are equivalent if one can be obtained from the other by
a combination of
(A) permutation of the columns of the code;

(B) relabelling the symbols appearing in a fixed column.
Remark: Note that the distances between codewords are unchanged by each of these
operations. That is, equivalent codes have the same (n, M, d) parameters and can
correct the same number of errors. Furthermore, in a q-ary symmetric channel, the
error-correction performance of equivalent codes will be identical.
• The binary code  

0 1 0 1 0
1 1 1 1 1
 
0 0 1 0 0
1 0 0 0 1
is seen to be equivalent to our previous (5, 4, 3) code C3 by interchanging the first
two columns and then relabelling 0 ↔ 1 in the first and fourth columns of the
resulting matrix.
Lemma 1.2 (Zero Vector): Any code over an alphabet containing the symbol 0 is
equivalent to a code containing the zero vector 0.
Proof: Given a code of length n, choose any codeword x1 x2 . . . xn . For each i such
that xi 6= 0, apply the relabelling 0 ↔ xi to the symbols in the ith column.
• Armed with the above lemma and the concept of equivalence, it is now easy to
prove that A2 (5, 3) = 4. Let C be a (5, M, 3) code with M ≥ 4. Without loss
of generality, we may assume that C contains the zero vector (if necessary, by
replacing C with an equivalent code). Then there can be no codewords with just
one or two 1s since d = 3. Also, there can be at most one codeword with four or
more 1s; otherwise there would be two codewords with at least three 1s in common
positions and less than a distance 3 apart. Since M ≥ 4, there must be at least
two codewords containing exactly three 1s. By rearranging columns, if necessary,
we see that the code contains the codewords
 
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1
There is no way to add any more codewords containing exactly three 1s and we
can also now rule out the possibility of five 1s. This means that there can be at
most four codewords, that is, A2 (5, 3) ≤ 4. Since we have previously shown that
A2 (5, 3) ≥ 4, we deduce that A2 (5, 3) = 4.
Remark: A fourth codeword, if present in the above code, must have exactly four 1s.
The only possible position for the 0 symbol is in the middle position, so the fourth
codeword must be 11011. We then see that the resulting code is equivalent to C3
and hence A2 (5, 3) is unique, up to equivalence.
The above trial-and-error approach becomes impractical for large codes. In some
of these cases, an important bound, known as the sphere-packing or Hamming bound,
can be used to establish that a code is as large as possible for given values of n and d.
Lemma 1.3 (Counting): A sphere of radius t in Fqn , with 0 ≤ t ≤ n, contains exactly
t
X n
(q − 1)k
k=0
k
vectors.
Proof: The number of vectors that are a distance k from a fixed vector in Fqn is
n
(q − 1)k , because there are nk choices for the k positions that differ from those of

k
the fixed vector and there are q − 1 values that can be assigned independently to each
of these k positions. Summing over the possible values of k, we obtain the desired
result.
Theorem 1.4 (Sphere-Packing Bound): A q-ary (n, M, 2t + 1) code satisfies

t
X n
M (q − 1)k ≤ q n . (1.1 )
k =0
k
Proof: By the triangle inequality, any two spheres of radius t that are centered on
distinct codewords will have no vectors in common. The total number of vectors in
the M spheres of radius t centered on the M codewords is thus given by the left-hand
side of the above inequality; this number can be no more than the total number q n
of vectors in Fqn .
• For our binary (5, 4, 3) code, Eq. (1.1) gives the bound M (1 + 5) ≤ 25 = 32,
which implies that A2 (5, 3) ≤ 5. We have already seen that A2 (5, 3) = 4. This
emphasizes, that just because some set of numbers {n, M, t} satisfy Eq. (1.1), there
is no guarantee that such a code actually exists.
Definition: A perfect code is a code for which equality occurs in 1.1. For such a
code, the M spheres of radius t centered on the codewords fill the whole space Fqn
completely, without overlapping.
Remark: The codes that consist of a single codeword (taking t = n and M = 1),
codes that contain all vectors of Fqn (with t = 0 and M = q n ), and the binary
repetition code (with t = (n − 1)/2 and M = 2) of odd length n are trivially perfect
codes.
Problem 1.1: Prove that n

X n
(q − 1)t = q n .
t=0
t
Each term in this sum is the number of vectors of weight t in Fqn . When we sum over
all possible values of t, we obtain q n , the total number of vectors in Fqn .
Alternatively, we see directly from the Binomial Theorem that
n
X n
(q − 1)t = (1 + (q − 1))n = q n .
t
t=0
Problem 1.2: Show that a q-ary (n, M, d) code must satisfy M ≤ q n−d+1 . Hint: what
can can you say about the vectors obtained by deleting the last d − 1 positions of
all codewords? It might help to first consider the special cases d = 1 and d = 2.
If you delete the last d − 1 positions of all codewords, the resulting vectors must be
distinct, or else the codewords could not be a distance d apart from each other. Since the
number of distinct q-ary vectors of length n − d + 1 is q n−d+1 , the number of codewords M
must be less or equal to this number.
Problem 1.3: (a) Given an (n, M, d) q-ary code C, let Ni : i = 0, 1, . . . , q − 1 be the

number of codewords ending with the symbol i. Prove that there exists some i for
which Ni ≥ M/q.
This follows from the pigeon-hole principle: construct q boxes, one for each possible final
digit. If we try to stuff the M codewords into the q boxes, at least one box must contain
dM/qe or more codewords.
One can also establish this result directly, with a proof by contradiction. Suppose
that Ni < M/q for each i = 0, 1, . . . , q − 1. One would then obtain the contradiction
M = q−1
P Pq−1
i=0 Ni < i=0 M/q ≤ M .
(b) Let C 0 be the code obtained by deleting the final symbol from each codeword
in C. Show that C 0 contains an (n − 1, dM/qe) subcode having minimum distance d
or greater (that is, C 0 contains at least dM/qe codewords that are still a distance d
or more apart).
From part (a), we know that C contains at least dM/qe codewords ending in the same
symbol. These codewords form a subcode of C having minimum distance at least d. When
we delete the last symbol from the codewords in this subcode, their minimum distance does
not change: they form a (n − 1, dM/qe) subcode of C 0 having minimum distance at least d.
(c) Conclude that

Aq (n, d) ≤ qAq (n − 1, d).
Recall that Aq (n, d) is the largest value of M such that there exists a q-ary (n, M, d)
code.
Let C be an (n, Aq (n, d), d) code. We know from part(b) that we can construct an
(n − 1, dAq (n, d)/qe) subcode from C with minimum distance d0 ≥ d. Let x and y be two
codewords in the subcode with d(x, y) = d0 . Replace d0 − d positions of x and y where they
disagree with zeros, thereby forming an (n − 1, dAq (n, d)/qe, d) subcode. This shows that
Aq (n, d)
Aq (n − 1, d) ≥ .
q
Problem 1.4: Let C be a code with even distance d = 2m. Let t be the maximum
number of errors that C can be guaranteed to correct.
(a) Express t in terms of m.

d−1
To correct t errors we need d ≥ 2t + 1; that is, t ≤ 2 . The maximum value of t is

d−1 1
t= = m− = m − 1.
2 2
(b) Prove that C cannot be a perfect code. That is, there is no integer M such
that
t
X n
M (q − 1)k = q n .
k=0
k
For C to be perfect, each vector in Fqn would have to be contained in exactly one of the
M codeword spheres of radius t. However, we know that there are codewords x and y with
d(x, y) = 2m = 2t + 2. Consider the vector v obtained by changing t + 1 of those digits
where x disagrees with y to the corresponding digits in y. Then d(v, x) = d(v, y) = t + 1,
so v does not lie within the codeword spheres about x or y. If v were within a distance t
from another codeword z, the triangle inequality would imply that
d(x, z) ≤ d(x, v) + d(v, z) = t + 1 + t = 2t + 1,
contradicting the fact that the code has minimum distance 2t + 2. Thus v does not lie in
any codeword sphere. That is, C is not a perfect code.
1.B Balanced Block Designs

1.B. BALANCED BLOCK DESIGNS 17
Definition: A balanced block design consists of a collection of b subsets, called blocks,

of a set S of v points such that
(i) each point lies in exactly r blocks;
(ii) each block contains exactly k points;
(iii) each pair of points occurs together in exactly λ blocks.
Such a design is called a (b, v, r, k, λ) design.
• Let S = {1, 2, 3, 4, 5, 6, 7} and consider the subsets {1, 2, 4}, {2, 3, 5}, {3, 4, 6},
{4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3} of S. Each number lies in exactly 3 blocks, each
block contains 3 numbers, and each pair of numbers occurs together in exactly 1
block. The six lines and circle in Fig. 1.3 represent the blocks. Hence these subsets
form a (7, 7, 3, 3, 1) design.
Figure 1.3: Seven-point plane.
Remark: The parameters (b, v, r, k, λ) are not independent. Consider the set of
ordered pairs
T = {(x, B) : x is a point, B is a block, x ∈ B}.
Since each of the v points lie in r blocks, there must be a total of vr ordered pairs
in T . Alternatively, we know that since there are b blocks and k points in each
block, we can form exactly bk such pairs. Thus bk = vr. Similarly, by considering
the set
U = {(x, y, B) : x, y are distinct points, B is a block, x, y ∈ B},
we deduce
bk(k − 1) = λv(v − 1),
which, using bk = vr, simplifies to r(k − 1) = λ(v − 1).
Definition: A block design is symmetric if v = b (and hence k = r); that is, the
number of points and blocks is identical. For brevity, this is called a (v, k, λ)
design.
Definition: The incidence matrix of a block design is a v×b matrix with entries

1 if xi ∈ Bj ,
aij =
0 if xi ∈
/ Bj ,
where xi , i = 1, . . . , v are the design points and Bj , j = 1, . . . , b are the design

blocks.
• For our above (7, 3, 1) symmetric design, the incidence matrix A is

 
1 0 0 0 1 0 1
1 1 0 0 0 1 0
 
0 1 1 0 0 0 1
 
 1 0 1 1 0 0 0 .
 
0 1 0 1 1 0 0
 
0 0 1 0 1 1 0
0 0 0 1 0 1 1
• We now construct a (7, 16, 3) binary code C consisting of the zero vector 0, the
unit vector 1, the 7 rows of A, and the 7 rows of the matrix B obtained from A by
the relabelling 0 ↔ 1:
   
0 0 0 0 0 0 0 0
 1  1 1 1 1 1 1 1
   
   
   
 a1   1 0 0 0 1 0 1
   
 a2   1 1 0 0 0 1 0
   
 a3   0 1 1 0 0 0 1
   
 a4   1 0 1 1 0 0 0
   
 a5   0 1 0 1 1 0 0
   
 a6   0 0 1 0 1 1 0
C=
 a7  =  0
  .
   0 0 1 0 1 1
   
   
 b1   0 1 1 1 0 1 0
   
 b2   0 0 1 1 1 0 1
   
 b3   1 0 0 1 1 1 0
   
 b4   0 1 0 0 1 1 1
   
 b5   1 0 1 0 0 1 1
   
 b6   1 1 0 1 0 0 1
b7 1 1 1 0 1 0 0
To find the minimum distance of this code, note that each row of A has exactly
three 1s (since r = 3) and any two distinct rows of A have exactly one 1 in common
1.C. THE ISBN CODE 19
(since λ = 1). Hence d(ai , aj ) = 3 + 3 − 2(1) = 4 for i 6= j. Likewise, d(bi , bj ) = 4.

Furthermore,
d(0, ai ) = 3, d(0, bi ) = 4,
d(1, ai ) = 4, d(1, bi ) = 3,
d(ai , bi ) = d(0, 1) = 7,
for i = 1, . . . , 7. Finally, ai and bj disagree in precisely those places where ai and aj
agree, so
d(ai , bj ) = w(ai − bj ) = w(1 − (ai − aj )) = w(1) + w(ai − aj ) − 2w(ai − aj )

= 7 − w(ai − aj ) = 7 − d(ai , aj ) = 7 − 4 = 3, for i 6= j.
Thus C is a (7, 16, 3) code, which in fact is perfect, since the equality in Eq. (1.1) is
satisfied:
7 7
16 + = 16(1 + 7) = 128 = 27 .
0 1
The existence of a perfect binary (7, 16, 3) code establishes A2 (7, 3) = 16, so we
have now established another entry of Table 1.1.
1.C The ISBN Code

Modern books are assigned an International Standard Book Number (ISBN), a 10-
digit codeword, by the publisher. For example, Hill [1997] has the ISBN number
0-19-853803-0. The three hyphens separate the codeword into four fields. The first
field specifies the language (0 means English), the second field indicates the publisher
(19 means Oxford University Press), the third field (853803) is the book number
assigned by the publisher, and the final digit (0) is a check digit. If the digits of the
ISBN number are denoted x = x1 . . . x10 , then the check digit x10 is chosen as
9
X
x10 = kxk (mod 11).
k=1
If x10 turns out to be 10, an X is printed in place of the final digit. The tenth digit
serves to make the weighted check sum
10
X 9
X 9
X 9
X
kxk = kxk + 10 kxk = 11 kxk = 0 (mod 11).
k=1 k=1 k=1 k=1
So, if 10
P
k=1 kxk 6= 0 (mod 11), we know that an error has occurred. In fact, the ISBN
number is able to (ii) detect a single error or (ii) detect a transposition error that
results in two digits (not necessarily adjacent) being interchanged.
P10If a single error occurs, then some digit xj is received as xj + e with e 6= 0. Then
k=1 kxk + je = je (mod 11) 6= 0 (mod 11) since j and e are nonzero.
Let y be the vector obtained by exchanging the digits xj and xk in an ISBN
code x, where j 6= k. Then
10
X
ixi + (k − j)xj + (j − k)xk = (k − j)xj + (j − k)xk (mod 11)
i=1
= (k − j)(xj − xk ) (mod 11) 6= 0 (mod 11)
if xj 6= xk .
In the above arguments we have used the property of the field Z11 (the integers
modulo 11) that the product of two nonzero elements is always nonzero (since ab = 0
and a 6= 0 ⇒ a−1 ab = 0 ⇒ b = 0). Consequently, Zab with a, b > 1 cannot be a field
because the product ab = 0 (mod ab), even though a 6= 0 and b 6= 0. Note also that
there can be no inverse a−1 in Zab , for otherwise b = a−1 ab = a−1 0 = 0 (mod ab).
In fact, Zp is a field ⇐⇒ p is prime (cf. Theorem 5). For this reason, the ISBN
code is calculated in Z11 and not in Z10 , where 2 · 5 = 0 (mod n).
The ISBN code cannot be used to correct errors unless we know a priori which digit
is in error. To do this, we first need to construct a table of inverses modulo 11 using
the Euclidean division algorithm. For example, let y be the inverse of 2 modulo 11.
Then 2y = 1 (mod 11) implies 2y = 11q+1 or 1 = −11q+2y for some integers y and q.
On dividing 11 by 2 as we would to show that gcd(11, 2) = 1, we find 11 = 5 · 2 + 1 so
that 1 = 11 − 5 · 2, from which we see that q = −1 and y = −5 (mod 11) = 6 (mod 11)
are solutions. Similarly, 7−1 = 8 (mod 11) since 11 = 1 · 7 + 4 and 7 = 1 · 4 + 3 and
4 = 1·3+1, so 1 = 4−1·3 = 4−1·(7−1·4) = 2·4−1·7 = 2·(11−1·7)−1·7 = 2·11−3·7.
Thus −3 · 7 = −2 · 11 + 1; that is, 7 and −3 = 8 are inverses mod 11. The complete
table of inverses modulo 11 is shown in Table 1.2.
x 1 2 3 4 5 6 7 8 9 10
x−1 1 6 4 3 9 2 8 7 5 10
Table 1.2: Inverses modulo 11.
Suppose that we detect an error and we also know that it is the digit xj that is
in error (and hence unknown). Then we can use our table of inverses to solve for the
value of xj , assuming all of the other digits are correct. Since
10
X
jxj + kxk = 0 (mod 11),
k=1
k6=j
we know that
10
X
xj = −j −1 kxk (mod 11).
k=1
k6=j
1.C. THE ISBN CODE 21
For example, if we did not know the fourth digit x of the ISBN 0-19-x53803-0, we
would calculate
x = −4−1 (1 · 0 + 2 · 1 + 3 · 9 + 5 · 5 + 6 · 3 + 7 · 8 + 8 · 0 + 9 · 3 + 10 · 0) (mod 11)

= −3(0 + 2 + 5 + 3 + 7 + 1 + 0 + 5 + 0) (mod 11) = −3(1) (mod 11) = 8,
which is indeed correct.
Problem 1.5: A smudge has obscured one of the digits of the ISBN code 0-8018-
6183057294739-1.
Determine the unknown digit.
The sixth digit is
x6 = −6−1 (1 · 0 + 2 · 8 + 3 · 0 + 4 · 1 + 5 · 8 + 7 · 7 + 8 · 3 + 9 · 9 + 10 · 1) (mod 11)

= −2(0 + 5 + 0 + 4 + 7 + 5 + 2 + 4 + 10) (mod 11)
= −2(4) (mod 11) = −8 (mod 11) = 3.
Problem 1.6: A smudge has obscured one of the digits of the ISBN code 0-393-
051061830572940-X.
Determine the unknown digit.
The eighth digit is
x5 = −8−1 (1 · 0 + 2 · 3 + 3 · 9 + 4 · 3 + 5 · 0 + 6 · 5 + 7 · 1 + 9 · 0 + 10 · 10) (mod 11)

= −7(0 + 6 + 5 + 1 + 0 + 8 + 7 + 0 + 1) (mod 11)
= −7(6) (mod 11) = −9 (mod 11) = 2.
Chapter 2
Linear Codes
An important class of codes are linear codes in the vector space Fqn , where Fq is a
field.
Definition: A linear code C is a code for which, whenever u ∈ C and v ∈ C, then
αu + βv ∈ C for all α, β ∈ Fq . That is, C is a linear subspace of Fqn .
Remark: The zero vector 0 automatically belongs to all linear codes.
Remark: A binary code C is linear ⇐⇒ it contains 0 and the sum of any two
codewords in C is also in C.
Problem 2.1: Show that the (7, 16, 3) code developed in the previous chapter is
linear.
Remark: A linear code C will always be a k-dimensional linear subspace of Fqn for
some integer k between 1 and n. A k-dimensional code C is simply the set of all
linear combinations of k linearly independent codewords, called basis vectors. We
say that these k basis codewords generate or span the entire code space C.
Definition: We say that a k-dimensional code in Fqn is an [n, k] code, or if we also

wish to specify the minimum distance d, an [n, k, d] code.
Remark: Note that a q-ary [n, k, d] code is an (n, q k , d) code. To see this, let the k
basis vectors of an [n, k, d] code be uj , for j = 1, . . . , k. The q k codewords are
obtained as the linear combinations kj=1 aj uj ; there are q possible values for each
P
of the k coefficients aj . Note that
k
X k
X k
X
aj uj = bj u j ⇒ (aj − bj )uj = 0 ⇒ aj = bj , j = 1, . . . k,
j=1 j=1 j=1
by the linear independence of the basis vectors, so the q k generated codewords are
distinct.
22
23
Remark: Not every (n, q k , d) code is a q-ary [n, k, d] code (it might not be linear).
Definition: Define the minimum weight of a code to be w(C) = min{w(x) : x ∈

C, x 6= 0}.
One of the advantages of linear codes is illustrated by the following lemma.
Lemma 2.1 (Distance of a Linear Code): If C is a linear code in Fqn , then d(C) =
w(C).
Proof: There exist codewords x, y, and z with x 6= y, and z 6= 0 such that

d(x, y) = d(C) and w(z) = w(C). Then
d(C) ≤ d(z, 0) = w(z − 0) = w(z) = w(C) ≤ w(x − y) = d(x, y) = d(C),
so w(C) = d(C).
Remark: Lemma 2.1 implies, for a linear code, that we only have to examine the
weights of the M − 1 nonzero codewords in order to find the minimum distance.
M

In contrast, for a general nonlinear code, we need to make 2 = M (M − 1)/2
comparisons (between all possible pairs of distinct codewords) to determine the
minimum distance.
Definition: A k × n matrix with rows that are basis vectors for a linear [n, k] code C
is called a generator matrix of C.
• A q-ary repetition code of length n is an [n, 1, n] code with generator matrix

[1 1 . . . 1].
Problem 2.2: Show that the (7, 16, 3) perfect binary code in Chapter 1 is a [7, 4, 3]
linear code (note that 24 = 16) with generator matrix
   
1 1 1 1 1 1 1 1
 a1   1 0 0 0 1 0 1
 = 
 a2   1 1 0 0 0 1 0
a3 0 1 1 0 0 0 1
24 CHAPTER 2. LINEAR CODES
Remark: Linear q-ary codes are not defined unless q is a power of a prime (this is sim-
ply the requirement for the existence of the field Fq ). However, lower-dimensional
codes can always be obtained from linear q-ary codes by projection onto a lower-
dimensional subspace of Fqn . For example, the ISBN code is a subset of the 9-
10
dimensional subspace of F11 consisting of all vectors perpendicular to the vector
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); this is the space
( 10
)
X
(x1 x2 . . . x10 ) : kxk = 0 (mod 11) .
k=1
However, not all vectors in this set (for example X-00-000000-1) are in the ISBN
code. That is, the ISBN code is not a linear code.
For linear codes we must slightly restrict our definition of equivalence so that the
codes remain linear (e.g., in order that the zero vector remains in the code).
Definition: Two linear q-ary codes are equivalent if one can be obtained from the
other by a combination of
(A) permutation of the columns of the code;
(B) multiplication of the symbols appearing in a fixed column by a nonzero scalar.
Definition: A k × n matrix of rank k is in reduced echelon form (or standard form)

if it can be written as
[ 1k | A ],
where 1k is the k × k identity matrix and A is a k × (n − k) matrix.
Remark: A generator matrix for a vector space can always be reduced to an equiv-
alent reduced echelon form spanning the same vector space, by permutation of its
rows and columns, multiplication of a row by a non-zero scalar, or addition of one
row to another. Note that any combination of these operations, including operation
(B) above, will generate equivalent linear codes.
Problem 2.3: Show that the generator matrix for the (7, 16, 3) perfect code in Chap-
ter 1 can be written in reduced echelon form as
 
1 0 0 0 1 0 1
0 1 0 0 1 1 1
G=  0 0 1 0 1 1 0 .

0 0 0 1 0 1 1
2.A. ENCODING AND DECODING 25
2.A Encoding and Decoding

A [n, k] linear code C contains q k codewords, corresponding to q k distinct messages.
We identify each message with a k-tuple
u = [ u1 u2 . . . uk ],
where the components ui are elements of Fq . We can encode u by multiplying it on

the right with the generator matrix G. This maps u to the linear combination uG of
the codewords. In particular the message with components ui = δik gets mapped to
the codeword appearing in the kth row of G.
• Given the message [0, 1, 0, 1] and the above generator matrix for our (7, 16, 3) code,
the encoded codeword
 
1 0 0 0 1 0 1
0 1 0 0 1 1 1
[ 0 1 0 1 ] 0 0 1 0 1 1 0 = [0 1 0 1 1 0 0]

0 0 0 1 0 1 1
is just the sum of the second and fourth rows of G.
Problem 2.4: If a generator for a linear [n, k] code is in standard form, show that
the message vector is just the first k bits of the codeword.
Definition: Let C be a linear code over Fqn . Let a be any vector in Fqn . The set
a + C = {a + x : x ∈ C} is called a coset of C.
Lemma 2.2 (Equivalent Cosets): Let C be a linear code in Fqn and a ∈ Fqn . If b is
an element of the coset a + C, then
b + C = a + C.
Proof: Since b ∈ a + C, then b = a + x for some x ∈ C. Consider any vector

b + y ∈ b + C, with y ∈ C. Then
b + y = (a + x) + y = a + (x + y) ∈ a + C,
so b + C ⊂ a + C. Furthermore a = b + (−x) ∈ b + C, so the same argument implies

a + C ⊂ b + C. Hence b + C = a + C.
The following theorem from group theory states that Fqn is just the union of q n−k
distinct cosets of a linear [n, k] code C, each containing q k elements.
Theorem 2.1 (Lagrange’s Theorem): Suppose C is an [n, k] code in Fqn . Then
(i) every vector of Fqn is in some coset of C;
(ii) every coset contains exactly q k vectors;

(iii) any two cosets are either equivalent or disjoint.
Proof:
(i) a = a + 0 ∈ a + C for every a ∈ Fqn .
(ii) Since the mapping φ(x) = a + x is one-to-one, |a + C| = |C| = q k . Here |C|
denotes the number of elements in C.
(iii) Let a, b ∈ Fqn . Suppose that the cosets a + C and b + C have a common vector
v = a + x = b + y, with x, y ∈ C. Then b = a + (x − y) ∈ a + C, so by
Lemma 2.2 b + C = a + C.
Definition: The standard array (or Slepian) of a linear [n, k] code C in Fqn is a
q n−k × q k array listing all the cosets of C. The first row consists of the codewords
in C themselves, listed with 0 appearing in the first column. Subsequent rows are
listed one at a time, beginning with a vector of minimal weight that has not already
been listed in previous rows, such that the entry in the (i, j)th position is the sum
of the entries in position (i, 1) and position (1, j). The vectors in the first column
of the array are referred to as coset leaders.
• Let us revisit our linear (5, 4, 3) code

 
0 0 0 0 0
0 1 1 0 1
C3 =  1

0 1 1 0
1 1 0 1 1
with generator matrix
0 1 1 0 1
G3 = .
1 0 1 1 0
The standard array for C3 is a 8 × 4 array of cosets listed here in three groups of
increasing coset leader weight:
0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0
0 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1
0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1
0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1
1 0 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1 0 1 1
0 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0
0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1
2.A. ENCODING AND DECODING 27
Remark: The last two rows of the standard array for C3 could equally well have
been written as
1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1
1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0
Definition: If the codeword x is sent, but the received vector is y, we define the
.
error vector e = y − x.
Remark: If no more than t errors have occurred, the coset leaders of weight t or
less are precisely the error vectors that can be corrected. Recall that the code C3 ,
having minimum distance 3, can only correct one error. For the code C3 , as long as
no more than one error has occurred, the error vector will have weight at most one.
We can then decode the received vector by checking to see under which codeword
it appears in the standard array, remembering that the codewords themselves are
listed in the first row. For example, if y = 10111 is received, we know that the
error vector e = 00001, and the transmitted codeword must have been x = y − e =
10111 − 00001 = 10110.
Remark: If two errors have occurred, one cannot determine the original vector with
certainty, because in each row with coset leader weight 2, there are actually two
vectors of weight 2. For a code with minimum distance 2t + 1, the rows in the
standard array of coset leader weight greater than t can be written in more than one
way, as we have seen above. Thus, if 01110 is received, then either 01110 − 00011 =
01101 or 01110 − 11000 = 10110 could have been transmitted.
Remark: Let C be a binary [n, k] linear code and αi denote the number of coset
leaders for C having weight i, where i = 0, . . . , n. If p is the error probability for a
single bit, then the probability Pcorr (C) that a received vector is correctly decoded
is n
X
Pcorr (C) = αi pi (1 − p)n−i .
i=0
Remark: If C can correct t errors then the coset leaders of weight no more than
t
are unique and hence the total number of such leaders of weight i is αi = ni for
0 ≤ i ≤ t. In particular, if n = t, then
n
X n i
Pcorr (C) = p (1 − p)n−i = (p + 1 − p)n = 1.
i=0
i
Such a code is able to correct all possible errors (no matter how poor the transmis-
sion line is); however, since C only contains a single codeword, it cannot be used
to send any information!
Remark: For i > t, the coefficients αi can be difficult to calculate. For a perfect
code, however, we know that every vector is within a distance t of some codeword.
Thus, the error vectors that can be corrected by a perfect code are precisely those
vectors of weight no more than t; consequently,

 n for 0 ≤ i ≤ t,
αi = i

0 for i > t.
• For the code C3 , we see that α0 = 1, α1 = 5, α2 = 2, and α3 = α4 = α5 = 0. Hence
Pcorr (C3 ) = (1 − p)5 + 5p(1 − p)4 + 2p2 (1 − p)3 = (1 − p)3 (1 + 3p − 2p2 ).

.
For example, if p = 0.01, then Pcorr = 0.99921 and Perr = 1 − Pcorr = 0.00079,
more than a factor 12 lower than the raw bit error probability p. Of course, this
improvement in reliability comes at a price: we must now send n = 5 bits for every
k = 2 information bits. The ratio k/n is referred to as the rate of the code. It
is interesting to compare the performance of C3 with a code that sends two bits
of information by using two back-to-back repetition codes each of length 5 and for
which α0 = 1, α1 = 5, and α2 = 10. We find that Pcorr for such a code is
[(1 − p)5 + 5p(1 − p)4 + 10p2 (1 − p)3 ]2 = [(1 − p)3 (1 + 3p + 6p2 )]2 = 0.99998
so that Perr = 0.00002. While this error rate is almost four times lower than that
for C3 , bear in mind that the repetition scheme requires the transmission of twice
as much data for the same number of information digits (i.e. it has half the rate
of C3 ).
2.B Syndrome Decoding

The standard array for our (5, 4, 3) code had 32 entries; for a general code of length n,
we will have to search through 2n entries every time we wish to decode a received
vector. For codes of any reasonable length, this is not practical. Fortunately, there is
a more efficient alternative, which we now describe.
Definition: Let C be a [n, k] linear code. The dual code C ⊥ of C in Fqn is the set of
all vectors that are orthogonal to every codeword of C:
C ⊥ = {v ∈ Fqn : v·u = 0, ∀u ∈ C}.
Problem 2.5: Show that dual code C ⊥ to a linear code C is itself linear.
2.B. SYNDROME DECODING 29
Remark: The dual code C ⊥ is just the null space of G:
C ⊥ = {u ∈ Fqn : Gut = 0}.
That is,
v ∈ C ⊥ ⇐⇒ Gv t = 0
(where the superscript t denotes transposition). This just says that v is orthogonal
to each of the rows of G. From linear algebra, we know that the space spanned by
the k independent rows of G is a k dimensional subspace and the null space of G,
which is just C ⊥ , is an n − k dimensional subspace.
Remark: Since every vector in C is perpendicular to every vector in C ⊥ , we know

immediately that C ⊂ (C ⊥ )⊥ . In fact, since the dimension of the linear supspace
(C ⊥ )⊥ is n − (n − k) = k, we deduce that C = (C ⊥ )⊥ .
Definition: Let C be a [n, k] linear code. An (n − k) × n generator matrix H for C ⊥

is called a parity-check matrix.
.
Definition: The redundancy r = n − k of a code represents the number of parity
check digits in the code.
Remark: A code C is completely specified by its parity-check matrix:
C = (C ⊥ )⊥ = {u ∈ Fqn : Hut = 0};
that is, C is the space of all vectors that are orthogonal to every vector in C ⊥ . In
other words, Hut = 0 ⇐⇒ u ∈ C.
Theorem 2.2 (Minimum Distance): A linear code has minimum distance d ⇐⇒ d

is the maximum number such that any d − 1 columns of its parity-check matrix are
linearly independent.
Proof: Let C be a linear code and u be a codeword such that w(u) = d(C) = d.
Since
u ∈ C ⇐⇒ Hut = 0
and u has d nonzero components, we see that some d columns of H are linearly
dependent. However, any d − 1 columns of H must be linearly independent, or else
there would exist a nonzero codeword in C with weight d − 1.
Remark: Equivalently, a linear code has minimum distance d if d is the smallest

number for which some d columns of its parity-check matrix are linearly dependent.
• For a code with weight 3, Theorem 2.2 tells us that any two columns of its parity-
check matrix must be linearly independent, but that some 3 columns are linearly
dependent.
Definition: Given a linear code with parity-check matrix H, the column vector Hut
is called the syndrome of u.
Lemma 2.3: Two vectors u and v are in the same coset of a linear code C ⇐⇒
they have the same syndrome.
Proof:
u − v ∈ C ⇐⇒ H(u − v)t = 0 ⇐⇒ Hut = Hv t .
Remark: We thus see that is there is a one-to-one correspondence between cosets

and syndromes. This leads to an alternative decoding scheme known as syndrome
decoding. When a vector u is received, one computes the syndrome Hut and
compares it to the syndromes of the coset leaders. If the coset leader having the
same syndrome is of minimal weight within its coset, it is the error vector for
decoding u.
To compute the syndrome for a code, we need only first determine the parity check
matrix. The following lemma describes an easy way to construct the standard form
of the parity-check matrix from the standard-form generator matrix.
Lemma 2.4: An (n − k) × n parity-check matrix H for an [n, k] code generated by

the matrix G = [1k | A], where A is a k × (n − k) matrix, is given by
[ −At | 1n−k ].
Proof: This follows from the fact that the rows of G are orthogonal to every row
of H, in other words, that

t −A
GH = [ 1k A ] = 1k (−A) + (A)1n−k = −A + A = 0,
1n−k
the k × (n − k) zero matrix.
• A parity-check matrix H3 for our (5, 4, 3) code is

 
1 1 1 0 0
H3 = 1 0
 0 1 0 .
0 1 0 0 1
Problem 2.6: Show that the null space of a matrix is invariant to standard row
reduction operations (permutation of rows, multiplication of a row by a non-zero
scalar, and addition of one row to another) and that these operations may be used
to put a matrix H of full rank into standard form.
Remark: The syndrome Het of a binary error vector e is just the sum of those
columns of H for which the corresponding entry in e is nonzero.
The following theorem makes it particularly easy to correct errors of unit weight.
It will play a particularly important role for the Hamming codes discussed in the next
chapter.
Theorem 2.3: The syndrome of a vector that has a single error of m in the ith
position is m times the ith column of H.
Proof: Let ei be the vector with the value m in the ith position and zero in all
other positions. If the codeword x is sent and the vector y = x + ei is received the
syndrome Hy t = Hxt + Heti = 0 + Heti = Heti is just m times the ith column of H.
• For our (5, 4, 3) code, if y = 10111 is received, we compute Hy t = 001, which

matches the fifth column of H. Thus, the fifth digit is in error (assuming that only
a single error has occurred), and we decode y to the codeword 10110, just as we
deduced earlier using the standard array.
Remark: If the syndrome does not match any of the columns of H, we know that
more than one error has occurred. We can still determine which coset the syndrome
belongs to by comparing the computed syndrome with a table of syndromes of all
coset leaders. If the corresponding coset leader has minimal weight within its coset,
we are able to correct the error. To decode errors of weight greater than one we
will need to construct a syndrome table, but this table, having only q n−k entries,
is smaller than the standard array, which has q n entries.
Problem 2.7: Using the binary linear code with parity check matrix
 
0 0 1 1
H= 1 0 1
 0 ,
0 1 1 0
decode the received vector 1011.
The syndrome [0, 0, 1]t corresponds to the second column of H. So the transmitted
vector was 1011 − 0100 = 1111.
Problem 2.8: Consider the linear [6, M, d] binary code C generated by

 
1 1 0 0 1 1
G =  0 1 0 1 1 0 .
1 0 1 1 1 0
(a) Find a parity check matrix H for C.

First, we put G in standard form:
 
1 0 0 1 0 1
G = 0 1 0 1 1 0 ,
0 0 1 0 1 1
from which we see that  

1 1 0 1 0 0
H = 0 1 1 0 1 0 ,
1 0 1 0 0 1
(b) Determine the number of codewords M and minimum distance d of C. Justify

your answers.
Since G has 3 (linearly independent) rows, it spans a three-dimensional code space over
F2 . Thus, M = 23 = 8. Since no two columns of H are linearly dependent but the third
column is the sum of the first two, we know by Theorem 2.2 that d = 3.
(c) How many errors can this code correct?
The code can correct only b(d − 1)/2c = 1 error.
(d) Is C a perfect code? Justify your answer.
No, because 8 60 + 6
= 8(1 + 6) = 56 < 64 = 26 .

1
(e) Suppose the vector 011011 is received. Can this vector be decoded, assuming
that only one error has occurred? If so, what was the transmitted vector?
The syndrome is [110]t , which is the second column of H. So the transmitted vector
was 001011.
(f) Suppose the vector 011010 is received. Can this vector be decoded, assuming
that only one error has occurred? If so, what was the transmitted vector?
No, we cannot decode this vector because the syndrome is [111]t , which is not a syndrome
corresponding to an error vector of weight 1. At least 2 errors must have occurred and we
cannot correct 2 errors with this code.
Problem 2.9:
(a) Let C be a linear code. If C = C ⊥ , prove that n is even and C must be an

[n, n/2] code.
Let k be the dimension of the linear space C. The dimension of C ⊥ is n − k. If C = C ⊥ ,
then k = n − k, so n = 2k.
(b) Prove that exactly 2n−1 vectors in F2n have even weight.
By specifying that a vector in F2n has even weight, we are effectively imposing a parity
check equation on it; the last bit is constrained to be the sum of the previous n − 1 bits. So
one can construct exactly 2q−1 vectors of even weight.
(c) If C ⊥ is the binary repetition code of length n, prove that C is a binary code
consisting of all even weight vectors. Hint: find a generator matrix for C ⊥ .
The generator matrix for C ⊥ is the 1 × n matrix
G⊥ = [ 1 1 1 ... 1 1 1 ].
This must be a parity checkPmatrix for C, so we know that C consists of all vectors
x1 x2 . . . xn for which w(x) = ni=1 xi = 0 (mod 2). That is, C consists of all even weight
vectors.
Alternatively, we can explicitly find a parity check matrix for C ⊥ ; namely, the n − 1 × n
matrix
1 1 0 0 ··· 0 0
 
1 0 1 0 ··· 0 0
 
⊥
1 0 0 1 ··· 0 0
H =  ..
 .. .. .
. . . 

1 0 0 ··· 0 1 0
1 0 0 0 ··· 0 1
We see that H ⊥ is a generator matrix for C and that C consists only of even weight vectors.
Furthermore, the vector space C has dimension n − 1, so we know that it contains all 2n−1
even weight vectors.
Problem 2.10: Let C be the code consisting of all vectors in Fqn with checksum
0 mod q. Let C 0 be the q-ary repetition code of length n.
(a) Find a generator G and parity-check matrix H for C. What are the sizes of
these matrices?
A generator for C is the (n − 1) × n matrix
1 0 0 ··· 0 −1
 
0 1 0 ··· 0 −1 
··· −1 
 
0 0 1 0
G=  ... .. .. .
 . . 

0 0 ··· 1 0 −1 
0 0 0 ··· 1 −1
A parity-check matrix for C is the 1 × n matrix
H = [1 1 ... 1 ].
(b) Find a generator G0 and parity-check matrix H 0 for C 0 .

A generator for C 0 is the 1 × n matrix G0 = H. A parity-check matrix for C 0 is the
(n − 1) × n matrix H 0 = G.
(c) Which of the following statements are correct? Circle all correct statements.

0 ⊥
• C ⊂ C
,

• C 0 = C ⊥
,

0 ⊥
• C ⊃ C
,
• Neither C 0 ⊃ C ⊥ nor C 0 ⊂ C ⊥ holds.
• C 0 ∩ C ⊥ = ∅,
(d) Find d(C). Justify your answer.

Any set containing just one column of the parity-check matrix H of C is linearly inde-
pendent, but the first and second column (say) are not. From Theorem 2.2, we conclude
that d(C) = 2.
(e) Find d(C 0 ). Justify your answer.
Since each codeword of C 0 differs from all of the others in all n places, we see that
d(C 0 ) = n.
(f) How many codewords are there in C?
Since G has n − 1 rows, there are q n−1 possible codewords.
(g) How many codewords are there in C 0 ?
Since G0 has 1 row, there are q possible codewords.
(h) Suppose q = 2 and n is odd. Use part(g) to prove that
n−1
2
X n
= 2n−1 .
k=0
k
A odd-length binary (n, 2, n) code can correct correct t = (n − 1)/2 errors. Odd-length
binary codes are (trivially) perfect: they satisfy the Hamming equality
n−1
2
X n
2 = 2n ,
k
k=0
from which the desired result follows. (Equivalently, this is a consequence of the left-right
symmetry of Pascal’s triangle.)
Problem 2.11: Consider the linear [7, M, d] binary code C generated by

 
1 1 0 0 0 1 1
G= 1  0 1 1 0 0 1 ,
0 0 1 0 1 1 1
(a) Find a parity check matrix H for C.

First, we row reduce G to standard form:
 
1 0 0 1 1 1 0
G = 0 1 0 1 1 0 1 ,
0 0 1 0 1 1 1
from which we see that  

1 1 0 1 0 0 0
1 1 1 0 1 0 0
H=
1
,
0 1 0 0 1 0
0 1 1 0 0 0 1
(b) Determine the number of codewords M in C. Justify your answer.

Since G has 3 (linearly independent) rows, it spans a three-dimensional code space over
F2 . Thus, M = 23 = 8.
(c) Find the maximum number N such that any set of N columns of H are linearly
independent. Justify your answer.
It is convenient to divide the columns into two groups of clearly linearly independent
vectors: the first three columns (which are distinct and do not sum up to zero) and the last
four columns. Each of the first three columns has weight 3, and therefore cannot be written
as a sum of two of the last four columns. Any two of the first three columns differ in more
than one place, and so their sum cannot equal any of the last four columns. Thus, no three
columns of H are linearly dependent. However, the sum of the first three columns is equal
to the fifth column, so N = 3 is the maximum number of linearly independent columns.
(d) Determine the minimum distance d of C.
From part (c) and Theorem 2.2 we know that d = 4.
(e) How many errors can C correct?
The code can correct only b(d − 1)/2c = 1 error.
(f) Is C a perfect code? Justify your answer.
No, from Problem 1.4(b) we know that a code with even distance can never be perfect.
Alternatively, we note that 8 70 + 71 = 8(1 + 7) = 64 < 128 = 27 .

(g) By examining the inner (dot) products of the rows of G with each other,
determine which of the following statements are correct (circle all correct statements
and explain):

• C ⊂ C ⊥
,
• C = C ⊥,
• C ⊃ C ⊥,
• Neither C ⊃ C ⊥ nor C ⊂ C ⊥ holds.
• C ∩ C ⊥ = ∅,
The only correct statement is C ⊂ C ⊥ , since the rows of G are orthogonal to each other.
Note that C cannot be self-dual because it has dimension k = 3 and C ⊥ has dimension
n − k = 7 − 3 = 4.
(h) Suppose the vector 1100011 is received. Can this vector be decoded, assuming
that no more than one error has occurred? If so, what was the transmitted codeword?
Yes, in fact this is the first row of G, so it must be a codeword. So no errors have
occurred; the transmitted codeword was 1100011. As a check, one can verify that the
syndrome is [0000]t .
(i) Suppose the vector 1010100 is received. Can this vector be decoded, assuming
that no more than one error has occurred? If so, what was the transmitted codeword?
The syndrome is [1101]t , which is the second column of H. So the transmitted vector
was 1110100.
(j) Suppose the vector 1111111 is received. Show that at least 3 errors have
occurred. Can this vector be unambiguously decoded by C? If so what was the
transmitted codeword? If not, and if only 3 errors have occurred, what are the
possible codewords that could have been transmitted?
Since the syndrome [1011]t is neither a column of H nor the sum of two columns of H,
it does not correspond to an error vector of weight 1 or 2. Thus, at least 3 errors have
occurred. We cannot unambiguously decode this vector because C can only correct 1 error.
In fact, since the rows of G have weight 4, by part (g) and Problem 4.3, we know that
all nonzero codewords in C have weight 4. So any nonzero codeword could have been
transmitted, with 3 errors, to receive 1111111.
Problem 2.12: Consider a single error-correcting ternary code C with parity-check

matrix  
2 0 1 1 0 0
H =  1 2 0 0 1 0 .
0 2 2 0 0 1
(a) Find a generator matrix G.

A generator matrix is
 
1 0 0 1 2 0
G = 0 1 0 0 1 1 .
0 0 1 2 0 1
(b) Use G to encode the information messages 100, 010, 001, 200, 201, and 221.
The information word x is encoded as xG. So the information messages can be encoded
as follows:    
1 0 0 1 0 0 1 2 0
 0 1 0   0 1 0 0 1 1
0 0 1 1 0 0 1 2 0
   
0 0 1 2 0 1
2 0 0 0 1 0 0 1 1 =
   .
2 0 0 2 1 0
2 0 1 0 0 1 2 0 1
   
2 0 1 1 1 1
2 2 1 2 2 1 1 0 0
That is, the encoded words are the rows of the resulting matrix, namely 100120, 010011,
001201, 200210, 201111, and 221100.
(c) What is the minimum distance of this code?
Since  
1 0 2 2 0 0
2H = 2
 1 0 0 2 0 ,
0 1 1 0 0 2
we see that the columns of H and 2H are distinct, so no two columns of H are linearly
dependent. But the first column of H is the fifth column plus twice the fourth column, so
by Theorem 2.2 we know that d = 3.
(d) Decode the received word 122112, if possible. If you can decode it, determine
the corresponding message vector.
The syndrome is  
1
  2   
2 0 1 1 0 0 
2
 2
1 2 0 0 1 0  
 =  0 .
1
0 2 2 0 0 1 
1
 1
2
The syndrome 201 is twice the third column of H, so the corrected word is 122112 −
2(00100) = 120112. Since G is in standard form, the corresponding message word, 120, is
just the first three bits of the codeword.
(e) Decode the received word 102201, if possible. If you can decode it, determine
the corresponding message vector.
The syndrome is  
1
  0   
2 0 1 1 0 0 
2
 0
1 2 0 0 1 0  
 =  1 .
2
0 2 2 0 0 1 
0
 2
1
The syndrome 012 is not a multiple of any column of H, so either an incorrect codeword
was transmitted or more than one error in transmission has occurred. But you can only
correct one error with this code, so you have to ask for a retransmission.
Chapter 3
Hamming Codes
One way to construct perfect binary [n, k] codes that can correct single errors is to
ensure that every nonzero vector in F2n−k appears as a unique column of H. In this
manner, the syndrome of every possible vector in F2n can be identified with a column
of H, so that every vector in F2n is at most a distance one away from a codeword.
This is called a binary Hamming code, which we now discuss in the general space Fqn ,
where Fq is a field.
Remark: One can form q − 1 distinct scalar multiples from any nonzero vector u
in Fqr : if λ, γ ∈ Fq , then
λu = γu ⇒ (λ − γ)u = 0 ⇒ λ = γ or u = (λ − γ)−1 0 = 0.
Definition: Given an integer r ≥ 2, let n = (q r − 1)/(q − 1). The Hamming code

Ham(r, q) is a linear [n, n − r] code in Fqn for which the columns of the r × n parity-
check matrix H are the n distinct non-zero vectors of Fqr with first nonzero entry
equal to 1.
Remark: Not only are the columns of H distinct, all nonzero multiples of any two
columns are also distinct. That is, any two columns of H are linearly independent.
The total number of nonzero column multiples that can thus be formed is n(q−1) =
q r − 1. Including the zero vector, we see that H yields a total of q r distinct
syndromes, corresponding to all possible error vectors of unit weight in Fqr .
• The columns of a parity-check matrix for the binary Hamming code Ham(r, 2)
consist of all possible nonzero binary codewords of length r.
Remark: The columns of a parity-check matrix H for a Hamming code may be

written in any order. However, both the syndromes and codewords will depend on
the order of the columns. If H is row reduced to standard form, the codewords will
be unchanged. However, other equivalent Ham(4, 2) codes obtained by rearranging
columns of H will have rearranged codewords.
38
39
Problem 3.1: Given a parity-check matrix H for a binary Hamming code, show that
the standard form for H (obtained by row reduction) is just a rearrangement of
the columns of H.
Remark: The dimension k of Ham(r, q) is given by

qr − 1
n−r = − r.
q−1
• A parity-check matrix for the one-dimensional code Ham(2, 2) is

0 1 1
,
1 0 1
which can row reduced to standard form:

1 1 0
.
1 0 1
The generator matrix is then seen to be [ 1 1 1 ]. That is, Ham(2, 2) is just the
binary triple-repetition code.
• A parity-check matrix for the one-dimensional code Ham(3, 2) in standard form, is

 
0 1 1 1 1 0 0
1 0 1 1 0 1 0 .
1 1 0 1 0 0 1
Problem 3.2: Show that this code is equivalent to the (7, 16, 3) perfect code in
Chapter 1.
Remark: An equivalent way to construct the binary Hamming code Ham(r, 2) is to

consider all n = 2r − 1 nonempty subsets of a set S containing r elements. Each of
these subsets corresponds to a position of a code in F2n . A codeword can then be
thought of as just a collection of nonempty subsets of S. Any particular element a
of S will appear in exactly half of all 2r subsets (that is, in 2r−1 subsets) of S, so
that an even number of the 2r − 1 nonempty subsets will contain a. This gives us
a parity-check equation, which says that the sum of all digits corresponding to a
subset containing a must be 0 (mod 2). There will be a parity-check equation for
each of the r elements of S corresponding to a row of the parity-check matrix H.
That is, each column of H corresponds to one of the subsets, with a 1 appearing
in the ith position if the subset contains the ith element and 0 if it doesn’t.
40 CHAPTER 3. HAMMING CODES
• A parity check matrix for Ham(3, 2) can be constructed by considering all possible
nonempty subsets of {a, b, c}, each of which corresponds to one of the bits of a
codeword x = x1 x2 . . . x7 in F27 :
a a a a
b b b b
c c c c
x1 x2 x3 x4 x5 x6 x7
Given any four binary information digits x1 , x2 , x3 , and x4 , there will be a unique
codeword satisfying Hx = 0; the parity-check digits x5 , x6 , and x7 can be deter-
mined from the three checksum equations corresponding to each of the elements a,
b, and c:
a : x2 + x3 + x4 + x5 = 0 (mod 2),
b: x1 + x3 + x4 + x6 = 0 (mod 2),
and
c: x1 + x2 + x4 + x7 = 0 (mod 2).
For example, the vector x = 1100110 corresponds to the collection
{{b, c}, {a, c}, {a}, {b}}.
Since there are an even number of as, bs, and cs in this collection, we know that x
is a codeword.
Problem 3.3: Show that two distinct codewords x and y that satisfy the above three
parity check equations must differ in at least 3 places.
Remark: When constructing binary Hamming codes, there is a distinct advantage in

arranging the parity-check matrix so that the columns, treated as binary numbers,
are in ascending order. The syndrome, interpreted in exactly the same way as a
binary number, immediately tells us in which position a single error has occurred.
• We can write a parity-check matrix for a Ham(3, 2) code in in the binary ascending
form  
0 0 0 1 1 1 1
H =  0 1 1 0 0 1 1 .
1 0 1 0 1 0 1
If the vector 1110110 is received, the syndrome is [0, 1, 1]t , which corresponds to
the binary number 3, so we know immediately that the a single error must have
occurred in the third position, without even looking at H. Thus, the transmitted
codeword was 1100110.
41
Remark: For nonbinary Hamming codes, we need to compare the computed syn-
drome with all nonzero multiples of the columns of the parity-check matrix.
• A parity-check matrix for Ham(2, 3) is

0 1 1 1
H= .
1 0 1 2
If the vector 2020, which has syndrome [2, 1]t = 2[1, 2]t , is received and at most a
single digit is in error, we see that an error of 2 has occurred in the last position
and decode the vector as x = y − e = 2020 − 0002 = 2021.
• A parity-check matrix for Ham(3, 3) is

 
0 0 0 0 1 1 1 1 1 1 1 1 1
H =  0 1 1 1 0 0 0 1 1 1 2 2 2 .
1 0 1 2 0 1 2 0 1 2 0 1 2
If the vector 2000 0000 00001 is sent and at most a single error has occurred, then
from the syndrome [1, 2, 1]t we see that an error of 1 has occurred in the second-last
position, so the transmitted vector was 2000 0000 00021.
The following theorem establishes that Hamming codes can always correct single
errors, as we saw in the above examples, and also that they are perfect.
Theorem 3.1 (Hamming Codes are Perfect): Every Ham(r, q) code is perfect and
has distance 3.
Proof: Since any two columns of H are linearly independent, we know from The-
orem 2.2 that Ham(r, q) has a distance of at least 3, so it can correct single errors.
The distance cannot be any greater than 3 because the nonzero columns
     
0 0 0
 ...   ...   ... 
     
 0 ,  0 ,  0 
     
0 1 1
1 0 1
are linearly dependent.
Furthermore, we know that Ham(r, q) has M = q k = q n−r codewords, so the
sphere-packing bound
q n−r (1 + n(q − 1)) = q n−r (1 + q r − 1) = q n
is perfectly achieved.
Corollary 3.1.1 (Hamming Size): For any integer r ≥ 2, we have A2 (2r − 1, 3) =
r
22 −1−r .
42 CHAPTER 3. HAMMING CODES
• Thus A2 (3, 3) = 2, A2 (7, 3) = 16, A2 (15, 3) = 211 = 2048, and A2 (31, 3) = 226 .
Problem 3.4: Determine the number αi of coset leaders of weight i for Ham(r, 2),
for each i = 0, . . . , n.
We know that the Hamming code is perfect and has minimum distance 3. The error
vectors that can be corrected by a Hamming code are precisely those vectors of weight one
or less. These vectors fill Fqn completely, where n = 2r − 1. Consequently, the coset weights
are distributed according to

 n for 0 ≤ i ≤ 1,
αi = i

0 for i > 1.
That is, α0 = 1, α1 = n = 2r − 1, α2 = α3 = . . . = αn = 0. Note that the total number of
cosets is α0 + α1 = 2r = 2n−k and each of them contain 2k vectors, where k = n − r.
Problem 3.5: For all r ∈ N, describe how to construct from Ham(r, 2) a code of
r
length n = 2r with minimum distance d = 4 that contains M = 22 −1−r codewords.
Prove that the minimum distance of your code is 4 and that M is the maximum
number of possible codewords for these parameters.
r
Extend the Hamming code Ham(r, 2), with length n − 1 = 2r − 1, M = 2n−r = 22 −1−r ,
and distance 3 by adding a parity check to produce a code with n = 2r but still M codewords.
Since the parity check guarantees that the weight of all extended codewords is even, we know
that the distance between any two of these codewords x and y is w(x − y) = w(x) + w(y) −
2w(xy), which is even. Hence the minimum distance of the extended code, which is at least 3
and certainly no more than 4, must in fact be 4. We also know that the Hamming code is
perfect. The extended Hamming code is not perfect, but we know by Corollary 1.3.1 that
the maximum number of codewords for the parameters (n, 4) is the same as the maximum
number M of codewords for the parameters (n − 1, 3).
Chapter 4
Golay Codes
We saw in the last chapter that the linear Hamming codes are nontrivial perfect
codes.
Q. Are there any other nontrivial perfect codes?
A. Yes, two other linear perfect codes were found by Golay in 1949. In addition,
several nonlinear perfect codes are known that have the same n, M , and d
parameters as Hamming codes.
The condition for a code to be perfect is that its n, M , and d values satisfy the
sphere-packing bound
t
X n
M (q − 1)k = q n , (4.1)
k =0
k
with d = 2t + 1. Golay found three other possible integer triples (n, M, d) that do
not correspond to the parameters of a Hamming or trivial perfect code. They are
(23, 212 , 7) and (90, 278 , 5) for q = 2 and (11, 36 , 5) for q = 3. It turns out that there
do indeed exist linear binary [23, 12, 7] and ternary [11, 6, 5] codes; these are known as
Golay codes. But, as we shall soon, it is impossible for linear or nonlinear (90, 278 , 5)
codes to exist.
Problem 4.1: Show that the (n, M, d) triples (23, 212 , 7), (90, 278 , 5) for q = 2, and
(11, 36 , 5) for q = 3 satisfy the sphere-packing bound (1.1).
Remark: In view of Theorem 1.3, a convenient way of finding a binary [23, 12, 7]
Golay code is to construct first the extended Golay [24, 12, 8] code, which is just
the [23, 12, 7] Golay code augmented with a final parity check in the last position
(such that the weight of every codeword is even).
43
44 CHAPTER 4. GOLAY CODES
The extended binary Golay [24, 12, 8] code C24 can be generated by the matrix
G24 defined by
 
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0
 
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1
 
0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1
 
0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0
 
0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1
 .
0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1
 
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1
 
0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0
 
0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0
 
0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1
Remark: We can express G24 = [112 | A], where A is a 12 × 12 symmetric matrix;

that is, At = A.
Problem 4.2: Show that u·v = 0 for all rows u and v of G24 . Hint: note that the
first row of G is orthogonal to itself. Then establish that u·v = 0 when u is the
second row and v is any row of G24 . Then use the cyclic symmetry of the rows of
the matrix A0 formed by deleting the first column and first row of A.
Remark: The above exercise establishes that the rows of G24 are orthogonal to each
other. Noting that the weight of the rows of G24 is either 12 or 8, we make use of
the following result.
Definition: A linear code C is self-orthogonal if C ⊂ C ⊥ . A linear code C is self-dual

if C = C ⊥ .
Problem 4.3: Let C be a binary linear code with generator matrix G. If each row
of G is orthogonal to itself and all other rows and has weight divisible by 4, prove
that C ⊂ C ⊥ and that the weight of every codeword in C is a multiple of 4.
⊥
Remark: Since k = 12 and n − k = 12, the linear spaces C24 and C24 have the same
⊥ ⊥
dimension. Hence C24 ⊂ C24 implies C24 = C24 . This means that the parity check
matrix H24 = [A | 112 ] for C24 is also a generator matrix for C24 !
We are now ready to show that distance of C24 is 8 and, consequently, that the bi-
nary Golay [23, 12] code generated by the first 23 columns of G24 must have minimum
distance either 7 or 8. But since the third row of this reduced generator matrix is a
codeword of weight 7, we can then be sure that the minimum distance is exactly 7.
45
Theorem 4.1 (Extended Golay [24, 12] code): The [24, 12] code generated by G24 has
minimum distance 8.
Proof: We know that the weight of the code generated by G24 must be divisible
by 4. Since both G24 and H24 are generator matrices for the code, any codeword
can be expressed either as a linear combination of the rows of G24 or as a linear
combination of the rows of H24 . We now show that a codeword x ∈ C24 cannot have
weight 4. It is not possible for the all of the left-most twelve bits of x to be 0 if x
is some nontrivial linear combination of the rows of G24 . Likewise, it is not possible
for all of the right-most twelve symbols of x to be 0 if x is some nontrivial linear
combination of the rows of H24 . If exactly one of the left-most (right-most) twelve
bits of x were 1, then x would then be identical to a row of G24 (H24 ), none of which
has weight 4. The only possible codeword of weight 4 is therefore a sum of two rows
of G24 , but it is easily seen (again using the cyclic symmetry of A0 ) that no two rows
of G24 differ in only four positions. Since the weight of every codeword in C24 must be
a multiple of 4, we now know that C24 must have a minimum distance of at least 8. In
fact, since the second row of G24 is a codeword of weight 8, we see that the minimum
distance of C24 is exactly 8.
Problem 4.4: Show that the ternary Golay [11, 6] code generated by the first 11
columns of the generator matrix
 
1 0 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 0 1 0 1 2 2 1
 
0 0 1 0 0 0 1 1 0 1 2 2
G12 = 
0 0 0 1

 0 0 1 2 1 0 1 2
0 0 0 0 1 0 1 2 2 1 0 1
0 0 0 0 0 1 1 1 2 2 1 0
has minimum distance 5.

Theorem 4.2 (Nonexistence of binary (90, 278 , 5) codes): There exist no binary
(90, 278 , 5) codes.
Proof: Suppose that a binary (90, 278 , 5) code C exists. By Lemma 1.2, without
loss of generality we may assume that 0 ∈ C. Let Y be the set of vectors in F290 of
weight 3 that begin with two 1s. Since there are 88 possible positions for the third
one, |Y | = 88. From Eq. (4.1), we know that C is perfect, with d(C) = 5. Thus
each y ∈ Y is within a distance 2 from a unique codeword x. But then from the
triangle inequality,
2 = d(C) − w(y) ≤ w(x) − w(y) ≤ w(x − y) ≤ 2,
from which we see that w(x) = 5 and d(x, y) = w(x − y) = 2. This means that x
must have a 1 in every position that y does.
46 CHAPTER 4. GOLAY CODES
Let X be the set of all codewords of weight 5 that begin with two 1s. We know
that for each y ∈ Y there is a unique x ∈ X such that d(x, y) = 2. That is, there are
exactly |Y | = 88 elements in the set {(x, y) : x ∈ X, y ∈ Y, d(x, y) = 2}. But each
x ∈ X contains exactly three ones after the first two positions. Thus, for each x ∈ X
there are precisely three vectors y ∈ Y such that d(x, y) = 2. That is, 3 |X| = 88.
This is a contradiction, since |X| must be an integer.
Remark: In 1973, Tietävainen, based on work by Van Lint, proved that any non-
trivial perfect code over the field Fqn must either have the parameters ((q r − 1)/(q −
1), q n−r , 3) of a Hamming code, the parameters (23, 212 , 7) of the binary Golay code,
or the parameters (11, 36 , 5) of the ternary Golay code.
Problem 4.5: Consider the extended ternary (q = 3) Golay [12, 6, 6] code C12 gen-
erated by
 
1 0 0 0 0 0 0 1 1 1 1 1
0 1 0 0 0 0 1 0 1 2 2 1
 
0 0 1 0 0 0 1 1 0 1 2 2
G12 = 0

 0 0 1 0 0 1 2 1 0 1 2
0 0 0 0 1 0 1 2 2 1 0 1
0 0 0 0 0 1 1 1 2 2 1 0
⊥
(a) Use the fact that C12 is self-orthogonal (C12 ⊂ C12 ) to find a parity-check
matrix for C12 .
Since n − k = 12 − 6 = 6 = k, we know that the linear subspace C12 ⊥ and C
12 have the
⊥
same dimension, so C12 = C12 . Hence, G12 itself is a parity check matrix for C12 .
(b) Decode the received vector y = 010 000 010 101, assuming that at most two
errors have occurred.
The syndrome of this vector is
     
0 0 0
1 1 0
     
1 1
  =   + 2 0 .
 
1 1 0
     
1 1 0
0 1 1
Thus an error of 1 has occurred in position 7 and an error of 2 has occurred in position 6.
That is, the error vector is e = 000 002 100 000, so the transmitted vector was x = y − e =
010 001 210 101.
Chapter 5
Finite Fields
Until now we have always restricted our attention to the case where Fq is the set
Zq = {0, 1, 2, . . . , q − 1} for some prime number q. In this chapter, we review the fact
that Zq is a finite field if and only if q is prime. We then ask whether there exist finite
fields of order q when q is not a prime number. We will conclude that there exist
finite fields of order q if and only if q is an integral power pr of some prime p. Finally,
we demonstrate that although general finite fields of order q = pr may at first appear
to be somewhat complicated, they all have a very simple underlying structure.
Theorem 5.1 (Zn ): The ring Zn is a field ⇐⇒ n is prime.
Proof:
“⇒” Let Zn be a field. If n = ab, with 1 < a, b < n, then b = a−1 ab =

a−1 n = 0 (mod n), a contradiction. Hence n must be prime.
“⇐” Let n be prime. Since Zn has a unit and is commutative, we need
only verify that each element a 6= 0 has an inverse. Consider the elements
ia, for i = 1, 2, . . . , n − 1. Each of these elements must be nonzero since
neither i nor a is divisible by the prime number n. These n − 1 elements
are distinct from each other since, for i, j ∈ 1, 2, . . . , n − 1,
ia = ja ⇒ (i − j)a = 0 (mod n) ⇒ n|(i − j)a ⇒ n|(i − j) ⇒ i = j.
Thus, the n − 1 elements a, 2a, . . . , (n − 1)a must be equal to the n − 1

elements 1, 2, . . . n − 1 in some order. One of them, say ia, must be equal
to 1. That is, a has inverse i.
Definition: The order of a finite field F is the number of elements in F .
Theorem 5.2 (Subfield Isomorphic to Zp ): Every finite field has the order of a power
of a prime p and contains a subfield isomorphic to Zp .
47
48 CHAPTER 5. FINITE FIELDS
Proof: Let 1 (one) denote the (unique) multiplicative identity in F , a field of

order n. The element 1 + 1 must be in F , so label this element 2. Similarly 2 + 1 ∈ F ,
which we label by 3. We continue in this manner until the first time we encounter
an element k to which we have already assigned a label ` (F is a finite field): the
.
sum of k ones equals the sum of ` ones, with k > `. Hence the sum of p = k − `
ones must be the additive identity, 0. If p is composite, p = ab, then the product of
the elements that we have labelled a and b would be 0, contradicting the fact that
F is a field. Thus p must be prime and the set of numbers that we have labelled
{0, 1, 2, . . . , p − 1} is isomorphic to the field Zp . Now consider all subsets {x1 , . . . , xr }
of linearly independent elements of F , in the sense that
a1 x1 + a2 x2 + . . . + ar xr = 0 ⇒ a1 = a2 = . . . = 0, where ai ∈ Zp .
There must be at least one such subset having a maximal number of elements. Then,
if x is any element of F , the elements {x, x1 , . . . , xr } cannot be linearly independent,
so that x can be written as a linear combination of {x1 , . . . , xr }. Thus {x1 , . . . , xr }
forms a basis for F , so that the elements of F may be uniquely identified by all
possible values of the coefficients a1 , a2 , . . . , ar . Since there are p choices for each of
the r coefficients, there are exactly pr distinct elements in F .
Corollary 5.2.1 (Isomorphism to Zp ): Any field F with prime order p is isomorphic

to Zp .
Proof: Theorem 5.2 says that the prime p must be the power of a prime, which
can only be p itself. It also says that F contains Zp . Since the order of Zp is already p,
there are no other elements in F .
Theorem 5.3 (Prime Power Fields): There exists a field F of order n ⇐⇒ n is a

power of a prime.
Proof:
“⇒” This is implied by Theorem 5.2.

“⇐” Let p be prime and g be an irreducible polynomial of degree r in
the polynomial ring Zp [x] (for a proof of the existence of such a polyno-
mial, see van Lint [1991]). Recall that every polynomial can be written
as a polynomial multiple of g plus a residue polynomial of degree less
than r. The field Zp [x]/g, which is just the residue class polynomial ring
Zp [x] (mod g), establishes the existence of a field with exactly pr elements,
corresponding to the p possible choices for each of the r coefficients of a
polynomial of degree less than r.
49
• For example, we can construct a field with 8 = 23 elements using the polynomial
g(x) = x3 + x + 1 in Z2 [x]. Note that g is irreducible: the fact that g(c) =
c3 + c + 1 6= 0 for all c ∈ Z2 , implies that g(x) cannot have a linear factor (x − c).
Alternatively, we can establish the irreducibility of g in Z2 [x] directly: If g(x) =
(x2 + Bx + C)(x + D) = x3 + (B + D)x2 + (C + BD)x + CD, then
CD = 1 ⇒ C = D = 1
and hence
C + BD = 1 ⇒ B = 0,
which contradicts B + D = 0.
That is, if a and b are two polynomials in Z2 [x]/g, their product can be zero
(mod g) only if one of them is itself zero. Thus, Z2 [x]/g is a field with exactly
23 = 8 elements, corresponding to the 2 possible choices for each of the 3 polynomial
coefficients.
Definition: The Euler indicator or Euler totient function
.
ϕ(n) = |{m ∈ N : 1 ≤ m ≤ n, (m, n) = 1}|
is the number of positive integers less than or equal to n that are relatively prime
(share no common factors).
• ϕ(p) = p − 1 for any prime number p.
• ϕ(pr ) = pr − pr−1 for any prime number p and any r ∈ N since p, 2p, 3p, . . .,
(pr−1 − 1)p all have a factor in common with pr .
Remark: If we denote the set of integers in Zn that are not zero divisors by Z∗n , we
see that ϕ(n) = |Z∗n |.
• Here are the first 12 values of ϕ:
x 1 2 3 4 5 6 7 8 9 10 11 12
ϕ(x) 1 1 2 2 4 2 6 4 6 4 10 4
Remark: Note that
ϕ(1) + ϕ(2) + ϕ(3) + ϕ(6) = 1 + 1 + 2 + 2 = 6,
ϕ(1) + ϕ(2) + ϕ(3) + ϕ(4) + ϕ(6) + ϕ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12,

and ϕ(1) + ϕ(p) = 1 + (p − 1) = p for any prime p.
Problem 5.1: The Chinese remainder theorem implies that ϕ(mn) = ϕ(m)ϕ(n)
whenever (m, n) = 1. Use this result to prove for any n ∈ N that
X
ϕ(d) = n.
d|n
Problem 5.2: Consider the set

k
Sn = :1≤k≤n .
n
(a) How many distinct elements does Sn contain?

(b) If k and n have a common factor, reduce the fraction k/n to m/d, where d
divides n and (m, d) = 1, with 1 ≤ m ≤ d. For each d, express the number of possible
values of m in terms of the Euler ϕ function.
(c) Obtain an alternative proof of the formula in Problem 5.1 from parts (a)
and (b).
Definition: The order of a nonzero element α of a finite field is the smallest natural
number e such that αe = 1.
Theorem 5.4 (Primitive Element of a Field): The nonzero elements of any finite
field can be written as powers of a single element.
Proof: Given a finite field F of order q, let 1 ≤ e ≤ q − 1. Either there exists
no elements in F of order e or there exists at least one element α of order e. In the
latter case, α is a root of the polynomial xe − 1 in F [x]; that is, αe = 1. Hence
(αn )e = (αe )n = 1 for n = 0, 1, 2, . . .. Since α has order e, we know that each of the
roots αn for n = 1, 2, . . . , e are distinct. Since xe − 1 can have at most e zeros in F [x],
we then immediately know the factorization of the polynomial xe − 1 in F [x]:
xe − 1 = (x − 1)(x − α)(x − α2 ) . . . (x − αe−1 ).
Thus, the only possible elements of order e in F are powers αi for 1 ≤ i < e. However,
if i and e share a common factor n > 1, then (αi )e/n = 1 and the order of αi would
be less than or equal to e/n. So this leaves only the elements αi where (i, e) = 1
as possible candidates for elements of order e. Note that the e powers of α are a
subgroup (coset) of the multiplicative group G formed by the nonzero elements of F ,
so Lagrange’s Theorem implies that e must divide the order of G, that is, e|(q − 1).
Consequently, the number of elements of order e, where e divides q − 1, is either 0
or ϕ(e). If the number of elements of order e were 0 for some divisor
P e of q − 1, then
the total number of nonzero elements in F would be less than e|(q−1) ϕ(e) = q − 1,
which is a contradiction. Hence, there exist elements in F of any order e that divides
q − 1, including q − 1 itself. The distinct powers of an element of order q − 1 are just
the q − 1 nonzero elements of F .
51
Definition: An element of order q − 1 in a finite field Fq is called a primitive element.
Remark: Theorem 5.4 states that the elements of a finite field Fq can be listed in
terms of a primitive element, say α:
Fq = {0, α0 , α1 , α2 , . . . , αq−2 }.
Remark: The fact that all elements in a field Fq can be expressed as powers of a
primitive element can be exploited whenever we wish to multiply two elements
together. We can compute the product αi αj simply by determining which element
can be expressed as α raised to the power (i + j) mod(q − 1), in exactly the same
manner as one uses a table of logarithms to multiply real numbers.
Remark: A primitive element of a finite field Fpr need not be unique. In fact, we
see from the proof of Theorem 5.4 that the number of such elements is ϕ(pr − 1).
Specifically, if α is a primitive element, then the powers αi , for the ϕ(pr − 1) values
of i that are relatively prime to pr − 1, are also primitive elements.
Remark: A primitive element α of Fq satisfies the equation αq−1 = 1, so that αq = α,

and has the highest possible order (q − 1). Note that (αi )−1 = αq−1−i .
Problem 5.3: Show that every nonzero element β of a finite field satisfies β q−1 = 1
in Fq .
Remark: If α is a primitive element of Fq , then α−1 = αq−2 is also a primitive

element of Fq since (q − 2)(q − 1 − i) = i mod(q − 1).
The fact that a primitive element α satisfies αq = α leads to the following corollary
of Theorem 5.4.
Corollary 5.4.1 (Cyclic Nature of Fields): Every element β of a finite field of order
q is a root of the equation β q − β = 0.
Remark: In particular, Corollary 5.4.1 states that every element β in a finite field
Fpr is a root of some polynomial f (x) ∈ Fp [x].
Definition: Given an element β in a field Fpr , the monic polynomial m(x) in Fp [x]
of least degree with β as a root is called the minimal polynomial of β.
Theorem 5.5 (Minimal Polynomial): Let β ∈ Fpr . If f (x) ∈ Fp [x] has β as a root,
then f (x) is divisible by the minimal polynomial of β.
Proof: Let m(x) be the minimal polynomial of β. If f (β) = 0, then expressing
f (x) = q(x)m(x) + r(x) with deg r < deg m, we see that r(β) = 0. By the minimality
of deg m, we see that r(x) is identically zero.
Corollary 5.5.1 (Minimal Polynomials Divide xq − x): The minimal polynomial of
an element of a field Fq divides xq − x.
Corollary 5.5.2 (Irreducibility of Minimal Polynomial): Let m(x) be a monic poly-

nomial in Fp [x] that has β as a root. Then m(x) is the minimal polynomial
of β ⇐⇒ m(x) is irreducible in Fp [x].
Proof:
“⇒” If m(x) = a(x)b(x), where a and b are of smaller degree, then

a(β)b(β) = 0 implies that a(β) = 0 or b(β) = 0; this would contradict the
minimality of deg m. Thus m(x) is irreducible.
“⇐” Since m(β) = 0, we know from Theorem 5.5 that m(x) is divisible
by the minimal polynomial of β. But since m(x) is irreducible and monic,
the minimal polynomial must be m(x) itself.
Definition: A primitive polynomial of a field is the minimal polynomial of a primitive

element of the field.
Q. How do we find the minimal polynomial of an element αi in the field Fpr ?
A. The following theorems provide some assistance.
Theorem 5.6 (Functions of Powers): If f (x) ∈ Fp [x], then f (xp ) = [f (x)]p .
Proof: Exercise.
Corollary 5.6.1 (Root Powers): If α is a root of a polynomial f (x) ∈ Fp [x] then αp

is also a root of f (x).
Theorem 5.7 (Reciprocal Polynomials): In a finite field Fpr the following statements
hold:
(a) If α ∈ Fpr is a nonzero root of f (x) ∈ Fp [x], then α−1 is a root of the reciprocal
polynomial of f (x).
(b) a polynomial is irreducible ⇐⇒ its reciprocal polynomial is irreducible.
(c) a polynomial is a minimal polynomial of a nonzero element α ∈ Fpr ⇒ a scalar

multiple of its reciprocal polynomial is a minimal polynomial of α−1 .
(d) a polynomial is primitive ⇒ a scalar multiple of its reciprocal polynomial is

primitive.
Proof: Exercise.
Problem 5.4: Show that the pth powers of distinct elements of a field Fpr are distinct.
53
Problem 5.5: Show that the only elements a of Fpr that satisfy the property that
ap−1 = 1 in Fpr are the p − 1 nonzero elements of Fp .
Suppose we want to find the minimal polynomial m(x) of αi in Fpr . Identify the
2
set of distinct elements {αi , αip , αip , . . .}. The powers of α modulo pr − 1 in this set
form the cyclotomic coset of i. Suppose there are s distinct elements in this set. By
Corollary 5.6.1, each of these elements are distinct roots of m(x), and so the monic
polynomial
s−1
k
Y
f (x) = (x − αip )
k=0
is certainly a factor of m(x).

ipk
Notice that the pth power of every rootPs α kof f (x) is another such root. The
coefficients ak in the expansion f (x) = k=0 ak x are symmetric functions of these
roots, consisting of sums of products of the roots. When we raise these sums to the
pth power we obtain symmetric sums of the pth powers of the products of the roots.
Since the pth power of a root is another root and the coefficients ak are invariant under
root permutations, we deduce that apk = ak . It follows that each of the coefficients ak
belong to the base field Fp . That is, on expanding all of the factors of f (x), all of the
αs disappear! Hence f (x) ∈ Fp [x] and f (αi ) = 0, so by Theorem 5.5, we know also
that m(x) is a factor of f (x). Since f (x) is monic we conclude that m(x) = f (x).
Remark: Since the degree of the minimal polynomial m(x) of αi equals the number
of elements s in the cyclotomic coset of αi , we can sometimes use the previous
theorems to help us quickly determine m(x) without having actually to perform
the above product. Note that, since pr = 1 mod(pr − 1), minimal polynomials
in Fpr have degree s ≤ r.
Problem 5.6: Show that the elements generated by powers belonging to a particular
cyclotomic coset share the same minimal polynomial and order.
Remark: Every primitive polynomial of Fpr has degree r and each of its roots is
a primitive element of Fpr . This follows immediately from the distinctness of the
2 r−1 r
elements α, αp αp , . . ., αp for a primitive element α of Fpr , noting that αp = α.
• We now find the minimal polynomial for each of the 16 elements of the field F24 =
F2 [x]/(x4 + x3 + 1). It is straightforward to check that the polynomial x is a
primitive element of the field (see Table 5.1). Since x is a root of the irreducible
polynomial x4 + x3 + 1 in F2 [x]/(x4 + x3 + 1), we know from Corollary 5.5.2 that
x4 + x3 + 1 is the minimal polynomial of x and hence is a primitive polynomial
of F16 . The cyclotomic cosets consist of powers i2k (mod 15) of each element αi :
{1, 2, 4, 8},
{3, 6, 12, 9},

{5, 10},
{7, 14, 13, 11},
{0}.
The first cyclotomic coset corresponds to the primitive element α = x, for which
the minimal polynomial is x4 + x3 + 1. This is also the minimal polynomial for the
other powers of α in the cyclotomic coset containing 1, namely α2 , α4 , and α8 .
The reciprocal polynomial of x4 +x3 +1 is x4 +x+1; this is the minimal polynomial

of the inverse elements α−i = α15−i for i = 1, 2, 4, 8, that is, for α14 , α13 , α11 , and α7 .
We see that these are just the elements corresponding to the second last coset.
We can also easily find the minimal polynomial of α3 , α6 , α12 , and α9 . Since
α15 = 1, we observe that α3 satisfies the equation x5 − 1 = 0. We can factorize
x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1) and since α3 6= 1, we know that α3 must be a
root of the remaining factor, x4 + x3 + x2 + x + 1. Furthermore, since the cyclotomic
coset corresponding to α3 contains 4 elements, the minimal polynomial must have
degree 4. So x4 + x3 + x2 + x + 1 is in fact the minimal polynomial of α3 , α6 , α9 , and
α12 (hence we have indirectly proven that x4 + x3 + x2 + x + 1 is irreducible in F2 [x]).
Likewise, since the minimal polynomial of x5 must be a factor of x3 − 1 = (x −
1)(x2 + x + 1) with degree 2, we see that the minimal polynomial for these elements
is x2 + x + 1.
Finally, the minimal polynomial of the multiplicative unit α0 = 1 is just the first
degree polynomial x + 1. The minimal polynomial of 0 is x.
These results are summarized in Table 5.1.
Remark: The cyclotomic cosets containing powers that are relatively prime to pr − 1
contain the ϕ(pr − 1) primitive elements of Fpr ; their minimal polynomials are
primitive and have degree r. Note that x4 + x3 + 1 and x4 + x + 1 are primitive
polynomials of F2 [x]/(x4 + x3 + 1) and their roots comprise the ϕ(15) = ϕ(5)ϕ(3) =
4 · 2 = 8 primitive elements of Fpr . Even though the minimal polynomial of the
element α3 also has degree r = 4, it is not a primitive polynomial, since (α3 )5 = 1.
Remark: There is another interpretation of finite fields, as demonstrated by the

following example. Consider the field F4 = F2 [x]/(x2 + x + 1), which contains the
elements {0, 1, x, x + 1}. Since the primitive element α = x satisfies the equation
x2 + x + 1 = 0, we could, using the quadratic formula, think of α as the complex
number √ √
−1 + 1 − 4 1 3
α= =− +i .
2 2 2
The other root to the equation x2 + x + 1 = 0 is the complex conjugate α of α.
That is, x2 + x + 1 = (x − α)(x − α). From this it follows that 1 = αα = |α|2
55
Element Polynomial Order Minimal Polynomial

α0 1 1 x+1
α1 α 15 x4 + x3 + 1
α2 α2 15 x4 + x3 + 1
α3 α3 5 x4 + x3 + x2 + x + 1
α4 α3 + 1 15 x4 + x3 + 1
α5 α3 + α + 1 3 x2 + x + 1
α6 α3 + α2 + α + 1 5 x4 + x 3 + x2 + x + 1
α7 α2 + α + 1 15 x4 + x + 1
α8 α3 + α2 + α 15 x4 + x3 + 1
α9 α2 + 1 5 x4 + x3 + x2 + x + 1
α10 α3 + α 3 x2 + x + 1
α11 α3 + α2 + 1 15 x4 + x + 1
α12 α+1 5 x4 + x3 + x2 + x + 1
α13 α2 + α 15 x4 + x + 1
α14 α3 + α2 15 x4 + x + 1
Table 5.1: Nonzero elements of the field F2 [x]/(x4 + x3 + 1) expressed in terms of the
primitive element α = x.
and hence α = eiθ = cos θ + i sin θ for some real number θ. In fact, we see that
θ = 2π/3. Thus α3 = e3θi = e2πi = 1. In this way, we have constructed a number
α that is a primitive third root of unity, which is precisely what we mean when we
say that α is a primitive element of F4 . The field F4 may be thought of either as
the set {0, 1, x, x + 1} or as the set {0, 1, e2πi/3 , e−2πi/3 }, as illustrated in Fig. 5.1.
Similarly, the field F3 = {0, 1, 2} is isomorphic to {0, 1, −1} and F5 = {0, 1, 2, 3, 4}
is isomorphic to {0, 1, i, −1, −i}.
Figure 5.1: A representation of the field F4 in the complex plane.

Chapter 6
Cyclic Codes
Cyclic codes are an important class of linear codes for which the encoding and de-
coding can be efficiently implemented using shift registers. In the binary case, shift
registers are built out of two-state storage elements known as flip-flops and arith-
metic devices called binary adders that output the sum of their two binary inputs,
modulo 2.
Many common linear codes, including Hamming and Golay codes, have an equiv-
alent cyclic representation.
Definition: A linear code C is cyclic if
a0 a1 . . . an−1 ∈ C ⇒ an−1 a0 a1 . . . an−2 ∈ C.
Remark: If x is a codeword of a cyclic code C, then all cyclic shifts of x also belong
to C.
• The binary linear code (000, 101, 011, 110) is cyclic.
• The (7, 16, 3) perfect code in Chapter 1, which we now know is equivalent to
Ham(3, 2), is cyclic.
• The binary linear code (0000, 1001, 0110, 1111) is not cyclic. However, upon inter-
changing the third and fourth positions, we note that it is equivalent to the linear
code (0000, 1010, 0101, 1111), which is cyclic.
It is convenient to identify a codeword a0 a1 . . . an−1 in a cyclic code C with the
polynomial
c(x) = a0 + a1 x + a2 x2 + . . . + an−1 xn−1 .
Then an−1 a0 a1 . . . an−2 corresponds to the polynomial
an−1 + a0 x + a1 x2 + . . . + an−2 xn−1 = xc(x) (mod xn − 1),
56
57
since xn = 1 (mod xn − 1). Thus, a linear code C is cyclic iff
c(x) ∈ C ⇒ xc(x) (mod xn − 1) ∈ C.
That is, multiplication by x (modulo the polynomial xn − 1) corresponds to a cyclic

shift.
Definition: The polynomial ring Fq [x ] is the set of all polynomials P (x) with coeffi-
cients in Fq .
.
Definition: The residue class ring Rqn = Fq [x]/(xn − 1) is the set of all polynomial
remainders obtained by long division of polynomials in Fq [x] by xn − 1. That is,
Rqn is the set of all polynomials of degree less than n.
Remark: A cyclic code in Fqn can be thought of as a particular subset of the residue
class polynomial ring Rqn . In fact, the following theorem shows that a cyclic code C
is an ideal of Rqn .
Theorem 6.1 (Cyclic Codes are Ideals): A linear code C in Rqn is cyclic ⇐⇒
c(x) ∈ C, r(x) ∈ Rqn ⇒ r(x)c(x) ∈ C.
Proof: Suppose C is a cyclic code in Rqn . We know that multiplication of a

codeword c(x) in C by x corresponds to a cyclic shift of its coefficients, and since C is
linear, we know that c(x) ∈ C ⇒ αc(x) ∈ C for all α ∈ Fq . We thus see by induction
that
c(x) ∈ C ⇒ r(x)c(x) ∈ C ∀r(x) ∈ Rqn , (6.1)
where the multiplication is performed modulo xn − 1. Conversely, suppose that C
satisfies Eq. (6.1). Taking r(x) = x shows that C is cyclic.
Definition: The principal ideal
hg(x)i = {r(x)g(x) : r(x) ∈ Rqn }
of Rqn is the cyclic code generated by the polynomial g(x).
Problem 6.1: Verify that hg(x)i is an ideal.
Remark: The next theorem states that every ideal in Rqn is a principal ideal (i.e. Rqn
is a Principal Ideal Domain).
58 CHAPTER 6. CYCLIC CODES
Definition: A polynomial is monic if its highest-degree coefficient is 1.

Theorem 6.2 (Generator Polynomial): Let C be a nonzero q-ary cyclic code in Rqn .
Then
(i) there exists a unique monic polynomial g(x) of smallest degree in C;
(ii) C = hg(x)i;
(iii) g(x) is a factor of xn − 1 in Fq [x].
Proof:
(i) If g(x) and h(x) are both monic polynomials in C of smallest degree, then
g(x) − h(x) is a polynomial in C of smaller degree. If g(x) − h(x) 6= 0, a certain
scalar multiple of g(x) − h(x) would be a monic polynomial in C of degree
smaller than deg g, which is a contradiction. Hence g(x) = h(x).
(ii) Theorem 6.1 shows that hg(x)i ⊂ C, so it only remains to show that C ⊂ hg(x)i.
Suppose c(x) ∈ C. Using long division, we can express c(x) = q(x)g(x) + r(x),
where deg r < deg g. But since c(x) and q(x)g(x) are both in the cyclic code C,
we know by the linearity of C that r(x) = c(x) − q(x)g(x) is also in C. Hence
r(x) = 0 (otherwise a scalar multiple of r(x) would be a monic polynomial in C
of degree smaller than deg g). That is, c(x) ∈ hg(x)i.
(iii) By long division, we may express xn − 1 = q(x)g(x) + r(x), where deg r < deg g.
But then r(x) = −q(x)g(x) (mod xn − 1) implies that r(x) ∈ hg(x)i. By the
minimality of deg g, we see that r(x) = 0; that is, xn − 1 is a multiple of g(x).
Definition: The monic polynomial of least degree in Theorem 6.2 is called the
generator polynomial of C.
Theorem 6.3 (Lowest Generator Polynomial Coefficient): Let g(x) = g0 +g1 x+. . .+
gr xr be the generator polynomial of a cyclic code. Then g0 6= 0.
Proof: Suppose g0 = 0. Then xn−1 g(x) = x−1 g(x) is a codeword of degree r − 1,
contradicting the minimality of deg g.
Theorem 6.4 (Cyclic Generator Matrix): A cyclic code with generator polynomial
g(x) = g0 + g1 x + . . . + gr xr
has dimension n − r and generator matrix
g0 g1 g2 . . . gr 0 0 ... 0
 
 0 g0 g1 g2 . . . gr 0 ... 0 
 
G= 0 0 g0 g1 g2 ... gr ... 0 .
 . .. .. .. .. .. .. 
 .. . . . . . . 
0 0 ... 0 g0 g1 g2 ... gr
59
Proof: Let c(x) be a codeword in a cyclic code C with generator g(x). From
Theorem 6.2, we know that
c(x) = q(x)g(x)
for some polynomial q(x). Note that deg q < n − r since deg c < n. That is,
c(x) = q0 + q1 x + . . . + qn−r−1 xn−r−1 g(x) = q0 g(x)+q1 xg(x)+. . .+qn−r−1 xn−r−1 g(x),

which is a linear combination of the n − r rows g(x), xg(x), x2 g(x), . . . , xn−r−1 g(x)
of G. The diagonal of nonzero g0 s next to a lower-triangular zero submatrix ensures
that the rows of G are linearly independent. Thus, the span of the rows of G is the
n − r dimensional code C.
Remark: Together, Theorems 6.1 and 6.2 say that an [n, k] code is cyclic ⇐⇒ it
is generated by a factor of xn − 1. The following lemma is useful in finding these
factors.
Lemma 6.1 (Linear Factors): A polynomial c(x) has a linear factor x − a ⇐⇒
c(a) = 0.
Proof: Exercise.
Definition: A polynomial is said to be irreducible in Fq [x] if it cannot be factored
into polynomials of smaller degree.
Lemma 6.2 (Irreducible 2nd or 3rd Degree Polynomials): A polynomial c(x) in Fq [x]
of degree 2 or 3 is irreducible ⇐⇒ c(a) 6= 0 for all a ∈ Fq .
Proof: c(x) can be factored into polynomials of smaller degree ⇐⇒ it has at
least one linear factor (x − a) ⇐⇒ c(a) = 0, by Lemma 6.1.
• Suppose we wish to find all ternary cyclic codes of length n = 4. The generators
for such codes must be factors of x4 − 1 in the ring F3 [x]. Since 1 is a root of the
equation x4 − 1 we know that (x − 1) is a factor and hence
(x4 − 1) = (x − 1)(x3 + x2 + x + 1)
By Lemma 6.2, the factor x3 + x2 + x + 1 is not irreducible because it has a linear
root at a = 2 = −1 in F3 . Using long division, we obtain
(x4 − 1) = (x − 1)(x + 1)(x2 + 1).
Since any combination of these three irreducible factors can be used to construct
a generator polynomial g(x) for a cyclic code, there are a total of 23 = 8 ternary
cyclic codes of length 4, as illustrated in Table 6.1. Upon examining the weights of
the rows of the possible generator matrices, we see that the generated codes either
have minimum distance less than or equal to 2 or else equal to 4. Hence, it is not
possible to have a cyclic code of length 4 and minimum distance 3. In particular,
Ham(2, 3), for which n = (32 − 1)/(3 − 1) = 4, cannot be cyclic. Thus, not all
Hamming codes have a cyclic representation.
g(x) G
 
1 0 0 0
0 1 0 0
1 
0

0 1 0
0 0 0 1
 
−1 1 0 0
x−1  0 −1 1 0 
0 0 −1 1
 
1 1 0 0
x+1 0 1 1 0
0 0 1 1

2 1 0 1 0
x +1
0 1 0 1

2 −1 0 1 0
(x − 1)(x + 1) = x − 1
0 −1 0 1
(x − 1)(x2 + 1) = x3 − x2 + x − 1 [ −1 1 −1 1 ]
(x + 1)(x2 + 1) = x3 + x2 + x + 1 [1 1 1 1]
x4 − 1 = 0 [0 0 0 0]
Table 6.1: Generator polynomial g(x) and corresponding generator matrix G for all
possible ternary cyclic codes of length 4.
61
An easy way to find the parity check matrix for a cyclic [n, k] code (without
requiring that we first put G given by Theorem 6.4 in standard form) is to first
construct the check polynomial h(x) of C from its generator polynomial g(x), where
h(x) satisfies
xn − 1 = g(x)h(x)
in Fq [x]. Since g is monic and has degree n − k, we see that h is monic and has degree
k.
Theorem 6.5 (Cyclic Check Polynomial): An element c(x) of Rqn is a codeword of

the cyclic code with check polynomial h ⇐⇒ c(x)h(x) = 0 in Rqn .
Proof:
“⇒” If c(x) is a codeword, then in Rqn we have
c(x) = a(x)g(x) ⇒ c(x)h(x) = a(x)g(x)h(x) = a(x)(xn −1) = a(x)0 (mod xn −1) = 0.
“⇐” We can express any polynomial c(x) in Rqn as c(x) = q(x)g(x) + r(x)
where deg r < deg g = n − k. If c(x)h(x) = 0 then
r(x)h(x) = c(x)h(x) − q(x)g(x)h(x) = 0 (mod xn − 1).
But deg r(x)h(x) < n − k + k = n, so r(x)h(x) = 0 in Fq [x], not just

in Rqn . If r(x) 6= 0, consider its highest degree coefficient a 6= 0. Then
since h is monic, the coefficient of the highest degree term of the product
r(x)h(x) is a = a · 1 = 0, which is a contradiction. Thus r(x) = 0 and so
c(x) is a codeword: c(x) = q(x)g(x) ∈ hg(x)i.
Theorem 6.6 (Cyclic Parity Check Matrix): A cyclic code with check polynomial
h(x) = h0 + h1 x + . . . + hk xk
has dimension k and parity check matrix
hk hk−1 hk−2 ... h0 0 0 ... 0

 
 0 hk hk−1 hk−2 ... h0 0 ... 0 
 
H= 0 0 hk hk−1 hk−2 ... h0 ... 0 .
 . .. ... ... ... ... .. 
 .. . . 
0 0 ... 0 hk hk−1 hk−2 ... h0
Proof: Since the degree of the generator polynomial g is r = n−k, by Theorem 6.4,
the dimension of the code must be k. From Theorem 6.5, we know that a codeword
c(x) = c0 +c1 x+. . .+cn−1 xn−1 must satisfy c(x)h(x) = 0. In particular, the coefficients
xk , xk+1 , . . . , xn−1 of the product c(x)h(x) must be zero; for ` = k, k + 1, . . . , n − 1 we

then have X
0= ci hj .
i+j=`
But then, since each of these equations is one of the n − k rows of the matrix equation
hk hk−1 hk−2 ... h0 0 0 ... 0 c0

    
0
 0 hk hk−1 hk−2 ... h0 0 . . . 0  c1   0 
    
 0 0 hk hk−1 hk−2 ... h0 . . . 0  c2  =  0 ,
 . .. .. .. .. .. .  .   . 
 .. . . . . . ..  ..   .. 
0 0 ... 0 hk hk−1 hk−2 . . . h0 cn−1 0
the codewords are orthogonal to all cyclic shifts of the vector hk hk−1 hk−2 . . . h0 00 . . . 0.
The codewords are thus orthogonal to all linear combinations of the rows of H. This
means that C ⊥ contains the span of the rows of H. But hk = 1, so we see that H
has rank n − k and hence generates exactly the linear subspace C ⊥ . That is, H is a
parity check matrix for the code with check polynomial h(x).
Definition: The reciprocal polynomial h(x) of a polynomial
h(x) = h0 + h1 x + . . . + hk xk
is obtained by reversing the order of its coefficients:

.
h(x) = xk h(x−1 ) = h0 xk + h1 xk−1 + . . . + hk = hk + hk−1 x + . . . + h0 xk .
Remark: Since
h(x)g(x) = h(x)xn−k g(x−1 ) = xn h(x−1 )g(x−1 ) = xn [(x−1 )n − 1] = 1 − xn ,
we see that h(x) is a factor of xn − 1. In view of Theorems 6.1, 6.2, and 6.6, this
says that C ⊥ is itself a cyclic code, with (monic) generator h−1
0 h(x).
We are now able to show that all binary Hamming codes have an equivalent cyclic
representation.
Theorem 6.7 (Cyclic Binary Hamming Codes): The binary Hamming code Ham(r, 2)
is equivalent to a cyclic code.
Proof: Let p(x) be an irreducible polynomial of degree r in F2 [x]. By Theorem 5.3

F2 [x]/p(x) is a field of order 2r , and by Theorem 5.4 we know that F2 [x]/p(x) can be
r
expressed as the set of distinct elements {0, α0 , α1 , α2 , . . . , α2 −2 } for some primitive
63
element α. We associate each element a0 + a1 x + a2 x2 + . . . + ar−1 xr−1 ∈ F2 [x]/p(x)

with the column vector
a0
 
 a1 
 . .
 .. 
ar−1
Let n = 2r − 1. The r × n matrix
H = [ 1 α α2 . . . αn−1 ]
is seen to be the parity check matrix for C = Ham(r, 2) since its columns are precisely
the distinct nonzero vectors of F2r . A codeword c(x) = c0 + c1 x + . . . + cn−1 xn−1 in
this code must then satisfy the vector equation c0 + c1 α1 + c1 α2 + . . . + cn−1 αn−1 = 0,
so that
C = {c(x) ∈ R2n : c(α) = 0 in F2 [x]/p(x)}.
If c(x) ∈ C and r(x) ∈ R2n , we have r(α)c(α) = r(α)0 = 0 in F2 [x]/p(x), noting that
αn = 1, so r(x)c(x) is also an element of C. Theorem 6.1 then implies that C is
cyclic.
• The irreducible polynomial x3 + x + 1 in F2 [x] can be used to generate the field
F8 = F2 [x]/(x3 + x + 1) with 23 = 8 elements. Note that F8 has x as a primitive
element since all polynomials in F2 [x] of degree less than 3 can be expressed as
powers of x:
F8 = {0, 1, x, x2 , x3 = x + 1, x4 = x2 + x, x5 = x2 + x + 1, x6 = x2 + 1}.
Note that x7 = x3 + x = 1; that is, the primitive element has order 7 = 8 − 1. The
primitive element x is a root of the primitive polynomial x3 + x + 1 in F8 .
A parity check matrix for a cyclic version of the Hamming code Ham(3, 2) is thus
 
1 0 0 1 0 1 1
H =  0 1 0 1 1 1 0 .
0 0 1 0 1 1 1
Q. What is the generator polynomial for Ham(r, 2)?
A. The close parallel between Theorem 6.2 and Theorem 5.5 when n = pr −1 gives us
a clue: on comparing these results, we see from Theorem 6.4 that any minimal
polynomial of a primitive element β of Fpr is a generator polynomial for a cyclic
code in Fpr (as we saw in Chapter 5, β is a root of xn −1 = 0). In particular, the
following corollary to Theorem 6.7 establishes that Ham(r, 2) can be generated
by any primitive polynomial of F2r , which is just a monic irreducible polynomial
in F2 [x] having a primitive element as a root.
Corollary 6.7.1 (Binary Hamming Generator Polynomials): Any primitive polyno-

mial of F2r is a generator polynomial for a cyclic Hamming code Ham(r, 2).
Proof: Let α be a primitive element of F2r . Its minimal polynomial p(x) is a

primitive polynomial of F2r . From the proof of Theorem 6.7, we see that Ham(r, 2)
consists precisely of those polynomials c(x) for which c(α) = 0, for example, p(x)
itself. By Theorem 5.5, any such polynomial must be a multiple of p(x). That
is, Ham(r, 2) ⊂ hp(x)i. Moreover, Theorem 6.1 implies that every multiple of the
codeword p(x) belongs to the cyclic code Ham(r, 2). Hence Ham(r, 2) = hp(x)i.
• Consider the irreducible polynomial p(x) = x3 + x + 1 in F2 [x]. Since x is a

primitive element of F2 [x]/p(x) and p(x) = 0 mod(x3 + x + 1), we know that p(x)
is a primitive polynomial of F23 = F2 [x]/p(x) and hence Ham(3, 2) = hp(x)i. From
Theorem 6.4, we can then immediately write down a generator matrix for a cyclic
Ham(3, 2) code:  
1 1 0 1 0 0 0
0 1 1 0 1 0 0
 0 0 1 1 0 1 0 .
 
0 0 0 1 1 0 1
Chapter 7
BCH Codes
For noisy transmission lines, Hamming codes are of limited use because they cannot
correct more than one error. In this chapter, we discuss a class of important and
widely used cyclic codes that can correct multiple errors, developed by R. C. Bose
and D. K. Ray-Chaudhuri (1960) and independently by A. Hocquenghem (1959),
known as Bose–Chaudhuri–Hocquenghem (BCH) codes.
Definition: Let α be an element of order n in a finite field Fqs . A BCH code of
length n and design distance d is a cyclic code generated by the product of the
distinct minimal polynomials in Fq [x] of the elements α, α2 , . . . , αd−1 .
Remark: Often we take α to be a primitive element of Fqs , so that n = q s − 1. The

resulting BCH code is known as a primitive BCH code. However, it is possible to
construct BCH codes over Fqs of length n, where n is any factor of q s − 1.
Remark: We will establish that a BCH code of odd design distance d has a minimum
distance of at least d, by showing that such a code can correct (d − 1)/2 errors.
To encode
Pk−1 the message word a0 a1 . . . ak−1 , we represent it by the polynomial
i
f (x) = i=0 ai x and form its product with the generator polynomial g(x), to obtain
the codeword c(x) = f (x)g(x).
• For the primitive element α = x of the field F24 = F2 [x]/(x4 +x+1), we can construct
a [15, 7] code that can correct two errors, by finding a generator polynomial g(x)
that has roots at α, α2 , a3 , and α4 . Such a generator can be created from the
product of the minimal polynomials m1 (x) = x4 + x + 1 of α and m3 (x) = x4 +
x3 + x2 + x + 1 of α3 :
g(x) = m1 (x)m3 (x) = (x4 + x + 1)(x4 + x3 + x2 + x + 1) = x8 + x7 + x6 + x4 + 1.
In fact, g(x) has even more roots than prescribed, namely at α, α2 , α4 , α8 , α3 , α6 ,
α12 , and α9 . Once we have shown that this code can correct two errors, we will
know that its minimum distance is exactly 5 since the codeword g(x) has weight 5.
65
66 CHAPTER 7. BCH CODES
Remark: In the binary case q = 2, the generator of a BCH code is just the product
of the distinct minimal polynomials of the odd powers, from 1 to d − 1, of the
primitive element.
Problem 7.1: Show that a polynomial c(x) belongs to a BCH code with design
distance d ⇐⇒ c(α) = c(α2 ) = . . . = c(αd−1 ) = 0.
We now describe the decoding procedure for BCH codes. To keep the notation
simple we begin by illustrating the procedure first for the binary case, where q = 2.
Suppose that y(x) is received rather than c(x) and that t errors have occurred. Then
the error polynomial e(x) = y(x) − c(x) can be written as e(x) = x`1 + x`2 + . . . + x`t
for some unknown powers `1 , `2 , . . . , `t . We then compute the syndrome S1 by
substituting α into y(x),
.
S1 = y(α) = c(α) + e(α) = e(α) = e1 + . . . + et ,
.
where ei = α`i for i = 1, 2, . . . , t. Likewise, we evaluate
.
S2 = y(α2 ) = c(α2 ) + e(α2 ) = e(α2 ) = e21 + . . . + e2t ,
.
S3 = y(α3 ) = c(α3 ) + e(α3 ) = e(α3 ) = e31 + . . . + e3t ,
...
.
Sd−1 = y(αd−1 ) = c(αd−1 ) + e(αd−1 ) = e(αd−1 ) = e1d−1 + . . . + ed−1
t .
The decoding problem now amounts to determining if there is a value of t and choices
of field elements e1 , e2 , . . . , et consistent with the above equations. If a solution
exists, from a table of the elements of Fqs , one would then like to determine the
.
corresponding powers `1 , `2 , . . . , `t such that ei = α`i . These powers tell us directly
which bits we need to toggle. To find a possible solution to the above equations, the
following definition will be helpful.
Definition: The error locator polynomial is

.
σ(x) = (e1 x − 1)(e2 x − 1) . . . (et x − 1) = bt xt + bt−1 xt−1 + . . . + b1 x + 1.
Notice that the roots of σ(x) are just the inverses of ei , i = 1, 2, . . . , t.
To understand how the above syndrome equations are solved, it will be helpful to
first discuss the case where d = 5 and t ≤ 2 errors have occurred. We define ei = 0
for i > t and write
S1 = e1 + e2 ,
S2 = e21 + e22 ,
67
S3 = e31 + e32 ,
S4 = e41 + e42 .
The error locator polynomial is σ(x) = b2 x2 +b1 x+1. Since σ(e−1
i ) = 0 for i = 1, 2
we know that
0 = e31 σ(e−1 3 −2 −1 2 3
1 ) = e1 (b2 e1 + b1 e1 + 1) = b2 e1 + b1 e1 + e1
and
0 = e32 σ(e−1 2 3
2 ) = b2 e2 + b1 e2 + e2 .
On adding these equations, we obtain
0 = b2 (e1 + e2 ) + b1 (e21 + e22 ) + (e31 + e32 ),
i.e.
S1 b2 + S2 b1 = −S3 .
If for each i we had multiplied σ(e−1 4 3
i ) = 0 by ei instead of ei and added the resulting
equations, we would have obtained
S2 b2 + S3 b1 = −S4 .
To find b1 and b2 , we only need to solve the system of equations

S1 S2 b2 S
=− 3 (7.1)
S2 S3 b1 S4
(Of course, in the binary case, the minus sign can be omitted.) If the coefficient
matrix in Eq. (7.1) has rank 0, then S1 = S2 = S3 = S4 = 0 and hence e1 + e2 = 0,
so that e1 = e2 . This would imply that `1 = `2 , in which case e(x) = 0; that is, no
error has occurred. That is, the system of equations will have rank 0 ⇐⇒ no errors
have occurred.
Suppose that the coefficient matrix has rank 1. Since q = 2, we know that S2 = S12 .
Note that S1 6= 0, for otherwise the first equation would imply that S3 = 0 and the
rank of the coefficient matrix would be 0. Since the determinant S1 S3 − S22 = 0, we
deduce S3 = S13 . But
e31 + e32 = (e1 + e2 )3 ⇒ 0 = 3e1 e2 (e1 + e2 ) = 3e1 e2 S1 .
This implies that e2 = 0 (only one error has occurred) and that S1 = e1 = α`1 .
Conversely, if only one error has occurred, then S3 = S13 6= 0 and the coefficient
matrix of Eq. (7.1) will have rank 1. Using a power table for F24 , we simply look
up the exponent `1 such that α`1 = S1 and then toggle bit `1 of y(x) to obtain the
transmitted codeword c(x).
Finally, if the rank of the coefficient matrix is 2, we can solve for the coefficients b1
and b2 . If two errors have occurred, the error locator polynomial σ(x) = b2 x2 +b1 x+1
must have two roots in F24 , which we can determine by trial and error. The powers
of α associated with the inverses of these roots identify the two bit positions in which
errors have occurred.
• Let us demonstrate this decoding scheme for the [15, 7] BCH code generated by
the polynomial g(x) = x8 + x7 + x6 + x4 + 1. Given the message word 110 0000,
the transmitted codeword is 110 011 100 100 000, i.e. c(x) = (1 + x) g(x) =
x9 + x6 + x5 + x4 + x + 1. Suppose that two errors have occurred, so that the
received vector is 110 010 101 100 000, that is, y(x) = x9 + x8 + x6 + x4 + x + 1.
Consulting the power table for F2 [x]/(x4 + x + 1), we see that the syndromes are
S1 = y(α) = α9 + α8 + α6 + α4 + α + 1
= (α3 + α) + (α2 + 1) + (α3 + α2 ) + (α + 1) + α + 1 = α + 1 = α4 ,
S2 = S12 = α8 ,
S3 = y(α3 ) = α27 + α24 + α18 + α12 + α3 + 1
= α12 + α9 + α3 + α12 + α3 + 1 = α9 + 1 = α3 + α + 1 = α7 ,
S4 = S22 = α16 = α.
Since S1 6= 0 and S1 S3 −S22 = S1 (S3 −S13 ) = S1 (α7 −α12 ) 6= 0, the system of equations
S1 b2 + S2 b1 = S3 ⇒ α4 b2 + α8 b1 = α7 ,
S2 b2 + S3 b1 = S4 ⇒ α8 b2 + α7 b1 = α,
has rank 2. Upon adding α4 times the first equation to the second equation, we see
that
(α12 + α7 )b1 = α11 + α.
Thus, b1 = α−2 α6 = α4 and hence b2 = α−4 (α7 + α8 α4 ) = α−4 α2 = α13 . Thus, the
error polynomial is
σ(x) = α13 x2 + α4 x + 1 = (e1 x − 1)(e2 x − 1)
We determine the roots of this equation by trial and error, That is, we search through
the field until we find an i such that α2i−2 + αi+4 = 1. Incrementing from i = 0, the
first such i we find is i = 7, so one root is α7 . The inverse, say e1 , of this root
is α8 . Since the product e1 e2 = b2 = α13 , we immediately see that e2 = α5 . That is,
the two errors are in the fifth and eighth positions, so we decode the received vector
110 010 101 100 000 as the codeword 110 011 100 100 000. Upon division of the
associated polynomial x9 + x6 + x5 + x4 + x + 1 by g(x) = x8 + x7 + x6 + x4 + 1 we
obtain x + 1, which corresponds to the original message, 110 0000.
• In the previous example, if instead the received vector was 110 010 100 100 000,
that is, y(x) = x9 + x6 + x4 + x + 1, the syndromes would be
S1 = y(α) = α9 + α6 + α4 + α + 1
= (α3 + α) + (α3 + α2 ) + (α + 1) + α + 1 = α2 + α = α5 ,
S2 = S12 = α10 ,
S3 = y(α3 ) = α27 + α18 + α12 + α3 + 1
= α12 + α3 + α12 + α3 + 1 = 1,
S4 = S22 = α20 = α5 .
69
Since S3 = S13 6= 0, we know that only one error has occurred. In fact, S1 = α5 ,
so the error must be in the fifth position; one again we see that the transmitted
codeword was 110 011 100 100 000.
In general, decoding requires that we solve the nonlinear system of d−1 syndrome
equations
Si = y(αi ) = ei1 + . . . + eit , i = 1, . . . , d − 1 (7.2)
for the value of t and the errors {ej : j = 1, . . . , t}. Here t ≤ (d − 1)/2 is the actual
number of errors that have occurred, so that each of the values ej for j = 1, . . . , t are
nonzero and distinct.
A straightforward generalization of the t = 2 decoding scheme leads to the t
equations:
0 = et+1
i σ(e−1 2 t t+1
i ) = bt ei + bt−1 ei + . . . + b1 ei + ei ,
0 = et+2
i σ(e−1 2 3 t+1
i ) = bt ei + bt−1 ei + . . . + b1 ei + et+2
i ,
...
−1 t+1
0 = e2t t
i σ(ei ) = bt ei + bt−1 ei + . . . + b1 e2t−1
i + e2t
i .
On summing each of these equations over i, we obtain a linear system of equations

for the values b1 , b2 , . . . , bt in terms of the 2t ≤ d − 1 syndromes S1 , S2 , . . . , S2t :
S1 S2 ... St bt St+1
    
 S2 S3 ... St+1  bt−1  S 
 .  = − t+2
 ... . (7.3)
 . .. ..  
 .. . .  .. 
St St+1 . . . S2t−1 b1 S2t
Problem 7.2: Show that we may rewrite the coefficient matrix in Eq. (7.3) as
M = V DV t ,
where V is the Vandermonde matrix

1 1 ... 1
 
 e1 e2 ... et 
 2
e22 e2t

V = e ...
 .1

 .. .. .. 
. . 
et−1
1 et−1
2 . . . et−1
t
and D = diag(e1 , e2 , . . . , et ) is a diagonal matrix with components dii = ei .

Remark: The matrix D is nonsingular ⇐⇒ each of its eigenvalues ej , j = 1, . . . , t are

nonzero. Also, the following theorem establishes that the matrix V is nonsingular
⇐⇒ the values ej are distinct.
Theorem 7.1 (Vandermonde Determinants): For t ≥ 2 the t×t Vandermonde matrix
1 1 ... 1
 
 e1 e2 . . . et 
 2
e22 . . . e2t 

V = e
 .1 .. .. 
 .. . . 
et−1
1 et−1
2 ... et−1
t
t
Y
has determinant (ei − ej ).
i,j=1
i>j
Proof: When t = 2 we see that det V = e2 − e1 . For t > 2, suppose that all
(t − 1)×(t − 1) Vandermonde matrices have determinant
t−1
Y t−1 Y
Y i−1
(ei − ej ) = (ei − ej ).
i,j=1 i=1 j=1
i>j
By subtracting et times row i − 1 from row i, for i = t, t − 1, . . . , 2, we can rewrite

the determinant of any t×t Vandermonde matrix as
1 1 ... 1 1

e1 − et e2 − et ... et−1 − et 0

e1 (e1 − et ) e2 (e2 − et ) . . . et−1 (et−1 − et ) 0

.. .. .. ..

. . . .
et−2 (e − e ) et−2 (e − e ) . . . et−2 (e − e ) 0
1 1 t 2 2 t t−1 t−1 t
e1 − et e2 − et ... et−1 − et

e1 (e1 − et ) e2 (e2 − et ) . . . et−1 (et−1 − et )

t−1
= (−1) .. .. ..
. . .

et−2 (e − e ) et−2 (e − e ) . . . et−2 (e − e )
1 1 t 2 2 t t−1 t−1 t
1 1 ... 1

e1 e2 . . . et−1

2
= e1 e22 . . . e2t−1 (et − e1 )(et − e2 ) . . . (et − et−1 )

... ..
.
..
.

et−2 et−2 . . . et−2
1 2 t−1
t−1 Y
Y i−1 t−1
Y Yt Y i−1
= (ei − ej ) · (et − ej ) = (ei − ej ).
i=1 j=1 j=1 i=1 j=1
71
Remark: We thus see that the matrix M = V DV t is nonsingular ⇐⇒ the error

values ej are nonzero and distinct.
Remark: If we attempt to increase the value of t in Eq. (7.2) beyond the actual
number of errors that have occurred, either the values ej will no longer be distinct
or at least one of them will be zero. In either case, M will no longer be invertible.
This gives us a method for finding the number of errors: t is just the largest number
such that
S1 S2 . . . St
 
.  S2 S3 . . . St+1 
M =  ... .. .. 
. . 
St St+1 . . . S2t−1
is invertible.
Remark: If it is a priori known that no more than t errors have occurred in a received
polynomial y, then it is impossible for a (t + 1) × (t + 1) or larger syndrome matrix
based on y to be invertible.
Remark: Once we have determined the maximum value of t such that the coeffi-
cient matrix M is invertible, we simply solve the linear system Eq. (7.3) for the
coefficients b1 , b2 , . . . , bt of the error locator polynomial σ(x). We can determine
all t roots of σ(x) simply by searching through all of the field elements (at most
one pass is required). The exponents `1 , `2 , . . . , `t corresponding to the inverses of
these roots precisely identify the t positions of the received vector that are in error.
Remark: The above decoding procedure can be easily extended to nonbinary codes.
In this case, the error vector becomes e(x) = q1 x`1 + q2 x`2 + . . . + qt x`t , where each
qi ∈ Fq , the syndromes become Si = q1 ei1 +. . .+qt eit , and D = diag(q1 e1 , q2 e2 , . . . , qt et ).
We then see that any BCH code of design distance d can correct b(d − 1)/2c errors.
We encapsulate this result in the following theorem.
Theorem 7.2 (BCH Bound): The minimum distance of a BCH code of odd design
distance d is at least d.
Proof: This follows from Theorem 1.1 and the fact that the BCH code can correct
(d − 1)/2 errors.
Remark: Although Theorem 7.2 may be shown to hold also when the design dis-
tance d is even, we are normally interested only in the case of odd d.
Remark: It may happen that the minimum distance of a BCH code exceeds its
design distance d, as illustrated by the following example.
• Let α be a primitive element of F211 . Since 211 − 1 = 2047 = 23 × 89, the

element β = α89 has order n = 23. The cyclotomic cosets mod 23 are {0},
{1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}, and {5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14}. Thus the
minimal polynomials of m1 (x) of β and m5 (x) of β 5 in F211 each have degree 11.1
We can then construct a [23, 12] binary BCH code of length 23 from the degree 11
generator polynomial m1 (x), which has roots at β, β 2 , β 3 , and β 4 . While the design
distance of this code is 5, the actual minimum distance is 7; in fact, this BCH code
is equivalent to the triple-error correcting [23, 12, 7] Golay code we encountered in
Chapter 4.
Remark: The special case of an [n, k] BCH code for s = 1, where the primitive
element α comes from the same field Fq as the coefficients of the generator poly-
nomial, is known as a Reed–Solomon code. Note that the minimal polynomial of
any element of Fq has degree s = 1. The generator polynomial of a Reed–Solomon
code of design distance d,
g(x) = (x − α)(x − α2 )(x − α3 ) . . . (x − αd−1 ),
thus has degree n − k = d − 1. That is, the minimum distance of the code must
at least n − k + 1. But since there are rk H ≤ n − k independent columns in
the parity check matrix, we know from Theorem 2.2 that the minimum distance
can be no more than n − k + 1. Thus, a Reed–Solomon code achieves the so-
called singleton upper bound n − k + 1 for the minimum distance of a linear code.
Because Reed–Solomon codes are optimal in this sense and easily implementable
in hardware (using shift registers), they are widely used for error correction in
computer memory chips, magnetic and optical (compact disk) storage systems,
high-speed modems, and data transmission channels.
• Since 2 is a primitive element of Z11 , the polynomial
g(x) = (x−2)(x−4)(x−8)(x−5)(x−10)(x−9) = x6 +6x5 +5x4 +7x3 +2x2 +8x+2
generates a triple-error correcting [10, 4, 7] Reed–Solomon code over Z11 . One of

the codewords is g(x) itself, which has weight 7, consistent with the above claim
that the design distance of a Reed-Solomon code is in fact the actual minimum
distance.
• Compact disk players use a double-error correcting [255, 251, 5] Reed–Solomon code
over F256 (the symbols are eight-bit bytes) with interleaving of the data over the
disk to increase robustness to localized data loss.
1
Since β 23 = 1, we know from Theorem 5.5 that x23 − 1 = (x − 1)m1 (x)m5 (x), moreover,
Theorem 5.7 implies that m5 (x) = m1 (x)
73
• High-performance computer memory chips containing so-called ECC SDRAM use

Reed–Solomon codes to correct one error per 64-bit word in addition to detecting
very rare multiple errors (which are programmed to generate a machine halt).
Problem 7.3: Prove that the Hamming code Ham(r, 2) is equivalent to an [n, k]
BCH code with distance d = 3. What is the value of k?
Problem 7.3 establishes the hierarchy of error-correcting codes illustrated in Fig. 7.1.
Figure 7.1: Hierarchy of Error-Correcting Codes.
Problem 7.4: In this question, we construct, from the primitive element α = x in

the field F2 [x]/(x4 + x3 + 1), a BCH code C of length n = 15, design distance 7.
(a) Find the degree of the generator polynomial g(x) for C.
We want α,α2 ,. . . ,α6 to be roots of g(x), so we want g(x) = m1 (x)m3 (x)m5 (x), which
has degree 4 + 4 + 2 = 10. That is, n − k = 10.
(b) What is the dimension k of C?
k = n − 10 = 5
(c) Is C perfect? Circle the correct answer: Yes / No
.
This code is not perfect since it has neither the parameters of a Hamming code nor a
Golay code.
(d) Construct the generator polynomial g(x) for C.
g(x) = m1 (x)m3 (x)m5 (x) = (x4 + x3 + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1)

= (x8 + x4 + x2 + x + 1)(x2 + x + 1) = x10 + x9 + x8 + x6 + x5 + x2 + 1.
(e) We know that the minimum distance of C is at least the design distance 7.
Using the fact that g(x) itself is a codeword of C, prove that the actual minimum
distance of C is exactly 7.
The weight of g(x) is 7, so the minimum distance of this linear code cannot exceed 7.
(f) Use the irreducible factors of x15 − 1 (or any other means) to find the check
polynomial h(x) of C.
Since
x16 − x = x(x + 1)m1 (x)m3 (x)m5 (x)m7 (x),
we know that
x15 − 1 = (x + 1)m1 (x)m3 (x)m5 (x)m7 (x) = (x + 1)m7 (x)g(x).
Hence h(x) = (x + 1)m7 (x) = (x + 1)(x4 + x + 1) = x5 + x4 + x2 + 1.

(g) How many errors can C correct?
(h) Suppose the vector 011 111 101 110 111 is received. Without computing
syndromes, find the transmitted codeword. How many errors have occurred?
Hint: Look for an obvious nearby codeword.
Since α15 = 1 in F16 , we see that
1 + α + α2 + α3 + . . . + α15 = (α − 1)−1 α15 − 1 = (α − 1)−1 · 0 = 0.

That is, the vector consisting of 15 ones is a codeword. Our received vector is only a distance
three away. Errors have occurred in positions 0, 7, and 11, but we can correct three errors.
The transmitted codeword was thus 111 111 111 111 111.
(i) Determine the original transmitted message polynomial and the corresponding
message.
The original message was
1 + x + x2 + x3 + . . . + x15 = (x + 1)−1 x15 − 1 .

From part (f) we know that
(x + 1)−1 x15 − 1 = m1 (x)m3 (x)m5 (x)m7 (x) = m7 (x)g(x).

Thus, the original message polynomial was m7 (x) = x4 +x+1, corresponding to the message
11001.
Problem 7.5: (a) Show that x2 + 1 is irreducible in Z3 [x].
Since x2 + 1 evaluates to 1, 2, 2 at the respective values 0, 1, 2 of Z3 , we know from

Theorem 6.1 that it cannot have a linear factor. Since the degree of x2 + 1 is 2, it must be
irreducible.
(b) Consider the field F9 = Z3 [x]/(x2 + 1). Show that the element x is not a
primitive element of this field. What is the order of x?
Since x2 = −1, we see that x4 = 1. The order e must divide 8, so it is in fact 4. Since
4 < 8, we know that x is not a primitive element of this field.
2
(c) List all cyclotomic cosets (the distinct exponents in the sets {αi , α3i , α3 i , . . .},
where α is a primitive element) of F9 .
{0}, {1, 3}, {2, 6}, {4}, {5, 7}.

75
(d) Establish that α = x + 1 is a primitive element of the field Z3 [x]/(x2 + 1) by

completing the following table. Indicate the order and minimal polynomial of each
element. Remember that the polynomial coefficients come from Z3 .
Element Polynomial Order Minimal Polynomial

α0 1 1 x+2
α1 x+1 8 x2 + x + 2
α2 2x 4 x2 + 1
α3 2x + 1 8 x2 + x + 2
α4 2 2 x+1
α5 2x + 2 8 x2 + 2x + 2
α6 x 4 x2 + 1
α7 x+2 8 x2 + 2x + 2
Problem 7.6: In the field Z3 [x]/(x2 + 1), with primitive element x + 1, consider the
BCH code C of length n = 8 and design distance 5.
(a) Find the degrees of the minimal polynomials used to construct the generator
polynomial g of C and the degree of g itself.
Since we want α, α2 , α3 , and α4 to be roots of g(x), we know that g must be the
product of m1 (x) (degree 2), m2 (x) (degree 2), and m4 (degree 1). Hence g must have
degree 2 + 2 + 1 = 5. That is, n − k = 5.
(b) What is the dimension k of C?
k = n − 5 = 3.
(c) How many codewords are there in C?
There are 3k = 27 codewords in C.
(d) Compute the syndromes S1 , S2 , and S3 for the received polynomial v(x) =
x + x4 + 2x5 + x6 .
3
S1 = v(α) = α3 + α4 + 2α5 + α6 = (2x + 1) + 2 + 2(2x + 2) + x = x + 1 = α,
S2 = v(α2 ) = α6 + α8 + 2α10 + α12 = x + 1 + 2(2x) + 2 = 2x = α2 ,

S3 = v(α3 ) = S13 = α3 .
(e) Using the value of the syndrome S1 and the syndrome equation

S1 S2 b2 S
=− 3 ,
S2 S3 b1 S4
show that the received polynomial in part(d) contains exactly one error.
Since S1 6= 0 but S1 S3 − S22 = αα3 − (α2 )2 = 0, we know that exactly one error has
occurred.
(f) What was the transmitted polynomial in part (d)?

On solving
S1 = α = qe,
S2 = α2 = qe2 ,
we see that e = α and q = 1. So an error of 1 has appeared in the coefficient of x. On
subtracting this error, we obtain the transmitted polynomial
2x + x3 + x4 + 2x5 + x6 .
Problem 7.7: Consider the [15, 7, 5] primitive BCH code C over F16 . Let α be a
primitive element of F16 .
(a) Find the degree of the generator polynomial g for C.

deg g = n − k = 15 − 7 = 8.
(b) Find the degrees of the minimal polynomials used to construct g.
The generator g is constructed to have roots at α, α2 , α3 , and α4 . From the cyclotomic
cosets
{0}, {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11},
we see that it must include the minimal polynomials of m1 (x) (degree 4) and m3 (x) (degree
4). Since the sum of these degrees is 4 + 4 = 8, we see that g cannot contain any additional
roots.
(c) Without computing syndromes, show that 100 100 100 100 100 is a codeword
of C.
We 3 6 9 12
know3 that
the3 geometric series c(x) = 1 + x + x + x + x has the value (1 +
x3 )−1 5
1 + (x ) for x 6= 1. Then for i = 1, 2, 3, 4,
−1 h 5 i −1 h i i
c(αi ) = 1 + α3i 1 + α3i = 1 + α3i 1 + α15
−1 −1
= 1 + α3i (1 + 1i ) = 1 + α3i 0=0
since α3i 6= 1. That is, α, α2 , α3 , and α4 (but incidentally, not α5 ) are roots of c(x). By
Theorem 5.5, c(x) is a multiple of the minimal polynomial of each of these elements, and
therefore, of g(x) itself. Thus c(x) is in the code generated by g(x).
Chapter 8
Cryptographic Codes
In contrast to error-correcting codes, which are designed only to increase the reliability
of data communications, cryptographic codes are designed to increase their security.
In cryptography, the sender uses a key to encrypt a message before it is sent through
an insecure channel (such as a telephone line, radio transmission or the internet).
An authorized receiver at the other end then uses a key to decrypt the received data
to a message. Often, data compression algorithms and error-correcting codes are
used in tandem with cryptographic codes to yield communications that are both
efficient, robust to data transmission errors, and secure to eavesdropping and/or
tampering. Typically, data compression is performed first; the resulting compressed
data is then encrypted and finally encoded with an error-correcting scheme before
being transmitted through the channel.
Definition: Let K be a set of cryptographic keys. A cryptosystem is a set
{e, d, Ee , Dd : e ∈ K}
of encrypting and decrypting keys, e and d, and their associated encrypting function
Ee and Dd , respectively.
Most cryptosystems, or ciphers, fall into one of two broad classes: symmetric-key
cryptosystems, where essentially the same key is used both to encrypt and decrypt
a message (precisely, where d can be easily determined whenever e is known) and
public-key cryptosystems, where the encryption key e is made publicly available, but
the decryption key d is kept secret and is (hopefully) known only to the receiver.
8.A Symmetric-Key Cryptography

One of the simplest cryptographic system is the shift cipher employed by Julius
Caeser. Shift ciphers encode each symbol m ∈ {0, 1, . . . , n − 1} in the message as
c = Ee (m) = m + e (mod n),
77
78 CHAPTER 8. CRYPTOGRAPHIC CODES
where e ∈ N. Decoding is accomplished via the inverse transformation
m = Dd (c) = c + d (mod n),
where d = −e. That is, encoding is accomplished by addition modulo e and decoding
is accomplished by subtraction modulo e. Caeser adopted the value e = 3 to encrypt
the n = 26 symbols of the Roman alphabet, using 0 to represent the letter A and
25 to represent the letter Z. Some fans of the film “2001: A Space Odyssey” even
suggest that the computer name HAL is really a shift cipher for IBM, with e = 25!
A slight generalization of the shift cipher is the affine cipher, defined by
c = Ea,b (m) = am + b (mod n),
where a ∈ N is relatively prime to n. This condition guarantees the existence of an

inverse transformation,
m = Da,b (c) = a−1 (c − b) (mod n).
Both shift and affine ciphers are very insecure since they are easily decoded simply
by trying all possible values of a and b! They are both special cases of simple sub-
stitution ciphers or monoalphabetic substitution ciphers, which permute the alphabet
symbols in a prescribed manner. Simple substitution ciphers can be cryptanalyzed
(decoded by an unauthorized third party) by frequency analysis, in which the en-
crypted symbol frequencies are compared to those of the original message language
to determine the applied permutation. Block substitution ciphers or polyalphabetic
substitution ciphers divide the message into blocks of length r and apply different
permutations to the symbols in individual positions of the block. Given enough en-
crypted text, block substitution ciphers are also easily cryptanalyzed once the block
size r is determined, simply by doing a frequency analysis on the letters in each fixed
position of all blocks.
Digraph ciphers map pairs of letters in the message text to encrypted pairs of
letters. A general example of this is the linear block or Hill cipher, which uses an
r × r invertible matrix e to encrypt an entire block m of r message symbols:
c = Ee (m) = em (mod n),
m = De (c) = e−1 c (mod n).

The existence of e−1 requires that det e have an inverse in Zn , which happens only
when gcd(det e, n) = 1.
• Choose r = 2, n = 26 and
2 1
e= .
3 4
8.A. SYMMETRIC-KEY CRYPTOGRAPHY 79
We see that det e = 5 has no common factors with 26. To find the inverse of 5 in Z26
we use the Euclidean division algorithm: 1 = 5x+26y, 26 = 5·5+1 ⇒ 1 = 26−5·5,
from which we see that x = −5 is a solution. Thus

−1 4 −1 6 5
e = −5 = .
−3 2 15 16
We can use e to encrypt the word “SECRET”, in other words the message 18 4
2 17 4 19, by breaking the message up into vectors of length two: [18 4], [2 17],
[4 19] and then multiplying the transpose of each vector by e on the left. The
result is [14 18], [21 22], [1 10], or the cipher text “OSVWBK”. Note that the two
letters “E” are not mapped to the same symbol in the ciphertext. For this reason
the Hill cipher is less susceptible to frequency analysis (particularly for large block
sizes; however, the number of entries in the key matrix then becomes unreasonably
large).
Problem 8.1: Verify that the original message “SECRET” is recovered when “OS-
VWBK” is decoded with the matrix e−1 .
A special case of the block cipher is the permutation cipher, in which the order of
the characters in every block of text is rearranged in a prescribed manner. Permuta-
tion ciphers can be detected by frequency analysis since they preserve the frequency
distribution of each symbol. In fact, all linear or affine block methods are subject
to cryptanalysis using linear algebra, once r or r + 1 plaintext–ciphertext pairs are
known.
A widely used commercial symmetric-key cryptosystem is the Data Encryption
Standard (DES), which is a type of Feistel cipher endorsed in 1977 by the United
States National Bureau of Standards for the protection of confidential (but unclassi-
fied) government data. In 1981, DES was approved also for use in the private-sector.
Feistel ciphers are block ciphers over F22t . One divides a plaintext block message of 2t
bits into two halves, L0 and R0 , and then performs the iteration
Li = Ri−1 ,
Ri = Li−1 + f (Ri−1 , ei ), i = 1, . . . , r,
where the ei are the keys and f is a specific nonlinear cipher function. The encryption
function is Ee (L0 | R0 ) = Rr | Lr , where | denotes concatenation, and e = (e1 , . . . er )
denotes a set of r encryption keys. The decryption function De (Lr | Rr ) = R0 | L0 , is
implemented by applying the inverse iteration
Li−1 = Ri + f (Li , ei ),
Ri−1 = Li , i = r, . . . , 1.
With Feistel ciphers, the encryption and decryption algorithms are essentially the
same, except that the key sequence is reversed.
The DES cipher uses the half width t = 32 and r = 16 rounds of encryption.
All 16 keys are generated from a bit sequence of length 64 that is divided into 8
bytes. The eighth bit of each byte is an (odd) parity check, so in fact there are
only 56 information bits in the key. Hence the number of keys that need to be
searched in a brute-force attack on DES is 256 . In fact, because of an inherent ones-
complement symmetry, only 255 keys need to be checked. On a modern supercomputer
this is quite feasible; moreover, DES has recently been shown to be susceptible to
relatively new cryptanalytic techniques, such as differential cryptanalysis and linear
cryptanalysis. Somewhat more secure variants of DES (such as Triple-DES, where
DES is applied three times in succession with three different keys), were developed as
interim solutions. One common application of DES that persists today is its use in
encrypting computer passwords, using the password itself as a key. This is why many
computer passwords are still restricted to a length of eight characters (64 bits).
In October 2000, the Rijndael Cryptosystem was adopted by the National Bureau
of Standards as the Advanced Encryption Standard (AES) to replace DES. It is
based on a combinations of byte substitutions, shifts, and key additions, along with a
diffusion-enhancing technique based on cyclic coding theory, where the data values are
multiplied by the polynomial 3x3 + x2 + x + 2 in the polynomial ring F256 [x]/(x4 − 1).
8.B Public-Key Cryptography

A principle difficulty with symmetric-key cryptosystems is the problem of key distri-
bution and management. Somehow, both parties, which may be quite distant from
each other, have to securely exchange their secret keys before they can begin commu-
nication.
One technique for avoiding the problem of key exchange makes use of two secure
envelopes, or locks, which each party alternately applies and later removes from the
sensitive data, as the data makes a total of three transits between sender and receiver.
The required three transmissions makes this method awkward to use in practice.
In public-key cryptosystems, key exchange is avoided altogether by making copies
of the receiver’s encrypting key (lock) available to anyone who wants to communicate
with him. Both the secure envelope technique and the public-key technique require
that the encrypting key e is designed so that the decrypting key d is extremely difficult
to determine from knowledge of e. They also require authentication of the lock itself,
to guard against so-called man-in-the-middle attacks.
8.B.1 RSA Cryptosystem

The most well known public-key cipher is the Rivest–Shamir–Aldeman (RSA) Cryp-
tosystem. First, the receiver forms the product n of two distinct large prime numbers p
8.B. PUBLIC-KEY CRYPTOGRAPHY 81
and q chosen at random, but such that p and q cannot be easily determined from n.1
The receiver then selects a random integer e between 1 and ϕ(n) = (p − 1)(q − 1) that
is relatively prime to ϕ(n) and, using the Euclidean division algorithm, computes
d = e−1 in Zϕ(n) (why does e−1 exist?). The numbers n and e are made publicly
available, but d, p, q are kept secret.
Anyone who wishes to send a message m, where 0 ≤ m < n, to the receiver
encrypts the message using the encoding function
c = Ee (m) = me (mod n)
and transmits c. Because the receiver has knowledge of d, the receiver can decrypt c
using the decoding function
M = De (c) = cd (mod n).
To show that M = m, we will need the following results.
Theorem 8.1 (Modified Fermat’s Little Theorem): If s is prime and a and m are
natural numbers, then
m ma(s−1) − 1 = 0 (mod s).

Proof: If m is a multiple of s we are done. Otherwise, we know that ma is not

a multiple of s, so Fermat’s little theorem2 implies that (ma )s−1 = 1 (mod s), from
which the result follows.
Corollary 8.1.1 (RSA Inversion): The RSA decoding function De is the inverse of
the RSA encoding function Ee .
By construction ed = 1 + kϕ(n) for some integer k, so
M = De (c) = cd = (me )d = med = m1+kϕ(n) = m1+k(p−1)(q−1) (mod n).
We first apply Theorem 8.1 with a = k(q − 1), s = p and then with a = k(p − 1),
s = q, to deduce that m[mk(q−1)(p−1) − 1] is a multiple of both of the distinct primes p
and q, that is, m[mk(q−1)(p−1) − 1] = 0 (mod pq). Thus
M = mmk(q−1)(p−1) = m (mod pq) = m (mod n).
1
For example, if p and q are close enough that (p + q)2 − 4n = (p + q)2 − 4pq = (p − q)2 is small,
then the sum p + q could be determined by searching for a small value of p − q such that (p − q)2 + 4n
is a perfect square, which must be p + q. Knowledge of p − q and p + q is sufficient to determine
both p and q.
2
This follows from applying Theorem 5.4 to the field Zs .
• Let us encode the message “SECRET” (18 4 2 17 4 19) using the RSA scheme with
a block size of 1. The receiver chooses p = 5 and q = 11, so that n = pq = 55 and
ϕ(n) = 40. He then selects e = 17 and finds d = e−1 in Z40 , so that 17d = 40k + 1
for some k ∈ N. This amounts to finding gcd(17, 40):
40 = 2 · 17 + 6, 17 = 2 · 6 + 5, 6 = 1 · 5 + 1,
from which we see that
1 = 6 − 5 = 6 − (17 − 2 · 6) = 3 · (40 − 2 · 17) − 17 = 3 · 40 − 7 · 17.
That is, d = −7 (mod 40) = 33. The receiver publishes the numbers n = 55 and
e = 17, but keeps the factors p = 5, q = 11, and d = 33 (and ϕ(n)) secret.
The sender then encodes 18 4 2 17 4 19 as
1817 417 217 1717 417 1917 (mod 55) = 28 49 7 52 49 24
The two Es are encoded in exactly the same way, since the block size is 1: obviously,
a larger block size should be used to thwart frequency analysis attacks.3
The receiver would then decode the received message 28 49 7 52 49 24 as
2833 4933 733 5233 4933 2433 (mod 55) = 18 4 2 17 4 19.
Remark: While the required exponentiations can be performed by repeated squaring

and multiplication in Zϕ(n) (e.g. x33 = x32 · x), RSA decryption can be implemented
in a more efficient manner. This is important, since to make computing the secret
key d (from knowledge of n and e alone) difficult, d must be chosen to be about
as large as n. Instead of computing m = cd directly, we first find a = cd (mod p)
and b = cd (mod q). This is very easy since Fermat’s little theorem says that
cp−1 = 1 (mod p), so these definitions reduce to
a = cd mod(p−1)
(mod p), b = cd mod(q−1)
(mod q).
The Chinese remainder theorem then guarantees that the system of linear congru-
ences
m = a (mod p), m = b (mod q)
has exactly one solution in {0, 1, . . . , n − 1}. One can find this solution by using the
Euclidean division algorithm to construct integers x and y such that 1 = xp + yq.
Since yq = 1 (mod p) and xp = 1 (mod q), we see that
m = ayq + bxp (mod n)
is the desired solution. Since the numbers x and y are independent of the ciphertext,
the factors xp and yq can be precomputed.
3
For example, we could encode pairs of letters i and j as 26i + j and choose n ≥ 262 = 676,
although such a limited block size would still be vulnerable to more time consuming but feasible
digraph frequency attacks.
8.B. PUBLIC-KEY CRYPTOGRAPHY 83
• To set up an efficient decoding scheme we precompute x and y such that 1 = px+qy.

For p = 5 and q = 11, we see that x = −2 and y = 1 are solutions, so that xp = −10
and yq = 11. Once a and b are determined from the ciphertext we can quickly
compute m = 11a − 10b (mod 55). For example, to compute 2833 we evaluate
a = 2833 (mod 4)
(mod 5) = 28 (mod 5) = 3,
b = 2833 (mod 10)

(mod 11) = 283 mod 11 = 63 (mod 11) = 7
and then compute m = 11a − 10b = (33 − 70) (mod 55) = 18.
Remark: Determining d from e and n can be shown to be equivalent to determining

the prime factors p and q of n. Since factoring large integers in general is an
extremely difficult problem, the belief by many that RSA is a secure cryptographic
system rests on this equivalence. However, it has not been ruled out that no
other technique for decrypting RSA ciphertext exists. If such a technique exists,
presumably it does not involve direct knowledge of d (as that would constitute an
efficient algorithm for factorizing integers!).
Problem 8.2: You have intercepted an encrypted transmission that was intended
for your math professor. It consists of the three numbers 26, 14, and 19. Each of
these numbers was separately encoded, using RSA encoding and a block size of 1,
where the letters A to Z are mapped to Z26 in the usual way. On your professor’s
web page you notice that he lists his public key as (n = 33, e = 13).
(a) Without breaking into your professor’s computer, determine the “secret” prime
factors p and q of n.
p = 3, q = 11.
(b) Determine the decryption exponent d, knowing e, p, and q.

First we find φ(n) = (p − 1)(q − 1) = 20. Since 20 = 1 · 13 + 7, 13 = 1 · 7 + 6, and
7 = 1·6+1, we see that 1 = 7−6 = 7−(13−7) = 2·7−13 = 2·(20−13)−13 = 2·20−3·13.
So d = −3 (mod 20) = 17.
(c) Use d to decrypt the secret message. Interpret your result as a three-letter
English word.
Since 11 = 3 · 3 + 2 and 3 = 1 · 2 + 1 we see that 1 = 3 − 2 = 3 − (11 − 3 · 3) = 4 · 3 − 11.
Hence 1 = xp + yq, where x = 4 and y = −1. Hence we can decode the message c as
m = 12b − 11a (mod 33), where a = c17 (mod 3) = c1 (mod 3) and b = c17 (mod 11) =
c7 (mod 11).
For c = 26, we find
a = 261 (mod 3) = 21 (mod 3) = 2,
b = 267 (mod 11) = 47 (mod 11) = 214 (mod 11) = 24 (mod 11) = 5.
This yields m = 12(5) − 11(2) = 38 (mod 33) = 5.
Similarly, for c = 14, we find
a = 21 (mod 3) = 2,
b = 37 (mod 11) = 3 · 272 (mod 11) = 3 · 52 (mod 11) = 3 · 3 (mod 11) = 9.

This yields m = 12(9) − 11(2) = 20.
Finally, for c = 19, we find
a = 117 (mod 3) = 1,
b = 87 (mod 11) = 221 (mod 11) = 21 (mod 11) = 2.

This yields m = 12(2) − 11(1) = 13.
Thus, the sent message was 5, 20, 13, which spells FUN!
Problem 8.3: You have intercepted an encrypted transmission from the Prime Min-
ister’s Office to the Leader of the Official Opposition. It consists of the two numbers
27 and 14, which were separately encoded, using RSA encoding and a block size
of 1, where the letters A to Z are mapped to Z26 in the usual way. On the Leader
of the Official Opposition’s web page you notice that he lists his public key as
(n = 35, e = 11).
(a) Determine the “secret” prime factors p and q of n.

p = 5, q = 7.
(b) Determine the decryption exponent d, knowing e, p, and q.

First we find φ(n) = (p − 1)(q − 1) = 24. Since 24 = 2 · 11 + 2, 11 = 5 · 2 + 1, we see
that 1 = 11 − 5 · 2 = 11 − 5 · (24 − 2 · 11) = 11 · 11 − 5 · 24. So d = 11.
(c) Use d to decrypt the secret message. Interpret your result as a two-letter
English word.
Since 7 = 1 · 5 + 2 and 5 = 2 · 2 + 1 we see that 1 = 5 − 2 · 2 = 5 − 2 · (7 − 1 · 5) = 3 · 5 − 2 · 7.
Hence 1 = xp + yq, where x = 3 and y = −2. Hence we can decode the message c as m =
15b − 14a (mod 35), where a = c11 (mod 5) = c3 (mod 5) and b = c11 (mod 7) = c5 (mod 7).
For c = 27, we find
a = 273 (mod 5) = 23 (mod 5) = 3,
b = 275 (mod 7) = (−1)5 (mod 7) = −1(mod 7) = 6.

This yields m = 15(6) − 14(3) = 48 (mod 35) = 13.
Similarly, for c = 14, we find
a = 143 (mod 5) = (−1)3 (mod 5) = 4,
b = 145 (mod 7) = 0.
This yields m = −14(4) = −56 (mod 35) = 14.
Thus, the sent message was 13, 14 which spells NO!
8.C. DISCRETE LOGARITHM SCHEMES 85
8.B.2 Rabin Public-Key Cryptosystem

In contrast to the RSA scheme, the Rabin Public-Key Cryptosystem has been proven
to be as secure as factorizing large integers is difficult. Again the receiver forms the
product n = pq of two large distinct primes p and q that are kept secret. To make
decoding efficient, p and q are normally chosen to be both congruent to 3 (mod 4).
This time, the sender encodes the message m ∈ {0, 1, . . . , n − 1} as
c = Ee (m) = m2 (mod n).
To decode the message, the receiver must be able to compute square roots modulo n.
This can be efficiently accomplished in terms of integers x and y satisfying 1 = xp+yq.
First one notes from Lemma 6.1 that the equation 0 = x2 −c has at most two solutions
in Zp . In fact, these solutions are given by ±a, where a = c(p+1)/4 (mod p):
(±a)2 = c(p+1)/2 (mod p) = cc(p−1)/2 (mod p) = cm(p−1) (mod p) = c (mod p).
Similarly, the two square roots of c in Zq are ±b, where b = c(q+1)/4 (mod q). Conse-
quently, by the Chinese remainder theorem, the linear congruences
M = ±a (mod p), M = ±b (mod q)
yield four solutions:

M = ±(ayq ± bxp) (mod n),
one of which is the original message m.
8.C Discrete Logarithm Schemes

The RSA system is based on the trapdoor property that multiplying two large prime
numbers is much easier than factoring a large composite number into two constituent
primes. Another example of such a one-way function is the fact that computing a
high power of an element within a group is much easier than the reverse process of
determining the required exponent.
8.C.1 Diffie–Hellman Key Exchange

Definition: Let G be a finite group and b ∈ G. Suppose y ∈ G can be obtained as
the power bx in G. The number x is called the discrete logarithm of y to the base b
in G.
Remark: The Diffie–Hellman assumption conjectures that it is computationally in-

feasible to compute αab knowing only αa and αb . It is assumed that this would
require first determining one of the powers a or b (in which case it as difficult as
computing a discrete logarithm).
Let Fq be a publicly agreed upon field with q elements, with primitive element α.
If Alice and Bob want to agree on a common secret key, they each secretly choose
a random integer between 1 and q − 1, which they call a and b, respectively. Alice
computes and sends αa to Bob; likewise, Bob computes and sends αb to Alice. Their
common secret key is then αab . If the Diffie–Hellman assumption is correct, a third
party will be unable to determine αab from knowledge of the public keys αa and αb
alone.
In the ElGamal Cryptosystem, Alice sends a message m to Bob as the pair of
elements (αk , mαbk ), where k is a randomly chosen integer. Bob can then determine m
by dividing mαbk by (αk )b .
8.C.2 Okamoto Authentication Scheme

One of the more difficult issues in public key cryptography is that of authentication,
that is, verifying the identity of a sender or receiver. For example, Alice should
not blindly assume that Bob’s posted public key is really his, without independent
confirmation via a trusted source. And Bob, when he decrypts a message from Alice,
should not naively believe that it was really Alice who used his public encoding key
to send the message to him in the first place.
A trusted authority (perhaps the government?) might issue Alice an electronic
certificate based on more conventional forms of identification (such as a passport,
driver’s license, or birth certificate), which Alice would like to then use to authenticate
herself while communicating with Bob. However, Alice can’t simply send Bob her
secret identification code. Even if she encrypted it with Bob’s public key, there would
always be the risk that Bob might later use Alice’s identification to impersonate her!
Obviously, part of Alice’s identification must be kept secret.
One practical scheme for doing this is the Okamoto authentication scheme, a
variation of an earlier scheme by Schnorr. A trusted certifying authority chooses a
field Zp , where the prime p is chosen such that p − 1 has a large prime factor q.
The authority also chooses two distinct elements of order q in Zp , say g1 and g2 . To
request a certificate, Alice chooses two secret random exponents a1 and a2 in Zq and
sends the number
s = g1−a1 g2−a2 (mod p).
to the trusted authority, who uses a secret algorithm to generate an identifying cer-
tificate C(s) for Alice. When Alice communicates with Bob, she identifies herself by
sending him both her signature s and certificate C(s). She can then authenticate
herself to Bob with the following procedure.
8.C. DISCRETE LOGARITHM SCHEMES 87
Bob first checks with the trusted authority to confirm that s and C(s) really belong
to Alice. But since s and C(s) aren’t secret, this doesn’t yet establish that Alice was
really the one who sent them to Bob. So Bob challenges the person claiming to be
Alice to prove that she really owns the signature s, by first sending her a random
number r ∈ Zq .
Alice now tries to prove to Bob that she owns the underlying private keys a1
and a2 , without actually revealing them to him, by choosing random numbers k1
and k2 in Zq and sending him the three numbers
y1 = k1 + a1 r (mod q),
y2 = k2 + a2 r (mod q),
γ = g1k1 g2k2 (mod p).
Bob uses the fact that g1q = g2q = 1 (mod p) and the value of s to verify in Zp that
g1y1 g2y2 sr = g1k1 +a1 r g2k2 +a2 r sr = g1k1 g2k2 = γ (mod p).
The agreement of the numbers g1y1 g2y2 sr and γ in Zp begins to convince Bob that
maybe he really is talking to Alice after all.
But the question is, is it possible that a third party, say Charlie, is impersonating
Alice, having somehow devised a clever algorithm to determine numbers y10 and y20 that
fool Bob into thinking the sender is Alice? We now show that impersonation under
the Okamoto authentication scheme is as difficult as solving the discrete logarithm
problem.
Suppose Charlie has managed to find a way to convince Bob that he is Alice. That
is, without knowing Alice’s secret key, he has figured out a clever way to generate
two exponents y10 and y20 such that
y0 y0 0
g1 1 g2 2 sr = γ (mod p),
no matter what challenge r0 Bob sends him. Suppose he uses his algorithm again, for
a distinct challenge r00 6= r0 , to determine exponents y100 and y200 :
y 00 y 00 00
g1 1 g2 2 sr = γ (mod p).
Then
y 0 −y100 y 00 −y20 r00 −r0
g1 1 = g2 2 s (mod p),
and so
(r00 −r0 )−1 (y10 −y100 ) (r00 −r0 )−1 (y20 −y200 )
g1 g2 = s.
Charlie has thus determined two exponents a01 and a02 such that
−a0 −a02
s = g1 1 g2 (mod p).
It is not hard to show, when q is sufficiently large, that for virtually all possible
challenges r0 and r00 , the resulting pair of exponents (a01 , a02 ) will be distinct from
Alice’s exponents (a1 , a2 ) (for example, see Stinson [1995]). Without loss of generality,
we can relabel these exponents so that a2 6= a02 .
Together with Alice’s original construction
s = g1−a1 g2−a2 (mod p),
Charlie’s scheme would then constitute a computationally feasible algorithm for com-
puting loga1 g2 in Zp : we would know
a −a01 a0 −a2
g1 1 = g2 2 (mod p),
so that, on using the fact that a02 6= a2 ,
logg1 g2 = (a02 − a2 )−1 (a1 − a01 ).
Note that since g1 and g2 were chosen by the trusted authority, neither Alice nor
Charlie had any prior knowledge of the value logg1 g2 .
8.C.3 Digital Signature Standard

Another situation that arises frequently is where Bob hasn’t yet gone to the trouble of
creating a public key, but Alice would nevertheless like to send him an electronically
signed document. Her electronic signature should guarantee not only that she is the
sender, but also that the document hasn’t been tampered with during transmission.
One means for doing this is the Digital Signature Standard (DSS) proposed in 1991 by
the U.S. government National Institute of Standards and Technology as a standard
for electronically signing documents.
In the DSS, a large prime p is chosen such that p − 1 has a large prime factor
q and an element g of order q is chosen from Zp . Alice’s chooses as her private key
the random integer a in Zq . Her public key is A = g a . Alice first applies to her
document x a hash function f , which is essentially a function that maps a long string
of characters to a much shorter one, such that it is computationally infeasible to find
another document x0 such that f (x0 ) = f (x) (even though such an x0 will likely exist).
This makes it virtually impossible to tamper with the document without altering the
hash value. The short string of characters given by the hash is converted to an
integer h in Zq .
Alice now chooses a random number k in Zq and finds an integer s such that
sk = h + ag k (mod q), where g k ∈ Zp . She signs her document with the pair (g k , s).
Bob can verify the authenticity and integrity of the document he receives by first
calculating its hash h. He then uses Alice’s public key A to check that
−1 h −1 g k −1 (h+ag k )
gs As = gs = g k (mod p).
If this is indeed the case then Bob is convinced that the contents and signature are
genuine.
8.D. CRYPTOGRAPHIC ERROR-CORRECTING CODES 89
8.C.4 Silver–Pohlig–Hellman Discrete Logarithm Algorithm

As it happens, a fast means for computing discrete logarithms in Fq , the Silver–
Pohlig–Hellman algorithm, is known if all of the prime factors p of q − 1 are small.
For this reason, care must be taken when choosing the size q of the field used in
cryptographic schemes that rely on the Diffie–Hellman assumption.
To find x such that bx = y in Fq , it suffices to find x mod pap for each prime factor p
of q − 1, where ap is the number of p factors appearing in the prime factorization of
q − 1. The Chinese remainder theorem can then be used to solve the simultaneous
congruence problem that determines the value of x.
For each prime factor p, we first compute a table of the pth roots of unity bj(q−1)/p
for j = 0, 1, . . . , p − 1, noting that bq−1 = 1 in the field Zq .
To find x mod pa , we attempt to compute each of the coefficients in the p-ary
expansion of x mod pa :
x = x0 + x1 p + . . . + xa−1 pa−1 mod pa .
For example, to find x0 , we compute the pth root of unity y (q−1)/p . But y (q−1)/p =
bx(q−1)/p = bx0 (q−1)/p , so in our table of pth roots, x0 is just the j value corresponding
to the root y (q−1)/p .
To find x1 we repeat the above procedure replacing y with y1 = yb−x0 = bx−x0 ,
which has the discrete logarithm x1 p + . . . + xa−1 pa−1 . Since y1 is evidently a pth
(q−1)/p (q−1)/p2 2
power, we see that y1 = 1 in Zq and y1 = b(x−x0 )(q−1)/p = bx1 (q−1)/p is
the pth root of unity corresponding to j = x1 . Continuing in this manner, we can
compute each of the xi values for i = 0, 1, . . . , a − 1. Once we have found x mod pap
for each prime factor p of q − 1, we can use the Chinese remainder theorem to find x
itself.
8.D Cryptographic Error-Correcting Codes

We conclude with an interesting cryptographic application of error-correcting codes
due to McEliece [1978]. The receiver selects a block size k and a private key consisting
of an [n, k, 2t+1] linear code C with generator matrix G, a k×k nonsingular scrambler
matrix S, and an n × n random permutation matrix P . He then constructs the k × n
matrix K = SGP as his public key. A sender encodes each message block m as
c = Ee (m) = mK + z,
where z is a random error vector of length n and weight no more than t. The receiver
then computes
cP −1 = (mK + z)P −1 = (mSGP + z)P −1 = mSG + zP −1 .
Since the weight of zP −1 is no more than t, he can use the code C to decode the
vector mSG + zP −1 to the codeword mS. After multiplication on the right by S −1 ,
he recovers the original message m.
Bibliography
[Buchmann 2001] J. A. Buchmann, Introduction to Cryptography,

Springer, New York, 2001.
[Hill 1997] R. Hill, A First Course in Coding Theory, Oxford

University Press, Oxford, 1997.
[Koblitz 1994] N. Koblitz, A Course in Number Theory and Cryp-

tography, Springer, New York, 2nd edition, 1994.
[Lin & Daniel J. Costello 2004] S. Lin & J. Daniel J. Costello, Error Control Cod-
ing, Pearson Prentice Hall, Upper Saddle River, New
Jersey, 2nd edition, 2004.
[Ling & Xing 2004] S. Ling & C. Xing, Coding Theory: A First Course,
Cambridge Univ. Presso, Cambridge, 2004.
[Mollin 2001] R. A. Mollin, An Introduction to Cryptography,

Chapman & Hall/CRC, Boca Raton, Florida, 2001.
[Pless 1989] V. Pless, Introduction to the Theory of Error-

Correcting Codes, Wiley, New York, 2nd edition,
1989.
[Rosen 2000] K. H. Rosen, Elementary Number Theory and its ap-

plications, Addison-Wesley, Reading, Massachusetts,
4th edition, 2000.
[Stinson 1995] D. R. Stinson, Cryptography: Theory and Practice,

CRC Press, Boca Raton, Florida, 1995.
[van Lint 1991] J. van Lint, Introduction to Coding Theory, Springer,

Berlin, 3rd edition, 1991.
[Welsh 2000] D. Welsh, Codes and Cryptography, Oxford Univer-

sity Press, Oxford, 2000.
90
Index
(n, M, d) code, 9 coset leaders, 27

Aq (n, d), 11 cryptosystem, 78
Fq [x], 58 cyclic, 57
[n, k, d] code, 23 cyclotomic coset, 54
[n, k] code, 23
|C|, 27 Data Encryption Standard (DES), 80
. design distance, 66
=, 7
q-ary symmetric channel, 6 detect, 10
differential cryptanalysis, 81
affine cipher, 79 Diffie–Hellman assumption, 87
alphabet, 7 Digital Signature Standard, 89
authentication, 87 Digraph ciphers, 79
discrete logarithm, 86
balanced block design, 17
basis vectors, 23 ElGamal Cryptosystem, 87
BCH code, 66 encode, 26
binary, 8 envelopes, 81
binary adders, 57 equivalent, 13, 25
binary ascending form, 41 error locator polynomial, 67
binary code, 7 error polynomial, 67
binary codewords, 7 error vector, 28
binary Hamming code, 39 Euler indicator, 50
binary symmetric, 6 Euler totient, 50
bit, 6 extended Golay, 44
Block substitution ciphers, 79
Feistel, 80
blocks, 17
flip-flops, 57
Bose–Chaudhuri–Hocquenghem (BCH) codes,
frequency analysis, 79
66
generate, 23
check polynomial, 62 generated, 58
Chinese remainder theorem, 83 generator matrix, 24
ciphers, 78 generator polynomial, 59
code, 8
codeword, 7 Hamming bound, 14
correct, 10 Hamming code, 39
coset, 26 Hamming distance, 8
91
92 INDEX
hash, 89 reduced echelon form, 25

Hill cipher, 79 redundancy, 30
Reed–Solomon, 73
ideal, 58 repetition code, 7
incidence matrix, 18 residue class ring, 58
information digits, 41 Rijndael Cryptosystem, 81
irreducible, 60 Rivest–Shamir–Aldeman (RSA) Cryptosys-
linear block, 79 tem, 81
linear code, 23 Schnorr, 87
linear cryptanalysis, 81 scrambler matrix, 90
man-in-the-middle, 81 self-dual, 45
metric, 8 self-orthogonal, 45
minimal polynomial, 52, 64 shift cipher, 78
minimum distance, 9 shift registers, 57
minimum weight, 24 Silver–Pohlig–Hellman algorithm, 90
monic, 59 simple substitution ciphers, 79
monoalphabetic substitution ciphers, 79 singleton, 73
size, 8
nearest-neighbour decoding, 8 Slepian, 27
null space, 30 span, 23
sphere-packing, 14
Okamoto authentication scheme, 87
Sphere-Packing Bound, 14
one-way function, 86
standard array, 27
order, 48, 51
standard form, 25, 31
parity-check digits, 41 symmetric, 18
parity-check matrix, 30 symmetric matrix, 45
perfect code, 15 symmetric-key cryptosystems, 78
permutation cipher, 80 syndrome, 31, 67
permutation matrix, 90 syndrome decoding, 31
points, 17
ternary, 8
polyalphabetic substitution ciphers, 79
trapdoor property, 86
polynomial ring, 58
triangle inequality, 8
primitive BCH code, 66
Triple-DES, 81
primitive element, 52, 63
trivially perfect codes, 15
primitive polynomial, 53, 64
principal ideal, 58 Vandermonde matrix, 70
Principal Ideal Domain, 58
public-key cryptosystems, 78 weight, 9
weighted check sum, 20
Rabin Public-Key Cryptosystem, 86
rate, 29
reciprocal polynomial, 63

Math 422 Coding Theory & Cryptography: John C. Bowman University of Alberta

Uploaded by

Copyright:

Available Formats

Math 422 Coding Theory & Cryptography: John C. Bowman University of Alberta

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Math 422 Coding Theory & Cryptography: John C. Bowman University of Alberta

Uploaded by

Copyright:

Available Formats

Math 422

Coding Theory & Cryptography

October 15, 2015

If the message 11 or 00 is received, either 0 or 2 errors have occurred. Thus, we

1.A Error Detection and Correction

• A binary codeword, corresponding to the case q = 2, is just a finite sequence of 0s

• A ternary codeword, corresponding to the case q = 3, is just a finite sequence of

Definition: A q-ary code is a set of M codewords, where M ∈ N is known as the size

Figure 1.1: Triangle inequality.

Remark: We can use property 2 to rewrite the triangle inequality as

d(x, y) − d(y, z) ≤ d(x, z) ∀x, y, z ∈ Fqn .

Remark: Let x and y be binary codewords in Zn2 . Then d(x, y) = w(x − y) =

Definition: An (n, M, d) code is a code of length n, containing M codewords and

Upon considering each of the 42 = 4×3

Figure 1.2: Detection of up to t errors in a transmitted codeword x requires that all

• Since we have already constructed a (5, 4, 3) code, we know that A2 (5, 3) ≥ 4. We

Theorem 1.2 (Special Cases): For any values of q and n,

n d=3 d=5 d=7

Table 1.1: Maximum code size A2 (n, d) for n ≤ 16 and d ≤ 7.

(A) permutation of the columns of the code;

(B) relabelling the symbols appearing in a fixed column.

• The binary code  

Lemma 1.3 (Counting): A sphere of radius t in Fqn , with 0 ≤ t ≤ n, contains exactly

Theorem 1.4 (Sphere-Packing Bound): A q-ary (n, M, 2t + 1) code satisfies

Problem 1.1: Prove that n  

Problem 1.3: (a) Given an (n, M, d) q-ary code C, let Ni : i = 0, 1, . . . , q − 1 be the

(c) Conclude that

(a) Express t in terms of m.

d(x, z) ≤ d(x, v) + d(v, z) = t + 1 + t = 2t + 1,

1.B Balanced Block Designs

Definition: A balanced block design consists of a collection of b subsets, called blocks,

(i) each point lies in exactly r blocks;

(ii) each block contains exactly k points;

(iii) each pair of points occurs together in exactly λ blocks.

Such a design is called a (b, v, r, k, λ) design.

Figure 1.3: Seven-point plane.

T = {(x, B) : x is a point, B is a block, x ∈ B}.

U = {(x, y, B) : x, y are distinct points, B is a block, x, y ∈ B},

where xi , i = 1, . . . , v are the design points and Bj , j = 1, . . . , b are the design

• For our above (7, 3, 1) symmetric design, the incidence matrix A is

(since λ = 1). Hence d(ai , aj ) = 3 + 3 − 2(1) = 4 for i 6= j. Likewise, d(bi , bj ) = 4.

d(ai , bj ) = w(ai − bj ) = w(1 − (ai − aj )) = w(1) + w(ai − aj ) − 2w(ai − aj )

1.C The ISBN Code

Table 1.2: Inverses modulo 11.

x = −4−1 (1 · 0 + 2 · 1 + 3 · 9 + 5 · 5 + 6 · 3 + 7 · 8 + 8 · 0 + 9 · 3 + 10 · 0) (mod 11)

which is indeed correct.

x6 = −6−1 (1 · 0 + 2 · 8 + 3 · 0 + 4 · 1 + 5 · 8 + 7 · 7 + 8 · 3 + 9 · 9 + 10 · 1) (mod 11)

x5 = −8−1 (1 · 0 + 2 · 3 + 3 · 9 + 4 · 3 + 5 · 0 + 6 · 5 + 7 · 1 + 9 · 0 + 10 · 10) (mod 11)

Remark: The zero vector 0 automatically belongs to all linear codes.

Definition: We say that a k-dimensional code in Fqn is an [n, k] code, or if we also

Definition: Define the minimum weight of a code to be w(C) = min{w(x) : x ∈

One of the advantages of linear codes is illustrated by the following lemma.

Proof: There exist codewords x, y, and z with x 6= y, and z 6= 0 such that

d(C) ≤ d(z, 0) = w(z − 0) = w(z) = w(C) ≤ w(x − y) = d(x, y) = d(C),

• A q-ary repetition code of length n is an [n, 1, n] code with generator matrix

(A) permutation of the columns of the code;

(B) multiplication of the symbols appearing in a fixed column by a nonzero scalar.

Definition: A k × n matrix of rank k is in reduced echelon form (or standard form)

2.A Encoding and Decoding

Problem 1.1: Prove that n