Hamming Codes
Hamming Codes
Here are some resources I have used on Hamming codes.
https://codegolf.stackexchange.com/questions/123219/generate-hamming-codes I tried to solve this code golf coding golf challenge and was unable to. There seems to be a complication with Hamming codes.
Wikipedia article—https://en.wikipedia.org/wiki/Hamming_code
Calculator with options for even or odd parity, sender or receiver, and endianness—https://www.compscilib.com/calculate/hamming-code?variation=default
https://www.omnicalculator.com/other/hamming-code—A calculator for Hamming code with an explanation with matrices and matrix multiplication and linear algebra
https://www.mathaddict.net/hamming.htm—this website explains how to build a Hamming code by checking and skipping positions. I think this is what my program is based on.
https://www.youtube.com/watch?v=X8jsijhllIA and https://www.youtube.com/watch?v=b3NxrZOu_CE—a series of two YouTube videos by the math channel 3blue1brown. the first video is an introduction and the second video delves into the code.
The function processHammingstring converts from strings and characters to 0s and 1s in a list/array. The function replaces everything except 0 and 1 with the empty string lambda λ / epsilon ϵ “”, effectively deleting other characters.
In[]:=
processHammingString[string_String?StringQ]:=ToExpression[Characters[StringReplace[string,Except[Characters["01"]]->""]]]
In[]:=
processHammingString["1100"]
Out[]=
{1,1,0,0}
This is useful because the input data can have separators and delimiters like space “ “, hyphen “-“, and underscore “_” for readability.
In[]:=
randomByteArray[length_/;Divisible[length,4]&&length>0]:=RandomChoice[{0,1},{length/4,4}]
In[]:=
randomByteString//ClearAll
In[]:=
randomByteString[length_/;Divisible[length,4]&&length>0,delimiterSeparator_:""]:=StringRiffle[StringJoin/@Map[ToString[#]&,randomByteArray[length],{2}],delimiterSeparator]
In[]:=
randomByteArray[20]
Out[]=
{{1,0,1,0},{1,0,0,0},{0,0,1,1},{0,1,1,1},{0,0,0,0}}
In[]:=
HammingArrayToString[input_]:=StringJoin[ToString/@input]
In[]:=
HammingArrayToStringOfBytes//ClearAll
In[]:=
HammingArrayToStringOfBytes[input_/;!StringQ[input],delimiterSeparator_:""]:=StringRiffle[StringJoin/@Map[ToString[#]&,Partition[PadLeft[Flatten[input],Ceiling[Length[Flatten[input]],4],0],4],{2}],delimiterSeparator]
In[]:=
HammingArrayToStringOfBytes[{1,0,1,0}]
Out[]=
1010
In[]:=
HammingArrayToStringOfBytes[RandomChoice[{0,1},37]," "]
Out[]=
0000 0111 0010 0110 0100 0110 0001 1000 0001 1001
In[]:=
HammingArrayToStringOfBytes[RandomChoice[{0,1},37],"-"]
Out[]=
0001-1010-0100-0111-0000-1100-1001-0111-1100-0010
In[]:=
HammingArrayToStringOfBytes[RandomChoice[{0,1},37],"_"]
Out[]=
0000_0111_0000_1011_0011_0010_0100_1001_0110_0011
Here is the default.
In[]:=
HammingArrayToStringOfBytes[RandomChoice[{0,1},37]]
Out[]=
0001000001101000011011111111101001111010
In[]:=
HammingArrayToStringOfBytes[RandomChoice[{0,1},37],""]
Out[]=
0000100001101000000000101000100111011111
Here we use the function.
In[]:=
HammingArrayToStringOfBytes[{1,0,1,1}]
Out[]=
1011
In[]:=
HammingArrayToStringOfBytes[EchoLabel["without zero padding"]@RandomChoice[{0,1},37],"-"]
»
without zero padding{0,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,1,1,1,0,1}
Out[]=
0000-0011-0000-1011-0010-1010-1000-0101-0111-1101
In[]:=
HammingArrayToStringOfBytes[EchoLabel["without zero padding"]@RandomChoice[{0,1},37],"-"]
»
without zero padding{1,0,1,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,0,0,0,0,1,0,1,0}
Out[]=
0001-0100-0001-0001-1110-0110-1111-1011-0000-1010
In[]:=
HammingArrayToStringOfBytes[EchoLabel["without zero padding"]@RandomChoice[{0,1},37],"_"]
»
without zero padding{1,1,1,1,1,0,0,0,1,0,1,1,1,1,0,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,1,1,1,0,0}
Out[]=
0001_1111_0001_0111_1011_0001_1010_0001_0001_1100
In[]:=
HammingArrayToStringOfBytes[EchoLabel["without zero padding"]@RandomChoice[{0,1},37]," "]
»
without zero padding{0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,1,0,0,1,1,1,0,1}
Out[]=
0000 0010 0110 0100 0000 1110 0000 0010 1001 1101
In[]:=
HammingArrayToStringOfBytes[EchoLabel["without zero padding"]@RandomChoice[{0,1},37],""]
»
without zero padding{0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0}
Out[]=
0000010001011101100100101000000011000100
They look the same.
In[]:=
EchoFunction[InputForm]@randomByteString[20]
»
"10000010011110100100"
Out[]=
10000010011110100100
In[]:=
dataset=Dataset[Table[<|"delimiterSeparator"->delimiterSeparator,"example"->randomByteString[20,delimiterSeparator]|>,{delimiterSeparator,{""," ","-","_"}}]]
Out[]=
The separators are handled.
In[]:=
Normal[dataset[All,processHammingString[#"example"]&]]
Out[]=
{{1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1},{1,1,1,1,0,1,0,1,1,0,1,0,1,0,1,1,0,0,1,0},{1,0,0,0,0,1,1,0,1,1,1,0,1,1,1,0,1,0,0,1},{0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,0,0,0,0}}
In[]:=
processHammingString["1100-1000"]
Out[]=
{1,1,0,0,1,0,0,0}
In[]:=
deleteblank[input_]:=DeleteCases[input,"_"]
The function CalculateHammingCode calculates how you would encode a message in Hamming code as a sender.
In[]:=
CalculateHammingCode[data_String?StringQ]:=CalculateHammingCode[ToExpression[Characters[StringReplace[data,Except[DigitCharacter]->""]]]]
In[]:=
CalculateHammingCode[list_List?ListQ/;ContainsOnly[list,{0,1}]]:=Module[{lengthoflist,lengthtoadd,lengthtouse,arraytoworkwith,lengthtoaddwithoutplus1,i,j,currentelement,numbersnotcharacters},numbersnotcharacters=list;lengthoflist=Length[list];lengthtoaddwithoutplus1=Floor[Log[2,lengthoflist]];lengthtoadd=Floor[Log[2,lengthoflist]]+1;lengthtouse=lengthoflist+lengthtoadd;arraytoworkwith=Normal[SparseArray[Thread[Table[,{pet,0,lengthtoaddwithoutplus1}]->"_"],{lengthtouse}]];For[i=1;j=1;,i<Length[arraytoworkwith]+1,i++,currentelement=arraytoworkwith[[i]];If[!StringMatchQ[ToString[currentelement],"_"],arraytoworkwith[[i]]=numbersnotcharacters[[j]];j=j+1;];];For[i=1,i<lengthtouse,i=i*2,arraytoworkwith[[i]]=whatvalue[deleteblank[Extract[arraytoworkwith,List/@Cases[Flatten[Extract[Partition[Drop[Range[lengthtouse],i-1],UpTo[i]],{1;;-1;;2}]],x_/;x<=lengthtouse]]]]];arraytoworkwith]
pet
2
I often use hamming code as a string so I added an option to return a string.
In[]:=
CalculateHammingCode[argument_,"String"]:=StringJoin[ToString/@CalculateHammingCode[argument]]
This is the default.
In[]:=
CalculateHammingCode["1001"]
Out[]=
{0,0,1,1,0,0,1}
If you want a string, you can do this:
In[]:=
StringJoin[ToString/@CalculateHammingCode["1001"]]
Out[]=
0011001
Or you can do this, which I prefer.
In[]:=
CalculateHammingCode["1001","String"]
Out[]=
0011001
And you can get the list too.
In[]:=
CalculateHammingCode[argument_,"List"]:=CalculateHammingCode[argument]
In[]:=
CalculateHammingCode["1001","List"]
Out[]=
{0,0,1,1,0,0,1}
The list is useful to output because if I output a string if I want to process that and find the bad bit I need to go back to an array/list of 0 and 1 so the default format is 0 and 1. The string format is useful for comparing and copying and pasting into Hamming code calculators. The string format is also useful and helpful for compact layout and display.
The function whatvalue takes a list and counts how many 1s. Then if there are an odd number of 1s, it returns 1 so there will be an even number of ones. If there are an even number of ones, then it will return 0 so the number of 1s will stay even. We want an even number of 1s because we have an even-parity Hamming code.
When we discover a bad bit, we know the correct bit is 0 if there’s a 1 and 1 if there’s a 0. If there were more than two possibilities like with base 3 ternary with 2’s we would not know this with mutually exclusive logic. This only works for base 2 binary with 0 and 1.
The function CorrectHammingCode takes a message encoded in Hamming code that has been received and corrects it. It works if there is no error (0 errors) or 1 bit flip error. It will not work if there have been 2 or more errors.
The function DecodeHammingCode takes hamming code that has been received, fixes the bad bit, and then extracts the bits in the message. It goes from the message with error correction to just the message.
I made this function to flip a random bit for demonstration purposes.
Generate a random message:
Generate the Hamming code for the message:
Pick a random bit to flip:
Flip the bit:
I made a function to flip a random bit.
The strings are not equal, so there is an error:
Fix the string with error:
We can also get the string instead.
The fixed string is equal:
Get the original data:
Here is a better formatted version.
This equals the test string:
Here they are side by side.
Here is the formatted string with 1 error.
See if you can spot where the error is. The bottom version is fixed.
I have some more work where I was comparing what I had with an online calculator. I expected to get the same result, but I didn’t. So either I’m wrong and the online calculator is wrong or I’m wrong and the online calculator is right or I’m right and the online calculator is wrong. I think I’m right and the online calculator is wrong, or at least the online calculator is wrong because the online-calculator said that what you would send for a 64-character message would take up 57 characters, which doesn’t make sense because the message with error correcting bits is always longer than the message without error-correcting bits. I don’t think the message with error correction can ever be shorter than the message without error-correction. When I applied Hamming error correction, I got a 71-character string.
The online calculator did match up for smaller examples.
Let’s do an example of checking the work.
The error is 0010 0010 0111 1010 should end with 1011.
end of checking work
end of checking work
paclet note
paclet note
Considering that there are many functions here, it might be worth combining them into a paclet or package. That’s kind of involved and complicated though and paclets are still experimental. I have submitted the function that generates the Hamming encoding for a message, the function that fixes a broken message, and the function that fixes the broken message and extracts the original data to the Function Repository.
attempt 2
attempt 2
Generate a random message:
Generate the Hamming code for the message:
I made a function to flip a random bit.
See if you can spot the error.
The strings are not equal, so there is an error:
Fix the string with error:
The fixed string is equal:
Let’s see what the calculator has.
The calculator says we should send
Our answers match!
Now let’s play the role of receiver. The message we receive is
Here is the difference.
The website says there is multiple errors but I don’t think there are. I think there is only 1 error.
Let’s work through a small example then.
We agree with the calculator!
We have a match!
So it seems that the website works for small to medium sized strings but not large messages like 001010100110000000001001000110000110100101001110100011, which has only 1 error while the calculator says has multiple errors.
So maybe don’t trust this calculator if the message you want to fix is 54 characters long or larger or longer.