Innehåll
Hamming-koder används för att infoga felkorrigeringsinformation i dataströmmar. Koderna är utformade så att ett fel inte bara upptäcks utan också korrigeras. Lägga till felkorrigeringsinformation ökar mängden data, men det ökar också tillförlitligheten för kommunikation över media med höga felfrekvenser.
Hamming-kodning kan vara komplicerat att implementera, men det kan göras mycket snabbt med hjälp av bitnivå aritmetiska tricks. Detta gör det möjligt att skapa ett användbart och snabbkorrigeringssystem som kan användas i inbäddade applikationer.
Steg 1
Skapa dataordet. Varje bit med en position som är en kraft på två (första, andra, fjärde osv.) Måste reserveras för paritetsinformation. Använd så länge som behövs för att ordet ska ha de ursprungliga data- och paritetsbitarna.
Exempel:
1 1 0 1 0 0 1 0 blir _ _ 1 _ 1 0 1 _ 0 0 1 0
De ursprungliga bitarna förblir i samma ordning men sprids ut för att infoga paritetsbitarna.
Steg 2
Beräkna den första paritetsbiten. Från och med den första biten läses en bit och sedan hoppas en bit över och proceduren upprepas till slutet. Under tiden räknas antalet hittade. Paritetsbitar räknas inte med i denna process.
Om antalet är jämnt, ställ in den första biten till noll. Annars ställer du in den på en.
Exempel:
Bitarna 1, 3, 5, 7, 9 och 11 i _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, innehåller fyra. Detta är jämnt, så den första biten är satt till noll: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Steg 3
Beräkna de återstående paritetsbitarna. Från och med den andra biten läses två bitar och sedan hoppas över två bitar och proceduren upprepas till slutet. Den fjärde biten läser fyra bitar, hoppar över ytterligare fyra, börjar med bit fyra. Samma mönster följs av alla paritetsbitar tills de alla beräknas.
Exempel:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 kontrollerar _1, 01, 01, som innehåller tre, så bit 2 är inställd på en. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 kontrollerar _101, 0, som innehåller två, så bit 4 är satt till noll. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 kontrollerar _0010, som bara innehåller en, så bit 8 är inställd på en.
Ordet kodas därför som 011010110010.
Steg 4
Bekräfta ordet. Om ett ord är korrupt kommer paritetsbitarna inte att matcha det som förväntas. För att bekräfta att ordet inte är korrupt beräknar du bara paritetsbitarna med hjälp av steg två och tre. Om bitarna inte är desamma, registrera deras positioner.
Steg 5
Korrigera fel bit. Om du hittar felaktiga paritetsbitar, lägg bara till bitarnas positioner. Summan är positionen för den felaktiga biten. Ändra bitvärdet i den här positionen.
Till exempel, om de felaktiga paritetsbitarna är en och fyra, kommer felet att korrigeras genom att ändra värdet på den femte biten.