(Network) Coding und Verbindungen zur Systemtheorie€¦ · (Network) Coding und Verbindungen zur Systemtheorie Klassische Codierungstheorie Einf uhrung De nition Ein Block-Code uber

(Network) Coding und Verbindungen zur Systemtheorie

(Network) Coding und Verbindungen zurSystemtheorie

Anna-Lena Horlemann-Trautmann

Algorithmics Laboratory, EPFL, Schweiz

10. Februar 2016Elgersburg Workshop


Klassische Codierungstheorie

Einfuhrung



Einfuhrung

Klassische Codierungstheorie:

−→ −→

ReceiverSource(100111010100011)

Was, wenn Fehler wahrend der Ubertragung passieren?

=⇒ Konnen korrigiert werden, indem man Redundanz denDaten hinzufugt, Daten codiert.

1 / 1



Einfuhrung

Klassische Codierungstheorie:

−→ −→

ReceiverSource(100111010100011)

Was, wenn Fehler wahrend der Ubertragung passieren?

=⇒ Konnen korrigiert werden, indem man Redundanz denDaten hinzufugt, Daten codiert.

1 / 1



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



Einfuhrung



2 / 1



Einfuhrung



2 / 1



Einfuhrung



2 / 1



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



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



Einfuhrung

Definition


dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq






4 / 1



Einfuhrung

Definition


dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq






4 / 1



Einfuhrung

Definition


dH(r, c) := |{i | ri 6= ci}| r, c ∈ Fnq






4 / 1



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



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



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



Systemtheorie-Verbindungen




Der komplette Vorgang:

Manchmal konnen Decodierer und Retriever auch zusammen-gelegt werden.

7 / 1




Der komplette Vorgang:

Manchmal konnen Decodierer und Retriever auch zusammen-gelegt werden.

7 / 1




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




Systeme:

Input Output









=⇒ Interessant: Decodierer

8 / 1




Systeme:

Input Output









=⇒ Interessant: Decodierer8 / 1




Decodierer + Retriever:

Nachricht =argmin{dH(mG, r) | m ∈ Fkq}=argmin{||mG− r||H | m ∈ Fkq}

G ∈ Fk×nq Generatormatrixr ∈ Fnq empfangenes Wort

9 / 1




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




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




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




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







si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0




13 / 1







si+t+1 + Λ1si+t + · · ·+ Λtsi+1 = 0




13 / 1





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




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




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





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-Theorie

Einfuhrung



Einfuhrung

Network Coding

Das Multicast-Modell:

Alle Empfanger sollen (gleichzeitig) die selben Daten erhalten.

17 / 1



Einfuhrung

Network Coding

Das Multicast-Modell:

Alle Empfanger sollen (gleichzeitig) die selben Daten erhalten.

17 / 1



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



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



Einfuhrung

Problem: Mit linearem Codieren pflanzen sich Fehler imNetzwerk fort!

bb

+e

a

c

=⇒ Eine andere Metrik wird zum Dekodieren benotigt.

19 / 1



Einfuhrung


bb

+e

a

c


19 / 1



Einfuhrung


bb

+e

a

c


19 / 1



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



Einfuhrung

Definition






20 / 1



Einfuhrung

Definition






20 / 1



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



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



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



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



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







Uberblick Network Coding-Prozess:

25 / 1




Systeme:

Input Output


Kanal Codeword empfangenes Wort


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




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




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




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




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




Theorem








(αx3) ◦ (x3 − αx) = αx9 − α2x3

Nicht kommutativ!!

=⇒ Inverse Operation nennt man symbolische Divison.

29 / 1




Theorem








(αx3) ◦ (x3 − αx) = αx9 − α2x3

Nicht kommutativ!!=⇒ Inverse Operation nennt man symbolische Divison.

29 / 1




Auf zum linearisierten Berlekamp-Massey-Algorithmus!

30 / 1




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




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




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





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





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




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





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




Zweites Beispiel: Welch-Berlekamp-Algorithmus

36 / 1




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





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






Π(x) 0−Λ(x) x

].






38 / 1






Π(x) 0−Λ(x) x

].






38 / 1


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



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



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

Documents

(Network) Coding und Verbindungen zur Systemtheorie€¦ · (Network) Coding und Verbindungen zur Systemtheorie Klassische Codierungstheorie Einf uhrung De nition Ein Block-Code uber