View
1.467
Download
5
Embed Size (px)
Citation preview
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
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
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
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
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
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
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
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
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
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
O
InformationstheorieInformationstheorie
Beispiel: Symmetrischer Binarkanal
BER: Bit Error Ratio
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 7/50
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
O
InformationstheorieInformationstheorie
Transinformation, Kanalkapazitat:
Verringerung der Unsicherheit uber X durch Beobachtung von Y :
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 8/50
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
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
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
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
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
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
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
O
InformationstheorieInformationstheorie
Kapazitat des AWGN–Kanals:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50
O
InformationstheorieInformationstheorie
Kapazitat des AWGN–Kanals:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50
O
InformationstheorieInformationstheorie
Kapazitat des AWGN–Kanals:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50
O
InformationstheorieInformationstheorie
Kapazitat des AWGN–Kanals:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50
O
InformationstheorieInformationstheorie
Kapazitat des AWGN–Kanals:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 12/50
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
O
Algebraische BlockcodesAlgebraische Blockcodes
Konstruktion von Codes mittels
Mathematik in endlichen Korpern (Galoisfelder)
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 19/50
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
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
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
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
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
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
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
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
O
Algebraische BlockcodesAlgebraische Blockcodes
Optimierungsziel seit Hamming (1947):
moglichst große minimale Hammingdistanz δmin
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 21/50
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
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
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
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
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
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
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
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
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
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
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
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
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
O
Algebraische BlockcodesAlgebraische Blockcodes
Ursachen der beschrankten Leistungsfahigkeit algebraischerCodierverfahren:
optimale Maximum–Likelihood–Decodierung
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 24/50
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
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
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
O
FaltungscodesFaltungscodes
Scrambler (”Verwurfler“) fur Binarsequenzen:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 26/50
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
O
FaltungscodesFaltungscodes
Faltungscoder mit Rate 1/2:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50
O
FaltungscodesFaltungscodes
Faltungscoder mit Rate 1/n:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50
O
FaltungscodesFaltungscodes
Systematischer Faltungscoder mit Rate 1/n:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 27/50
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
O
Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50
O
Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50
O
Faltungscodes: Soft-Decision DecodingFaltungscodes: Soft-Decision Decoding
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 28/50
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
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
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
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
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
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
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
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
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
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
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
O
Faltungscodes: BeispielFaltungscodes: Beispiel
Faltungscode mit Rate R = 1/2:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50
O
Faltungscodes: BeispielFaltungscodes: Beispiel
Faltungscode mit Rate R = 1/2:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 31/50
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
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
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
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
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
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
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
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
O
Turbo–CodesTurbo–Codes
Parallele Verkettung von Faltungscodes:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50
O
Turbo–CodesTurbo–Codes
Parallele Verkettung von Faltungscodes:
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 33/50
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
O
Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart
Geschlossener Tunnel
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50
O
Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart
Geschlossener Tunnel ⇒ keine Konvergenz bei (1,1)!
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50
O
Turbo–Codes — EXIT ChartTurbo–Codes — EXIT Chart
Abstand zur Kanalkapazitat: Flache des Konvergenztunnels
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 38/50
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
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
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
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
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
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
O
LDPC–CodesLDPC–Codes
Low–Density–Parity–Check–Codes:
Prufgleichungen eines linearen Codes
Johannes Huber: Wege, Umwege, Irrwege zur Kanalkapazitat 41/50
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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