Codierungstheorie

Hamming-Code

 aufwärts

Hamming-Codes (nach R.W. Hammingzur Person) sind lineare (n, k)-Codes mit dem Hamming-Abstand 3; mit ihnen lassen sich also Einfach­fehler korrigieren [Ham 50].

Idee

Die Idee, die der Konstruktion von Hamming-Codes zugrunde­liegt, lässt sich auf zwei unter­schiedliche Weisen vermitteln. Die eine Möglichkeit beruht auf den algebraischen Eigen­schaften von linearen Codes, mit dieser beginnen wir im Folgenden. Alternativ dazu ist die Konstruktion durch überlappende Paritäts­prüfungen möglich.

Ein n-Bit-Hamming-Code ist ein linearer Code, der als Kontroll­matrix H eine Matrix verwendet, deren j-ter Spalten­vektor die Binär­darstellung der Zahl j enthält (j Element {1, ..., n}).

Beispiel:  Es sei n = 5. Dann ist die Kontroll­matrix

H   =   eckige Klammer auf
00011
01100
10101
eckige Klammer zu

Die j-te Spalte von H enthält jeweils die Binär­darstellung von j.

Sei nun c Element boolesche Werten ein Codewort des Hamming-Codes, das durch einen Einfach­fehler e Element boolesche Werten in ein Wort x Element boolesche Werten verfälscht worden ist:

x  =  centweder odere

Dann liefert das Syndrom x·HT genau die Position (in Binär­darstellung) des Einfach­fehlers. Denn es ist

x · HT = (centweder odere) · HT
 = c · HT entweder oder e · HT
 = e · HT

Da der Einfach­fehler e an genau einer Stelle j eine 1 hat, ergibt e · HT die j-te Spalte von H, und diese enthält die Binär­darstellung von j.

Der Einfach­fehler lässt sich somit korrigieren, indem das j-te Bit von x invertiert wird.

Beispiel:  Es ist

[1 1 1 0 1] · HT   =   [1 0 1]

d.h. an Position 5 ist ein Fehler aufgetreten. Das richtige Codewort wäre 1 1 1 0 0 gewesen.

Konstruktion des Hamming-Codes

Ist die Kontroll­matrix H in der obigen Form gegeben, so lässt sich der zugehörige Hamming-Code durch Umkehrung des im Kapitel Lineare Codes beschriebenen Verfahrens konstruieren.

Zunächst wird die Kontroll­matrix H durch Spalten­vertauschungen (repräsentiert durch die Permutationsmatrix S) in die Form

H'  =  H · S  =  [PT In-k]

gebracht.

Aus H' wird G' konstruiert:

G'  =  [Ik P],

und durch Rückgängig­machen der Spalten­vertauschungen wird aus G' eine Generator­matrix des Hamming-Codes erzeugt:

G  =  G' · ST.

 

Beispiel:  Gegeben sei die Kontroll­matrix H aus dem vorigen Beispiel.

H   =   eckige Klammer auf
00011
01100
10101
eckige Klammer zu

Durch Spalten­vertauschungen ergibt sich

H'   =   [PT I3]   =   eckige Klammer auf
10100
01010
11001
eckige Klammer zu

Damit ist

G'   =   [I2 P]   =   eckige Klammer auf
10101
01011
eckige Klammer zu

und durch Rückgängig­machen der Spalten­vertauschungen ergibt sich die Generator­matrix G des Hamming-Codes:

G   =   eckige Klammer auf
10011
11100
eckige Klammer zu

Der erzeugte Hamming-Code ist ein (5,2)-Code, d.h. ein Code mit 5 Bit Code­wort­länge, bestehend aus 2 Informations- und 3 Prüfbits.

Perfekte Hamming-Codes

Statt nur 2 Informationsbits wie im vorigen Beispiel wären auch 4 Informationsbits möglich gewesen. Hierzu ist die Kontroll­matrix um zwei weitere Spalten mit den Binär­darstellungen von 6 und 7 zu erweitern und anschließend das Konstruktionsverfahren durch­zuführen. Das Ergebnis ist ein (7,4)-Code, also ein Code mit 7 Bit Code­wort­länge, davon 4 Informationsbits und 3 Prüfbits.

Dieser (7,4)-Hamming-Code hat folgende Kontroll­matrix H und Generator­matrix G:

H   =   eckige Klammer auf
0001111
0110011
1010101
eckige Klammer zu
G   =  eckige Klammer auf
1101001
0101010
1001100
1110000
eckige Klammer zu

Der (7,4)-Hamming-Code ist ein perfekter Code, da er für die Code­wort­länge 7 und den vorgegebenen Hamming-Abstand 3 die maximal mögliche Anzahl von Codewörtern enthält.

Allgemein gibt es perfekte (n, k)-Hamming-Codes mit n = 2m-1, wobei m Element natürliche Zahlen die Anzahl der Prüfbits und k = n-m die Anzahl der Informationsbits sind. Dies sind also (1,0)-, (3,1)-, (7,4)-, (15,11)-, (31,26)-Hamming-Codes usw. 1)

Alternative Konstruktion des Hamming-Codes

Die Multi­plikation eines Wortes x Element boolesche Werten mit einer Spalte von HT (d.h. mit einer Zeile von H) entspricht einer Paritäts­prüfung in denjenigem Teilbereich des Wortes x, in dem die Zeile von H Einsen hat.

Im Falle der Kontroll­matrix H des (7,4)-Hamming-Codes kommen hierdurch drei einander überlappende Paritäts­prüfungen zustande (blau, grün und gelb gekenn­zeichnete Bereiche in Bild 1). Bei Codewörtern muss die Parität in allen diesen Bereichen 0 sein. Ist die Parität in einem oder mehreren Bereichen verletzt, lässt sich die Position des Fehlers aufgrund der Über­lappungen der Bereiche eindeutig bestimmen.

Bild 1: Bereiche mit Parität 0 in einem Codewort
Bild 1: Bereiche mit Parität 0 in einem Codewort

Um ein Codewort zu konstruieren, werden zunächst die Bit­positionen 2i des Wortes für Paritätsbits reserviert. Dann werden die restlichen Positionen beliebig mit Informationsbits belegt. Anschließend wird jedes Paritätsbit so gesetzt, dass der Bereich, dem es angehört, die Parität 0 erhält.

In folgendem Bild ist ein Beispiel eines 7-Bit-Codewortes zu sehen. Die Paritätsbits stehen an den Positionen 1, 2 und 4 des Wortes. Die restlichen Positionen sind mit Datenbits belegt. Die Paritätsbits sind so gewählt, dass der blaue, der grüne und der gelbe Bereich die Parität 0 haben.

Bild 2: Belegung der Paritätsbits (farbig hinterlegt)
Bild 2: Belegung der Paritätsbits (farbig hinterlegt)

Literatur

[Ham 50]R.W. Hamming: Error Detection and Error Correction Codes. The Bell System Technical Journal, Vol. XXVI, 2, 147-160 (1950)
[Wit 01]K.U. Witt: Algebraische Grundlagen der Informatik. Vieweg (2001)

1)  Der (1,0)-Code, der nur aus einem Prüfbit und null Informationsbits besteht, ist natürlich wenig sinnvoll.

 

Weiter mit:   [CRC-Verfahren]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 10.10.2003   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik