(Network) Coding und Verbindungen zur Systemtheorie€¦ · (Network) Coding und Verbindungen zur...

Preview:

Citation preview

(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

Recommended