296.3:Algorithms in the Real WorldGeneral ModelApplicationsBlock CodesHierarchy of CodesBinary CodesHypercube InterpretationError Detection with Parity BitError Correcting One Bit MessagesExample of (6,3,3)2 systematic codeError Correcting Multibit MessagesHamming Codes: EncodingHamming Codes: DecodingHamming CodesLower bound on parity bitsSlide 16Lower Bounds: a side noteLinear CodesSlide 19Generator and Parity Check MatricesAdvantages of Linear CodesExample and “Standard Form”Relationship of G and HProof that H is a Parity Check MatrixThe d of linear codesDual CodesNASA Mariner:How to find the error locations296.3 Page1296.3:Algorithms in the Real WorldError Correcting Codes I– Overview– Hamming Codes– Linear Codes296.3 Page2General Modelcodeword (c)codernoisychanneldecodermessage (m)message or errorcodeword’ (c’)Errors introduced by the noisy channel:•changed fields in the codeword (e.g. a flipped bit)•missing fields in the codeword (e.g. a lost byte). Called erasuresHow the decoder deals with errors.•error detection vs. •error correction296.3 Page3Applications•Storage: CDs, DVDs, “hard drives”,•Wireless: Cell phones, wireless links•Satellite and Space: TV, Mars rover, …•Digital Television: DVD, MPEG2 layover•High Speed Modems: ADSL, DSL, ..Reed-Solomon codes are by far the most used in practice, including pretty much all the examples mentioned above.Algorithms for decoding are quite sophisticated.296.3 Page4Block CodesEach message and codeword is of fixed size = codeword alphabet k =|m| n = |c| q = ||C  n (codewords)(x,y) = number of positions s.t. xi  yid = min{(x,y) : x,y C, x  y}s = max{(c,c’)} that the code can correctCode described as: (n,k,d)qcodeword (c)codernoisychanneldecodermessage (m)message or errorcodeword’ (c’)296.3 Page5Hierarchy of CodescycliclinearBCHHamming Reed-SolomonThese are all block codes (operate on fixed-length strengths).Bose-Chaudhuri-HochquenghemC forms a linear subspace of n of dimension kC is linear andc0c1c2…cn-1 is a codeword impliesc1c2…cn-1c0 is a codeword296.3 Page6Binary CodesToday we will mostly be considering  = {0,1} and will sometimes use (n,k,d) as shorthand for (n,k,d)2In binary x,y) is often called the Hamming distance296.3 Page7Hypercube InterpretationConsider codewords as vertices on a hypercube.000001111100101011110010codewordThe distance between nodes on the hypercube is the Hamming distance . The minimum distance is d.001 is equidistance from 000, 011 and 101.For s-bit error detection d  s + 1For s-bit error correction d  2s + 1d = 2 = min distancen = 3 = dimensionality2n = 8 = number of nodes296.3 Page8Error Detection with Parity BitA (k+1,k,2)2 codeEncoding: m1m2…mk  m1m2…mkpk+1 where pk+1 = m1  m2  …  mkd = 2 since the parity is always even (it takes two bit changes to go from one codeword to another).Detects one-bit error since this gives odd parityCannot be used to correct 1-bit error since any odd-parity word is equal distance  to k+1 valid codewords.296.3 Page9Error Correcting One Bit MessagesHow many bits do we need to correct a one-bit error on a one-bit message? 000001111100101011110010000111102 bits0 -> 00, 1-> 11(n=2,k=1,d=2)3 bits0 -> 000, 1-> 111(n=3,k=1,d=3)In general need d  3 to correct one error. Why?296.3 Page10Example of (6,3,3)2 systematic codeDefinition: A Systematic code is one in which the message appears in the codewordmessagecodeword000 000000001 001011010 010101011 011110100 100110101 101101110 110011111 111000Same in any bit of message implies two bits of difference in extra codeword columns.296.3 Page11Error Correcting Multibit MessagesWe will first discuss Hamming CodesDetect and correct 1-bit errors.Codes are of form: (2r-1, 2r-1 – r, 3) for any r > 1 e.g. (3,1,3), (7,4,3), (15,11,3), (31, 26, 3), …which correspond to 2, 3, 4, 5, … “parity bits” (i.e. n-k)The high-level idea is to “localize” the error.Any specific ideas?296.3 Page12Hamming Codes: Encodingm3m5m6m7m11m10m9p8p0m15m14m13m12Localizing error to top or bottom half 1xxx or 0xxxp8 = m15  m14  m13  m12  m11  m10  m9Localizing error to x1xx or x0xxm3p4m5m6m7m11m10m9p8p0m15m14m13m12p4 = m15  m14  m13  m12  m7  m6  m5Localizing error to xx1x or xx0xp2m3p4m5m6m7m11m10m9p8p0m15m14m13m12p2 = m15  m14  m11  m10  m7  m6  m3Localizing error to xxx1 or xxx0p1p2m3p4m5m6m7m11m10m9p8p0m15m14m13m12p1 = m15  m13  m11  m9  m7  m5  m3296.3 Page13Hamming Codes: DecodingWe don’t need p0, so we have a (15,11,?) code.After transmission, we generateb8 = p8  m15  m14  m13  m12  m11  m10  m9b4 = p4  m15  m14  m13  m12  m7  m6  m5b2 = p2  m15  m14  m11  m10  m7  m6  m3b1 = p1  m15  m13  m11  m9  m7  m5  m3With no errors, these will all be zeroWith one error b8b4b2b1 gives us the error location.e.g. 0100 would tell us that p4 is wrong, and 1100 would tell us that m12 is wrongp1p2m3p4m5m6m7m11m10m9p8p0m15m14m13m12296.3 Page14Hamming CodesCan be generalized to any power of 2–n = 2r – 1 (15 in the example)–(n-k) = r (4 in the example)–d = 3 (discuss later)–Can correct one error, but can’t tell difference between one and two!–Gives (2r-1, 2r-1-r, 3) codeExtended Hamming code–Add back the parity bit at the end–Gives (2r, 2r-1-r, 4) code–Can correct one error and detect 2–(not so obvious)296.3 Page15Lower bound on parity bitsHow many nodes in hypercube do we need so that d = 3?Each of the 2k codewords eliminates n neighbors plus itself, i.e. n+1 )1(log)1(log2)1(222nknnknnknIn previous hamming code 15  11 +  log2(15+1)  = 15Hamming Codes are called perfect codes since they match the lower bound exactlyneed296.3 Page16Lower bound on parity bitsWhat about fixing 2 errors (i.e. d=5)?Each of the 2k codewords eliminates itself, its neighbors and its neighbors’ neighbors, giving:1log2)2/)1(1(log2)2/)1(1(222nknnnknnnnknGenerally to correct s errors:211nn)211(log2snnnkn 296.3 Page17Lower Bounds: a side noteThe lower bounds assume random placement of bit errors.In practice errors are likely to be less than random, e.g. evenly