Capacity of Bsc I (X;Y)=Hb(Po)-Hb(Pe) H(P)=P log(1/P)+(1-P)log(1/1-P Hb(P)<=1 with equality if P=1/2 C=max po ((X; Y)=Hb(Po)-H(Pe))=1-Hb(Pe Hb(P) C=1-Hb(Pe 1/2 C=0 when P= 1/2 and c 1 when P=0 or P =1
Eytan Modiano Slide 6 Capacity of BSC I (X;Y) = Hb (P0) - Hb(Pe) • Hb(P) = P log(1/P) + (1-P) log(1/ 1-P) – Hb(P) <= 1 with equality if P=1/2 C = max P0 {I (X;Y) = Hb (P0) - Hb(Pe)} = 1 - Hb(Pe) C = 0 when Pe = 1/2 and C = 1 when Pe = 0 or Pe=1 0 1/2 1 P Hb(P) 1 0 1/2 1 Pe C = 1 - Hb(Pe) 1
Channel Coding Theorem(Claude Shannon) Theorem For allr<c and e>o there exists a code of rate r whose error probability <e e can be arbitrarily small Proof uses large block size n as n -oo 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 to achieving capacity Converse of Coding Theorem For all codes of rate R>C, EEo>0, such that the probability of error is always greater than Eo For code rates greater than capacity, the probability of error is bounded away from 0
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 to achieving 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 bounded away from 0
Channel coding Block diagram Source Source h chanelle Modulator Channel Sink Source Channel decoder decoder KH Demod K
Eytan Modiano Slide 8 Channel Coding • Block diagram Source Source encoder Channel encoder Modulator Channel Demod Channel decoder Source decoder Sink
pproaches 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 10→110010 011→011100 11→111001 An(n, k binary block code is a collection of 2k binary n-tuples(n>k) n= block length k= number of data bits n-k= number of checked bits Rek/n=code rate
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