1 Hamming Distance - Ryerson University

1 Linear CodesP. Danziger1 Hamming DistanceThroughout this documentFmeans the binary could define dot product, magnitude and Distance in analogy withRn, but in this case wewould get all vectors having length 0 or 1, not very interesting. Instead we use a different definitionof magnitude and Distance , which is much more useful in this 1 ( Hamming Distance )Given two vectorsu,v Fnwe define thehamming distancebetweenuandv,d(u,v), to be the number of places the Hamming Distance between two vectors is the number of bits we must change to changeone into the the Distance between the vectors 01101010 and differ in four places, so the Hamming distanced(01101010,11011011) = 2 (Weight)Theweightof a vectoru Fnisw(u) =d(u,0), the Distance ofuto thezero weight of a vector is equal to the number of 1 s in it. The weight may be thought of as themagnitude of the the weight of contains 6 ones, sow(11011011) = Error Correcting CodesError correcting codes are used in many places, wherever there is the possibility of errors duringtransmission.

2 Some examples are NASA probes (Galileo), CD players and the Ethernet assume that the original message consists of a series of bits, which can be split into equal sizeblocks and that each block is of lengthn, a member usual process consists of the original blockx Fnthis is then encoded by someencodingfunctiontou Fn+kwhich is then sent across some (noisy) channel. At the other end the receivedvaluev Fn+kis decode by means of the correspondingdecoding functionto somey Encode u Transmit v Decode yIf there are no errors in the channelu=vandx= CodesP. DanzigerDefinition 3 (Code)Acodeis a setC Fm, wherem=n+k, together with a 1-1 encodingtransformationT:Fn FmwithRan(T) =Cand an onto decoding transformationD:C practice the domain ofDis often larger thanCto allow for the smallest Hamming Distance between two codewords in a codeC,d= minu,v C{d(u,v)}.

3 Thus to change one codeword to another requires at leastdbit changes. ThenCcan detect up tod 1 errors, since anyd 1 transmission errors cannot change one codeword to code is characterized by the three numbers:n- the original message length (bits),k- the number of bits added in encoding, andd- the minimum Distance between thatuwas sent andvwas received andd(u,v) (d 1)/2, ie. less than (d 1)/2 errorsoccurred. Then, the Distance ofvto any codeword other thanu,w Csay, is greater than (d 1)/2,sinced(u,w) dby the definition ofd. Thusuis the nearest codeword tov, the number of bitchanges required to get fromutov(the number of errors in the channel) is less than the numberof errors required to get from any other codeword tov. We correctvtou, soCcan correct up tot= (d 1)/2 (3 Repetition Code)n= 1, each bit is a block so a message is either 0 or 2, som= 3,C={000,111}.

4 Encode: (T)0 0001 : (D)001,010,100,000 0110,101,011,111 3, so this code can detect up to 2 errors (d 1) and correct up to 1 ((d 1)/2).In general we wish to keepkas low as possible - we want to add as few extra bits as possible, whilstgettingdas high as possible, to enable us to detect as many errors as possible. For a given value ofdwe may measure the efficiency of a code by the information rateR=n/(n+k). The repetitioncode above hasd= 3 with information rateR= 1/3, the encoded message is three times as longas the original, which is not very 4 (Linear Codes)A code is called alinear codeif the transformationTis a matrixtransformation. In this case there will be an(n+k) nzero-one matrixGsuch thatT(x) =Gx,Gis called thegeneratorof the 1 1,Gis row equivalent to a matrix withnpivots. In particular it is always possible toreduce the firstnrows ofGto then nidentity matrix,In.

5 Thus we will assume thatG=(InA),whereAis ak nmatrix. In this case if the original message isx, then the encoded messageGx=(xp), wherep=Ax. The components ofpare called theparity bits, the matrixAis calledtheparity matrixand the equationsAxare called theparity CodesP. DanzigerNote that the columns ofGare codewords, the first column is the encoding of , the secondof , the third , etc. In fact the columns ofGform a basis ((n,k,d) = (4,3,3) Hamming code)This code adds three parity bits to each nibble and corrects up to 1 error. This code hasd= 3with information rateR= 4/7, thus the encoded message is 7/4 times as long as the original, muchbetter than the 3 repetition code 1 0 0 00 1 0 00 0 1 00 0 0 11 1 0 11 0 1 10 1 1 1 ,soA= 1 1 0 11 0 1 10 1 1 1 To encodex= 0110 we computeGx= 0110110, 110 are the parity Parity Check MatricesWe wish to be able to decode messages, check for errors and correct them quickly.

6 One commonmethod isSyndrome Decodingwhich relies on the parity check matrix for a 5 (Parity Check Matrix)Given a linear codeCwith generatorG, ann (n+k)matrixHis called aparity check matrix forCifv Cif and only ifHv= 6 Given a linear codeCwith generatorG=(InA), then the corresponding parity checkmatrix isH= (A|Ik). FurtherHG=O, whereOis then nzero :LetC,GandHbe as given above, we must show thatv C Hv=0.( ) Assumev C, sincevis a codeword it must be the encoding of some messagex Fn, somex Fn. SoHv=HGx= (A|Ik)(InA)x= (A+A)x=Ox=0.(Remember thatAis ak nzero one matrix and all addition is binary, soA+A=O.)Note that we have also shown thatHG=O.( ) Assumev Fn+kandHv=0. Writev=(v1v2), wherev1 Fnandv2 Fk. Now0=Hv= (A|Ik)(v1v2)=Av1+v23 Linear CodesP. DanzigerSoAv1+v2=0, Thusv=(v1Av1)=(InA)v1=Gv1and sov can also calculatedfrom the parity check matrix.

7 If there aredcolumns ofHwhose sum is0,but no set ofd 1 columns ofHsum to0then the code has minimum distanced. Every setofd 1 column vectors fromHis linearly independent, but there is some set ofdcolumn vectorsofHwhich is linearly of binary matrices is fast, especially if implemented in hardware. Thus we mayquickly detect errors in an incoming transmissionvby computingHv, if it is non-zero an error hasoccurred. If no error has occurred the original message may be recovered by stripping off the Syndrome DecodingLetCbe a linear code with generatorG, parity check matrixHand minimum distanced. Lett= (d 1)/2, then we may correct up toterrors. Supposeu=Gxis sent, and up toterrors occur,thenv=Gx+ewill be received, wheree Fn+khas a 1 in each position that was changed in thetransmission ofu, we are assumingw(e) t. Consider the action ofHon the received vector:Hv=H(Gx+e) =HGx+He=Ox+He=He= can calculateHvon the received vector to get the values=He.

8 We would like to invert theaction ofHonsto retrievee, butHis not invertible (it s not even square). However, we knowthatw(e) tand so it is feasible to do the inversion for such vectors by means of a lookup table,called the syndrome Fn+kiss=He Fk, ifeis a codeword its syndrome will be0. We keep a tableof the syndromes of alle Fn+kwithw(e) t, allewith less thantones. If we receivev,we calculates=Hv, then the corrected codeword will bev+e, whereehas syndromesfrom theprecalculated The 3 repetition code given above is a linear code withG= 111 , soA=(11), andH=(1 1 01 0 1),d= 3, andt= 1. We now calculate the syndrome table, 001,010,100 arethe vectors inF3with one CodesP. DanzigerThus if we receive 101, calculate the syndromeH 101 =(10). 10 corresponds to 010from the table, so the corrected codeword is 101 + 010 = 111 and the message was The (4,3,3) Hamming code given above hasG= 1 0 0 00 1 0 00 0 1 00 0 0 11 1 0 11 0 1 10 1 1 1 ,soA= 1 1 0 11 0 1 10 1 1 1 so the parity check matrixH= (A|I3) = 1 1 0 1 1 0 01 0 1 1 0 1 00 1 1 1 0 0 1.

9 The syndrome table ises=He000000000000000010010000010010000 0100100000100011100100000110100000101100 0000110 Thus if we receive 1001100, we calculate the syndromeH(1001100)T= (101)T, which corre-sponds to 0100000 from the table, so the corrected codeword is 1001100 + 0100000 = 1101100,and the message was Exercises1. Find the weight of each of the following vectors, find the Hamming Distance between the givenpairs.(a) 0011, 1111 F4(b) 0011, 1100 F4(c) 11011001, 10011001 F8(d) 00111001, 00001001 F85 Linear CodesP. Danziger2. What is the maximum weight of a vector inFn?What is the maximum Hamming Distance between two vectors inFn?3. A common code is theParity Check Code, in this kind of code one bit is added to each messageword,x Fn. This bit is 0 ifw(x) is even and 1 ifw(x) is odd. The Parity Check Code is alinear code.(a) What isdfor this code?

10 (b) What is the information rateRfor this code in terms ofn?(c) If the original message is 8 bits (n= 8) find the generatorGfor this code. What is thecorresponding parity matrixA?4. The extended Hamming code has generating matrixG= 1 0 0 00 1 0 00 0 1 00 0 0 11 1 1 01 1 0 11 0 1 10 1 1 1 (a) Find the encodings of 0011 and 1010.(b)i. What is the size of each (unencoded) message (n)?ii. How many check bits are added (k)?iii. What is the information rateR? 3 for this code, what is the error correction ratet?v. Considering your answer to part 4(b)iii, which is the better code, this one or theHamming code given in the text?(c) What is the parity matrixA?(d) Find the parity check matrixH.(e) Compile the syndrome table for this code.(f) In each case below the received vector is given, use H and your table to find what 11011100ii.