176
O Wege, Umwege, Irrwege Wege, Umwege, Irrwege zur Kanalkapazit ¨ at zur Kanalkapazit ¨ at – Die Entwicklung hocheffizienter digitaler ¨ Ubertragungsverfahren – Johannes Huber Lehrstuhl f ¨ ur Informations ¨ ubertragung Friedrich–Alexander–Universit ¨ at Erlangen–N¨ urnberg Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazit ¨ at 1/50

Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

Embed Size (px)

Citation preview

Page 1: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Wege, Umwege, IrrwegeWege, Umwege, Irrwege

zur Kanalkapazitatzur Kanalkapazitat

– Die Entwicklung hocheffizienter digitaler Ubertragungsverfahren –

Johannes Huber

Lehrstuhl fur Informationsubertragung

Friedrich–Alexander–Universitat Erlangen–Nurnberg

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 1/50

Page 2: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

UbersichtUbersicht

Informationstheorie

Kanalcodierung und Kanalcodierungstheorem

Algebraische Kanalcodierung

Faltungscodierung

Turbo–Codes

LDPC–Codes und deren Wiederentdeckung

Polar Codes

Zusammenfassung und Schlußfolgerungen

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 2/50

Page 3: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Das Shannonsche Informationsmaß:

Informationssymbol

X = {x1, x2, . . . , xi, . . . , xM}

Informationsempfanger: Beobachter eines Zufallsexperiments

Information: Verringerung der Unsicherheit uber das Ergebnis eines

Zufallsexperiments

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 3/50

Page 4: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Das Shannonsche Informationsmaß:

Informationssymbol

X = {x1, x2, . . . , xi, . . . , xM}

Informationsempfanger: Beobachter eines Zufallsexperiments

Information: Verringerung der Unsicherheit uber das Ergebnis eines

Zufallsexperiments

Informationsmaß nach C.E. Shannon (1948):

IS(xi) = − log2(Pr{X = xi}) bitSymbol

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 3/50

Page 5: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Mittlerer Informationsgehalt je Quellensymbol:

→ Entropie der Informationsquelle

H(X) = −M∑i=1

Pr{X = xi} log2(Pr{X = xi}) bitSymbol

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 4/50

Page 6: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Mittlerer Informationsgehalt je Quellensymbol:

→ Entropie der Informationsquelle

H(X) = −M∑i=1

Pr{X = xi} log2(Pr{X = xi}) bitSymbol

Beispiel: Vereinfachtes Lotto

X = {6−, 5−, 4−, 3 − Richtige, kein Gewinn}

H(X) = 0,14 bit/Ziehung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 4/50

Page 7: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Binare Quelle

X ∈ {A,B} , Pr{X = A} = p , Pr{X = B} = 1 − p

H(X

)

bitBinarsymbol

p

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 5/50

Page 8: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Binare Quelle

X ∈ {A,B} , Pr{X = A} = p , Pr{X = B} = 1 − p

fairer Munzwurf

↓H

(X)

bitBinarsymbol

p

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 5/50

Page 9: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Informationsubertragung uber gestorte Kanale:

Direkte Beobachtung von X nicht moglich.

⇒ Ruckschluß auf X anhand der Beobachtung von Y , aber leider

unzuverlassig!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 6/50

Page 10: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Informationsubertragung uber gestorte Kanale:

Direkte Beobachtung von X nicht moglich.

⇒ Ruckschluß auf X anhand der Beobachtung von Y , aber leider

unzuverlassig!

Kanal: Mehr oder weniger zufallige Erzeugung von Y aus X.

M × L bedingte Wahrscheinlichkeiten Pr{Y = yj | X = xi} = kij

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 6/50

Page 11: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Symmetrischer Binarkanal

BER: Bit Error Ratio

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 7/50

Page 12: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Symmetrischer Binarkanal

BER: Bit Error Ratio

Beispiel: Additives weißes gauß’sches Rauschen

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 7/50

Page 13: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Transinformation, Kanalkapazitat:

Verringerung der Unsicherheit uber X durch Beobachtung von Y :

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 8/50

Page 14: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Transinformation, Kanalkapazitat:

Verringerung der Unsicherheit uber X durch Beobachtung von Y :

− log2(Pr{X = xi})

Unsicherheit vorher

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 8/50

Page 15: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Transinformation, Kanalkapazitat:

Verringerung der Unsicherheit uber X durch Beobachtung von Y :

− log2(Pr{X = xi}) − (− log2(Pr{X = xi | Y = yj}))

Unsicherheit vorher − Unsicherheit nachher

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 8/50

Page 16: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Transinformation, Kanalkapazitat:

Verringerung der Unsicherheit uber X durch Beobachtung von Y :

− log2(Pr{X = xi}) − (− log2(Pr{X = xi | Y = yj})) =

Unsicherheit vorher − Unsicherheit nachher =

= ubertragene Information

[bit

Kanalbenutzung

]

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 8/50

Page 17: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Im Mittel je Kanalbenutzung ubertragene Information:

→ Transinformation

I(X;Y ) =M∑i=1

L∑j=1

Pr{X = xi} kij log2

(kij∑M

l=1 Pr{X = xl} klj

)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 9/50

Page 18: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Im Mittel je Kanalbenutzung ubertragene Information:

→ Transinformation

I(X;Y ) =M∑i=1

L∑j=1

Pr{X = xi} kij log2

(kij∑M

l=1 Pr{X = xl} klj

)

Maximierung der Transinformation

Kanalkapazitat:

C = maxPr{X}

I(X;Y )bit

Kanalbenutzung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 9/50

Page 19: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Symmetrischer Binarkanal mit Bit Error Ratio BER

C = 1 + BER log2(BER) + (1 − BER) log2(1 − BER)bit

Kanalbenutzung

C

bitKanalbenutzung

BER

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 10/50

Page 20: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Beispiel: Kanal mit additivem weißen gauß’schen Rauschen

Bei beschrankter mittlerer Sendeleistung S = σ2x wird die

Transinformation fur kontinuierlich gaußverteilte Eingangsvariable X

maximiert:

Kanalkapazitat (AWGN–Kanal):

C =12

log2

(1 +

S

N

)bit

Kanalbenutzung

Shannons beruhmte Gleichung (1948).

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 11/50

Page 21: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Kapazitat des AWGN–Kanals:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50

Page 22: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Kapazitat des AWGN–Kanals:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50

Page 23: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Kapazitat des AWGN–Kanals:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50

Page 24: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Kapazitat des AWGN–Kanals:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50

Page 25: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

InformationstheorieInformationstheorie

Kapazitat des AWGN–Kanals:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50

Page 26: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Redundante Kanalcodierung:

Wort aus n Binarsymbolen Xi ∈ {0, 1}

⇒ Es existieren somit 2n mogliche verschiedene Worter

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 13/50

Page 27: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Redundante Kanalcodierung:

Wort aus n Binarsymbolen Xi ∈ {0, 1}

⇒ Es existieren somit 2n mogliche verschiedene Worter

Beispiele:

• n = 10 210 = 1024

• n = 100 2100 = 1,3 · 1030

• n = 1000 21000 = 1,1 · 10301

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 13/50

Page 28: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information je Wort k bit Information je Wort

n Binarsymbole

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 14/50

Page 29: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information je Wort k bit Information je Wort

n Binarsymbole

Von 2n moglichen Wortern sind nur 2k Codeworter zugelassen → Code

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 14/50

Page 30: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information je Wort k bit Information je Wort

n Binarsymbole

Von 2n moglichen Wortern sind nur 2k Codeworter zugelassen → Code

Mittlerer Informationsgehalt je Codesymbol → Rate des Code

R =k

n

bit

Codesymbol

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 14/50

Page 31: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information je Wort k bit Information je Wort

n Binarsymbole

Von 2n moglichen Wortern sind nur 2k Codeworter zugelassen → Code

Mittlerer Informationsgehalt je Codesymbol → Rate des Code

R =k

n

bit

Codesymbol

Coderedundanz je binarem Codesymbol:

ρ = 1 − R =n − k

n

bit

Codesymbol

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 14/50

Page 32: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information je Wort k bit Information je Wort

n Binarsymbole

Von 2n moglichen Wortern sind nur 2k Codeworter zugelassen → Code

Mittlerer Informationsgehalt je Codesymbol → Rate des Code

R =k

n

bit

Codesymbol

Coderedundanz je binarem Codesymbol:

ρ = 1 − R =n − k

n

bit

Codesymbol

Je zugelassenem Codewort werden 2n−k mogliche Worter verworfen!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 14/50

Page 33: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information/Wort k bit Information/Wort

n Binarsymbole

Beispiel: Code mit Rate R = 0,6bit

Codesymbol

• n = 100, k = 60 → Dichte =1

1,1 · 1012

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 15/50

Page 34: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information/Wort k bit Information/Wort

n Binarsymbole

Beispiel: Code mit Rate R = 0,6bit

Codesymbol

• n = 100, k = 60 → Dichte =1

1,1 · 1012

• n = 1000, k = 600 → Dichte =1

2,6 · 10120

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 15/50

Page 35: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information/Wort k bit Information/Wort

n Binarsymbole

Beispiel: Code mit Rate R = 0,6bit

Codesymbol

• n = 100, k = 60 → Dichte =1

1,1 · 1012

• n = 1000, k = 600 → Dichte =1

2,6 · 10120

• n = 10000, k = 6000 → Dichte =1

1,3 · 101204

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 15/50

Page 36: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

k bit Information/Wort k bit Information/Wort

n Binarsymbole

Beispiel: Code mit Rate R = 0,6bit

Codesymbol

• n = 100, k = 60 → Dichte =1

1,1 · 1012

• n = 1000, k = 600 → Dichte =1

2,6 · 10120

• n = 10000, k = 6000 → Dichte =1

1,3 · 101204

Die geringe Dichte zugelassener Codeworter erlaubt sichere Erkennung und

Korrektur von Fehlern!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 15/50

Page 37: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Kanalcodierungstheorem (Shannon 1948):

Theorem:

Auch uber einen gestorten Ubertragungskanal kann Information prinzipiell mit

beliebig hoher Zuverlassigkeit ubertragen werden, wenn man eine redundante

Kanalcodierung einsetzt und dabei die Rate R des Codes kleiner als die Ka-

pazitat C des Kanals sowie die Blocklange n genugend groß gewahlt werden.

Ubersteigt dahingegen die Coderate die Kanalkapazitat, dann ist eine zu-

verlassige Informationsubertragung prinzipiell unmoglich.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 16/50

Page 38: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Kanalcodierungstheorem (Shannon 1948):

Theorem:

Auch uber einen gestorten Ubertragungskanal kann Information prinzipiell mit

beliebig hoher Zuverlassigkeit ubertragen werden, wenn man eine redundante

Kanalcodierung einsetzt und dabei die Rate R des Codes kleiner als die Ka-

pazitat C des Kanals sowie die Blocklange n genugend groß gewahlt werden.

Ubersteigt dahingegen die Coderate die Kanalkapazitat, dann ist eine zu-

verlassige Informationsubertragung prinzipiell unmoglich.

Beweisverfahren: Berechnung einer oberen Schranke fur den Mittelwert der Wort-

fehlerwahrscheinlichkeit fur alle moglichen Codes, bzw. wenn Codeworter zufallig aus

der Menge der moglichen Worter ausgewahlt werden.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 16/50

Page 39: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Kommentare und Interpretationen:

Uber einen gestorten Kanal kann je Benutzung aufgrund der verbleibenden

Unsicherheit beim Einzelsymbol nicht log2(M) sondern hochstens C ≤ log2(M)

bit Information sicher ubertragen werden.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 17/50

Page 40: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Kommentare und Interpretationen:

Uber einen gestorten Kanal kann je Benutzung aufgrund der verbleibenden

Unsicherheit beim Einzelsymbol nicht log2(M) sondern hochstens C ≤ log2(M)

bit Information sicher ubertragen werden.

Durch den Kanalcode werden k bit Information auf n Codesymbole gleichmaßig

verteilt.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 17/50

Page 41: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Kommentare und Interpretationen:

Uber einen gestorten Kanal kann je Benutzung aufgrund der verbleibenden

Unsicherheit beim Einzelsymbol nicht log2(M) sondern hochstens C ≤ log2(M)

bit Information sicher ubertragen werden.

Durch den Kanalcode werden k bit Information auf n Codesymbole gleichmaßig

verteilt.

Eine zuverlassige Ubertragung ist dann und nur dann moglich, wenn im Mittel

nicht mehr Informationsubertragung vom Kanal verlangt wird, als dieser zu

ubertragen in der Lage ist.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 17/50

Page 42: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Ein Kanalcode funktioniert wie eine Krankenversicherung:

• Krankheit: → Storung

• Pramie: → Redundanz

• mehr Versicherte, bessere Mittellung: → große Codewortlange

• Bankrott der Versicherung (mehr Kosten als Pramien):

→ Codewortfehler

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 18/50

Page 43: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Ein Kanalcode funktioniert wie eine Krankenversicherung:

• Krankheit: → Storung

• Pramie: → Redundanz

• mehr Versicherte, bessere Mittellung: → große Codewortlange

• Bankrott der Versicherung (mehr Kosten als Pramien):

→ Codewortfehler

Informationstheorie liefert nur prinzipielle Aussagen:

• keine Hinweise auf praktikable Verfahren

• Tabellen fur Coder und Decoder sind fur großere Wortlangen prinzipiell nicht

moglich!

⇒ Suche nach algorithmischen Verfahren

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 18/50

Page 44: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Ein Kanalcode funktioniert wie eine Krankenversicherung:

• Krankheit: → Storung

• Pramie: → Redundanz

• mehr Versicherte, bessere Mittellung: → große Codewortlange

• Bankrott der Versicherung (mehr Kosten als Pramien):

→ Codewortfehler

Informationstheorie liefert nur prinzipielle Aussagen:

• keine Hinweise auf praktikable Verfahren

• Tabellen fur Coder und Decoder sind fur großere Wortlangen prinzipiell nicht

moglich!

⇒ Suche nach algorithmischen Verfahren

Bei großen Wortlangen sind (fast) alle moglichen Codes gute Codes!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 18/50

Page 45: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Kanalcodierung, KanalcodierungstheoremKanalcodierung, Kanalcodierungstheorem

Ein Kanalcode funktioniert wie eine Krankenversicherung:

• Krankheit: → Storung

• Pramie: → Redundanz

• mehr Versicherte, bessere Mittellung: → große Codewortlange

• Bankrott der Versicherung (mehr Kosten als Pramien):

→ Codewortfehler

Informationstheorie liefert nur prinzipielle Aussagen:

• keine Hinweise auf praktikable Verfahren

• Tabellen fur Coder und Decoder sind fur großere Wortlangen prinzipiell nicht

moglich!

⇒ Suche nach algorithmischen Verfahren

Bei großen Wortlangen sind (fast) alle moglichen Codes gute Codes!

Die Codiertheoreme bestatigen die Relevanz des Shannonschen

Informationsmaßes

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 18/50

Page 46: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Konstruktion von Codes mittels

Mathematik in endlichen Korpern (Galoisfelder)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50

Page 47: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Konstruktion von Codes mittels

Mathematik in endlichen Korpern (Galoisfelder)

• Algorithmische Verfahren fur Codierung und Decodierung

• Codes mit großen Wortlangen werden praktikabel!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50

Page 48: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Konstruktion von Codes mittels

Mathematik in endlichen Korpern (Galoisfelder)

• Algorithmische Verfahren fur Codierung und Decodierung

• Codes mit großen Wortlangen werden praktikabel!

Anzahl der Symbole, in denen sich zwei zugelassene Codeworter

unterscheiden: Hammingdistanz

Codewort A: 0 1 0 1 0 1 1 0 1

Codewort B: 1 1 1 1 0 0 1 0 1

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50

Page 49: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Konstruktion von Codes mittels

Mathematik in endlichen Korpern (Galoisfelder)

• Algorithmische Verfahren fur Codierung und Decodierung

• Codes mit großen Wortlangen werden praktikabel!

Anzahl der Symbole, in denen sich zwei zugelassene Codeworter

unterscheiden: Hammingdistanz

Codewort A: 0 1 0 1 0 1 1 0 1

Codewort B: 1 1 1 1 0 0 1 0 1

Hammingdistanz δ = 3

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50

Page 50: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Konstruktion von Codes mittels

Mathematik in endlichen Korpern (Galoisfelder)

• Algorithmische Verfahren fur Codierung und Decodierung

• Codes mit großen Wortlangen werden praktikabel!

Anzahl der Symbole, in denen sich zwei zugelassene Codeworter

unterscheiden: Hammingdistanz

Codewort A: 0 1 0 1 0 1 1 0 1

Codewort B: 1 1 1 1 0 0 1 0 1

Hammingdistanz δ = 3

Der Code, d.h. die Menge der zugelassenen Codeworter, wird zu einem

metrischen Raum!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50

Page 51: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Code als metrischer Raum bzgl. der Hammingdistanz:

Menge der 2n moglichen Worter

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 20/50

Page 52: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Code als metrischer Raum bzgl. der Hammingdistanz:

Menge der 2n moglichen Worter

Menge der 2k zugelassenen Codeworter (Code)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 20/50

Page 53: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Code als metrischer Raum bzgl. der Hammingdistanz:

Menge der 2n moglichen Worter

Menge der 2k zugelassenen Codeworter (Code)

Hammingdistanz δ

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 20/50

Page 54: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Code als metrischer Raum bzgl. der Hammingdistanz:

Menge der 2n moglichen Worter

Menge der 2k zugelassenen Codeworter (Code)

Hammingdistanz δ

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 20/50

Page 55: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Optimierungsziel seit Hamming (1947):

moglichst große minimale Hammingdistanz δmin

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 21/50

Page 56: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Optimierungsziel seit Hamming (1947):

moglichst große minimale Hammingdistanz δmin

Code mit minimaler Hammingdistanz δmin → sicher bis zu

t ≤⌊δmin − 1

2

⌋Codesymbolfehler korrigierbar

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 21/50

Page 57: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Optimierungsziel seit Hamming (1947):

moglichst große minimale Hammingdistanz δmin

Code mit minimaler Hammingdistanz δmin → sicher bis zu

t ≤⌊δmin − 1

2

⌋Codesymbolfehler korrigierbar

Effiziente algebraische Methoden zur Vorwartsfehlerkorrektur

(Forward Error Correction: FEC)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 21/50

Page 58: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Optimierungsziel seit Hamming (1947):

moglichst große minimale Hammingdistanz δmin

Code mit minimaler Hammingdistanz δmin → sicher bis zu

t ≤⌊δmin − 1

2

⌋Codesymbolfehler korrigierbar

Effiziente algebraische Methoden zur Vorwartsfehlerkorrektur

(Forward Error Correction: FEC)

Bounded–Minimum–Distance (BMD) Fehlerkorrektur:

”Kugel“ mit Radius t (bzgl. Hammingdistanz) um die Codeworter

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 21/50

Page 59: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Bose–Chaudhuri–Hocquenghem (BCH) Codes (1959/60):

Konstruktion mittels Methoden der Signalverarbeitung, jedoch in finiten

Korpern:

⇒ Korpererweiterung, Diskrete Fouriertransformation, Tiefpassfilterung,

Abtasttheorem usw.

(Blahut 1979)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 22/50

Page 60: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 61: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 62: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 63: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 64: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 65: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Eb: Empfangsenergie je bit ubertragener Information

N0: einseitige Rauschleistungsdichte

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 66: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 67: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

5,8 dB Codegewinn bei BER ≈ 10−8:

⇒ Reduktion der Sendeleistung um Faktor 3,8

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 68: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

BER fur binare BCH–Codes mit Rate R ≈ 1/2 (AWGN + 2ASK):

5,8 dB Codegewinn bei BER ≈ 10−8:

⇒ Reduktion der Sendeleistung um Faktor 3,86,0 dB Abstand zur Kapazitatsschranke

Halber Weg zur Kanalkapazitat!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 23/50

Page 69: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Ursachen der beschrankten Leistungsfahigkeit algebraischerCodierverfahren:

optimale Maximum–Likelihood–Decodierung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 24/50

Page 70: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Ursachen der beschrankten Leistungsfahigkeit algebraischerCodierverfahren:

optimale Maximum–Likelihood–Decodierung

stattdessen Bounded–Minimum–Distance–Fehlerkorrektur

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 24/50

Page 71: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Binare Vorentscheidung uber die Codesymbole vor der eigentlichen

Decodierung (Hard–Decision FEC)

⇒ Verlust von Zuverlassigkeitsinformation fur die einzelnen Symbole

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 25/50

Page 72: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Algebraische BlockcodesAlgebraische Blockcodes

Binare Vorentscheidung uber die Codesymbole vor der eigentlichen

Decodierung (Hard–Decision FEC)

⇒ Verlust von Zuverlassigkeitsinformation fur die einzelnen Symbole

Bisher keine effizienten Soft–Decision–Maximum–Likelihood–

Decodieralgorithmen fur lange, algebraisch konstruierte Codes bekannt!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 25/50

Page 73: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Scrambler (”Verwurfler“) fur Binarsequenzen:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 26/50

Page 74: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Scrambler (”Verwurfler“) fur Binarsequenzen:

Ausgangsfolge = Faltung der Eingangsfolge mit der Impulsantwort g[i]des linearen, dispersiven Systems A(z)/B(z)

mit z−1 : Binare Speicherzelle (D-Flip-Flop)

⊕: Addition modulo 2 (XOR)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 26/50

Page 75: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Faltungscoder mit Rate 1/2:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50

Page 76: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Faltungscoder mit Rate 1/n:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50

Page 77: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Systematischer Faltungscoder mit Rate 1/n:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50

Page 78: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

FaltungscodesFaltungscodes

Systematischer Faltungscoder mit Rate 1/n:

Auswahl der Scrambler fur großtmogliche minimale Hammingdistanz

zwischen unterschiedlichen Ausgangsfolgen X[l]

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50

Page 79: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 80: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 81: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 82: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Bestimmung von a-posteriori Wahrscheinlichkeiten fur die einzelnen

Codesymbole

Pr {X[l] = 0 | Y [l]}

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 83: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Bestimmung von a-posteriori Wahrscheinlichkeiten fur die einzelnen

Codesymbole

Pr {X[l] = 0 | Y [l]}Decodierung: Suche nach Codewort mit großter Wahrscheinlichkeit

⇒ Verwertung von Zuverlassigkeitsinformationen fur die einzelnen

Symbole

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 84: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Bestimmung von a-posteriori Wahrscheinlichkeiten fur die einzelnen

Codesymbole

Pr {X[l] = 0 | Y [l]}Decodierung: Suche nach Codewort mit großter Wahrscheinlichkeit

⇒ Verwertung von Zuverlassigkeitsinformationen fur die einzelnen

Symbole

Soft–Decision–Decodierung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50

Page 85: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Decodierung von Faltungscodes:

Bestimmung der Folge U [0], U [1], . . . , die aufgrund der analogen

Empfangswerte Y [0], Y [1], . . . , unter Berucksichtigung der Codegesetze

die großte Wahrscheinlichkeit besitzt.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 29/50

Page 86: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Decodierung von Faltungscodes:

Bestimmung der Folge U [0], U [1], . . . , die aufgrund der analogen

Empfangswerte Y [0], Y [1], . . . , unter Berucksichtigung der Codegesetze

die großte Wahrscheinlichkeit besitzt.

Verwertung von Zuverlassigkeitsinformation:

Soft–Decision–Maximum–Likelihood–Sequence–Estimation

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 29/50

Page 87: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Decodierung von Faltungscodes:

Bestimmung der Folge U [0], U [1], . . . , die aufgrund der analogen

Empfangswerte Y [0], Y [1], . . . , unter Berucksichtigung der Codegesetze

die großte Wahrscheinlichkeit besitzt.

Verwertung von Zuverlassigkeitsinformation:

Soft–Decision–Maximum–Likelihood–Sequence–Estimation

Viterbi–Algorithmus (1967/1971)

Linear Programming (Bellman 1958)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 29/50

Page 88: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding

Decodierung von Faltungscodes:

Bestimmung der Folge U [0], U [1], . . . , die aufgrund der analogen

Empfangswerte Y [0], Y [1], . . . , unter Berucksichtigung der Codegesetze

die großte Wahrscheinlichkeit besitzt.

Verwertung von Zuverlassigkeitsinformation:

Soft–Decision–Maximum–Likelihood–Sequence–Estimation

Viterbi–Algorithmus (1967/1971)

Linear Programming (Bellman 1958)

Komplexitat steigt exponentiell mit der Zahl der binaren Speicherzellen!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 29/50

Page 89: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-In/Soft-Out DecodingFaltungscodes: Soft-In/Soft-Out Decoding

Decodierung von Faltungscodes:

Berechnung von a–posteriori Wahrscheinlichkeiten fur alle einzelnen

Informationssymbole:

Pr {U [i] = 0 | (Y [0], Y [1], . . .)}

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 30/50

Page 90: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-In/Soft-Out DecodingFaltungscodes: Soft-In/Soft-Out Decoding

Decodierung von Faltungscodes:

Berechnung von a–posteriori Wahrscheinlichkeiten fur alle einzelnen

Informationssymbole:

Pr {U [i] = 0 | (Y [0], Y [1], . . .)}

Verwertung von Zuverlassigkeitsinformation und Erzeugung von

Zuverlassigkeitsinformation:

Soft–In/Soft–Out–Decoder (SISO)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 30/50

Page 91: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-In/Soft-Out DecodingFaltungscodes: Soft-In/Soft-Out Decoding

Decodierung von Faltungscodes:

Berechnung von a–posteriori Wahrscheinlichkeiten fur alle einzelnen

Informationssymbole:

Pr {U [i] = 0 | (Y [0], Y [1], . . .)}

Verwertung von Zuverlassigkeitsinformation und Erzeugung von

Zuverlassigkeitsinformation:

Soft–In/Soft–Out–Decoder (SISO)

Effizienter Algorithmus (Bahl, Cocke, Jelinek, Raviv 1974)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 30/50

Page 92: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: Soft-In/Soft-Out DecodingFaltungscodes: Soft-In/Soft-Out Decoding

Decodierung von Faltungscodes:

Berechnung von a–posteriori Wahrscheinlichkeiten fur alle einzelnen

Informationssymbole:

Pr {U [i] = 0 | (Y [0], Y [1], . . .)}

Verwertung von Zuverlassigkeitsinformation und Erzeugung von

Zuverlassigkeitsinformation:

Soft–In/Soft–Out–Decoder (SISO)

Effizienter Algorithmus (Bahl, Cocke, Jelinek, Raviv 1974)

Komplexitat steigt exponentiell mit der Zahl der binaren Speicherzellen!

optimale Decodieralgorithmen verfugbar, aber nur fur relativ einfache Codes

Soft-Output Viterbi-Algorithmus (SOVA)

(Hagenauer, Hoher / Huber, 1988)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 30/50

Page 93: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: BeispielFaltungscodes: Beispiel

Faltungscode mit Rate R = 1/2:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50

Page 94: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: BeispielFaltungscodes: Beispiel

Faltungscode mit Rate R = 1/2:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50

Page 95: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: BeispielFaltungscodes: Beispiel

Faltungscode mit Rate R = 1/2:

• 6 dB Codegewinn bei BER ≈ 10−8:

⇒ Reduktion der Sendeleistung um Faktor 4

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50

Page 96: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Faltungscodes: BeispielFaltungscodes: Beispiel

Faltungscode mit Rate R = 1/2:

• 6 dB Codegewinn bei BER ≈ 10−8:

⇒ Reduktion der Sendeleistung um Faktor 4

• Abstand zur Kapazitatsschranke: 5,8 dBHalber Weg zur Kanalkapazitat!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50

Page 97: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 98: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Faltungscodierung: Optimale Decodierverfahren fur relativ schwache

Codes

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 99: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Faltungscodierung: Optimale Decodierverfahren fur relativ schwache

Codes

Verknupfung von algebraischer Blockcodierung und Faltungs-

codierung: NASA–Standard–Code: BER ≈ 10−8 bei 3,2 dB

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 100: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Faltungscodierung: Optimale Decodierverfahren fur relativ schwache

Codes

Verknupfung von algebraischer Blockcodierung und Faltungs-

codierung: NASA–Standard–Code: BER ≈ 10−8 bei 3,2 dB

3/4 des Weges zur Kanalkapazitat!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 101: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Faltungscodierung: Optimale Decodierverfahren fur relativ schwache

Codes

Verknupfung von algebraischer Blockcodierung und Faltungs-

codierung: NASA–Standard–Code: BER ≈ 10−8 bei 3,2 dB

3/4 des Weges zur Kanalkapazitat!

Die Kanalkapazitat erscheint unerreichbar!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 102: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Stand der Kanalcodierung 1990Stand der Kanalcodierung 1990

Algebraische Blockcodierung: hervorragende Distanzeigenschaften, aber

geringe Leistungsfahigkeit wegen suboptimaler Decodierung

Faltungscodierung: Optimale Decodierverfahren fur relativ schwache

Codes

Verknupfung von algebraischer Blockcodierung und Faltungs-

codierung: NASA–Standard–Code: BER ≈ 10−8 bei 3,2 dB

3/4 des Weges zur Kanalkapazitat!

Die Kanalkapazitat erscheint unerreichbar!

”Theorem“ der Informationstheorie (Jacobs): Alle Codes sind gut, bis auf

diejenigen, die wir kennen und anwenden konnen.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 32/50

Page 103: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Parallele Verkettung von Faltungscodes:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50

Page 104: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Parallele Verkettung von Faltungscodes:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50

Page 105: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Parallele Verkettung von Faltungscodes:

Decodierung nach dem Turbo–Prinzip mit Soft–In/Soft–Out–Decoder

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50

Page 106: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Parallele Verkettung von Faltungscodes:

Decodierung nach dem Turbo–Prinzip mit Soft–In/Soft–Out–Decoder

Inspiriert durch die Arbeiten von Hagenauer, Hoher / Huber zu

Soft-Output Viterbi-Decodierung

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50

Page 107: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Blockschaltbild der iterativen Decodierung:

C. Berrou und A. Glavieux (ENST Brest, Frankreich, 1991, publ. 1993):

• Interpretation des SISO–Decoders als Signalverarbeitungsmodul

• Anwendung von Methoden der Regelungstechnik zur Stabilisierung des

rekursiven Decodierprozesses

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 34/50

Page 108: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Blockschaltbild der iterativen Decodierung:

C. Berrou und A. Glavieux (ENST Brest, Frankreich, 1991, publ. 1993):

• Interpretation des SISO–Decoders als Signalverarbeitungsmodul

• Anwendung von Methoden der Regelungstechnik zur Stabilisierung des

rekursiven Decodierprozesses

• Erfindung von Außenseitern

• nicht betriebsblind durch Fixierung auf Minimaldistanz

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 34/50

Page 109: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Blockschaltbild der iterativen Decodierung:

C. Berrou und A. Glavieux (ENST Brest, Frankreich, 1991, publ. 1993):

• Interpretation des SISO–Decoders als Signalverarbeitungsmodul

• Anwendung von Methoden der Regelungstechnik zur Stabilisierung des

rekursiven Decodierprozesses

• Erfindung von Außenseitern

• nicht betriebsblind durch Fixierung auf Minimaldistanz

Tutorial Paper von Hagenauer et. al. 1996Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 34/50

Page 110: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 111: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 112: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1Iteration 2

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 113: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1Iteration 23

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 114: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1Iteration 236

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 115: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1Iteration 23618

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 116: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — BeispielTurbo–Codes — Beispiel

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1Iteration 23618

10 log10(Eb/N0) in dB −→

BE

R−→

Theo

r.Gre

nze

,0,1

9dB

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

95% des Weges zur Kanalkapazitat!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 35/50

Page 117: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — KennzeichenTurbo–Codes — Kennzeichen

Optimale Decodierbarkeit von strukturierten Teilcodes

Anwendung des Prinzips der Zufallscodierung

→ Shannons Beweistechnik!

→ pseudozufallige Permutation zur Verknupfung der Teilcodes

⇒ Verknupfung der Zufallscodierung mit algorithmischen Verfahren fur

Codierung und Decodierung von Teilcodes

vollige Vernachlassigung der Minimaldistanz bei der Codekonstruktion

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 36/50

Page 118: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 119: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 120: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 121: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 122: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

I(U ;E2) = I(U ;A2) ; I(U ;A1) = I(U ;E1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 123: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Stefan ten Brink 1999

Analyse des iterativen Decodiervorgangs: Bestimme minimalen

Storabstand fur mogliche Konvergenz zum Punkt (1,1)

I(U ;E2) = I(U ;A2) ; I(U ;A1) = I(U ;E1)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 37/50

Page 124: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Geschlossener Tunnel

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50

Page 125: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Geschlossener Tunnel ⇒ keine Konvergenz bei (1,1)!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50

Page 126: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

Abstand zur Kanalkapazitat: Flache des Konvergenztunnels

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50

Page 127: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

kapazitatserreichende Turbo–Codes (ten Brink 2000):

• irregulare Turbo–Codes (Kotter, Tuchler)

• Multiple Turbo–Codes (Huber, Huttinger)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 39/50

Page 128: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart

kapazitatserreichende Turbo–Codes (ten Brink 2000):

• irregulare Turbo–Codes (Kotter, Tuchler)

• Multiple Turbo–Codes (Huber, Huttinger)

Das Ziel ist nach 52 Jahren erreicht!Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 39/50

Page 129: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Theorem (Lazic 1995):

Ubersteigt die minimale Hammingsdistanz die Gilbert–Varshamov

Schranke, so konnen sehr lange Codes die Kapazitat des symmetrischen

Binarkanals nicht erreichen!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 40/50

Page 130: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Theorem (Lazic 1995):

Ubersteigt die minimale Hammingsdistanz die Gilbert–Varshamov

Schranke, so konnen sehr lange Codes die Kapazitat des symmetrischen

Binarkanals nicht erreichen!

Ebenso beim Entwurf von Codierverfahren fur bandbreiteneffiziente,

mehrstufige Ubertragungsverfahren:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 40/50

Page 131: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Theorem (Lazic 1995):

Ubersteigt die minimale Hammingsdistanz die Gilbert–Varshamov

Schranke, so konnen sehr lange Codes die Kapazitat des symmetrischen

Binarkanals nicht erreichen!

Ebenso beim Entwurf von Codierverfahren fur bandbreiteneffiziente,

mehrstufige Ubertragungsverfahren:

Erfolg durch informationstheoretischen Ratenentwurf (Huber/Wachsmann

1993/1996) fur Multilevel Codes anstelle Maximierung der minimalen

Distanz im Signalraum.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 40/50

Page 132: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Turbo–CodesTurbo–Codes

Theorem (Lazic 1995):

Ubersteigt die minimale Hammingsdistanz die Gilbert–Varshamov

Schranke, so konnen sehr lange Codes die Kapazitat des symmetrischen

Binarkanals nicht erreichen!

Ebenso beim Entwurf von Codierverfahren fur bandbreiteneffiziente,

mehrstufige Ubertragungsverfahren:

Erfolg durch informationstheoretischen Ratenentwurf (Huber/Wachsmann

1993/1996) fur Multilevel Codes anstelle Maximierung der minimalen

Distanz im Signalraum.

Optimierung von Codes nach Kriterium

große Minimaldistanz

erweist sich als Irrweg!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 40/50

Page 133: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 134: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 135: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 . . .

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 136: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 . . . . . .

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 137: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 . . . . . . . . .

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 138: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 . . . . . . . . .

Zusammenfassung aller Prufgleichungen in einer (n − k) × n

Parity–Check–Matrix H

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 139: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Low–Density–Parity–Check–Codes:

Prufgleichungen eines linearen Codes

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 . . . . . . . . .

Zusammenfassung aller Prufgleichungen in einer (n − k) × n

Parity–Check–Matrix H

fur alle zugelassenen Codeworter x gilt

xHT = 0

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50

Page 140: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Eine Prufgleichung bewirkt eine doppelte Ubertragung eines Symbols

(wie beim Wiederholungscode!)

• Intrinsische Information uber X1

X1 → Y1 → pin = Pr{X1 = 0 | Y1}

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 42/50

Page 141: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Eine Prufgleichung bewirkt eine doppelte Ubertragung eines Symbols

(wie beim Wiederholungscode!)

• Intrinsische Information uber X1

X1 → Y1 → pin = Pr{X1 = 0 | Y1}

• Extrinsische Information uber X1

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 → X1 = X5 ⊕ X9 ⊕ X13

X5, X9, X13 → Y5, Y9, Y13 → pex = Pr{X1 = 0 | Y5, Y9, Y13}

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 42/50

Page 142: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Eine Prufgleichung bewirkt eine doppelte Ubertragung eines Symbols

(wie beim Wiederholungscode!)

• Intrinsische Information uber X1

X1 → Y1 → pin = Pr{X1 = 0 | Y1}

• Extrinsische Information uber X1

X1 ⊕ X5 ⊕ X9 ⊕ X13 = 0 → X1 = X5 ⊕ X9 ⊕ X13

X5, X9, X13 → Y5, Y9, Y13 → pex = Pr{X1 = 0 | Y5, Y9, Y13}

• Verknupfen beider Wahrscheinlichkeiten

Pr{X1 = 0 | . . .} =pinpex

pinpex + (1 − pin)(1 − pex)

Codegesetze genutzt zur Erhohung der Zuverlassigkeit!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 42/50

Page 143: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–CodesLDPC–Codes

Iterativer Prozess:

→ Erneute Verbesserung von Pr{Xi = 0 | . . .} durch Wiederholung

moglich!

Nur gultig, solange die statistische Unabhangigkeit der unterschiedlichen

Aussagen uber ein Symbol gewahrt bleibt!

Es sollten keine Kreise (Zyklen) bei der Informationsweitergabe entstehen.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 43/50

Page 144: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — Gallager (1963)LDPC–Codes — Gallager (1963)

Wahl der Prufgleichungen moglichst zufallig

Jedes Symbol ist an J Prufgleichungen beteiligt

Jede Prufgleichung erstreckt sich uber K Symbole

Coderate R = 1 − JK

(Beispiel: J = 3, K = 6, R = 12 )

Vermeidung von Zyklen durch sehr große Wortlange und durch

Verwendung weniger Symbole in der Prufgleichung (Low Density)

Verknupfung von Struktur und Zufallsentwurf

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 44/50

Page 145: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — Gallager (1963)LDPC–Codes — Gallager (1963)

Iterativer Decodierprozeß mit Berucksichtigung von

Zuverlassigkeitsinformation fur die einzelnen Codesymbole!

einfachste Teildecoder:

• Single–Parity–Check–Code

• Wiederholungscode (Repetition Code)

In den 60er Jahren weder theoretisch noch simulativ bei großen

Wortlangen und sehr vielen Iterationen analysierbar

Eher bescheidene Leistungsdaten bei handhabbaren kurzen Codes

Nicht vorgebbare und daher meist geringe minimale Hammingdistanz

⇒ als”schlechte“ Codes verworfen

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 45/50

Page 146: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — Gallager (1963)LDPC–Codes — Gallager (1963)

Iterativer Decodierprozeß mit Berucksichtigung von

Zuverlassigkeitsinformation fur die einzelnen Codesymbole!

einfachste Teildecoder:

• Single–Parity–Check–Code

• Wiederholungscode (Repetition Code)

In den 60er Jahren weder theoretisch noch simulativ bei großen

Wortlangen und sehr vielen Iterationen analysierbar

Eher bescheidene Leistungsdaten bei handhabbaren kurzen Codes

Nicht vorgebbare und daher meist geringe minimale Hammingdistanz

⇒ als”schlechte“ Codes verworfen

Fallen ab 1965 der Vergessenheit anheim!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 45/50

Page 147: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

Ahnlichkeiten iterativer Decodierverfahren von LDPC–Codes und

Turbo–Codes (MacKay 1996)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 46/50

Page 148: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

Ahnlichkeiten iterativer Decodierverfahren von LDPC–Codes und

Turbo–Codes (MacKay 1996)

Nun mogliche Simulationen bei sehr langen Wortlangen und sehr vielen

Iterationen zeigen ahnlich gute Leistungsfahigkeit wie bei Turbo–Codes

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 46/50

Page 149: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

Ahnlichkeiten iterativer Decodierverfahren von LDPC–Codes und

Turbo–Codes (MacKay 1996)

Nun mogliche Simulationen bei sehr langen Wortlangen und sehr vielen

Iterationen zeigen ahnlich gute Leistungsfahigkeit wie bei Turbo–Codes

Entwicklung von”Density Evolution“ zur Analyse und Optimierung von

LDPC–Codes (Richardson/Urbanke)

• Irregulare LDPC–Codes: unterschiedlich viele Symbole je

Prufgleichung und unterschiedlich viele Prufgleichungen je Symbol

• LDPC–Codes erreichen fur n → ∞ die Kanalkapazitat

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 46/50

Page 150: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

Ahnlichkeiten iterativer Decodierverfahren von LDPC–Codes und

Turbo–Codes (MacKay 1996)

Nun mogliche Simulationen bei sehr langen Wortlangen und sehr vielen

Iterationen zeigen ahnlich gute Leistungsfahigkeit wie bei Turbo–Codes

Entwicklung von”Density Evolution“ zur Analyse und Optimierung von

LDPC–Codes (Richardson/Urbanke)

• Irregulare LDPC–Codes: unterschiedlich viele Symbole je

Prufgleichung und unterschiedlich viele Prufgleichungen je Symbol

• LDPC–Codes erreichen fur n → ∞ die Kanalkapazitat

Schranken fur EXIT–Kurven fur LDPC–Codes unabhangig von den

speziellen Kanaleigenschaften (Huber/Land, Shamai/Sutzkover 2004)

⇒ Analytische Optimierung von LDPC–Codes wird moglich!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 46/50

Page 151: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 152: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 153: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

2

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 154: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

210

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 155: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

21020

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 156: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

2102030

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 157: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

2102030

40

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 158: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

2102030

40

100

10 log10(Eb/N0) in dB −→

BE

R−→

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 159: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

LDPC–Codes — WiederentdeckungLDPC–Codes — Wiederentdeckung

0 1 2 3 4 5 610

−5

10−4

10−3

10−2

10−1

100

Uncodiert

Iteration 1

2102030

40

100

10 log10(Eb/N0) in dB −→

BE

R−→

Theo

r.Gre

nze

,0,1

9dB

Lange 216 = 65536, Rate R = 1/2, AWGN–2ASK–Kanal

Das Tor zur Kanalkapazitat stand bereits 1963 weit offen!

Der Umweg erforderte 33 Jahre harter Arbeit!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 47/50

Page 160: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere ÜbertragungX Y

n × n Polar Matrix

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 161: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 162: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

0000

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 163: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

0000

Schrittweise Decodierung mit Entscheidungsruckkopplung moglich: O (n log(n))

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 164: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

0000

Schrittweise Decodierung mit Entscheidungsruckkopplung moglich: O (n log(n))⇒ Anwendung der Kettenregel fur die Transinformation(vgl. Huber / Wachsmann

”Codierte Modulation“ 1993)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 165: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

0000

Schrittweise Decodierung mit Entscheidungsruckkopplung moglich: O (n log(n))⇒ Anwendung der Kettenregel fur die Transinformation(vgl. Huber / Wachsmann

”Codierte Modulation“ 1993)

Beweis der Polarisierungseigenschaft und der Erreichbarkeit der

Kanalkapazitat anhand von”Extremes in Information Combining“

(Huber / Land 2004)

E {WER} = 2−√

nEp(R)

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 166: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

Polar Codes (Arikan 2007)Polar Codes (Arikan 2007)

10000000

11000000

10100000

11110000

10001000

11001100

1

101010

011111111

der Symboleunsichere Übertragung

sehr unsichereSymbole

sehr sichereSymbole

X Y

n × n Polar Matrix

0000

Schrittweise Decodierung mit Entscheidungsruckkopplung moglich: O (n log(n))⇒ Anwendung der Kettenregel fur die Transinformation(vgl. Huber / Wachsmann

”Codierte Modulation“ 1993)

Beweis der Polarisierungseigenschaft und der Erreichbarkeit der

Kanalkapazitat anhand von”Extremes in Information Combining“

(Huber / Land 2004)

E {WER} = 2−√

nEp(R)

Konstruktionsprinzip wie bei Reed–Muller–Code, jedoch Auswahl von

aktiven Zeilen fur Generatormatrix nicht nach dem Kriterium

max. MinimaldistanzJohannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 48/50

Page 167: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

ZusammenfassungZusammenfassung

Der Weg zur Kanalkapazitat wurde uber lange Zeit durch Fixierung auf

das Optimierungskriterium Minimaldistanz verstellt.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 49/50

Page 168: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

ZusammenfassungZusammenfassung

Der Weg zur Kanalkapazitat wurde uber lange Zeit durch Fixierung auf

das Optimierungskriterium Minimaldistanz verstellt.

Verknupfung von Zufall und Struktur fuhrt zusammen mit iterativen

Decodierverfahren schließlich zum Ziel.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 49/50

Page 169: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

ZusammenfassungZusammenfassung

Der Weg zur Kanalkapazitat wurde uber lange Zeit durch Fixierung auf

das Optimierungskriterium Minimaldistanz verstellt.

Verknupfung von Zufall und Struktur fuhrt zusammen mit iterativen

Decodierverfahren schließlich zum Ziel.

⇒ Dieser Weg ware durch die Beweistechnik der

Zufallscodierung in der Informationstheorie eigentlich

vorgezeichnet gewesen!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 49/50

Page 170: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

ZusammenfassungZusammenfassung

Der Weg zur Kanalkapazitat wurde uber lange Zeit durch Fixierung auf

das Optimierungskriterium Minimaldistanz verstellt.

Verknupfung von Zufall und Struktur fuhrt zusammen mit iterativen

Decodierverfahren schließlich zum Ziel.

⇒ Dieser Weg ware durch die Beweistechnik der

Zufallscodierung in der Informationstheorie eigentlich

vorgezeichnet gewesen!

Manchmal kann es Jahrzehnte dauern, bis die Zeit zur technischen

Umsetzung genialer Erfindungen reif wird.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 49/50

Page 171: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50

Page 172: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Nur Ingenieure mit umfassenden theoretischen Kenntnissen sind in der

Lage, die aktuelle Technik zu verstehen und davon ausgehend neue,

konkurrenzfahige Technik zu entwickeln.

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50

Page 173: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Nur Ingenieure mit umfassenden theoretischen Kenntnissen sind in der

Lage, die aktuelle Technik zu verstehen und davon ausgehend neue,

konkurrenzfahige Technik zu entwickeln.

Nichts ist praktischer als eine gute Theorie!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50

Page 174: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Nur Ingenieure mit umfassenden theoretischen Kenntnissen sind in der

Lage, die aktuelle Technik zu verstehen und davon ausgehend neue,

konkurrenzfahige Technik zu entwickeln.

Nichts ist praktischer als eine gute Theorie!

Digitale Signalverarbeitung und Softwarelosungen verkurzen den Weg von

der theoretischen Erkenntnis zum Produkt dramatisch:

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50

Page 175: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Nur Ingenieure mit umfassenden theoretischen Kenntnissen sind in der

Lage, die aktuelle Technik zu verstehen und davon ausgehend neue,

konkurrenzfahige Technik zu entwickeln.

Nichts ist praktischer als eine gute Theorie!

Digitale Signalverarbeitung und Softwarelosungen verkurzen den Weg von

der theoretischen Erkenntnis zum Produkt dramatisch:

Die Theorie ist der direkte Weg zur Praxis!

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50

Page 176: Wege, Umwege, Irrwege zur Kanalkapazität : Zur Geschichte der Entwicklung hocheffizienter digitaler Übertragungsverfahren

O

SchlussfolgerungenSchlussfolgerungen

Vielfaltige theoretischen Grundlagen moderner Ubertragungstechnik:

• Mathematik (Analysis, Funktionentheorie, Algebra, lineare Algebra,

diskrete Mathematik, Numerik, Stochastik usw.)

• Systemtheorie, Informations- und Codierungstheorie

• Digitale Signalverarbeitung

• Hochfrequenztechnik, Mikroelektronik

Nur Ingenieure mit umfassenden theoretischen Kenntnissen sind in der

Lage, die aktuelle Technik zu verstehen und davon ausgehend neue,

konkurrenzfahige Technik zu entwickeln.

Nichts ist praktischer als eine gute Theorie!

Digitale Signalverarbeitung und Softwarelosungen verkurzen den Weg von

der theoretischen Erkenntnis zum Produkt dramatisch:

Die Theorie ist der direkte Weg zur Praxis!

Was macht in diesem Umfeld ein Bachelor?

Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 50/50