Low Density Parity Check

[gloob]

Hallöchen

hab hier ne aufgabe heute bekommen und raffe die absolut nicht.

soll gucken wie nen low density parity check erstellt wird bzw mittels des Quellkodeworts der redundante Teil des Kanalkodeworts gebildet wird. hat einer von euch dazu fällig nen bissl ahnung und könnte mir das vielleicht in nen paar sätzen erklären oder nen skript schicken. weil google bringt mich da leider nicht wirklich weite.

ich danke euch echt für eure mithilfe.

MfG

Das Gloob

 

[Cyrics]

ohje... wie war denn das?!
Ist auch schon ein bisschen her bei mir

Also vielleicht reden wir ja auch jetzt über zwei verschiedene Verfahren, aber ich würde behaupten, das was du meinst, ist Codiering per lineare Codes mit Paritätsuntersuchung und Prüfmatrix.

Also man bekommt eine Matrix zugeteilt

1 0 0 0 0 0 1
0 1 0 0 0 1 1
0 0 1 0 0 1 0
0 0 0 1 1 1 1

Dabei ist vorne rangestellt eine Einheitsmatrix und hinten die 3x4-Matrix die Prüfmatrix.
Nun soll man beispielsweise überprüfen ob diese mit der Bitfolge 1101111 ein zulässiges Codewort ergibt.
Dann nimmt mal also die 3x4-Matrix, also die Prüfmatrix, transponiert diese und hängt eine Einheitsmatrix hinten an um die Länge der zu prüfenden Bitfolge zu erhalten.

Damit haben wir folgendes:

0 0 0 1 1 0 0
0 1 1 1 0 1 0
1 1 0 1 0 0 1

und dies wird nun mit AND verknüpft mit unserer zur prüfenden Bitfolge. Dabei müssen Matrizen prinzipiell in den Dimensionen gleich sein, daher wird unserere zu prüfenden Bitfolge erweitert zu:

1 1 0 1 1 1 1
1 1 0 1 1 1 1
1 1 0 1 1 1 1

Jetzt wird wie gesagt per AND jedes Bit mit einander verglichen und man erhält eine Ergebnismatrix

0 0 0 1 1 0 0
0 1 0 1 0 1 0
1 1 0 1 0 0 1

dies liest man nun von links nach rechts in jeder Zeile und überprüft dadurch die Parität des erhaltenen Codeworts mit der erhaltenen Bitfolge.
Dabei wird addiert ohne Übertrag und wir erhalten

0
1
0

Damit ist die Parität verletzt und die Übermittlung gescheitert. 000 oder 111 wären erfolgreich gewesen.

Das ist meine Version der Paritätsüberprüfung. Bei Wikipedia geht das Ganze natürlich dann noch schön mathematisch

 

[gloob]

ui das ist echt hilfreich aber das ist ja nur das prüfen dann obs richtig ist oder nicht.

hast du vielleicht auch sowas in der richtung wie das erstellen der prüfmatrix dann geht? einfach reversibel zu deinem hier geschriebenen oder gibs da nen anderen algorithmus für?

 

[Cyrics]

hmmm... das ist echt schon zu lange her. Soweit ich weiß kann man einem Algorithmus folgen, aber welcher genau das ist, ist unterschiedlich.

Prinzipiell kriegt man immer nur eine Matrix vorgesetzt.
Die Erstellung einer Prüfmatrix kann dabei eben unterschiedlich sein...
zum Beispiel kannst du eine Problemstellung festlegen... meinetwegen du hast 5 Problemfälle und 4 mögliche Ursachen. Dies ist auch ein Beispiel bei Wikipedia und würdest nun die Probleme mit den Ursachen bejahen oder verneinen. Je nachdem würde sich dann eine 5x4-Matrix ergeben und eine bestimmte Bitfolge mit 1 und 0. Das wäre deine Prüfmatrix.
Und dann gibt es noch etwa zig andere Möglichkeiten

Einfachheitshalber haben wir es bisher immer bei einer fertig erstellten Prüfmatrix belassen und mussten dann mit dieser arbeiten.
Ich hatte eben auch gedacht, dass du eben parity check erwähnt hast, dass du eine Überprüfung der Parität meintest.
Vielleicht kennt ja jemand anderes den passenden Algorithmus dafür.