Het is al weer een hele tijd geleden dat ik op een website zat waar leuke programmeer opdrachten werden uitgedeeld. Deze opdrachten kan je voltooien en hiermee kan je dan punten verdienen, leuk om kennis op te doen en tijd te doden.
Een opdracht die mij het meest is bijgebleven is een opdracht over foutcorrectie in binaire code. Het was de 10e opdracht in de categorie “Cryptography”. De titel van de opdracht was “Hamming” en de inhoud van de opdracht was “Decode this string and find the right password! 1000100101010101100100101001000111000001010010”. Dat het hier om binaire code gaat is wel duidelijk, dus ik heb direct geprobeerd de binaire code om te zetten naar ASCII, zonder succes natuurlijk (anders was de opdracht ook niet moeilijk). Hierdoor kwam ik er wel achter dat de binaire code bestond uit 46 tekens, raar, want een normale binaire code kan je altijd delen door 8 (als je naar text (ASCII) wilt).
*8 bits maakt 1 byte en 1 ASCII teken is 1 byte. (ik ga hier niet uitleggen hoe binaire code werkt, daar gaat het ook niet om)*
Oke, de binaire code bestaat dus uit 46 tekens, iets te veel of iets te weinig…Toch maar gaan onderzoeken waar de titel van de opdracht opslaat. Op Google intypt “Hamming binary code”, meteen resultaat op een Wikipedia pagina, dat is altijd gunstig. Ok, een korte uitleg over hamming code en waar het weg komt, met als bron Wikipedia:
“In de telecommunicatie is een Hamming-code een foutcorrigerende code, genoemd naar de uitvinder, Richard Hamming. Hamming-codes zijn lineaire codes, en zij kunnen 1 of 2 bitfouten detecteren, of 1 bitfout corrigeren. Dit in tegenstelling tot het gebruik van een enkelvoudige pariteitcontrole (met 1 pariteitsbit), die een even aantal bitfouten niet detecteert, en die geen hulp kan bieden voor het corrigeren van gevonden bitfouten.”
Ok, duidelijk, Hamming-code is dus een foutcorrigerende code die fouten kan detecteren en/of corrigeren in binaire code, handig! Maar goed, dit verklaart nog niet waarom er meer of minder bits in de opdracht staan. Even doorlezen dus…
Om alles een beetje kort uit te leggen. Richard Hamming werkte in de jaren 40 bij Bell Labs aan de Bell Model V computer. De invoer van gegevens in deze computer vond plaats via ponskaarten, waarbij altijd leesfouten optraden. Richard Hamming werkte tijdens de weekenden, en werd steeds gefrustreerder over het opnieuw moeten starten van zijn programma’s vanwege de onbetrouwbaarheid van de kaartlezer.
Gedurende een aantal jaren werkte hij aan het vraagstuk van foutcorrectie, waarbij hij een set krachtige algoritmes ontwikkelde. In 1950 publiceerde hij wat nu bekend staat als de Hamming-code, die momenteel in bepaalde situaties nog steeds toegepast wordt.
De hamming code voegt foutcorrigerende bits toe aan de originele binaire code. Als deze bits juist worden gerangschikt kunnen foutieve bits worden geïdentificeerd. Als je eenmaal weet welke bit er fout is, is het niet moeilijk meer, het kan immers alleen maar 0 of 1 zijn. De positie bepaling van de zogenaamde pariteit bits is hierin zeer belangrijk en onderdeel van het algoritme. Ik heb deze opdracht al eens gedaan en heb hierbij ook een PHP code geschreven waarmee hamming-codes terug te zetten zijn naar binaire code met een enkele fout detectie. Daarbij heb ik ook een PHP code geschreven om hamming-codes zelf te genereren, leek me destijds wel handig voor testdoeleinden. De positie bepaling is eigenlijk vrij simpel. Alle bitposities die tweemacht zijn worden gebruikt als pariteit bits. Dus 1,2,4,8,16,32 etc. etc. Hieronder een voorbeeld hoe je dit in PHP kan bepalen:
$sNewString = "01000001"; // Letter A in ASCII
for($i = 1; $i < strlen($sString); $i = ($i * 2))
{
$sNewString = substr($sNewString, 0, ($i - 1))."P".substr($sNewString, ($i - 1));
}
Zoals je hier boven kan zien bevat de variabele $sString de binaire code “01000001”, zodra $sString uit de for loop komt heeft $sString “PP0P100P0001″ als inhoud. Hierbij staat de letter P op de plek waar de pariteit bit moet komen. Op deze manier kan je goed zien of de for loop goed zijn werk doet en kan je je een voorstelling maken hoe het in zijn werk gaat. Nu moeten we gaan bepalen of de letter P moet worden vervangen met een 0 of 1. Om dit te kunnen bepalen heb ik ook een PHP code geschreven, maar ik ga eerst uitleggen hoe je het de hand zou kunnen doen (af te raden uiteraard).
In het bovenstaande voorbeeld hebben we 4 pariteit bits (noem ik vanaf nu P1, P2, P4 en P8). De pariteit bits kijken alleen naar een bepaald gedeelte van de nieuwe code (PP0P100P0001). P1 checkt alleen bit 1,3,5,7,9 etc. van de nieuwe code. P2 checkt alleen bit 2,3,6,7,10,11 etc. van de nieuwe code. P4 checkt alleen bit 4,5,6,7,12,13,14,15,20,21,22,23 etc. van de nieuwe. Enzovoort. Hoewel je het misschien niet meteen zien, zit hier echter een logica achter:
P1: skip 0 bits, check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc.
P2: skip 1 bit, check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc.
P4: skip 3 bits, check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc.
P8: skip 7 bits, check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc.
Op deze manier kunnen we makkelijk de letters P invullen. We gaan tellen in de nieuwe code (de bits die gecheckt moeten worden) en gaan dan kijken of de uitkomt even of oneven is. P1 checkt alleen bit 1, 3, 5, 7, 9, 11 van de nieuwe code, dus checkt hij PP0P100P0001. De letter P zelf weten we nog niets van dus P1 checkt alleen de cijfers 0+1+0+0+0 waarvan de uitkomst oneven is, namelijk 1. P1 wordt dan ook vervangen door een oneven nummer (we hebben alleen maar de keuze uit 0 en 1 dus dat is simpel). De nieuwe code komt er nu als volgt uit te zien 1P0P100P0001. Het zelfde geldt voor P2, deze pariteit checkt alleen bit 2,3,6,7,10,11 van de nieuwe code, dus checkt hij 1P0P100P0001. De letter P zelf weten we wederom niet dus P2 checkt alleen de cijfers 0+0+0+0+0 waarvan de uitkomst even is, namelijk 0. P2 wordt dan ook vervangen door een even nummer. De nieuwe code komt er nu als volgt uit te zien 100P100P0001. En zo kan je de rest van de pariteit bits ook nakijken. Zodra dit alles gedaan is, heb je daadwerkelijk een hamming-code gecreëerd, gefeliciteerd! De hamming-code komt er alsvolgt uit te zien “100010010001”. Zoals ik al aangaf heb ik hier ook een PHP code voor, deze code sluit aan op de PHP code die hierboven genoemd is. De PHP code is van zo’n 2 jaar en nu ik er weer naar kijk zie ik allemaal dingen die ik anders zou aanpakken, nu. Maar ja, ik post de code zoals ik hem toen gemaakt heb:
$aHammingMethod = array(1 => '1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51', 2 => '2,3,6,7,10,11,14,15,18,19,22,23,26,27,30,31,34,35,38,39,42,43,46,47,50,51', 4 => '4,5,6,7,12,13,14,15,20,21,22,23,28,29,30,31,36,37,38,39,44,45,46,47,52,53,54,55', 8 => '8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31,40,41,42,43,44,45,46,47,48', 16 => '16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31', 32 => '32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47');
for($i = 1; $i <= strlen($sNewString); $i = ($i * 2))
{
$iHammingBit = $i;
$aHammings = explode(",", $aHammingMethod[$iHammingBit]);
$iTrueBit = 0;
foreach($aHammings as $iValue)
{
if(substr($sNewString, ($iValue - 1), 1) == 1 && $iValue <= strlen($sNewString))
{
$iTrueBit ++;
}
}
if(($iTrueBit % 2) == 0)
{
$iNewHammingBit = 0;
}
else
{
$iNewHammingBit = 1;
}
$sTempNewString = str_replace("P", $iNewHammingBit, substr($sNewString, 0, $i));
$sNewString = $sTempNewString . substr($sNewString, strlen($sTempNewString));
}
Door middel van de $aHammingMethod array loop ik voorbij alle bit posities. Zoals je ziet gebruik ik de zelfde manier van for loop als bij het eerste voorbeeld. Ik moet met pariteit de cijfers controleren, dus met ik vanaf positie 1,2,4,8 controleren. Dit doe ik door middel van for($i = 1; $i <= strlen($sNewString); $i = ($i * 2)). Verder spreekt het naar mijn idee redelijk voor zichzelf. Er wordt gekeken naar het aantal keer 1 per pariteit. Door middel van een rest deling ((x % 2) == 0) bepaal ik of het even of oneven is ((x delen door 2) als de rest 0 is). Vervolgens wordt de P vervangen door een 1 of een 0, vrij simpel.
Nu snap ik dus hoe ze in de opdracht aan 46 bits komen, er zitten pariteit bits bij in, maar ja, hoe krijg je die er weer uit. Hamming-code is een foutcorrigerende code, dus er zal ook ongetwijfeld een fout in de gegeven opdracht zitten. Oke, dan ga ik ook een fout creëren in deze voorbeeld code, zodat ik het decoderen van de hamming-code makkelijker kan uitleggen. In dit voorbeeld is de hamming-code dus 100010010001, dit is de originele code inclusief 4 pariteit bits. Het schijnt dus zo te zijn dat ik in deze hamming-code een fout mag maken en dat ik toch terug kom bij het origineel. Ik verander 1 cijfer in dit voorbeeld.
Origineel: 100010010001
Foutief: 100010011001 (de 9e bit is hier dus fout!)
Het controleren op fouten is een kwestie van reverse engineering, omdat we nu weten hoe een hamming-code tot stand komt. We nemen bijna de zelfde PHP code als hier boven om te kijken of onze pariteit bits nog kloppen. Zoals ik al uit heb gelegd is P1 “1” geworden omdat alle bits, die P1 moest checken en bij elkaar opgeteld, oneven waren. Door middel van de volgende PHP code kun je kijken waar een fout wordt gedetecteerd:
$aHammingMethod = array(1 => '1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51', 2 => '2,3,6,7,10,11,14,15,18,19,22,23,26,27,30,31,34,35,38,39,42,43,46,47,50,51', 4 => '4,5,6,7,12,13,14,15,20,21,22,23,28,29,30,31,36,37,38,39,44,45,46,47,52,53,54,55', 8 => '8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31,40,41,42,43,44,45,46,47,48', 16 => '16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31', 32 => '32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47');
$sNewString = "100010011001"; // De hamming code met de foutieve bit op positie 9
for($i = 1; $i <= strlen($sNewString); $i = ($i * 2))
{
$iHammingBit = $i;
$aHammings = explode(",", $aHammingMethod[$iHammingBit]);
$iTrueBit = 0;
foreach($aHammings as $iValue)
{
if(substr($sNewString, ($iValue - 1), 1) == 1)
{
$iTrueBit ++;
}
}
if(($iTrueBit % 2) == 0)
{
$aHammingBits[$iHammingBit] = "Correct";
}
else
{
$aHammingBits[$iHammingBit] = "Foutief";
}
}
echo "<pre>".print_r($aHammingBits, true)."</pre>";
Na dat je de print_r() hebt bekeken zie je waarschijnlijk al wat er gebeurd, hierbij de print-out van de gemaakte array:
Array([1] => Foutief [2] => Correct [4] => Correct [8] => Foutief)
Snap je wat ik bedoel of zie je het nog niet? Ik zal je even iets op weg helpen, de foutieve bit zit op positie 9. Als je de pariteit bit posities bij elkaar op waar is “Foutief” staat, kom je uit op 9. Nu is het dus duidelijk waar de fout zit. Wat nu nog moet gebeuren is het corrigeren van deze bit en het verwijderen van de pariteit bits. De foutieve hamming-code was natuurlijk 100010011001, met de fout dik gedrukt. Deze kan dus nu herstelt worden aangezien het duidelijk is waar de fout zit, op positie 9, 100010010001. Nu moeten de pariteit bits worden verwijderd en dan blijft er als het goed is een valide binaire code over. De pariteit posities zijn altijd het zelfde en dus zijn deze bekend namelijk, P1 op positie 1, P2 op positie 2, P4 op positie 4 en P8 op positie 8 (100010010001). Als deze weg worden gelaten blijft er 01000001 over en ja, dit is de originele code waarmee dit voorbeeld oorspronkelijk begon. Ook hierbij heb ik uiteraard een stukje PHP code, eerst maar eens de PHP code waarmee de positie van de fout bepalen:
$iFaultBit = 0;
foreach($aHammingBits as $iKey => $sValue)
{
if($sValue == "Foutief")
{
$iFaultBit += $iKey;
}
}
Vervolgens heb ik een stukje PHP code gemaakt waarmee de foutieve bit wordt vervangen en de pariteit bits er uit worden gehaald:
if($iFaultBit > 0)
{
$sFinalPariteit = "";
$sFinal = "";
for($i = 0; $i < strlen($sNewString); $i ++)
{
if(($i + 1) == $iFaultBit)
{
$sFinalPariteit .= ($sNewString[$i] == 1) ? 0 : 1;
}
else
{
$sFinalPariteit .= $sNewString[$i];
}
}
$sFinal = $sFinalPariteit;
foreach($aHammingMethod as $iKey => $sValue)
{
$sFinal[$iKey - 1] = 'P';
}
$sFinal = str_replace("P", "", $sFinal);
echo "De foutieve bit is: {$iFaultBit}e bit<br />";
echo "String correctie met pariteit: {$sFinalPariteit}<br />";
echo "String correctie zonder pariteit: {$sFinal}";
}
else
{
echo "Deze binaire string is correct!";
}
De pariteit bits worden in de het bovenstaande voorbeeld weer vervangen door de letter P en worden vervolgens vervangen met niets. Ook de foute bit wordt in het bovenstaande voorbeeld vervangen door middel van een short if lus.
Het is dus gelukt om een hamming-code te maken en hierin een fout aan te brengen. Vervolgens is het gelukt deze fout te ontdekken weer te corrigeren! Nu maar eens terug naar de oorspronkelijke opdracht waar dit artikel mee begon. De binaire code die ik daar ontving is dus blijkbaar een hamming-code, vandaar de zijn lengte van 46 bits. Ik heb deze code (1000100101010101100100101001000111000001010010) aan het tweede gedeelte van mijn PHP code toegevoegd om te kijken of er een fout zit. Dit blijkt wel het geval te zijn (logisch op zich, anders was de opdracht niets waard), de fout zit op positie 15. Door de hamming-code door mijn PHP code te halen, wordt de fout gecorrigeerd, worden de pariteit bits verwijderd en blijft er binaire code over (0100010101110010010100100011000001010010).
Deze binaire code heb ik vervolgens terug gezet naar ASCII en daar komt het woord “ErR0R” uit. Dit is blijkbaar het wachtwoord waar de opdracht om vroeg, na het invullen van de code op de website was de opdracht geslaagd. Ik heb weer punten verdient en ondertussen heb ik veel kennis opgedaan over foutcorrectie in binaire code. De PHP code die ik hier heb gebruikt heb ik ruim 2 jaar geleden geschreven.