| | |
| Titel: | Lineare Binärcodes. | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Kontrollmatrix, Generatormatrix
Es soll die Nachricht u=u1...uk gesendet werden. Um etwaige Übertragungsfehler zu erkennen, wird der Nachricht bei der Übertragung zusätzliche Redundanz hinzugefügt: die Kontrollbits. Ein Codewort x=x1x2...xn (xi=0,1) besteht demnach aus k Informationsbits (x1=u1,x2=u2, ..., xk=uk). Bei einem systematischen Code hat man n-k Kontrollbits. Die Codewörter werden so gewählt, dass sie der Bedingung H*x=0 genügen, wobei H eine für den Code spezifische (n-k) x n-Matrix ist und H=[A|In-k].Dabei ist A eine (n-k) x k-Matrix und In-k eine (n-k) x (n-k)-Einheitsmatrix.
x ist also genau dann ein Codewort, wenn H*x=0 gilt. Deshalb ist der Code durch die Matrix H eindeutig bestimmt. Des Weiteren gibt es zu jeder Nachricht u genau ein Codewort x. Da H*0=0 für alle Matrizen H gilt, ist 0 immer ein Codewort.
Bsp.1.1:
| 0 1 1 | 1 0 0 |
H = | 1 0 1 | 0 1 0 |
| 1 1 0 | 0 0 1 |
Hier ist k=3 und n=6 (also hat man Codewörter der Länge 6 mit 3 Informationsbits).
Aus der Bedingung H*x=0 ergeben sich folgende Gleichungen, welche für das Codewort erfüllt sein müssen:
- x2+x3+x4=0
- x1+x3+x5=0
- x1+x2+x6=0
- x4=o-x2-x3=0 (aus Gleichung 1)
- x5=-x1-x3=1 (aus Gleichung 2)
- x6=-x1-x2=1 (aus Gleichung 3)
Da jedes Informationsbit 1 oder 0 sein kann, gibt es insgesamt 23=8 Codewörter (für diese Kontrollmatrix), nämlich
000000, 011011, 110110, 001110, 100011, 111000, 010101, 101101
Im allgemeinen Fall gibt es natürlich 2k Codewörter. Die Kontrollmatrix eines Codes ist ferner nicht eindeutig.
Ein Code heißt linear, falls folgende zwei Bedingungen erfüllt sind:
- Sind x und y Codewörter, so ist auch deren Summe ein Codewort.
- Ist x ein Codewort und c ein beliebiges Element des Alphabets, so ist auch (c*x) ein Codewort.
Als nächstes stellt man sich die Frage, wie man direkt (also ohne obiges Gleichungssystem) zu einer gegebenen Nachricht das zugehörige Codewort ermitteln kann. Das geht mit Hilfe der Generatormatrix. Ist H=[A|In-k], so ist die entsprechende Generatormatrix G=[Ik|Atr], wobei At die zu A transponierte Matrix ist. Das Codewort x zu einer gegebenen Nachricht u lässt sich dann durch die Gleichung xtr=utr*G ausrechnen. Hat G obige Form mit Einheitsmatrix, d.h. kann man aus den ersten k Symbolen des Codewortes die ursprüngliche Nachricht direkt ablesen, so heißt der Code systematisch. Da jeder Code auf systematische Form gebracht werden kann, beschränken wir uns hier nur auf solche. Die Zeilen der Generatormatrix können auch als eine Basis des Codes aufgefasst werden. Sie müssen also linear unabhängig sein. Es gilt außerdem G*Htr=0 bzw. H*Gtr=0
Bsp.1.2:
Für die Kontrollmatrix aus Bsp.1.1 ist die Generatormatrix
|100 | 011 | = g1
G = |010 | 101 | = g2
|001 | 110 | = g3 .
Für u=011 ergibt sich xtr=utr*G = 0*g1 + 1*g2 +
1*g3 = g2+g3 = 010101 + 001110 = 011011
Zurück zur Themenseite:
StudyPaper.com/Startseite/Computer/Informatik
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
