> hamming | (7,4) | ecc <
// Hamming-kode – feilkorrigeringskode for pålitelig dataoverføring
Feilkorrigering
Oppdager og retter automatisk enkeltbit-feil i data.
Deteksjon av doble feil
Kan oppdage (men ikke rette) feil på to biter i hver blokk.
Minimal overhead
Bare 3 paritetsbiter for hver 4 databiter (75 % effektivitet).
>> teknisk info
Hvordan Hamming-kode fungerer:
Hamming(7,4)-koden legger til 3 paritetsbiter til hver 4 databiter og danner 7-bitsblokker. Paritetsbitene plasseres på posisjoner som er potenser av 2 (1, 2, 4). Når feil oppstår, peker syndromet (resultatet av paritetskontrollen) direkte på posisjonen til det feilaktige bitet.
Hamming(7,4)-struktur:
Data: 1011 (4 biter) Posisjoner: P1 P2 D1 P3 D2 D3 D4 Hamming: 1 0 1 1 0 1 1 P1 = D1 ⊕ D2 ⊕ D4 = 1 ⊕ 0 ⊕ 1 = 0 P2 = D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 = 1 P3 = D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 = 0
Hvorfor bruke Hamming-kode:
- >Feilkorrigering i minne
- >Satellittkommunikasjon
- >Datasystemer for lagring
- >Nettverksoverføring
- >RAID-arrays
>> vanlige spørsmål
Hva er Hamming-kode?
Hamming-kode er en feilkorrigeringskode som ble utviklet av Richard Hamming i 1950. Den legger til paritetsbiter i dataene slik at enkeltbit-feil kan oppdages og rettes automatisk.
Hva betyr (7,4)?
Hamming(7,4) betyr 7 biter totalt, med 4 databiter og 3 paritetsbiter. Koden kan korrigere enhver enkeltbit-feil i 7-bitsblokken. Andre varianter inkluderer (15,11) og (31,26).
Hvordan fungerer feilkorrigering?
Når data mottas, beregnes paritetsbitene på nytt. Hvis de ikke stemmer overens, angir syndromet (forskjellen) direkte hvilket bit som er feil. Feilen rettes ved å invertere det bitet.
Hamming vs. andre ECC-koder?
Hamming-kode er enkel og effektiv for enkeltbit-feil. Mer komplekse koder som Reed–Solomon kan korrigere flere feil, men med høyere overhead. Hamming er ideell for kanaler med lav støy.
// Hurtigreferanse
| Pos | bit | covered by |
|---|---|---|
| 1 | p1 | p1 |
| 2 | p2 | p2 |
| 3 | d1 | p1 p2 |
| 4 | p3 | p3 |
| 5 | d2 | p1 p3 |
| 6 | d3 | p2 p3 |
| 7 | d4 | p1 p2 p3 |
// Gjennomregnet eksempel
Data 1011 -> positions 3,5,6,7 = 1,0,1,1 p1 = d3^d5^d7 = 1^0^1 = 0 p2 = d3^d6^d7 = 1^1^1 = 1 p3 = d5^d6^d7 = 0^1^1 = 0 Codeword (pos 1..7) 0110011 Received 0110111 (bit 5 flipped) Syndrome s3 s2 s1 = 1 0 1 = 5 -> flip bit 5 -> 0110011 corrected
>> Flere spørsmål
S: Hva betyr (7,4) i Hamming-koden?
S: 4 databit suppleres med 3 paritetsbit til et kodeord på 7 bit. Paritetsbitene ligger på topotensposisjonene 1, 2 og 4. Minste avstand er 3: én feil rettes, to feil oppdages men rettes ikke.
S: Hvordan viser syndromet feilens posisjon?
S: Hvert paritetsbit kontrollerer posisjonene der nummeret har tilsvarende bit satt. De tre resultatene danner binært posisjonen til den feilaktige biten (0 = ingen feil). I eksempelet peker 101 på posisjon 5.
S: Hva er utvidet Hamming (SECDED)?
S: Et ekstra totalparitetsbit gjør (7,4) til (8,4): retter 1 feil og oppdager 2. ECC-minne bruker samme prinsipp, ofte som (72,64) med 8 kontrollbit per 64 databit.