Computerarchitektur
Béat Hirsbrunner
S2 - 25 Oktober 2006
Kap. 2 - Aufbau von Prozessoren
2.2 Primäre Speicher
Fehlerkorrekturcodes
1
2.2.4 Fehlerkorrekturcodes (1/6)
•
Einige Definitionen
 Ein n-Bit-CodeWort besteht aus m Datenbits und r Prüfbits
 Hamming-Abstand w zweier Codewörter = Anzahl Bitstellen in
denen sich die beiden Codewörter unterscheiden
•
Beispiel: w=1 für die Codewörter 000 und 010
 Hamming-Abstand c eines Codes = minimaler Hamming-Abstand
zweier zulässigen Codewörter
•
Eigenschaften (für d Einzelbitfehler)
 Fehlererkennung: möglich für c = d + 1 (d.h. c > d)
 Fehlerkorrektur: theoretisch möglich für c = 2d + 1 (d.h. c > 2d)
•
Beispiel: Paritätsbit
 Jedem m Datenbit wird ein einzelnes Paritätsbit angehängt
•
Für ein solcher Code gilt c = 2
(oder anders ausgedrückt : es sind 2 Einzelbitfehler erforderlich, um von einem
gültigen Codewort zu einem anderen gültigen Codewort zu gelangen)
•
und es lassen sich Einzelbitfehler erkennen
2
2.2.4 Fehlerkorrekturcodes (2/6)
•
Lemma (Richard Hamming, 1950)
Um einen 1-bitfehler in einem m=2k-datenbit :
(a) zu erkennen
(b) zu korrigieren
braucht man 1 beziehungsweise k+1 Prüfbits (für k≥2)
•
Beweis (a)
Paritätsbit !
•
Beweis (b)
 1) es gibt 2m gültige Muster
 2) mit r-prüfsbits gibt es 2m+r verschiedene Codewörter
 3) Für jedes gültige Muster gibt es m+r ungültige mit einem Abstand von 1
(man bildet sie, indem man systematisch jedes der m+r bits invertiert)
 Aus (1) - (3) folgt : (m+r+1) * 2m ≤ 2m+r, d.h. m+r+1 ≤ 2r, d.h. k +1 ≤ r
3
2.2.4 Fehlerkorrekturcodes (3/6)
4
2.2.4 Fehlerkorrekturcodes (4/6)
•
Hamming Algorithmus
 Kodierung des 4-Bit-Speicherwort 1100 in den Mengen AB, ABC,
AC und BC mit je einem Bit je Menge (in alphabetischer
Reihenfolge)
5
2.2.4 Fehlerkorrekturcodes (5/6)
A
A
A
error
0
1
1
1
C
0
1
0
0
1
0
C
•
1
0
B
error
0
C
0
1
B
Fehler
1
Paritätsbit
B
Hamming Algorithmus (wiederbesucht)
 Kodierung des 4-Bit-Speicherwort 1100 in den Mengen AB, AC, BC
und ABC mit je einem Bit
6
2.2.4 Fehlerkorrekturcodes (6/6)
Das gleiche in einer anderer Darstellung
A B
C
0 1 1 1 1 0 0
1 2
4
Position
Position
Position
Position
3
5
6
7
ist
ist
ist
ist
: Mengen
: Codewort
: Stellenposition (2k, k=0,1,2,…)
durch
durch
durch
durch
A und B geprüft
A und C geprüft
B und C geprüft
A, B und c geprüft
(3=1+2 !)
(5=1+4 !)
(6=2+4 !)
(7=1+2+4 !)
d.h. Position 1 prüft 3, 5 und 7
Position 2 prüft 3, 6 und 7
Position 4 prüft 5, 6 und 7
Verallgemeinerung (Hamming Algorithmus)
1) Die k+1 Prüfungsbits belegen die Positionen einer 2er Potenz (1,2,..2K)
2) Bit b wird durch die Paritätsbits bj geprüft, wobei b = b1 + b2 + … + bi
3) Indem man die Positionen der Paritätsbits addiert die versagen
erhält man die Position des falschen Bits !!!
7

2.2.4 Fehlerkorrekturcodes