Introduction to coding theory (CMU, Spr 2010)

February 24, 2010

Lecture 12 summary

Filed under: Lecture summary — Venkat Guruswami @ 3:25 pm

Bound on number of zeroes of multivariate polynomials and its implication for distance of Reed-Muller codes; Concatenated codes, their rate and lower bound on their distance; Polynomial time construction of asymptotically good binary codes (by finding binary linear codes of block length m meeting the Gilbert-Varshamov bound in 2^{O(m)} time); the Zyablov trade-off between relative distance and rate.

February 23, 2010

Notes for Lecture 10

Filed under: Announcements — Venkat Guruswami @ 2:37 pm

Some notes on Reed-Solomon and BCH codes (in pdf form) are now posted on the course webpage. I’ll post an expanded version including material from tomorrow’s lecture on the blog when it is ready.

February 21, 2010

Problem set 2

Filed under: Problem sets — Venkat Guruswami @ 11:34 pm

Problem set 2 is now posted. It is due on March 19 (firm deadline), so you have almost four weeks to work on it (one of those weeks is spring break; in any case I encourage you to start thinking about the problems early). Please use the comments section of this post to ask any questions, point out mistakes or typos if you find any, etc.

February 20, 2010

Lecture 11

Filed under: Lecture summary — Venkat Guruswami @ 8:44 am

We had a guest lecture by Madhu Sudan on “Error-correcting codes: Progress and Challenges.” Here are the slides: pdf pptx from his talk.

February 17, 2010

Lecture 10 summary

Filed under: Lecture summary — Venkat Guruswami @ 3:15 pm

Minimum distance property of Reed-Solomon codes; Parity check view of RS codes; RS codes for burst error correction;

Bose, Ray-Chaudhuri, Hocquenghem (BCH) codes: parameters of binary BCH codes and their optimality up to lower order terms; BCH codes as subfield subcodes of RS codes;

Reed-Muller codes and statement of their distance property.

February 16, 2010

Regular lecture tomorrow

Filed under: Announcements — Venkat Guruswami @ 4:51 pm

Tomorrow (Feb 17) we will have a regular lecture, and not a special lecture by Madhu Sudan on progress and challenges in coding theory as earlier announced (this is due to weather related travel disruptions). We might have the special lecture for Friday’s class (Feb 19); I will announce later if that is the case.

February 13, 2010

Upcoming lectures

Filed under: Announcements — Venkat Guruswami @ 9:17 am

Two important announcements about the lectures during the coming two weeks:

  1. Madhu Sudan, who will be visiting CMU this week, has kindly agreed to give a guest lecture in our course on Wednesday, Feb 17th. The topic will roughly be a survey on some progress and challenges ahead in coding theory. It should be very useful and informative for the course, so please attend!
  2. There will be no class on Friday, Feb 26, in view of the CSD open house. Students are encouraged to participate in the afternoon poster sessions or otherwise be involved in the visit day activities instead.

February 12, 2010

Lecture 9 summary

Filed under: Lecture summary — Venkat Guruswami @ 3:31 pm

We finished the proof of the first MRRW bound. We compared the Gilbert-Varshamov, Elias-Bassalygo, and MRRW bounds for the regime \delta \to 1/2, specifically that they give rate bounds of \Omega(\epsilon^2), O(\epsilon) and O(\epsilon^2 \log (1/\epsilon)) for \delta = 1/2-\epsilon. We stated the second MRRW bound.

In preparation for the next segment of the course on constructions of good algebraic codes, we reviewed some basic facts about finite fields. We proved that a univariate polynomial of degree d over any field {\mathbb F} has at most d roots in {\mathbb F}. We concluded with a definition of Reed-Solomon codes as polynomial evaluation codes.

Basics of Finite Fields

Filed under: Lecture notes — Venkat Guruswami @ 11:48 am

In the next segment of the course, we will study explicitly constructed codes, and develop error-correction algorithms for them. Prominent among these will be certain algebraic constructions of codes based on polynomials over finite fields.

It is possible to get quite far treating finite fields as “black-boxes” that allow the field operations to be performed efficiently as atomic steps, along with just one important mantra:

A non-zero polynomial of degree {d} with coefficients from a field {{\mathbb F}} has at most {d} roots in {{\mathbb F}}.

But it is nevertheless desirable to have a good working knowledge of the basics of the theory of finite fields, and we will appeal to some of these results later on for list decoding some powerful algebraic codes. You are likely already familiar with this material from your undergraduate algebra. You can refer to your favorite algebra text for the basic theorems and their proofs, but I wanted to point to some notes that you can turn to if you need a refresher and a convenient reference.

So here are some excellently done notes on finite fields, written by G. David Forney and available on MIT’s OpenCourseWare for the course 6.451 Principles of Digital Communication II. These notes rigorously prove everything that we would need (and more!) from first principles, in a nice sequence.

Collected below are some basic results about finite fields, for quick reference. (I do not recall the definition of fields and the field axioms here.) All these facts are proved in the above linked notes.

  1. For every prime {p}, there is a unique finite field of size {p} that is isomorphic to {{\mathbb F}_p} which is the set {\{0,1,\dots,p-1\}} under mod-{p} addition and multiplication.
  2. For each prime {p}, positive integer {m \ge 1}, and polynomial {g(X)} with coefficients in {{\mathbb F}_p} of degree {m} that is irreducible (in {{\mathbb F}_p[X]}), the set of polynomials in {{\mathbb F}_p[X]} of degree at most {m-1} with addition and multiplication of the polynomials defined modulo {g(X)} is a finite field (denoted {{\mathbb F}_{g(X)}}) with {p^m} elements.
  3. Every finite field is isomorphic to such a field, and therefore must have {p^m} elements for some prime {p} and positive integer {m}.
  4. For every prime {p} and integer {m \ge 1}, there exists an irreducible polynomial {g(X) \in {\mathbb F}_p[X]} of degree {m}. Therefore, there is a finite field with {p^m} elements for every prime {p} and positive integer {m}.
  5. Additively, a finite field with {p^m} elements has the structure of a vector space of dimension {m} over {{\mathbb F}_p}.
  6. The multiplicative group of a finite field (consisting of its non-zero elements) is cyclic. In other words, the non-zero elements of a field {{\mathbb F}} can be written as {\{1,\gamma,\gamma^2,\dots,\gamma^{|{\mathbb F}|-2}\}} for some {\gamma \in {\mathbb F}}.
    • A {\gamma} with such a property is called a primitive element of the field {{\mathbb F}}.
    • A field {{\mathbb F}} has {\varphi(|{\mathbb F}|-1)} primitive elements, where {\phi(\cdot)} is the Euler’s totient function.
  7. All fields of size {p^m} are isomorphic to {{\mathbb F}_{g(X)}} for an arbitrary choice of degree {m} irreducible polynomial {g(X) \in {\mathbb F}_p[X]}.
    The finite field with {p^m} elements is therefore unique up to isomorphism field and will be denoted by {{\mathbb F}_{p^m}}.

    Remark: While one can pick any irreducible {g(X)} to represent the field {{\mathbb F}_{p^m}} as {{\mathbb F}_{g(X)}}, sometimes a special choice can be judicious. For example, the complexity of multiplication is better if {g(X)} is sparse (i.e., has very few non-zero coefficients).

  8. The elements of {{\mathbb F}_{p^m}} are the {p^m} distinct roots of the polynomial {X^{p^m}-X \in {\mathbb F}_p[X]}.
  9. For each {k} dividing {m}, the field {{\mathbb F}_{p^m}} has a unique subfield of size {p^k}, which consists of the roots of the polynomial {X^{p^k}-X}.
  10. The polynomial {X^{p^m}-X} is the product of all monic irreducible polynomials in {{\mathbb F}_p[X]} whose degree divides {m}, with no repetitions.

February 10, 2010

No class today

Filed under: Announcements — Venkat Guruswami @ 12:21 pm

Since some students explicitly asked me, I wanted to make it clear that we do not have a lecture today in view of CMU canceling its classes for the day.

In light of this disruption over the past few days, you can take two extra days for the problem set if you wish, and turn it in by Feb 19 (which will be a firm deadline).

Next Page »

Theme: Rubric. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.