This article will focus on Hamming codes - mainly, this represents an attempt to explain a little bit better how this method can help in detecting and correcting… 1 bit errors.
This method is not really useful at “higher level” - just because the data we work with is either 100% correct or has way more than 1 bit corrupted - and in this case, the Hamming code doesn’t work. It seems to be used in low-level (data link layer) networking and in some DRAMs - to prevent interferences from corrupting data.
As an example, we can consider this byte of data: 11010010
Hamming Encoding
The encoding implies taking the bits of the original message and computing a set of parity/control bits that will help us detect possible errors - we’ll know which bit is flipped, so the correction consists in negating that one bit. In the end, we insert the parity bits at positions equal to powers of 2 (1,2,4,8,…).
The encoded message will look like this: P1P2D1P4D2D3D4P8D5D6D7D8
- where D is a data bit, from our original message, and P a parity bit => 12 bits.
In order to determine the formulas for the parity bits it is important to understand the following part:
We say that a bit at position n, from our encoded data, is “controlled” by the parity bits whose positions, once summed, are equal to n. This can be written as:
| Position (n) | Bit | is controlled by parity bit(s) |
|---|---|---|
| 1 | P1 | P1 |
| 2 | P2 | P2 |
| 3 | D1 | P1 + P2 |
| 4 | P4 | P4 |
| 5 | D2 | P1 + P4 |
| 6 | D3 | P2 + P4 |
| 7 | D4 | P1 + P2 + P4 |
| 8 | P8 | P8 |
| 9 | D5 | P1 + P8 |
| 10 | D6 | P2 + P8 |
| 11 | D7 | P1 + P2 + P8 |
| 12 | D8 | P4 + P8 |
* notice that the sum of the indexes is equal to the position, for each row.
From the table, we observe that:
- P1 “controls” data bits: D1, D2, D4, D5, D7.
- P2 “controls” data bits: D1, D3, D4, D6, D7.
- P4 “controls” data bits: D2, D3, D4, D8.
- P8 “controls” data bit: D5, D6, D7, D8.
If we know this, we can write the equations for the parity bits:
P1 = D1 ^ D2 ^ D4 ^ D5 ^ D7
P2 = D1 ^ D3 ^ D4 ^ D6 ^ D7
P4 = D2 ^ D3 ^ D4 ^ D8
P8 = D5 ^ D6 ^ D7 ^ D8
* that’s XOR between them, ok?
If we apply this theory to our example 11010010, we get:
P1 = 1 ^ 1 ^ 1 ^ 0 ^ 1 = 0
P2 = 1 ^ 0 ^ 1 ^ 0 ^ 1 = 1
P4 = 1 ^ 0 ^ 1 ^ 0 = 0
P8 = 0 ^ 0 ^ 1 ^ 0 = 1
So the encoded data is: 011010110010.
Hamming Decoding
This part verifies the original bits and flips one of them if it’s corrupted. Keeping the same example, we use the value that we determined before, but to make it more interesting, we’ll corrupt 1 bit.
original: 011010110010
corrupted: 011010110110
* in this case I corrupted a data bit - if a parity bit gets corrupted there’s no need to correct anything, we only care about the data bits.
We have to recalculate the parity bits, but this time we’ll also include their values (taken from the encoded data):
P1 = P1 ^ D1 ^ D2 ^ D4 ^ D5 ^ D7
P2 = P2 ^ D1 ^ D3 ^ D4 ^ D6 ^ D7
P4 = P4 ^ D2 ^ D3 ^ D4 ^ D8
P8 = P8 ^ D5 ^ D6 ^ D7 ^ D8
If there were no bits corrupted, each new parity bit should be 0 (because we’re XOR-ing 2 identical bits). Replacing the values with the ones in the example, we get:
P1 = 0 ^ 1 ^ 1 ^ 1 ^ 0 ^ 1 = 0
P2 = 1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 1 = 1
P4 = 0 ^ 1 ^ 0 ^ 1 ^ 0 = 0
P8 = 1 ^ 0 ^ 1 ^ 1 ^ 0 = 1
This result is somehow obvious since I flipped/corrupted the 6th bit of data, and from the formulas, only P2 and P4 include that bit.
However, in a general case we won’t know which bit is corrupted…so here’s how these parity bits become useful. We use them to create the sindrome, so we arrange these bits like this:
P8P4P2P1
and by replacing, we get this number in binary: 1010 (10 in decimal) => the 10th bit, in the encoded data, is corrupted and needs some flippin’.
Aand…finally, we get the original encoded message: 011010110010. From here, we extract the data bits => 11010010.
The end
That’s all…probably not the most interesting article, but my teachers seem to love this subject (especially during the finals), so…just trying to help.
No comments:
Post a Comment