Notes 1: Introduction, linear codes

1 Introduction to Coding TheoryCMU: Spring 2010 Notes 1: Introduction, linear codesJanuary 2010 Lecturer: Venkatesan GuruswamiScribe: Venkatesan GuruswamiThe theory of error-correcting codes and more broadly, information theory, originated in ClaudeShannon s monumental work A mathematical theory of communication, published over 60 yearsago in 1948. Shannon s work gave a precise measure of the information content in the output of arandom source in terms of itsentropy. Thenoiseless coding theoremor the source coding theoreminformally states random variables each with entropyH(X) can be compressed inton(H(X) + ) bits with negligible probability of information loss, and conversely compression inton(H(X) ) bits would entail almost certain information directly relevant to this course is Shannon snoisy coding theoremwhich considered com-munication of a message (say consisting ofkbits that are output by a source coder) on a noisycommunication channel whose behavior is given by a stochastic channel law.

2 The noisy codingtheorem states that every such channel has a precisely defined real number calledcapacitythatquantifies the maximum rate at which reliable communication is possible on that channel. Moreprecisely, given a noisy channel with capacityC, if information is transmitted at rateR(whichmeansk=nRmessage bits are communicated innuses of the channel), then ifR < Cthenexistcoding schemes (comprising an encoder/decoder pair) that guarantee negligible probabilityof miscommunication, whereas ifR > C, then regardless of the coding scheme, the probability oferror at the receiver is bounded below by some constant (which increased asRincreases). (Later,a strong converse to the Shannon coding theorem was proved, which shows that whenR > C, theprobability of miscommunication goes exponentially (ink) to 1.) Shannon s theorem was one ofthe early uses of the probabilistic method; it asserted the existence of good coding schemes at allrates below capacity, but did not give any efficient method to construct a good code or for thatmatter to verify that a certain code was will return to Shannon s probabilistic viewpoint and in particular his noisy coding theorem ina couple of lectures, but we will begin by introducing error-correcting codes from a more combina-torial/geometric viewpoint, focusing on aspects such as the minimum distance of the code.

3 Thisviewpoint was pioneered by Richard Hamming in his celebrated 1950 paper Error detecting anderror correcting codes . The Hamming approach is more suitable for tackling worst-case/adversarialerrors, whereas the Shannon theory handles stochastic/probabilistic errors. This corresponds to arough dichotomy in coding theory results while the two approaches have somewhat different goalsand face somewhat different limits and challenges, they share many common constructions, tools,and techniques. Further, by considering meaningful relaxations of the adversarial noise model orthe requirement on the encoder/decoder, it is possible to bridge the gap between the Shannon andHamming approaches. (We will see some results in this vein during the course.)The course will be roughly divided into the following interrelated parts. We will begin by resultson the existence and limitations of codes , both in the Hamming and Shannon approaches. Thiswill highlight some criteria to judge when a code is good, and we will follow up with severalexplicit constructions of good codes (we will encounter basic finite field algebra during these1constructions).

4 While this part will mostly have a combinatorial flavor, we will keep track ofimportant algorithmic challenges that arise. This will set the stage for the algorithmic componentof the course, which will deal with efficient (polynomial time) algorithms to decode some importantclasses of codes . 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 andprobabilistic error models). codes , and ideas behind some of the good constructions, have also found many exciting ex-traneous applications such as in complexity theory, cryptography, pseudorandomness and explicitcombinatorial constructions. (For example, in the spring 2009 offering of 15-855 (the graduate com-plexity theory course), we covered in detail the Sudan-Trevisan-Vadhan proof of the Impagliazzo-Wigderson theorem that P = BPP under a exponential circuit lower bound for E, based on a highlyefficient decoding algorithm for Reed-Muller codes .)

5 Depending on time, we may mention/discusssome of these applications of coding theory towards the end of the course, though given that thereis plenty to discuss even restricting ourselves to primarily coding-theoretic motivations, this couldbe now look at some simple codes and give the basic definitions concerning codes . But beforethat, we will digress with some recreational mathematics and pose a famous Hat puzzle, whichhappens to have close connections to the codes we will soon introduce (that s your hint, if youhaven t seen the puzzle before!)Guessing hat colorsThe following puzzle made the New York Times in players enter a room and a red or blue hat is placed on each person s head. The color of eachhat is determined by a coin toss, with the outcome of one coin toss having no effect on the person can see the other players hats but not his communication of any sort is allowed, except for an initial strategy session before the gamebegins.

6 Once they have had a chance to look at the other hats, the players must simultaneouslyguess the color of their own hats or pass. The group wins the game if at least one player guessescorrectly and no players guess obvious strategy for the players, for instance, would be for one player to always guess red while the other players pass. This would give the group a 50 percent chance of winning the the group achieve a higher probability of winning (probability being taken over the initialrandom assignment of hat colors)? If so, how high a probability can they achieve?(The same game can be played with any number of players. The general problem is to find astrategy for the group that maximizes its chances of winning the prize.)1 A simple codeSuppose we need to store 64 bit words in such a way that they can be correctly recovered evenif a single bit per word gets flipped. One way is to store each information bit by duplicating it2three times.

7 We can thus store 21 bits of information in the word. This would permit only abouta fraction13of information to be stored per bit of the word. However, it would allow us to correctany single bit flip since the majority value of the three copies of the bit gives the correct value ofthe bit, even if one of the copies is in 1950 introduced a code, now called the Hamming code, which could also correct1-bit errors using fewer redundant (or extra) bits. The code is defined in such a way that a chunkof 4 information bitsx1,x2,x3,x4gets mapped (or encoded ) to a codeword of 7 bits asx1, x2, x3, x4, x2 x3 x4, x1 x3 x4x1 x2 x4,This transformation can equivalently be represented as a mapping fromxtoGx(the operationsare done modulo 2) wherexis the column vector [x1x2x3x4]TandGis the matrix 1 0 0 00 1 0 00 0 1 00 0 0 10 1 1 11 0 1 11 1 0 1 It is easy to verify that two distinct 4-bit vectorsxandyget mapped to codewordsGxandGywhich differ in at least 3 bits.

8 (Definew=x yso thatw6= 0. Now check that for each non-zerow,Gwhas at least 3 bits which are 1.) It follows that the above code can correct all single bit flips,since for any 7-bit vector there is always at most one codeword which can be obtained by a singlebit flip. (As we will see soon, these codes also have the remarkable property that fory {0,1}7which is not a codeword, there is always a codeword which can be obtained by a single bit flip.)2 Some basic definitionsLet us get a few simple definitions out of the 1 (Hamming distance )The Hamming distance between two stringsxandyof thesame length over a finite alphabet , denoted (x,y), is defined as the number of positions at whichthe two strings differ, , (x,y) =|{i|xi6=yi}|. The fractional Hamming distance or relativedistance betweenx,y nis given by (x,y) = (x,y) is trivial to check that the Hamming distance defines a metric on 2 (Hamming weight)The Hamming weight of a stringxover alphabet is definedas the number of non-zero symbols in the string.

9 More formally, the Hamming weight of a stringwt(x) =|{i|xi6= 0}|. Note thatwt(x y) = (x,y).Given a stringx n, theHamming ballor radiusraroundxis the set{y n| (x,y) r}.3 Definition 3 (Code)An error correcting code or block codeCof lengthnover a finite alphabet is a subset of n. The elements ofCare called the codewords inC, and the collection of allcodewords is sometimes called a alphabet ofCis , and if| |=q, we say thatCis aq-ary code. Whenq= 2, we say thatCis a binary code. The lengthnof the codewords ofCis called the block length with a code is also an encoding mapEwhich maps the message setM, identified insome canonical way with{1,2,..,|C|}say, to codewords belonging to n. The code is then theimage of the encoding now define two crucial parameters concerning a code: itsratewhich measures the amount ofredundancy introduced by the code, and itsminimum distancewhich measures the error-resilienceof a code quantified in terms of how many errors need to be introduced to confuse one codewordfor 4 (Rate)The rate of a codeC n, denotedR(C), is defined byR(C) =log|C|nlog| |.

10 Thus,R(C)is the amount of non-redundant information per bit in codewords dimension ofCis defined tolog|C|log| |; this terminology will make sense once we define linearcodes shortly. Note that aq-ary code of dimension`hasq` 5 ( distance )The minimum distance , or simply distance , of a codeC, denoted (C),is defined to be the minimum Hamming distance between two distinct codewords ofC. That is, (C) = minc1,c2 Cc16=c2 (c1,c2).In particular, for every pair of distinct codewords inCthe Hamming distance between them is atleast (C).The relative distance ofC, denoted (C), is the normalized quantity (C)n, wherenis the blocklength ofC. Thus, any two codewords ofCdiffer in at least a fraction (C)of 1 The parity check code, which mapskbits tok+ 1bits by appending the parity of themessage bits, is an example of distance2code. Its rate isk/(k+ 1).Example 2 The Hamming code discussed earlier is an example of distance 3 code, and has rate4 following simple fact highlights the importance of distance of a code for correcting (worst-case)errors.