| | |
| Title: | Lineare Binärcodes. | |
| Home deutsch | ||
| ||
| |<< First < Previous Index Next > Last >>| | |  |
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
|
|
| Information, Organization and Management | |
| Siehe auch: | |
| Strategisches IT-Management: Wert steigern, Leist... | |
| Menschliche Kommunikation: Formen, Störungen,... | |
| Handbuch der Strategien: 220 Konzepte der weltb... | |
| Die besten Strategietools in der Praxis: Welche W... | |
| Digital Analog Wandler Solisto DAC 4all incl. Kabel und Netzteil von avail Information Systems (in Computer & Zubehör) | |
Back to the topic site:
StudyPaper.com/Startseite/Computer/Informatik
External Links to this site are permitted without prior consent.
