ERRORCONTROLCODING.PPTVIP

* * * * * ERROR CONTROL CODING Basic concepts Classes of codes: Block Codes Linear Codes Cyclic Codes Convolutional Codes * Basic Concepts Example: Binary Repetition Codes (3,1) code: 0 == 000 1 == 111 Received: 011. What was transmitted? scenario A: 111 with one error in 1st location scenario B: 000 with two errors in 2nd 3rd locations. Decoding: P(A) = (1- p)2 p P(B) = (1- p) p2 P(A) P(B) (for p0.5) Decoding decision: 011 == 111 * Probability of Error After Decoding (3,1) repetition code can correct single errors. In general for a tc-error correcting code: Bit error probability = [for the (3,1) code, Pb = Pu] Gain: For a BSC with p= 10-2, Pb=3x10-4. Cost: Expansion in bandwidth or lower rate. * Hamming Distance Def.: The Hamming distance between two codewords ci and cj, denoted by d(ci,cj), is the number of components at which they differ. dH(011,000) = 2 dH [C1,C2]=WH(C1+C2) dH (011,111) = 1 Therefore 011 is closer to 111. Maximum Likelihood Decoding reduces to Minimum Distance Decoding, if the priory probabilities are equal (P(0)=P(1)) * Geometrical IllustrationHamming Cube * 000 111 001 011 101 100 110 010 Error Correction and Detection Consider a code consisting of two codewords with Hamming distance dmin. How many errors can be detected? Corrected? # of errors that can be detected = td= dmin -1 # of errors that can be corrected = tc = In other words, for t-error correction, we must have dmin = 2tc + 1 * Error Correction and Detection (cont’d) Example: dmin = 5 Can correct two errors Or, detect four errors Or, correct one error and detect two more errors. In general d min= 2tc + td + 1 * d min 2tc + 1 d min tc + td + 1 Minimum Distance of a Code Def.: The minimum distance of a code C is the minimum Hamming distance between any two different codewords. A code with minimum distance dmin can correct all error patterns up to and including t-error patterns, where dmin = 2tc + 1 It may be able to