Hamming-kod: Felsökning och korrigering med exempel

Vad är ett fel?

Överförda data kan skadas under kommunikation. Den kommer sannolikt att påverkas av externt buller eller andra fysiska fel. I en sådan situation kan indata inte vara samma som utdata. Denna oöverensstämmelse kallas "Fel".

Datafelen kan resultera i förlust av viktig eller säker data. Det mesta av dataöverföringen i digitala system kommer att ske i form av "Bitöverföring". Även en liten förändring kan påverka hela systemets prestanda. I en datasekvens, om 1 ändras till 0 eller 0 ändras till 1, kallas det "Bitfel".

Typer av fel

Det finns huvudsakligen tre typer av bitfel som uppstår vid dataöverföring från sändaren till mottagaren.

• Enkelbitsfel
• Flera bitfel
• Burst-fel

Enkelbitsfel

Ändringen som görs i en bit i hela datasekvensen kallas "Single bit error". Förekomsten av enbitsfel är dock inte så vanligt. Dessutom uppstår detta fel endast i ett parallellt kommunikationssystem eftersom data överförs bitvis på en enda linje. Därför finns det fler chanser att en enda linje kan vara bullrig.

Flera bitfel

I datasekvens, om det finns en förändring i två eller flera bitar av en datasekvens från en sändare till mottagare, kallas det "flera bitfel."

Denna typ av fel uppstår oftast i både seriella och parallella datakommunikationsnätverk.

Burst-fel

Ändringen av uppsättningen bitar i datasekvensen är känd som "Burst error". Denna typ av datafel beräknas från den första bitändringen till den sista bitändringen.

Vad är feldetektering och felkorrigering?

I digitalt kommunikationssystem överförs fel från ett kommunikationssystem till ett annat. Om dessa fel inte upptäcks och korrigeras kommer data att gå förlorade. För effektiv kommunikation bör systemdata överföras med hög noggrannhet. Detta kommer att göras genom att först identifiera felen och korrigera dem.

Feldetektering är en metod för att detektera de fel som finns i data som överförs från en sändare till mottagare i ett datakommunikationssystem.

Här kan du använda redundanskoder för att hitta dessa fel, genom att lägga till data när den sänds från källan. Dessa koder kallas "Feldetektering av koder".

Tre typer av feldetekteringskoder är:

• Paritetskontroll
• Cyclic Redundancy Check (CRC)
• Longitudinell redundanskontroll (LRC)

Paritetskontroll

• Det är också känt som en paritetskontroll.
• Den har en kostnadseffektiv mekanism för feldetektering.
• I denna teknik är den redundanta biten känd som en paritetsbit. Den bifogas för varje dataenhet. Det totala antalet 1:or i enheten ska bli jämnt, vilket är känt som en paritetsbit.

Longitudinell redundanskontroll

I denna feldetekteringsteknik är ett block av bitar organiserat i tabellformatet. LRC-metoden hjälper dig att beräkna paritetsbiten för varje kolumn. Uppsättningen av denna paritet skickas också tillsammans med originaldata. Paritetsblocket hjälper dig att kontrollera redundansen.

Cyklisk redundanskontroll

Cyklisk redundanskontroll är en sekvens av redundans som måste läggas till i slutet av enheten. Det är därför den resulterande dataenheten bör bli delbar med ett andra, förutbestämt binärt tal.

På destinationen måste inkommande data delas med samma nummer. Om det inte finns någon återstod, antas dataenheten vara korrekt och accepteras. Annars indikerar det att dataenheten är skadad i överföringen och därför måste den avvisas.

I Hamming-kod kodar källan meddelandet genom att lägga till redundanta bitar i meddelandet. Dessa redundanta bitar infogas och genereras oftast vid vissa positioner i meddelandet för att utföra feldetektering och korrigeringsprocessen.

Historien om Hamming-koden

• Hamming-kod är en teknik byggd av RWHamming för att upptäcka fel.
• Hammingkod bör appliceras på dataenheter av valfri längd och använder förhållandet mellan data och redundansbitar.
• Han arbetade med problemet med felkorrigeringsmetoden och utvecklade en allt kraftfullare uppsättning algoritmer som kallas Hamming-kod.
• 1950 publicerade han Hamming-koden, som idag används allmänt i applikationer som ECC-minne.

Tillämpning av Hamming-kod

Här är några vanliga tillämpningar för att använda Hamming-kod:

• satelliter
• Datorminne
• modem
• PlasmaCAM
• Öppna kontakter
• Avskärmande tråd
• Inbyggd processor

Fördelar med Hamming-kod

• Hamming-kodmetoden är effektiv på nätverk där dataströmmarna ges för enbitsfel.
• Hamming-kod ger inte bara upptäckt av ett bitfel utan hjälper dig också att dra in bitar som innehåller fel så att det kan korrigeras.
• Den enkla användningen av hamming-koder gör att de är bäst lämpade för användning i datorminne och enfelskorrigering.

Nackdelar med Hamming-kod

• Enbits feldetektering och korrigeringskod. Men om flera bitar är grundade fel, kan resultatet resultera i att en annan bit som bör vara korrekt ändras. Detta kan göra att data blir ytterligare felaktiga.
• Hamming-kodalgoritm kan bara lösa problem med enstaka bitar.

Hur man kodar ett meddelande i Hamming Code

Processen som används av avsändaren för att koda meddelandet inkluderar följande tre steg:

• Beräkning av totalt antal redundanta bitar.
• Kontrollera läget för de redundanta bitarna.
• Slutligen beräkna värdena för dessa redundanta bitar.

När ovanstående redundanta bitar är inbäddade i meddelandet skickas det till användaren.

Steg 1) Beräkning av det totala antalet redundanta bitar.

Låt anta att meddelandet innehåller:

• n– antal databitar
• p – antal redundanta bitar som läggs till så att np kan indikera åtminstone (n + p + 1) olika tillstånd.

Här skildrar (n + p) platsen för ett fel i var och en av (n + p) bitpositioner och ett extra tillstånd indikerar inget fel. Som p-bitar kan indikera 2^p stater, 2^p måste vara minst lika med (n + p + 1).

Steg 2) Placera de redundanta bitarna i rätt position.

De p redundanta bitarna bör placeras i bitpositioner med potenser 2. Till exempel 1, 2, 4, 8, 16, etc. De kallas p₁ (vid position 1), sid₂ (vid position 2), sid₃ (vid position 4) osv.

Steg 3) Beräkning av värdena för den redundanta biten.

De redundanta bitarna bör vara paritetsbitar, vilket gör antalet 1:or till antingen jämna eller udda.

De två typerna av paritet är ?

• Det totala antalet bitar i meddelandet som görs jämnt kallas jämn paritet.
• Det totala antalet bitar i meddelandet görs udda kallas udda paritet.

Här måste all redundant bit, p1, beräknas som pariteten. Den bör täcka alla bitpositioner vars binära representation bör inkludera en 1:a i den 1:a positionen exklusive positionen för p1.

P1 är paritetsbiten för varje databit i positioner vars binära representation inkluderar en 1 i den mindre viktiga positionen som inte inkluderar 1 Like (3, 5, 7, 9, ….)

P2 är paritetsbiten för varje databit i positioner vars binära representation inkluderar 1 i position 2 från höger, inte inklusive 2 Like (3, 6, 7, 10, 11,...)

P3 är paritetsbiten för varje bit i positioner vars binära representation inkluderar en 1 i position 3 från höger inte inkluderar 4 Like (5-7, 12-15,...)

Dekrypterar ett meddelande i Hamming-kod

Mottagaren får inkommande meddelanden som måste utföra omräkningar för att hitta och korrigera fel.

Omräkningsprocessen görs i följande steg:

• Räknar antalet redundanta bitar.
• Korrekt placering av alla redundanta bitar.
• Paritetskontroll

Steg 1) Räknar antalet redundanta bitar

Du kan använda samma formel för kodning, antalet redundanta bitar

2^p ? n + p + 1

Här är antalet databitar och p antalet redundanta bitar.

Steg 2) Korrekt placera alla redundanta bitar

Här är p en redundant bit som är placerad vid bitpositioner med potenser 2, till exempel 1, 2, 4, 8, etc.

Steg 3) Paritetskontroll

Paritetsbitar måste beräknas baserat på databitar och de redundanta bitarna.

p1 = paritet(1, 3, 5, 7, 9, 11...)

p2 = paritet(2, 3, 6, 7, 10, 11...)

p3 = paritet(4-7, 12-15, 20-23...)

Sammanfattning

• Överförda data kan skadas under kommunikation
• Tre typer av bitfel är 1) Enbitsfel 2) Flerbitarsfel 3) Burstbitfel
• Ändringen som görs i en bit i hela datasekvensen kallas "Single bit error."
• I datasekvens, om det finns en förändring i två eller flera bitar av en datasekvens från en sändare till mottagare, kallas det "flera bitfel."
• Ändringen av uppsättningen bitar i datasekvensen är känd som "Burst error".
• Feldetektering är en metod för att upptäcka de fel som finns i data som överförs från en sändare till mottagare i ett datakommunikationssystem
• Tre typer av feldetekteringskoder är 1) Paritetskontroll 2) Cyklisk redundanskontroll (CRC) 3) Longitudinell redundanskontroll (LRC)
• Hamming-kod är en liner-kod som är användbar för feldetektering upp till två omedelbara bitfel. Den är kapabel till enbitsfel.
• Hamming-kod är en teknik byggd av RWHamming för att upptäcka fel.
• Vanliga tillämpningar för att använda Hamming-kod är satelliter datorminne, modem, inbyggd processor, etc.
• Den största fördelen med hamming-kodmetoden är effektiv på nätverk där dataströmmarna ges för enbitsfel.
• Den största nackdelen med hamming-kodmetoden är att den bara kan lösa problem med enstaka bitar.
• Vi kan utföra processen att kryptera och avkoda meddelandet med hjälp av hamming-kod.