Felrättning

Om mottagaren upptäcker ett överföringsfel, till exempel med hjälp av kontrollbitar, kan den be sändaren överföra data på nytt. Vid framåtriktad felrättning behövs däremot ofta ingen omsändning. Då läggs extra information till nyttodata, till exempel flera kontrollbitar. Under vissa förutsättningar kan mottagaren då inte bara se att ett fel har uppstått utan också avgöra vilken bit som är felaktig och rätta den. På engelska kallas metoden Forward Error Correction (FEC).

Hur det kan fungera i detalj visas i fördjupningen bredvid med en Hamming-kod som exempel. Den exakta metoden behöver du inte kunna utantill.

Hamming-koden är en felrättningsmetod som använder flera paritetsbitar. Anta att vi vill överföra följande $\num{11}$ databitar:

Den här alternativtexten har ännu inte granskats.
1) Kort sammanfattning: En vågrät rad av elva bredvid varandra liggande, svartkantade rutor, där siffrorna 0 och 1 står.
2) Detaljerad beskrivning: Rutorna är rektangulära, lika stora och visade på vit botten, var och en med en enskild siffra centrerad. Från vänster till höger lyder siffrorna: 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1. Det finns inga axlar, pilar eller ytterligare märkningar. — Figur HAREC-16.25.1:

För att ett enskilt bitfel inte bara ska kunna upptäckas utan också rättas måste vi kunna avgöra var felet har uppstått. Därför tittar vi först på de enskilda bitarnas positioner och ger dem bokstavsnamn i alfabetisk ordning:

Den här alternativtexten har ännu inte granskats.
1) Kort beskrivning: En vågrät rad av elva lika stora, inramade rutor, var och en märkt med gemenerna ”a” till ”k”.
2) Detaljerad beskrivning: Från vänster till höger syns elva rektangulära fält med tunn svart ram, åtskilda av lodräta linjer. I varje fält står en enskild gemen centrerad, i ordning: ”a”, ”b”, ”c”, ”d”, ”e”, ”f”, ”g”, ”h”, ”i”, ”j”, ”k”. Det finns inga andra märkningar, axlar eller symboler; bakgrund och fält är ljusa. — Figur HAREC-16.25.2:

Nu ordnar vi databitarna lite annorlunda och lägger till fyra extra paritetsbitar $p_1$ till $p_4$:

Den här alternativtexten har ännu inte granskats.
1. Kort sammanfattning: Ett 4×4-rutnät med svarta rutnätslinjer; några fält innehåller svarta gemener från a till k.
2. Detaljerad beskrivning: Vit bakgrund, tjocka svarta linjer bildar ett kvadratiskt rutnät på 4 kolumner × 4 rader. Bokstäverna står centrerade i vissa celler. Positionerna (rader uppifrån och ned 1–4, kolumner från vänster till höger 1–4): Rad 1: kolumn 1–3 tomma, kolumn 4 ”a”. Rad 2: kolumn 1 tom, kolumn 2 ”b”, kolumn 3 ”c”, kolumn 4 ”d”. Rad 3: kolumn 1 tom, kolumn 2 ”e”, kolumn 3 ”f”, kolumn 4 ”g”. Rad 4: kolumn 1 ”h”, kolumn 2 ”i”, kolumn 3 ”j”, kolumn 4 ”k”. Alla bokstäver är svarta och visas som gemener. — Figur HAREC-16.25.3:

De fyra paritetsbitarna kontrollerar olika, överlappande grupper av bitar:

Den här alternativtexten har ännu inte granskats.
Kort beskrivning: Ett 4×4-rutnät med tjocka svarta linjer; cellerna innehåller delvis tecknen p1–p4 och bokstäverna a–k, en cell är tom.
Detaljerad beskrivning: Rutnätet har fyra rader och fyra kolumner. Uppifrån och ned, läst från vänster till höger:
- Rad 1: Cell 1 tom; cell 2 ”p1” (kursiv); cell 3 ”p2” (kursiv); cell 4 ”a”.
- Rad 2: Cell 1 ”p3” (kursiv); cell 2 ”b”; cell 3 ”c”; cell 4 ”d”.
- Rad 3: Cell 1 ”p4” (kursiv); cell 2 ”e”; cell 3 ”f”; cell 4 ”g”.
- Rad 4: Cell 1 ”h”; cell 2 ”i”; cell 3 ”j”; cell 4 ”k”.
Bokstäverna a–k är satta med normal, upprätt stil. — Figur HAREC-16.25.4:

Varje paritetsbit säkrar en bestämd grupp:

Den här alternativtexten har ännu inte granskats.
1) Kort sammanfattning: En rutnätsgrafik med 4 rader och 16 kolumner med växelvis grå och vita celler, indelad i fyra identiska block om 4 kolumner med märkningarna p1, p2, a, p3, b, c, d, p4, e, f, g, h, i, j, k.
2) Detaljerad beskrivning: Rutnätet består av fyra rader och sexton kolumner, visuellt indelade i fyra lika breda block om fyra kolumner. I varje block upprepas samma ordning på cellernas text. Rad 1 i ett block visar (från vänster till höger): ”p1”, ”p2”, ”a” och en tom cell. Rad 2 visar: ”p3”, ”b”, ”c”, ”d”. Rad 3 visar: ”p4”, ”e”, ”f”, ”g”. Rad 4 visar: ”h”, ”i”, ”j”, ”k”. Många celler har grå bakgrund, andra vit; de grå och vita ytorna växlar fältvis och växlingsmönstret upprepas blockvis över hela bredden. Endast de nämnda bokstäverna och teckenföljderna ”p1”, ”p2”, ”p3”, ”p4” syns; det finns inga andra axlar, pilar eller teckenförklaringar. — Figur HAREC-16.25.5:

För var och en av dessa grupper beräknar vi nu den tillhörande paritetsbiten med jämn paritet:

Den här alternativtexten har ännu inte granskats.
Kort sammanfattning: Ett 4×4-rutnät med tjocka svarta linjer visar siffrorna 0 och 1, några fält har grå bakgrund, flera poster har små nedsänkta bokstäver; fältet uppe till vänster är tomt.
Detaljerad beskrivning:
- Ram: Svart kant, rutnät med tjocka svarta linjer.
- Rad 1 (från vänster till höger):
1) vit, tom; 2) grå, ”1”; 3) grå, ”0”; 4) vit, ”1_a” (a litet, nedsänkt nere till höger).
- Rad 2:
1) grå, ”0”; 2) vit, ”1_b”; 3) vit, ”0_c”; 4) vit, ”0_d”.
- Rad 3:
1) grå, ”1”; 2) vit, ”1_e”; 3) vit, ”0_f”; 4) vit, ”1_g”.
- Rad 4:
1) vit, ”1_h”; 2) vit, ”0_i”; 3) vit, ”1_j”; 4) vit, ”1_k”. — Figur HAREC-16.25.6:

Om ett enskilt bitfel uppstår vid överföringen misslyckas vissa paritetskontroller. Av kombinationen av de misslyckade kontrollerna går det att avgöra på vilken position felet har uppstått. Den felaktiga biten kan sedan vändas och därmed rättas.

Om till exempel bit $k$ blir en $\num{0}$ vid överföringen misslyckas alla fyra paritetskontrollerna $p_1$ till $p_4$. Endast bit $k$ tillhör alla fyra kontrollerade grupper. Felet måste därför ligga i bit $k$.

Uppstår i stället ett fel i bit $a$ misslyckas bara kontrollerna för $p_1$ och $p_2$, medan kontrollerna för $p_3$ och $p_4$ lyckas. Av detta mönster kan mottagaren se att bit $a$ är felaktig.

Även ett fel i själva paritetsbiten kan upptäckas och rättas. Om till exempel $p_1$ är felaktig misslyckas bara den paritetskontroll som hör till $p_1$, medan kontrollerna för $p_2$, $p_3$ och $p_4$ lyckas. Felet måste därför ligga i $p_1$.

Hamming-koden som visas här är avsedd för att rätta ett enskilt bitfel. Om flera bitfel uppstår samtidigt går det inte längre att på ett tillförlitligt sätt avgöra den verkliga felpositionen utifrån paritetskontrollerna. Utökade Hamming-koder kan dessutom till exempel säkert upptäcka två samtidiga bitfel.

Fortsätt till nästa avsnitt: Sändar- och mottagarkedjor