Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
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