Difference between revisions of "Channel Coding/Bounds for Block Error Probability"

From LNTwww
Line 282: Line 282:
 
[[Aufgaben:1.16 Schranken für AWGN|A1.16 Schranken für AWGN]]
 
[[Aufgaben:1.16 Schranken für AWGN|A1.16 Schranken für AWGN]]
  
−
[[Zusatzaufgaben:1.16 Schranken für Q(x)]]
+
[[Aufgaben:1.16Z_Schranken_für_Q(x)|Zusatzaufgabe 1.16: Schranken für Q(x)]]
  
 
{{Display}}
 
{{Display}}

Revision as of 20:51, 2 January 2018

  1. Channel Coding
  2. Binäre Blockcodes zur Kanalcodierung
  3. Bounds for Block Error Probability

Distanzspektrum eines linearen Codes


Wir gehen weiterhin von einem linearen und binären (n,k)–Blockcode C aus. Ein wesentliches Ziel des Codedesigns ist es, die Blockfehlerwahrscheinlichkeit Pr(u_≠v_)=Pr(z_≠x_) möglichst gering zu halten. Dies erreicht man unter anderem dadurch, dass

  • die minimale Distanz dmin zwischen zwei Codeworten x_ und x_′ möglichst groß ist, so dass man bis zu t=⌊(dmin−1)/2⌋ Bitfehler richtig korrigieren kann;
  • gleichzeitig die minimale Distanz dmin   ⇒   worst–case möglichst selten auftritt, wenn man alle zulässigen Codeworte berücksichtigt.

Definition:  Wir benennen die Anzahl der Codeworte x_′∈C mit der Hamming–Distanz i vom betrachteten Codewort x_ des gleichen Codes C mit Wi(x_), wobei gilt:

Wi(x_)=|{x_,x_′∈C|dH(x_,x_′)=i}|.
  • Die Betragsstriche kennzeichnen hierbei die Anzahl der Codeworte x_′, die die Bedingung dH(x_,x_′)=i erfüllen.
  • Man bezeichnet diesen Wert auch als Vielfachheit (englisch: Multiplicity).


Hamming–Distanzen zwischen allen Codeworten

Beispiel 1:  Wir betrachten den (5,2)–Blockcode C mit der Generatormatrix

G=(1011001011).

Die Tabelle zeigt die Hamming–Distanzen zwischen allen Codeworten x_i zu den Bezugsworten x_0, ... , x_3.

Man erkennt, dass unabhängig vom Bezugswort x_i gilt:

W0=1,W1=W2=0,
W3=2,W4=1
⇒dmin=3.


Nicht nur in diesem Beispiel, sondern bei jedem linearen Code ergeben sich für jedes Codewort die gleichen Vielfachheiten Wi. Da zudem das Nullwort 0_=(0,0, ...,0) Bestandteil eines jeden linearen Binärcodes ist, lässt sich die obige Definition auch wie folgt formulieren:

Definition:  Das Distanzspektrum eines linearen binären (n,k)–Blockcodes ist die Menge {Wi} mit i=0,1, ... , n. Hierbei gibt Wi die Anzahl der Codeworte x_∈C mit Hamming–Gewicht wH(x_)=i an.

Oft beschreibt man die Menge {Wi} auch als Polynom mit einer Pseudovariablen X:

{Wi}⇔W(X)=n∑i=0Wi⋅Xii=W0+W1⋅X+W2⋅X2+...+Wn⋅Xn.

Man bezeichnet W(X) auch als Gewichtsfunktion (englisch: Weight Enumerator Function, WEF).


Beispielsweise lautet die Gewichtsfunktion des (5,2)–Codes C={(0,0,0,0,0),(0,1,0,1,1),(1,0,1,1,0),(1,1,1,0,1)} von Beispiel 1:

W(X)=1+2⋅X3+X4.

Wie aus der Tabelle seiner Codeworte hervorgeht, erhält man für den (7,4,3)–Hamming–Code:

W(X)=1+7⋅X3+7⋅X4+X7.

Die Überführung des Distanzspektrums {Wi} in die Gewichtsfunktion W(X) bietet zudem bei manchen Aufgabenstellungen große numerische Vorteile. Ist beispielsweise die Weight Enumerator Function W(X) eines (n,k)–Blockcodes C bekannt, so gilt für den hierzu dualen (n,n−k)–Code CDual:

WDual(X)=(1+X)n2k⋅W(1−X1+X).

Beispiel 2:  Gesucht ist die Gewichtsfunktion W(X) des Single Parity–check Codes mit n=6, k=5   ⇒   SPC (6, 5). Man erhält diese durch Vergleich aller 25=32 Codeworte mit dem Nullwort:

WSPC(6,5)(X)=1+15⋅X2+15⋅X4+X6.

Unter Berücksichtigung obiger Gleichung kommt man sehr viel schneller zum gleichen Ergebnis:

  • Der zu SPC (6, 5) duale Code ist der Repetition Code RC (6, 1) mit nur zwei Codeworten (0,0,0,0,0,0) und (1,1,1,1,1,1):
WRC(6,1)(X)=1+X6.
  • Daraus folgt für die Gewichtsfunktion des SPC (6, 5) nach obiger Gleichung mit k=1:
WSPC(6,5)(X)=(1+X)621⋅W[1+((1−X)/(1+X))6]=1/2⋅[(1+X)6+(1−X)6]=1+15⋅X2+15⋅X4+X6.


Union Bound der Blockfehlerwahrscheinlichkeit


Wir betrachten wie im Beispiel 1 zum Distanzspektrum] den (5,2)–Blockcode C=(x_0,x_1,x_2,x_3) und setzen voraus, dass das Codewort x_0 gesendet wurde. Die Grafik verdeutlicht den Sachverhalt).

Zur Herleitung der Union Bound

Im fehlerfreien Fall würde dann der Codewortschätzer z_=x_0 liefern. Andernfalls käme es zu einem Blockfehler (das heißt z_≠x_0 und dementsprechend v_≠u_0 mit der Wahrscheinlichkeit

Pr(Blockfehler)=Pr([x_0↦x_1]∪[x_0↦x_2]∪[x_0↦x_3]).

Das Ereignis „Verfälschung von x_0 nach x_1” tritt für ein gegebenes Empfangswort y_ entsprechend der Maximum–Likelihood–Entscheidungsregel (block–wise ML) genau dann ein, wenn für die bedingte Wahrscheinlichkeitsdichtefunktion gilt:

[x_0↦x_1]⟺f(x_0|y_)<f(x_1|y_).

Da [x_0↦x_1], [x_0↦x_2], [x_0↦x_3]nicht notwendigerweise disjunkte Ereignisse sind (die sich somit gegenseitig ausschließen würden), ist die Wahrscheinlichkeit der Vereinigungsmenge kleiner oder gleich der Summe der Einzelwahrscheinlichkeiten:

Pr(Blockfehler)≤Pr[x_0↦x_1]+Pr[x_0↦x_2]+Pr[x_0↦x_3].

Man nennt diese obere Schranke für die (Block–)Fehlerwahrscheinlichkeit die Union Bound. Diese wurde bereits im Kapitel Approximation_der_Fehlerwahrscheinlichkeit des Buches „Digitalsignalübertragung” verwendet.

Verallgemeinern und formalisieren wir diese Ergebnisse unter der Voraussetzung, dass sowohl x_ als auch x_′ zum Code C gehören. Dann gelten folgende Berechnungsvorschriften:

Definitionen: 

  • Blockfehlerwahrscheinlichkeit:
Pr(Blockfehler)=Pr(⋃x_′≠x_[x_↦x_′]),
  • Obere Schranke nach der Union Bound:
Pr(UnionBound)≤∑x_′≠x_Pr[x_↦x_′],
  • Paarweise Fehlerwahrscheinlichkeit (nach dem MAP– bzw. ML–Kriterium):
Pr[x_↦x_′]=Pr[f(x_|y_)≤f(x_′|y_)].

Auf den nächsten Seiten werden diese Ergebnisse auf verschiedene Kanäle angewendet.

Union Bound für das BSC–Modell


Wir betrachten weiterhin den beispielhaften (5,2)–Code: C={(0,0,0,0,0),(0,1,0,1,1),(1,0,1,1,0),(1,1,1,0,1)} und für den digitalen Kanal verwenden wir das BSC–Modell (Binary Symmetric Channel):

Pr(y=1|x=0)=Pr(y=0|x=1)=Pr(e=1)=ε,
Pr(y=0|x=0)=Pr(y=1|x=1)=Pr(e=0)=1−ε.
BSC–Modell und ML–Detektion

Dann gilt:

  • Die beiden Codeworte x_0=(0,0,0,0,0) und x_1=(0,1,0,1,1) unterscheiden sich in genau d=3 Bitpositionen, wobei d die Hamming–Distanz zwischen x_0 und x_1 angibt.
  • Ein falsches Decodierergebnis [x_0↦x_1] erhält man immer dann, wenn mindestens zwei der drei Bit an den Bitpositionen 2, 4 und 5 verfälscht werden.
  • Die Bitpositionen 1 und 3 spielen hier dagegen keine Rolle, da diese für x_0 und x_1 gleich sind.


Da der betrachtete Code t=⌊(d−1)/2⌋=1 Fehler korrigieren kann, gilt:

Pr[x_0↦x_1]=d∑i=t+1(di)⋅εi⋅(1−ε)d−i=(32)⋅ε2⋅(1−ε)+(33)⋅ε3=3⋅ε2⋅(1−ε)+ε3=Pr[x_0↦x_2].

Hierbei ist berücksichtigt, dass sich x_0=(0,0,0,0,0) und x_2=(1,0,1,1,0) ebenfalls in drei Bitpositionen unterscheiden.

Die Codeworte x_0=(0,0,0,0,0) und x_3=(1,1,1,0,1) unterscheiden sich dagegen in vier Bitpositionen:

  • Zu einer falschen Decodierung des Blocks kommt es deshalb mit Sicherheit, wenn vier oder drei Bit verfälscht werden.
  • Eine Verfälschung von zwei Bit hat mit 50–prozentiger Wahrscheinlichkeit ebenfalls einen Blockfehler zur Folge, wenn man hierfür eine Zufallsentscheidung voraussetzt.
Pr[x_0↦x_3]=ε4+4⋅ε3⋅(1−ε)+1/2⋅6⋅ε2⋅(1−ε)2.

Daraus ergibt sich für die „Union Bound”:

Pr(UnionBound)=Pr[x_0↦x_1]+Pr[x_0↦x_2]+Pr[x_0↦x_3]≥Pr(Blockfehler).

Zahlenmäßige Union Bound für den (5, 2)–Code

Beispiel 3:  In der Tabelle sind die Ergebnisse für verschiedene Werte des BSC–Parameters ε zusammengefasst.


Zu erwähnen ist, dass die völlig unterschiedlich zu berechnenden Wahrscheinlichkeiten Pr[x_0↦x_1] und Pr[x_0↦x_3] genau das gleiche Ergebnis liefern.


Die obere Schranke nach Bhattacharyya


Eine weitere obere Schranke für die Blockfehlerwahrscheinlichkeit wurde von Bhattacharyya angegeben:

Pr(Blockfehler)≤W(X=β)−1=Pr(Bhattacharyya).

Hierzu ist anzumerken:

  • W(X) ist die oben definierte Gewichtsfunktion, die den verwendeten Kanalcode charakterisiert.
  • Der Bhattacharyya–Parameter β kennzeichnet den digitalen Kanal. Beispielsweise gilt:
β={λ√4⋅ε⋅(1−ε)exp[−R⋅EB/N0]f¨urdasBEC−Modell,f¨urdasBSC−Modell,f¨urdasAWGN−Modell.
  • Die Bhattacharyya–Schranke liegt stets (und meist deutlich) oberhalb der Kurve für die „Union Bound”. Mit dem Ziel, eine für alle Kanäle einheitliche Schranke zu finden, müssen hier sehr viel gröbere Abschätzungen vorgenommen werden als für die Herleitung der „Union Bound”.

Wir beschränken uns hier auf die Bhattacharyya–Schranke für das BSC–Modell. Für dessen paarweise Verfälschungswahrscheinlichkeit wurde vorne hergeleitet:

Pr[x_0↦x_1]=d∑i=⌊(d−1)/2⌋(di)⋅εi⋅(1−ε)d−i=d∑i=⌈d/2⌉(di)⋅εi⋅(1−ε)d−i.

Hierbei kennzeichnet ε=Pr(y=1|x=0)=Pr(y=0|x=1)<0.5 das Kanalmodell und d=dH(x_0,x_1) gibt die Hamming–Distanz der betrachteten Codeworte an.

Um zur Bhattacharyya–Schranke zu kommen, müssen folgende Abschätzungen getroffen werden:

  • Für allei<d gilt εi⋅(1−ε)d−i≤(1−ε)d/2:
Pr[x_0↦x_1]≤[ε⋅(1−ε)]d/2⋅d∑i=⌈d/2⌉(di).
  • Änderung bezüglich der unteren Grenze der Laufvariablen i:
d∑i=⌈d/2⌉(di)<d∑i=0(di)=2d,β=2⋅√ε⋅(1−ε)⇒Pr[x_0↦x_1]=βd.
  • Umsortierung gemäß den Hamming–Gewichten Wi (Hamming–Distanz d=i kommt Wi mal vor):
Pr(Blockfehler)≤n∑i=1Wi⋅βi=1+W1⋅β+W2⋅β2+...+Wn⋅βn.
  • Mit der Gewichtsfunktion W(X)=1+W1⋅X+W2⋅X2+...+Wn⋅Xn:
Pr(Blockfehler)≤W(X=β)−1=Pr(Bhattacharyya).
Vergleich Union Bound vs. Bhattacharyya–Schranke (BSC–Modell)

Beispiel 4:  In der Tabelle sind die Bhattacharyya–Ergebnisse für verschiedene Werte des BSC–Parameters ε zusammengefasst, gültig für den beispielhaften (5, 2)–Code. Für diesen gilt:

W0=1,  W1=W2=0,  W3=2,  W4=1
⇒W(X)=1+2⋅X3+X4.

Damit kann die Bhattacharyya–Schranke berechnet werden:

Pr(Bhattacharyya)=W(β)−1=2⋅β3+β4.

Diese stellt eine (oft grobe) Schranke für die Blockfehlerwahrscheinlichkeit dar:

Pr(Blockfehler)≤Pr(Bhattacharyya).


Fazit:  Basierend auf Beispiel 3 und Beispiel 4 (auf dieser Seite) für den einfachen (5, 2)–Bolckcode, der allerdings wenig praxisrelevant ist, sowie im Vorgriff aufdas Beispiel 5 (auf der folgenden Seite) für den (7, 4, 3)–Hamming–Code kann man zusammenfassen:

  • Die Blockfehlerwahrscheinlichkeit eines Codiersystems ist oft analytisch nicht angebbar und muss per Simulation ermittelt werden. Gleiches gilt für die Bitfehlerwahrscheinlichkeit.
  • Die Union Bound liefert eine obere Schranke für die Blockfehlerwahrscheinlichkeit. Bei vielen Anwendungen (insbesondere bei kurzen Codes) liegt sie nur geringfügig über dieser.
  • Die Bhattacharyya–Schranke liegt beim BEC–Kanal etwa um den Faktor 2 oberhalb der Union Bound – siehe Aufgabe 1.14. Beim BSC– und beim AWGN–Kanal ist der Abstand zwischen beiden Schranken deutlich größer. Der Faktor 10 (oder mehr) ist keine Seltenheit.
  • Die Bhattacharyya–Schranke W(β)−1 wirkt auf den ersten Blick sehr einfach. Es sind aber einige Vereinfachungsschritte erforderlich, um auf diese Form zu kommen. Trotzdem benötigt man auch hier Kenntnis über die genaue Gewichtsfunktion W(ξ) des Codes.
  • Bei Kenntnis des Übertragungskanals (BEC, BSC, AWGN oder Abwandlungen hiervon) und dessen Parameter spricht vom Aufwand her nichts dagegen, die Union Bound als obere Schranke für die Blockfehlerwahrscheinlichkeit zu verwenden.


Schranken für den (7, 4, 3)–Hamming–Code beim AWGN–Kanal


Abschließend betrachten wir die Blockfehlerwahrscheinlichkeit und deren Schranken (Union Bound und Bhattacharyya–Schranke) für die folgende Konfiguration:

  • AWGN–Kanal, gekennzeichnet durch den Quotienten EB/N0,
  • Hamming–Code (7, 4)   ⇒   R=4/7,   W(X)−1=–1=7⋅X3+7⋅X4+X7,
  • Soft–Decision nach dem ML–Kriterium.

Blockfehlerwahrscheinlichkeit und Schranken des HC (7, 4, 3)

Beispiel 5:  Die Ergebnisse sind in der Grafik zusammengefasst.

  • Im Gegensatz zur Grafik im Abschnitt Codiergewinn – Bitfehlerrate bei AWGN ist hier die Blockfehlerrate angegeben und nicht die Bitfehlerrate.
  • Näherungsweise ist Letztere um den Faktor dmin/k kleiner, falls wie hier dmin<k ist. Im vorliegenden Beispiel gilt dmin/k=0.75.
  • Berechnet wurden nur die Punkte für ganzzahlige dB–Werte. Die gestrichelten Linien wurden interpoliert.
  • Die rechts angegebenen (blauen) Zahlenwerte gelten für 10⋅lgEB/N0=8dB   ⇒   EB/N0≈6.31 (blaue Vertikale).


Die grünen Kreuze markieren die Union Bound. Nach dieser gilt:

Pr(Blockfehler)≤n∑i=dminWi⋅Q(√i⋅2R⋅EB/N0)=7⋅Q(4.65)+7⋅Q(5.37)+Q(7.10)
⇒Pr(Blockfehler)≈7⋅1.66⋅10−6+7⋅3.93⋅10−8+10−9=1.2⋅10−5.
  • Die Zahlenwerte machen deutlich, dass die Union Bound durch den ersten Term bestimmt wird:
Pr(UnionBound)≈Wdmin⋅Q(√dmin⋅2R⋅EB/N0)=1.16⋅10−5.
  • Allerdings ist diese so genannte Truncated Union Bound nicht mehr bei allen Anwendungen eine echte Schranke für die Blockfehlerwahrscheinlichkeit, sondern ist als Näherung zu verstehen.
  • Die Bhattacharyya–Schranke ist in der Grafik durch rote Punkte markiert. Diese Schranke liegt aufgrund der stark vereinfachten Chernoff–Rubin Bound Q(x)≤e−x2/2 deutlich über der Union Bound.
  • Für 10⋅lgEB/N0=8dB erhält man mit β=e−R⋅EB/N0≈0.027:
Pr(Bhattacharyya)=W(β)−1=7⋅β3+7⋅β4+β7≈1.44⋅10−4.

Aufgaben zum Kapitel


A1.14 Bhattacharyya–Schranke für BEC

A1.15 Distanzspektren

A1.16 Schranken für AWGN

Zusatzaufgabe 1.16: Schranken für Q(x)



Retrieved from "http://en.lntwww.de/index.php?title=Channel_Coding/Bounds_for_Block_Error_Probability&oldid=21277"
  • Powered by MediaWiki