Eytan Modiano Slide 1 16.36: Communication Systems Engineering Lectures 12/13: Channel Capacity and Coding Eytan Modiano Eytan Modiano Slide 2 Channel Coding ? When transmitting over a noisy channel, some of the bits arereceived with errorsExample : Binary Symmetric Channel (BSC) ? Q: How can these errors be removed? ? A: Coding: the addition of redundant bits that help us determinewhat was sent with greater accuracy 1 1 00 1-Pe 1-Pe Pe Pe = Probability of error Eytan Modiano Slide 3 Example (Repetition code) Repeat each bit n times (n-odd) Input Code 0 000 ……..0 1 11.. ……..1 Decoder:? If received sequence contains n/2 or more 1 ’s decode as a 1 and 0 otherwise – Max likelihood decoding P ( error | 1 sent ) = P ( error | 0 sent ) = P[ more than n / 2 bit errors occur ] = n i PP in n e i e ni ?? ? ?? ? ? = ?? ? ∑ / () 2 1 Eytan Modiano Slide 4 Repetition code, cont. ? For P e < 1/2, P(error) is decreasing in n – ???? for any εεεε , ???? n large enough so that P (error) < εεεε Code Rate : ratio of data bits to transmitted bits – For the repetition code R = 1/n – To send one data bit, must transmit n channel bits “bandwidth expansion ” ? In general, an (n,k) code uses n channel bits to transmit k data bits – Code rate R = k / n ? Goal: for a desired error probability, εεεε , find the highest rate code that can achieve p(error) < εεεε Eytan Modiano Slide 5 Channel Capacity ? The capacity of a discrete memoryless channel is given by, – Example : Binary Symmetric Channel (BSC) I(X;Y) = H (Y) - H (Y|X) = H (X) - H (X|Y)H (X|Y) = H (X|Y=0)*P(Y=0) + H (X|Y=1)*P(Y=1)H (X|Y=0) = H (X|Y=1) = P e log (1/P e ) + (1- P e )log(1/ 1- P e ) = H b (P e ) H (X|Y) = H b (P e ) => I(X;Y) = H(X) - H b (P e ) H (X) = P 0 log (1/P 0 ) + (1-P 0 ) log (1/ 1-P 0 ) = H b (p 0 ) => I (X;Y) = H b (P 0 ) - H b (P e ) CI X Y px = max ( ; ) () Channel X Y 1 1 00 1-Pe 1-Pe Pe P 0 P 1 =1-P 0 Eytan Modiano Slide 6 Capacity of BSC I (X;Y) = H b (P 0 ) - H b (P e ) ? H b (P) = P log(1/P) + (1-P) log(1/ 1-P) – H b (P) <= 1 with equality if P=1/2 C = max P0 {I (X;Y) = H b (P 0 ) - H b (P e )} = 1 - H b (P e ) C = 0 when P e = 1/2 and C = 1 when P e = 0 or P e =1 1 0 1/2 P H b (P) 1 1 0 1/2 Pe C = 1 - H b (Pe) 1 Eytan Modiano Slide 7 Channel Coding Theorem (Claude Shannon) Theorem: For all R < C and εεεε > o; there exists a code of rate R whose error probability < εεεε – εεεε can be arbitrarily small – Proof uses large block size n as n →→→→ ∞∞∞∞ capacity is achieved ? In practice codes that achieve capacity are difficult to find – The goal is to find a code that comes as close as possible toachieving capacity ? Converse of Coding Theorem: – For all codes of rate R > C, ???? εεεε 0 > 0, such that the probability of error is always greater than εεεε 0 For code rates greater than capacity, the probability of error is boundedaway from 0 Eytan Modiano Slide 8 Channel Coding ? Block diagram Source Source encoder Channelencoder Modulator Channel Demod Channeldecoder Source decoder Sink Eytan Modiano Slide 9 Approaches to coding ? Block Codes – Data is broken up into blocks of equal length – Each block is “ mapped ” onto a larger block Example: (6,3) code, n = 6, k = 3, R = 1/2 000 →→→→ 000000 100 →→→→ 100101 001 →→→→ 001011 101 →→→→ 101110 010 →→→→ 010111 110 →→→→ 110010 011 →→→→ 011100 111 →→→→ 111001 ? An (n,k) binary block code is a collection of 2 k binary n- tuples (n>k) – n = block length – k = number of data bits – n-k = number of checked bits – R = k / n = code rate Eytan Modiano Slide 1 0 Approaches to coding ? Convolutional Codes – The output is provided by looking at a sliding window of input Delay Delay + + + C i C i+1 U K C (2K) = U (2K) U (2K-2) , C (2K+1) = U (2K+1) U (2K) U (2K-1) + + + + mod ( 2 ) addition ( 1+1=0 ) Eytan Modiano Slide 1 1 Block Codes ? A block code is systematic if every codeword can be broken into adata part and a redundant part – Previous (6,3) code was systematic Definitions : ? Given X ∈∈∈∈ {0,1} n , the Hamming Weight of X is the number of 1 ’s in X ? Given X, Y in {0,1} n , the Hamming Distance between X & Y is the number of places in which they differ, ? The minimum distance of a code is the Hamming Distance between the two closest codewords : d min = min { d H (C 1 ,C 2 )} C 1 ,C 2 ∈∈∈∈ C dX YX Y Weight X Y XY x y xy xy Hi i n i nn (, ) ( ) [, , , ] =⊕ = + += ⊕ ⊕ ⊕ = ∑ 1 11 2 2 L Eytan Modiano Slide 1 2 Decoding ? r may not equal to u due to transmission errors ? Given r how do we know which codeword was sent? Maximum likelihood Decoding : Map the received n- tuple r into the codeword C that maximizes, P { r | C was transmitted } Minimum Distance Decoding (nearest neighbor) Map r to the codeword C such that the hamming distance betweenr and C is minimized (I.e., min d H (r,C)) ???? For most channels Min Distance Decoding is the same as Max likelihood decoding Channel u r Eytan Modiano Slide 1 3 Linear Block Codes ? A (n,k) linear block code (LBC) is defined by 2 k codewords o f length n C = { C 1 ….C m } ? A (n,k) LBC is a K-dimensional subspace of {0,1} n – (0…0) is always a codeword – If C 1 ,C 2 ∈∈∈∈ C, C 1 +C 2 ∈∈∈∈ C ? Theorem: For a LBC the minimum distance is equal to the minweight ( W min ) of the code W min = min (over all Ci) Weight ( C i ) Proof : Suppose d min = d H (C i ,C j ), where C 1 ,C 2 ∈∈∈∈ C d H (C i ,C j ) = Weight ( C i + C j ), but since C is a LBC then C i + C j is also a codeword Eytan Modiano Slide 1 4 Systematic codes Theorem: Any (n,k) LBC can be represented in Systematic form where: data = x 1 ..x k , codeword = x 1 ..x k c k+1 .. x n – Hence we will restrict our discussion to systematic codes only ? The codewords corresponding to the information sequences: e 1 = (1,0,..0), e 2 =(0,1,0..0), e k = (0,0,..,1) for a basis for the code – Clearly, they are linearly independent – K linearly independent n- tuples completely define the K dimensional subspace that forms the code Information sequence Codeword e 1 = (1,0,..0) g 1 = (1,0,..,0, g (1,k+1) …g (1,n) ) e 2 =(0,1,0..0) g 2 = (0,1,..,0, g (2,k+1) …g (2,n) ) e k = (0,0,..,1) g k = (0,0,..,k, g (k,k+1) …g (k,n) ) ? g 1 , g 2 , …,g k form a basis for the code Eytan Modiano Slide 1 5 The Generator Matrix ? For input sequence x = (x 1 ,…,x k ): C x = xG – Every codeword is a linear combination of the rows of G – The codeword corresponding to every input sequence can be derived from G – Since any input can be represented as a linear combination of thebasis (e 1 ,e 2 ,…, e k ), every corresponding codeword can be represented as a linear combination of the corresponding rows of G ? Note: x 1 C 1 , x 2 C 2 => x 1 +x 2 C 1 +C 2 G ggg gg g gggg k nn kk n = ?? ???? ?? ???? = ?? ???? ?? ???? 12 11 12 1 21 2 1 M L M Eytan Modiano Slide 1 6 Example ? Consider the (6,3) code from earlier:100 →→→→ 100101; 010 →→→→ 010111; 001 →→→→ 001011 Codeword for (1,0,1) = (1,0,1)G = (1,0,1,1,1,0) G = ?? ??? ?? ??? 100 1 0 1 01 011 1 00101 1 GI P KK x n K = ?? ??? ?? ??? = ? () I KxK identity matrix K Eytan Modiano Slide 1 7 The parity check matrix HP I n T nK = ?? ??? ?? ??? =? ? () ( I K)x(n - K) identity matrix (n - K ) H = ?? ??? ?? ??? 110 1 0 0 011 0 10 111 0 0 1 Example: Now, if c i is a codework of C then, cH i T = v 0 ? “C is in the null space of H”? Any codeword in C is orthogonal to the rows of H Eytan Modiano Slide 1 8 Decoding ? v = transmitted codeword = v 1 … v n ? r = received codeword = r 1 … r n ? e = error pattern = e 1 … e n ? r = v + e ? S = rH T = Syndrome of r = (v+e)H T = vH T + eH T = eH T ? S is equal to ‘ 0’ if and only if e ∈∈∈∈ C – I.e., error pattern is a codeword ? S ≠≠≠≠ 0 => error detected ? S = 0 => no errors detected (they may have occurred and notdetected) ? Suppose S ≠≠≠≠ 0, how can we know what was the actual transmitted codeword ? Eytan Modiano Slide 1 9 Syndrome decoding ? Many error patterns may have created the same syndrome For error pattern e 0 => S 0 = e 0 H T Consider error pattern e 0 + c i (c i ∈∈∈∈ C) S’ 0 = (e 0 + c i) )H T =e 0 H T + c i H T = e 0 H T = S 0 ? So, for a given error pattern, e 0 , all other error patterns that can be expressed as e 0 + c i for some c i ∈∈∈∈ C are also error patterns with the same syndrome ? For a given syndrome, we can not tell which error pattern actuallyoccurred, but the most likely is the one with minimum weight – Minimum distance decoding ? For a given syndrome, find the error pattern of minimum weight(e min ) that gives this syndrome and decode: r ’ = r + e min Eytan Modiano Slide 2 0 Standard Array ? Row 1 consists of all M codewords ? Row 2 e 1 = min weight n- tuple not in the array – I.e., the minimum weight error pattern ? Row i, e i = min weight n- tuple not in the array ? All elements of any row have the same syndrome – Elements of a row are called “ co-sets” ? The first element of each row is the minimum weight error patternwith that syndrome – Called “co-set leader” CC C Syndrome ee C e C S eC eC S eS M MM nK nK 12 11 2 1 1 22 2 2 21 21 L M ++++ ? ? ?? () () M = 2 K Eytan Modiano Slide 2 1 Decoding algorithm ? Receive vector r 1) Find S = rH T = syndrome of r 2) Find the co-set leader e, corresponding to S3) Decode: C = r+e? “Minimum distance decoding ” – Decode into the codeword that is closest to the received sequence Eytan Modiano Slide 2 2 Example (syndrome decoding) ? Simple (4,2) code Data codeword 00 0000 01 0101 10 1010 11 1111 Standard array 0000 0101 1010 1111 Syndrome 1000 1101 0010 0111 10 0100 0001 1110 1011 0 1 1100 1001 0110 0011 1 1 Suppose 0111 is received, S = 10, co-set leader = 1000 Decode: C = 0111 + 1000 = 1111 G HH T = ?? ? ?? ? = ?? ? ?? ? = ?? ???? ?? ???? 10 10 01 01 10 10 01 01 10011001 Eytan Modiano Slide 2 3 Minimum distance decoding ? Minimum distance decoding maps a received sequence onto the nearestcodeword ? If an error pattern maps the sent codeword onto another valid codeword , that error will be undetected (e.g., e3) – Any error pattern that is equal to a codeword will result in undetected errors ? If an error pattern maps the sent sequence onto the sphere of anothercodeword , it will be incorrectly decoded (e.g., e2) c 5 c 1 c 2 c 3 c 4 undetectederror incorrect decoding e1 e2 e3 correctly decoded Eytan Modiano Slide 2 4 Performance of Block Codes ? Error detection: Compute syndrome, S ≠≠≠≠ 0 => error detected – Request retransmission – Used in packet networks ? A linear block code will detect all error patterns that are notcodewords ? Error correction: Syndrome decoding – All error patterns of weight < d min /2 will be correctly decoded – This is why it is important to design codes with large minimumdistance ( d min ) – The larger the minimum distance the smaller the probability ofincorrect decoding Eytan Modiano Slide 2 5 Hamming Codes ? Linear block code capable of correcting single errors – n = 2 m - 1, k = 2 m -1 -m (e.g., (3,1), (7,4), (15,11) … ) – R = 1 - m/(2 m - 1) => very high rate – d min = 3 => single error correction ? Construction of Hamming codes – Parity check matrix (H) consists of all non-zero binary m- tuples Example: (7,4) hamming code (m=3) HG = ?? ??? ?? ??? = ?? ???? ?? ???? 10 111 0 0 110 1 010 011 1 001 1000110010001100 10 10 1 0001111 ,