Hamming Codes — Even Parity Single Bit Error Detection in C++ and Python
I am a first-year computer science student, recently I learned about Hamming Codes and Error correction. I was impressed by the elegance of it, add to it the overwhelming explanation of 3Blue1Brown.
The video makes Hamming codes and error correction as discoverable as possible (which a lot of explanations lack), the instructor realizes the mathematics behind with stellar animations. In the end, we get a precious Aha moment, and trust me! nothing is more satisfying than that!
By the end of part 2, he also tries to implement a python code to do the same repetitive (yet not menial) task. The python code here is the replica of it (nearly in its entirety), I used it to get an idea of what actually needs to be done and how.
Now, I am currently learning C++, so I thought, it would be nice of a challenge to write a C++ code to do the same thing. I took it to be a menial task to implement it in C++ as I already had the Python code at my disposal, but as it turns out it was not as simple as I took it to be, it ended becoming a hell of a challenge, especially for a complete beginner in C++.
This article is intended to explain the thought process of writing the C++ code, if you want a thorough explanation of the Python code, you can find it on 3Blue1Brown video part 2. But once you get your head around the C++ one, Python code is easy enough to understand.
Both .py and .cpp file available on my GitHub
The overall idea is to take a bitstring from the user, XOR the positions of 1s, if the result is not 0, for sure there is an error position. Interestingly enough, the result of XOR gives the exact position of the error (in binary representation).
For a deeper understanding of how mathematics goes and more importantly why? 3Blue1Brown has beautifully explained it.
The first thing is to take input from the user. You may be tempted to take in the input as an integer but, that way you can’t access every 1/0 the user enters (as the input will be taken as a number). Instead, this can be achieved by using an array. But the problem with creating a C Standard array is that you have to predefine the number of elements expected. Hence instead, the most natural way of taking the input is to use strings.
(If you for some reason, choose take-in input as integers, you will have to take the bits one at a time. For example, Enter Bit 1: then Enter Bit 2 and so on….)
In its essence, strings are just const char* array, so we are still using arrays only.
I have used the String class in the C++ standard library for this purpose.
Parsing the input:
Having taken input as a string (const char array) so every element in the array is a character, but what we want is an integer… so we need some way to convert the characters to integers. Luckily, we know for sure that the inputs are going to be only 1s and 0s. This makes the problem way easier.
Simply put, we want to map the character to integers, C++ standard library has a class for this purpose called map.
So, creating a map from characters to integers, if we get a character 1, we map it to integer 1 and character 0 to integer 0.
(In C/C++, characters are represented but ‘’ (single quotation mark))
We iterate through the string mapping every character to either 1 or 0, if it is anything else, the map will return an error and the program is terminated, so need to add special error detection functionality. To store this information, we create a dynamic array (since we don’t know at the compilation time, what is going to be the size of the array) called bits. Further to optimize, we reserve the amount of memory needed to store the mapped characters (what now are integers).
(Notice the use of emplace_back instead of push_back for optimization)
After all the parsing is done, just to confirm the message is parsed correctly, display it to the screen.
Extracting all the positions with 1:
Our next task is to extract all the positions with 1.
Iterating through the array of the mapped characters, we check if the bit (integer/element) is 1, and append to a new dynamic array called pos (short for position).
Note: pos array is optimized the same way we did for bits array in the previous section.
XORing all of them:
The only thing we are left with is XORing all of the positions.
Note that the binary representation of positions needs to be XORed. But we don’t have to worry about it, as the computer reads the integers as its binary representation only.
(At the time of writing this article I realized, use of unsigned int would have been more suited for the purpose but, fortunately, it worked fine with int as well.)
I didn’t find any readymade function to iterate through the array XORing the bits (elements), so I ended up writing my own viz. xor_function.
This part just a child’s play. We just have to check if the result of XOR is 0.
If it is then, no worries, our message is fine
But if it isn’t then we got an error.
I did not write a function similar to Python code, because the process was straightforward. And I believe, writing a function would have led to a whole new stack memory allocation which I did not deem worth it. (Correct me if this reasoning is wrong, I am just a beginner) And on the flip side, when you write in C++ you tend to think more about memory and performance more! 😬
Interestingly enough the result of XOR gives the position of faulty bit position. So, flipping that bit will correct our error.
I rewrote the not operator to flip the bit, because, the bit is an integer for our program 😅 viz not_op. Not operator in Boolean algebra can be thought of as a map from 0 to 1 and from 1 to 0. Using the same map class from C++ STL, this can also be achieved.
Finally, we display the corrected message, and Voila we are done!