Codes on Graphs: Normal Realizations

Codes on Graphs: Normal Realizations
Autor: G. David Forney, Jr.
Seminarvortrag von
Madeleine Leidheiser und Melanie Reuter
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Inhaltsverzeichnis
●
Einführung
•
•
●
Graphendarstellungen
•
•
•
●
Motivation
Einleitung
Trellis
Factor Graph
Normal Graph
Algorithmus
•
•
•
Cut-Set Bound
Sum-Product Algorithmus
Belief-Propagation
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Motivation
Ausgangspunkt:
Senden von codierten (binären) Nachrichten über einen
Kanal, dabei können die Nachrichten beschädigt werden
➔
Algorithmus zur Fehlerbehebung beim Decodieren
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
Definition:
Eine generalized state realization besteht aus symbolvariables, state-variables und constraints.
➔Darstellung
für einen Code
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
Beispiel:
(8,4,4) Hamming Code,
allg.: (n, k, d) Code
n = 8 – Länge der Codewörter/ Anzahl der symbol variables
k = 4 – Anzahl der information Bits
d = 4 – Hamming Distanz
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
4 constraints: ergeben die parity-check Matrix H
y 1 y 2 y 3 y 4 =0
y 2 y 4  y5  y7 =0
y 3 y 4  y5  y6 =0
y 5 y 6 y 7  y8 =0

1
0
H =
0
0
Codes on Graphs: Normal Realizations
1
1
0
0
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1

Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
Decodierung: parity-check Matrix H
wissen: gültige Codewörter erfüllen
H⋅y = 0
Codierung: generator Matrix G
Generierung von gültigen Codewörtern:
In unserem Beispiel:
8
y = u ⋅G
y∈F 2  und u∈F 2
Codes on Graphs: Normal Realizations
T
4
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
allgemein gilt:
T
G ⋅H = 0
hier: der (8,4,4) – Code ist selbst-dual
➔
G=H

1
G = 0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1

Die 4 Zeilen werden Generatoren genannt.
Jede Linearkombination erzeugt ein zulässiges Codewort.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
Definition:
span eines Codewortes = Intervall vom ersten bis zum
letzten Eintrag in der Matrix, der ungleich 0 ist.
minimum-span generator Matrix = Menge von k linear
unabhängiger Generatoren mit kürzest möglicher effektiver
Länge (=> trellis-oriented generator Matrix)
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
Theorem:
Eine Menge von k linear unabhängiger generators ist eine
minimum-span generator Matrix genau dann, wenn die
Start- und Endzeiten aller spans unterschiedlich sind.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Motivation | Einleitung
Einleitung
➔
G ist bereits eine minimum-span generator Matrix
Nebenstehende Matrix ist keine solche Matrix

1
0
G =
0
0
1
1
0
0
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1
 
Codes on Graphs: Normal Realizations
1
0
G' =
1
0
1
1
1
0
1
0
0
0
1
1
0
0
0
1
1
1
0
0
1
1
0
1
0
1
0
0
0
1

Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
0
0
0
1
0
1
1
1
1
0
0
0
1
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
0
0
0
1
1
0
1
1
0
1
1
1
0
1
0
0
0
y 1 y 2 y 3 y 4 =0
1
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
0,0,0 ,0
1,1,1 ,1
Codes on Graphs: Normal Realizations
y 1 y 2 y 3  y 4=0
y 2 y 4  y5  y7 =0
y 3 y 4  y5  y6 =0
y 5 y 6 y 7  y8 =0
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
0
0
0
1
0
1
1
1
Codes on Graphs: Normal Realizations
y 1 y 2 y 3  y 4=0
y 2 y 4  y5  y7 =0
y 3 y 4  y5  y6 =0
y 5 y 6 y 7  y8 =0
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
0
0
1
0
1
0
0
1
1
1
1
0
1
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
0
1
0
1
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Trellis
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Factor Graph
u1
u2
C
C
C
C
C
C
y1
y2
y3
y4
y5
Y6
C
C
C
C
C
C
y1
y2
y3
y4
y5
Y6
C
C
C
C
u4
u3
C
C
Codes on Graphs: Normal Realizations
C
y7
C
y7
C
y8
C
y8
C
Madeleine Leidheiser und Melanie Reuter
C
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Normal Graph
Definition:
Ein normal Graph ist ein Graph, in dem jede symbol variable Grad 1
und jede state variable Grad 2 hat.
Symbol variables werden durch einen dongle dargestellt, state
variables als Kanten.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Trellis | Factor Graph | Normal Graph
Normal Graph
1
C
C
C
3
2
3
2
C
Codes on Graphs: Normal Realizations
C
2
C
1
C
Madeleine Leidheiser und Melanie Reuter
C
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
Y F ={ y 5, y 6 , y 7 , y8 }
Y P ={y 1, y 2 , y 3 , y 4 }
CP
●

CF
Entfernen einer Kante teilt Graphen in “Past” und
“Future” auf
●
Y
●
Y
●
CP
: constraints von Past
●
CF
: constraints von Future
P
: symbol variables von Past
F
:symbol variables von Future
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
Für einen Wert s j der state variable

besteht die
Menge der mit s j konsistenten Codewörter aus
Y P(s j)
Y F( s j )
Y
CP
Codes on Graphs: Normal Realizations
Y
F
P

CF
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
Definition:
Cut Set: Minimale Menge von Kanten, die einen Graph in
zwei unverbundene Untergraphen aufteilt.
Lemma:
Ein Graph ist kreisfrei
Codes on Graphs: Normal Realizations
jede Kante ist ein Cut set
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
Theorem: Cut-set-bound
Gegeben sei eine graphische kreisfreie Realisierung
eines Codes C und ein cut-set X, dann ist die Größe
des Alphabets (hier (0,1)
) von unten begrenzt
n size eines trellis an
durch die minimal state space
der selben Trennstelle.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
C
C
C
C
C
C
C
C
Die Komplexität kreisfreier Graphen
ist von unten beschränkt.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Cut-Set Bound
(24,12,8) Golay Code
8
8
8
8
8
8
8
4
4
4
4
4
4
4
2 8 =256
4
2 =16
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus
Sum-Product Algorithmus
Entwickeln den Algorithmus auf einem kreisfreien normal
graph als APP (= a posteriori probability) Decodierung.
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus
Sum-Product Algorithmus
Notationen:
•
Menge der symbol variables:
•
erhaltenes Wort:
•
Codewort: y = { yi , i∈I }
{Y i , i ∈ I }
r = {r i , i ∈ I }
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus
Sum-Product Algorithmus
•
likelihood Vektoren {{ p r i ∣ y i , y i ∈ i} , i∈I } , wobei  i das
Alphabet von
•
Yi
ist
likelihood des Codewortes y:
p r ∣ y =
∏ i∈ I p r i∣y i 
(komponentenweises Produkt)
•
APPs { p  y ∣ r  , y∈C }
•
Teilmenge der Codewörter, in denen die symbol variable Y i
den Wert y i ∈ i annimmt: C i  yi 
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus
Sum-Product Algorithmus
Annahme: gleichwahrscheinliche Codewörter
➔Bayes
Gesetz
p  y ∣ r =
p r ∣ y p y 
∝ p r ∣ y  , y∈C
p r 
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus
Sum-Product Algorithmus
➔
APP Vektor
pY i = yi∣r=
∑y∈C  y  p y∣r ∝∑y∈C  y  p r∣y 
i
i
i
i
=∑ y∈C  y  ∏i ´ ∈I p r i ´∣yi ´  , y i ∈ i
i
Codes on Graphs: Normal Realizations
i
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Genauso für states:
C j  s j  Teilmenge der Codewörter, die konsistent sind mit der
state variable  j , die den Wert s j aus dem Alphabet S j
annimmt.
p   j = s j ∣ r  ∝ ∑ y∈C  s  ∏ i∈ I p ri∣y i ,
j
Codes on Graphs: Normal Realizations
j
s j ∈S j
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Es gibt zwei grundlegende Regeln für den Algorithmus:
1. Past-future decomposition rule
2. Sum-product update rule
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Past – future decomposition rule:
C j s j = Y
∣P
 s j × Y
∣F
 s j
Cartesian-product distributive law:
Für X, Y disjunkte, diskrete Mengen und f(x) und g(y) zwei
Funktionen, die auf X und Y definiert sind, gilt:
∑ x , y ∈ X ×Y
f  x  g  y =  ∑ x∈ X f  x  ∑ y∈Y g  y
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Past – future decomposition rule für state variables:
p  j = s j ∣ r  ∝

∑y
∣F
∈Y ∣F  s j 
∏i ∈I
F
p r i ∣ y i   
∑y
∣P
∈Y ∣F  s j 
∏i∈ I
P
p ri ∣ y i 
∝ p  j =s j ∣ r ∣P  p  j =s j ∣ r ∣F 
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Past – future decomposition rule für symbol variables:
p Y i = yi ∣ r  ∝
p r i ∣ yi 
∑
y ∈C i  y i 
∏i ´≠i p r i ´
∣ yi ´ 

∝ p y i ∣ r i  p  yi ∣ r ∣i ´≠i 
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Beispiel:
p  y i = 0 p i
p  y i = 1qi
Normalerweise:
∏i  p i oder q i Wahrscheinlichkeit für ein erhaltenes Codewort
∑y∈C  y  ∏i  pi oder qi 
i
i
Wahrscheinlichkeit für alle
Codewörter, die an Stelle i den Wert yi
annehmen
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
state
Y 1,... ,4 Past 
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
00
Y 5,... ,8 Future
0
1
0
1
Codes on Graphs: Normal Realizations
0
1
0
1
0
1
0
1
0
1
0
1
p 1⋅ ... ⋅p 8
p 1⋅ ... ⋅p 4⋅q5⋅ ... ⋅q8
q 1⋅ ... ⋅q4⋅p5⋅ ... ⋅p8
q 1⋅ ... ⋅q8
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Mit der past-future decomposition rule:
 p 1 p 2 p 3 p4q1 q 2 q 3 q4  ⋅  p 5 p6 p7 p8q5 q6 q7 q 8
➔
Reduzierung auf 16 Multiplikationen und 2 Additionen
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Sum-product update rule:
p   j =s j ∣ r ∣P  =
∑C  s  ∏ j ´∈ K
k
Codes on Graphs: Normal Realizations
j
jk
p  j ´ =s j ´ ∣ r ∣P 
j´
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
Der Algorithmus:
•
pro Kante 2 APP Vektoren für past und future.
•
nach sum-product update rule Berechnen jeder Nachricht
•
an allen Kanten 2 Nachrichten: alle APPs können mit der
Past-future decomposition rule berechnet werden
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Sum-Product Algorithmus
BCJR Algorithmus: (Bahl-Cocke-Jelinek-Raviv)
läuft auf einem „chain-graph of a trellis“
ι0
Y0
C0
ε0
α1
β1
ι1
Y1
C1
ε1
α2
β2
ι2
Y2
C2
ε2
α3
β3
ι3
Y3
C3
ε3
α4
β4
ι4
Y4
C4
ε4
α5
β5
ι5
Y5
ε5
C5
Berechnung von α, β, ε mit sum-product update rule
Berechnung der APP Vektoren: komponentenweise
Multiplikation der ι und ε nach der past-future decomposition
rule
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Tanner Graph
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
+
=
+
=
=
+
=
Codes on Graphs: Normal Realizations
=
+
=
=
=
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
y0
y1
+
p i=P  y i =0∣r 
qi=P  y i =1∣r
y2
y0
y1
y2
0
0
0
 p 0⋅p1 
0
1
1
 p 0⋅q1 
1
0
1  p 0⋅p1 
1
1
0
q0⋅q1 
P y 2=0∣r= p0⋅p1 q0⋅q1
P y 2 =1∣r= p0⋅q1q0⋅p 1
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
p0
 y =ln
q0
0
p1
 y =ln
q1
1
p0⋅p1q0⋅q1
 y =ln
p0⋅q1q0⋅p 1
2
Zur besseren Lesbarkeit definieren wir:
y 0 := x
y 1 := y
y 2 := z
p 0⋅q0
1


p0⋅q0 p1⋅q 1
p 1⋅q1
e ⋅e 1
 z=ln 
=ln
=ln   
p0⋅q1 p1⋅q 0
p0 q0
e e

p1 q1
x
y
x
Codes on Graphs: Normal Realizations
y
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
x
x
2
y
y
2
− x
2
− y
2
e ⋅e 1
e ⋅e e ⋅e
ln  
=ln  −

− 
e e
e 2 e 2
x
y
x
y
x
y
x  y
cosh 

2
=ln 

x − y
cosh 

2
x
y
x
y
cosh  ⋅cosh  sinh  ⋅sinh  
2
2
2
2
=ln 

x
y
x
y
cosh  ⋅cosh  −sinh  ⋅sinh  
2
2
2
2
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
x
y
x
y
1sinh ⋅sinh   / cosh  ⋅cosh  
2
2
2
2
ln 

x
y
x
y
1−sinh ⋅sinh   / cosh  ⋅cosh  
2
2
2
2
x
y
1tanh ⋅tanh 
2
2
=ln 

x
y
1−tanh ⋅tanh 
2
2
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
x
y
1tanh  ⋅tanh  
2
2
ln 

x
y
1−tanh  ⋅tanh  
2
2
x
y
 z=2artanh  tanh ⋅tanh 
2
2
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter
Einführung | Graphendarstellungen | Algorithmus
Cut-Set Bound | Sum-Product Algorithmus | Belief Propagation
Belief Propagation
+
=
+
=
=
+
=
Codes on Graphs: Normal Realizations
=
+
=
=
=
Madeleine Leidheiser und Melanie Reuter
Vielen Dank für die Aufmerksamkeit!
Codes on Graphs: Normal Realizations
Madeleine Leidheiser und Melanie Reuter

Download Report