Lecture Notes in Mathematics A collection of informal reports and seminars Edited by A. Dold, Heidelberg and B. Eckmann, ZUrich Series: California Institute of Technology, Pasadena Adviser: C. R. DePrima
201 Jacobus H. van Lint California Institute of Technology, Pasadena, CA/USA
Cod ing Theory Second Printing
Springer-Verlag Berlin · Heidelberg · New York 1973
AMS Subject Classifications (1970): 94A 10
ISBN 3-540-06363-3 Springer-Verlag Berlin - Heidelberg -New York ISBN 0-387-06363-3 Springer-Verlag New York · Heidelberg . Berlin ISBN 3-540-05476-6 1. Auflage Springer-Verlag Berlin· Heidelberg· New York ISBN 0-387-05476-6 1st edition Springer-Verlag New York· Heidelberg· Berlin
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Verlag Berlin· Heidelberg 1973. Library of Congress Catalog Card Number 73-83239. Printed in Germany. Offsetdruck: Julius Beltz, Hemsbach
PREFACE These lecture notes are the contents of a two-term course given by me during the 1970-1971 academic year as Morgan Ward visiting professor at the California Institute of Technology. and graduate students.
The students who took the course were mathematics seniors Therefore a thorough knowledge of algebra. (a.o. linear
algebra, theory of finite fields, characters of abelian groups) and also probability theory were assumed.
After introducing coding theory and linear codes these notes
concern topics mostly from algebraic coding theory. subject, e.g. circuitry, is not included.
The practical side of the
Some topics which one would like to
include 1n a course for students of mathematics such as bounds on the information rate of codes and many connections between combinatorial mathematics and coding theory could not be treated due to lack of time.
For an extension of the course
into a third term these two topics would have been chosen. Although the material for this course came from many sources there are three which contributed heavily and which were used as suggested reading material for the students.
These are W. W. Peterson's Error-Correcting Codes «(15]),
E. R. Berlekamp's Algebraic Coding Theory «(5]) and several of the AFCRL-reports
by E. F. Assmus, H. F. Mattson and R. Turyn ([2], (3), [4] a.o.).
For several
fruitful discussions I would like to thank R. J. McEliece. The extensive treatment of perfect codes is due to my own interest in this topic and recent developments.
The reader who is familiar with coding theory will
notice that in several places I have given a new treatment or new proofs of known theorems.
Since coding theory is young there remain several parts which need
polishing and several problems are still open.
I sincerely hope that the course
and these notes will contribute to the growing interest of mathematicians in this fascinating subject. For her excellent typing of these lecture notes I thank Mrs. L. Decker.
Pasadena, March 1971.
J. H. van Lint.
CONTENTS
CHAPl'ER I:
Introduction
1 •1
Channels, noise, redundancy ••.•••••••••••••••••••••••••••••••
1.2
An introductory example •••••••••••••••••••••••••••••••••••••• 4
1.3
Some definitions in information theory ••••••.••••• · . . • • • • • • • •
1 .4
Shannon I s fundamental theorem. • • • • • • • • • • • • • • • • • • • • • • • • • • • • . •• 10
13
Problems.
CHAPI'ER II:
8
Linear codes
2. 1
General theory. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 15
2.2
Hamming codes •.
2·3
Reed-Muller codes •••••••••••••••.•••••••••••••••••••••.••• 27
2.4
Threshold decoding
2·5
Direct -product codes ••••••••••••••••••••••••••••••••••••••• 36
2.6
Problems •••••• • • • • • • • •• • •• • • • • • • • •••• • • • • • • • • • • • • • • • • • • • • 40
CHAPI'ER III:
20
32
Cyclic codes
Introduction
42
The zeros of a cyclic code
46
Idempotents ••••••••••••••••••••
49
Some other representations of cyclic codes ••.••••••••••••••••••
55
Problems ••••••••••••••••••••••••••••••••••••••••••••••••• 59
VI CHAPI'ER IV:
Important cyclic codes
. ... . ... . . . . . . . . ... .... ..... . . . . . .. ..... 61
4.1
BCR codes •••••••
4.2
Reed-Solomon codes •••••••••
10
4.3
Generalized Reed-Muller codes
15
4.4
Quadratic residue codes
19
4.5
Problems •••••••••••••••••••••••••••••••••••••••••••••••• 85
CHAPl'ER V:
Perfect codes
86
5.1
Perfect single-error-correcting codes.
5.2
The sphere-packing condition •••••••••••••••••••••••••••••••• 92
5·3
The Go.la.y codes •••••••••••••••••••••••••••••••••••••••••.
5.4
Lloyd's theorem
5·5
Nonexistence theorems ••••••••••••••••••••••••••••••••••••• 112
CHAPrER VI:
98
•••••••••••••••••••••••••••••••••••• 104
Weight enumeration
6.1
The MacWilliams equations ...•••.•.....•••..•••.
120
6.2
Weight enumeration of Reed-Muller codes ••••••••••••
122
6.3
The Carlitz-Uchiyama bound ••••••••••••••••••••••••••••••••• 121 References • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• 130 Index • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • •• 1 32
NCYrATION P(a) and Prob (a) denote the probability of the event a. Vectors are denoted by underlined symbols, e.g. (~,~)
a b
~,
l,
!.
is the usual inner product. is a product of vectors which is defined in
(2.3.1).
e(n) is the n-dimensional vector space (over a specified field GF(q)). Systems with binary operations are denoted by giving the set and the operation, e.g. (GF(q)[x],+, ) is the ring of polynomials with coefficients in GF(q) and addition denoted by + and multiplication denoted without a special symbol. For matrices A and vectors! the transpose is AT resp. xT • If a and b are integers then alb means Ita divides bit.
A := B is used when the expression B defines A. A C B does not exclude A = B. ] refers to the references at the end of the notes.
I. 1.1
INTRODUCTION
Channels, noise, redundancy The problems we shall be discussing, mostly of a mathematical nature, although
sometimes belonging to the field of electrical engineering, are part of the theory of communication.
In mentioning communication we think of many different things
e.g. human speech, telephone conversations, storage devices like magnetic tape units for computers, high frequency radio, space communication links (e.g. telemetry systems in satellites), digital communication with computers etc.
The problem concerns
information coming from a source and going to a destination called the receiver through a medium we refer to as a channel (telephone, space).
If the channel is
"nOiseless", i.e. every bit of information going in comes out unchanged, there is no problem but in practice this is not the case. and as a result
~
Noise is added to the information
are introduced by the channel.
For example in telephone con-
versations there is cross-talk, thermal noise, impulsive switching noise, sometimes lightning causes noise; in radio we have static; magnetic tapes sometimes have the wrong digits after storage etc. As an illustration we consider the following possible way of sending messages (think of teletype): we use 32 symbols namely a blank, the letters of our alphabet and a few punctuation marks (say 0 = blank, 1
= a,
2 = b, ••• ).
Any message in
English is converted into this code before entering the channel and back again afterwards as in the following model
source to Source----.....-...
binary to
binary
Channel
converter
destination~--~Destination
converter
where e.g. the letter m is converted into 01101 and later back again.
In the fol-
lowing we will no longer be concerned with the source and assume the information is presented as binary numbers
o~
something analogous i.e. there is a finite set of
2
information symbols at the source.
For us the channel is an abstract thing in which
noise is added according to specified rules.
To better understand what actually
happens we give one example. Consider the two time functions given by the graphs below.
... t
-tt
The first we identify with 0, the second with 1 and we let the functions denote the amplitude of a signal, e.g. the power emitted by a radio transmitter. the channel consists of verter.
seve~l
Remark that
components, one being a binary to waveform con-
Now the letter m is transmitted through the channel as the following wave-
form:
... t
letter m
Due to the addition of noise the following wave is received.
...t received signal
The receiver gets OltOl.
The decision on the third bit is difficult.
One possi-
bility is to make no decision at all and to declare what is called an erasure.
If
the receiver must make a decision (~ decision) it is possible that an error is
3
introduced, i.e. 01001 which is then converted into the letter i. situations information on how sure we are about each bit can be
In more refined
provide~.
In the following we shall be concerned mostly with the case where errors are introduced.
Even then there are several possibilities.
The easiest to treat is the
one where the errors are randomly distributed over the message.
For many practical
situations this is not a good model e.g. a flash of lightning will disturb several consecutive letters of a telephone conversation, errors on magnetic tape generally occur in bursts.
In this case we speak of
~-~.
We shall treat these later.
Normal spoken languages (in contrast to machine language, Morse code etc.) combat noise by using redundancy.
Most words, especially long words, contain more letters
than are necessary to recognize the word.
This feature will be the basis of our
theory resulting in the following communication scheme:
,r- -- ---
-- - - - - - - - - -
I
source to binary
binary to binary encoder
,
--j
binary to . Channel channel •
1 ,- _
_
_
-
-
For many channels we could settle for
-
-
-
binary - to destination -
-
-
-
~-detection instead
telephone where one can ask for a repetition of the message. way-channel or a channel with feedback.
We call this a two-
But if on a stored magnetic tape errors are
detected it is too late to ask for a retransmission. study will be
of correction as in
Hence the main object of our
~-correction.
An example of an error-detecting code which is well known is the code used on paper tape for computers.
~-~
There, after the information has been con-
verted into binary digits (bits) one bit is added such that the mod 2 sum of the bits is 0 (e.g. 01101 is changed into 011011). called a parity-check.
The redundancy is one bit.
This is
In case one error is introduced by the channel (no matter
in which bit) this error is detected because the sum of the bits then has the wrong parity.
4
1.2
~
introductory example
Consider a channel with an input alphabet a 1, a 2 , ••• ,
~
and an output alphabet
b 1 , b 2 , ••• , b - Suppose that each output letter depends statistically on the cort responding input letter only and according to a fixed probability_ We write p(bjlai ) := probability that b j is received if a is transmitted. i This is called a discrete memoryless channel (DMC).
We shall often consider the fol-
lowing special example of a DMC:
Output alphabet (b j )
Input alphabet (a ) i
o
o
q=l-p
This is called the binary symmetric channel (BSC). In our theory we shall assume that at the source each letter of the input alphabet has the same probability of occurring.
Remark that if a certain symbol would
occur more often than others it would be wise to use this knowledge in the construction of the code (as is done in shorthand). Now suppose our BSC can handle 2A symbols per minute - We wish to use the channel to communicate to a receiver the result of an experiment carried out in the room we are in.
A person is flipping a coin repeatedly at a speed of A times per minute.
Every time "heads" comes up we can transmit a OJ if "tails" comes up a 1. some number to work with, assume the charmel is poor and has p :: 0.02.
To have
Then the re-
ceiver will get approximately ~ of the information incorrectly. Of course there is time enough to repeat each message once. useless as far as error-correction is concerned!
This is obviously
Now consider the following
We wait until the coin has been flipped twice and then transmit as follows:
~.
5
Experiment result
Code message
HH
0000
TH
1001
HT
0111
TT
11'0
Except for a delay at the beginning we'll keep up with the experiment. gets the following
The receiver
if anything different from these four messages is
decoding~:
received then assume that one of the first three bits is in error.
This rule unique-
ly assigns one code message to every possible sequence of four zeros and ones.
Now
let us do some computation:
= q4
Prob (4 bits received correctly)
Prob (one error among the first 3 bits) = 3pq3 Hence
= q4 + 3pq3
Prob (correct decoding)
~
0.9188.
The receiver will get both experiments false if the last bit is received correctly and there are 2 or more errors among the first three bits. p3q + 3p2q2.
This has probability
There remains probability p that one of the experiments will come
through correctly. formation in error.
Therefore the receiver will get approximately '.1~ of the inQuite an improvementt
(But not best possible.)
Note that the receiver extracts two bits of infonnation about the experiment from every four bits received. (1.2.1)
DEFnrITION:
We say that the
infonna.tion-~ is
1
2' •
If we use a binary code of k words of length n (i.e. choose n k out of a possible 2 words) we shall say that the information-rate is n
We now continue with our example. executed and then transmit
8
-1
lo~
k.
We now wait until 3 flips of the coin have been
sequence of 6 bits a,a2 •• -86
of the experiment is identical with
8
1a 2a 3 ; a 4
= a2
+ a ,
3
as follows. 8
5
= a3 +
a"
The outcome a6
= a 1 + a2 •
6
(All additions are mod 2).
1
Just as in the first example the information rate is 2' .
For the received word (b"b2 ,···,b6 ) we wr1te b i • a 1 + e1 and call the ~-pattern. Now we have
(e"e 2 , ••• ,e6)
(1.2.2)
In
(1.2.2) we compute the left-hand side from the received sequence. The rule is:
of all possible error-patterns leading to the same left-hand side choose the one with the least number of errors.
This method is called
max~um-l1kelihood decoding.
The effect is as follows:
a)
(g)
b)
(~),(D,G); one error among a 4,a5 ,a6, probability is 3q5p, error is corrected,
c)
(D,(!){~} one error among a ,a2 ,a3,
d)
(D
no errors
, prdbability is
1
assume e"e 4 are false
6
q ,
probability is 3q5p, error is corrected.
, probability is q4p2 •
Apparently any single error leads to correct decoding!
What about double errors?
We must distinguish between a)
2 errors among first
thre~ say e2 = e 3 = 1.
the error pattern were
a)
y)
(1,0,0,0,0,0). Final result:
2 errors among last three, say e the error pattern were
This leads to
4
= e 5 = 1.
(!), decoded as if
all three wrong!
This leads to
(1) , d~coded
as if
(0,0,1,0,0,0). Final result: two correct, one false.
one error in first three, one in last three. which are decoded as if the error pattern were
This leads to either
(~) or (~)
(1,0,0,',0,0) resp. (9,0,0,0,0,1).
In the last case two experiment-results are interpreted correctly.
In the first
7
case either both errors are corrected as mentioned in d) above or two more are intraduced.
Since p is small we do not calculate what happens if 3 errors occur.
The average percentage of incorrect information at the receiver is now about 0.29'/J.
The normal question to ask at this point is: "Can we get the percentage of
error down as low as we wish using information rate
1/2'"
We shall now answer this
question. First a definition:
(1.2.3)
DEFINITION:
Consider the space (O,l)n consisting of all sequences of n zeros and ones.
In this n-dimensional vector space (addition
mod 2) we define the Hamming-distance ~(~'l) of two vectors
! and l to be the number of places in which these vectors differ. Note that with ~ as distance {O,l)n is a metric space.
(1.2.4)
DEFINITION:
For p >
° and ~ ~ {O,l)n we define the sphere of radius p with
center at ! by
If, on continuing with our example, we wait until m flips of the coin have been ex-
ecuted and then transmit 2m bits,
suppose we succeed in choosing the code in such a
way that for each pair of distinct code words ~ and
does this mean?
!
we have ~(~,Z) ~ 5.
What
The effect is that if a received word contains less than 3 errors
the transmitted word can be determined by maximum likelihood decoding because there is exactly one code word at a distance
~ ~
2 from the received word (by the tri-
angle inequality. , q2m-l P + ) The probability of correct decoding is now q2m + (2m) 2m 2m-222m 3 (2 )q P A1 1 - (3)P if m is not too large and p is small. So, much depends on how large m must be to achieve this proerty of correcting 2 errors.
We shall not
attempt to find m but we shall find the answer to our question in .ect1on 1.4.
8
1.3
~
definitions in information theory
Let X denote
8
probability space consisting of the set (a, ,82 , ••• ,~} with
probabilities PX(a ), i = 1,2, ••• ,k and let Y be the probability space consisting of i
(b"b , ••• ,btl with probabilities Py(b j ), j 2
= 1,2, ••• ,t.
Also let a probability
measure Pxy be given on the product space of pairs (ai,b j ).
Note that there are
several relations connecting these probabilities e.g.
t
P (a ) = X 1
L
p xy(a ,b )
1
j=l
(1
j
= 1, ••• ,k),
if we interpret (ai,b ) as the outcomes of a 2-outcome experiment, X denoting the j
first outcome, etc.
As usual we denote the probability of the occurrence of the
event ai' given that the outcome of the second alternative is b j by p(ailb j ) or Clearly
( 1.3.2)
We recall that the events x
=ai
and y
=bj
are called statistically independent if
i.e. Now in the situations we are interested in the a the b. outputs. J
i
will be inputs of a channel and
Usually we shall consider situations where all the px(a.) are equal ~
but right now we do not assume that yet. last thing we want.
Of course in this case independence is the
In fact if the output is some b j we would like to be certain
about the input (noiseless 'channel).
To measure what a certain output tells us we
introduce the quantity
and call this the information provided about ~
the occurrence of the event y
information of x
= a.~
and y = b .• .J
= bj
2
~
x = a
or also the mutual
i
9
Examples: (b)
(a)
In the case of independence no information is provided and I
C
OJ
For a noiseless channel the probability spaces X and Yare identical and
Ix , yeS,S) (1.3.5)
'" lOg2
~ ~x\SJ
DEFINITION:
•
IX(ai
) :'"
event x Example: ity 2-
n
i
ai-
)
is called the ~-information of the
If X is the set of all binary sequences of length n, each having probabilthen the self-information of one sequence is n, i.e. the number of bits of
that sequence.
(1.3.6)
c
1
log2 PX{a
For this reason information is generally measured in bits.
DEFINITION:
The quantity k
I(X;Y) :'"
t
2: 2:
pxy(ai,bJ)IX,y(ai,bJ)
i=l j=l
is called the average mutual information. Analogously (1 .3- 7)
DEFINITION:
The quantity
k
H(X) :=
2: i=l
k
-2:
PX(ai)log PX(a ) '" PX(ai)log PX(ai ) i i=l
is called the average self-information or entropy of the probability space X. We shall not go into the connection with the use of the word entropy in thexmodynamics.
A. I. Khinchin has shown (cf. [ 8 ]) that if one wishes to measure uncer-
tainty and requires this measure to have a few natural properties there is only one function with these properties, namely the entropy function.
Naw as was suggested
above interpret X and Y as input and output of a discrete memoryless channel. the PylX(b j fa ) depend on the channel. i (i = 1,2, ••• ,k) any way we like.
(1.3.8) DEFINITION:
Here
We can still choose the probabili~ies PX(a i )
This leads us to:
The maximum average mutual
information I(X;Y) over all pos-
sible input probabilities is called the capacity C of the DMC.
10
It should now be plausible that C is a measure for the amount of infonnation the channel can handle in one use. Let us compute C for the BSC with error probability p. Then by
Let PX(o) = x
(O~x"S.l).
(1.3.4) and (1.3.6) we have 1 -
p.
p}
I ( XjY ) = x.{ ( l-p) log x(l-p)+(l-x)p + P log xp+(l-x)(l-p)
= P log P + q log q - (x(1-p) + (l-x)p)log{x(l-p) + (l-x)p}
- {xp + (l-x)(l-p»)log{xp + (l-x)(l-p») and this is maximal if x =
2'1 in which case we find
(1.3.9) The capacity of the
BSC with error probability p is 1 + P log P + q log q
(where q := l-p as usual). Sometimes
(1.3.9) is given as definition with no further comment. We hope the above
explanation makes the word capacity a little less vague.
1 .4
Shannon's Fundamental Theorem Consider once again a BSC with error probability p, (0 < p <
~). Suppose we
have a code consisting of M vectors chosen from {O,l}n with some decoding rule.
Let
Pi denote the probability that an error occurs (after decoding) if .!1 is transmitted. Then the probability of error when using this code is M
(1.4.1)
Perror
-1 \'
=M L
Pi·
i=l
We now define
(1.4.2) P*(M,n,p)
:= minimum of Perror over all codes with the given parameters.
We can now fOImulate Shannon's first theorem which is the basis of the rest of this course.
Let C be the capacity of the BSC, defined in
(1.3.9).
11
(1.4.3) THEOREM (Shannon): Let M -
if n
n
Then P* (M ,n,p) ~
:= 2[Rn] where 0 < R < C.
--
n
°
~ 00.
Note that this means that there is a sequence of codes with infonmation rate tending to R and error probability tending to 0.
Or in other words: given
there is a code with rate> R and error-probability < We now prove this theorem.
€
> 0 and R < C
€.
Before giving the main idea of the proof we isolate
a number of the more technical details to be used in the main part of the proof. If a code word is transmitted over the channel then the probability of a specific error pattern (at the receiver) with w errors is pwqn-w, i.e. this probability depends only on the number of errors.
Remark that P(~ll)
= p(ll~).
errors in received words is a random variable with expected value np np(l-p).
If b :=
(~~_p»)1/2
Prob (w > np + b) ~ 2"
Let p := [np + b].
and variance
then by the Bienayme-Chebyshev inequality 1
(1.4.4)
The number of
€.
By (1.2.4) the number of points in a sphere S (x) is P -
Isp (x) I -
(1.4.5)
=
I WSP
The last inequality follows from nn
n
n pP (n-p )n-p
(n) < .!. n(n) < .!. n w 2 p - 2
= (p
+ n_p)n
We have
(1.4.6)
.£ log .£ n n
= [np
=P
+
n
b1
log
Wp
nJ
b {log p + log (1 + b 1 + O(n) 1 (p +:Ii) J
+ b]
n
A
log P + O(n-~).
p , log ( 1 - -p) = q log q + ()( n -1/2) • and Analogously ( 1 - -)
n
n
We introduce two auxiliary functions.
(1.4.7)
f(~,!)
. = {o
If ~i is any vector in the code and!
(1.4.8)
1
If ~
E {O,l}n, v E {O,l}n we define:
if
<1I(~,!)
>
p ,
if
<1I(~'!)
S.
p •
E (O,l}n then
gi (l:) := 1 -
f(l:'~i) +
I
j~i
f(l:'!j).
12
Remark that gi(Y) -
0 if ~
I::
-...
e Sp(y) -
and no other code word is in this sphere and
otherwise gi (l.) ~ 1.
Now we come to the main part of our proof.
We choose the code words !.1'
••• , ~ at random from {O, l)n and use these to transmit M possible messages.
~i
with distance
Sp
to 1.. then l.. is decoded into !i·
is declared (or one could always take !.1 in this case). probability of incorrect decoding when !.i is transmitted. following
The
If l is received and there is one
decoding rule for the receiver is as follows. code word
~,
Otherwise an error
Again, let Pi denote the We have, by the remark
(1.4.8), Pi
~
I
p(ll~i)gi (l)
lE{O,l}n
=
I p(ll!.:!.){l - f<'~>~i)} I I +
l
l
j~i
f(l'~j )p(ll!i)'
The first sum on the right-hand side is just the probability that l is not in Sp(~i). This number does not depend on xi but only on p.
ex < P -
1
-2
-
Call it ex. p
By
(1.4.4)
we have
€.
Now by (1.4.1) P error
1
S2'€
+M
M -1 \'
I I p(ll!i )f(l'~j)'
L
1.. j~i
1=1
We now calculate the expected value of the right-hand side and remark that P* (M,n,p) can not be larger.
Since the !.i are chosen at random they are independent variables.
Hence we have
* P (M,n,p)
M
~
1
2'
€
-1 \' + M
L
1=1
1 = 2
€
I I E(P(ll!.t»E(f(Z,!j» .. l
j~i
I + (M-1)2 -nl Sp.
13
Now take logarithms (base 2), use
By definition of Mn we have n
-1
(1.4.5) and (1.4.6) and divide by n. We find
log Mn - C + ~(n
-1/2
) <
-a
< 0 for n > nO'
i.e.
This completes the proof.
1 .5
Problems
(1.5. 1) Consider the vectorspace {0,1}6 with Hamming distance. What is the number of points in a sphere of radius 1?
Is it possible to find 9 vectors such that for
Consider a BSC with error probability p (0 < p < 1/2).
(1.5.2)
We wish to txansmit
two possible messages 0 and 1 by using a repetition code of length 2n + 1, i.e.
o=
(0,0, ••• ,0) and 1
decoding. (1.5.3)
Prove
= (1,',1, ••• ,1). P
l~
n ..
00
n
Let P
n
denote the probability of incorrect
= O.
Consider a ESC with 10% error probability.
6
coded using words frem {0,1 J
•
Four possible messages are
What error probability can be achieved?
( 1 .5.4) We wish to transmit 0 1 S and 1's over a binary erasure channel with 1cJ%, erasure probability
(i.e. if a 0 or 1 is transmitted there is probability 0.9
o. 1
that it is received correctly and probability
mission with information rate 1/2 is acceptable.
that a ? is received).
Trans-
Does repeating each bit help?
Can we do any better?
(1.5.5) Consider the code with 8 code words a5
= a,
+ a , a6 3
= a,
+ a2 -
probability p of erasure.
{O,1}6 defined
2 + a 3, Let this code be used over an erasure channel with €
by a
4
= a
Determine the probability of correct decoding.
Compare
this with repetition of each bit. (1.5.6)
The entropy of a discrete probability space is maximal if all probabilities
are equal.
Prove this.
14
(1.5.7)
Consider the alphabet
{O,1,2).
they form a single-error-correcting code.
Try to find 9 four letter words such that
II. 2.1
LINEAR CODES
General Theory In this chapter we construct codes for a discrete memoryless channel for which
the input and output alphabets are a set of q symbols where q is a power of a prime, q = po..
In this case we can identify these alphabets with the elements of GF(q).
We are going to construct block codes, i.e. codes in which all code words have the same length n which is called the
~
length or
~
length.
Let R be the vector space of dimension n over GF(q).
A subset V of R is an
e-~r-correcting-codeif \ . Ev Vl.EV[(~ ~ ~) .. (<'\r(~1:):: 2e+l)] where the
Hamming distance <'\r is defined as in (1.2.3). than others, (2.1.1)
(If certain errors are more likely
Hamming distance is not a good distance
DEFINITION:
function to use!)
A k-dimensional linear subspace V of R is called a linear code or (n,k)-code over GF(q).
Linear codes are group codes (V is a subgroup of
(R,+».
In general a group-code V
is a subgroup of the direct product of n copies of an additive abelian group G. Since most of the codes we shall be studying in this course are linear codes it will be useful to go into the general theory first and find simple representations of such codes. (2.1.2)
DEFINITION:
The Hamming-weight
w(~)
of a vector!. E ~ is the number of
coordinates different fram O. The first advantage of linear codes compared to other codes is the following property. (2.1.3)
For a linear code VcR the minimum distance of different code vectors is equal to the minimum weight of all non-zero code vectors.
Since the minimum distance of the code determines the number of errors that can be corrected when using maximum likelihood decoding, it is convenient to have this easy way of finding the minimum distance.
Of course if e.g. q
cannot inspect all code words to find the minimum weight ~
= 2,
n
= 100,
k
= 80
one
16
In the following we shall generally take q = 2 as an example but the theory
holds for all fields GF(q).
One advantage of GF(2) 1s that we can change any - sign
into + if we prefer that. We shall now look at two ways of describing the code V.
The first is to take
a basis of the linear subspace V and to form the matrix G where the rows of G are the basis vectors of V.
The matrix G is called the generator
E.g. G :=
(~ ~ ~ o
0
1
0
~
of the code.
~1'~ )
is the generator matrix of a (5,3)-code over GF(2). Since the property we are most interested in is possible error-correction and this property is not changed if in all code words we interchange two symbols (e.g. the first and second letter of each code word) we shall call two codes equivalent if one can be obtained by applying a fixed pennutation to the words of the other.
With
this in mind we see that for every linear code there is an equivalent code which has a generator matrix of the form G
= (J1tP)
where J1t is the k by k identity matrix and P is a k by (n-k) matrix. given above is of this type.
The example
This is often called the reduced echelon form of G.
At this point we should remark that as far as error-correction is concerned the code does not change either if in any coordinate place we change all o·s into 1'8 and vice-versa.
The resulting code is no longer linear.
In fact what this
t~ns-
formation amounts to in the binary case is adding a fixed vector to all code words i.e. looking at a coset of the linear subspace instead of the subspace itself. (This more general equivalence will be used in Section 5.1). Now a well known theorem from linear algebra states that i f V is a k-dimensional linear subspace of
R then there is an (n-k)-dimensional subspace
V~ of
V~ EY VY.. EY.L [(~,l) = 0] where (~'l) denotes the usual inner product. the orthogonal complement of V.
R such that
r
is called
We warn the reader that it is no longer true, as in
spaces overm, that each vector in R is the sum of a vector from V and a vector from
17
In fact it is possible that Y and yJ. coincide.
yJ..
If V = y~ then y is called self-dual.
of Y.
The code yJ. is called the dual
To avoid confusion we warn the reader
that often, when speaking of the dual code the order of the symbols is reversed. Why this 1s done in certain instances will become clear later. A generator matrix H of the dual V is called a V.
~-check
matrix of the code
For instance for the example given above
C0010) o
H := is a :parity-check. matrix.
If G =
(~p) then we can take H = (_pT1n _k ). Remember
that the single parity-check code mentioned in Section 1.1 had the property that
= ° (addition
(a 1 ,a2 , ••• ,a6) was a code word iff a, + a 2 + ••• + a6 has now been generalized.
A word
~
ea
in GF(2».
This
is in the code V iff it is orthogonal to
every row of H, i.e. T
(2.1.4)
(~H
= 2)
~ (~ E V).
Here {2.4} is a system of n - k linear equations which must be satisfied if x is a code word.
These are called the
! HT the syndrome of~.
~-check
equations.
Then 3S. E V iff the syndrome is Q.
elon form makes it very clear what is actually happening. (a"a2 , ••• ,an ) by choosing al,a2' ••• '~ arbitrarily.
For any
~
E R we call
Using the reduced echWe can make a code word
Then either G or H tells us
the rest of the word namely (using G) we have to take a 1 times the first row of G + a 2 times the second row etc., respectively (using H) we have ~+1 P2,a2 ••• -Pkl~ etc. according to (2.4).
= -Pl,a,
-
So the bits a1,a2' ••. '~ carry the in-
formation and the remaining n - k bits are the redundant part which is there to help correct errors.
The rate of information (q = 2) is apparently kin.
We have here an
example of what is called a systematic code i.e. one for which a subset of symbols can take on arbitrary values (these are the infonnation symbols) and the other symbols are then detennined ( ~ - ~ symbols). is a
(6,3)
The example described by (1.2.2)
code over GF(2) with parity check matrix H
=
(
0
101
1
1
0
1
1
1
0
0
0
1
°
0) 0
1
18
The reader who now thinks we have embarked on a study of a trivial part of linear algebra can try to find the minimum weight of a linear code from the generator G. This should be sufficient to change his mindt
Now consider the problem of correcting errors in a linear code.
Let us take a
particular error-pattern, i.e. a vector in R and add it to all the code words. resulting set is a coset of V in the additive group pattern the coset is ! + V :== T ( !, + ~)H
drome.
= (!2
T
+ ~)H
= ~HT ,
(!
+ !
On the other hand, if !:!IT
THEOREM:
If e is the error-
If!l and ~ are in the code then
i.e. two vectors 1n the same coset have the same synI:
!. and 1. are in the same coset of V. (2.1.5)
I ! E V}.
(R,+).
The
T tfiT then (! - l)H == Q, i. e.
~ - lEV and hence
We have proved:
Two vectors ~ and l. are in the same coset of V iff they have the same syndrome.
The next important remark is that the error-pattern
~
is itself in the coset e + V
and any vector in this coset could be the error pattern. ment take !, E V.
To prove the last state-
Then (!., + ~) + V :: ~ + V since y, + V == V.
The last remark now
tells us how to proceed when using maxtmum likelihood decoding.
If we wish to find
an error-pattern which changes the words of V into the words of a particular coset then the candidates are the words of minimum weight in this coset. we choose such a word and call this word the coset leader. array:
For each coset
Consider the following
(i) in the first row we write the words of the code, starting with
Q (which
is the leader of the coset V); (1i) in the first column we write the coset leaders
Q,
_e l , --c ~~, •.•
word !j.
(iii) in the row with leader -J. e. we write e.J+. v under the code j
This is called the standard array.
used in Section 1.2.
As an example we take the first code
This is a linear code with G = (
~ ~ ~ ~).
array corresponding to the decoding rule we used is: 000 0
1 0 0 1
1 000
o
1 0 0
001 0
o
1
1
1
0
o0 0 1
1 1
1
o
0
1 1 0 1
o
0 1 1
100
, 0 1 1
o
1 0 1
1 1 0 0
The standard
19
For the receiver this array is a dictionary to be used as follows: decode a received word into the code 'o1ord at the top of the column containing the received word.
Note
that in this example the coset leaders are uniquely determined except in the second row where we could have taken 0001. For any code a complete dictionary is the least sophisticated way of providing a decoding rule.
We can now find something much simpler for linear codes by recall-
ing that words in the same row of the standard array all have the same syndrome, this being the syndrome of the error pattern which is the coset leader. (2.1.6) THEOREM.
Hence
For a linear code a maximum likelihood decoding rule is completely described if a list of coset leaders with their syndromes is given.
The way to use (2.'.6) is: (i) If ! is received compute the syndrome ~Tj (ii) look up the syndrome in the table to find the error pattern~; (iii) ~ - e is the code word. n For an (n,k)-code over GF(2) a complete dictionary consists of all possible 2 words whereas the list of (2.'.6) has only 2
= 100,
good codes are long e.g. n
k
n-k
= 80
words and their syndromes.
In practice
and then the list of (2.1.6) WQuld still be
much too long to be of practical use. We have seen that the coset leader is not alway? uniquely defined.
To change this
we use an idea of E. Prange and D. Slepian.
Number the elements of GF(q) from 1 to
q giving the field element 0 the number q.
Now in every coset choose as the leader
the minimal weight element which cames first lexicographically. an interesting theorem. (2.1.7) DEFINITION:
We can now prove
First we define
If ~
E R, 1. E R then we define !
~~!
:-
Vi,l~i~[Xi
= Yi
or Xi
~
1. by
= 0].
Then we have (2.1.8) THEOREM: ~:
If 1. is a coset leader and!
-< I
then! is a coset leader.
It is sufficient to prove the theorem for the case w(1. -
In this case let l. - !
=~.
!) = 1.
Every vector in the coset. 1. + V can be obtained
20
by adding! to a suitable vector in
~
+ V_ Since all vectors in l. + V have
weight ~ w{Z) no vector in ! + V can have weight less than w{r) - 1 i.e. ! has minimal weight in its coset.
Now let ~ ~ 0 and e
If ! is a minimal-weight vector in ! + V then! + tor in 1. + V and hence ~ =
o. If!
~ ~ then !. +
after l and hence ! is lexiocraphically after!_
i
=0
= w{!),
for i ~ k.
~
is a minimal weight vec-
!
is lexicographically
This proves the theorem.
A decoding algorithm called step-by-step decoding is based on the above definition of standard array and (2. 1 .8) • We refer the -interested reader to [ , 5 ], Chapter 3.
2.2
Hamming
~
Let H be the parity-check matrix of a binary linear code. transmitted and received with error-pattern
~
(i.e. ! +
drome as defined in the previous section is ~HT.
~
If a code word
~
is
is received) then the syn-
This syndrome is just the (trans-
pose of the) sum of those columns of H corresponding to places where errors have occurred.
Therefore an error in a place corresponding to a column of zeros in H
does not influence the syndrome and hence such an error is not even
detected~
If H
has two identical columns and in the corresponding places errors are made the syndrome is again Q., i.e. these two errors are not detected.
If, on the other hand,
all columns of H are different then a single error in the k-th coordinate results in the syndrome being the k-th column of H. ized and corrected.
Therefore the single error can be local-
Therefore every weight one vector is a coset leader.
An other
way of seeing this is to remark that a linear combination of columns of H can be Q. only if the number of terms with nonzero coefficient is at least three or in other words
T
~
=
Q. implies w{?f.)
~
3-
Therefore the minimum distance of the code is at
least 3 and the code is single-error-correcting. We have thus given two proofs of (2.2.1) THEOREM:
A linear binary code can correct all IBtterns of not more than one error iff all columns of the-par1ty-cheCk matrix are different and nonzero.
21
If H has r rows, i.e. the number of parity check symbols is
~
r then clearly H can
have at most 2r _ 1 columns if they are all to be different and nonzero. (2.2.2) DEFINITION: A binary linear code for which the columns of the parity check matrix H are the binary representations of 1, 2, ••• , 2r_ 1 is called the (2r_ 1, 2r- 1-r) Hamming code. The (7,4) Hamming code has the parity check matrix 0 0 0 H:=
(
1 1 1
0
1 1 0 0 1
1
0
1
010
If a word! 1s received and ~T is the binary r~resentation of the integer k then the most likely error pattern 1s one error in the k-th place.
Note that this is a
tremendous improvement compared to (2. 1.6) since now knowledge of H is sufficient for the decoding
rule~
If in the case of the
the
pe~utation
(7,4)
code we wish to generate the code words we apply
(4,5)(6,2)(1,7) to H to obtain the form with I
G as described in Section 2. 1 and permute back.
G =
1 0 1 0 0 1) 1 0 1 010 ( 1110000 100 1 100
o1
3
at the end, obtain
We find
' 00 0 0 01 01 11) .010 or after some linear combJ.nation 0 0 1 0 , 1 0 • ( 0001111
From this last form of G it is obvious that all code words have weight Hamming codes have a remarkable property.
~
3-
The
Not only are the spheres with radius one
and centers at the code words disjoint but they also fill the whole
~ace
R,.
Such a
code is called perfect. (2.2.3) DEFINITION: If an e-error-correcting code VcR has the property
u
s (x) :: R ! EVe then the code is called perfect. If r is the number of parity-cheCk symbols of a Hamming code then the block-length n is 2r_ 1. The number of information symbols is 2r _ 1 - r and the rate is therefore
22
r
1 - -r-- which 1s nearly 1 for large r.
The proof that a
2 - 1
Hamming code 1s perfect
follows from the equality 2
n
= (l+n).2k
if
n = 2
Of course a consequence of the fact that a not detect any pattern of two errors:
r
- 1 and k
= 2r
- 1 - r.
Hamming code is perfect 1s that it can
A very simple device will remedy this, namely
the addition (to every word) of one more check symbol which 1s the sum of the other symbols.
If we call this symbol &0 then the new parity check matrix is 1 1 1 1 1 ••• 1
o
o o
H
o Since this extended code obviously has minimum weight of 2 errors.
4 it can detect all patterns
One way of using such a code is to employ an incomplete decoding rule
which corrects all error patterns of weight
~
, and which declares a decoding fail-
ure in case 2 errors are detected. The idea behind Hamming codes is not restricted to binary codes.
An as exam-
ple we take GF(3) and construct all nonzero columns of r elements of GF(3) with the restriction now that (starting from the top) the first nonzero element is always 1.
The number of columns of this type is n := ~ (3 r _ 1).
Once again a linear combin-
ation of two of these columns, with coefficients 1 or 2 cannot be we take H to be the matrix with these columns then ~T
Q.
Therefore if
= Q implies w(~) ~ 3,
H is the parity check matrix of a single error correcting code over GF(3). again
I8 1 I = 1 +
2n
the code is perfect. (2.2.4) THECBEM:
=
n-k 3 =3 where k is the dimension of the code. r
i.e. Once
Therefore
The same proof holds with q instead of 3.
H9mIIl1ng codes over a field GF(q) are perfect codes.
The (13,10) ternary Hamming code provides a solution to the football-pool problem for 13 matches. (In some countries this is the actual number of matches in the pool~)
In a football pool one forecasts the outcome of a number of (Soccer)-matches:
23
o = draw,
1
= win,
2
= lose
(for home team).
To be sure of first prize (all correct)
there is no alternative but to enter all 313 possible forecasts. clear that for second prize (12 correct) it suffices to enter 3 fact 3
10
are enough!
Since the (13,10)
13-dimensional space over GF(3) has
A priori it is
12
forecasts but in
Hamming code is perfect every word in the
Hamming distance at most 1 to some code word.
Using the code words as forecasts therefore guarantees 2
nd
prize.
The football pool
problem is to determine the minimal number A(k) of forecasts necessary to guarantee 2 k
nd
prize if k is the number of matches. 1
=2
(3
r
- 1).
Apparently the problem 1s solved for
Besides theee onlyA(2), A(3) and A(5) are known.
A(5) == 27 takes 10 pages.
(cr. [
7 ]).
The proof that
We will return to this problem in Section
5.1 • We have seen that the error-correcting capabilities of a linear code depend on the minimum weight of the code.
If more is known about the weights of the code
words we can provide infonnation about the probability of error.
For this purpose
we introduce (2.2.5) DEFINITION:
If Ai denotes the number of code words of weight i in a code
then
n
A(z) := .
I
AiZ
i
i=O is called the weight enumerator of the code; (n is the block length). Consider a code with minimum distance d ~ 2t + 1, weight enumerator A(z) and suppose the decoding algorithm corrects up to .t errors and otherwise fails. easily compute the probability that the error-plttern has weight
~
Since we can t we can find
the probability of a decoding error by computing the probability that the error pattern is in a coset with a leader of weight and we change
~
of the "s to O's and
~
~
t.
If
~
is a codeword of weight i
of the O's to 1's we obtain a vector of
weight 1 - ~ + ~ with distance ~ + ~ to~.
Let Ai(j,k) denote the number of words
of weight k with distance j to a specific code word of weight i.
We have
24
I
(2.2.6)
i
I I (~)(n~i)s~Tli-~ =
l>i(j,k)~j,f = k
j
n-i
\)=0 t.4=0
The probability that the error-pattern is ina coset with a leader of weight
St
is
then (for a BSC with error probability p): t
n
n
L
L
k 'nk AiAi(j,k)p (l-p) - •
\~\
L
j=O i=O k==O In order to calculate this probability we introduce the polynomial pt(X) of degree ~ t
by
n
t
Pt(x) :=
n
I I I
j=O i=O k=O
A ·A (j,k)l(1-p)n-kx .1.
i
i
Note that pt(X) is obtained by truncating Pn(X).
Pn(x)
=
n
I
A (X-xp+p)l(l-p+xp)n-i
i
i=O
(2.2.7)
We have by (2.2.6)
+ = (l-p+xp) n A(X~1-p+xp
Example:
').
Consider the BSC of Section 1.2 and suppose we use the
(8,4)
extended
Hamming code (rate 1/2) with the incomplete decoding algorithm which corrects one error. , + 14z
By inspecting the generator matrix we immediately see tha:t A(z) ==
4
8
+ z.
From (2.2.7) we find P (x) and by truncating we find the required
8
probability P,(l) that the decoding procedure does not fail.
The result is
Prob( correct decoding) == (1_p)8 + 8p( l-p) 7 == 1 _ 28p2 + 112p3 _ 21 Op 4 + ••• • Prob(decoding) == (1_p)8+ 14 (1_p)4p 4+ p8+ 8(1_p)7p + 56(1_p)3p 5+ 56p3(1-p)5+ 8p7(1-p) == 2 = 1 - 28p + 166p3 - 476p4 + ••• • Prob{decoding error)= 54p3 - 266p4 + ••• = 0.00039, i.e. about 0.04% while Prob (correct decoding) ~ 0.9897 so that the other 1.03
%is
practically completely decoding failure.
We shall now calculate A(z) for the binary Hamming codes.
°If we take i - 1
25
columns of the parity check matrix H then there are 3 possibilities: (i) the sum of these columns can be 0, (ii) the sum of these columns can be one of the chosen columns, (1ii) the sum of these columns can be equal to one of the remaining columns. n
The total number of possible choices is (i-1).
Possibility (i) can occur in A _1 i ways, possibility (i1) in (n-i+2)A _2 ways and possibility (iii) in iA ways. 1 i Therefore
(2.2.8) Obviously An- 1 + An = 1 and therefore (2.2.8) also holds for i > n. Multiply both i-1 sides of (2.2.8 ) by z and sum for i = 1,2, ••• ,n+2. The result is 2 A ' ( z) = (1 +z)n - A( z) - nzA (z) + z A / ( Z )
•
Since A(O) = 1 the solution of this linear differential equation is n-1
A(z) =
(2.2.10)
n+1
-1(l+z)n + ~1 (l+Z)~(l-z)~ n+1 n+
Let us now use this result to calculate the expected number of errors per block 1n a. Hamming code of block length n = 2m - 1. Look at the standard array described in Section 2.1.
If an error pattern of weight i is a code word then none of the
errors are corrected.
If an error pattern of weight i+ 1 is under a code word of
weight 1 then one error is corrected.
If an error pattern of weight i-1 is under
a code word of weight i then the decoding algorithm introduces an extra error! Therefore the expected number of errors 1s n
E :=
~ L
i=O
iA i {Pi q n-i + ( n- i) p i+1 qn-i-1 + ip i-1 q n-i+'}
n
q
n ~
{i L iAix
1=0
we then have
+ (n-i)x i+1 + ix i-l} .
I
=
26
E = Qn1
(2.2.11)
n~l
(1+x)n-1 -
n~l
n-3
n-1
(1+nx)(1+x)2(1-x)2 ] +
n-5 n-3 3 [~( )n -2 n (n -1 ) , 2 ) ( )2( ) + (x-x ) ---rn+fJ 1+x + ~nx +2x-l '+x l-x 2 ] } •
i.e. 2
E =
(n-1)~ +
1)[
n~l
n-1
(1 - (1 +
(n-1)p)(1-2p)~
]
+
Now let us see how this expression behaves if we let n and p vary, np and n -+
=0
(fixed)
Then
00.
E-+[l - (1-+a)e
=0
-ex
] +0[1 -e
+ [1 - (l+2a)e
-ex ]
-a].
Now remark that a is the expected number of errors per block before decoding.
0> 1.2564 •••
the
te~
If
in square brackets is positive, i.e. the expected number of
errors per block is larger after decoding than before!
With this e.xam.ple we hope to
have made clear that it is useful to compute these error probabilities and also that we need codes which are much better than the Examples:
Hamming codes.
For the ESC with p = 0.02 and the (7,4)
of errors per bloCk before decoding is 0.14. a reasonable improvement.
Hamming code the expected number
After decoding this is
0.02~which
is
For the (3 1,26) code these numbers are 0.62 and 0.407
which is already disappointing.
For the (127,120) code we find 2.54 and 3.06, i.e •.
the code is useless! If P is small the following
est~te
which is easier to obtain than (2.2.'1)
will be good enough for later applications. of length n = 2m•
We consider the extended Hamming code
If an error pattern of weight i
S 1 occurs the decoded word con-
tains no errors, if 1 = 2 nothing happens and the decoded word contains 2 errors. In other cases it is possible that decoding increases the number of errors by one.
Therefore the expected number of errors per block after decoding is at most
27
E*
n
i n-i := 2 (n) 2 P2 qn-2 + \L ( i+1 )(n) i P q
=
1=3
( n) 2 [n-2 = 2 2 P q +
(2.2. 12)
r
n 2 n-2 ~ 2(2)P _q
~
i~3
(i+
1
)(~)
2(~)
p
i-2 n-iJ q S
n ~ (n-2) i-2 n-iJ + i-2 P q
L
= n ( n-1 )p2
2 < (np) ·
1=3
.
This estimate will be used in Section 2.5 .
2.3
Reed-Muller codes Let n
= 2m and
let R(m) be the m-dimensional vector space over GF(2) and R(n)
the n-dimensional space.
Just as in Section 2.2 we consider an m by n matrix in
which the columns are the binary representations of the integers 0,1, ••• ,~-1. We now take the least significant bit first.
!1 1
~I
~1' ~,
"'1
~
= i~1
..JIl-l
••• , u denote the columns with number 1, 2, 4, ..• , ~
R(m) ) then the vector in position
j
~....
=
m
(that is the stan-
t ~i.2 i=l J
1-1
is
~ij~'
In the space R(n) we define
(2.3.1)
If
in R(n) and the columns are all the vectors of R(m).
dard basis of the space m
.!oj
The rows of this matrix are vectors
DEFINITION.
If a ab
Remark that for all
8
multiplication as follows:
= (80 ,a"
••. ,an _1 ) and £ = (bo,b" .•. ,bn _,) then
:= (aObo,a,b" ••• ,an_lbn_l).
~ e R(n)
we have
~2 = !:.
Let Ai be the subset of R(m) consisting of those vectors which have a 1 in position i, i.e, Ai :=
{~j E R(m), ~ij
as the characteristic function of Ai. characteristic function of A.
J.,
= 1}.
We can then interpret the vector
In this interpretation !i!i
n Ai n··· n Ai. 2
K
• ··!1
12k
Yi
is the
This last set is the subset of
R(m) consisting of the vectors which have l's in all the positions
il,i2/""~'
28
This is an (m-k) -dimensional affine subspace of R, (m) and therefore consists of
vectors of R(m) (of course here we must assume that
il,i2""'~ are
zn-k
distinct). We
have proved:
(2.3.2) LEMMA: w(v v.
-il-~2
m-k . •• ~ ) = 2 • K
In the following we shall need affine subspaces of R(m) defined by fixing certain coordinates, the others being free.
We can describe these using the Ai and their
complements but to have a compacter notation we introduce
(2.3.3)
DEFINITION:
C(i 1,i2,···,ik ):= set of all integers J which ~ij
=0
m
= i:l ~iJ2i-l
if i ~ (il' .• ·'~}. (The set
(i" •.. ,~}
for may
also be empty). As usual we denote {x + a
I
x E C} by C + a.
With this notation we have for example:
The subset (x.} of R(m) has as characteristic function the vector -J
~J = (0,0, ••• 0,1,0, ••• ,0) E R(n) introduce the vector
with a 1 in position J, (j
!o := (1,1, ••• ,1),
= O,l, ••• ,n-l).
We
i.e. the characteristic function of R(m).
Then we have
(2.3.4) m Each of the 2 basis vectors e. of a(n) has thus been written as a product Which, -J
on expansion, yields a polynomial of degree
(interpreting
!o
as unity).
~
m in the vectors !1'
Since this is a set of 1 + (~) + .•• + (:)
{!o' !1' •.• , !m' = 2m =
!m
(2.3.5) THEOREM: The vectors!o, !"
!m
... ,
!1~' .•• , !1~ .•• vm}·
n vectors it is a basis of the
vector space R(n), i.e. the products are independent.
•••
.•• ,
This means that R(n) is generated by the set of product
vectors ~1 ••• !~ (k ~ m), i.e. the set
!1~
~,
We have proved:
!m' !,!2' !'!3' ... ,
fom a basis of
~
(n)
•
~-lYm' Yl~Y3' ••• ,
29
Example:
Let m = 4, n
= 16.
Then
!,
=
Y.2
=(
(0
0
0 0 1
o 1 010 00
( 0 0 0 0 1 1
1 1 )
1 1
1 1
~ = ( 1
0
0
01)
10011001
)
100 0 Q 1
)
( 000 000 0 0 1 1 1 1 ) ( 000 1 000 1 000 1 000 1 ) ( 000 0 0 1 0 1 0 000 0 1 01)
!1!3
=:
Y.1!4
=(
0 0 0 0 0 0 000 1 0 1 0 1 01)
~!3
=(
0 0 0 0 0 0 1 100 0 000 1
)
~!4 = ( 0 000 0 0 000 0 1 100 1
)
!3!4 = ( 0 0 0 0 0 0 0 0 0 000 1 1 1
)
!'~!3 = ( 0 0 0 0 000 1 0 000 000 1~)
Y1!e!4 = (
0 0 0 0 0 0 0 000 0 1 000 1 )
!1!3Y4 = ( 000 0 0 0 000 0 0 001 01) ~!.3!4
=(
000 0 0 0 000 0 0 0 0 0 1
)
!'~!3~ = ( 0 0 0 0 0 0 0 0 000 0 0 0 0 )
We can now define a number of linear codes which were discovered by D. E. MUller and for which I. S. Reed found a very nice decoding method.
(2.3.6) DEFINITION: The linear subspace of R,(n) which has as basis and all products Yi Yoi
:!oJ
!1'
.'.J :!m
• •• !i. with k :: r is called the
12K
r-th order Reed-Muller code o-th order RM code has
!o as
(RM-code) of length n a basis.
= 2m•
The
It is a repetition code
m
of length 2 •
We remark that the following alternative description is equivalent: polynomials of degree GF(2).
~
Consider all
r in m variables xl' x2 , ••• , xm which can take values in
Consider the possible set of values of xl' x2 ' ••• , x : m
30
Xl
= 0,
0, ••• ,
X
= 0,
0, ••• ,
X
2
m
= 0, 1, ••• ,
Successively substitute these sets of values in the polynomial p(x" ••• ,x ). m
Let
the result be a code word.
We then obtain the r-th order RM code of length 2m•
Note that i f !:. = !i !oi
~
b = v -
v···
-jl-j 2
1
V
-jt
2
is a basis vector of the r-th order RM code and
is a basis vector of the (m-r-l)-st order RM code then _a b_ is a
basis vector of the (m-l)-st order RM code and by (2.3.2) ! which implies (!J!?.)
= o.
~
Now the dimension of the r-th order RM code is
+ (~) + ••• + (~) and the dimension of the (m-r-l)-st order
+ (~) + ••• + (m-~-l)
sions is 2m = n.
then has even weight
= (:)
+
(m~l) + ••• + (r:l)·
RM code is
The sum of these two d~en-
Since we have just noted the orthogonality of respective basis
vectors we have proved:
(2.3.7) THEOREM: The dual of the r-th order RM code of length 2m is the (m-r-l)-st ~
m
RM code of length 2 •
A special case is
(2.3.8) COROLLARY: The (m-2)-nd order RM code of length n
= 2m is
m m the (2 ,2 _m_l)
extended Hamming code. Now we consider the problem of error correction when using the RM codes. shall find a way to express a vector f
.!i!oi
···!oi·
12k
E R(n) as
a linear combination of products
From. (2.3.4) it follows that !oi!i
of ! j only if ;1j
···!i
12k
=0
First we
occurs in the expansion
for all i ~ (il,i2' ••• '~) and by (2.3.3) we can therefore
write n-l
!. =
I
j=O
f
j~j =
I
(i 1,i2 ,·.·,1k )
( I
f j
jEC(il,i2'- •• '~)
)
~ t ~2
!j.' k
31
where the sum is over all k-tuples and k = 0, 1, ••• , m.
We shall use the r-th
order RM code as follows. A sequence (a 1 ,a2 , ••• ,~) of information bits (binary), with M = 1 + (~) + ••• + (~), is coded as
Let as be the coefficient of one of the products containing r factors, say
Y.i
r
• By (2.3.9) we have
(2.3.10)
Since C(i 1,i , ••• ,i ,t) 2 r
= C(i 1,i2 , ••• ,i r ) U [C(i 1,i2 , ••• ,i r )
t 1
+ 2 - ) and this is a
tUlionof disjoint sets) we have from (2.3.10) and (2.3.11)
(2.3.12)
a5
=
r 2 We can now consider the sum over C(il,i2, ••• ,ir,tl,t2)' We find a set of 2 + coefficients f j summing to 0.
This set contains the disjoint sets C(i 1 ,i 2 , ••• ,i ), r
t,-l t -1 C(i 1,i , ••• ,i ) + 2 , C(i 1,i2 , ••• ,i ) + 2 2 and for each of these the sum of 2 r r the fj'S was as.
Therefore this is true for the remaining set.
By induction we
then have: (2.3.13)
THEO~:
For every infonnation symbol as corresponding to a product of r vectors !i we can split the set
{O,l, ••• ,n-'}
into ~-r disjoint
subsets C of 2 r elements such that for each of these a
s
=
1:
jEC
f .• J
32
To check this consider the example given above. ficient of ~!3.
The set C(2,3) is (o,2,4,6) by (2.3.3).
first 11 rows of the example ex·cept the row 6 sum to o.
=2
Take r
~!3
and let a
s
be the coef-
Indeed, for each of the
the symbols in positions 0,2,4 and
The same holds for C(2,3) + 8 = (8,10,12,14) and also for (1,3,5,7} and
(9,11,13,15). So we have 4 "disjoint relations" involving the coefficient a s of Now let us assume the received message is
~
= (xo,x"
••• ,xn _,).
Consider as we
did above an information symbol as corresponding to a product of r of the !i's.
,..m-r the absence of errors we have ~.
.
d~sjoint
1
~-r
If the vector x contains less than 2- c-will still hold.
Hence we can then
relations a
s
=
In
m - ,2 r)• t x ( v = 1,2, ••• "€C j
J
v
errors then the majority ·of the relations
dete~ine
as by a majority decision.
After
doing this for all information symbols corresponding to products of r of the Vi's we subtract the linear combination of the!oi
••• v. that we have found. The trans, -~r mitted and the received message have been reduced to the (r-l)-st order RM code and we repeat the procedure.
This shows that the code can correct < ~-r-l_ 1 errors
and therefore has minimum distance > ~-r - 1. even weight and the basis vectors v.
-~,
weight of the code: (2.3.14) THmREM: We
rema~k
Since all vectors in the code have
!oi have weight zn-r this is the minimum r
mr ~ r-th order RM code has minimum weight 2 - •
that several of the proofs given in this section could have been replaced
by more geometrical arguments.
The interested reader can construct such
pr~ofs
as
an exercise.
2.4.
Threshold decoding The method of decoding used in Section 2.3 is a variation of a decoding method
which is used £or many different codes and which is known as threshold decoding. very simple example will serve as an introduction. Consider the binary repetition code of length 2n + 1. the all-zero word and the all-one word.
This code consists of
As a system of parity-check equations we
A
33
can choose
x, + x2 = 0, (2.4.1)
x, + x
3
= 0,
Xl + x 2n+ 1
If the received word is
=x
v
L
-
o. + e then y, + y.
J.
-
= e,
+ e. (i J.
= 2, ••• ,2n+l).
If more
than n of the expressions Y1 + Y is 1 this can be explained by either less than n i
=1
errors among which e, l~ely.
or by more than n errors and e,
= O.
A majority vote among the y, + Y decides whether e, i
o or 1.
If the num-
= 1.
ber of votes exceeds the threshold n then we set e,
The equations (2.4.1) are a special example of the (2.4.2) DEFINITION:
The former is more
follm~ing
Let V be a linear code with block length n.
situation: A set of parity
check equations for V is said to be orthogonal .9E. the set of positions P c {',2, ••• ,n} iff (a) for every i
E P the term
Xi occurs in each equation with a
non-zero coefficient; (b) for every i ~ P the te~ x. occurs in at most one of the J.
equations with a non-zero coefficient. Let us now demonstrate how to use such a set of parity-check equations. sider the dual of the (15,11) Hamming code.
Con-
If H is the parity-check equation of
this Hamming code then for every pair of distinct columns of H there is a third column of H such that the 3 columns sum to zero.
Each of the weight-3 code words of
the Hamming code obtained in this way gives us a parity-check equation for the dual code with three terms.
Among these the set of 7 equations:
34
is orthogonal on position number ,.
For the symbol x, we therefore have the equa-
tions:
(2.4.4.)
e,
Y,
= Xl
+
Y2 + Y 3
= Xl
+ (e 2 +e ),
3
The code under consideration has minimum distance 8.
If the number of errors in the
received message l is less than 4 the majority of the left-hand sides of (2.4.4) will have the value value
x,.
x,.
Once again a majority vote with threshold 4 decides the
If the vote comes out four to four then 4 errors are detected.
that for a ESC with error probability p we have Prob (e, = 0) (e.+ e.) ~ J
=0
= (l_p)2 + p2 < 1 - p.
that the estimate
Y, = x,
=1
Now remark
- p and Frob
Therefore in the case of a tie it is more likely
is correct and we decode in this way.
After decoding the
first symbol we proceed in the same way, using a set of parity-check equations orthogonal on the second position, etc.
Not only are threshold decoders often easily im-
plemented but they also have the additional feature of correcting many more errorpatterns than the code is designed for.
For example in the code treated above many
patterns of 4 errors are correctly decoded, e.g. (111100000000000). By treating one example we shall show that threshold decoding can also be used for RM codes.
Let us consider the (32,16)-second order RM code.
By (2.3. 14) this is
a 3-error-correcting code and by (2.3.7) the code is self-dual. 'Hence every paritycheck equation for the code contains at least 8 terms.
It is therefore tmpossible
to find a set of 6 parity-check equations orthogonal on one position. ity decision in case of 3 errors we need at least 6 equations: this problem 1s obtained by making the decision in two steps. more about the 18rity-check equations of a RM code. (2.4.5) THEOREM:
For a major-
The solution for First we need to know
The following theorem is useful:
m Let V be the (m-k) -th order RM code of length 2 • Then the characteristic function of any k-dimensional affine sUbspace of is a code word of V.
a(m)
35
Proof:
Consider a k-dimensional affine sUbspace A of R(m) and let!. E R(n)
be the characteristic function of A. !i
ficient of !i !i 1
2
r
in the expansion of
L:
coefficient is
Take r > m - k and consider the coef-
jEC(i"i2 ,···,i r )
!
as given by (2.3.9).
This
f j which is just the number of vectors in
the affine subspace A which are also in the linear subspace L := (!j E R(m)
I
j E C(i 1,i2 , ••• ,i )}. r
Since L has dimension r > m - k the
intersection of L and A is empty or an affine subspace of dtmension >
o.
This intersection therefore has an even number of points, i.e. the coefficient of Yoi !i 1
2
~
r
is O.
In other words, f is in the (m-k)-th order
RM code. A consequence of (2.4.5) is that every 3-dimensional affine subspace of R(5) provides us with a parity check for the 2-nd order RM code of length 32 since this code is self-dual. such that
In the following array (a,b,c,d) will denote a set of positions
(~,~,~,~} is
a 2-dimensional affine subspace of R(5).
In every row
these 2-dimensional subspaces are translates of the first space in the row, i.e. the union of such a pair forms a set of positions of a parity-check equation of the RM code:
The subspaces in the first column form a set of positions which in a sense
analogous to (2.4.2) is orthogonal on position 00 0,1,2,3
4,5,6,7 8,9,10,11 12,13,14}5 16,17,18}9
0,4,8,12
1,5,9,13 2,6,10,14 3,7,11,15
16,20,2~8 17,21,25~9 18,22,2~0 19,23,2~31
0,5,10,15
1,4,11j42,7,8,13 3,6,9,12
16,21,26J1
0,6,16,22
1,7,1~3 ~,4,18,20
0,7,19,20
1,6,1~1
2,5,17,22 3,4,16,23 8,15,27,28 9,14,26,29
0,9,18,27
1,8,1~6
2,11,lq25 3,10,17,24 4,13,22,315,12,23,30 6,15,20,29 7,14,21,28
3,5,19,21
20,21,2~3
24,25,2gg7 28,29,3q31
17,20,2~30 18,23,24~9 19,22,25~8
8,14,24,30 9,15,25,31 10,12,2qg8
Once again let a code word!. be transmitted and let 1. =
?Eo
+
~
11,13,27~9
10,13,25~O 11,12,2~1
be received.
We have
36
(2.4.6)
Just as in
(2.4.4) a majority vote among the left-hand sides of (2.4.6) decides 1
whether eO+e,+e2+e is 0 or 1. The threshold is taken as 3 2 , i.e. e O+e,+e 2+e 3 3 is taken to be 1 if 4 or more of the syndrome elements are 1. If the number of errors is 3 or·less, then eO+e,+e 2+e is given the correct value. 3
We repeat this
procedure for each row of the array and then let a final majority vote over the first column with threshold 3 ~ decide whether eO applied for every e • i
=0
or eO
= 1.
This procedure is
It is easily seen that if the number of errors is 3 or less
this decoding procedure reproduces!. which are also decoded correctly.
There are many error patterns of weight > 3
This example of two-step threshold decoding gives
an idea of how the method works in general.
For more information on this subject we
refer the reader to J. L. Massey, Threshold Decoding, MIT-Press, 1963.
2.5.
~-product
codes
Consider a block code with length n
= n,n2 .
Instead of writing the code words
as row vectors of length n we can represent the code words by matrices with n, rows and n ~
2
columns.
= (ao,a"
One way of doing this is e.g. representing the code word
••• ,an _,) by the matrix A := [a ij ], (i
where a ij := a + • in2 j
(2.5.') DEFINITION:
= 0,1, ••. ,n,-1;
j = 0,1, ••. ,n2 -'),
This is called the canonical ordering. Let V, be a linear code of length n, and V2 a linear code of length n • 2
Let V be a code of length n,n2 represented by n by 1
n2 matrices (with the canonical ordering).
We shall say that
is the direct product of V, and V2 iff V consists of all code words for which the matrix representation has the following properties:
(i) each column of a matrix is (the transpose of)
a code word of V" of V2 •
(ii) each row of a matrix 1s a
co~e
word
V
37
It is clear that the direct product of two linear codes is again a linear code.
If
we interchange the factors V, and V we obtain an equivalent code in the sense de2 fined in Section 2.1.
We shall denote the direct product of V, and V2 by V, X V2 -
(2.5.2) THEOREM: The minimum weight of V, X V is the product of the minimum weights 2
:?! V, ~:
and V2.
Let V, have length n, and let V2 have length n2 and let the n, by n 2
matrix A represent a non-zero code word of V := V, X V2 low that there are such words).
(We shall see be-
At least one row of A contains
an element
, 0 and hence at least w(V ) non-zero elements where w(V ) denotes the min2 2 imum weight of V . 2
Each of these non-zero elements is in a column with at
least w(v,) non-zero elements, i.e. at least w(v,)w(V ) elements of A are 2 not zero. Let V, be an (n"k,) linear code and V2 an (n2 ,k 2 ) linear code.
Let G, and G2 be
the generator matrices of these codes, both in reduced echelon form.
row vectors of Gt by (j
= O, .•. ,k2 -1).
~1)
(i
= O, ••• ,k1-1)
We denote the
and the row vectors of G2 by
Now define the matrix A.. (0 < i < k" J.J
-
~2)
0 < j < k2 ) as follows: -
The first k 1 rows of Aij are zero except the i-th row which is ~(~). The first k2 colllllll'E of A are zero except the j-th column which is ~(~)T. For k ::: k 1 the k-th ij row is g~) ~~ 2 )• Consequently for t ::: k2 the t-th column is g~~) ~( ~ )T • This matrix has the form 0
o
0
o ••• A
ij
=
0
010 0
0
o 0****
o
o
o
*
0
0
** *
38
Obviously this matrix represents a code word of V, X V and each code word of 2 V1 X V2 must be represented by a linear combination of such matrices.
This proves:
(2.5.3) THEOREM: If V, is an (n"k,) linear code and V2 ~ (n2 ,k2 ) linear code then V,
X
V2 ~ (n,n2 , k,k2 ) linear code.
In the representation used in the proof of (2.5.3) the elements in the k, X k
sub2 matrix of a matrix A are the information symbols. We now shall try to find the generator matrix of V, X V2.
(2.5.4) DEFINITION:
We need a definition from matrix theory:
If A := [aij ] is an n, by m, matrix and B is an n2 by m matrix 2 then the Kronecker product A X B is the matrix
a, m B 1
A X B :=
a
( 2
Example:
o
Now consider G, X G2 • in its canonical fined above.
') -1
X
n, ,B
(3 '") 1
2
6 4 2 13 2 ') 2 ( o 0 -3 -1 o 0 -1 -2
If we take the (k2 i+j)-th row of this matrix and represent it
fo~ ~s
an n, by n2 matrix then this matrix is the matrix Aij de-
Hence G1 X G2 is the generator matrix of V1 X V2.
For this reason
direct-product codes are also called Kronecker product codes. The following decoding algorithm is used for direct-product codes.
If a matrix
A representing a code word is received then first the rows of A are decoded by the procedure for the code V and then the columns of A are decoded by the procedure 2 for V,.
Due to the simplicity of this rule implementation is not too difficult.
Notice that if a burst-error occurs some of the rows of A will contain very many errors but the burst will not seriously effect the columns and it is possible that it is completely corrected in the second phase. An even more effective way of combating burst errors i~ possible if (n 1,n2 )
= ,.
The matrix A= [aijl, i= 0, ••• ,n,-1,
39
j = 0, ••• ,n2 -1 is transmitted as the sequence £ := (cO'c" ••• ,c ck := a ij if k
=i
(mod n1 ) and k
=j
(mod ~).
n,n2
-1) where
By the Chinese remainder theorem
this is a one-one correspondence between the elements of A and
£. Using this cyclic
ordering a burst error in .£ will be distributed among the rows and columns of A.
It
would be very useful if a not too complicated decoding algorithm for product codes could be found which actually corrects the error patterns that one knows can be corrected.
The following example shows that this is not true for the procedure des-
cribed above:
If V1 and V2 both have minimum distance 3 e.g. if they are Hamming
codes then by (2.5.2) V, X V2 is a 4-error-correcting code.
If a word of V, X V is
2
received with 4 errors in places which in the matrix representation are in rows 0 and 1 and columns 0 and 1 then these 4 errors are not corrected, in fact more errors are introduced in both phases of the procedure described above! Recall that Shannon I s theorem, proved in Section 1.4, asserts that for a ESC a sequence of codes can be found such that the corresponding sequence of
e~ror
prob-
abilities tends to 0 while the rates remain> R if R < C (C is the capacity of the channel).
By using product codes, P. Elias constructed a sequence of codes for
which the error probabilities tend to 0 and the rates are bounded away from.
zero.
Although this is not quite as good as is possible according to Shannon I s theorem it is still the only known sequence of codes with this
property~
The construction runs
as follows: Consider a BSC with error probability p and assume p is small enough for there to be an extended Hamming code of length 2m for which the expected number of errors per block at the receiver is <
1 2'. We take this extended Hamming code as the first
code in our sequence, say V1 •
If code Vi has been defined then
code Vi +1 is obtained by taking the, direct product of the extended Hamming code of length ~+i and Vi •
Denote the length of Vi by n i and the dimension by k i • Furthennore let ni Pi
be the expected number of errors per block after decoding of Vi. ing procedure described above.
We use the decod-
In every phase of decoding the errors in a block
are in different words which were corrected in the previous phase and therefore these errors are independent.
We therefore have by (2.5.3) and (2.2.12):
40
n = i
ki
=
TT
i- 1
zm+j
J= 0 i - 1
TT
j=O
J
(~+J - m - J - 1),
_i i -1
Pi = p~
.L
= 2miT2L (i-l)
TT
j= 0
(~+1-j-')
2J
Note that the rate of Viis
Furthermore by (2.5.7) since tAp < ~: i i i
Pi = p2 2(m+l)2 ~-i-l < (tA+ 1p )2 ~ 0 i f i ~ ~J and also niP
i
.. 0 if i ..
an error tends to 0).
00.
(In fact the probability that a decoded word contains
This shows that the codes Vi' the ~ ~ , have the
property stated above.
2.6 Problems
(2.6.1)
Let H:=
(~~ ~ ~ ~~)
be the parity-check matrix of a binary linear
101 100
code. (2.6.2)
Decode the following received messages:
(a)
110110,
(b)
010100.
If an (n,k) linear code over GF(q) has a generator G in which no column
with only zeros occurs then the sum of the weights of the code wo~s is n(q_1)qk-1. Prove this. (2.6.3)
If V is a binary linear (n,k) code then all code words have even weight or
the code words of even weight fom an (n,k-l) linear code. relation between the parity-check matrices of the two codes?
Prove this.
What is the
41
(2.6.4)
If a (22,14) 2-error-correcting code exists what can be said about the
weights of the coset leaders in the standard array7 (2.6.5)
Let P be a prime.
Is there always an (8,4) self-dual linear code over
GF(p)7 (2.6.6)
Determine the weight enumerator of the extended binary Hamming code.
(2.6.1)
Dete~ine
(2.6.8)
Prove that the row vectors
the weight enumerator of a Hamming code over GF{q) if q > 2.
Yo'
!1' • •• , !1~ •••
:Ym as described in
Section 2.3 can be rearranged in such a way that they form a matrix with zeros below the main diagonal. (2.6.9) code7
Consider the 2
nd
-order RM code of length 32.
Decode the following received word:
(2.6.10)
What is the rate of this
(1011010010110100101,000000001111).
Determine the number of words of weight 4 in the 2
nd
-order RM code of
length 16. (2.6.11) Analyze the possible outcomes of the decoding procedure described in Section 2.4 in the case of the 2nd -order RM code of length 16 if the error pattern has we ight 4.
III. CYCLIC CODES
3. ,
Introduction In this chapter R(n) will denote the n-dimensional vector space over GF(q).
We shall make the restriction (n,q)
=,.
Consider the ring R of all polynomials
with coefficients in GF(q), i.e. (GF(q)[x],+, ).
Let S be the principal ideal in R
n
generated by the polynomial x _ 1, i.e. S := «(xn _l),+, class ring R mod S, i.e. (GF(q)[x] mod «(x
n
-l}1+, ).
). Rls
is the residue
The elements of this ring can
be represented by polynomials of degree < n with coefficients in GF(q). itive group of R/S is isomorphic to R(n). the vector ~
= (aO,a1, ••• ,an _1 )
The add-
An isomorphism is given by associating
n 1 with the polynomial a O + a1x + ••• + an_1x - •
From now on we shall make use of this isomorphism in the following way:
The
elements of the vector space R(n) are either referred to as "words" (or vectors) or as "polynomials tl and generally we do not distinguish between the two representations. In addition to the vector space structure there is now also a multiplication in R(O)
which is just the multiplication of polynomials mod (x n _ 1). Notice that the multiplication by x amounts to applying the cyclic shift which
(3.1.1) DEFINITION:
A k-dimensional linear subspace V of R(n) is called a cyclic code (or cyclic sUbspace) if
(n) [(aO,a1,···,an_1) E V ~
V
(ao,· .• ,an _1 )E R
(an_"aO,a" ••• ,an_2 ) E V ] · Since we are using two
te~inologies
simultaneously we can interpret V as a subset
of the ring R/S.
(3. 1 .2) THEOREM: V is a cyclic code iff V is an ideal in R/S. Proof:
(i) If V is an ideal in R/S and (a ,a 1, ••• ,a _1 ) O n
nomial obtained by multiplying by x is also in V.
E V then the poly-
This is the cyclic shift
43
(ii) If (ao,a" ••• ,an _1 ) E V implies (an_l,aO, ••• ,an_2)
(an_l,aO,··.,an_2)·
E V then for every polynomial a(x) E V we have xa(x) E V.
2 x a(x) E V, x 3a(x) E V etc. nomial p(x), i.e.
V
From now on we shall write
E V for any poly-
Hence we also have p(x)a(x)
is an ideal in
But then also
Rls.
R instead of R(n) or Ris and denote the ideal generated
by a polynomial g(x) by Rg(x).
Every ideal in R is a principal ideal generated by
the monic polynomial of lowest degree in the ideal, say g(x), where g(x) 1s a divisor of x n - , in R.
We shall call g(x) the generator (-polynomial) of the cyclic
code. Let x
n
- 1
= f,(x)f 2 (x)
ible factors in R.
••• ft(X) be the decomposition of x
Since (n,q)
=1
n
- 1 into irreduc-
there are no multiple factors.
(3. 1.3) DEFINITION ~ The cyclic code generated by f i (x) is called a maximal cyclic code and denoted by M~ := R, f i (x). Note that a maximal cyclic code is a maximal ideal in R. Let n denote the permutation k ~ jk (mod n) of the set of integers {O", ••• ,n-l}. j
\ve can also interpret definition
1t
j
as an automorphism of the ring R by taking the natural
n-l i n-l ji n j ( t aix ) := t aix i=O i=O
Of special interest to us is the binary case (q = 2, n odd).
C"C2 , ••• ,Ct denote the cycles of the permutation n2 •
For this case let
E.g. if n = 63 we have the
cycles (1,2,4,8,16,32), (3,6,12,24,48,33), (5,10,20,40,11,34), (1,14,28,56,49,35), (9,'8,36), (11,22,44,25,50,31), (13,26,5 2 ;41,19,38), (15,30,60,51,51,39), (21,42), (23,46,29,58,53,43), (21,54,45), (3 1 ,62,61,59,55,41), CO). Fran the theory of finite fields we know that if a is a primitive n-th root of
n
i (x-o: ) where i EC C is any of the cycles mentioned above is an irreducible factor of x n - 1 in R.
unity (in a suitable extension field of GF(2»
the polynomial
Hence to each of the t cycles corresponds one of the factors f cyclic code.
i
and one maximal
In the example considered above we can take a to be a primitive
44
6 element of GF{2 ).
In this case the polynomial
ible factor of x 7 -
(x~)(x~18)(x~36) is an irreduc-
(i.e. a 9 is a primitive element of GF(8».
We saye is the e . exponent of a(x) if e is the least positive integer such that a(x) divides x - 1 (in R).
For any cycle C the exponent of the corresponding polynomial is nld if d is
the greatest cammon divisor of the numbers in the cycle. ~:
then x
e
If a(x) is a divisor of x
n
e - , with eA-ponent e < n, i.e. a(x) Ix - 1 (in R)
- 1 is a code word of weight 2 in the code generated by a(x).
that we shall have little interest in
It 1s clear
such codes for practical purposesl
We can now find all cyclic codes of length n over GF(q) by factoring xn - 1 t n into f,(x) ••• ft(x) and taking any of the 2 factors of x - 1 as a generator. Many of these codes will be equivalent! Let g(x) be the generator of a cyclic code of length n over GF(q) and let n
x
- 1
= g(x)h(x)
(in R).
If g has degree n - d then h bas degree d.
(We observe
that the polynomials g(x), xg(x), ••• , Xd-'g(x) form an independent set, in fact a basis, in the vector space a
R. Therefore, if g (x ) = go
+ g,x + ••• + gn_dx
n-d
then
generator matrix of the cyclic code R g(x) is gog, G .-
o gog,
o
0
· ••• • ·~-d 0 0 ••••••
gn-d
• • · • • •0 go
0
°.... °
•• • • • • • ••. gn -d
A more convenient form of the generator matrix is obtained
by
defining, (for
i
i ~ n - d), x =: g(x)qi(x) + ri(x) where ri(x) is a polynomial of degree < n - d. The polynomials xi - r. (x) are code woras of R g(x) and form a basis. ~
basis vectors the generator matrix has the form matrix.
i
= 0,1, ••. ,n-1
we have
Taking these
(-R I) where I is the identity
45
(where the subscripts are to be interpreted mod n).
o0
o
•••• 0 h •••• d ·.·.··0 h
H :=
••••••
d
Therefore h h 1 O hOO
o is a parity check matrix of the code. the dual of
Rg(x) (by the
Notice that the code
pe~utation x ~ x-
1
Rh(x) is equivalent to
Because of this equivalence we
).
shall from now on refer to the code Rh(x) as the dual of the code Rg(x).
The poly-
nomial hex) is called the check-polynomial of the code Rg(x).
R is called a minimal
An ideal V in than (OJ.
~
if it contains no subideal other
From the description of the ideals in R given above we see that the minWe denote by M~ the dual of M~.
imal ideals are the duals of the maximal ideals. n The generator of M~ is (x -l)/f (x). i
The codes M~ are called irreducible cyclic
codes. (3.1.4) DEFINITION:
If V, and V2 are ideals in R we denote by V, + V2 the ideal generated by V, and V , i.e. the smallest ideal which contains
2
V, and V2 • Notice that V,
n V2 1s also an ideal in R.
(i)
V,
n V2
is generated by the least common multiple of
g, (x)
and g2(x), (ii)
V, + V2 is generated by the greatest common divisor of g,(x) and ~(x).
We leave the proof to the reader as an exercise.
We remark that Mi-
n M~J = [OJ -
if i ~ j and that M+ i
n M~J = R(fi(x)f.(x». J
From (3. 15)
it follows that an ideal V in R is the "sum" of the minimal ideals contained in V. To conclude this introduction we treat a simple example namely n
We have x 7 _ ,
=
2 (X_l)(x 3+x +1)(x 3+x+l).
= 7,
q
= 2.
If we take g(x) = x 3 + x + 1 we find the
46
maximal cyclic code with generator 1101000
o1 o0
G =
10' 0 0 101 0
0001101
2 4 Since h(x) = x + x + x + 1 we have
(~~~~ ~~)
H=
1 0 1 1
0 0
It is not hard to see that this code is equivalent to the (1,4)
Hamming
code.
(See 3.2.1).
3.2 The zeros of a cyclic code If g(x) is the generator of a cyclic code and 0:"
02, ••• ,
O:n_d are the zeros
of g in a suitable extension field of GF(q) then a polynomial a(x) is a code 'Word of Rg(x) iff a(o:,)
= a(0:2) = ••• = a(an _d ) = O. In
this way we have an alternate
description of cyclic codes namely by the zeros common to all code words. necessary to give all the zeros of g(x) to specify g(x). Section 3.', g(x) a(Cti ) = a(Cti ) , 2
= fi
= •••
1
It is no
If, in the notation of
(x)f. (x) ••• f. (x) it is sufficient to require that ~2
~
= a(a
i k ) = 0 where a 1 j is a zero of f i.. J
From the theory of
finite fields we know that if a is a zero of a polynomial with coefficients in· GF(q) then o:q is also a zero of this polynomial. Let us now consider the simplest example namely the case where only one zero m is required. We take n = 2 - " q = 2. Let 0: be a primitive element of GF(2 m) 2 4 ~-1 and m,(x) = (x-a)(x-a )(x-a ) ••• (x-a ) the minimal polynomial of a. (In the following we shall always denote the minimal polynomial of a i where a is a primitive element of GF(~) by m (x). i
In these cases m is fixed).
GF(zrt) can be expressed uniquely as . .
m-t
t
i=O
€.cl ~
Every element of
where €i E GF(2).
for which the J-th column (J = O,1, ••• ,~-2) is (€O'€l'···'€m-l)
Let H be the matru T
of a
j
m-l
i
= i:O €ia •
47
n We have seen that a(x) = &0 + &,X + ••• an_,x -' E Qm,(x) iff a(a) = 0 but this is so iff aHT = by m (x). 1
':? -1
Q.
Therefore H is a parity-cheCk matrix of the cyclic code generated
Since H is obtained by pennuting the binary representations of 1, 2, ••• ,
we have proved:
(3.2.1) THEOREM.
m The binary cyclic code of length n = 2 _l for which the generator m is the minimal polynomial of a primitive element of GF(2 ) is equivalent to the (n,n-m)-Hamming code.
Exam,ple:
Using the irreducible polynomial x
4 + x + 1 we can generate GF(16).
For
the nonzero elements we find the representation:
4
1
a,
a,2
a,3
0.
c?
0,6
0,7
1
0
0
0
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
1
,
0
0
0
1
0
0
1
0
0,8
a,9
,
a,lO
0.11
a,12
1
0
1
,
1
1
1
1
0
0
1
0
0 \,
1
0
1
0
1
0
1
1
1
0
1
0
1
1
,
a,'3
,
a,14
1
If we use this representation of the (15,11) Hamming code and its parity-check matrix the encoder codes a sequence (ao,a" ••• ,a 10 ) of information bits into the code 4 10 . word c(x) := a(x)(x +x+l) where a(x) := ~ a.x~. Let us, as before, assume the i=O J. e received word contains one error, i.e. it is c(x) + x • The receiver computes the syndrome which is nothing else than c(a) + a
e
= ae •
decoding rule is to assume an error in position e.
Hence if the syndrome is a e the Note that decoding is just as
simple as in our first description of Hamming codes but now the encoder has a simplicity we did not have
before~
As a second example we let
m,(x) be as above and consider g(x)
:= (x+l)m (x).
1
Then Rg(x) is the cyclic code consisting of the words c(x) for which c(l) = c(a)
= O.
This is a subcode of the Hamming code obtained by adding a row of l's to the parity check matrix, i.e. it is the code consisting of the code words of even weight in the
48
(2.6.3».
Hamming code, (see
As a third example we take n = 15 and g(x) = m1(x)m {x). We have g{x) = 5 4 C) 10 4 2 3 4 5 6 (x +x+l){x~)(x~ ) = (x +x+l){x +x+l) = , + x + x + x + x. Therefore g{x) generates a 9-dimensional cyclic code of length 15.
The simplest form. of a parity-
check matrix of this code now is
H =
where each entry a
i
(~
stands for a column vector with 4 entries from GF(2).
Since
g{x) has degree 6 we know that a parity-check matrix for this code should have 6 rows.
Therefore the rows of the matrix H are not independent. Up to now we have taken n
x
n
n
- 1 =
TT
= 2m -
Now let n be arbitrary, q
1.
= 2.
Then
ai ) where a is a
primitive n-th root of unity. Ifm is the multim plicative order of 2 mod n (2 == 1 mod n) and ex is a primitive element of GF{2m), i= 1
(x -
2 m_l
we can take
-j
e = ex
nomial Q(n)(x).
n
where (j,n) = "
a is
i.e.
any zero of the cyclotomic poly-
We can now specify a cyclic code by specifying k
K := (k(mod n)1 g($ )
= OJ.
i
Since g{a )
=0
tion U must leave K invariant (as a set). 2
defines a cJClic code (if not depend on the choice
(3.2.2) THEOREM: Let
e is of a.
given).
a and e* be
2-
~ g{e 1)
=
e and
giving the set
° we see that the permuta-
Vice versa any set K with this property
We now show that in a sense, the code does
two primitive n-th roots of unity and let K be a
subset of (0,1, ••• ,n-1} which is closed under multiplication by 2 (mod n). ~
Define g{x) :=
IT
kEK
k (x - a ), g*(x) :=
TT
kEK
(x - e*k).
g(x) and g* (x) generate equivalent cyclic codes.
*
-
There is a j with (n,j) = 1 such that a = eJ • If c{x) is a code n-l i k word in Rg{x), say c(x) = t cix, then for every k E K we have c{e ) = 0. i=O n-1 1-k n-l *k 1 This can be written as t c ( )a J = 0, i.e. t c (_){$ ) = 0. i=O nj i i=O n j 1 Proof:
49
Therefore there 1s a permutation which permutes all code words of Rg(x) into code words of Rg* (x). The important thing we learn from the point of view of this paragraph is that the cyclic shifts are not the only permutations which leave a cyclic code invariant. e~g.
If
we take a binary cyclic code of odd word length n then the permutation g2 per-
mutes code words into code words.
This information will be used to determine the
weight enumerators for cyclic codes.
(See 3.3).
The larger the automorphism group
of a code is the easier it is in general to find the weight enumerator of the code.
3.3
Idempotents In this section we again use the symbol nj to denote the permutation of
{O,l, ••• ,n-l) given by nj(k) = jk (mod n) and also to denote the automorphism of R n jk k given by nj(x ) = x mod (x _l). If V is the cyclic code Rg(x) then njv denotes the cyclic code Rnj(g(x». (n odd).
We shall now consider binary cyclic codes of length n
In Section 3.1 and 3.2 we saw that there is a 1-1 correspondence between
the cycles of n2 and the irreducible factors of x
n
In fact if (c"c 2 ' •.• 'c ) k Ci is a cycle of n2 and a is a primitive n-th root of unity then f(x) = (x- a ) 1= 1 n is an irreducible factor of x - 1.
(3.3.1) THEOREM:
-,.
Tf
For every ideal V in R there is a unique polynomial c(x) E V, called the idempotent of V, with the following properties: 2 (1) c(x) = c (x), (ii) c(x) generates V, (iii) Yf(x)EV [c(x)f(x) (iv)
Proof: Since x
if (j,n)
=1
= rex)],
then nj(c(x»
i.e. c(x) 1s a unit for V, 1s the idempotent of njv.
(i) Let g(x) be the generator of V and g(x)h(x) = x n
- , has no multiple zeros we have (g(x),h(x»
are polynomials p,(x) and P2(x) such that (in R)
= 1.
n
- 1 (in R). Therefore there
50
Now take c(x) := P, (x)g(x). c
2
Multiply both sides of (*) by c(x).
We find
Since (in ~) g(x)h(x) = 0 we have
(x) + P,(x)P2(x)g(x)h(x) = c(x).
proved (i). (ii)
The monic polynomial of lowest degree in the ideal generated by c(x) n is (c(x),x -l) = (P1(x)g(x), g(x)h(x» = g(x). By (ii) every rex) E V is a multiple of c(x). Let f(x) = c(x)f,(x). 2 Then c(x)f(x) = C (X)f 1 (X) = c(x)f 1 (x) = f(x), i.e. c(x) is a unit in V. (iii)
(iv)
Since
Jt j
is an automorphism of R the polynomial
potent and unit in 'lCjV.
Jt j
(c (x»
is an idem-
Since the unit is unique we have proved (iv).
Note that an ideal can contain more than one idempotent but that only one of these has all the properties (i) to (iv).
The advantage of using idempotents for describ-
ing cyclic codes is that it is no longer necessary to factor xn - 1. k
c
k
2c
k
To see this
c
Then I: x i = I.: x i which means that 1=' 1=1 1=1 the set (c 1,c 2 , ••• ,c } 1s invariant under the permutation n2 of (O,1, ••• ,n-l}. This k
assume that
t
x
i
is an idempotent in R.
set must then be the un10n of cycles of
We have seen that the t cycles of -2 t are easily obtained and from these we find the 2 idempotents generating the cyclic Jt
2
•
codes in R. Since we would like to use the representation of 3.1 and 3.2 and idempotents simultaneously we are faced with the problem of finding a correspondence between generators of ideals and the idempotents of the ideals. know that if c(x) is the idempotent of
V
then
1 +
From the equation (*) we
c(x) is
~e
idempotent of the dual
code.
(3.3.2) DEFINITION:
The idempotent of a minimal code M~ is called a primitive idempotent and denoted by ai(x) (or ~i).
Remark: as
unit~
Notice that a minimal code is a finite field with the :primitive idempotent
51
If V1 and V2 are ideals in R with idempotents c,(x) and c (x) then 2
(3.3.3) THEOREM:
n V2
(i) V1
has idempotent c, (x)c 2 (x),
(ii) V, + V2 has idempotent c,(x) + c2 (x) + c 1 (x)c 2 (x). Proof:
(1)
generators of V1 and V2 thenV 1 tiple g(x).
= a(x)g(x),
1s generated by their least cammon mul-
£,
+
£e + £,£e
=
i.e. c 1(x)c 2 (x) is the (unique) unit of V,
n V2 •
Let a and b be
Obviously £, + £2 + £1~ is an idempotent in V 1 + V2 •
arbitrary polynomials.
i.e.
n V2
If g,(x) and ~(x) are
For any code word a(x)g(x) we have c,(x)c 2 (x)a(x)g(x)
c2 (x)a(x)g(x) (1i)
n V2 •
c 1 (x)c2 (x) is a code word 1n V,
-
-
Then
is the (unique) unit of V, + V2 •
(3.3.4) THEOREM: For the primitive idempotents we have:
!i!j = 0
(i )
(ii)
t
i ~ j,
= 1,
t !i
i=1
( iii) , +
if
~
,
+!i
2
+... +!ir
Rf. (x )f i (x) ••• 2
~1
Proof:
(i)
By
fi
r
is the idempotent of the ideal
(x).
(3.3.2) and (3.3.3) !1!j is the generator of
M~
n Mj = CO).
(ii) By repeated application of (3.3.3) (ii) and (3.3.4) (1) we see that t t t !i is the idempotent of M~ + M; + ••• + M~ = R, i.e •. 1: ~ = 1.
i=1
1=1
1, (x) ••. f i ·(x) is the dual of M~
(iii) Rf.
r
If S and Tare nonempty subsets of {1,2, ••• ,t} then
1
+
M~ + ••• + M2
ir
(tES !j)(.tJ €I' !j) = J'esrlr . L !j and j
this is 0 only if S
n T = ¢.
which ~ ~j = 0 if i ~ the
~j·s.
~
j.
Therefore the
Suppose
S-, '~' ••• ,
~t is a set of idempotents for
Every ~j is a sum of !i 1 S and no !i can occur in two of s .s...t J
must be a permutation of the primitive idempotents.
52
This principle enables us to find the primitive idempotents in the following way: (3.3.5)
Algorithm: First construct the idempotents :Ill' Then 1 =
1I2e
11,
TIe' .•• , 1lt
corresponding to cycles of
+ (' + ],) is a decomposition of 1 into mutually ortho-
gonal idempotentse
Suppose 1 has been written as the sum of ,. < t mutually
,.
orthogonal. idempotents, i.e. 1 .. j:1 ~j with ~~j .. 0 if i ~ j.
any idempotent.
Let ~ be
Suppose that for some j the idempotents ~j~ and s..j(l+~)
are different from
o.
For i 1= j we have ~~j'1=0 and ~~j(l +~) = 0, i.e.
the two idempotents ~j~ and ~j (1 + s.) are orthogonal to all the others and also mutually orthogonal and therefore all different.
i.j (1
+
~)
potents.
we can then write 1. as the sum of This process fails if for every T
but since .1: J=l
(j
-S.j
= 1, ••• ,T).
~j
i.j-S.
=
+
+ 1 mutually orthogonal idem-
T
j we
have
s..jt =
0 or ~j( 1+s.) = 0
= 1 this means that ~ is a linear combination of the ~j t s
Among the idempotents
11"
••• , .TIt
~,
for which this is not the case since the ]i patents.
Since
fo~
there is at least one
a basis for all the idem-
This algorithm leads to a decomposition of 1 into t mutually
orthogonal idempotents and these must then be the primitive idempotents. (3.3.6)
Example: ~ =
Take n
= 15.
(7,11,13,14),
Let:Ill
= (1,2,4,8), Jle = (3,6,9,12),
]3
n, = (0) where for abbreviation we have written
(1,2,4,8) instead of x + x
248 + x + X , etc.
Apply the algorithm with ~ 1
= Jle
=],
Now appl.y the algorithm with
We start with 1
to (, + ]1). +
Jl3
(TI,
+
TIe)
=],
+ (1 +
to ], and (1 +
Jle).
TIe).
We find:
The last one
of these was to be expected since for g(x) = 1 + x the equation
(xn-2 + xn-4 + ••• + x)(l + x) + 1 • (, + x + ••• + xn-1) n-1
is a primitive idempotent.
+ (1+ ],).
We find
which must be the decomposition into primitive idempotents.
1 + x + ••• + x
= (5,10),
(*)
= 1 and
is
therefore
53
The advantage of the algorithm
(3.3.5)
We are now in a position to
R given
by T(g(x»
2
n-1
the weights of code words in a cyclic
= xg(x).
If a(x) is a code word in a cyclic code then
! are also code 'Words in this code but not necessarily all differ-
T!, T!.1 ••• , T ent.
enumera.t~
In the following T denotes the permutation k .. k + 1 (mod n) or the mapping
code. of
is that it is easily carried out by computer.
1 The number of different code words in the set (!J T!:J T2~ ••• , Tn - !} is
called the period of
~
and denoted by per (!.).
(3.3.1)~: Let a(x)
E R.
n
n
In R let (a(x),x -1) =: g(x), h(x) .- (x -l)/g(x).
If e is the exponent of hex) then per
Proof: (i) n
(c(x),x -l) e T .!. =~. (1i)
e Define g*(x) := (x -l)/h(X). Then a(x)(x -l)
Therefore per (!)
If per
(!)
n
Let a(x) = c(x)g(x) with i.e.
S e.
= e' then (x
ible by x _l in R.
= e.
= c(x)g(x)g*(X)h(x) = ° in R,
e
= 1.
(!)
e'
-l)a(x) = 0, i.e. c(x)g(x)(x n
Since (c(x),x -l)
= 1 we
e'
-1) is divis-
see that hex) divides x e '_ 1.
Therefore e' > e. From (1) and (ii) the lemma follows.
The set ( !:, T!:J ••• , T'e-1 !:} is called a cycle of length e.
(3.3.9)
THEOREM: ~:
Every cycle (except the cycle containing The theorem is a consequence of
word in M~ and x
n
(3.3.7)
n
- 1 have g.c.d. (x -l)/f
i
2)
of M~ has length e • i
since every nonzero code
(X).
Now suppose we have cycle representatives for the codes M~ and ~
M:. J
a(x) E M~1 b(x) E Mjl h := (per(~), per<:~», H := [per(~), per(~)]. a,'
a'k
T ! + T
a. a,' ~' then T ! - T ~ =T £.
-
a~,
T
E.g. let
If TOa+ TSb =
but since the vord on the left-hand side
is in M- and the one on the right-hand side is in i
M:J they must
both be
o.
-
Therefore
TO! + T$E. takes on per(!).per(~) different values. These are cod-e words in M~+ Mj. ex ~ ex a,' Furthermore per(T ! + T £) = H. Finally, suppose T ! + !?. and T ! + b are in the
54
A ex
same cycle of M~ + Mj.
Then for some A we have T (T !. + E.)
(mod h) and therefore ex
==
(3-3.10) THEOREM:
If
ex' (mod h).
~ tM~
and
I
Ta. !. + ~, i.e. A == 0
a=
Summarizing we have:
k E Mj
then the
per(~)'per(~) different
code'words
Ta.~ + T~£ (0 ~ a. < per(~), .~ ~ • < per (£» of the code M~ + Mj are partitioned into h cycles of length H for which the words
.p! + ~
(0 ~
0:
< h) are representatives.
(3. 3. 11) Example: We shall now treat one example in detail to show 'that for codes with not too many code words, the weight enumerator can be determined by hand (or computer for slightly larger codes).
Take n
I:
In (3.3.6) we
15.
found the five primitive idempotents to be ~1 ~
!3 ~
~
3
6
7
9
12 13 14 '+x +x +x 2 3 4 6 7 8 9 11 12 13 14 :== ]1 + TIe + llit X +x +x +x +x +x +x +x +x +x +x +x 2 3 4. 6 8 q 12 := 1 + ~ X +x +x +x +x +x +X' +x 2 4 5 7 8 10 11 13 14 := TIl +]3 +.Tht x+x +x +x +x +x +x +x +x +x 10 3 4 5 6 7 8 :=]1 + ~ + ]3 + ~ + ~ = x +x +x +x +x +x +x +x9 +x + 11 12+ 13 14 := ~ + ~ == x +x +x +x +x
11
I:
n
I:
I:
+l
+ x
+ x
x
+x
•
We already know that f (x) = 1 + x. Since (x + x + 1)9 (x) = 0 we see that f 4(X) 4 5 2 15 x + x + 1. We know fram the cycles of ~2 that x -, 2 (X+l)(x +X+1)'Q(5)(X)f (X)f j (X) where fi(x) and fj(x) are the irreducible factors i of Q(1 5 )(x). Now Q(5)(x) = x 4 + x 3 + x2 + x + 1 corresponds to ~ i.e. f 2 (x) = 2
=
I:
1 + x + x 2 + x 3 + x 4.
4.
Consider the cyclic code V := ~ + M
Since f 2 has degree
4: and f 4 has degree 2 the code V has dimension 6. The idempotent of V is !2 +
112
3 5 .6 9 10 12 + TI == x + x + x + x + x + x
3
3
I:
X
x 15 - 1 2 2 3 4 • (In this case (l+x+x ) (l+x+x +x +x )
the idempotent is a cyclic shift of the generatort) the exponent of f (x) is 3.
4
~ =
The exponent of f 2 (x) is 5 and
Therefore, by (3.3.9) the code ~ has three cycles of
4
length 5 and the cycle consisting of 2. whereas the code M has one cycle of length 3 and the Q cycle.
55
Notice that:
~
= (011110111101111), + T~ = (110001100011000),
~
+
~
T2~
= (101001010010100)
are obviously in different cycles of ~ and are therefore three cycles of ~ of length 5.
!4 = (011011011011011).
representatives of the
4
For M we have the representative
We now apply Theorem (3.3.10) and find the following re-
presentatives of cycles for V:
-0=
(000000000000000),
weight
~= (0110110110'1011), ~
= (011110111101111),
!2 + T~ = (110001100011000), 2 ~+T~r: (101001010010100), ~
!4 +
+ ~ r: (000101100110100),
92 + T!2 2
= (101010111000011),
~+~+T~r: (110010001001111),
Therefore the weight enumerator of V is 1 + 25z
0
,
length
f.
10 ,
11
3
tt
12
11
5
It
6
It
5
rt
6
ft
5
If
6
tt
15
II
8
If
15
tI
8 ,
It
15 •
6
+
30z8
+
3z 10 + 5z 12 • The code 1s
2-error-correcting and 3-error-detecting. ~:
The theory presented in this section is a special case of more general
theorems on idempotents for an algebra with unity which is the supplementary sum of a number of ideals.
We refer the interested reader to A. A. Albert, Structure of
Algebras (Chapt. II), AMS Call. Publ. 24.
The special application in this section
15 due to F. J. MacWilliams (The structure and properties of binary cyclic alphabets,
Bell System Tech. J. 44 (1965), 303-332).
3.4 Some other representations of cyclic codes Let P be a prime and let k be the multiplicative order of p mod n.
If q = p
then the primitive n-th roots of unity are in GF(q) and in no subfield of GF(q).
k
56
(3.4.1) DEFINITION:
For ~ E GF(q) we define the ~ of ~ as
Tr(~) := ~ + ~P + ~P
2
k-l + ••• + ~P
Note that the trace has the following properties:
(3.4.2)
(a)
For every ~
E GF(q)
the trace Tr(~) 1s in GF(p). k-l
x:P + ••• + ~ = 0 has at elements S E GF(q) with Tr(~) ~ O.
(b) Since the equation x + GF(q) there are
k-l
most p
roots in
(c) Y~€GF(q) YilEGF{q) (Tr(~ + 11) = Tr(~)+ Tr(l1)]· (d)
'aEGF(p) Y~EGF(q) [Tr{a~)
=a
Tr(~)].
Combined with (c) this means that Tr is a linear mapping of the vector space GF{q) over GF(p) onto GF(p). (e)
If ms(x) is the minimal polynomial of ~ and the degree of ms{x) is d then the polyncmial of~.
f~(X)"
f~(X) :.. {~(x)}k/d
is called the
~ polyncmial
We remark that
TT
k - 1 i.O
(x -
i
~p ) ..
k
x -
k 1
Tr(~)x
-
k..._
+ ••• + (-1)~(~).
In the regular representation of GF(q) as a matrix ring over GF(p) the
trace of the matrix representing ~ is Tr(~) and the characteristic polynomial of this matrix is f~(X). Instead of Tr we sometimes shall use the notation T (x) = x + k
x:P
+
2
xP
+... +
k-l
xP
which is useful if k is not fixed in the problem being discussed.
(3.4.3) THEOREM: If ~ is a primitive n-th root of unity in GF(q) ~ q = pk (k is the mult. order of p modn) then the set
V := (£(s) := (Tr(~), Tr(~~), ••• , Tr(~~n-l»1 ~
e GF(q)}
is an irreducible cyclic code (of length n and dimension k).
57
~:
By (3.4.2) (c) and (d) V is a linear code.
Next we note that
£(~S-l) is a cyclic shift of £(~). Therefore V is a cyclic code. We know that S is a zero of an irreducible polynomial hex) :: h + h,x + ••• + \.xk O since S is in no subfield of GF(q). k
t cihi • Tr(~h(S» i.O
the code V.
= (co,c"
If ..£(~)
••• ,c n _1 ) E V then
:: Tr(O) :: 0, i.e. we have a parity check equation for
Since h(x) is irreducible we see that xkh(x-') 1s the check.
polynomial of V and V is therefore an irreducible code. A
~
ao'
recurring sequence with elements in GF(q) is defined by an initial sequence
a 1 , ••• ,
~-1
and a recursion k
at +
I
i='
=0
biat _i
(t ~ k).
The classical standard technique for finding a solution is to try at
a solution of
= $t.
This is
(*) if S is a root of the equation k \'
k
k-i
h(x) :- x + L bix
- O.
i=' Let us assume that this equation has k distinct roots 9" extension field of GF(q).
82 , ••• , Sk in same
Then, if c l ' c2 ' ••• , ck are arbitrary,
the sequence
k t at = t cia i is a solution of (*). We can then try to choose the c i in such a way i=l
that a O' a"
••• ,
have the prescribed values.
~_,
k linear equations in the unknowns a O' a" is the Vandermonde determinant
$,
f32
1
k-l
8,
13 2
e
2 2
k-l
13 2
••• ,
This means solving a system of The coefficient determinant
~-1.
Sk $2 k
=
TT
i> j
(~.
~
- Bj )
~
o.
k-'
$k
Hence we can solve the equations. n Now let hex) be a divisor of x - 1, (n,q)
= 1.
The linear recurring sequence
58
then is periodic with period n. where
(aO,al'.'.'~_l)
If we consider the set of all (a ,a" ••• ,a _ ) o n 1
runs through all points of R(k) this is an (n,k) cyclic code
and by the definition we see that xkh(x-1) in the check polynomial. tion at"
The presenta-
k
E ci$~ gives us another way of interpreting the code words.
1=1
We describe yet another representation of the code words in a cyclic code. Once again let (n,q) = 1 and let V be a cyclic code of length n over GF(q).
Let $
be a primitive n-th root of unjty.
(3.4.4)
DEFINrrION: The Mattson-Solomon polynomial MS(,£,x) of a code word c
defined as
E V is
n
.:: 1. \' ·
n
L
j=l
n-1
where
SJ := c(SJ) =
L
i=O
(We consider this polynomial as an element of R
= Rls,
i.e. we have x
n
= 1.)
We
then have
(3.4.5) THEOREM: If £
= (cO'c"
••• ,c n _,) is a code word in a cyclic code V and the
Sj are defined as in (3.4.~) then
c
t
~:
MS(£,$t) ..
~
t = MS(£,$)
= 0,1, ••. ,n-1).
(t
n
n
n-1
j=l
j=l
i=O
LSj$-Jt .. ~ Ll3-jt I
Since the inner sum is 0 if i ~ t and n if i
Ci$i
=t
j
..
~
n-1
n
i=O
j=l
I Ci L a(i-t)j.
the result follows.
To determine the degree of the Mattson-Solamon polynomial MS(£,x) we consider the generator g(x):: under _q}.
IT (x
kEK
- $k )of the code V.
(Here K C {1,2, ••• ,n J is invariant
If d is the smallest integer which is not in K then for every j < d we
have c(sj) = 0, i.e. S. :: O. J
We have proved
This means that the degree of MS(£,x) is < n - d.
59
(3.4.6) LEMMA:
If V is a cyclic code generated by g(x) =
TT (x-Sk ),
if
k EK
{1,2, ••. ,d-l} cK and if £ E V then the degree of MS(£,x) is at most n - d. (3.4.7) THEOREM: If there are r n-th roots of unity which are zeros of
MS(£,x) then
w(~) ~ n - r.
The weight of £ 1s the number of coordinates c ~
Proof:
t
o.
By (3.4.5)
there are r values of t for which c = O. t It is sometimes useful to rewrite the Mattson-Solomon polynomial in the following way.
We consider only binary cyclic codes of length n
= 2m -
1.
Then if a is
m
a primitive element of GF(2 ) and .£ a code word in a cyclic code V we have Sj .. j c(a ).
We now observe that S2j .. S~. Now partition
Cl, ••• ,n}
into the cycles of
i
1 n2 • Let deg (a ) denote the degree of the minimal polynomial of a.
Then we have
(in R): (3.4.8)
where the
(3.5. 1 )
*
indicates that one :1 is taken from. each cycle of
Let V be a binary cyclic code with generator g(x).
11
2
•
What condition must
g(x) satisfy if changing all o's to l's and vice versa leaves the code invariant? (3.5.2)
A (9,3) binary linear code V is defined by (a ,8 , ••• ,a ) 1 2 9
(a 1 = a 2 = a and a4 = a = a6 and a = a8 5 3 7 cyclic code and determine the generator.
I:
a )· 9
EV
•
Show that V is equivalent to a
4 (3.5.3) A binary cyclic code of length 63 is generated by x 5 + x + 1.
What is the
minimum distance of this code? (3.5.4) A (63,47) binary cyclic code can be described by specifying some zeros of all code words as was shown in Section 3.2. case'
How many zeros are necessary in this
60
(3.5.5) Consider the binary cyclic code of length 15 with check pol¥00mial 6 4 x + x5 + x + x 3 + 1. Determine the weight enumerator of this code.
(3.5.6) Consider cyclic codes of length
11 over GF(3).
Show that f,(x) := x - 1,
532 S 432 f 2 (x) := x - x + x - x - " f (X) := ~ + x - x + x - 1 are the irreducible 3 l1 2 factors of x - 1. Generalize section 3.3 to show that -1 - x - x ••• _x'O, 10 8 6 2 4 7 1 + x + x + x + x + x and 1 + x + x 3 +x + x 5 + x 9 are the primitive idempatents and that (3.3.4) (i) and (ii) hold. Although the calculation is more lengthy it is possible to show, as in (3.3. 11),
6
8
that M; has weight enumerator 1 + 132z5 + l32z + 330z + 110z9 + 24z 11. this code is
Prove that
perfect~
4 Generate GF(2 ) using the irreducible polynomial x 4 + x + 1. Let a be a ·4 i 3 J primitive element of GF(2). For 0 S. i S. 14 write ex == 1: aiJa with a E GF(2) iJ j=O (3.5.7)
and let
!1
denote the column vector (aiO ' ail' a i2 , a )T. i3
(!:oi' !:.i+ l' !.i+2' 4+3)·
Let Mi be the matrix
Show that the 15 matrices M1 and the zero matrix with
addition and matrix multiplication over GF(2) form a field isomorphic to GF(2 4 ). For 0
S. i
~
i
14 prove that Tr(a ) = trace of Mi
==
&i3.
IV • IMPORTANT CYCLIC CODES
4. 1 BCH codes We now introduce a set of multiple-error correcting codes which were discovered by R. C. Bose and D. K. Ray-Chaudhuri and independently by A. Hocquenghem and which are now known as l£H-codes. Let R = R,(n) as in Chapter 3 and let g(x) be the generator of a cyclic code of length n over GF(q). let
e be
(Again we take (n,q) = 1).
If m is the order of q mod n then
a primitive n-th root of unity in GF(qm).
(4.1.1) DEFINITION:
If g(x) is the product of the minimal polynomials of S,
ad - 1 ,
a2 , ••• ,
(no factor occurring more than once), then the cyclic
code generated by g(x) is called a BaH code (of designed distance d). We remark that a more general definition is used
somet~es
·
quired that g ( x ) is the product of the minimal polynomials of If n = qm - 1 we can take
a=
case the BCH code is called
0;
where
0;
a ,at+ 1,... ,8 t+d-2 .
is a primitive element of GF(qm).
In this
pr~itive.
We now show that the code defined in (4.1.1) has (4.1.2) THEOREM:
in which it is re-
t
min~um
distance at least d.
The minimum distance of a BCH code of designed distance d is at least d.
1st Proof:
We use the symbolic notation of Section 3.2 to define the m(d - 1)
by n matrix H:
an-1 62 (n-1) H :=
d-l 2(d-1) a s.·
A word c is in the BCH code iff £HT = £. are not necessarily linearly independent.
s(n-1)(d-1)
Note that the m(d-1) rows of H Consider any d - 1 columns of H.
62
The determinant of the submatr1x of H obtained by taking the columns headed 1d _1 1, i 2 by ~, := a , ~2:= e , ••• , ~d-l := a is
g,
~2
~d-l
;~
s~
~d-'
2
= ;,g2 .•.
- - ..... d-l ~1 since
~
d-l ~2
~d-l
IT (gi - ~j)
~ 0
i> j
d-l ~d-1
is a primitive n-th root of unity.
Therefore any d - , columns of
£ has
H are linearly independent and this implies that a code word £ ~ weight w(~) ~ d. nd 2 Proof:
If £ is a code word in the BCH-code then by Lemma (3.4.6) the degree
of MS(£,x) is at most n - d.
Therefore in Theorem
0.4.1) r
< n - d and
hence w{.£.) ~ d. The easiest case to treat is again the binary case. Note that since g(e i ) = 0 im2i plies g( ) = 0 every other row in H is superfluous. If n = ,;n - 1 and ex is a
a
m primitive element of GF(2 ) then a polynomial g(x) for which g{a)
= g(ex3)
= ••• =
g(a2t -') = 0 generates a cyclic code which by (4.1.2) corrects any pattern of up to terrors. As an example we take n = 3 1 and t = 4. Now notice that m {x) = 5 5 10 20 q 18 . (X4l )(x4l ){x~ )(x~)(x~ ) = m (x). Therefore g(x) = m,(x)m3(x)m5(x)~(x) 9 2 lO has as zeros a.o. a, a , a and hence g(x) generates 5-error-correcting
02, ... ,
codel
a
This example shows that a BCR code can be better than (4.1.2) promises.
Finding the actual minimal distance of a BCH code is in general a hard problem. Even the easier problem of finding which rows in the matrix H given above are superfluous is not easy. bols in the code. Berlekamp.
This problem amounts to finding the number of information sym-
An algorithm which solves this problem was found by E. R.
It is given in [ 5 ], Chapter 12.
The important thing to realize about
BCH codes is that they have relatively high rates.
Again, take q
= -2,
n
= zn
- ,.
63
If we demand
g(a) = g(ex3 ) = ... = g(ex2t -') = 0 then g(x) generates a t-error- cor-
recting BCH code of length n.
The parity-check matrix for this code can be obtained
by taking a number of rows (maybe all the rows) of
*
H
(:
=
cf- 1 a 3(n-l) a (2t-l )(n-1 mt ---m
Therefore the rate of this code is > ,
- 1
2
Now suppose the rate R is really 1 probability p.
mt
---~ - 1
and consider a ESC with error
The expected number of errors per block at the receiver is pn and
from what we learned in the last part of Section 2.2 we do not expect the BCH code , - R
to be very useful unless t > pn which means -m- > p. not true for large m.
For a fixed rate R this is
Therefore we do not expect a sequence of BCH codes to achieve
what is promised by Shannon's theorem (1.4.3).
Complete information on this problem
is not known yet but the heuristic argument used above shows us what to expect.
For
practical purposes BCH codes are useful even though they are not the very good codes we are still looking for l n =
We give one example of a more general BCH code:
Let
15 and let a be a pr~itive element of GF(2 4), (see the table on page 47). Then
a = ex14
0
,
2
is a primitive 15-th root of unity. If we require g(~ ) = gee ) = g(S ) = 4 g(a 3 ) = g(a ) then by an obvious extension of (4.1.2) g(x) generates a BCH code with
minimum distance ~ 6.
. ~s
ml(x)~(x),
In this example g(x)
4 2 i.e. (x +x+l)(x +x+l)
= mO(x)m3(x)m.y(x).
543 = x6 + x + x + x
+ 1.
The check polynomial Therefore this is the
code of problem 3.5.5. Let us now look at a procedure take a simple example first.
for correcting the errors.
We take n = '5 and as before generate GF(2 4 ) using
x 4 + x + 1, (see the table on page 47). 4
It is useful to
432
J
,
If ex is a primitive element and g(x) =
876
4
m,(x)m (x) = (x +x+l)(x +x +x +x+') = x + x + x + x +' then g(x) generates the 3 (15,7) binary 2-error-correcting BCH code. As a parity check matrix we can take
64
Now let
< 2.
~
be transmitted and y..
Let e.g. the syndrome
=~ + !
received.
We assume that! has weight
lJ:I*T be (11111101). Since this is not Q. we know at
least one error has been made.
If exactly one error was made say in the position
corresponding to a i then fram the first row of H* (i.e. actually the first 4 rows of H* as (O,l)-matrix) we see that
~ = (1111)
i.e. i
= 12,
Then
021 = a36 = a6 =
(0011) and since this is not the second half of the syndrome the assumption that one error was made is false. ing to
~ and
ac1.
Now IH*T
So we turn to two errors, say in positions correspond-
= (~+ ~)H*T
= ~H*T
= (the
transpose of) the sum of the
columns i and j of H* , i.e.
ai
+a
j
(1111)
021 + a 3j = (1101)
= a 12 , = a1 •
the solutions of the equation
2
We cannot solve this equat.ion but by substituting 1, a, a , ... a 3 and alOe
we find the roots
This means that two errors in positions corresponding to 0,3 and a 10
would indeed lead to the syndrome (11111101) and the decoder assumes this to be the error pattern.
In practice the circuitry is designed in such a way that when the
bit Yi is leaVing the decoder this is changed to Y + 1 iff a
i
i
equation.
is a root of the
This simple example illustrates one of the difficulties of decoding.
In
our treatment the procedure depended on the number of errors and if we have e.g. a 5-error-correcting code this would become a complicated matter.
The procedure des-
cribed above, and also the one we describe below, will not always lead to decoding, i.e. failure can occur. Now we shall describe a general decoding procedure.
The presentation will be
somewhat clearer if we use a different notation than we have been using. a t-error-correcting BCH code. be a code word and
~ =
Let Q = ( CO,C 1,··· ,Cn _1 )
= Co + C,x +
Consider
n-1 ••• + C _ x
n 1
R(x) the received word, R(x) = C(x) + E(x) where! =
(E ,E 1 , ••• ,E _1 ) is the error-word. O n
We use the matrix H as in (4.1.2).
The
65
syndrome then gives us 8"
k
k
8 2 , ••• , 8 2t where ~ := R(S ) = E(S ) =
e ~ t errors have occurred then e of the E are not zero.
-----j, j2
ik
•
If
1=0
j
j2
If these correspond to S 1, S , •••
E. ~ 0 are called the error-locations. shall write X, :=
t EiB
The positions where
i
~
n-1
we
B ,X2 = B , •••• The nonzero value of Ei at an error-location
is called an error-value and these ve denote by Y"
(4.'.3) DEFINITION: The polynomial a(z)
:=
locator.
Y2 , ••• , Ye •
e
TT (1
- Xiz) is called the error-
1 =1
The zeros of a(z) are the reciprocals of the error-locations.
5ince
~
can be de-
fined as was done above for all k > 1 we can introduce the formal power series
(4.1.4)
.-
5(z)
00
I k=l
~z
k
•
We then have: 00
S(z)
I k=1
e
8 Z k
e
I i=lI Yi~ = 1=1I i=1I 00
k
zk
==
Yi
fo~l
power series etc.
e
5(z)a(z) = \
.L
Y.X1z
~
~=1
where w(z) is a polynomial of degree
~
e.
f
e
the left-hand side of
(4.1.6)
==
e t
·
1=0
aiz~.
TT (1
jji
I i=l
YiXiZ 1 - XiZ
Therefore we now have
- X.z) =: w(z), J
We can rewrite
equations involving the known quantities 5"
••. , a if a(z)
(Xiz)k =
k=l
where all computations are with
cr ' c" O
e
00
(4.1.5) as a system of
52' ••• , 52t and the unknowns
5ince the coefficients
0
f
Z
(4.1.5) must be 0 we find 0"08 e + 1 + 0",8 e
+ •••
= 0
0"05 e +2 + 0",8 e + 1
+ •••
=0
e+1
,z
e+2
, •••
on
66
A decoding procedure then consists of solving (4.1.6) which gives the error-locations X. and w(z). ~
-1
By substituting z ::: Xi
in w(z) we can then find Y.. 1
This problem has
no mathematical difficulty and only the implementation presents a problem.
But we
have not solved the major difficulty yet, namely: the decoder does not know e. Since we are using maximum likelihood decoding the following theorem solves this problem for us in theory.
(4.1.1) THEOREM:
~
e be the
smallest integer such that there exists a polynomial
a( z) of degree
S.
e with &( 0)
::: 1 and such that 1n the product
&(z)S(z) the coefficients of z
e+l
e+2 , z , ••. , z2t ~
o.
Then
e = e and &(z) = a(z). ~:
Obviously
e So e.
Now we have for k :::
A
A
e
o=
I
e
t=o
a.r,
I
unknowns
a(X~
)Y • i
e
a.r,
I
i=1
Yi~--t
e
Yi~
I
teO
a.r, x~.r, =
Weinterpret this as a set of 2t -
1
I
t=o
2t
A
e
i=1
=
Sk-.t
e+l, .•. ,
Since 2t -
e equations with coefficients
e > 2t
- e
~ and
> e the columns of the coefficient
matrix
~t 1
~t e
are independent (once again using the Vandermonde determinant ~ ) . Y1 are not 0 all the aA( Xi-1) must be zero which proves the theorem.
Since the
67
Theorem (4.1.7) provides the key to the solution of the decoding problem. we need is an algorithm which finds the polynomial condition of
(4.1.1)
etc.
a of lowest
What
degree satisfying the
Such an iterative algorithm was found by E. R. Berlekamp.
The interested reader can find it in [
5 ] ,Chapter 7 and a modification due to
6 ], Chapter 6. We shall not discuss it here nor go further into
J. L. Massey in [
the problems of decoding BCH codes (failure etc).
In previous discussions on weight enumeration of codes we have remarked that to solve this problem it is useful to know the automorphism group of the code.
In
Section 3.3 we used the invariance of binary cyclic codes under the permutation to attack the problem of weight enumeration.
~
For BCH codes we can find many other
automorphisms as we shall now show.
In the following we take n = qm..,,1 and we let
0: be a primitive element of GF{qm).
We consider a BCH code of length n and extend
it by adding an overall parity check.
The overall parity-check symbol, first intro-
duced in Section 2.2 is chosen such that in the extended word the sum of the symbols is
Xi (i
o.
As before we shall denote the positions of the symbols 1n a word by
= 0,1, ••• ,n-1)
where X.1
= o:i.
We shall denote the additional position by X00 00
and we denote the element 0 E GF( qm) by 0:
•
When representing a code word as a
n-1 00 "polynomial" Co + C1x + ••• + Cn_,X + Coox for i ~ 0 (mod n).
00
we shall let 1
u,v
(X):= uX + v
(u
E GF(qm),
v
form a group, the ~ permutation group QE. GF(qm).
E GF(qm),
shift on X ' X" O
such that P
U,V
(Xi) = Y. (i = 1
Y2 with Y, ~ Y2
Notice that Pa,O is the cyclic
••• , Xn _1 and that it leaves Xoo invariant.
every extended cyclic code into itself.
w.
1,2».
u ~ 0)
This group is doubly trans-
itive (i.e. for every pair Xl' X2 with Xl ~ X2 and every pair Y" u,v
=0
The permutations P of the elements of GF(qm) given by u,v
P
there is a P
i 00 := 1 and (0:)
Hence Pa,o transforms
We now prove the following theorem due to
W. Peterson.
(4.'.8) THEOREM:
Every extended BCH code of block length n + 1::: qm ~ GF(q) is invariant under the affine pe~utation group on GF(qm).
68
Proof:
Let
BCH code.
(X,
a 2 , ••• , exd-l be the prescribed zeros of the generator of the
If (CO,Cl, ••• ,Cn_l'C~) is a code word in the extended code and we
apply the permutation P to the positions of the symbols to obtain the u,v permuted word
(CO,C~,
••• ) then for k = 0, 1, ••• , d-l we have
I c~ cfk = I
k
C (ucl+v)k i
I I (~)
=
i i i k
It=o (~) 'V
utvk - t ) C i-.J i i JV i
\
because the inner sum St := ~ ci(a
)
C i
l-citvk-t
=
t=O
(at)i
is 0 for t
=0
= 0,
1, ••• , d-l.
There-
° if for those t
for
i
fore the permuted word is also in the extended code. Observe that in the last line of the proof we would also get which St
~ 0 we would have (~) = o. This immediately yields the following general-
ization of
(4.'.8) due to T. Kasami.
(4.' .9) THEOREM:
Let a: be a primitive element of GF(qm).
If g(x) =
IT (x-cf)
k EK
is
the generator of a cyclic code of len~h n = qm_ 1 ~ GF(q), if
o f.
K
~ Vkac
V t
[(~)
" 0
~
t E K U {O}) then the extended
code is inva~iant under the affine permutation group on GF(qm). The permutation nq which also leaves the extended code invariant is given by q n (X) = X and this permutation is not 'anelement of the affine permutation group q
(unless m = 1 in which case.q is the identity). We shall now consider one example in detail.
As usual we take n = '5 and gen-
erate GF(2 4) using x 4 + x + 1 as in the table on page 47. correcting BCH code.
This code is generated by
Now consider the 2-error-
m,(x)m3 (x) =
2 4 4 (x +x+,)(x +x 3+x +X+l)
which in the terminology of Section 3-3 is f (x)f2 (X). The code is therefore 3 M~ + M + M;. Now apply the method of Section 3. 3 to M~ and M arid then observe
4
4
69
5
that adding on M amounts to doubling the number of code words by adding on the all-1 vector to the generator matrix.
We find the following set of representatives
for the cycles of the BCH code and the connected words in the extended code: Cycle representative (C O,C 1 ' ••• 'C 14 ) 0
(000000000000000)
c:
= (111111111111111) = (011011011011011) = (100100100100100) = (000100110101111) = (111011001010000)
% ~ ~+% !1
~1 +~
C00
length of cycle
weight
weight in extended code
0
1
0
0
1
1
15
16
0
3
10
10
1
3
5
6
0
15
8
8
1
15
1
8
!1 +~
= (011111101110100)
0
15
10
10
~1 + ~ + %
= (100000010001011)
1
15
5
6
0
15
6
6
1
15
9
10
0
15
6
6
1
15
9
10
= (111001000001100) = (000110111110011)
T!1 + 94
T!l + ~ + ~ 2 = (101010010110000) T !1 + 94 2 T e +~+!5= (010101101001111) -1
8 6 The weight enumerator of the BCH code is 1 + 18z5 + 30z + 15z1 + 15z + 30z 9 + 6 15 + 18z 10 + z15 and the weight enumerator for the extended code is 1 + 48z + 30z + 48z 10 + z16 • The pennutations P are generated by P", 0 and the four"transu,v ~,
,
lations" P1 , l' P 1 a,' P1
,of, P, ,a,3.
Using the table on page 41 we find
Pu,v
permutation of (XO' Xl' ••• , X14 , Xoo )
p 1, 1
(0,00)(1,4)(2,8)(3,14)(5,10)(6,13)(1,9)(11,12)
P 1,a,
(0,4)(1,00)(2,5)(3,9)(6,11)(7,14)(8,10)(12,13)
,rJ
(0,8)(1,5)(2,00)(3,6)(4,10)(1,12)(9,11)(13,14)
P 1,a3
(0,14)(1,9)(2,6)(3,00)(4,7)(5,11)(8,13)(10,12)
Pl
70
If we examine the action of these
pe~utations
on
!,
we see that the first three
leave (~1'0) invariant and P1,a3 transforms it into (~1 + ~5,1).
Since the two
5
cycles !1 and ~1 + ~ with .Q and ~ form the code words of ~ + M which is the 3error-correcting BCH code we could have expected this kind of behavior from As a second example we apply P 1,a to
(T!,
6 which is (T (~1+ ~+ ~),1).
+ 94 ,0).
(4.1.8).
This yields (0010111000000101)
The following theorem, due to E. Prange, shows how knowledge of the type of Theorem (4.1.8) can be used in weight enumeration. n
(4.1.10) THEOREa~: If a(z) := .E aiz
i
is the weight enumerator of a linear binary n+1 . code of block length n and A(z) := E A.z~ is the weight enumer1=0 l~=O
ator of the extended code
and if this extended code is invariant
under a transitive permutation group then for all 1 2i a 2i a 2i - 1 = n+ 1 - 2i 1. e •
Proof: a
a( z)
Clearly A2i
= A( z)
+
= a 2i _1 +
- words of weight 2i 2i 1
hav~
code words of weight 21 is 2iA a transitive
pe~utation
~:~
5..!-A n+ 1 2i'
A' ( z ) •
a 2i and A2i - 1
= O. ex)
a 1 in position a. 21
•
In the extended code The total weight of the
If the extended code is invariant under
group this weight is divided equally among the n+1
positions, i.e. (n+l)a2i _1 = 2iA from which the theorem follows. 2i The weight enumerators of the 2-error-correcting BCH code which we calculated above are an example.
Combining
(4.1.8)
and (4.1.10) we find
(4.1 .11) THEOREM: The minimum weight of a binary BCH code is odd if m
4.2
2m - 1.
Reed-Solomon codes Up to now we have been concerned mostly with random errors and we have paid no
attention to the problem of correcting burst errors.
We now consider codes
71
introduced by I. S. Reed and G. Solanon which turned out to be a special kind of BCR codes and with which the problem of burst error correction can be attacked. First we shall define what we mean by a burst error. (4.2.1) DEFINITION: A ~ of length d is a vector whose only nonzero components are among d successive canponents of which the first and the last are not zero.
A
~ ~
is an error vector which is a burst.
The following is a very simple theorem concerning these errors. (4.2.2) THEOREM: Every (n,k) cyclic code can detect any burst error of length d ~:
< n - k.
An error vector is detected if it is not a code word.
length d
:s. n
A burst of
i
- k has the form x a(x) where a(x) has degree d - 1 ~ n - k - 1.
Hence a(x) is not divisible by g(x), the generator of the (n,k) code, since g(x) has degree n - k.
Therefore no burst vector of length d
Sn
- k is a
code word. We now first introduce the Reed-Solomon codes (RS-codes) and we will come back to the problem of burst errors later. (4.2.3) DEFINITION: A Reed-Solomon code is a BCR code of length n By (4.1.1) the generator of the code has the form g(x) =
d -,
TT
i= 1 pr~itive
=q
- lover GF(q).
i (x~) where a is a
element of GF(q) (which then is a prfmitive n-th root of unity).
Clearly
RS codes are only interesting for large q (the binary RS code has word length 1). The dfmension of the code with generator of degree d - 1 is k = n + 1 - d. (4.1.2) we know that the minimum distance of this RS code is at least d. consider any linear code of block length n and dimension k.
From Now let us
If we consider k - 1
positions and look at the code words which have zeros in these positions we obtain a subcode of dfmension at least 1 (since the k - 1 extra parity checks a
••• = a i
K-l
i1
= a.
= 0 are not necessarily independent of the other parity checks).
subcode has minimum distance at most n - k + 1 (namely the block length) and
~2
=
This
72
therefore this is also true for the original code.
(An other way of seeing this is
by remarking that every set of n - k + 1 columns of the parity check matrix H
= (_pTI n-k)
Hence d < n - k + 1.) From what we remarked
is linearly dependent.
above we now see that we have proved:
(4.2.4) THEOREM:
The minimum distance of the RS code with generator
g(x) =
d- 1
IT
i=1
(x-ai ) is d. -
The RS codes are examples of codes which are sometimes called optimal (n,k) codes for which the minimum distance is d
=n
~,
i.e.
- k + 1 (which is thea priori
maximum). If we consider a set of d positions and then loOk at the subcode of an optimal
code with zeros in all other positions this subcode has dimension
~k
- (n-d)
Since this subcode has minimum distance d it must have dimension exactly 1. follows that, for n
~
d'
~
= 1. It
d, specifying a set of d' positions and requiring the
code words to be 0 in all other positions will define a subcode of dimension d' - d + 1 of the optimal code, i.e.
(4.2.5) THEOREM:
~
n :::. d' ~ d
=n
+ 1 - k the subcode of an optimal (n,k) code
consisting of those code words which have zeros outside a set of d' positions has dimension d' - d + 1. For a RS code the Mattson Solomon polynomial of a code word k - 1 by
(3.4.6).
This polynomial has coefficients in GF(q).
a way to encode infonnation. coded into ~ MS(£,x).
~
= (F(l), F(a),
has degree
~
n - d
=
This provides us with
The sequence (aO,al' ••• '~_l) of information bits is ,." F(aq - 2 » where F(X) = a O + a 1x + ". + ~_lxk-l =
The RS codes are used in the following way.
over GF(qm) has word length n
= qm
A t-error-correcting RS code
- 1 and dimension n - 2t.
If we write each sym-
bol in GF(qm) as a vector of length mover GF(q) we obtain a new linear code of length nm and dimension (n-2t)m over GF( q).
This code is then a good code to use
to correct burst errors since a burst of length b
S (t-l)m +
1 affects at most t
consecutive symbols of the original code, an error which is corrected.
Of course
73
this code can also correct t random errors but that is not very good. hand if several bursts occur which together affect they are all corrected:
~
On the other
t symbols of the original code
RS codes campare favorably with same other codes used for
burst error correction. It is possible to find the weight enumerator of an optimal code using (4.2.5)
and the principle of inclusion a.nd exclusion.
To do this we first prove an analog
of the M8'bius inversion formula.
(4.2.6) DEFINITION:
If N is a finite set and S CT
C
N then we define
,-,(S,T) := (_1)ITI-lsl.
(4.2.7) THEOREM: Let N be a finite set and let f be a function defined on P(N).
I
g(S) := feR) Res then
f(T) ..
I
~(S,T)g(S).
SCT
Proof:
I
I
I
iJo(S,T)g(S) .. iJo(S,T) f (R) .. seT SCT Res
.. I RCT
feR)
I
iJo(S,T)
RCSCT
and the proof now follows fran the equality
Now we have
(4.2.8) THEOREM: Let V be an (n,k) optimal code over GF(q) and let 1 + where d = n + 1 - k, be the weight enumerator of V.
n
t
i=d
~
i A.z , J.
If
74
1-d
Ai = (~)
l: (_1)j(~)(qi-j-d+1
- 1)
.1=0 i-d =
(~)(q-1)
l:
(_1)j(i 1)qi- j -d
j
.1=0 Proof:
(i = d,d+1, ••• ,n) .
Take N := (O,l, ••• ,n-l) and for R E P(N) define f(R) := number of
code words (c ,c 1, ••• ,c _ ) for which c ~ a ~ i ~ R. n 1 1 O (4.2.7) we have by (4.2.5) g(S)
==
q Is I-d+ 1
if
lsi S d
if
n
l:
Rai,IRI=i
l:
(_nIHI-lsl
. (~){ I
f(R) and therefore applica-
g(S) •
i
(~)(-ni-j +
.1=0 i
d •
SCR
d-1
= (~){l:
as in
RCN,IRI=1
tion of (4.2.1) yields Ai =
g
- 1,
~ lsi ~ t
By our definition of f we have Ai ==
If we define
l:
(~)(_ni-j qj-d+1}=
jed
(~)( _n i - j ( qj-d+1 - 1) •
i-d
(~)
l:
(~)( -n j ( qi-j-d+l
- 1)
.1.0
jed
i
fran which the second assertion of the theorem follows if we replace (.1) by
i-1) + (1-1 (.1.1 ) and take together the tenms with (1) .1 • 1
(4.2.9) COROLlARY:
If an optimal (n,k) code over GF(q) exists then q ~ n - k + 1
or k < 1. Proof:
Let d = n - k + 1.
By
(4.2.8) we lJave (if d < n) 0
~Ad+l
I:
(d~1 ) ( q -1 ) (q -d). Another inequality of this kind can be obtained by considering a set R eN with
IRI
-= d - 2.
Fix a position outside R.
By
(4.2.5) we can find a code word which
75
has a 1 in this position, nonzero coefficients in the positions of R and one other nonzero coefficient in any of the remaining positions. have distance
~
d the parts corresponding to the positions of R must have distance
d - 2 for any pair of these words. of these words.
Since two such code words
This is impossible if there are more than q - 1
This proves:
(4.2.10) THEOREM: If an optimal (n,k) code over GF{q) exists then q::: k + d
I:
n - k + 1
< 2.
Actually (4.2.9) and (4.2.10) are dual theorems. (4.2.11) THEOREM: If an ~:
Let G
(n~k)
= (~p)
This is shown by
code 1s optimal then the dual code is also optimal. be the generator matrix of an (n,k) code.
is optimal iff every set of d - 1 H :: (_pT I
or
=n
This code
- k columns of the parity-check matrix
k) is linearly independent and this is equivalent to saying that
n-
every square submatrix of -PT has a nonzero determinant.
This t.hen also
holds for P and since G is the parity check matrix of the dual code this code is also optimal.
4.3 Generalized Reed-Muller codes We now consider a class of (extended) cyclic codes some of which will turn out to be equivalent to the RM codes defined in
(2.3.6). First, we generalize the idea
of Hamming-weight to integers written in the q-ary number system:
(4.3.1) DEFINITION: If q is an integer::: i Remark:
= 0,
2 and j c
m-l 1:
1=0
i
~iq,
with 0
S ~i
< q for
m-l 1, ••• , m-1, then we define w (j) := t ~i. q i=O
Note that the sum in
(4.3.1) is taken 1n Z.
The codes we wish to study are now defined as follows:
(4.3.2) DEFINITION: The shortened r-th order generalized Reed-Muller code (GRM code) of length n :: qm - lover GF{q) is the cyclic code with
76
generator
IT m
g(x):-
j
(x -a ),
O<j
O<w \j)«q-l)m-r -q where ex is a primitive element in GF(qm).
The r-th order
GRM code of length qm has the generator matrix 1 1 1 1 0
0
*
G :=
G
0
where G is a generator matrix for the shortened GRM code. (It is obvious that the set of exponents j in (4.3.2) is closed under multiplication by q). code.
Notice that by (3.2.2) replacing a by ex In terms of
-1
in (4.3.2) yields an equivalent
ex this code has generator
and the dual code then has generator
h*{X):=
IT
O<j
(x - ~).
-
From this we prove:
(4.3.3) THEOREM: The dual of the r-th order GRM code of length
cf
is equivalent to
! ({q-l)m-r-l)-st order GRM code. Proof:
From what we showed above we know that (x-l)h* (x) is the generator
of a «q-1)m-r-l)-st order shortened Gmt code.
If we now lengthen the
cyclic codes to obtain the two GRM codes we findas generator matrices
77
and
G
A
H
A where H is the generator matrix of the code with (x-l)h* (x) as generator
polynomial.
For the two matrices orthogonality of all rows except the first
is a consequence of what we proved above. , word is orthogonal to 1 tsel! • multiple of q.
We now have to show that the all-
This is true since the word length is a
For the other rows in the two matrices this orthogonality is
a consequence of the factor (x-l) in both of the generators.
The proof is
complete since the dimensions of the lengthened cyclic codes have sum qm. To show the connection of these codes with the codes defined in Section 2.3 we must first prove a lemma.
(4.3.4) LEMMA:
Let (n,q) = 1.
Let V, be a cyclic code of length n over GF(q) with
check polynomial i(x)
k,
= IT i= 1
(x-<X ). i
Let V2 be a cyclic code of the k
same length over GF(q) with check polynomial f (x) = 2 By flex)
*
=1
f 2 (x) we denote the polynomial which divides x
which has as its zeros all products aiS j (i • J
j
2
IT
(x-e.). J
n
= l,2, ••• ,k,;
- 1 and j
= 1,2, ••
k ); (note that these products need not all be different). 2
The
set of words
generates a cyclic code which is a subcode of the code with flex) ~ f
Proof:
2
(x) as check polynomial.
The assertion is an immediate consequence of one of. the representa-
tions of cyclic codes we studied in Section 3.4 namely the one using linear recurring sequences. • • •J
We know there are constants c l ' c2 ,
c' such that for t = 0, 1, ••• , n-1 we have k2
... ,
~
and 1
78
k
and
b-r,
=
I
2
cja;t
j=l
fran which we find that for t
= 0,
1, ••• , n-l the components atb
t are lin-
ear combinations (With coefficients independent of -t) of the reciprocals of zeros of f 1 (x)
~
f 2 (x), proving the lemma.
Now the correspondence we referred to is: (4.3.5) THEOREM:
~ r-th order GRM code of length 2
m
~ GF(2) is equivalent to
the r-th order RM code of length 2m• ~:
The proof is by induction.
Since for r = 0 the codes defined by
(2.3.6) and (4.3.2) are repetition codes, they are identical.
For r
= 1 we
have already proved (4.3.5) namely by a combination of (2.3.7), (2.3.8) and (3.2.1) and (4.3.3). a primitive element
a
Now assume (4.3.5) is true for same r. We can choose E GF(2m) in such a way that the check polynomial of
the shortened r-th order GRM code is h*(x)
=
j
IT
O<j~-l,
(x - a ).
The check
w2(j)~r
polynomial of the shortened l-st order RM code is h~(X):= Now h* (x) ® h~ (x) =
IT
O<j~-l w2 (j)S,r+1
j
(x-o: ), (for r < m-2).
IT m
(x -a:
j
).
O<j<2 -l, w (j)= 1 2
The procedure described
in (4.3.4) corresponds to the way one goes from the r-th order RM code to the (r+l)-st order RM code by definition (2.3.6).
Therefore (4.3.5) follows
from (4.3.4). In Sections 2.3 and 2.4 two error-correction procedures for RM codes were described.
The method of threshold decoding can be used with a fixed scheme
for all the pos-
itions of the shortened code if this one is represented in the manner of this section, making it a cyclic code.
The decoding procedure described partially in
Section 4.1 can also be used as we shall now show.
79
(4.3.6) THEOREM:
~ r-th order GRM code of length qm ~ GF(q) is a subcode of
the extended BCH code of designed distance r =
Proof:
Q(q-l) + R, 0
~ R.<
d = (q_R)qm- Q-l ~
q-l.
For all j < d-l the number w (j) is less than q
Q Q«Q_R)qm- -1 - 1) = (Q-R-1) +
m-Q-2
W
2:
(Q-1)
=
i=O
(q-l)(m-Q-l) + (q-R-l)
= (q-1)m o
1
Hence a , a , .•. , a order GRM code. Note that
4.4
d-2
_. r.
are among the zeros of the generator of the r-th
(Here we use the more general definition of BCH code).
(4.3.6) generalizes (2.3.)4).
~adratic
residue codes
(4.4.1) Notation: (i) In this section n will denote an odd
pr~e.
(ii) a is a prfmitive n-th root of unity in an extension field of (iii)
GF(q). R denotes the set of quadratic residues mod n, i.e. those O elements ~ 0 in GF(n) which are squares; R, is the set of nonzero elements of GF(n) which are not in RO•
(iv)
gO(x)
:=
Note that
IT (x - a r ), g, (x)
rERO
:=
IT (x - cl').
rERl
xn - 1 = (x-l)go(x)g,(x). n-l
2
In the following we shall assume that q
== 1 (mod n) or in other words that q is
a quadratic residue mod n. The nonzero
~lements
of GF(n) are powers of a primitive element a E GF(n).
Clearly ae is a quadratic residue if e a 0 (mod 2) and a non-residue if e
(mod 2).
The product of two (non-) residues is a quadratic residue.
=1
Since q is a
quadratic residue the set RO is closed under multiplication by q (mod n).
80
We then are able to define:
(4.4.2) DEFINITION: The cyclic codes of length n over GF(q) with generators gO(x) and (x-1)go(x) are both called quadratic residue codes codes).
(QR-
The extended quadratic residue code of length n + 1 is
obtained by annexing an overall parity check to the code with generator go(x). We remark that in the binary case the code with generator (x-l)gO(x) consists of the words of even weight in the code with generator gO(x). for the first of these codes then
~dding
If G is a generator matrix
the all-one vector will yield a generator
matrix for the second code and the generator matrix for the extended code will then
be
In the binary case the condition that q is a quadratic residue mod n is satis-
fied if n
= ±1
(mod 8).
To show this we consider the integers 1, 2, ""
If we multiply all these by 2 we obtain the even integers
~ n;l and the even inte-
n-1 which we can write as x = -y in GF ( n ) where 1 gers x > ~ of these is v
n-1 =~
if n
=1
( 1 if n mod) 4 and v = n+ ~
~(n-l}l2 2 2 i
rr
= -1
n;l •
n-1 S y S ~. ( mod) 4.
The number Hence
(n-1Y2 III
(-1) v
1=1
IT j
(mod n)
j=l
(it is easily seen that after the above reduction each factor
n-1
~ ~
occurs once).
Since the two products are not divisible by n we find that n-1
2~
= 1 (mod
n) if v is even, i.e. n
=±1
(mod
8).
E H, the permutation n j maps HO into R, and vice versa. From (3. 2 .2) it then follows that if we replace RO by R, in (4.4.2) we obtain equivalent
We saw above that if j
codes.
If n
= -1
(mod 4) then -1 E R, and therefore the transformation x
~
x
-1
maps a code word of the code with generator go(x) into a code word of the code with generator g, (x).
81
We now prove some theorems which will enable us to find inequalities for the n-l i Let us consider a code word c(x) = t cix of the code n-1 i=O with generator gO(x) for which I: c ~ 0 (i.e. the code word. does not belong to the i i=O
minimum weight of QR-codes.
QR-code with generator (x-l )go(x».
As we saw above a suitable" j will permute
c(x) into a word c(x) which is divisible by g1 (x) but again not by (x-l).
£ is
weight of £ is d then the weight of nomial with at most d
2
If the
also d and the product c(x)c(x) 1s a poly-
nonzero coefficients.
Since c(x)c(x) is a multiple of
gO(x)g, (x) and not a multiple of (x-l) it must be a constant multiple of 1 + x + x
2
+ ••• + x
n-1
•
(4.4.3) TIm:OREM:
This proves the following theorem:
=
If a code word c(x) i: c i i=O
d
Remark:
1
1: cix of the code with generator so(x), i:::O ~ OJ has weight d then
n-1
for which
n-1
2
> n.
Since n is prime, equality in (4.4.3) is impossible.
The following improvement is possible 1f n == -1 (mod 4). that in this case we could take c(x)
= c(x-').
We remaIked above
In this case the product c(x)c(x)
2 has d terms of the form cixO, i.e. c(x)c(x) has at most d - d + 1 nonzero coefficients:
(4.4.4) THEOREM:
~ n a -1 (mod
4). If a code word c{x) n-1
witb generator so(x), for which.k ~:::o
d
2
- d + 1
This type of argument can be extended further.
c
i
product c(x)c(x) ::: 1 +
I: 1: x
1 ~ j
the terms cancel, i.e. if e e
j
- e
i
== e
t
Therefore d
2
i
i
Suppose c(x)
j will have less than d
- e j :::
~
- e
1: cix of the QR-code i=O ~ 0, has weight d then
> n.
odd weight d in the binary QR-code with generator gO(x).
e -e
1
n-1
c:
d
= 1:
1:::1
x
e
i
is a word of
Let n == -1 (mod 8). 2
The
- d + 1 terms if some of
t for some i,j,k,t.
In that case also
- eke Apparently the number of terms which cancel is a multiple of 4. - d + 1 - 4!, == n which implies that d a 3 (mod 4):
82
(4.4.5)
!f.
THEOREM:
= -1
n
(mod
8)
and .£ is a code word of odd weight d in the
binary QR-code with generator gO(x) ~ d We shall now study in more detail the binary QR-codes.
= ±1
=3
(mod
4).
Again n is a prime
(mod 8) and ex is a pr~itive n-th root of unity in·an.extension field of GF(2).
Let us consider the polynomial e(x)
Since R is closed under multiplication by 2 we see that e(x) is an idempotent in O n the ring a of polynomials over GF(2) mod x - 1. Hence (e(ex)}2 = e(a) which implies i In the same way we see that e(a )
that 9(0) E GF(2). other hand, i E R
9(a)
1
then
e(ai
) +
9(a)
=
t
af
reO~l
a
==
= e(ex)
+
oF +
ar- 1
••• +
'
If, on the == 1.
Since
cannot be equal to one for all the primitive n-th roots of unity we can choose
a in such a way that e(a) = O. This then implies that e(ai ) 9(01 ) = 1 if 1 € R,. n
if 1 E R • O
= -1
(mod
8).
== 0 if i E R
If i = 0 then 9(01 ) = n;' which is 0 if n
O
E ,
and
(mod 8)"and , if
It follows that e(x) is a multiple of (x-l)go(x) if n e 1 (mod
8)
and that e(x) is a multiple of go(x) if n :; -1 (mod 8) and in fact we have shown:
(4.4.6) THEOREM:
If the primitive n-th root of unity ex in chosen then the polynomial 9(x) ==
1:
(4.4.1)
(ii) is suitably
xr is the idempotent of the
reO binary QR-code with generator (x-l)gO(x) if n :: 1 (mod 8) and of the code with generator go(x) if n
= -1
(mod
8).
To obtain the extended code in the case n == 1 (mod 8) we must annex the all one vector to the generator matrix of the code with (x-1)gO(x) as generator.
In the
case n == -1 (mod 8) we just annex an overall parity check to the words of the QRcode with go(x) as generator (see the remark following (4.4.2». circulant matrix with the code word! as its first row.
n
=1
(mod 8) and
~ :=
Let £ := (0 0 ••• 0) if
(1 , 1 ••• 1) if n s -1 (mod 8) and define G :=
c
')
Iiow let C be the
83
We then have the following
consequ~nce
of
(4.4.6):
(4.4.7) COROLLARY: The rows of G generate the extended binary QR-code of length n + 1.
Of course the rows of G are not linearly independent since there are twice as many as the dimension of the code.
The representation of
(4.4.7) will be useful in the
following discussion on pennutations which leave the extended QR-code invariant. We shall number the positions of the symbols in the extended QR-code using the coordinates of the projective line of order n, i.e.
00,
0, 1, ••• , n-1.
We make the
usual conventions about arithmetic operations With these coordinates e.g. ±O ~
-1
= 0,
(4.4.8)
00
+a =
THEOREM:
00
= 0,
for a
"
-1
=
00,
.••• ,n-1 etc.
The extended binary QR-code of length n +
is invariant under the
group PSL (2,n) acting on the positions.
~: The group PSL(2,n) consists of with a,b,c,d in GF(n) and ad - bc
= ,.
all the transformations x ...
This group is generated by the two
transformations Sx := x + 1 and Tx := -x -1 leaves position
00
T
Since the transformation S
invariant and since it is a
positions it leaves the code invariant.
(4.4.7). Apply
~ : ~
cyclic shift of the other
To study the action of T we use
to the rows and columns of G to obtain the matrix
H := [hij ] which generates the permuted code. We consider a number of cases separately: (i)
row (ii) -j
-1
If i 00
=0
= goo,_j-1 = 1
then hij
for all j, i.e. row 0 of H is equal to
of G. If i E RO
=
00
then hij = gO,_j-1.
If n == 1 (mod 8) then j
since in this case -1 is a square and therefore
which proves that row
00
of H is equal to row 0 of G.
(mod 8 )then j E RO iff -j
go ,-j-1 = goo,J.
+
go, j'
-1
E R, and
go,o
e RO iff go,o
= go,oo = 0
If, however, n == -1
= 0 while go,oo = 1.
In that case
i.e. row 0 of H is the sum of two rows of G.
84
(iii)
Consider row i of H where i E R • O
Add row i of G to this row.
the sum row we have zeros for j = 1, for j = those j
1.
r
0 for which j - 1 and -j
-1
+ 1
00
In
if n :: -1 (mod 8) and for
-1
are both in R or both in R,. O .1 -1) This last condition is satisfied iff ( j-1 ) (-j +i E Ro ' i.e. ij E RO' i. e. j E R • O 00
0
This proves that the sum row is equal to the sum of rows 0 and
of G, i.e. row i of H is the sum of 3 rows of G.
(iv) We leave as an exercise to the reader to show that if i E R, then row i of H is the sum of 2 rows of G. Apparently the permuted code is a subcode of the original code. two codes are equivalent they are identical. Thanks to
This completes the proof.
(4.4.8) the Theorems (4.4.3) to (4.4.5) will now become very useful.
group PSL (2,n) is doubly transitive.
and
(4.4.4)
(4.4.9) THEOREM:
The
Just as in (4.1.11) it follows from (4.1.10)
that the minimum weight of the QR-code with generator gO(x) is odd.
(4.4.3)
Since the
Therefore
yield:
The minimum weight of the QR code of length nwith generator gO(x) is an odd number d for which
(4.4.10) Example:
2
> n if n!i
(i)
d
(ii)
2 d - d + 1
1 (mod 8),
> n if n
= -1
(mod
8).
Over GF(2) we have
x23 _ 1
(x_l)(xl1+x9+x7+x6+x5+X+l)(x11+x10+x6+x5+x4+x2+1)
I:
The binary QR code of length 23 with generator go(x) is a (23) 12) code.
By
(4.4.9)
d(d-l ) ~ 22.
the min~um distance d of this code satisfies
Since d 1s odd we have d ~ 7.
The code is at least
3-error-correcting.
Now the number of words in a sphere of radius 3 23 11 3 around a code word is t (i) = 2 • It follows that the code 1=0
has minimum distance 7 and that the code
1s perfect!
This code
is known as the binary Golay~. If we had applied (4.1.2) to
85
find the minimum distance of this code we would have found d (4.4.11) Example: Consider the binary QR-code of length 47.
~
5.
By (4.4.9) the minimum
distance d of this code is at least 9. Now we apply (4.4.5) to 6 41 23 find d ~ 11. Since I: (i) > 2 the code cannot be 6-errori=O correcting, i.e. d = 11. Severa.l QR-codes are better than BCH codes but the decoding of these codes is not as easy.
We shall not discuss decoding methods at all.
The interested reader 1s re-
ferred to F. J. MacWilliams, Permutation Decoding of Systematic Codes, Bell System Tech. J. 43 (1964), 485-505.
4.5 Problems (4.5.1)
Let a be a primitive element of GF(3 3 ) satisfying a 3
gene~tor
=a -
1.
What is the
of the 2-error-correct1ng ternary BCH code of length 26 if we use a as the
primitive 26-th root of unity in (4.1.1)t (4.5.2) What is the dimension of the ternary 5-error-correct1ng BCH code of length
Bot (4.5.3)
2 Let a be a zero of x5 + x + 1 in GF(2 5 ).
error-correcting BCH code of (1110011101) (4.5.4)
~ength
31.
We use a to define a binary 2-
If a received word has the syndrome
find the positions where errors have been made.
If an (n,k) optimal code over GF(q) is a perfect 2-error-correcting code
and k > 1, then e == 1.
Prove this by considering the number of code words of
weight 2e + 1. (4.5.5) Prove that the 2-nd order GRM code of length 25 over GF(5) has dimension 6 and minimum distance d == 15. (4.5.6) Show that the ternary QR code of length 11 with generator go(x) has minimum distance 5.
Prove that this code 1s perfect.
COJD.1)8.re with (3.5.6).
v• 5.1 Perfect
PERF~T
CODES
single-error-co~ectingcodes
The concept "perfect code" was introduced in
(2.2.3) and then in (2.2.4) it
was shown that Hamming codes over GF(q) are perfect. We recall that these codes qm 1 were defined as follows: Let H be the m by n := ----, matrix consisting of all q the different nonzero columns with elements from GF(q) such that the first nonzero entry in each column is 1.
Since no linear combination of two columns can be Q we
see that H is the parity check matrix of a linear (n,k) code over GF(q) with minimum distance 3.
Because qk(l + n(q-l»)
= qm+k
= qn the code is perfect.
In (3.2.1) it was shown that binary Hamming codes are equivalent to cyclic
This is not true for all Hamming codes but it is possible to generalize qm_ , (3.2.1). Let n := q-::-r and let a be a primitive element in GF(qm). If we define
cod~s.
e :=
Qq -1 then
e is
a primitive n-th root of unity.
Now
length n with as generator g(x) the minimal polynomial
S m,
i.e. the dimension of V is
~
n - m.
let
of~.
V
be the cyclic code of
The degree of g(x) is
If the code is single-error-correcting it
is again perfect because (1 + n(q-l )}qn-m == qn.
To show that the minimum distance
of the code is at least 3 we must prove that for 0 < e < n and a E GF(q) the genere ator g(x) does not divide x - a. This is the case if Se ~ GF(q) for 0 < e < n, i.e. ae (q-l) ~ for 0 < e < n. Therefore it is necessary and sufficient to require that (n,q-l) == 1 which is true iff (m,q-l) == 1. cyclic code is
The parity-check matrix of this
• which every (l,S,S 2 , ••. ,S n-l) which is a m by n matrix over GF(q) for
pair of columns is linearly independent just as we had for the matrix H above. From this discussion it follows that the first method of generaliZing the binary Hamming codes yields more perfect codes than the method using cyclic codes. The smallest example where the cycliq-code approach fails is q == 3, m = 2 in which case n
II:
4.
It is easily seen that the (4,2) ternary Hamming code...is not equivalent
to a cyclic code (see problem
(1.5.1».
Now we turn to the question whether there are other perfect single-error-correcting codes than the ones mentioned above.
Let us consider an alphabet of q
87
symbols where q is no longer necessarily a power of a prime but an arbitrary integer. Consider the set Q(n) of all
n~letter words
with symbols from this alphabet and let
V C Q(n) be a perfect single-error-correcting code.
This implies that the total
number of words, i.e. qn, is a multiple of the number of words in a sphere of radius 1 which is 1 + n(q-l). (5.1.1) THEOREM.
Therefore we have
A necessary condition for the existence of a perfect single-errorcorrecting code of
le~h
n over an alEhabet of q symbols is
[1 + n(q-l)] If q
= po"
I
qn.
is a power of a prime this implies 1 + n(q-l) = qa.
Proof: We only have to show the last part.
If 1 + n(q-l) = pAqa with
o ~ A < a then we have
The first
te~
on the right-hand side is an integer.
The second
te~
is an
integer only if A = O. The only case where q is not a power of a prime for which it is known if a perfect code exists is n = 7, q = 6.
The following proof is due to R. E. Block and M. Hall.
Let V be a perfect single-error-correcting code of length 7 over the alphabet of 6 symbols (which we shall denote by 1,2,3,4,5,6).
The code V has 65 words (c"c 2 , ••• ,
c ) and no two of these can have the same initial 5-letter word (c 1,c 2 , ••• ,c ) since 5 7 the minimum distance of V is 3. There are exactly 65 possible 5-tuples (c 1,c2 , ••• , c ) and therefore each of these is the initial 5-tuple of one code word. of V. There5 fore V contains 36 words of type (l,l,l,i,j,aij ,b ij ) and for these 36 words all pairs (i,J) are distinct.
Now define the two 6 X 6 matrices A and B byA := [aijl,
B := [bij ] (i = 1, ••• ,6j j = 1, ••• ,6). Since the 36 words (l,l,l,i,j,aij ,b ij ) have distance ~ 3 no row or column of A and B can contain the same symbol twice. Furthermore all pairs (aiJ,b ij ) are distinct. Therefore A and B are two orthogonal Latin squares of order 6. It is known that two such Latin squares do not exist (cf. H. J. Ryser, Combinatorial Mathematics, p. 84).
This proves:
88
(5.1.2) THEOREM:
A perfect single-arror-correcting code of
le~h
1
~
6-
symbol alphabet does not exist. Since a pair of orthogonal Latin squares of order q can be found for q ~ 2 or 6 we cannot generalize the proof of (5.1.2).
The reasoning in the following proof re-
sembles that of (5.1.2).
(5. 1. 3) THEOREM:
If, a perfect single-error-correcting code of length n = q + ,
~
an alphabet of q symbols is a group code then q is a power of a prime.
~:
Let R(n) be the direct product of n copies of the abelian group G of
order q.
Just as in the proof of (5. 1.2) we see that in a perfect code
V CR(n) each (q-l)-tuple (c ,c , ••• ,c _ ) occurs exactly once as the init1 2 q 1
ial (q-1)-tuple of a code word.
For i
= 1,
pings O'i: G ... G and T : G .. G as follows. i (c"c 2 ' ••• 'c q+,) with c i
=a
and c j
2, ••• , q-1 we define the mapFor a
e G there
= ° for j # i,
1
Sj
is one code word
~ q-1.
We define
(a) := cq+1 • Clearly C i &nd T i are permutations of G which Since V is a subgroup of R(n) we have V Vb€G[a i (a+b) = afG
O'i (a) := c q ' fix O.
Ti
0'1 (a) + O'i (b)] and an analogous relation for T •
i
automorphisms of the group G.
aq- ,(c q- ,), c q , c q+1)
Therefore O'i and Ti are
The code with words (a, (c,), 0'2(c 2 ), ••.• ,
is also a perfect group code V'.
This code V' has
code words ~(i,a) := (O,o, ••• ,o,a,o, ••• ,O,a,Ti(a» where the first a is in position i (1
Si
~ q-l)
and Ti is an automorphism of G.
For a E G and
1 ~ i 1 < i2
S q-1
the words £ (i"a) and ~ (i 2 ,a) have distance 3 only if
(a) ~
(a).
Now let p be a prime plq and let a E G be an element of
T
i1
T. 1. 2
order p in G. (1
~
i
S q-')
Since V'is a group code the q-l distinct elements Ti(a) also have order p, i.e. every nonzero element of G has order p.
Therefore q is a power of the prime p. The proof of
(5. 1 .3) is due to B.
Lindst~m.
The theorem shows that if a perfect
single-error-correcting code of length q+1 over an alphabet of q elements, where q
89
is not a prime -power, exists then the code will not have anything like the algebraic structure of the codes we have studied in this course. A method of showing non-existence of certain codes which sometimes leads to success is the following.
If one can find the weight enumerator of the code (which
supposedly exists) fram the properties of the code and if at least one of the coefficients of this polynomial is not a non-negative integer then clearly the code cannot exist.
An example of this method is (4.2.9).
Although the method is going to
fail in this section we shall nevertheless illustrate the attempt. Let us assume that a perfect code V of length n over an alphabet of q symbols
exists.
Without loss of generality we can take these symbols to be 0, 1, .•• , q-l
and assume that (0,0, ••• ,0)
e V.
We define Hamming-weight in the usual way.
sphere of radius 1 around a code word of weight
there are j words of weight j-1,
j
(q-2)j+1 words of weight j and (n-j)(q-l) words of weight j+l. the union of all such spheres is R(n).
If A(z) :=
stor of V we must have (5.1.4) for j
= 0,
(5.1.5)
Ina
t
i=O
Since V is perfect
A zj is the weight enumerj
(q-l)(n- j +l)A j _1 + [(q-2)j + l JAj + (j+l)A j+t • (~)(q-t)j 1, ••• , n.
If we multiply (5.1.4) by zj and sum over j we find
(q-l)nzA(z) - (q-l)z2A,(z) + (q-2)zA'(z) + A(z) +
The solution of
A'(z) = [l+(q-l)z]n.
(5.1.5) is
A(z) = n(q~l)+l {[t + (q-l)zJ
n
n-1 +
n(q-l)[t + (q-l)zl q (l-z)
n(q-l )+1
q
We remark that this must then be the solution to (2.6.7) for the case q = pO. q is not a power of a prime the substitution n nomial with integral coefficients.
qm
1
= ---1 q -
}. If
in (5. 1 .6) yields a poly-
This discourages us from trying to use (5.1.6)
to show non-existence of perfect single-error-correcting codes. We now tum to another question raised by (5. 1.3) namely whether there are non-linear
perfect~.
To make this problem meaningful we must identify equiv-
alent codes and extend equivalence as defined in Chapter 2.
If Jt is a pexmutation
90
of the symbols of the alphabet we are considering and V is a code of length n then the code obtained by applying
7t
to the 1-th symbol (1
called equivalent to V in the following discussion. to the question is positive.
:s. 1 :s n)
of the code words is
We shall show that the answer
The method due to J. L. Vasil1ev was generalized by
J. Sch8nheim (On linear and nonlinear single-error-correcting q-nary perfect codes, Inf. and Control .!,g (1968), 23-26) and B. Lindstr8m (On group and nongroup perfect codes, Math. Scand. 25 (1969), 149-158.) qm_ 1 Let q be a power of .a prime, n = - - .
Let vcR
q - 1
single-error-correcting code. m+l , N := nq+1 = q -, • q -
(R(n~q-l
be a perfect, linear,
Define
Let f: V .. GF(q) be any function with f(O) = O. -
the nonzero elements of GF(q) in any way, i.e. GF(q)'\{O) Define p:
(n)
= (a1 ,
Now order
a , ••• , aq _ ). 2 1
"'GF(q) by q-l
p(!.1' !2' ••. , !q-1) :=
I
1=1
n
(Xi
I
v ij •
j.1
Now let V* c a(N) be defined by
q-l
V*:= {(!l':Ye' ••• , !q-1' £. +
I
!..i' p(!" :Ye' ••• ,
!q-l) +
i=l
Y.:t E R(n ) for (where the notation is obvious). elements of R(N).
f(~»
i .. 1, 2, ••• , q - 1;
I
£. E V}
This is a subset of (qn) (q-l )qn-m = qN-(m+1)
To show that V* is also a perfect single-error-correcting code
it is sufficient to show that any two vectors in V* have distance
~
3. Let
q-l
!e' ..., :!q-l'
!!. := (!1'
£. +
I
!i' p(!,,···':!q-1) + f(£.»
i=l , c' ... , :!q-l'
be two different vectors in integers d"
~,
d
3
* v.
We write the distance d(~~/) as the sum of three
namely the contribution of the first n( q -1) canponents to
d(~~/), the contribution of the next n components and finally the contribution of
91
the last component.
We consider several cases:
(a)
d, ~ 3.
(b)
If d, == 0 then ~
(c)
If d, = , and.£ -I: .£' then ~ is at least 2 because c - c' E V.
Nothing to prove.
d(~,~')
(d)
If d
1
&:
d1 +
~ + c
£ = .£'
= 1 and
then
Hence d, +
For some k, 1
Sk
other 1 1n 1
S.
in V.
Therefore
3 ~ 3·
i.e. d = 1.
3
(e)
-I: £.' and hence ~ ~ 3 because .£ and .£' are both
d_
~
&:
~ +
1 and p(v ••• ,v' - 1 , ••• ,v - q,) _ .~ p(v,', -q- ,),
d = 3.
3
~ q-l, the vectors
!it
and ~ have distance 2 and for all
i ~ q-l the vectors Yoi and !~ are identical.
Then d 1 = 2.
Again using .£ - £.' E V we see t'hat d2 ~ 1 and hence d(~,~) ~ 3. (f)
For a pair i,j with 1 ~ i < j
S q-l
all other k in 1 ~ k ~ q-l we have
if .£ ~ £.'. d
3
=0
we have d(~,.!~) = 1, d(!.j,!j)
!it
=~.
Then again d,
The only difficulty arises if .£ Let v~ ~ V~, v jv ~
is possible. I
,
v1JJ, + v j '" = v~ + Vj~.
V
= £'.
Jv
•
&:
&:
1 and for
2 and again ~ ~ ,
We must now check if d
If d 2
2
&:
=
0 then ~ = v and
But then
p(y,'··.'!q_,) - p(~;' •.• '~-l) = a1(v~- v~)
+
aj(Vj~- vj~)
= (ai-aj)(v~-v~)
~ 0,
i.e. d = 1. 3 The cases (a) to (f) cover all possibilities.
Clearly .Q. E V* •
If we choose
f in such a way that it does not take all the values in its range the same number of
times then V* carmot be a linear subspace of R(N).
To be able to choose f in such a
way the code V must have at least 3 code words which is the case if q == 2 and m > 2 or q ~ 3 and m ~ 1.
Therefore we have proved
If q is a power of a prime, N:= ~m ~
2 if q
~
=2
3, then there exists a perfect single-error-
correcting code of length N a linear code.
qm+'_ 1 q _ 1 ' where m ~ 3 if q
~
GF(q) which 1s not equivalent to
92
In Section (2.2) we mentioned the connection between ternary Hamming codes and the
football-pool problem.
o.
In a more general form the problem was proposed by
Taussky and J. Todd (Ann. Soc. Polan. Math. ~ (1948), 303-305):
(5.1.8) PROBLEM:
Let G be an abelian group with n base elements g"
of order p (corresponding to R(n) in our notation).
(g~li
g2' ••• , ~
Let S be the set
= 1, ••• ,n; k = O,l, ••• ,p-l} (corresponding to our concept of a sphere
~
with radius 1). a subset H
C
Determine the minimal integer cr(n,p) such that there exists
G with a(n,p) elements such that G = HS.
When is it possible
to take for H a subgroup of GY It was shown by B. Kuttner, a prime and
Is I a
J. G. Mauldon and S. K zaremba
that if P is a power of
power of the same prime then the problem has a solution where H
is a subgroup and the decomposition of G unique.
Clearly this amounts to saying
that a perfect single-error-correcting code exists.
In the formulation of (5.1.8)
the problem is called the covering-problem for groups. covering we have a perfect code.
In the case of a perfect
The general covering problem is a hard combinator-
1al problem and only few of the values a(n,p) are known.
5.2 The sphere-;I:8cking condition Let us now turn to the harder problem of finding perfect e-error-correcting codes, with e
2, over an alphabet of q symbols.
~
by n as usual.
We shall denote the block length
If q 1s a power of a prime we write q
= pa.
Now the number of words in a sphere of radius e around any code word is
1 + (~)(q-l)
+
(~)(q_l)2
+ ••• +
(:)(q_1)e. As an analog of (5.1.1) we find the
following sphere-paCking condition:
(5.2.1) THEOREM:
A necessary condition for the existence of a perfect e-~ correcting code at block length n over an al;phabet of q symbols
e
I 1=0
(~)(q_1)i
I qn
93
(5.2.2) COROLLARY:
If q
&:
pa the condition in (5.1.1) can be stated as e \' n
L (i )(q-l) i
k
&:
q
i=O for some integer k. Proof:
e
i
0
k
By (5.1.1) we have ~ (~)(q-l) = pP q with
integer k ~ 0.
Also
qn _
i=O
n
1
t (~)(q_l)i
i=O
1
pa qk
..
&:
qn.
°< e < a
and some
-
By subtracting we find
n
I
(~)(q_l)1;: 0 (mod q-l),
i=e+l
which implies Remark:
e = 0.
(Compare with the proof of (5.1.1».
We could have used the same proof as in (5.1.1).
vantage that it shows that qn-k - 1 ==
° mod (q-l )e+1. e
This proof has the ad-
Also remark that if n > e
the left-hand side in (5.2.2) is more than ~ (~)(q_l)i = qe, i=O
(5.2.3) COROLLARY:
If q = pO the condition in
i.e. k > e.
(5.1.1) can be stated as
Proof: We start from (5.2.2) and in the sum on the left-hand side expand (q_l)i in powers of q and then rearrange.
The result follows from
e
e
e-j
i=j
i=j
k=O
I (_t)1(~)(~) = I (_l)i(~)(~=j) .. (~) I (_l)k+j(n~j) ..
Before taking a closer look at the equation
(5.1.2) we shall obtain one more re-
sult which is a straightforward consequence of the perfect sphere-packing. loss of generality we may assume that (0,0, ••• ,0) is in the perfect code.
Without Now
94
every word of weight e + 1 is not in the sphere S (0) but must be in exactly one e sphere of radius e around a code word. Since the min~ weight of the code is
2e+ 1 each word of weight e+ 1 must be in a sphere S (x) where w(x) :: 2e + 1. e-
-
other hand, such a sphere contains (2e+l) words of weight e + 1. e
On the.
It follows that
the code contains
( e~ 1) ( q - 1 ) e+
1
(2e+l) e
words of weight e (5.2.4) THEOREM:
(cf. problem 4.5.4.).
Therefore we have:
A necessary condition for the existence of a perfect e-~
correcting code of block length n over an alphabet of q symbols is that
is an integer. The necessary condition of (5.2.4) is one of a sequence which we shall now derive using a generalization of the concept of blocY design. (5.2.5) DEFINITION: A tactical configuration of type Aj t-d-n (also called a tdesign) is a collection
~
of d-subsets of an n-set S such that
every t-subset of S is contained in exactly A distinct members of~.
o<
t
To avoid trivial configurations one usually demands
< d < n.
For the special case t :: 2 the tactical configuration is called a balanced incamplete block design (cf. H. J. Ryser, Combinatorial Mathematics).
In the case A ::
the tactical configuration is called a Steiner system of type (t,d,n). different kinds of tactical configurations, a.o. important part of combinatorial analysis. established by the following theorem. generalization to q
= pO
The study of
finite projective planes, is an
The connection with perfect codes is
We restrict the theorem to binary codes.
is possible by adding the assumption of linearity.
The
95
(5.2.6) THEOREM:
~
V be a binary perfect e-error-correcting code of block length
n and assume Q E V.
We consider the collection
~
of (2e+1)-
subsets D 2! {1,2, ••• ,n) for which there is a code word
£
e V ?f
weight 2e+1 with its nonzero coordinates in the positions of D. This is a Steiner system of type (e+1, 2e+1, n). Proof:
The proof is exactly the same as the proof of (5.2.4).
Now if a Steiner-system ~ of type (t, d, n) exists with S = (1,2, ••• ,n} take any h-subset of S, e.g. H := {1,2, ••• ,h}, where 0 ~ h
S t.
n-h) This number is obviously (t-h.
of S containing H.
tained in exactly one d-subset belonging to j.
We now count the t-subsets
Each of these t-subsets is con-
Every d-subset in
~
which contains
d-h) t-subsets which also containH. Therefore the number H contains exactly ( t-h n-h) must be a multiple of (d-h) ( t-h t-h. (5.2.7) THEOREM:
Combined with (5.2.6) this proves:
If a binary perfect e-error-correcting code of block length n
exists then the numbers n -h) / (2e+l-h) ( e+l-h e+l-h'
h
= O,l, ••• ,e
are all integers. Note that substitution of h h
=e
=0
in (5.2.1) gives us (5.2.4) again.
Substitution of
yields
(5.2.8) COROLLARY:
If a binary perfect e-error-correcting code exists then
ne-;-r + 1
is an integer. Extensive computer searches have been made to find solutions of the equation of (5.2.2) with e > 1.
= 2;
q odd; 3
(1)
e
(2)
e ~ 20; q
(3)
e
~
The ranges that were covered were:
= 2;
1000; q
~
S q S 125, 3 S k S 40000
n
(E~
L. Cohen 1964),
S 210 (M. H. McAndrew 1965),
100; n < 1000
(J.
H. vanL1nt 1961).
96
No other solutions were found than trivial ones (e.g. e = n) and, corresponding to repetition codes,
(a)
q = 2, n = 2e +
(b)
q = 2, e ==
(c)
q == 2, e
= 3,
n == 23
(d)
q =
3, e
== 2,
n == 1 corresponding to the ternary Golay code treated in
2, n = 90 (excluded by (5.2.8»), corresponding to the binary Golay code treated in (4.4.10),
problem (3.5.6). (See E. L. Cohen, A note on perfect double error correcting codes on q symbols, In!. and Control
I (1964), 381 -384;
M. H. McAndrew, An algorithIn for solving a poly-
nomic congruence and its application to error-correcting codes, Math. of Comp •
.!2.
(1965),68-72; [9]). Of course computer searches cover only a finite range.
We shall show two ex-
amples of an infinite number of cases ruled out by the condition We consider the condition (5.2.9) LEMMA:
(5.2.2) for
If e is odd then
R
e
We shall prove
,
i=O where
q = 2 and e odd.
(5.2.1).
= '::T e. (n+1)Re (n)
(n) is a polynomial in n of degree e -
1
with integral
coefficients.
,
Proof:
Clearly
i:O(~) ~ n + , ~ Tr
by induction: ( n,) + ( n2 ) e+ e+
= 7"::72'" , \e+C)"
(e+2) +
e
(n-e-'») 1= TT0 (n-i),
e (e+2) (e+l)R (n) + (n--1) e i= 0
TT
which proves the lemma. We now. show one example of how this lemma can be used (cf. H. S. Shapiro and D. S. Slotnick,
On the mathematical theory of error-correcting codes, IBM. J. Res.
97
Develop.
1 (1959),
25-34).
If a binary perfect 3-error-correcting code exists then by
(5. 2 .2) and (5.2.9)
we have 2 (n+1)(n -n+6)
= 2k+ 1 •
3
or (n+1){(n+l)2 - 3(n+1) + 8} =
2k+ 1 •
3.
2 If (n+1) is divisible by 16 then the highest power of 2 which divides n - n + 6 is 2 2 3 , i.e. n - n + 6 is a divisor of 24 and then n + 1 < 16. divisible by 16 and hence (n+1) is a divisor of 24.
Therefore (n+1) is not
This leaves only the following
possible values for n: (a)
n = 0,',2
(b)
n
(c)
n = 7
(d)
n
=3
not corresponding to codes, corresponding to the trivial one-word code of length 3, corresponding to the (trivial) repetition code,
= 23
corresponding to the binary Golay code.
This proves: (5.2.10) THEOREM: The binary Golay code is the
on~
non-trivial binary perfect 3-
error-correcting code. By Lemma (5.2.9) we can do the swme type of calculation for other odd e. been done for e < 20 yielding no new binary perfect codes. case one would naturally study is e (5.2.10).
q
= 2.
This is more difficult than
=~
has been studied in several papers (cf. Math. Rev. 26,
The methods depend on unique factorization in "V-7).
= 1, 3, 5, 11 and 181 corresponding to n = 0, code), n = 5 (repetition code), n = 90 (excluded by
are x
Of course the first
In this case we have from (5.2.2):
2 The equation x + 7 *74).
= 2,
This has
1
The only solutions
(no codes), n
(5.2.8».
=2
(trivial
Therefore:
(5.2.11) THEOREM: There is no non-trivial binary perfect 2-error-correctiong code.
98
In Section (5.5) we shall prove this in a simple way. Let q = 6 and e
= 2.
We give one more example.
If a perfect code of block length n with these parameters
exists, then by (5.2.1)
i.e.
Since the factors on the left-hand side are relatively prime one must be a power of 2 and the other a power of 3.
It
.
~s
known that
I2a+1
- 3bl =
tions the pairs (2,1), (2,3), (4,3), and (8,9) which give n solutions of which only n
=2
=
has as only soluand n
= 2 as
only
corresponds to a code namely the trivial one-word
code.
5.3 The Golay codes In (4.4.10) we introduced the binary (23,12) Golay code which is a perfect 3-
error-correcting linear code.
By (5.2.6) the code words of weight 7 in the Golay
code form a Steiner system of type (4,7,23). which is a (24,12) code. itive group PSL (2,23). larger.
We now consider the extended code
By (4.4.8) this code is invariant under the doubly transThe group of autamorphisms of the code is in fact much
It is the Mathieu group M24 which is 5-fold transitive.
Because of the in-
teresting properties of this group the Golay codes (and possible other perfect codes!) have become objects of interest to group theorists.
We shall not discuss
M24 here (cf. e.g. E. F. Assmus and H. F. Mattson, Perfect codes and the Mathieu groups, Archiv der Math.
1I
(1966), pp. 121-135).
Let S be a 5-subset of the positions of the code words
i.e. (0,1, ••• ,22joo}.
C1early at most one code word of the extended Golay code has ones in the positions of S.
If
00
Golay code
E S then by (5.2.6) exactly one code word of weight 8 in the extended
has ones in the positions of S.
code word of the Golay code with weight
~
If
00
~
S then there must be exactly one
8 and ones in the positions of S and hence
exactly one word of weight 8 in the extended Golay code which has ones in the positions of S.
We have proved:
99
(5.3.1) THEOREM:
The code words of weight 8 in the extended binary Golay code fom a Steiner system of type (5,8,24). Let A2 := 77, A := 21, A4 := 5. Then for 1 = 2,3,4 and for 3 every i-subset S of (0,1, ••• ,22;oo} there are Ai code words of
(5.3.2) COROLLARY:
weight 8 in the extended binary Golay code such that these code words have ones in the positions of S. ~:
Just as in (5.2.7) we have
Ai
=(
24-1 ) /
( 8-i') •
5-i
5-i
'In connection with (5.3.1) we remark that there are no known t-designs with t
> 5.
For the binary extended Golay code the following generalization of the idea of threshold decoding as treated 1n Section 2.4 was suggested by J. MGoethals (cf. On the Golay perfect binary code, Report R93, MBLE, Brussels). d~ends
The decoding method
on (5.3.2) and the following theorem:
(5.3.3) THEOREM:
The extended binary Golay code is self dual.
••• , c 22 , coo) and (dO,d1, ••• , ~2' doo ) be two code words. 22 i 22 j Just as in the proof of (4.4.4) the product (t CiX)( E djX- ) is 0 or
~:
Let (co'c"
j=O
,the latter iff EC = Dd =: 1 which 1s the case if i i 22 It folloW's that E c i di + coodoo = O. 1=0
1 + x + ••• + x
Coo = doo = 1.
j=O
22
The decoding method now works as follows.
The extended binary Golay code has 253
code words of weight 8 with a 1 in a specified position (cf. (5. 2 these 253 code words can be used as parity-checks.
.4».
By (5.3.3)
If the result of substitution of
a received word in a parity-check equation is 1 we shall call this a parity-check failure.
From (5.3.2) we then find the following table:
100
Number of parity-check failures for the 253 p.c. equations
*of errors outside the fixed position
0
1
2
3
4
0
17
112
125
128
253
176
141
128
125
~
fixed position correct
"
fI
in error
From the table we see that if the number of errors is fixed position is correct or not.
3 we can decide if the
Then using the fact that the Golay code is cyclic
the errors can be corrected successively. known after the first step.
~
In this procedure the number of errors is
The numbers in the table show that 4 errors are detect-
ed but not corrected (we already knew this).
Another threshold-type decoding pro-
cedure was suggested by E. F. Assmus and H. F. Mattson (Report AFCRL-68-0478 of the Applied Research Laboratory of Sylvania Electronic Systems).
It also depends on
(5.3.2) and (5.3.3). It was shown by V. Pless (On the uniqueness of the Golay codes, J. Comb. Theory ~
(1968), 2 15-228) that the Golay codes are unique. Therefore every construction
leading to a perfect binary (23,12) code gives us a code equivalent to the binary Golay code as introduced in (4.4.10).
The following very simple construction is due
to E. F. Assmus and H. F. Mattson. In the description below we use
the
Hamming-weight of!.
l
to designate the all-one vector and
I!I
for
The product ~! of two vectors is defined as in (2.3.1).
Let H be the extended (8,4) Hamming code. tion) we see that H consists of
Q,
Using 3.1 and 3.3 (or simply by inspec-
the seven cyclic shifts of (1,1,0,1,0,0,0) each
followed by a parity-check 1 and the complements of these vectors, i.e. seven shifts of (0,0,1,0,1,1,1) each with a O-parity-check.
l
and the
Numbering the positions
of H from 1 to 8 and applying the permutation (1,7)(2,6)(3,5) we obtain the equivalent code H'.
We remark that H
n H'
=
(Q.,.!J,
that all other vectors of H and H'
have weight 4 and that all vectors of H + HI have even weight. V := (a x, b +x,a + + x) -+-b _
I a....
Now:
E H, -b E H, x - E H'}
101
is clearly a (24, 12) linear code.
To show that V is the extended Golay code we
only have to show that V bas minimum distance 8. at least one of the vectors"!J the other vectors
~
E.,
t~es
= Since I~I
=4
!+~ 2f. is either
= (!+~,
E.+~'. !+~!.) ~
Q. or 1 then
+!I + 21~!1 =
To check
we find
Ixl
+ 21!. +
we must show that
=~
~ 8.
I~I + 1:~~:1.
!?
+ !: ~ +
I! + ~ + ~ £ +
?Eo1· ~I ~ 2.
Since H is self-dual a b
has even weight and it is therefore sufficient to show that ~ + ~ + ~ + ~~
I!I
Q and
we use the equality:
I~ Applying this three
If!
implies (!.+.!)(~+JJ
= ?f. + 1.. where
weight 4 which is only possible if ~
=!?.
~ +
1,
~ +
:£ +
.!. and !
~
:£ .,
+
x.
Now
1.. all
have
Since ~ ~ !. this 1s impossible.
If we
finally shorten V we obtain the Golay code. Yet another representation was given by M. Karlin.
The quadratic residues
mod 11 fom an (11,5,2) difference set namely IJ := {--1,3,4,5,9}. and proof cf. H. J. Ryser, Canbinatorial Mathematics).
(For definitions
Now let C be the circulant
with first row (11011100010), i.e. ones in position 0,1,3,4,5,9.
31 + 3J where I is the unit matrix and J the all-one matrix. code generated by the rows of C.
Then CCT
= CTC =
Consider the cyclic
11 4 Since (1 + x + x 3+ x + x5+ x 9, x _ 1) = x - 1
this code is the 10-dimensional code consisting of all even-weight words, i.e. C has rank 10.
Using all these properties it is not hard to check that the matrix
generates a (23, 12) code with minimum weight 7 (remark that each row of G has weight
7 or 12). We omit the rather tedious details.
Apparently G is the generator matrix
in reduced echelon form of the binary Golay code.
102
The fact that the Golay code is perfect is enough to find the weight enumerator of this code.
By combining several theorems which we have proved the weight enumer23 1 ator can be found much faster. Let t a z be the weight enumerator. We know from 1 i=O (5.2.4) that ~
= 253.
From (4.4.8) and (4.1.10) we find a
ber of words of weight 7 which are at a distance
8
= 506.
The total num-
3 from the code words of weight 7
~
and 8 is:
= a,O = o. Since the Golay code a 23 = " a,6 = 2S3, a 15 = 506, a'4 = a'3 = O. 12 Since Ea = 2 we find all = a 12 = 1288. The i
Therefore the code has a tor we have
all
= a 12 •
contains the all-one vec-
9
From (4.1.10) we have
weight enumerator of the
extended binary Golay code is (1 + z
24
) + 759(z
8
+ z
16
) + 2576z
12
•
The ternary Golay code was first introduced in problem (3.5.6). seen that this perfect 2-error-correcting code is a QR code.
Since then we have
The methods of Section
4.4 allow us to prove that the code is perfect somewhat faster than was done in (3.5.6).
Let go(x) := x
(generator go(x»
5
+ x
432 - x + x - 1.
T
If C denotes the ternary Golay code
and C the subcode with generator (x-l)gO(x) then we know from
(4.4.4) that every code word in C+ \C has weight
~
4.
In the same way as (5.3.3)
was proved we find that any two words in C have inner product O. (x-1)gO(x) = x
6 + x 4 - x 3 - x 2 - x + 1 has weight 6 and the same of course holds for
the cyclic shifts of the generator.
III ::
0 (mod 3).
~
I!I ::
be the number of positions where ! and l both have
nonzero entries but different ones.
= (!,l) = a -
Let ~ and 1.. be two vectors of C with
Let a denote the number of positions where ! and l have the same
nonzero coordinates and let
o
Now the generator
$ and finally I~ +
Then
rl = a
I!I = a
+ ~ +
V"
+ V1 + V2 == I~I +
III = a III
+
S+
Y2 and
e 0 (mod 3).
this it follows that all code words in C have a weight == 0 (mod 3).
From
Furthezmore no
vector in C has weight 3 because if there were such a code word a cyclic shift would a have the form (l+x +xb ) with 0 < a < b
S
b a a b 10 and then (1+x +x )(l.+x- +x- )
=0
would
103
imply a
= -b =b
weight 6.
- a (mod 11) which is impossible.
Now in order to show that C is perfect we only have to show that a vec-
tor in C+\ C cannot have weight 4. be a
It follows that C has minimum
+
If there were such a code word there would also
code word of the form vex) = 1 + x
a
b + x % xc.
2 10 Then (1+x+x + ••• +x ) ± vex)
would be a word of weight 11 or 8 in C which we have shown to be impossible. The ternary Golay code is small enough to make decoding procedures of a canplicated nature superfluous.
A simple table of syndromes is just as fast.
For the ternary Golay code we can easily find a generating matrix in reduced echelon form of the same type as we had for the binary Golay code. circulant with first row (0,1,-1,-1,1).
G :=
Let C be the
Then define
fr. 11111) (6 c=J
H :=
T Then G has rank 6, H has rank 5 and GH =
C
-I
o.
From
5
gOOO)
( oo
-J
°
it follows that, with a := (a"
8
5
2 , ••• , a6):
6
a OOTaT = -(
2
I
ai)
I
1,
i=2 i.e. all code words ~ G in the code with generator G (and parity check matrix H) have a weight 'f:. 1 (mod 3).
The rows of G have weight 5 or 6.
of 3 or more rows of G has weight> 3, and hence
~
5.
A linear combination
So all we have to do is to
check the linear combinations of two rows of G by hand to see that G generates a ternary (11,6) code with minimum distance 5.
This code must then be equivalent to
104
the ternary Golay code. The weight enumerator for this code was found in
(3.5.6).
5.4 Lloyd t s Theorem
In 1957
s.
P. Lloyd ([12]) proved a theorem which gave a necessary condition
for the existence of a binary perfect e-error-correcting code. later generalized by F. J. MacWilliams and recast braic form.
This theorem was
by A. M. Gleason into an alge-
The theorem did not receive the attention it deserves because it was
hard to apply.
In the next section we shall see how Lloyd's theorem was used recent-
ly to show the non-existence of a large class of perfect codes.
We shall present
Gleason's proof of Lloyd's theorem in this section.
(5.4.l) NOTATION:
(i)
R:= R(n) will denote, as usual, the n-dimensional vector space over GF(q).
(ii)
tiwill bea vector space of dimension qn over~ with the elements of R as basis vectors.
We shall denote addition
in It by $.
The elements of tl are linear combinations
a 1!1
$
(!)
a 2Y2
sums bY!
•••
(a
i
E CQ,
~
E R).
We shall denote such
aiy"!' to distinquish from the addition in the
YaiER group (R,+). (iii)
We use capital letters for elements of U.
In U we define a binary operation, denoted- by the symbol
*,
by
which is just the formal product of the left-hand sides if
We then have:
(5.4.2) THEOREM:
(U,~,
*)
is a ring.
105
Proof:
We leave this to the reader as an exercise.
The ring U (which is also vector space over~) is called the group ~ of Rover To simplify the notation we use the following convention: V to denote the element
~
v in tl.
~-
(Q.
If VcR, then we also use
As before, we use w( v) to denote the weight of
vel
-
v E R, and we use Be to denote the sphere of radius e with center
2.,
i.e.
and by the previous convention we also have
In the rest of the section we shall assume that a perfect e-error-correcting code C ca(n) eXists, where e < n, and without loss of generality we assume that
o E C.
By the definition of a perfect code and (5.4.1) (iii) we have
(5.4.4)
NOTATION: The element
(1,1, .•• ,1,0,0, •.• ,0) E R for
which the first
k
cam-
ponents are 1 and the remaining components are 0 will be denoted by
~.
Obviously we have
Here the element !1
* cEil corresponds to the set
which is a perfect code obtained by translating C.
Since C contains a word of i
weight i but no word of smaller weight (i = 0,1, ••• ,e) we see that the elements C E U are linearly independent over
(5.4.6)
DEFINITION:
For i
= 0,
1, ••• , n we define:
106
(i)
~
Y1:=
Y.
!tR,w(!)=i (ii)
The symmetric subr1ng
'ii
c 91 is defined by
n
ii : = {~ i=O Note that
ii
0:1 Y1
I 0:1
E (Q, 1
= 0, 1, • • • , n}
1s an (n+ 1 )-dimensional vector space over
· Ii
To show that
is indeed a
subring of U we- consider the group G of all linear mappings of R into R with a matrix DP where D is a diagonal matrix with nonzero elements frem GF{q) and P is a permutation matrix. m := (q_l)n·n!.
(We call G the monomial group).
The order of G is
Notice that
Y EG V t::o [w( ~(v)) cp!.f;If, -
==
w( v)] • -
If we extend each cp E G to the vector space U by defining
then
~ ayql(:::) * ~ bwql(~)
!.ER -
~ER
i.e. each ~ EGis a homomorphism of the ring (11,
{A
e UI I
cp(A) = A) is a subring it follows that
subring of 11.
@,
n
ttcp
:=
tl, which is cP
ii,
*).
Since
is also a
107
Ii by
We now define an averaging-operator T which maps U into
n
Observe that T maps the element A :=
2av! into t (XiYi where (Xi is the average of
vE:R the coefficients a as the identity on
v
i=O
belonging to elements v with w(v) = i. --
It follows that T acts
ti.
We shall need the following lemma:
T(A*B) =
Proof:
i:
~
cp(A*B)
cp€G
=;
~
cp(A) * cp(B)
=
rp€G
=
i:
~A*
cp(B)
=A *
T(B).
cp€G
Since
we have by
(5.4.5)
and
(5.4.1) R
= T(R)
= T(S e* c)
and the same holds with G instead of C (i i
The elements
C.J.
= S e * T(C)
= 1,2, ••• ,e).
Let
are linearly independent elements of the vector space
Ii
over ~ for
the same reason that the C are linearly independent. i
We now define a linear transfo:rmation g
e
of the vector space
ii by
(5.4.10) From (5.4.8) it follows that the e linearly independent elements 6"1 ••• , e) of
U
satisfy
Co (1 = 1,2,
108
Therefore we have proved: (5.4.11) LEMMA:
The linear transfonnation 3
e
of
ii
has a kernel of dimension> e.
The second part of the proof of IJ.oyd t s theorem uses characters of a group. Although we assume the reader to be familiar with the elements of the theory of group characters we give the definition and a theorem we shall need. (5.4.12)
DEFINITION: A character X of R the group
(5.4.13)
(a:
X
, ),
is a homomorphism of the group (R,+) into
i.e. the multiplicative group of ~.
THEOREM: The characters of a finite abelian group ~
(5.4.14) DEFINITION:
R (with multiplication as If
a group isomorphic
~ration).
X is a non-trivial character on (GF(q),+) and! E R we de-
fine
Now suppose that Xv
R form
= x""
X
Xv : R .. C by
i.e. Y~ER[X((~y)
= X( (~!.»].
Then V~ER[X( (~,y-~) = ']
and since X is non-tri~al on GF(q) we must have V~ER[(~'Y.-:~!) = 0], i.e. y. = !!.. Apparently we can define qn different characters on Q using the fixed character X and (5.4.14).
We now extend each
Xv
to a ~ functional on
use the same symbol) by defining:
We shall need
qon {
if if
v~w.
tt (for which
we shall
109
Proof:
(i) X (A*B) v -
(11)
I
== X
v
(\' (
-
L
b )Z) L a uw -
\
==
E.E:ft ~+:!=! - -
\'
(
L
a b \. (z) = uwJXv-
)
l.-J
~+'!=! - -
!~
-
Xy(~)Xw(~)= Ix(~y»)x(u,w»)=
£~
-
-
~(fR
n
q
= \' L
~$
Xu (v-w) --
==
-
qn-l
if ! = !. ,
I
x(~) = 0
if
Y ~ !.
~EGF(q)
From (5.4.16) (ii) it follows that the qn linear functionals X of U (where v runs v through R) are linearly independent over~. Since there are qn of them they span the space of all linear functions of U (cf. e.g. W. H Greub, Linear Consider a mapping
I ~€R,w(~)=k
Algeb~,
§2.33).
Then we have
x(!J!») = xv(Yk),
i.e. the action of the linear functional Xv on U is the same for all! with the same weight.
So if we restrict the linear functionals Xv to
tionals X~ : ...
ti ~~x where Xi
:= X
!i
(cf.
Uwe
find n + 1 linear func-
(5.4.4»). Each linear functional on U
can be extended to a linear functional on U.
Therefore the Xi (i
==
O,', ••• ,n) must
span the space of all linear functionals on ij , i.e. they are linearly independent. We can actually explicitly
dete~ine
the characters Xi :
110
(5.4.17) LEMMA:
For k
= 0,
1, ••• , nand w = 0, 1, ••• , n we have k
\ ( 1 n-w w· k-1 Xw ( Y ) • L -1) (k-i )(1 )(q-1) •
k
i=O
I
Proof: (a) Fran X(O) ... 1 and
X(a) ... 0 it follows by induction that
atGF(q)
I* (a, ,a2 , •• • ,ai )
where the
*
x(a1 + a + ••• + ai) ... (_1)i, 2
indicates that the sum 1s taken over all i-tuples
of nonzero elements of GF(q).
I
(b) Xy(Yk)...
x( (!w'~») . .
~ER,w(~)=k
and the result follows from (a).
e = \ (_1)i(w-1)(n-w)( _l)e-i • ( 5.4.18) COROLLARY: Xw(S) e L i e-i q
i=O
~:
From (5.4.17) we find e
Xy(Se)'"
k
I I
(-1
)i(~)(~:~)(q_l)k-i ...
k=O i=O
e
e
. . I (-1) (~) I (~=~)( -1 )k q
i
=
i=O
k=i
e
e-l
1=0
t=O
-i ...
I (-1 )i(~) I (n,iw)(q_l).(..
w-l) If we write (w i) = (i -1 + (w-l) i and rearrange the sum. we obtain the required
result.
111
This canpletes the second part of the preliminaries and we can now fonnulate and prove Lloyd r s theorem •
(5.4.19) THIDREM:
If a ;peI!fect e-error-correctin~ code of block length n ~
GF(q) exists then the polynomial e
Pe (x) :=
I (_1}i(:=~)(X~
1
)( q-l )e-i ,
1=0 where (~) := a(a-1) ••• (a-i+1) / iI, has e distinct integral zeros among 1, 2, ••• , n-1. Proof:
Consider the linear transformation 3
let K be the kernel of gee definition S e
*A=
e
of U defined in (5.4.10) and
In (5.4.11) it was shown that dim (K) ~ e.
By
0 if A E K and then it follows fram (5.4.16)(i) that for
w = 0, 1, ••• , n and all A E K
Suppose r of the characters vanish identically on K. for the remaining n + 1 - r characters. early independent we must have dim (K) that P (w) e
= 'V(S). e '~
Apparently Xw(Se) = 0
Since the characters
Sn
+ 1 - r.
In
Xvi
were lin-
(5.4.18) we found
For at least e values of w we must have P (w) = 0 e
and since P (x) is a polynomial of degree e we see that all the zeros of e
Pe (x) are integers in [O,n]. By substitution we find e
Pe(o) =
I
(e~i)(q-l)e-i ~ 0,
1=0
P (n) e
= (-1) e(n-l) e
1 F
0 if n > e.
This proves the theorem. The following theorem gives us some idea of the interpretation of the zeros of P e (x). (5.4.20) THEOREM: If !. ~
2.
is a vector in the dual of a linear perfect e-~
correcting code then w(v) is a -
zero of the polynomial P (x). e
112
~:
If! is in the dual of the perfect e-error-correcting code C and
! ~ Q. then by (5.4.14) and (5.4.15) Xv(c) =
-
Lx( (£,!») = L
X(O) • qk
E.EC
~EC
if k is the dimension of C.
By (5.4.16) (i) and (5.4.3) we have
Xy(Se>xy(C)
-
-
=
Xy(R(n»
-
=
O.
Hence
For future use we put P (x) in an other fonn. e
To do this we apply the same reduc-
tlon that occurred in (5.2.3). First we remark e-j \ (n-~-~)(X~1) = L e-2-J 2 i=O
(n- j :'). e-J
This simply follows from multiplying the Taylor series of (l+z)n-x- j and (l+z)x-l and consider~ the coefficient of ze-j.
Then we have e-i
e
p (x) == \' (_l)i(n- x )(x:') \' (e:i)qj(_l)e-i- j = e L e-i 2 L J i=O j=O
e
(_1}e
L
(-1 )jqj
j=O
(_l)e
(5.4.21)
I
(~=~){e;i )(x·~ 1 ) =
1=0
e
e-j
j=O
i=O
L(-l)jqj(n;x) L(~=~=~){X~l),
p (x) e
e-j
= (_1)e
i.e.
e
\' (_1 )jqj(n:x)(n- j -l). L J e- j
j=O
5.5 Nonexistence theorems We shall now combine (5.4.19) {or (5.4.21» the nonexistence of certain perfect codes.
and (5.2.2) (or
(5. 2.3»
to show
We shall consider codes with one word
and repetition codes (2 words) as trivial perfect codes.
113
In the following we assume the existence of a perfect e-error-correcting code
(1 < e < n) over GF(q), where q == pa, and we shall try to arrive at a contradiction. By (5.4.19) there are e distinct integers 1 < xl < x2 < •.• < x < n which are the e zeros of the polynomial Pe (x). By substitution in (5.4.19) we find
= (n-l)(q_1)e e
P (1) e
~ 0
since
e < n-l
and P (2) e q = 1 +
2e + 1
e
n-e-1
which
(n-2 )(q_l)e-l{q(n_e_l) - (n-l)J = 0 only if e- 1
~plies
S n we must have
tition code.
==!e
e ==
e
n-l
~ ~.
n-l
q
~,
Since the mintmum distance of the code is
= 2 and
then we have the parameters of a repe-
Therefore we may assume that x, > 2.
The following lemma will be the basis of our theorems: (5.5. 1) LEMMA:
The zeros of Pe(x) satisfy the relations: e(e+l) (i ) x , + x2 + ••• + x e = e(n-e)(q-l) + q 2' (ii) (where k is the exponent in the right-hand side of (5.2.2».
Proof: We saw in the proof of (5.4.19) that e
Pe CO) = )~ {~)(q_1)i = qk ~
by (5.2.2).
i=O
From (5.4.21) we se~ that the coefficient of xe in Pe (x) is (_l)eqe/e! • e 1 Also from (5.4.21) we find the coefficient of x - in Pe (x) to be e-l e \' (_l)eqe-l {n-e} __ (_l)e+,'qe {e(2n'!"e+l) _ e(n-e)} • _(_l)e ;: L (n-i) + (e-l)! e., 2 q i=O Front these coefficients we find the sum and the product
P (x). e
of the zeros of
114
(5.5.2) COROLLARY:
If a perfect e-error-correcting code of block length n over GF(q) exists then e(n-e) e 0 (mod q).
Let us now consider perfect 2-error-correcting codes.
From (5.4.21) and (5.2.2)
we find
2P (x)
2
If q
= 2 we
= (qx)2
- (2n-l)q - (2n-4)}(qx) + 2qk.
know from Section 5.2 that (2n+l)2
+ 7 = 2k+3 = 8P2(O).
In this case
Lloyd. I s theorem says that the equation 2
y
has two distinct roots
_ 2(n+1)y + 2k+
:s. a
< b.
= 0
y, and Y2 which are even integers.
assume that Yl and Y2 are both> 4. where 3
1
Then 2(n+') = 2
80
Since Y'Y2
=
We saw above tha.t we may
_k+l a b Zwe must have Y1 == 2 , Y2 == 2
b + 2 and the equation (2n+1)2 + 7 == 2k+ 3 becomes
=7
and since a and b are both ~ 3 this implies 1 This then proves Theorem (5.2.1').
(mod 16) which is a contradiction.
Subsequently we look at e == 2, q> 2.
The equa-
tion (5.2.2) is a quadratic equation in n which we can solve, expressing n in q a.nd k.
For the roots of the equation P2(x) = 0 we then find from (5.5.1) k-2
x,x2 = 2q
,
k 2 1/2 q(x,+x2 ) == 1 + (8q +q -6q+l) •
Since we· may assume that Xl and x the other 2Jf where)" ~ 1,
2
are > 2 we see that one of the roots is
~ 1, A + ~
).II
==
a(k-2).
p""
and
Substitution in (5.5-3) and elim-
ination of the square root yields k-1
(5.5.4) Since
A and
8q
n-U! 2
A ~
- 2(1' +~ ).
~ are positive all the terms on the two sides of
by p, i.e. p == 2 or p ==
by
A
+ q - 6 == q(p +~)
3-
If l'
=2
(5.5.4)
then the right-hand side of
4 whereas this holds for the left-hand side only if q
==
2.
are divisible
(5.5.4)
is divisible
The case e == 2, q
=2
115
was settled above.
It remains to consider p
= 3.
First assume q
= 3.
Then
(5.5.4)
reduces to
which
~plies ~
other hand, q
= 1,
=3
Q
X = 2, i.e. k =
with a > 1 then
From this we find A = 1,
~
5 and hence n
= 11
(from
(5.2.2». If, on the
(5.5.4) implies
> 1 and then (5.5.4) reduces to
which is impossible because the left-hand side is clearly divisible by a higher power of 3 than the right-hand side.
Now all possibilities have been discussed and
we have:
(5.5.5) THEOREM: The only non-trivial perfect 2-error-correcting code over any alphabet GF(q) is the ternary Golay: code. In order to be able to use Lloyd I s theorem for e
~
3, where explicitly solving
P (x) = 0 is either impossible or too much work, we take a closer look at the polye a a(a-1)···(a-i+l) nomial Pe(x). Notice that if a is any positive integer then (i) = 1 1 ~
0 because a negative factor can occur in the numerator only if same other factor
is O.
Since we are interested in the value of Pe (x) for
(5.4.19) is an alternating sum (if 1 ~ x
~
n-1).
The
integ~l
te~s
x the sum in
in this sum decrease in
absolute value if x < (n-e+l)(q-l)+e (q-l)+e • Therefore Pe (x ) cannot be 0 for such integral values of x.
This proves
If P (x) has e integral zeros in [1,n-l] then e
x > (n-e+l~(q-l)+e 1 (q-l + e ~:
from
In the same way that
(5.5.6) was proved we can find a lower bound for Xl
(5.4.4) but this bound is not as good as (5.5.6).
116
From
(5.4.21) we can easily find an estimate for q. As we remarked in the (5.4.19) we have
proof of
Pe (n) = (-1)
e
n-1
( e )
-1
~
0
Fran (5.4.21) we find
P
e
and by
(n-1)
= (_1)2
{(n-l) _ q(n-2)}. e e-l
(_l)e
(n-l){l qe) e - n-1.
(5.4.19) this must have the same sign as Pe (n), i.e.
(5.5.1) THEOREM:
If a perfect e-error-correcting code of block length n .~ GF(q) ~(e
q
S.
(n-1)/e.
We are now in a position to prove a first nonexistence theorem.
(5.5.8)
THEOREM::
If e ~
3,
= pex ~ p >
q
e then there is no non-trivial
~rfect
e-error-correcting code over GF(q).
A typical term in (5.2.3) has the fom
(i)
~:
( 5.5·9 )
tj
. .=
(
-1
)j j n(n-l)···(n-j+l} (n-j-l)(n-j-2)···(n-e) q j; (e-j)l.
> e we find from (5.5.2) that
Since p
q
I
(n-e).
In the fractions in
(5.5.9) the only tem in the numerator which is divisible by p is n - e. No tem in the denominator is divisible by p.
CXj+all· t j for J
p
e 1: t
j=O
j
exeltt e . = 0, 1, ••• , e-1 and p
is divisible by p~ where k > e.
Let pall (n-e). By
( ) 5.2.3
the expression
This is only possible if the two
tems t j containing the lowest powers of p are divisible by the of p. (ii)
Then
~
power
ae :: a. Therefore we have proved that qel (n-e).
Hence
From (i) it follows that the first tenn on the right-hand side of
( 5.5.1 ) ( i ) p :: e+l.
.
16
divisible by q
e -1
•
The term
e (e+ 1) 2 is divisible by p only if
This fmplies that at least one zero of P (x) is not divisible by p e
unless p :: e+l in which case we know that at least one zero of P (x) is not e
117
2
It then follows from (5.5.1) (ii) that at least one of the
divisible by p.
zeros of P (x) is a divisor of (e+l)! e
(iii)
Hence xl < (e+l)! -
Then Lemma (5.5.6)
Since q> e and qel{n_e) we have (n-e) ~ (e+l)e.
yields x, > 1 +
~ (e+l)e. Combined with (ii) we find
which is false for e
~
1 +
~ (e+l)e ~ (e+l)!
3. This proves the theorem.
The argument in the proof of (5.5.8) goes through for e = 2.
~:
we do not arrive at a contradiction. but we find that xl = 6, q sibility.
=3
In that case
is the only pos-
This again leads to the ternary Golay code.
We now refine the argument used in the proof of (5.5.8) to prove:
(5.5.10)
THEOREM: If e ~
3,
q =
po > e and p < e, p
l
e then there is no non-trivial
perfect e-error-correcting code over GF(q). Proof:
(i) As in (5.5.8) we find gl(n-e) fram (5.5.2).
From (5.5.9) we
find (o ~ j
Now, since p } e and p
I
(n-e) we have p
1-
S e-l).
n which implies that at most one
of the factors in the denominator is divisible by p. exception of j
= e-l,
Furthennore, with the
the highest power of p which divides the denominator
is less than q because gl(n-e) and q > e.
Therefore the terms in (5.5.9)
containing the lowest powers of p are to and tea
Again, let pallen-e).
Since gl(n-e) and g > e the corresponding terms in the numerator and the denominator of (n-1 )(n-2) (e-1) (e-2)
are divisible by the same power of p.
(n-e+l)
Hence pall (n;' )
we show that paell te - So again we find a
= C¥e,
= to.
In the same way
i.e. gel{n_e)_
Part (ii) and (iii) of the proof of (5.5.8) can now be copied to complete the proof of (5.5. 10).
118
For
pr~es
p which divide e the result which we can obtain is weaker:
(5.5.11) THEOREM: ~ pie,
= pel and
q
let q> e if p> 2 ~ q > 2e if p
&:
2.
Define
!! p >
2e! + e - 1
2,
( (e-l)J) e + e - 1 if P ... 2, 1
~
(a)l denotes the largest odd factor of a.
;perfect
e-error-correcti~ code
of block
len~h
If a non-trivial n
~
GF(q)
exists, then n < M (e). --
(i)
~:
p
Suppose all the zeros of Pe (x) are divisible by a higher power
of p than is contained in
21 e(e+1). Then in (5.5. 1) (i) the two terms on
the right-hand side are divisible by the same power of p and therefore Q
p 1t2 (n-e).
Then, just as in the proof of (5.5.10), we see
Assume p > 2.
that numerator and denominator of (n-e+1)
(n-1) (n-2) (e-1) (e-2)
are divisible by the same power of p and hence q
1-
(n-1) contradicting e (5.2.3). If p = 2 the same reasoning holds because th~n pa- 111(n_e) and we a-l 1 required that p &: 2 q > e. (ii) Since we found a contradiction in (i) the assumption was false.
Hence
there is a zero of Pe (x) which is not divisible by a higher power of p than 1
2 e(e+l). (e-l):)
If p > 2 this implies Xl
, • (~e).
~
e! and if p
&:
2 it implies Xl <
The theorem then follows fram (5.5.6).
The theorems and methods of (5.5.8) to (5.5. 11) are sufficient to solve the problem of the existence of perfect e-error-correcting codes, given e. been done for e
~
This has
7 yielding no new perfect codes (cf. [9], [10], [11]). We shall
demonstrate the method for e
&:
length n over GF(q) exists (q
3.
= pal
If a perfect 3-error- correcting code of block then by (5.5.8) p ~ 3-
By (5.5.10) p
=2
119
~plies
q
implies q
=2 =3
which case was completely treated in or q > 3 and n < 14.
this is a contradiction.
(5. 2 • 10). If p
=
3 then (5.5. 11 )
In the latter case (5.5.7) implies q < 5 and
Apparently only q = 3 has to be ·considered.
Xl + x 2 + x 3
x 1x2x xl ~
If q
=3
we
= 2n,
k-2
= 2·3 3 2n - 1
,
--5-·
This is impossible because the second equation shows that the three zeros have the abc form 2·3 , 3 , 3. Since these zeros are distinct the sum of the zeros is ~ 7x, > 2n contradicting the first equation.
(5.5. 12) THEOREM:
We have proved:
The only non-trivial ;perfect 3-error-correcting code over any alphabet GF(q) is the binary Golay code.
It seems that only very little more than the material presented in this section should be enough to completely settle the question of the existence of non-trivial perfect codes. Since the appearance of the first printing of these lecture notes the question has indeed been settled by A. Tietavainen (cf.
D91 )
and independently by W.A.
Zinoviev and W.K. Leontiev (cf. [2Q) ). The proofs depend on a refinement of the arithmetic-geometric mean inequality which is applied to (i) and (ii) of (5.5.1}. It has also been shown by H. W. Lenstra jr. (cf. [21] ) tha t Theorem (5.4. 19) is also true if q, the number of symbols in the alphabet, is not a power of a prima The question of the existence of perfect codes in this case remains open. A survey perfect codes and connected material can be found in~~ •
VI. WEIGHT ENUMERATION
6. 1 The MacWilliams equations There is a remarkable relation between the weight enumerator of a linear code and the weight enumerator of the dual code. F. J. MacWilliams.
The relation was first discovered by
The proof we give here is based on an idea due to A. M. Gleason.
We shall first prove a lemma which resembles the M8bius inversion formula.
(6.1.1) LEMMA: Let X be a non-trivial character on (GF(q),+) and let Xv : R ~C+ be defined as in
(5.4.14). If A is a vector space
over~, f:
R~ A
and if g: R ... A is defined by
V~eR [g(~)
:=
Lf(!>Xv(~)J -
y.~
then for any linear subspace vcR and the dual space VJ. we have
Proof:
L g(~) L L f(!>Xv(~) L f(!) L x( (~,.!)) =
uEV
~el !€R
-
!~
=
uEV
In the inner sum of the second term (~,!) takes on every value same number of times and since
L
e GF(q)
the
X(cx) = 0 for every non-trivial char-
aEGF( q)
acter this proves the theorem. We apply this theorem with A := space of polynomials in two variables ~ and 11 with n coefficients in C, f(!) := ~w(y') l1 - w(!). Then we find (using w(a) := 1 if a F 0,
w(O) = 0):
121
w(V, )+ •••+w(Vn ) (l-w(v,) +... + (l-w(vn »
\
L S vnEGF(q)
Since the inner sum is U
i
~
+
~
(q-l)~
if u i = 0 and
~
+
~
[
I
x(u,v,+••• +unvn) =
x(a)] = ~ - ~
if
a€GF(q)
al:o
~ 0 we find
g(~) = ( ~
(q-l)~)
+
n-w(u) -
( ) (~ _ ~)w ~ •
Now let Y be a linear (n,k) code over GF(q) and yJ. the dual code.
n.
Let
n.
A(z) :: ~ A.z~ and B(z) :: ~ B.Z~ be the weight enumerators of Y and yJ.. i=O
i=O
~
Apply (6.1.1) witl?- f(!)
~
= ~w(,!) l1 n -w(y)
where
~ = z, 11
= 1.
We find
This is the MacWilliams identity i.e.
(6.1.2) THEOREM:
If A(z) is the weight enumerator of the linear (n,k) code over
GF(q) ~ B(z) is the weight enumerator of the dual code then
Example:
By (2.3.14) the weight enumerator of the first order RM code of length
is
A(z)
=1 +
(zm+
Hence B(z)
zn-l + zn
1 - 2)z
== 2 -m-l (1 +
Z
zn.
•
Z)
m z) 2 A('~
m is the weight enumerator of the extended Hamming code of length 2 {by (2.3.7) and
(2.3.8».
{See problem
(2.6.6».
122
The foxmula (6.1.2) can be very useful in weight enumeration problems.
We shall
illustrate this for q = 2 to simplify the calculations but everything goes through analogously for q
> 2. Suppose that the coefficients
n
A. of the weight enumerator J.
~ A zj of an (n,k) code are known except for s values of the index j. If BO' B1, j
j=O
••• , B _1 are known, which for instance is the case if the dual code has minimum s weight s (BO
= 1,
as follows.
From (6.1.2) we have
B,
= B2 = ••• :: n
Bs -1 = 0), then we can determine the unknown Aj
j
L:
AjZ =
j=O
2k-
n
n
l: j=O
Differentiate both sides t times, where 0
Bj (l-z)j(l+Z)n-
~t
<
5,
j
tS
•
divide by t! and substitute z = 1.
We find:
(t
which is a system of s linear equations in the unknowns A
j
coefficient matrix of this system is
(t
1
= 0,1, ••• ,8-1)
, A , j
2
••• , A j
•
s
The
= 0,1, ••• ,8-1; k :: 1,2, ••• ,s).
Since [a ] can be transformed into the Vandennonde matrix by elementary row opertk ations the equations are independent.
\.
6.2 Weight enumeration of RM codes. In the past few years much work has been done on the weights in RM codes.
In
this section we shall discuss same of the results briefly. First we consider a theorem due to G. Solomon and R. J. McEliece.
(6.2.1) THEOREM:
~ h(x) be the check polynomial of a binary cyclic code of length
n (odd).
If h(x) does not have a pair of zeros with product
then the weight of every code word is divisible by
4.
123
~:
Let g(x) be the generator of the code.
x - 1 divides g(x) and not hex). d
t
If c(x) =
x
e
1
Slnce 1.1 = 1 the factor
Therefore every code word has even weight.
1s a code word of weight d then the condition on hex) im-
1=1
plies that c(x)c(x -1)
lI:
0 (in the ring R,).
Now by the same argument that
was used to prove (4.4.5) we must have d(d-l) s 0 (mod 4), i.e. d e 0 (mod 4). Remark:
Theorem (6.2.1) was generalized by R. J. McEliece (On periodic sequences
from GF(q), Journal of Comb. Theory 10 (197 1 ), 80-9 1 ).
In the generalized form
j "pair ft is replaced by "j-tuple f ' and 4 is replaced by 2 • The proof is much more difficult.
A consequence of this theorem is that all the weights in the r-th order
m RM code of length 2 are divisJ.·ble by 2(m-l)/r].
( cf. (4 .3. 2) and (4 -3.5; ) also
see (6.2.3). For some time it was conjectured that a primitive BCH-code of designed distance d has minimum distance d.
As an application of (6.2.1) we show that this is false.
Let g(x) be the generator of the BCH code of length 127 and designed distance d
= 29.
Then the words of even weight form a subcode with generator (x-l)g(x) and
check polynomial hex).
Here hex) has degree
satisfies the conditions of (6.2.1). is divisible by 4.
42 and it is easily checked that hex)
Therefore the minimum weight in this subcode
We now annex the all-one vector to the generator matrix of the
subcode to find the original code back again.
Since we know from (4.1.11) that the
minimum distance of the BCH code is odd this minimum distance must be Therefore the minimum distance is not 29.
=3
(mod 4).
In fact it is 31.
The result on weights in RM codes mentioned in the remark above can be proved in different ways. (6.2.2) THEOREM:
One of them depends on the following theorem:
~ R(m)
be the m-dimensional vector space over GF(2) and let
F: R(m) ~ GF(2) be a pollOamial, F
= F(x 1,x2, ••• ,xm),
of
de~ree r.
We shall say G C F if the monomials of G form a subset of the monomials of F.
We define v( G) to be the number of variable s not
involved in G and we let
IGI
denote the number of monomials of
G.
124
If N(F) is the number of zeros of F in A, (m) then
zn- 1 + I
N(F) =
(-1) IG12 1GI+"'(G) -1 •
GCF
Proof:
For every G
C
F define f(G) to be the number of points in R(m) where
all the monomials of G have the value 0 and all the other monomials of F have the value 1.
Clearly we have
>f(H)
=
"'-i
2~(F-G)
ReG (because this is the number of points in the affine subspace of R(m) defined by xi
= xi
1
F - G.)
2
= ••• = xi
v
= 1 where the xi are the variables occurring in ~
It follows fram (4.2.7) that
I
f(G) =
~(H,G)2"'(F-H).
HCG
Clearly
I
=
N(F)
f(G).
GCF,IF-GI=O(mod 2)
Since
I
f(G) =
GCF
N(F)
zn we find
= zn-t
+
I ~ I ~ I ~
(_l)IF-GI f(G) =
OCF
= 2m- 1 +
OCF
= zn-1 =
zn-1
+
HCF
+
~
I
(_1)IF-G1
I
Iott(H,G)2",(F-H) =
HCG
(_1)IF-HI 2",(F-H)
I
1
=
Hc:nc:F
(_1}IF-HI 2",(F-H)2 IF - H1
HCF
= 2m- 1 +
~
I
(-1) IGI 2",(GHGI •
~F
(Remark:
This proof is new.
The theorem is due to R. J. McEliece).
125
Following the description on page 29
We now apply this theorem to RM codes.
the r-th order RM code is the set of value-tables of polynomials of degree
S!
in m
variables xl' x 2 ' •.• , xm over GF(2). The code word corresponding to the polynomial m F has weight 2 - N(F). If G c: F and G has degree d then "(G) ~ m - IGld, i.e.
IGI ~ rm ~ V(G)l
~
(where we use fal := min{n E Zln
r
,,(G) + m - v(G !
d
Since
a}).
)1 > r~l -
d
we have proved (by applying (6.2.2): (6.2.3) THEOREM:
The weights of the code words in the r-th order RM code of length r~l-
2m are divisible by 2 r
,
•
We now turn to the problem of weight enumeration for 2-nd order RM codes. this purpose we must study quadratic forms in m variables. 2
one vector fram the basis of the RM code.
Then, since Xi
value-tables of homogeneous quadratic forms
E a.jx.x ..
iSj
1.
1.
For
First, we omit the all-
= Xi'
all code words are
An invertible linear
J
transformation of R(m), i.e. a change of variables to say Yl' Y2 ' ••• , Y maps all m quadratic forms in Xl' ••• ,
~
into quadratic forms in y"
•.• , Ym.
Since the
weight of a code word is ~ - N(F) if F is the corresponding quadratic fo~, the linear transformation does not change the weights. will be useful. (6.2.4) LEMMA:
Therefore the following lemma
We consider nonsingular quadratic forms, i.e. forms F with ,,(F)
= o.
A non-singular homogeneous quadratic form F(x 1, ••• ,xm) =
E a ..xix. can be transformed by an invertible linear transformation
iSj 1.J
J
into a quadratic form of the type
Proof:
We know from (2.3.5) that F is not identically 1 or
F(~l' .•• '~)
=0
and (~l, ••• ,Sm) ~
Q then
= ~ixl
I
+ •••
If
we can find a transformation of
type Xi
o.
(1
l, •.• ,m)
126
which transforms F into a quadratic fom F/(X;, ••• ,X~) = i;ja~l~xj Without loss of generality we may assume a~2 ::,.
which a;l = O.
in
A trans-
m
formation with ~:: "I: a{ix~ then yields a quadratic form i=2 F H( x"h
If all the a~j are Yi
= X~.
for i
>
H) H H ••• 'Xm :: x,x 2 +
° we are finished.
ll 1/ II a ij Xi x j •
otherwise let Y, := x,/I +
II ~ a x.H , 2S,j 2j J ~
We then obtain the desired form.
2.
With the aid of this lemma we can prove the following theorem due to T. Kasami:
(6.2.5) THEOREM:
The weight of every code word in the second order RM code of m
~ 2
is of the form m 1 2 - + E: 2t
where Proof:
E:
0.2!:.±
First observe that we can remove the all-one vector from the basis
without changing the assertion.
By the definition on page 29 (see the ex-
ample on page 29 ) every basis vector v., i = 1, ••• , m-1 in the basis of the -~
RM codes of length 2m is of the form (v~, v~) where v~ is a basis vector for -1 ~ -J. m-l the RM codes of length 2 •
In the same way we see that for i = 1, 2, ••• ,
m-2 every basis vector -Vi bas the form (v~,v~,viH,v~) where -1 v~ is a basis - 1 - 1 - -1 m-2 vector for the RM codes of length 2 • theorem by induction.
This enables us to prove the
For small values of m it is easy to check the theorem.
If F(x" ••• ,x ) is a singular quadratic form we may assume without loss of m generality that x
m
does not occur and then the weight of the corresponding
code word is twice the weight ofa code word in the second orderRM code of length 2 m- 1 •
If F if; non-singular we apply (6.2.4) to transform F into
Now Ym-l :=: (9., 1., Q., 1) and !m = (9., 9., .l" .!) m-2 are of length 2 • It follows that the weight of the code
xm_,xm + Q(X" ••• ,xm- 2 )· where
.2
and
1.
m2 word corresponding to F is 3d + (2 - - d) where d is the weight of a code
word in the second order RM code of length
~-2
~.
• So in both cases the asser-
t10n follows from the induction hypothesis. (Remark:
This proof is new.
Kasami's proof depended on a standard form of quad-
ratic functions derived by extending (6.2.4). ) Combining the results of this section and section 6.1 and by generalizing (6.2.4) N. J. A. Sloane and E. R. Berlekamp have determined the complete weight enumerator for the second order RM code of length order Reed-Muller codes, IEEE Trans. on
tD..
(Weight enumerator for second-
Info~tion
Theorem, IT-16, 1970, 745-751).
By the same kind of methods T. Kasami and N. Tokura. have enumerated the code words with weight <
,..m-r+ 1
in the r-th order RM-code.
~
The smallest parameters for which one has not been able to find the weight enum256 . 1 erator are m = 8, r = 3. If t A1z is the weight enumerator of the 3-rd order RM i=O code of length 256 then we know that Ai = A256 - i • From the results of Kasami and
° (moi 4).
Tokura we can find Ai for i < 64.
By (6.2.3) Ai = 0 if i ~
17 coefficients to be determined.
Since the dual of this code is the 4-th order RM
code we know B. for J
tions.
j
This leaves
< 32 in (6.1.3) but this gives us only 16 independent equa-
Because of the size of the Ai this problem has eluded attempts to solve it
with the aid of a computer.
6.3 The
Carlitz-Uchi~
bound
In 1968 D. R. Anderson observed that a result of L. Carlitz and S. Uchiyama.
(Bounds for exponential sums, Duke Math. J. 24 (1951), 37-41) which depended on
A. Weil's well known paper on the Riemann Hypothesis in function fields (Proce Nat. Acad. Sci. U.S.A.
~
204-207) could be used to prove a theorem on weights in binary
codes. Consider a binary cyclic code of block length n t1
element of GF(2
).
= 2m -
1.
Let a be a primitive
If ~ is a code word in this code define
n-1 1 f(x) • -_ n- \'
L
j=O
S xJ j
= MS(c . -' x- ) = n- \'L * Tdeg(ai ) 1
1
i
(S xi) i
'
128
where
k-1 Tk(Z) :=
(6.3.2)
z L j=O
2
j
(see (3.4.4) and (3.4.8». We know from (3.4.5) that if c(x)
c.(, = f(a-.(,).
=
Now define
n-1 ~
1=0
1 c x then 1
For th1s function we have the following lemma: (6.3.4) LEMMA:
n-l
If c(x) = 1: c.x 1=0 ~
1
is a code word 1n the dual of the binary t-error-
correcting BCH code of block length n = 2m - 1 and if 2t - 2 < tfIl/2
then c = fy( a -t) for t = 0, 1, •.• , n-1 where a is a primitive t m element in GF(2 ). ~:
By (4.1.1) and (3.4.4) Si differs from 0 only if i belongs to a
cycle of -2 containing one of the integers 1,2, ••• , 2t.
Since, by (3.4.8),
we were to choose one 1 from each such cycle we can make this choice in such a way that i.:* SiX1 has degree i
that f(x)
= f(X)
S 2t
- 1.
if 2t - 2 < 2m/ 2 .
Tm(Sixi ) = Tdeg(ai)(Sixi) for i <
To prove the lemma we must show
To do this we must prove that
2~
Let di := deg(at). By (6.3.2) . 1 and the definition of deg (a~) it follows that T (s.x~) = T (S.x ) unless d• ~ m ~ ·
+ 1.
d
mid.~ is even, say m = 2k.d ~ i di
(ai )2
-1
= 1)
*
Then, since k d
~
(2 1_ 1 )1 = 0 (mod 2m_l) (because d.
k d
we have i ~ (2 i i _ 1)/(2 ~ _ 1) ~ 2 i
i +
This proves the lemma. Now the theorem of Carlitz and Uchiyama is: m (6.3.5) THEOREM: If a is a primitive element of GF(2 )
~
g(x) is a polynomial
of degree ".~ GF(2) such that for every polynomial rex) ~ any field GF(2t ) the polynomial [r(x)]2 - r(x) - g(x) is not constant then
12·9
This theorem on exponential sums over finite fields implies the following theorem:
(6.3.6) THEOREM: The mintmum distance of the dual of the binary t-error-correcting BCR code of block length n
= 2m -
1 is at least zn-l_l_
~t-1)zn/2.
*.
n-l i Let c(x) = t cix ~ Q be a code word in the i i=O dual of the t-error-correcting BCH code. It is easily seen that the condi-
Proof:
Let g(x) := t
tions of
S1X~.
(6.3.5) are satisfied. Then fram (6.3.5), (6.3.3) and (6.3.4) and
the fact that n is odd we find
I This
~lies
(t_l)~/2.
1+
I
n-l
(_l)C.r.,
t=o
m-1
that the minimum weight of the code is at least 2
To apply
- 1 -
(6.3.9) we needed the restriction 2t - 2 < ~/2 but
this. can now be dropped because
(2t-2)
I ~ (2t-2)zn/2 •
(6.3.6) is trivially correct if
~ zn/2.
Consider the binary 5 -error-correcting BCR code of block length 127.
Example:
By
inspection of the check polynomial of this code we see that the dual code is a subcode of a However
7-error-correcting
(6.3.6) implies d
~
BCH code and therefore has minimum distance d
~
15.
18.
Knowledge of the type provided by
(6.3.6) can be very useful in weight enum-
eration e.g. when one wishes to apply the MacWilliams relations
(6.1.3).
References [1]
E. F. Assmus and H. F. Mattson, On tactical configurations and errorcorrecting codes, Journal of Comb. Theory 3 (1967), 243-257.
[2]
E. F. Assmus, H. F. Mattson, R. Turyn, Cyclic codes, Report AFCRL-65-332 of the Applied Research Laboratory of Sylvania Electronic Systems (1965).
[3]
E. F. Assmus, H. F. Mattson, R. Turyn, Cyclic codes, Report AFCRL-66-348 of the Applied Research Laboratory of Sylvania Electronic Systems (1966).
[4]
E. F. Assmus, H. F. Mattson, R. Turyn, Research to develop the algebraic theory of codes, Report AFCRL-67-0365 of the Applied Research Laboratory of Sylvania Electronic Systems (1967).
[5]
E. R. Berlekamp, Algebraic coding theory, McGraw Hill, New York (1968).
[6]
R. G. Gallager, Information theory and reliable communication, Wiley,
New York (1968). [7]
H. J. L. Kamps and J. H. van Lint, The football pool problem for 5 matches,
Journal of Comb. Theory 3 (1967), 315-325.
[8] A. I. Khinchin, Mathematical foundations of information theory, Dover, New York (1957).
[9]
J. H. van Lint, 1967-1969 Report of the discrete mathematics group, Report
69-WSK-04 of the Technological University, Eindhoven, Netherlands (1969).
[10]
J. H. van Lint, On the nonexistence of perfect 2- and 3- Hamming-errorcorrecting codes over GF(q), Information and Control 16 (1970), 396-401.
[11]
J. H. van Lint, Nonexistence theorems for perfect error-correcting codes, Computers in algebra. and number theory, SIAM-AMS Vol. 3 (to appear).
[12]
J. H. van Lint, Nonexistence of perfect 5-6-and 7-Hamming-error-correcting codes over GF(q), Report 70-WSK-06 of the Technological University Eindhoven, Netherlands (1970).
131
[13]
S. P. Lloyd, Binary block coding, Bell System Tech. J. 36 (1951), 511-535.
[14]
H. F. Mattson and G. ,Solomon, A new treatment of Bose-Chaudhuri codes,
J. Soc. Indust. Appl. Math. 9 (1961), 654-669.
[15] W. W. Peterson, Error-correcting codes, M.I.T. Press, Cambridge (1961). [16]
I. S. Reed, A class of multiple-error-correcting codes and the decoding scheme, IEEE Trans. Inform. Theory, IT-4 (1954), 38-49.
[11]
D. Slepian, Coding theory, Nuovo Cimento 13 (1959), 313-388.
[18] A. D. Wyner,
On coding and information theory, SIAM Review
l' (1969),
311-346. O~
A. Tietavainen, On the non-existence of perfect codes over finite fields, SIAM j. Appl. Math. 24 (1973), 88-96.
~q
W.A. Zinoviev and W.K. Leontiev, A theorem on the nonexistence of perfect codes over finite fields (Russian), to appear.
~~
H.W. Lenstra jr., Two theorems on perfect codes, Discrete Math. 3 (1972), 125-132.
~~
J.H. van Lint, A survey of perfect codes, to appear in Rocky Mountain J. Math.
INDEX
affine
pe~utation
group
61
average mutual infonnation
9
average self-information
9
BCH code
61
block code
15
BSC, binary symmetric channel
4, 13 11
burst burst-error
3, 11
capacity
9,10
Carlitz-Uchiyama bound
121
channel character check-polynomial
108
45 4
code, BCH
61
binary Golay
84, 96, 91, 98, 119
block
15
cyclic
42
direct-product
36
dual
11
e-error-correcting
15
Elias
40
equivalent
16, 48, 90
extended
22, 80
generalized RM
15
group
15. 88
Hamming
20, 21, 22, 30, 41, 86
133
irreducible cyclic
45, 56
linear
15
maximal cyclic
43
(n,k)
15, 40
optimal
72
perfect
21, 22, 85, 86
primitive BCH
61
quadratic residue
79, 80
Reed-Muller
27, 29, 78
Reed-Solomon
70
repetition
13, 29, 96
systematic
17
ternary Golay
85, 96, 102, 115
coset leader
18, 19
covering problem
92
cyclic code
42
decoding failure
22
designed distance
61
direct-product code
36
DMC, discrete memoryless channel
4
dual code
17
Elias codes
40
entropy equivalent codes erasure
9, 13 16, 48, 90 2, 13
error error-correcting code
15
error location
65
error locator
65
134
error pattern
6
exponent
44
extended code
22, 80
field polynomial
56
football-pool problem
22, 92
generalized RM codes
75
generator matrix
16
generator polynomial
43
Golay code (binary)
84, 96, 97, 98,
tt
tr
(ternary)
group code group ring Hamming code Hamming distance idempotent primitive infonnation rate
85, 96, 102, 115
15, 88 105 20, 21, 22, 30,
7
49, 82 50, 51
5
information symbol
17
irreducible cyclic code
45, 56
Kronecker product
38
linear code
15
linear functional linear recurring sequence Lloyd I s theorem
119
108
57 104
JJ.(S,T)
73
Mathieu group
98
Mattson-Solomon polynomial
58
47, 86
135
max~l
cyclic code
maxDnum likelihood decoding min~l
ideal
minimum distance monomial group mutual information
43 6, 19 45 15 106
8
15, 40
(n,k)-code noise optimal codes
72
orthogonal parity-check equations
33, 36
overall parity-check
22
parity-check equation
'7, 33, 36
It
tt
matrix
It
II
symbol
17, 40
3, '7, 22
perfect code
21, 22, 85, 86
period
53
primitive BCR code
61
primitive idempotent
50, 51
PSL (2,n)
83, 98
quadratic residue codes
79, 80
reduced echelon form
16
redundancy
3
Reed-Muller codes
27, 29, 78
Reed-Salamon codes
70
repetition codes
13, 29, 96
self-information Shannon I s fundamental theorem
9 10, 11
136
sphere
1
sphere-packing condition
92
standard array
18
Steiner system
94
syndrome
17, 18
systematic code
17
tactical
94
configu~t1on
t-design
94
threshold decoding
32
trace
56
Vandermonde detezminant
57
weight
15
weight enumerator
23, 70, 73, 89, 120, 122
fI
word length
tt
(Hamming codes)
25, 41
15
Lecture Notes in Mathematics Comprehensive leaflet on request request Comprehensive
Vol. Vol. 178: 178: Th. Th. Brocker Brocker und und T. T. tom tom Dieck, Dieck, Kobordismentheorie. XVI, XVI,
Seiten. 1970. 1970. DM OM 18,191 Seiten. Vol. 146: A. A. B. Altman and S. S. Kleiman, Introduction Introduction to to Grothendieck Grothendieck Vol. Duality Theory. Theory. II, II, 192 192 pages. pages. 1970. 1970. DM DM 18,Duality
Vol. 147: 147: D. D. E. E. Dobbs, Dobbs, Cech Cech Cohomological Cohomological Dimensions Dimensions for for ComComVol. VI, 176 176 pages. pages. 1970. 1970. DM DM 16,16,mutative Rings. Rings. VI, mutative Vol. 148: R. Azencott, Espaces de POisson Poisson des Groupes Localement Vol. 1970. DM OM 16,Compacts. IX, 141 pages. 1970.
Vol. 149: R. G. Swan and E. G. Evans, K-Theory of Finite Groups and Vol. 1970. DM 20,Orders. IV, 237 pages. 1970. Vol. 150: 150: Heyer, Dualitiit DualiUit lokalkompakter Gruppen. XIII, 372 Seiten. Vol. 1970. DM 20,-
Vol. 151: M. Demazure et A. Grothendieck, Schemas en Groupes I. Vol. XV, 562 pages. 1970. DM 24,(SGA 3). XV,
Vol. Vol. 179: Semlnarre Seminaire Bourbaki Bourbaki - vol. 1968/69. Exposes Exposes 347-363. IV. IV.
295 pages. pages. 1971. 1971. DM DM 22,22,295 Vol. Vol. 180: 180: Seminaire Seminaire Bourbaki Bourbaki - vol. 1969170. 1969/70. Exposes 364·381. 364-381. IV, IV,
310 pages. pages. 1971. 1971. DM DM 22,310 Vol. Vol. 181: 181: F. DeMeyer DeMeyer and and E. E. Ingraham, Separable Separable Algebras Algebras over over
OM 16.Commutative Rings. V, 157 pages. 1971. DM
Vol. Vol. 182: L. D. Baumert. Cyclic Difference Sets. VI, VI, 166 pages. 1971.
OM 16,DM16,-
Vol. Vol. 183: Analytic Theoryof Differential Equations. Edited by P. F.Hsieh F..Hsieh and A. W. J. Stoddart. VI, VI, 225 pages. 1971. DM 20,-
Vol. 184: Symposium on Several Complex Variables, Park City, Utah, Vol. 20,1970. Edited by R. M. Brooks. V, 234 pages. 1971. DM 20,-
Vol. Vol. 185: Several Complex Variables Variables II, Maryland 1970. Edited by
Vol. 152: M. Demazure et A. Grothendieck, I3chemas ~chemas en Groupes II. Vol. 1970. DM OM 24,-(SGA 3). IX, 654 pages. 1970.
OM 24,J. Horvath. III, 287 pages. 1971. DM
Vol. 153: M. Demazure et A. Grothendieck, Schemas en Groupes III. Vol. OM 24,(SGA 3). VIII, 529 pages. 1970. DM
Vol. 186: Recent Trends in Graph Theory. Edited by M. Capobianco/ Vol. J. B. Frechen/M. Krolik. VI, VI, 219 pages. 1971. DM 18.-
Vol. '154: A. Lascoux et M. Berger, Varietes Kiihleriennes Kahleriennes Compactes. Vol. VII, 83 pages. 1970. DM 16,VII, Vol. 155: Several Complex Variables I, Maryland 1970. Edited by J. Horvath. IV, 214 pages. 1970. DM 18,Vol. 156: R. -Hartshorne, Ample Subvarieties of Algebraic Varieties. XIV, 256 pages. 1970. DM 20,-
-
Vol. Vol. 187: H. S. Shapiro, Topics in Approximation Theory. VIII, 275 pages.
OM 22,1971. DM Vol. 188: Symposium on Semantics of Algorithmic Languages. Edited OM 26,by E. Engeler. VI, 372 pages. 1971. DM Vol. 189 189: A. Weil, Dirichlet Series and Automorphic Forms. V. V, 164
OM 16,pages. 1971. DM
Vol. 190: Martingales. Marti~gales. A Report on a Meeting at Oberwolfach, May
Vol. 157: T. tom Dieck, K. H. Kamps und D. Puppe, Homotopietheorie. VI, 265 Seiten. 1970. DM 20,-
17-23,1970. Edited by H. Dinges. V, 75 pages. 1971. DM 16,-
Vol. 158: T. G. Ostrom, Finite Translation Planes. IV. 112 pages. 1970.
Vol. 191: Seminaire de Probabilites V. Edited by P. A. Meyer. IV, 372
OM16,DM16,-
pages. 1971. DM 26,-
Vol. 159: R. Ansorge und R. Hass. Konvergenz von Differenzenverfahren fur lineare und nichtlineare Anfangswertaufgaben. VIII, 145
Vol. 192: Proceedings of Liverpool Singularities - Symposium I. Edited OM 24,by C. T. C. Wall. V, 319 pages. 1971. DM
OM 16,Seiten. 1970. DM
Vol. 160: L. Sucheston, Constributions to Ergodic Theory and Probability. VII, 277 pages. 1970. DM 20,Vol. 161: J. Stasheff, H-Spaces from a Homotopy Point of View. VI, 95 pages. 1970. DM 16,Vol. 162: Harish-Chandra Harlsh-Chandra and van Oijk, DIJk, Harmonic Analysis on Reductive p-adic Groups. IV, 125 pages. 1970. OM DM 16,Vol. 163: P. Deligne, Equations Equalions Oifferentielles Differentlelles a Points Singuliers
Reguliers. 111,133 III, 133 pages. 1970. DM 16,-
Vol. 164: J. P. Ferrier, Seminaire sur les Algebres Completes. II, 69 pa-. pa·
ges. 1970. DM 16,-
Vol. 193: Symposium Sy.mposium on the Theory of Numerical Ana.lysis. Edited OM 16,by J. L1. Morns. VI, 152 pages. 1971. DM byJ.lI. Vol. M. Berger, Vol.. ,1194: ~4: .M. Be~ger, P. Gauduchon et E. Mazet. Le Spectre d'une Vanete Riemannlenne. R,emannlenne. VII, 251 pages. 1971. DM 22,Variete Vol. 195: Reports of the Midwest Category Seminar V. Edited by J.w. J.W. Gray and S. Mac Lane.lIl, Lane.lIl. 255 pages. 1971. OM DM 22,-
AoOt 1970. Edited by F. Vol. 196: H-spaces - NeuchAtel (Suisse)- AoCJt Sigrist, V, 156 pages. 1971. DM 16,Vol. 197: Manifolds - Amsterdam 1970. Edited by N. H. Kuiper. KUiper. V, 231
pages. 1971 1971. DM 20,-
Vol. 165: J. M. Cohen, Stable Homotopy. V, 194 pages. 1970. OM DM 16.-
Vol. 198: M. Herve, Analytic and Plurisubharmonic Functions in Finite and Infinite Dimensional Spaces. VI, 90 pages. 1971. DM 16.-
p-adics: Its its Representations, Vol. 166: A. J. Silberger, PGL PGL,2 over the p-adlcs: Spherical Functions, and Fourier Analysis. VII, 202 pages. 1970.
Vol. 199: Ch. J. Mozzochi, On the Pointwise PointWise Convergence of Fourier Series. VII, 87 pages. 1971. DM 16,-
OM 18,DM
Vol. 167: Lavrentiev, Romanov and Vasiliev, Multidimensional MultidimenSional Inverse Problems for Differential Equations. V, 59 pages. 1970. DM 16,Vol. 168: F. P. Peterson, The Steenrod Algebra and its Applications: A conference to Celebrate N. E. Steenrod's Sixtieth Birthday. VII,
317 pages. 1970. OM DM 22,-
Vol. 169: M. Raynaud, Anneaux Locaux Henseliens. V, 129 pages. 1970. DM 16,Vol. 170: Lectures in Modern Analysis and Applications III. Edited by C. T. Taam. VI, 213 pages. 1970. DM 18,. Vol. 171: Set-Valued Mappings, Selections and Topological Properties of 2 x. Edited by W. M. Fleischman. X, 110 pages. 1970. OM DM 16,Vol. 172: Y.-T. Siu and G. Trautmann, Gap-Sheaves and Extension of Coherent Analytic Subsheaves. V, 172 pages. 1971. DM 16,Vol. 173: J. N. Mordeson B. Vinograde, Structure of Arbitrary Mordeson. and B. Purely Inseparable Extension ExtenSion Fields. IV, 138 pages. 1970. OM DM 16,V~1. Vol. 174: B. iversen, Iversen, linear Linear Determinants with Applications to the Picard Scheme of a Family of Algebraic Curves. VI VI, 69 pages pages. 1970 1970. OM ' .. DM 16,16,-
Vol. 200: U. Neri, Singular Integrals. VII, 272 pages. 1971. DM OM 22,Vol. 201 201:: J. H. van Lint, Coding Theory. VII, 136 pages. 1971. DM 16,Vol. 202: J. Benedetto, Harmonic Analysis on Totally Disconnected
DM 22,Sets. VIII, 261 pages. 1971. OM Vol. 203: D. Knutson, Algebraic Spaces. VI, 261 pages. 1971. OM DM 22,SinguliElres. IV, 53 pages. 1971. Vol. 204: A. Zygmund, Integrales Singulieres. OM DM 16,Vol. 205: Seminaire Pierre Lelong (Analyse) Annee 1970. VI, 243 DM 20,pages. 1971. OM Vol. 206: Symposium on Differential Equations and Dynamical Systems. Edited by D. Chillingworth. XI, 173 pages. 1971. DM 16,Vol. 207: L. Bernstein, The Jacobi-Perron Algorithm - Its Theory and Application. Applicalion. IV, 161 pages. 1971. OM DM 16,-
Vol. 175: M. Brelot, On Topologies and Boundaries in Potential Theory. VI, 176 pages. 1971. OM DM 18,-
Vol. 208: A. Grothendieck and J. P. Murre, The Tame Fundamental Group of a Formal Neighbourhood of a Divisor with Normal Crossings on a Scheme. VIII, 133 pages. 1971. OM DM 16,Vol. 209: Proceedings of Liverpool Singularities Symposium II. Edited by C. T. C. Wall. V, 280 pages. 1971. DM 22,-
Vol. 176: H. Popp, Fundamentalgruppen algebraischer Mannigfaltigkeiten. IV, 154 Seiten. 1970. 1970. OM DM 16,-
111,118 Vol. 210: M. Eichler, Projective Varieties and Modular Forms. III, 118 pages. 1971. OM DM 16,-
Vol. 177: J. Lambek, Torsion Theories, Additive Semantics and Rings of Quotients. VI, 94 94 pages. 1971. OM DM 16,-
Vol. 211: Theorie des Matro"ldes. Matro'r'des. Edite par C. P. Bruter. III, 108 pages. 1971. OM DM 16,-
Please turn over
Vol. 212: B. Scarpellini, Proof Theory and IntUitlonistic Intuitionistic Systems. VII, 291 pages. 1971. DM 24,VII,291 Vol. 213: H. Hogbe-Nlend, Theorie des Bornologies et Applications. V, 168 pages. 1971. DM 18,Vol. 214: M. Smorodinsky, Ergodic Theory, Entropy. V, 64 pages. 1971. 1971 . DM 16,-
Vol. 246: Lectures on Rings and Modules. Tulane University Ring and Operator Theory Year, 1970-1971. Volume I. X, 661 pages. 1972. DM 40,Vol. 247: Lectures on Operator Algebras. Tulane University Ring and Operator Theory Year, 1970-1971. Volume II. XI, 786 pages. 1972. DM 40,Vol. 248: Lectures on the Applications of Sheaves to Ring Theory. Tulane UniverSity University Ring and Operator Theory Year, 1970-1971. Volume III. VIII, 315 pages. 1971. DM 26,-
Vol. 215: P. Antonelli, D. Burghelea and P. J. Kahn, The ConcordanceHomotopy Groups of Geometric Automorphism Groups. X, 140 pages. 1971.DM . 1971. DM 16,Vol. 216: H. MaaB, Siegel's Modular Forms and Dirichlet Series. VII, 328 pages. 1971. DM 20,Vol. 217: T. J. Jech, Lectures in Set Theory with Particular Emphasis on the Method of Forcing. V, 137 pages. 1971. DM 16,-
Vol. 250: B. Jonsson, Topics in Universal Algebra. VI, 220 pages. 1972. DM 20,-
Vol. 218: C. P. Schnorr, ZuHilligkeit Zufalligkeit und Wahrscheinlichkeit. IV, 212 Seiten 1971. DM 20,-
Vol. 251: The Theory of Arithmetic Functions. Edited by A. A. Gioia and D. L. Golds mith VI, 287 pages. 1972. DM 24,-
Vol. 219: N. L. Alling and N. Greenleaf, Foundations of the Theory of Klein Surfaces. IX, 117 pages. 1971. DM 16,-
Vol. 252: D. A. Stone, Stratified Polyhedra. IX, 193 pages. 1972. DM 18,Vol. 253: V. Komkov, Optimal Control Theory for the Damping of Vibrations of Simple Elastic Systems. V, 240 pages. 1972. DM 20,-
Vol. 220: W. A. Cappel, Coppel, Disconjugacy. V, 148 pages. 1971. DM 16,Vol. 221: P. Gabriel und F. Ulmer, Lokal prasentierbare Kategorien. V, 200 Seiten. 1971. DM 18,-
Vol. 222: C. Meghea, Compactification des Espaces Harmoniques. III, 108 pages. 1971. DM 16,111,108 Vol. 223: U. Feigner, Models of ZF-SetTheory. ZF-Set Theory. VI, 173 pages. 1971. DM 16,Vol. 224: Revetements Etales et Groupe Fondamental. (SGA 1). Dirige par A. Grothendieck XXII, 447 pages. 1971. DM 30,-
Vol. 225: Theorie des Intersections et Theoreme de Rlemann-Roch. Riemann-Roch. lliusie. XII, (SGA 6). Dirige par P. Berthelot, A. Grothendieck et L. Illusie. 700 pages. 1971. DM 40,Vol. 226: Seminar on Potential Theory, II. Edited by H. Bauer. IV, 170 pages. 1971. DM 18,-
Vol. 249: Symposium on Algebraic Topology. Edited by P. J. Hilton. VII, 111 pages. 1971. DM 16,-
UrTl et leurs ApVol. 254: C. U. Jensen, Les Foncteurs Derives de lim 1972. DM 16,plications en Theorie des Modules. V, 103 pages. 1972. Vol. 255: Conference in Mathematical Logic - London '70. Edited by W. Hodges. VIII, 351 pages. 1972. DM 26,Vol. 256: C. A. Berenstein and M. A. Dosial, Dostal, Analytically Uniform Spaces and their Applications to Convolution Equations. VII, 130 pages. 1972. DM 16,Vol. 257: R. B. Holmes, A Course on Optimization and Best Approximation. VIII, 233 pages. 1972. DM 20,Vol. 258: Seminaire de Probabilites VI. Edited by P. A. Meyer. VI, 253 pages. 1972. DM 22,Vol. 259: N. Moulis, Structures de Fredholm sur les Varietes Hilbertiennes. V, 123 pages. 1972. DM 16,-
Vol. 227: H. L. Montgomery, Topics in Multiplicative Number Theory. IX, 178 pages. 1971. DM 18,-
Vol. 260: R. Godement and H. Jacquet, Zeta Functions of Simple Algebras. IX, 188 pages. 1972. DM 18,-
Vol. 228: Conference on Applications of Numerical Analysis. Edited L1. Morris. X, 358 pages. 1971. DM 26,by J. LI.
Vol. 261: A. Guichardet, Symmetric Hilbert Spaces and Related Topics. V, 197 pages. 1972. DM 18,-
Vol. 229: J. Valsala, Vaisala, Lectures on n-Dimensional Ouasiconformal Quasiconformal Mappings. XIV, 144 pages. 1971. OM E>M 16,-
Vol. 262: H. G. Zimmer, Computational Problems, Methods, and Results in Algebraic Number Theory. V, 103 pages. 1972. DM 16,Vol. 263: T. Parthasarathy, Selection Theorems and their Applications. VII, 101 pages. 1972. DM 16,-
Vol. 230: L. Waelbroeck, Topological Vector Spaces and Algebras. VII, 158 pages. 1971. DM 16,Vol. 231: H. Reiter, L1-Algebras Ll-Algebras and Segal Algebras. XI, 113 pages. 1971. DM 16,Vol. 232: T. H. Ganelius, Tauberian Remainder Theorems. VI, 75 pages. 1971. DM 16,Vol. 233: C. P. Tsokos and W. J. Padgett. Random Integral Equations w ith Applications to Stochastic Systems. VII, 174 pages. 1971. DM with 118,8 ,Vol. 234: A. Andreotti and W. Stoll. Analytic and Algebraic Dependence of Meromorphic Functions. III, 390 pages. 1971. DM 26,-
Vol. 235: Global Differentiable Dynamics. Edited by O. Hajek, A. J. Lohwater, and R. McCann. X, 140 pages. 1971. DM 16,Vol. 236: M. Barr, P. A. Grillet, and D. H. van Osdol. Exact Categories and Categories of Sheaves. VII, 239 pages. 1971, DM 20,Vol. 237: B. Stenstrom. Rings and Modules of Ouotients. Quotients. VII, 136 pages. 1971. DM 16,-
Vol. 238: Der kanonische Modul eines Cohen-Macaulay-Rings. Herausgegeben von JUrgen JOrgen Herzog und Ernst Kunz. VI, 103 Seiten. 1971. DM 16,Vol. 239: L. Illusie, IIlusie, Complexe Cotangent et Deformations I. XV, 355 pages. 1971. DM 26,Vol. 240: A. Kerber, Representations of Permutation Groups I. VII, 192 pages. 1971. DM 18,Vol. 241: S. Kaneyuki, Homogeneous Bounded Domains and Siegel Domains. V, 89 pages. 1971. DM 16,Vol. 242: R. R. Coifman et G. Weiss, Analyse Harmonique NonCommutative sur Certains Espaces. V, 160 pages. 1971. DM 16,Vol. 243: Japan-United States Seminar on Ordinary Differential and Functional Equations. Edited by M. Urabe. VIII, 332 pages. 1971. DM 26,Vol. 244: Seminaire Bourbaki - vol. 1970/71. Exposes 382-399. IV, 356 pages. 1971. DM 26,Vol. 245: D. E. E Cohen, Groups of Cohomological Dimension One. V, 99 pages. 1972. DM 16,-
Vol. 264: W. Messing, The Crystals Associated to Barsotti-Tate Groups: with Applications to Abelian Schemes. III, 190 pages. 1972. DM 18,Vol. 265: N. Saavedra Rivano, Categories Tannakiennes. II, 418 pages. 1972. DM 26,Vol. 266: Conference on Harmonic Analysis. Edited by D. Gulick and R. L. Lipsman. VI, 323 pages. 1972. DM 24,Vol. 267: Numerische Losung nichtlinearer partieller Differential- und Integro-Differentialgleichungen. Herausgegeben von R. Ansorge und
W. Tornig, VI, 339 Seiten. 1972. DM 26,-
Vol. 268: C. G. Simader, On Dirichlet's Boundary Value Problem. IV, 238 pages. 1972. DM 20,Vol. 269: Theorie des Tapas Topos et Cohomologie Etale des Schemas. (SGA 4). Dirige par M. Artin, A. Grothendieck et J. L. Verdier. XIX, 525 pages. 1972. DM 50,Vol. 270: Theorie Thaorie des Tapas Topos et Cohomologie Etle des Schemas. Tome 2. (SGA 4). Dirige par M. Artin, A. Grothendieck et J. L. Verdier. V, 418 pages. 1972. DM 50,Vol. 271: J. P. May, The Geometry of Iterated Loop Spaces. IX, 175 pages. 1972. DM 18,Vol. 272: K. R. Parthasarathy and K. Schmidt, Positive Definite Kernels, Continuous Tensor Products, and Central Limit Theorems of Probability Theory. VI, 107 pages. 1972. DM 16,Vol. 273: U. Seip, Kompakt erzeugte Vektorraume und Analysis. IX, 119 Seiten. 1972. DM 16,Vol. 274: Toposes, Algebraic Geometry and Logic. Edited by. F. W. Lawvere. VI, VI,189 189 pages. 1972. DM 18,Vol. 275: seminaire 5eminaire Pierre lelong Lelong (Analyse) Annee 1970-1971. VI, 181 pages. 1972. DM 18,Vol. 276: A. Borel, Representations de Groupes Localement Compacts. V, 98 pages. 1972. DM 16,seminaire Banach. Edite par C. Houze!: VII, 229 pages. Vol. 277: 5eminaire 1972. DM 20,-
Vol. 278: H. Jacquet, Automorphic Forms on GL(2). Part II. XIII, 142 pages. 1972. OM 16,Vol. 279: R Bott, Sott, S. Gitler and I. M. James, Lectures on Algebraic and Differential Topology. Topology~ V, 174 pages. 1972. OM 18,Vol. 280: Conference on the Theory of Ordinary and Partial DifferenW. N. Everitt and B. D. Sleeman. XV, 367 tial Equations. Edited by byW. pages. 1972. OM 26,Vol. 281: Coherence in Categories. Edited by S. Mac Lane. VII, 235 pages. 1972. OM 20,-
Commutative Algebra. Edited by J. W. Vol. 311: Conference on Commutstive Brewer and E. A A. Rutter. VII, 251 pages. 1973. OM 22,Vol. 312: Symposium on Ordinary Differential Equations. Edited by W. A. Harris, Jr. and Y. Sibuya. VIII, 204 pages. 1973. OM 22,Vol. 313: K K. Jllrgens Jergens and J. Weidmann, Spectral Properties of Hamiltonian Operators. III, 140 pages. 1973. OM 16,Vol. 314: M. Deuring, Lectures on the Theory of Algebraic Functions of One Variable. VI, 151 pages. 1973. OM 16,Vol. 315: K. Biehteler, Bichteler, Integration Theory (with Special Attention to Vector Measures). VI, 357 pages. 1973. OM 26,-
Vol. 282: W. Klingenberg und P. Flaschel, Riemannsche Hilbertmannigfaltigkeiten. Periodische Geoditische. Geodlltische. VII, 211 Seiten. 1972. OM 20,-
Vol. 316: Symposium on Non-Well-Posed Problems and Logarithmic Convexity. Edited by R. J. Knops. V, 176 pages. 1973. OM 18,-
Vol. 283: L lIIusie, Complexe Cotangent et Deformations II. VII, 304 pages. 1972. OM 24,-
Vol. 317: 5eminaire seminaire Bourbaki - vol. 1971172. 1971/72. Exposes 400-417. IV, 361 pages. 1973. OM 26,-
Vol. 284: P. A A Meyer, Martingales and Stochastic Integrals I. VI, 89 pa/ ,-~ ges. 1972. OM 16,- /'
A. Beck, VIII, 285 pages. 1973. OM 24,-
Vol. 285: P. de 11I~rpe, I,,~rpe, Classical Banach-Lie Algebras and BanachLie Groups of CIf Operators Ue Operators in Hilbert Space. III, 160 pages. 1972. OM 16,' Vol. 286: S. Murakami, On Automorphisms of Siegel Domains. V, 95 pages. 1972. OM 16,. Vol. 287: Hyperfunctions and Pseudo-Differential Equations. Edited by H. Komatsu. VII, 529 pages. 1973. OM 36,288: Groupes Grou~s de Monodromie en Geometrie A1gebrique. Aigebrique. (SGA 7 Vol. 286: I). Dirige par A Grothendieck. IX, 523 pages. 1972. DM 50,Vol. 289: B. Fuglede, Finely Harmonic Functions. III, 188. 1972. OM 18,Vol. 290: D. B. Zagier, Equivariant Pontrjagin Classes and Applications to Orbit Spaces. IX, 130 pages. 1972. OM 16,-
Vol. 318: Recent Advsnces Advances in Topological Dynsmics. Dynamics. Edited by
R W. Gatterdam Vol. 319: Conference on Group Theory. Edited by R. and K K. W. Weston. V, 186 18,188 pages. 1973. OM .18,Vol. 320: Modular Functions of One Variable I. Edited by W. Kuyk. V. 195 pages. 1973. DM OM 18,Vol.: 321: Seminaire de Probabilites VII. Edite par P. A. Meyer. VI, 322 pages. 1973. OM 26,Vol. 322: Nonlinear Problems in the Physical Sciences and Biology. snd D. H. Sattinger, Ssttinger, VIII, 357 pages. Edited by I. Stakgold. D. D. Joseph and 1973. OM 26,Vol. 323: J. L. Lions, Perturbations Singulieres dsns dans les Problemes aux Limites et en ContrOle Optimal. XII, 645 pages. 1973. OM 42,Vol. 324: K. Kreith, Oscillation Theory. VI, 109 pages. 1973. DM 16,-
Vol. 291: P. Orlik, Seifert Manifolds. VIII, 155 pages. 1972. OM 16,Vol. 292: W. D. Wallis, A. P. Street and J. S. Wallis, Combinatorics: Room SQuares, Sum-Free Sets, Hadamard Matrices. V, 508 pages. 1972. DM oM 50,Vol. 293: R. A DeVore, The Approximation of Continuous Functions by Positive Linear Operators. VIII, 289 pages. 1972. DM 24,-.
Vol. 326: A. Robert, Elliptic Curves. VIII, 264 pages. 1973. OM DM 22,-
Vol. 294: Stability of Stochastic Dynamical Systems. Edited by RF. R. F. Curtain. IX, 332 pages. 1972. DM 26,-
Vol. 328: J. R R. SUchi BOchi and D. Siefkes, The Monadic Second Order Theory of All Countable Ordinals. VI, 217 pages. 1973. DM 20,-
Vol. 295: C. Dellacherie, Ensembles Analytiques, Capacites, Mesures de Hausdorff. XII, 123 pages. 1972. DM OM 16,-
Vol. 329: W. Trebels, Multipliers for (C, a)-Bounded Fourier Expansions in Banach Spaces and ApprOXimation Approximation Theory. VII, 103 pages. 1973. OM DM 16,-
Vol. 296: Probability and Information Theory II. Edited by M. Behara, Sehara, K. Krickeberg and J. Wolfowitz. V, 223 pages. 1973. DM 20,Vol. 297: J. Garnett, Analytic Capacity and Measure. IV, 138 pages. 1972. OM 16,Vol. 298: Proceedings of the Second Conference on Compact Transformation Groups. Part 1. XIII, XII1, 453 pages. 1972. OM 32,Vol. 299: Proceedings of the Second Conference on Compact Transformation GrouP!!. Group$. Part 2. XIV, 327 pages. 1972. OM 26,Vol. 300: P. Eymard, Invariantes et Representations Unitaires. Eymartt, Moyennes MoyennesInvariantes 11.113 pages. 1972. OM 16,1912. DM 301 : F. Pittnauer, Vorlesungen uber Vol. 301: Ober asymptotische Reihen. VI, 186 Seiten. 1972. OM! 18,Vol. 302: M. Dernazure, Demazure, Lectures on p-Divisible Groups. V, 98 pages. 1972. OM 16,Vol. 303: Graph Theory and and Applications. Edited by Y. Alavi, D. R. Lick and A. T. White. IX, 329 pages. 1972. OM 26,Vol. 304: A K. Bousfield and snd D. M. Kan, Homotopy Limits, Completions and Localizations. V, 348 pages. 1972. OM 26,Vol. 305: Th60rie Tapas et Cohomologie Etale des Schemas. Th~orie des Topos Tome 3. (SGA 4). Dirige par M. Min, Arlin, A A. Grothendieck et J. L. Verdier. VI, VI? 640 pages. 1973. OM 50,Vol. 306: H. Luckhardt, Extensional GOdel Functional Interpretation. VI, 161 pages. 1973. OM 18,P.-A. Meyer, Ecole d'ete Vol. 307: J. L. Bretagnolle, Bratagnolle, S. D. Chatterji et P.-A de Probabilites: Processus Stochastiques. VI, 198 pages. 1973. OM 20,Knutson, 1-Rings Vol. 308: D. Knulaon, A-Rings and the Representation Theory of the Symmetric Group. IV, 203 pages. 1973. OM 20,Vol. 309: D. H. Sattinger, Topics in Stability and Bifurcation Theory. VI,190 VI, 190 pages. 1973. OM 18,Vol. 310: B. Iversen, Generic Local Structure of the Morphisms in Commutative Algebra. IV, 108 pages. 1973. OM 16,-
Vol. 325: Ch.-eh. Ch.-Gh. Chou, La Transformation de Fourier Complexe et L'Equation de Convolution. IX, 137 pages. 1973. DM 16,Vol. 327: E. Matlis, l-Dimensional 1-Dimensional Cohen-Macaulay Rings. XII, 157 pages. 1973. DM 18,-
Vol. 330: Proceedings of the Second Japan-USSR Symposium on Probability Theory. Edited by G. Maruyama and Yu. V. Prokhorov. VI,550 VI, 550 psges. pages. 1973. OM 36,Vol. 331: Summer School on Topological Vector Spaces. Edited by L. L Waelbroeck. VI, 226 pages. 1973. OM 20,Seminaire Pierre Lelong (Analyse) Annee Vol. 332: S8minaire Annes 1971-1972. V, 131 pages. 1973. OM 16,Vol. 333: Numerische, insbesondere approximationstheoretische Behandlung von Funktionalgleichungen. Herausgegeban Herausgegeben von R. R Ansorge und W. Tllrnig. / Ternig. VI, 296 Seiten. 1973. OM 24,Vol. 334: F. Schweiger, The Metrical Theory of Jacobi-Perron Algorithm. V, 111 pages. 1973. OM 16,Vol. 335: H. Huck, R R. Roitzsch, U. Simon, W. Vortisch, R R. Walden, B. Wegner und W. Wendland, Beweismethoden der DifferentialundW. geometrie im GroBen. IX, 159 Seiten. 1973. OM 18,Vol. 336: L'Analyse Hsrmonique Harmonique dans Ie Domaine Complexe. Edite par E. J. Akutowicz. VIII, 169 pages. 1973. OM 18,-
