This project is a task on course "Fundamentals of telecommunication technologies" by A.A. Kureev (is also a Project on Computer Technologies course [4th semester] at MIPT). The task was to implement encode/decode utilties for single-bit error correcting.
The following application has to be installed:
- CMake of version 3.15 (or higher)
Step 1: Clone this repository.
git clone [email protected]:d-r-tikhonov/Hamming-Code-Implementation.git
cd Hamming-Code-Implementation
Step 2: Create build
folder.
mkdir build
cd build
Step 3: Use CMake:
cmake ..
cmake --build . --config <Debug|Release>
Step 4: Build the project and run the program:
make
./bin/HammingCode
Single-bit Error Correction
...
#include "hamming_code.hpp"
...
uint32_t n_bits = 16;
uint32_t input_message = 0x4235;
std::string encoded_message = hamming_code::encode(input_message, n_bits);
std::cout << "Encoded message: 0x" << std::hex << std::stoul(encoded_message, 0, 2) << std::endl;
std::string decoded_message = hamming_code::decode(std::stoul(encoded_message, 0, 2), encoded_message.length());
std::cout << "Decoded message: 0x" << std::hex << std::stoul(decoded_message, 0, 2) << std::endl;
std::string encoded_noise_message = replaceRandomChar(encoded_message);
std::cout << "Noise encoded message: 0x" << std::hex << std::stoul(encoded_noise_message, 0, 2) << std::endl;
std::string decoded_noise_message = hamming_code::decode(std::stoul(encoded_noise_message, 0, 2), encoded_noise_message.length());
std::cout << "Decoded noise message: 0x" << std::hex << std::stoul(decoded_noise_message, 0, 2) << std::endl;
...
As a result of the program execution:
Encoded message: 0x8a3ac
Decoded message: 0x4235
Noise encoded message: 0xa3ac
Decoded noise message: 0x4235
Hamming code is a block code that is capable of detecting up to two simultaneous bit errors and correcting single-bit errors. It was developed by R.W. Hamming for error correction.
In this coding method, the source encodes the message by inserting redundant bits within the message. These redundant bits are extra bits that are generated and inserted at specific positions in the message itself to enable error detection and correction. When the destination receives this message, it performs recalculations to detect errors and find the bit position that has error.
- Step 1: Calculation of the number of redundant bits.
If the message contains n number of data bits, p number of redundant bits are added to it then the inequality
Note
The Hamming code is used to transmit 16-bit messages. How many redundant bits would be required for the receiver to be guaranteed to be able to detect and correct single bit errors?
Tip
Answer: 5 bits.
-
Step 2: Positioning the redundant bits.
-
Step 3: Calculating the values of each redundant bit.
- For example, let 100001 is the input message then 00100001001 is the encode message.
-
Step 1: Calculation of the number of redundant bits.
-
Step 2: Positioning the redundant bits.
-
Step 3: Parity checking.
-
Step 4: Error detection and correction.
-
For example, let 00101001001 is the accepted code vector then
$s = 0101 = 5$ the error is in the 5th position.
Tasks related to new content.
- Add readme file with newline #example
- Add a description of the algorithm
- Make unit tests
- Make more examples
- Make a client and server simulation
- Make documentation
- Make an implementation of Hamming's code
- Create new
CMakeLists.txt
- Create README.md
Further information about the Hamming encoding algorithm employed within hamming-code-implementation
can be found in the following resources: