16.36: Communication Systems Engineering Lectures 12/13: Channel Capacity and Coding Eytan Modiano
Eytan Modiano Slide 1 16.36: Communication Systems Engineering Lectures 12/13: Channel Capacity and Coding Eytan Modiano
Channel Coding When transmitting over a noisy channel, some of the bits are received with errors Example: Binary Symmetric Channel (BSc) Pe= probability oferror Q: How can these errors be removed? A: Coding: the addition of redundant bits that help us determine what was sent with greater accuracy
Eytan Modiano Slide 2 Channel Coding • When transmitting over a noisy channel, some of the bits are received with errors Example: Binary Symmetric Channel (BSC) • Q: How can these errors be removed? • A: Coding: the addition of redundant bits that help us determine what was sent with greater accuracy 1 1 0 0 1-Pe 1-Pe Pe Pe = Probability of error
Example Repetition code Repeat each bit n times(n-odd Input Code 000.0 Decoder If received sequence contains n/2 or more 1s decode as a 1 and o otherwise Max likelihood decoding P(error 1 sent)=P(error 0 sent PI more than n /2 bit errors occur] ∑|,P(-Py m/2(
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 P P i n n e i e n i − = − ∑/ ( ) 2 1
Repetition code, cont For Pe<1/2, plerror) is decreasing in n for any e, 3 n large enough so that p(error)<e Code Rate: ratio of data bits to transmitted bits For the repetition codeR= 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 rek/n Goal: for a desired error probability, E, find the highest rate code that can achieve p(error) <e
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) < ε
Channel Capacity The capacity of a discrete memoryless channel is given by, C=max 1(r; Y) Channel Example: Binary Symmetric Channel (BSc) P0 P1=1 IX; Y)=H (Y-H YX=H(X)-H(XY H(X×Y)=H(XY=0)P(Y=0)+H(XY=1)P(Y=1) H(XY0)=H(XY=1=Pelog(1/Pe)(1-Pe)log(1/1-P)=Hb(Pe) H(XY=Hb(Pe=>I(; Y)=H(X)-Hb(Pe) H(X)=Po log(1/P0)+(1-Po)log(11-P0)=Hb(po) I(X; Y)=Hb (Po)-Hb(Pe
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) = Pelog(1/Pe) + (1-Pe)log(1/ 1-Pe) = Hb(Pe) H (X|Y) = Hb(Pe) => I(X;Y) = H(X) - Hb(Pe) H (X) = P0 log (1/P0) + (1-P0) log (1/ 1-P0) = Hb(p0) => I (X;Y) = Hb (P0) - Hb(Pe) C IXY = max ( ; ) p x( ) X Channel Y 1 1 0 0 1-Pe 1-Pe Pe P0 P1 =1-P0