Introduction to Coding Theory Lecture Notes

1 Introduction to Coding TheoryLecture Notes Yehuda LindellDepartment of Computer ScienceBar-Ilan University, IsraelJanuary 25, 2010 AbstractThese are Lecture Notes for an advanced undergraduate (and beginning graduate) course in CodingTheory in the Computer Science Department at Bar-Ilan University. These Notes contain the technicalmaterial covered but do not include much of the motivation and discussion that is given in the is therefore not intended for self study, and is not a replacement for what we cover in class. This is afirst draft of the Notes and they may therefore contain errors. These Lecture Notes are based on Notes taken by Alon Levy in 2008. We thank Alon for his Basic Definitions.. A Probabilistic Model.. 32 Linear Basic Definitions.

2 Code Weight and Code distance .. Generator and Parity-Check Matrices.. Equivalence of Codes.. Encoding Messages in Linear Codes.. Decoding Linear Codes.. Summary.. 123 The Main Question of Coding Theory .. The Sphere-Covering Lower Bound.. The hamming (Sphere Packing) Upper Bound.. Perfect Codes.. The Binary hamming Code.. Decoding the Binary hamming Code.. Extended Codes.. Golay Codes.. Summary - Perfect Codes.. The Singleton Bound and MDS Codes.. The Reed-Solomon Code.. A Digression Coding Theory and Communication Complexity.. The Gilbert-Varshamov Bound.. The Plotkin Bound.. The Hadamard Code.. The Walsh-Hadamard Code.. 274 Asymptotic Bounds and Shannon s Background: Information/Entropy.

3 Asymptotic Bounds on Codes.. Shannon s Theorem.. Channel Capacity (Shannon s Converse).. 385 Constructing Codes from Other General Rules for Construction.. The Reed-Muller Code.. 406 Generalized Reed-Solomon Codes (GRS) Definition.. Polynomial representation of GRS.. Decoding GRS Codes.. Step 1: Computing the Syndrome.. Step 2 The Key Equation of GRS Decoding.. Step III - Solving the Key Equations.. The Peterson-Gorenstein-Zierler GRS Decoding Algorithm.. 50ii7 Asymptotically Good Background.. Concatenation of Codes.. The Forney Code.. Efficient Decoding of the Forney Code.. A Probabilistic Decoding Algorithm.. A Deterministic Decoding Algorithn.. 568 Local Locally decoding Hadamard codes.

4 579 List Decoding5910 Hard Problems in Coding The Nearest Codeword Problem and NP-Completeness.. Hardness of Approximation.. 6211 CIRC: Error Correction for the CD-ROM67iiiiv1 IntroductionThe basic problem of Coding Theory is that of communication over an unreliable channel that results in errorsin the transmitted message. It is worthwhile noting that all communication channels have errors, and thuscodes are widely used. In fact, they are not just used for network communication, USB channels, satellitecommunication and so on, but also in disks and other physical media which are also prone to addition to their practical application, Coding Theory has many applications in the Theory of computerscience. As such it is a topic that is of interest to both practitionersand check:Consider the following code: For anyx=x1.

5 , xndefineC(x) = ni=1xi. This codecan detect a single error because any single change will result in the parity check bit being code cannot detect two errors because in such a case one codeword will be mapped to code:Letx=x1, .. , xnbe a message and letrbe the number of errors that we wish tocorrect. Then, defineC(x) =xkxk kx, where the number of times thatxis written in the outputis 2r+ 1. Decoding works by taking then-bit stringxthat appears a majority of the time. Note thatthis code correctsrerrors because anyrerrors can change at mostrof thexvalues, and thus ther+1values remain untouched. Thus the originalxvalue is the repetition code demonstrates that the Coding problem can be solved in principal. However, theproblem with this code is that it is extremely main questions of Coding Theory :1.

6 Construct codes that can correct a maximal number of errorswhile using a minimal amount of redun-dancy2. Construct codes (as above) with efficient encoding and Basic DefinitionsWe now proceed to the basic definitions of {a1, .. , aq}be analphabet; we call theaivaluessymbols. Ablock codeCof lengthnoverAis a subset ofAn. A vectorc Cis called acodeword. The number of elements inC, denoted|C|,is called thesizeof the code. A code of lengthnand sizeMis called an(n, M) code overA={0,1}is called abinary codeand a code overA={0,1,2}is called aternary will almost exclusively talk about sending a codewordc and then finding the codewordcthat was originally sent given a vectorxobtained by introducing errors intoc. This may seem strange atfirst since we ignore the problem of mapping a messageminto a codewordcand then findingmagain fromc.

7 As we will see later, this is typically not a problem (especially for linear codes) and thus the mapping oforiginal messages to codewords and back is not a rate of a code is a measure of its efficiency. Formally:Definition an(n, M)-code over an alphabet of sizeq. Then, therateofCis defined byrate(C) = that it is possible to specifyMmessages using logqMsymbols when there is no , the longer thatnis, the more wasteful the code (in principal, logqMsymbols suffice and then logqMadditional symbols are redundancy). Observe that the codeC=Aqhas an optimal rate of 1, but cannotdetect or correct any errors. In contrast, the repetition codehas rate ofn(2r+ 1)n=12r+ , the rate of the repetition code tends to 0 as the number of errors to be corrected general, we will assume that it is more likely to have less errors thanmore , we will assume an upper bound on the number of errors that occur (if we are wrong, then anincorrect message may be received).

8 This worst case approachto Coding is intuitively appealing withinitself, in our opinion. Nevertheless, it is closely connected to a simple probabilistic model where errors areintroduced into the message independently for each symbol and with a fixed probabilityp <1/2. See thetextbooks for more on this topic. In order to talk about the number of errors we introduce the notion ofHamming distance :Definition , .. , xnandy=y1, .. , yn. Then, for everyidefined(xi, yi) = 1xi6=yi0xi=yiand defined(x, y) =nXi=1d(xi, yi).We stress that the hamming distance is not dependent on the actual values ofxiandyibut only if theyare equal to each other or not functiondis a metric. That is, for everyx, y, z d(x, y) (x, y) = 0if and only ifx= (x, y) =d(y, x) (x, z) d(x, y) +d(y, z)(triangle inequality)We leave the proof of this as a simple exercise (first prove the proposition forn= 1).

9 We now describe thebasic rule for decoding:Definition a code of lengthnover an alphabetA. Thenearest neighbor decodingrule statesthat everyx Anis decoded tocx Cthat is closest tox. That is,D(x) =cxwherecxis such thatd(x, cx) = minc C{d(x, c)}. If there exist more than onecat this minimal distance , thenDreturns .Code distance and error detection and , a code is better if all the codewordsare far apart. We formalize this notion a code. Thedistanceof the code, denotedd(C), is defined byd(C) = min{d(c1, c2)|c1, c2 C, c16=c2}An(n, M)-code of distancedis called an(n, M, d)-code. The valuesn, M, dare called theparametersof what we have discussed above, the aim of Coding Theory isto construct a code with a shortn,and largeMandd; equivalently, the aim is to construct a code with a rate that is as close to 1 as possibleand withdas large as possible.

10 We now show a connection between the distanceof a code and the possibilityof detecting and correcting a code of lengthnover alphabetA. Cdetectsuerrors if for every codewordc Cand everyx Anwithx6=c, it holds that ifd(x, c) uthenx / C. Ccorrectsverrors if for every codewordc Cand everyx Anit holds that ifd(x, c) vthennearest neighbor decoding following theorem is easily proven and we leave it as an easy A codeCdetectsuerrors if and only ifd(C)> u. A codeCcorrectsverrors if and only ifd(C) 2v+ A Probabilistic ModelThe model that we have presented until now is a worst-case model . Specifically, what interests us is theamount of errors that we can correct and we are not interested inhow or where these errors occur. This isthe model that we will refer to in most of this course and was the model introduced by hamming .