Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Introduction to Coding Theory

CMU: Spring 2010

Notes 1: Introduction, linear codes
January 2010
Lecturer: Venkatesan Guruswami

Scribe: Venkatesan Guruswami

The theory of error-correcting codes and more broadly, information theory, originated in Claude
Shannon’s monumental work A mathematical theory of communication, published over 60 years
ago in 1948
...
The noiseless coding theorem or the source coding theorem
informally states that n i
...
d
...

More directly relevant to this course is Shannon’s noisy coding theorem which considered communication of a message (say consisting of k bits that are output by a source coder) on a noisy
communication channel whose behavior is given by a stochastic channel law
...
More
precisely, given a noisy channel with capacity C, if information is transmitted at rate R (which
means k = nR message bits are communicated in n uses of the channel), then if R < C then
exist coding schemes (comprising an encoder/decoder pair) that guarantee negligible probability
of miscommunication, whereas if R > C, then regardless of the coding scheme, the probability of
error at the receiver is bounded below by some constant (which increased as R increases)
...
) Shannon’s theorem was one of
the early uses of the probabilistic method; it asserted the existence of good coding schemes at all
rates below capacity, but did not give any efficient method to construct a good code or for that
matter to verify that a certain code was good
...
This
viewpoint was pioneered by Richard Hamming in his celebrated 1950 paper Error detecting and
error correcting codes
...
This corresponds to a
rough dichotomy in coding theory results – while the two approaches have somewhat different goals
and face somewhat different limits and challenges, they share many common constructions, tools,
and techniques
...
(We will see some results in this vein during the course
...
We will begin by results
on the existence and limitations of codes, both in the Hamming and Shannon approaches
...
While this part will mostly have a combinatorial flavor, we will keep track of
important algorithmic challenges that arise
...
This in turn will enable us to approach the absolute limits of error-correction
“constructively,” via explicit coding schemes and efficient algorithms (for both worst-case and
probabilistic error models)
...
(For example, in the spring 2009 offering of 15-855 (the graduate complexity theory course), we covered in detail the Sudan-Trevisan-Vadhan proof of the ImpagliazzoWigderson theorem that P = BPP under a exponential circuit lower bound for E, based on a highly
efficient decoding algorithm for Reed-Muller codes
...

We now look at some simple codes and give the basic definitions concerning codes
...

15 players enter a room and a red or blue hat is placed on each person’s head
...

Each person can see the other players’ hats but not his own
...
Once they have had a chance to look at the other hats, the players must simultaneously
guess the color of their own hats or pass
...

One obvious strategy for the players, for instance, would be for one player to always guess ”red”
while the other players pass
...

Can the group achieve a higher probability of winning (probability being taken over the initial
random assignment of hat colors)? If so, how high a probability can they achieve?
(The same game can be played with any number of players
...
)

1

A simple code

Suppose we need to store 64 bit words in such a way that they can be correctly recovered even
if a single bit per word gets flipped
...
We can thus store 21 bits of information in the word
...
However, it would allow us to correct
any single bit flip since the majority value of the three copies of the bit gives the correct value of
the bit, even if one of the copies is flipped
...
The code is defined in such a way that a chunk
of 4 information bits x1 , x2 , x3 , x4 gets mapped (or “encoded”) to a “codeword” of 7 bits as
x1 , x2 , x3 , x4 , x2 ⊕ x3 ⊕ x4 , x1 ⊕ x3 ⊕ x4 x1 ⊕ x2 ⊕ x4 ,
This transformation can equivalently be represented as a mapping from x to Gx (the operations
are done modulo 2) where x is the column vector [x1 x2 x3 x4 ]T and G is the matrix


1 0 0 0
0 1 0 0


0 0 1 0


0 0 0 1


0 1 1 1


1 0 1 1
1 1 0 1
It is easy to verify that two distinct 4-bit vectors x and y get mapped to codewords Gx and Gy
which differ in at least 3 bits
...
Now check that for each non-zero
w, Gw has at least 3 bits which are 1
...
(As we will see soon, these codes also have the remarkable property that for y ∈ {0, 1}7
which is not a codeword, there is always a codeword which can be obtained by a single bit flip
...

Definition 1 (Hamming distance) The Hamming distance between two strings x and y of the
same length over a finite alphabet Σ, denoted ∆(x, y), is defined as the number of positions at which
the two strings differ, i
...
, ∆(x, y) = |{i|xi 6= yi }|
...

It is trivial to check that the Hamming distance defines a metric on Σn
...
More formally, the Hamming weight of a string
wt(x) = |{i|xi 6= 0}|
...

Given a string x ∈ Σn , the Hamming ball or radius r around x is the set {y ∈ Σn | ∆(x, y) ≤ r}
...
The elements of C are called the codewords in C, and the collection of all
codewords is sometimes called a codebook
...
When q = 2, we say that C
is a binary code
...

Associated with a code is also an encoding map E which maps the message set M, identified in
some canonical way with {1, 2,
...
The code is then the
image of the encoding map
...

Definition 4 (Rate) The rate of a code C ⊆ Σn , denoted R(C), is defined by
R(C) =

log |C|

...

The dimension of C is defined to

log |C|
log |Σ| ;

this terminology will make sense once we define linear

codes shortly
...

Definition 5 (Distance) The minimum distance, or simply distance, of a code C, denoted ∆(C),
is defined to be the minimum Hamming distance between two distinct codewords of C
...

c1 ,c2 ∈C
c1 6=c2

In particular, for every pair of distinct codewords in C the Hamming distance between them is at
least ∆(C)
...
Thus, any two codewords of C differ in at least a fraction δ(C) of positions
...
Its rate is k/(k + 1)
...

The following simple fact highlights the importance of distance of a code for correcting (worst-case)
errors
...

Lemma 6 For a code, the following statements are equivalent:
4

1
...

2
...

3
...

4
...
(In the erasure model, some symbols are
erased and the rest are intact, and we know the locations of the erasures
...
)

3

Linear codes

A general code might have no structure and not admit any representation other than listing the
entire codebook
...
Many of the important and widely used codes are linear
...
Throughout, we will denote by Fq
the finite field with q elements, where q is a prime power
...
For now, we can safely
think of q as a prime, in which case Fq is just {0, 1,
...
)
Definition 7 (Linear code) If Σ is a field and C ⊂ Σn is a subspace of Σn then C is said to be
a linear code
...
, ck where k is the dimension of the subspace
...
We can write these
vectors in matrix form as the columns of a n × k matrix
...

Definition 8 (Generator matrix and encoding) Let C ⊆ Fnq be a linear code of dimension k
...

q
The generator matrix G provides a way to encode a message x ∈ Fkq (thought of as a column vector)
as the codeword Gx ∈ C ⊆ Fnq
...

Comment: Many coding texts define the “transpose” version, where the rows of the k×n generator
matrix span the code
...

Note that a linear code admits many different generator matrices, corresponding to the different
choices of basis for the code as a vector space
...
Further, it the code has minimum distance d, it will be referred to as an [n, k, d]q code
...

5

Example 3 Some simple examples of binary linear codes:
• The binary parity check code: This is an [n, n − 1, 2]2 code consisting of all vectors in Fn2 of
even Hamming weight
...

• The Hamming code discussed above is a [7, 4, 3]2 linear code
...
e
...

c∈C
c6=0

Exercise 2 (Systematic or standard form) Let C be an [n, k]q linear code
...

A generator matrix in the form [Ik | G0 ]T is said to be in systematic form
...

Thus, after permuting coordinates if needed, every linear code admits a systematic encoding
...


3
...


of full

In other words, C is the nullspace of H
...

A linear code can thus be compactly represented by either its generator matrix or its parity check
matrix
...

Lemma 9 If H is the parity check matrix of a linear code C, then ∆(C) equals the minimum
number of columns of H that are linearly dependent
...
2

Hamming code revisited

The Hamming code is best understood by the structure of its parity check matrix
...

We defined the CHam = [7, 4, 3]2 Hamming code

1
0

0

G=
0
0

1
1
If we define the matrix

using generator matrix

0 0 0
1 0 0

0 1 0

0 0 1

...
Note that H has
a rather nice structure: its columns are the integers 1 to 7 written in binary
...
We know by the distance property
of CHam that c is uniquely determined by y
...

A more slick (and faster) way to correct y is as follows
...
Note that Hy = H(c + ei ) =
Hc + Hei = Hei = the ith column of H
...

Definition 10 (Syndrome) The vector Hy is said to be the syndrome of y
...
This matrix must contain e1 through er , which are the binary
representations of all powers of two from 1 to 2r−1 , and thus has full row rank
...


to be the binary code with parity check matrix Hr
...

(r)

Proof: Since Hr has rank r, it follows that the dimension of CHam equals r
...
The former follows since the columns of Hr are all distinct
...

Despite its simplicity, the Hamming code is amazing in that it is optimal in the following sense
...

n+1

(1)

(r)

It follows that the Hamming code CHam has the maximum possible number of codewords (and thus
has largest rate) amongst all binary codes of block length 2r − 1 and minimum distance at least 3
...
For
each c ∈ C, define its neighborhood N (c) = {y ∈ {0, 1}n | ∆(y, c) ≤ 1} of all strings that differ in
at most one bit from c
...
Therefore
[
X
2n ≥ |
N (c)| =
|N (c)| = |C| · (n + 1)
c∈C

c∈C
(r)

giving the desired upper bound on |C|
...

The obvious generalization of the above argument to arbitrary distances d gives the following bound
...
We will meet this
bound again and also discuss some more sophisticated combinatorial bounds a few lectures down
...
Then
2n
|C| ≤ P d−1
b 2 c
i=0



...
Hamming balls of radius
n
b d−1
2 c around the codewords must cover each point in {0, 1} exactly once
...
(There is no way to
pack balls in Euclidean space in such a way, with no “holes” in between!) Codes which meet the
bound (2) are therefore called perfect codes
...
It turns out that perfect codes are a rare phenomenon
...
The following defines
it as a so-called “cyclic” code: Gol23 consists of (c0 , c1 ,
...


3
...

Definition 15 (Dual code) If C ⊆ Fnq is a linear code, then its dual, denoted C ⊥ , is a linear
code over Fq defined as
C ⊥ = {z ∈ Fnq | hz · ci = 0 ∀ c ∈ C}
...

Using Exercise 3, verify the following
...
If C is an [n, k]q linear code, then C ⊥ is an [n, n − k]q linear code
...
(C ⊥ )⊥ = C
...
If H is a parity check matrix for C, then H T is a generator matrix for C ⊥
...

Unlike vector spaces over R, where the dual (or orthogonal complement) W ⊥ of a subspace W ⊆ Rn
satisfies W ∩ W ⊥ = {0} (and W + W ⊥ = Rn ), for subspaces of Fnq , C and C ⊥ can intersect nontrivially
...

Exercise 5 For every even n, give an example of a self-dual binary linear code of block length n
...
We will now discuss the dual of the Hamming code, a
code called the Hadamard code which has been highly influential and played a fundamental role in
the computer-scientists’ study of coding theory
...
4

Hadamard code
(r)

The dual of the Hamming code CHam has as generator matrix Gr = (Hr )T , which is a (2r − 1) × r
matrix whose rows are all non-zero bit vectors of length r
...
The Hadamard code is obtained by adding the all-zeroes row to Gr
...
Thus the encoding map for the Hadamard
r
code encodes x ∈ Fr2 by a string in F22 consisting of the dot product hx, ai for every a ∈ Fr2
...

We note that the Hadamard code is the most redundant linear code in which no two codeword
symbols are equal in every codeword
...

The q-ary Hadamard code of dimension r has distance (1 − 1/q)q r
...
e
...

Assume for definiteness that x1 = 1
...
The proof for the q-ary case is similar
...
Thus the relative distance of Hadamard codes is
optimal, but their rate is (necessarily) rather poor
...
Linear algebraically, it is simply the subspace spanned by the Hadamard code and the
all 1’s vector (i
...
, the union of the Hadamard code H and its coset H + 1)
...
, mr , mr+1 to (m1 a1 +· · ·+mr ar +mr+1P
)a∈Fr2 , or equivalently the evaluations (M (a))a∈Fr2
of the r-variate polynomial M (X1 , X2 ,
...
It is a [2r , r + 1, 2r−1 ]2 code
...


Code families and Asymptotically good codes
The Hamming and Hadamard codes exhibit two extremes in the trade-off between rate and distance
...

Hadamard codes have (optimal) relative distance 1/2, but their rate approaches 0
...

To formulate this question formally, and also because our focus in this course is on the asymptotic
behavior of codes for large block lengths, we consider code families
...
Most of the constructions of codes we will encounter in this book will
naturally belong to an infinite family of codes that share the same general structure and properties
(and it is usually these asymptotic properties that will often guide our constructions)
...
Code
families where qi = q for all i for some fixed q will be of special interest (and turn out to be more

10

challenging to understand and construct)
...

The notions of rate and relative distance naturally extend to code families
...

i
ni
The (relative) distance of a family of codes C equals


∆(Ci )
δ(C) = lim inf

...
e
...

In this terminology, the question raised above concerning (binary) codes with both good rate and
good distance, can be phrased as: “Are there asymptotically good binary code families?”
For a code family, achieving a large rate and large relative distance are naturally conflicting codes,
and there are fundamental trade-offs between these
...
A
good deal is known about the existence (or even explicit construction) of good codes and as well as
limitations of codes, but the best possible asymptotic trade-off between rate and relative distance
for binary codes remains a fundamental open question

---