Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Channel Coding Theorem


Inhaltsbereich

Channel Coding Theorem

Lecture Note in German

Plain Text icon codthm.txt — Plain Text, 7 KB (7910 bytes)

File contents

Beweis des Kanalcodierungssatzes (Erreichbarkeit)
-------------------------------------------------

In diesem Abschnitt wollen wir die Erreichbarkeit der Kanalkapazitaet
fuer einen binaeren Kanal doch noch vollstaendig beweisen.  Die
Exposition lehnt sich an die Lecture Note von Wim van Dam und an
[Heise-Quattrocchi] an.

Zur Erinnerung noch einmal die zu beweisende Aussage.

Satz: Fuer jedes R < kappa und epsilon > 0 existiert ein Blockcode C
einer gewissen Laenge n und Rate mindestens R, dessen Verwendung eine
Fehlerwahrscheinlichkeit Pe <= epsilon erlaubt.

Der Beweis dieses Satzes erstreckt sich ueber den gesamten Abschnitt. 

Wir fixieren eine binaere Quelle X, sodass fuer 

                 Y = Ausgabe des Kanals C bei Eingabe X 

gilt: I(X;Y) = kappa. Erinnerung: Die Kanalkapazitaet kappa ist ja als
Maximum der Transinformation I(X;Y) definiert, wenn X ueber alle
binaeren gedaechtnislosen Quellen rangiert. X sei also so gewaehlt,
dass dieses Maximum erreicht wird. Beispielsweise gleichverteiltes X
im Falle eines BSC.

Fuer xs:{0,1}^n schreiben wir p(xs) kurz fuer Pr(X^n = xs), wobei X^n
fuer n unabhaengige Kopien von X steht. Ebenso schreiben wir fuer
ys:{0,1}^n dann p(xs,ys) fuer Pr(X^n=xs und Y^n=ys), wobei Y^n fuer die n
(unabhaengigen) Ausgaben steht, die bei Eingabe von X^n
entstehen. Schliesslich schreiben wir p(ys) := sum_xs p(xs,ys) fuer die
entsprechende Randverteilung. Man beachte, dass im allgemeinen nicht
gilt p(xs,ys) = p(xs)p(ys), denn dann waere ja kappa=0 und es koennte
ueberhaupt gar keine Information ueber den Kanal uebertragen werden.


Gemeinsam Typische Mengen
-------------------------

Def (gemeinsam typische Menge): Fuer epsilon>0 und n:N umfasst die
gemeinsam typische Menge A_epsilon^(n) alle Paare (xs,ys) mit
xs,ys:{0,1}^n fuer die gilt: 

i)  |-1/n*log p(xs) - H(X)| < epsilon 
ii) |-1/n*log p(ys) - H(Y)| < epsilon 
iii)|-1/n*log p(xs,ys) - H(X,Y)| < epsilon

Die Intuition fuer die Klausel |-1/n*log p(xs) - H(X)| < epsilon ist
wie folgt: ein Wort x_1...x_n ist "typisch", wenn der Mittelwert der
-log(p(x_i)) ueber i=1..n nahe beim Erwartungswert von -log p(X)
liegt, welcher ja gerade gleich H(X) ist. Die zweite und dritte
Klausel motivieren sich analog. 

Lemma 1: Sei epsilon > 0 gegeben. Fuer hinreichend grosses n gilt: 

Pr((xs,ys) : A_epsilon^{(n)}) >= 1-epsilon

D.h., die Wahrscheinlichkeit dafuer, dass (xs,ys) gemeinsam typisch ist, ist >= 1-epsilon.

Beweis: Die gemeinsame Entropie H(X,Y) ist der Erwartungswert der
Zufallsvariablen -log p(X^n,Y^n). Nach dem Gesetz der grossen Zahlen gilt
also 

1 <- Pr(|1/n sum_{j=1}^n -log p(x_i,y_i) - H(X,Y)| < epsilon) = 
Pr(|-1/n log p(xs,ys) - H(X,Y)| < epsilon). 

Also ist Pr(|-1/n log p(xs,ys) - H(X,Y)| < epsilon) > 1-delta fuer
beliebiges delta und hinr gr n. Ebenso erhaelt man 

Pr(|-1/n log p(xs) - H(X)| < epsilon) > 1-delta 
Pr(|-1/n log p(ys) - H(Y)| < epsilon) > 1-delta 

Fuer delta=epsilon/3 ergibt ich dann die Aussage des Lemmas []
 
Lemma 2: Fuer epsilon>0 und hinr gr n gilt 

(1-epsilon) * 2^{n*(H(X,Y)-epsilon)} <= |A_epsilon^{(n)}| <= 
2^{n*(H(X,Y)+epsilon)}. 

Beweis: 1 = sum_{xs,ys}p(xs,ys) >= sum_{(xs,ys):A_epsilon^{(n)}} p(xs,ys) >= 
     |A_epsilon^{(n)}|*2^{-n*(H(X,Y)+epsilon)}
nach Definition von A_epsilon^{(n)}
und daraus die rechte Ungleichung. 

Fuer hinreichend grosses n gilt nach Lemma 1: 

1-epsilon <= sum_{(xs,ys):A_epsilon^{(n)} p(xs,ys) <= 
            |A_epsilon^{(n)}| * 2^{-n*(H(X,Y)-epsilon)}

und daraus die zweite Ungleichung. []

Lemma 3: Fuer alle n gilt sum_{(xs,ys):A_epsilon^{(n)}}p(xs)*p(ys) <= 
2^{-n*(I(X;Y)-3*epsilon)}. 

Beweis: Fuer (xs,ys):A_epsilon^{(n)} gilt nach Definition 
   p(xs)*p(ys) <= 2^{-n*(H(X)+H(Y)-2*epsilon)}. Die Behauptung folgt
dann aus Lemma 2 und der Definition I(X;Y)=H(X)+H(Y)-H(X,Y). []


Stochastische Codes
-------------------

Def.: Ein stochastischer Code der Rate R und der Laenge n ist eine
(nicht notwendigerweise injektive) Funktion

                        x : {1..2^(nR)} -> {0,1}^n

Im Gegensatz zu einem Blockcode der Rate R und Laenge n ist hier also
die Zuordnung der Codewoerter x(w) zu "Botschaften" w:{1..2^(nR)}
fixiert. Darueberhinaus koennen sich bei einem stochastischen Code
Codewoerter wiederholen, es kann also passieren, dass x(w)=x(w'),
obwohl w =/= w'. 


Definition (Shannon - Decodierer): Sei ein stochastischer Code x der
Rate R und Laenge n gegeben und epsilon > 0 gegeben. Der Shannon
Decodierer fuer x (und epsilon) arbeitet wie folgt:

Eine vorgelegte Ausgabe  ys:{0,1}^n wird zu w decodiert, falls 

(x(w),ys) : A_epsilon^(n) gilt und ausserdem fuer kein weiteres w'=/=w
gilt (x(w'),ys) : A_epsilon^(n). 

In allen anderen Faellen signalisiert der Shannon Decodierer einen
Fehler; formal, indem er 0 zurueckliefert. 

Def. (Fehlerwahrscheinlichkeit): Zu gegebenem stochastischem Code x
(und epsilon) und Botschaft w definieren wir die Wahrscheinlichkeit
eines Uebertragungsfehlers Pe(x,w,epsilon) als die Wahrscheinlichkeit
dafuer, dass der Shannon Decodierer
angewandt auf die bei Eingabe x(w) resultierende Ausgabe ys ein
Ergebnis ungleich w liefert. 

Bemerkung: Falls x(w)=x(w') und w=/=w', so ist Pe(x,w,epsilon)=1. 

Wir konstruieren jetzt (zu gegebenem n und epsilon und R) einen
stochastischen Code x zufaellig (daher der Name), indem wir 
2^(nR) mal mithilfe der Quelle X jeweils n Symbole generieren lassen
und aus diesen das jeweilige Codewort x(w) zusammensetzen. Die
Wahrscheinlichkeit dafuer, dass ein bestimmter stochastischer Code x 
entsteht, ist dann 

              Pr(x) = prod_{w:{1..2^(nR)} p(x(w))  


Hauptlemma 4: Sei R < I(X;Y)-3*epsilon. Die mittlere
Fehlerwahrscheinlichkeit 

        sum_x sum_w Pr(x) * 2^(-nR) * Pe(x,w,epsilon) 

geht fuer n -> oo gegen Null. 

Wir stellen den Beweis des Hauptlemmas zunaechst zurueck und leiten
aus dem Hauptlemma den Satz her: 

Sei also nun eine Rate R_0 < I(X;Y)=kappa und eine Fehlerwahrscheinlichkeit
epsilon_0 vorgegeben. Wir waehlen R und epsilon so, dass R_0 < R <
I(X;Y) - 3*epsilon und epsilon <= epsilon_0 und epsilon < 1. 
Mithilfe des Hauptlemmas koennen wir nun n so waehlen, dass  

    sum_x sum_w Pr(x) * 2^(-nR) * Pe(x,w,epsilon) <= epsilon/2

und ausserdem R-1/n > R_0

wird. Das bedeutet, dass zumindest ein stochastischer Code x
existieren muss, fuer den gilt 

          sum_w  2^(-nR) * Pe(x,w,epsilon) <= epsilon/2

Nun kann es hoechstens 2^(nR) / 2 Botschaften w geben mit
Pe(x,w,epsilon) > epsilon, denn waeren es mehr, so wuerde der obige
Mittelwert selbst unter der optimistischen Annahme, dass die
Fehlerwahrscheinlichkeit bei den uebrigen 2^(nR)/2 Botschaften Null
ist, doch > epsilon/2. Streichen wir also diese maximal 2^(nR)/2
schlechten Botschaften, so verbleibt eine Menge C der Groesse
mindestens 2^(nR) / 2 = 2^(n * (R-1/n)) > 2^{n*R_0}, deren Elemente eine
Fehlerw. <= epsilon <= epsilon_0 besitzen. Man beachte, dass bei der
Streichungsaktion insbesondere alle Dubletten entfernt wurden, da
diese ja eine Fehlerw. von 1 besitzen (da epsilon < 1)
vorausgesetzt wurde). 

Diese Menge C ist der erwuenschte Blockcode!  []

Beweis des Hauptlemmas 4: 

sum_x sum_w Pr(x) * 2^(-nR) * Pe(x,w,epsilon) = 
sum_w 2^(-nR) * sum_x Pr(x) * Pe(x,w,epsilon) =
                \___________ _______________/
                            v
                    unabh. von w
 
sum_x Pr(x) * Pe(x,1,epsilon) <= 

sum_x Pr(x) * Pr((x(1),ys) not in A_epsilon^(n)) + 
sum_x Pr(x) * sum_{w=2}^{2^nR}Pr((x(w),ys) in A_epsilon^(n)) /* 2
						Moegl. fuer Fehler */ 

Nun gilt 

sum_x Pr(x) * Pr((x(1),ys) not in A_epsilon^(n)) = 
Pr((xs,ys) not in A_epsilon^(n)) -> 0 wg Lemma 1. 

Weiterhin gilt 

sum_x Pr(x) * sum_{w=2}^{2^nR}Pr((x(w),ys) in A_epsilon^(n)) = 
(2^{nR}-1) * sum_{(xs,ys):A_epsilon^{(n)}}p(xs)*p(ys)  /* da ja x(1) und x(w) unabhaengig gewaehlt
sind */ 
<= (2^{nR}-1) * 2^{-(n * (I(X;Y)-3*epsilon))}

Ist also R < I(X;Y)-3*epsilon, so geht auch dieser Term gegen Null. []

Document Actions


Funktionsleiste