Inspired by Ben Eater and Grant Sanderson (3blue1brown).

This IP implements a simple encoder-decoder pair using Hamming codes to encode a 4-bit message a message of arbitrary length in order to make it resilient to 1-bit errors. Specifically, 1-bit errors can always be corrected automatically, and 2-or-more-bit errors can be detected.

In order to use this IP in this specific project, you need to install ghdl and gtkwave in order to run tests and also visualize the test benches of the IPs. You will also need GNU Make in order to make this project.

Once you have these dependencies installed, you can simply make the project:

$ make

The two IPs will then be compiled and unit tests will run for each IP in order to confirm their functionality.

Note: this is not an in-depth mathematical explanation. For more details, visit the links at the beginning of this README.

Let us take a 8-bit message block in order to examine how this codec works. For reasons that will become apparent later, for a block of size X only X - log2(X) - 1 bits can actually be used for the message itself; the other bits will be used for parity.

Bit 0 is always used for global parity (parity amongst all the bits of the block); bits whose index is a power of two - that is to say, bits 1, 2 and 4 in this case - are used for Hamming parity. The block layout is displayed on the following table:

GP is the global parity bit, Px are Hamming parity bits and Dx are data (or message) bits.

Hamming parity bits ensure parity over specific groups of bits. For example, P1 ensures parity amongst D1, D2 and D4. This allows us to sort of binary-search the message block in order to pinpoint 1-bit errors efficiently. Blocks are thus split in the following fashion:

By XORing bits in each parity group we can detect which groups have the wrong parity, and their overlap allows us to pinpoint exactly which bit caused the parity error.

The groups themselves are formed by following a very simple rule: for n from 0 to log2(X) - 1, where X is the block size, Hamming parity group n consists of all the bits whose index's nth bit is equal to 1. For example, for the first parity group (meaning we have to "look" at bit 0, the LSB) in the previous example, we have:

In order to perform the decoding, we must first XOR the elements of each parity group together. If we then form a vector whose bits are the results of the previous XORs, with the first parity group corresponding to bit 0, the second corresponding to bit 1 etc, this vector will give us the index of the erroneous bit in the message block.

If the index of the erroneous bit is non-zero, we should first correct it (by flipping it) and then verify the global parity of the message block using bit 0. If the global parity is correct, then there was only one error, and we successfully corrected it. If not, then there is at least one more error, which cannot be pinpointed, and thus the decoder IP should communicate an error code to the user.

If the index of the erroneous bit is zero and the global parity is correct, then there is no error. If, on the other hand, the global parity is incorrect, then there are at least two errors, and the IP should once again communicate an error code to the user.

Finally, for a block of size 256 (bits) this method of encoding is very efficient, as it only uses 3.5% of the message block for parity checks, and leaves the remaining 96.5% for useful message data. This IP limits the maximum block size to 256 bits however, because even though Hamming codes become more efficient as the block size increases, the blocks themselves also become more vulnerable to more-than-one-bit errors, which this IP cannot recover from.