> hamming | (7,4) | ecc <
// Hamming-kode – fejlrettelseskode til pålidelig datatransmission
Fejlkorrektion
Registrerer og retter automatisk enkelt-bit-fejl i data.
Detektion af dobbeltfejl
Kan registrere (men ikke rette) fejl på to bit i hver blok.
Minimal overhead
Kun 3 paritetsbit for hver 4 databits (75 % effektivitet).
>> teknisk info
Sådan fungerer Hamming-kode:
Hamming(7,4)-koden tilføjer 3 paritetsbit til hver 4 databits og danner blokke på 7 bit. Paritetsbittene placeres på positioner, der er potenser af 2 (1, 2, 4). Når der opstår fejl, peger syndromet (resultatet af paritetskontrollen) direkte på den bit, der er fejl i.
Hamming(7,4)-struktur:
Data: 1011 (4 bit) Positioner: 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 bruge Hamming-kode:
- >Fejlkorrektion i hukommelse
- >Satellitkommunikation
- >Databaseskyttelsessystemer
- >Netværksoverførsel
- >RAID-arrays
>> ofte stillede spørgsmål
Hvad er Hamming-kode?
Hamming-kode er en fejlrettelseskode opfundet af Richard Hamming i 1950. Den tilføjer paritetsbit til data, så enkelt-bit-fejl kan registreres og rettes automatisk.
Hvad betyder (7,4)?
Hamming(7,4) betyder 7 bit i alt med 4 databits og 3 paritetsbit. Koden kan rette enhver enkelt-bit-fejl i 7-bit-blokken. Andre varianter omfatter (15,11) og (31,26).
Hvordan fungerer fejlkorrektion?
Når data modtages, beregnes paritetsbittene på ny. Hvis de ikke stemmer, angiver syndromet (forskellen) direkte, hvilken bit der er forkert. Fejlen rettes ved at vende den bit.
Hamming vs. andre ECC-koder?
Hamming-kode er enkel og effektiv til enkelt-bit-fejl. Mere komplekse koder som Reed–Solomon kan rette flere fejl, men med større overhead. Hamming er ideel til kanaler med lav støj.
// Hurtig reference
| 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 |
// Gennemregnet 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ørgsmål
S: Hvad betyder (7,4) i Hamming-koden?
S: 4 databit suppleres med 3 paritetsbit til et kodeord på 7 bit. Paritetsbittene ligger på topotenspositionerne 1, 2 og 4. Mindsteafstanden er 3: én fejl rettes, to fejl opdages men rettes ikke.
S: Hvordan viser syndromet fejlens position?
S: Hvert paritetsbit kontrollerer de positioner, hvis nummer har det tilsvarende bit sat. De tre resultater danner binært positionen for det forkerte bit (0 = ingen fejl). I eksemplet peger 101 på position 5.
S: Hvad er udvidet Hamming (SECDED)?
S: Et ekstra samlet paritetsbit gør (7,4) til (8,4): retter 1 fejl og opdager 2. ECC-hukommelse bruger samme princip, oftest som (72,64) med 8 kontrolbit pr. 64 databit.