(Network) Coding und Verbindungen zur Systemtheorie
(Network) Coding und Verbindungen zurSystemtheorie
Anna-Lena Horlemann-Trautmann
Algorithmics Laboratory, EPFL, Schweiz
10. Februar 2016Elgersburg Workshop
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Klassische Codierungstheorie:
−→ −→
ReceiverSource(100111010100011)
Was, wenn Fehler wahrend der Ubertragung passieren?
=⇒ Konnen korrigiert werden, indem man Redundanz denDaten hinzufugt, Daten codiert.
1 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Klassische Codierungstheorie:
−→ −→
ReceiverSource(100111010100011)
Was, wenn Fehler wahrend der Ubertragung passieren?
=⇒ Konnen korrigiert werden, indem man Redundanz denDaten hinzufugt, Daten codiert.
1 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Einfachstes Beispiel – der Wiederholungs-Code:
Da (000100) naher an (000000) als an (111111) ist, decodiertder Empfanger als (000000) und erhalt so die Nachricht “no”.
2 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Einfachstes Beispiel – der Wiederholungs-Code:
Da (000100) naher an (000000) als an (111111) ist, decodiertder Empfanger als (000000) und erhalt so die Nachricht “no”.
2 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Einfachstes Beispiel – der Wiederholungs-Code:
Da (000100) naher an (000000) als an (111111) ist, decodiertder Empfanger als (000000) und erhalt so die Nachricht “no”.
2 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Einfachstes Beispiel – der Wiederholungs-Code:
Da (000100) naher an (000000) als an (111111) ist, decodiertder Empfanger als (000000) und erhalt so die Nachricht “no”.
2 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Definition
Ein Block-Code uber Fq der Lange n ist einfach eine Teilmengevon Fnq . Die Elemente des Codes nennt man Codeworter. Einlinearer Code ist ein Untervektorraum von Fnq .
Kanal-Modell
Sei c ∈ Fnq ein uber den Kanal gesendetes Codewort. Bei der
Ubertragung konnen additive Fehler vorkommen, dement-sprechend ist das empfangen Wort
r = c+ e
wobei e ∈ Fnq der Fehlervektor ist.
3 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Definition
Die Metrik, mit der die Anzahl der Fehler gemessen wird, istdie Hamming-Metrik:
dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq
Die Minimal-Hammingdistanz eines Codes C ist definiert als
dmin(C) := min{dH(b, c) | b, c ∈ C, b 6= c}.
Der Empfanger decodiert das empfangene Wort zumnachsten Codeword bzgl. der Hamming-Metrik.
Je großer die Minimaldistanz des Codes, desto mehr Fehlerkonnen korrigiert werden.
Tradeoff: Je mehr Redundanz hinzugefugt wird, destoschlechter wird die Ubertragungsrate.
4 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Definition
Die Metrik, mit der die Anzahl der Fehler gemessen wird, istdie Hamming-Metrik:
dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq
Die Minimal-Hammingdistanz eines Codes C ist definiert als
dmin(C) := min{dH(b, c) | b, c ∈ C, b 6= c}.
Der Empfanger decodiert das empfangene Wort zumnachsten Codeword bzgl. der Hamming-Metrik.
Je großer die Minimaldistanz des Codes, desto mehr Fehlerkonnen korrigiert werden.
Tradeoff: Je mehr Redundanz hinzugefugt wird, destoschlechter wird die Ubertragungsrate.
4 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Definition
Die Metrik, mit der die Anzahl der Fehler gemessen wird, istdie Hamming-Metrik:
dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq
Die Minimal-Hammingdistanz eines Codes C ist definiert als
dmin(C) := min{dH(b, c) | b, c ∈ C, b 6= c}.
Der Empfanger decodiert das empfangene Wort zumnachsten Codeword bzgl. der Hamming-Metrik.
Je großer die Minimaldistanz des Codes, desto mehr Fehlerkonnen korrigiert werden.
Tradeoff: Je mehr Redundanz hinzugefugt wird, destoschlechter wird die Ubertragungsrate.
4 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Definition
Die Metrik, mit der die Anzahl der Fehler gemessen wird, istdie Hamming-Metrik:
dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq
Die Minimal-Hammingdistanz eines Codes C ist definiert als
dmin(C) := min{dH(b, c) | b, c ∈ C, b 6= c}.
Der Empfanger decodiert das empfangene Wort zumnachsten Codeword bzgl. der Hamming-Metrik.
Je großer die Minimaldistanz des Codes, desto mehr Fehlerkonnen korrigiert werden.
Tradeoff: Je mehr Redundanz hinzugefugt wird, destoschlechter wird die Ubertragungsrate.
4 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Beispiel
Uber F3 = {0, 1, 2} definieren wir den linearen Code C derLange 4 und Dimension 2 mit der Generatormatrix
G =
(1 0 0 10 1 2 1
).
Der Code hat 32 = 9 Codeworter und Minimal-Hammingdistanz2.
Aquivalent konnen wir C als Kern der Kontrollmatrix
H =
(0 1 1 02 2 0 1
)definieren (mit GHT = 0).
5 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Beispiel
Uber F3 = {0, 1, 2} definieren wir den linearen Code C derLange 4 und Dimension 2 mit der Generatormatrix
G =
(1 0 0 10 1 2 1
).
Der Code hat 32 = 9 Codeworter und Minimal-Hammingdistanz2. Aquivalent konnen wir C als Kern der Kontrollmatrix
H =
(0 1 1 02 2 0 1
)definieren (mit GHT = 0).
5 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Einfuhrung
Hauptforschungsziele (Block-Codes):
1 Fur einen gegebenen Raum Fnq und Minimaldistanz, findedie besten Packungen bzgl. der Hamming-Metrik.=⇒ beste mogliche Ubertragungsrate bei gleicherFehlerkorrektur
2 Finde effiziente Decodieralgorithmen (moglicherweisezusammen mit Code-Konstruktionen).=⇒ schnellere Kommunikation
6 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Der komplette Vorgang:
Manchmal konnen Decodierer und Retriever auch zusammen-gelegt werden.
7 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Der komplette Vorgang:
Manchmal konnen Decodierer und Retriever auch zusammen-gelegt werden.
7 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Systeme:
Input Output
Encoder Nachricht Codewort
Kanal Codewort empfangenes Wort
Decodierer empfangenes Wort Codewort
Retriever Codeword Nachricht
Diese Systeme sind alle diskret.
Als Encoder wird oft eine lineare Abbildung von Fkq nachFnq genommen.
Der Retriever ist die inverse Abbildung vom Encoder unddaher auch linear.
Kanal ist stochastisches System (Fehler folgt Wahrschein-lichkeitsverteilung).
=⇒ Interessant: Decodierer
8 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Systeme:
Input Output
Encoder Nachricht Codewort
Kanal Codewort empfangenes Wort
Decodierer empfangenes Wort Codewort
Retriever Codeword Nachricht
Diese Systeme sind alle diskret.
Als Encoder wird oft eine lineare Abbildung von Fkq nachFnq genommen.
Der Retriever ist die inverse Abbildung vom Encoder unddaher auch linear.
Kanal ist stochastisches System (Fehler folgt Wahrschein-lichkeitsverteilung).
=⇒ Interessant: Decodierer
8 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Systeme:
Input Output
Encoder Nachricht Codewort
Kanal Codewort empfangenes Wort
Decodierer empfangenes Wort Codewort
Retriever Codeword Nachricht
Diese Systeme sind alle diskret.
Als Encoder wird oft eine lineare Abbildung von Fkq nachFnq genommen.
Der Retriever ist die inverse Abbildung vom Encoder unddaher auch linear.
Kanal ist stochastisches System (Fehler folgt Wahrschein-lichkeitsverteilung).
=⇒ Interessant: Decodierer8 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Decodierer + Retriever:
Nachricht =argmin{dH(mG, r) | m ∈ Fkq}=argmin{||mG− r||H | m ∈ Fkq}
G ∈ Fk×nq Generatormatrixr ∈ Fnq empfangenes Wort
9 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Verschiedene Dekodieralgorithmen:
Mit der Hilfe der Kontrollmatrix (bzw. Syndromen), z.B.Berlekamp-Massey-Algorithmus.
Mit Polynom-Interpolation, z.B. Welch-Berlekamp-Algorithmus.
Mit Belief-Propagation-Algorithmus.
. . .
10 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Idee von Berlekamp-Massey-Algorithmus:
Sei α ∈ Fq Einheitswurzel und C ⊆ Fnq ein BCH-Code mitKontrollmatrix
H =
1 α α2 . . . αn
1 α2 α4 . . . α2n
......
1 αn−k α2(n−k) . . . αn(n−k)
und sei r = c+ e das empfangene Wort mit
e = (0...0ei1 ...0...ei2 ...0...eit0...0).
Berechne die Syndrome
(s1, s2, . . . , sn−k) = rHT = cHT + eHT = eHT .
11 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Idee von Berlekamp-Massey-Algorithmus:
H =
(1 α α2 . . . αn
...
)
Definiere die Error-Locators X` := α−i` und dasError-Locator-Polynom
Λ(z) =
t∑i=0
Λizi :=
t∏z=1
(z −X`).
Mit Newton-Gleichungen bekommt man
si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0
fur i = 1, . . . , n− k − t+ 1.
12 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Berlekamp-Massey-Algorithmus:
Finde Polynom Λ(x) =∑
Λixi vom kleinsten Grad t, s.d.
si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0
fur i = 0, . . . , n− k − t.Aquivalent: Finde das kurzeste linear ruckgekoppelteSchieberegister, so dass der Output s1, s2, . . . , sn−k ist.(Λ(D) ist Ruckkopplungspolynom des Schieberegisters.)
=⇒ irreduzible Transferfunktion / minimale Realisierung
Kann mit iterativem Algorithmus effizient berechnetwerden (siehe Wikipedia o.a.).
13 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Berlekamp-Massey-Algorithmus:
Finde Polynom Λ(x) =∑
Λixi vom kleinsten Grad t, s.d.
si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0
fur i = 0, . . . , n− k − t.Aquivalent: Finde das kurzeste linear ruckgekoppelteSchieberegister, so dass der Output s1, s2, . . . , sn−k ist.(Λ(D) ist Ruckkopplungspolynom des Schieberegisters.)
=⇒ irreduzible Transferfunktion / minimale Realisierung
Kann mit iterativem Algorithmus effizient berechnetwerden (siehe Wikipedia o.a.).
13 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Berlekamp-Massey-Algorithmus:
Finde Polynom Λ(x) =∑
Λixi vom kleinsten Grad t, s.d.
si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0
fur i = 0, . . . , n− k − t.Aquivalent: Finde das kurzeste linear ruckgekoppelteSchieberegister, so dass der Output s1, s2, . . . , sn−k ist.(Λ(D) ist Ruckkopplungspolynom des Schieberegisters.)
=⇒ irreduzible Transferfunktion / minimale Realisierung
Kann mit iterativem Algorithmus effizient berechnetwerden (siehe Wikipedia o.a.).
13 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Berlekamp-Massey-Algorithmus:
Finde Nullstellen −i1, . . . ,−it von Λ(x) ( mod q − 1).
Mit Kenntnis der Fehlerpositionen i1, i2, . . . , it konnen wirdann die Fehlerwerte eij finden, indem wir das lineareGleichungssystem
(ei1 , . . . , eit)
αi1 α2i1 . . . α(n−k)i1
αi2 α2i2 . . . α(n−k)i2
...
αit α2it . . . α(n−k)it
= (s1, . . . , sn−k)
losen.
Dann e = (0...0ei1 ...0...ei2 ...0...eit0...0) und c = r − e.
14 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Beispiel
Sei α ∈ F24 primitive Einheitswurzel mit α4 = α+ 1. Wirbetrachten F24 = F2[α] und den BCH-Code der Lange n = 11.Fur ein empfangenes r berechnen wir die Syndromfolge
(s1, s2, . . . , s7) = (1, 1, 0, 1, 1, 0, 1).
Der Berlekamp-Massey-Algorithmus ermitteltΛ(x) = x2 + x+ 1, d.h. das Schieberegister ist von der Form
.
15 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Beispiel fortgesetzt
Wir faktorisieren
Λ(x) = x2 + x+ 1 = (x− α5)(x− α10).
Also Fehler in Positionen i2 = −5 ≡ 10 und i1 = −10 ≡ 5.
Wir losen
(e5, e10)
(α5 α10 . . . α35
α10 α20 . . . α70
)= (1101101)
⇐⇒ (e5, e10) = (1, 1).
Also Fehlervektor e = (00000100001) und c = r − e.
16 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Klassische Codierungstheorie
Systemtheorie-Verbindungen
Beispiel fortgesetzt
Wir faktorisieren
Λ(x) = x2 + x+ 1 = (x− α5)(x− α10).
Also Fehler in Positionen i2 = −5 ≡ 10 und i1 = −10 ≡ 5.Wir losen
(e5, e10)
(α5 α10 . . . α35
α10 α20 . . . α70
)= (1101101)
⇐⇒ (e5, e10) = (1, 1).
Also Fehlervektor e = (00000100001) und c = r − e.
16 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Network Coding
Das Multicast-Modell:
Alle Empfanger sollen (gleichzeitig) die selben Daten erhalten.
17 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Network Coding
Das Multicast-Modell:
Alle Empfanger sollen (gleichzeitig) die selben Daten erhalten.
17 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
“Codieren ist besser als Weiterleiten”
Das Schmetterling-Netzwerk mit Weiterleiten:
R2
R1
a
a
a
aa
b b
b
a
R2 erhalt a und b, aber R1 erhalt nur a.=⇒ 2 Zeiteinheiten benotigt, um a, b an beide Empfanger zu
senden.
18 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
“Codieren ist besser als Weiterleiten”
Das Schmetterling-Netzwerk mit linearem Codieren:
R2
R1
a
a
a
a+ba+b
b b
b
a+b
Beide Empfanger konnen a, b rekonstruieren.=⇒ Nur 1 Zeiteinheit benotigt, um a, b an beide Empfanger zu
senden.
18 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Problem: Mit linearem Codieren pflanzen sich Fehler imNetzwerk fort!
bb
+e
a
c
=⇒ Eine andere Metrik wird zum Dekodieren benotigt.
19 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Problem: Mit linearem Codieren pflanzen sich Fehler imNetzwerk fort!
bb
+e
a
c
=⇒ Eine andere Metrik wird zum Dekodieren benotigt.
19 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Problem: Mit linearem Codieren pflanzen sich Fehler imNetzwerk fort!
bb
+e
a
c
=⇒ Eine andere Metrik wird zum Dekodieren benotigt.
19 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Definition
Ein Rang-Metrik-Code ist definiert als eine Teilmenge vonFm×nq . Die Rang-Metrik ist definiert als
dR(A,B) := Rang(A−B), A,B ∈ Fm×nq .
Die Minimal-Rangdistanz eines Codes C ⊆ Fm×nq ist definiert als
dmin,R(C) := min{dR(A,B) | A,B ∈ C,A 6= B}.
Codeworter sind jetzt Matrizen, wobei jeder Zeilen-Vektorentlang einer ausgehenden Kante vom Sender geschickt wird.
20 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Definition
Ein Rang-Metrik-Code ist definiert als eine Teilmenge vonFm×nq . Die Rang-Metrik ist definiert als
dR(A,B) := Rang(A−B), A,B ∈ Fm×nq .
Die Minimal-Rangdistanz eines Codes C ⊆ Fm×nq ist definiert als
dmin,R(C) := min{dR(A,B) | A,B ∈ C,A 6= B}.
Codeworter sind jetzt Matrizen, wobei jeder Zeilen-Vektorentlang einer ausgehenden Kante vom Sender geschickt wird.
20 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Definition
Ein Rang-Metrik-Code ist definiert als eine Teilmenge vonFm×nq . Die Rang-Metrik ist definiert als
dR(A,B) := Rang(A−B), A,B ∈ Fm×nq .
Die Minimal-Rangdistanz eines Codes C ⊆ Fm×nq ist definiert als
dmin,R(C) := min{dR(A,B) | A,B ∈ C,A 6= B}.
Codeworter sind jetzt Matrizen, wobei jeder Zeilen-Vektorentlang einer ausgehenden Kante vom Sender geschickt wird.
20 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Kanal-Modell (koharentes Network Coding)
Sei U ∈ Fm×nq ein Codewort, welches uber den Kanal geschicktwurde. Ein empfangenes Wort ist von der Form
R = AU + E
wobei A ∈ Fm×mq die Linearkombinationen der inneren Knoten(von Sender und Empfanger gekannt) reprasentiert, undE ∈ Fm×nq die Fehlermatrix ist.
Der Empfanger dekodiert zum nachsten Codewort zu A−1Rbzgl. der Rang-Metrik.
21 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Kanal-Modell (koharentes Network Coding)
Sei U ∈ Fm×nq ein Codewort, welches uber den Kanal geschicktwurde. Ein empfangenes Wort ist von der Form
R = AU + E
wobei A ∈ Fm×mq die Linearkombinationen der inneren Knoten(von Sender und Empfanger gekannt) reprasentiert, undE ∈ Fm×nq die Fehlermatrix ist.
Der Empfanger dekodiert zum nachsten Codewort zu A−1Rbzgl. der Rang-Metrik.
21 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Verbindung zu Block-Codes:
Uber Fmq ∼= Fqm konnen wir Matrizen in Fm×nq als Vektorenin Fnqm darstellen.
So kann jeder Block-Code C ⊆ Fnqm einen Rang-Metrik-Code erzeugen.
So konnen lineare Rang-Metrik-Codes definiert werden(erzeugt durch lineare Block-Codes).
22 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Beispiel
Sei F22∼= F2[α] mit α2 + α+ 1 = 0. Der lineare Block-Code mit
Generatormatrix G = (1 α 1) ist
C = {(0 0 0), (1 α 1), (α α+ 1 α), (α+ 1 1 α+ 1)} ⊆ F322 .
Als Rang-Metrik-Code C∗ ⊆ F2×32 erhalten wir
C∗ =
{(0 0 00 0 0
),
(1 0 10 1 0
),
(0 1 01 1 1
),
(1 1 11 0 1
)}mit Rang-Minimaldistanz 2.
23 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Einfuhrung
Hauptforschungsziele (koharentes Network Coding):
Fur einen gegebenen Raum Fm×nq und Minimaldistanz desCodes, finde die beste Packung bzgl. der Rang-Metrik.=⇒ beste mogliche Ubertragungsrate bei gleicherFehlerkorrektur
Finde effiziente Decodieralgorithmen (moglicherweisezusammen mit Code-Konstruktionen).=⇒ schnellere Kommunikation
24 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Uberblick Network Coding-Prozess:
25 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Systeme:
Input Output
Encoder Nachricht Codewort
Kanal Codeword empfangenes Wort
Decodierer empfangenes Wort Codewort
Retriever Codewort Nachricht
Durch die Beziehung zu Block-Codes, konnen fur Encoderund Retriever wieder linear Abbildungen verwendetwerden.
Viele Decodieralgorithmen sind ebenfalls analog zu denenin der Hamming-Metrik.
Fehlermatrix (im Kanal) folgt Wahrscheinlichkeits-verteilung.
26 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Decodierer + Retriever:
Nachricht =argmin{dR(mG,ϕ−1A (r)) | m ∈ Fkqm}=argmin{||mG− ϕ−1A (r)||R | m ∈ Fkqm}=argmin{||ϕA(mG)− r||R | m ∈ Fkqm}
G ∈ Fk×nqm Generatormatrixr ∈ Fnqm empfangenes WortϕA : Fnqm → Fnqm reprasentiert Linearkombinationen imNetzwerk (entspricht A : Fm×nq → Fm×nq )
27 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Resultate aus der klassischen Codierungstheorie mit normalenPolynomen werden fur die Rang-Metrik-Codes in Ring derlinearisierten Polynome ubertragen .
Definition
Ein linearisiertes Polynom in Fqm [x] ist von der Form
f(x) =
d∑i=0
fixqi .
Theorem
Die linearisierten Polynome in Fqm [x] bilden einen Ring mit derublichen Polynomaddition und Komposition als zweiterOperation.
28 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Resultate aus der klassischen Codierungstheorie mit normalenPolynomen werden fur die Rang-Metrik-Codes in Ring derlinearisierten Polynome ubertragen .
Definition
Ein linearisiertes Polynom in Fqm [x] ist von der Form
f(x) =
d∑i=0
fixqi .
Theorem
Die linearisierten Polynome in Fqm [x] bilden einen Ring mit derublichen Polynomaddition und Komposition als zweiterOperation.
28 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Theorem
Linearisierte Polynome in Fqm [x] sind Fq-lineareAbbildungen.
Die Nullstellen eines linearisierten Polynoms bilden einenFq-Vektorraum.
Zu jeden Fq-Vektorraum V ⊆ Fqm ist∏β∈V (x− β) ein
linearisiertes Polynom.
Beispiel in F32∼= F3[α]
Das linearisierte Polynom x3−αx hat Nullstellen 0, α2, 2α2.
Komposition: (x3 − αx) ◦ (αx3) = α3x9 − α2x3
(αx3) ◦ (x3 − αx) = αx9 − α2x3
Nicht kommutativ!!=⇒ Inverse Operation nennt man symbolische Divison.
29 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Theorem
Linearisierte Polynome in Fqm [x] sind Fq-lineareAbbildungen.
Die Nullstellen eines linearisierten Polynoms bilden einenFq-Vektorraum.
Zu jeden Fq-Vektorraum V ⊆ Fqm ist∏β∈V (x− β) ein
linearisiertes Polynom.
Beispiel in F32∼= F3[α]
Das linearisierte Polynom x3−αx hat Nullstellen 0, α2, 2α2.
Komposition: (x3 − αx) ◦ (αx3) = α3x9 − α2x3
(αx3) ◦ (x3 − αx) = αx9 − α2x3
Nicht kommutativ!!
=⇒ Inverse Operation nennt man symbolische Divison.
29 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Theorem
Linearisierte Polynome in Fqm [x] sind Fq-lineareAbbildungen.
Die Nullstellen eines linearisierten Polynoms bilden einenFq-Vektorraum.
Zu jeden Fq-Vektorraum V ⊆ Fqm ist∏β∈V (x− β) ein
linearisiertes Polynom.
Beispiel in F32∼= F3[α]
Das linearisierte Polynom x3−αx hat Nullstellen 0, α2, 2α2.
Komposition: (x3 − αx) ◦ (αx3) = α3x9 − α2x3
(αx3) ◦ (x3 − αx) = αx9 − α2x3
Nicht kommutativ!!=⇒ Inverse Operation nennt man symbolische Divison.
29 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Auf zum linearisierten Berlekamp-Massey-Algorithmus!
30 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Lemma
Wenn E ∈ Fm×nq Rang t hat, gibt es A ∈ Fm×tq , B ∈ Ft×nq mit
E = AB.
(Eindeutig bis auf GLt-Operation in Mitte.)
Isomorph: e = aB mit e ∈ Fnqm , a ∈ FtqmAlle Elemente in 〈a1, . . . , at〉Fq sind Nullstellen eineslinearisierten Polynoms Λ(x) vom q-Grad t.
Λ(x) =∑t
i=0 fixqi nennt man Error-Span-Polynom.
31 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Lemma
Wenn E ∈ Fm×nq Rang t hat, gibt es A ∈ Fm×tq , B ∈ Ft×nq mit
E = AB.
(Eindeutig bis auf GLt-Operation in Mitte.)
Isomorph: e = aB mit e ∈ Fnqm , a ∈ FtqmAlle Elemente in 〈a1, . . . , at〉Fq sind Nullstellen eineslinearisierten Polynoms Λ(x) vom q-Grad t.
Λ(x) =∑t
i=0 fixqi nennt man Error-Span-Polynom.
31 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Adaption von Berlekamp-Massey-Algorithmus:
Reprasentiere den Gabidulin-Code C ⊆ Fm×nq alsBlock-Code in Fnqm mit Kontrollmatrix
H =
1 α α2 . . . αn
1 αq α2q . . . αnq
......
1 αqn−k−1
α2qn−k−1. . . αnq
n−k−1
.
Reprasentiere die empfangene Matrix R = AU + E ∈ Fm×nq
als r = ϕA(c) + e ∈ Fnqm , wobei Rang(E) = t.
Berechne die Syndrome (s1, s2, . . . , sn−k) = rHT = eHT .
32 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Adaption von Berlekamp-Massey-Algorithmus:
Finde das linearisierte Polynom Λ(x) =∑
Λixqi ∈ Fqm [x]
vom kleinsten Grad, s.d.
Λ0si+t + Λ1sqi+t−1 + Λ2s
q2
i+t−2 + · · ·+ Λtsqt
i = 0
fur i = 0, . . . , n− k − t.
Bestimmte eine Basis {a1, . . . , at} des Nullstellen-Raumsvon Λ(x).
Lose das uber Fq expandierte Gleichungssystem
(a1, . . . , at)B︸ ︷︷ ︸E
HT = (s1, . . . , sn−k).
Decodiere zu U = A−1(R− E).
33 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Adaption von Berlekamp-Massey-Algorithmus:
Finde das linearisierte Polynom Λ(x) =∑
Λixqi ∈ Fqm [x]
vom kleinsten Grad, s.d.
Λ0si+t + Λ1sqi+t−1 + Λ2s
q2
i+t−2 + · · ·+ Λtsqt
i = 0
fur i = 0, . . . , n− k − t.Bestimmte eine Basis {a1, . . . , at} des Nullstellen-Raumsvon Λ(x).
Lose das uber Fq expandierte Gleichungssystem
(a1, . . . , at)B︸ ︷︷ ︸E
HT = (s1, . . . , sn−k).
Decodiere zu U = A−1(R− E).
33 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Beispiel
Wir betrachten F25 = F2[α] und haben die Syndromfolge
(s1, s2, s3, s4) = (α2 + 1, α3 + 1, α5 + 1, α9 + 1).
Der Berlekamp-Massey-Typ-Algorithmus ermittelt
Λ(x) = x4 + (α2 + α+ 1)x2 + (α2 + α)x.
Dies entspricht keinem linear ruckgekoppeltem Schieberegister,aber dem q-analogen eines solchen:
34 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Beispiel fortgesetzt
Die Nullstellen von
Λ(x) = x4 + (α2 + α+ 1)x2 + (α2 + α)x
sind {0, 1, α, α+ 1} = 〈1, α〉F2 . Dann konnen wir
(1, α)BHT = (α2 + 1, α3 + 1, α5 + 1, α9 + 1)
uber F2 losen, E = (1, α)B rekonstruieren und somit decodieren.
35 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Zweites Beispiel: Welch-Berlekamp-Algorithmus
36 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Welch-Berlekamp-Algorithmus (linearisiert):
Betrachte einen Gabidulin-Code C ⊆ Fnqm mitGeneratormatrix
G =
g1 g2 . . . gn
gq2
1 gq2
2 . . . gq2
n...
...
gqk−1
1 gqk−1
2 . . . gqk−1
n
und das empfangene Wort r = (r1, r2, . . . , rn) ∈ Fnqm .
Erstelle das linearisierte Lagrange-Polynom Λ(x), s.d.
Λ(gi) = ri
und das linearisierte Annullatorpolynom Π(x), s.d.
Π(gi) = 0.
37 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Welch-Berlekamp-Algorithmus (linearisiert):
Erstelle Modul M (uber dem Ring der linearisiertenPolynome) mit der Zeilen-Basis[
Π(x) 0−Λ(x) x
].
Finde minimale (reduzierte) Basis (b1 b2), (b′1 b′2) fur M
(bzgl. des (0, k − 1)-gewichteten q-Grads).
Dann ist b′1 ◦−1 b′2 die dekodierte Nachricht.
=⇒ Modellierung in Moduln von minimalem Grad= minimale Zustandsdarstellung
=⇒ kann mit linearisiertem Euklid oder Grobnerbasenberechnet werden
38 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Welch-Berlekamp-Algorithmus (linearisiert):
Erstelle Modul M (uber dem Ring der linearisiertenPolynome) mit der Zeilen-Basis[
Π(x) 0−Λ(x) x
].
Finde minimale (reduzierte) Basis (b1 b2), (b′1 b′2) fur M
(bzgl. des (0, k − 1)-gewichteten q-Grads).
Dann ist b′1 ◦−1 b′2 die dekodierte Nachricht.
=⇒ Modellierung in Moduln von minimalem Grad= minimale Zustandsdarstellung
=⇒ kann mit linearisiertem Euklid oder Grobnerbasenberechnet werden
38 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Network Coding-Theorie
Systemtheorie-Verbindungen
Welch-Berlekamp-Algorithmus (linearisiert):
Erstelle Modul M (uber dem Ring der linearisiertenPolynome) mit der Zeilen-Basis[
Π(x) 0−Λ(x) x
].
Finde minimale (reduzierte) Basis (b1 b2), (b′1 b′2) fur M
(bzgl. des (0, k − 1)-gewichteten q-Grads).
Dann ist b′1 ◦−1 b′2 die dekodierte Nachricht.
=⇒ Modellierung in Moduln von minimalem Grad= minimale Zustandsdarstellung
=⇒ kann mit linearisiertem Euklid oder Grobnerbasenberechnet werden
38 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Zusammenfassung und Ausblick
(Network) Coding und Verbindungen zur Systemtheorie
Zusammenfassung und Ausblick
Zusammenfassung
Einfuhrung klassische Codierungstheorie(Hamming-Metrik)
Einfuhrung koharentes Network Coding (Rang-Metrik)
Beispiele von verschiedenen Systemen:
Encoder, Kanal, Decodierer, RetrieverBerlekamp-Massey-Decodieralgorithmus (klassisch undlinearisiert)Welch-Berlekamp-Decodieralgorithmus (linearisiert)
Haufige Technik: Minimale Zustandsdarstellung /Irreduzible Transferfunktion
39 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Zusammenfassung und Ausblick
Ausblick in andere Bereiche
Belief-Propagation-Algorithmus (System mit Feedback, wasstabilisiert werden soll)
Faltungscodes (Encoder ist System mit Feedback)
Physical Layer Coding / Gitter-Codierungstheorie (uberRn oder Cn mit Euklidischer Metrik)
Coding uber Fading Channels
Danke fur die Aufmerksamkeit!Fragen? – Kommentare?
40 / 1
(Network) Coding und Verbindungen zur Systemtheorie
Zusammenfassung und Ausblick
Ausblick in andere Bereiche
Belief-Propagation-Algorithmus (System mit Feedback, wasstabilisiert werden soll)
Faltungscodes (Encoder ist System mit Feedback)
Physical Layer Coding / Gitter-Codierungstheorie (uberRn oder Cn mit Euklidischer Metrik)
Coding uber Fading Channels
Danke fur die Aufmerksamkeit!Fragen? – Kommentare?
40 / 1