cerror correction
I want to use Multiple Bit Error Detection and I have read a lot of sites but no one shows how to implement it using code and how the receiver performs the error correction to the received data.
The most important part is this Error Detection code needs to detect and correct the error. Just like Hamming Code, but for multiple bits.
Can anyone help, with providing books or any form of information that will help me to write up a program?
A Hamming code is a particular kind of error-correcting code (ECC) that allows single-bit errors in code words to be corrected. Such codes are used in data transmission or data storage systems in which it is not feasible to use retry mechanisms to recover the data when errors are detected. This type of error recovery is also known as forward error correction (FEC).
Constructing a Hamming code to protect, say, a 4-bit data word
Hamming codes are relatively easy to construct because they're based on parity logic. Each check bit is a parity bit for a particular subset of the data bits, and they're arranged so that the pattern of parity errors directly indicates the position of the bit error.
It takes three check bits to protect four data bits (the reason for this will become apparent shortly), giving a total of 7 bits in the encoded word. If you number the bit positions of an 8-bit word in binary, you see that there is one position that has no "1"s in its column, three positions that have a single "1" each, and four positions that have two or more "1"s.
If the four data bits are called A, B, C and D, and our three check bits are X, Y and Z, we place them in the columns such that the check bits are in the columns with one "1" and the data bits are in the columns with more than one "1". The bit in position 0 is not used.
Bit position: 7 6 5 4 3 2 1 0
in binary: 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
Bit: A B C X D Y Z -
The check bit X is set or cleared so that all of the bits with a "1" in the top row — A, B C and X — have even parity. Similarly, the check bit Y is the parity bit for all of the bits with a "1" in the second row (A, B and D), and the check bit Z is the parity bit for all of the bits with a "1" in the third row (A, C and D).
Now all seven bits — the codeword — are transmitted (or stored), usually reordered so that the data bits appear in their original sequence: A B C D X Y Z. When they're received (or retrieved) later, the data bits are put through the same encoding process as before, producing three new check bits X', Y' and Z'. If the new check bits are XOR'd with the received check bits, an interesting thing occurs. If there's no error in the received bits, the result of the XOR is all zeros. But if there's a single bit error in any of the seven received bits, the result of the XOR is a nonzero three-bit number called the "syndrome" that directly indicates the position of the bit error as defined in the table above. If the bit in this position is flipped, then the original 7-bit codeword is perfectly reconstructed.
A couple of examples will illustrate this. Let's assume that the data bits are all zero, which also means that all of the check bits are zero as well. If bit "B" is set in the received word, then the recomputed check bits X'Y'Z' (and the syndrome) will be 110, which is the bit position for B. If bit "Y" is set in the received word, then the recomputed check bits will be "000", and the syndrome will be "010", which is the bit position for Y.
Hamming codes get more efficient with larger codewords. Basically, you need enough check bits to enumerate all of the data bits plus the check bits plus one. Therefore, four check bits can protect up to 11 data bits, five check bits can protect up to 26 data bits, and so on. Eventually you get to the point where if you have 8 bytes of data (64 bits) with a parity bit on each byte, you have enough parity bits to do ECC on the 64 bits of data instead.
Different (but equivalent) Hamming codes
Given a specific number N of check bits, there are 2N equivalent Hamming codes that can be constructed by arbitrarily choosing each check bit to have either "even" or "odd" parity within its group of data bits. As long as the encoder and the decoder use the same definitions for the check bits, all of the properties of the Hamming code are preserved.
Sometimes it's useful to define the check bits so that an encoded word of all-zeros or all-ones is always detected as an error.
What happens when multiple bits get flipped in a Hamming codeword
Multible bit errors in a Hamming code cause trouble. Two bit errors will always be detected as an error, but the wrong bit will get flipped by the correction logic, resulting in gibberish. If there are more than two bits in error, the received codeword may appear to be a valid one (but different from the original), which means that the error may or may not be detected.
In any case, the error-correcting logic can't tell the difference between single bit errors and multiple bit errors, and so the corrected output can't be relied on.
Extending a Hamming code to detect double-bit errors
Any single-error correcting Hamming code can be extended to reliably detect double bit errors by adding one more parity bit over the entire encoded word. This type of code is called a SECDED (single-error correcting, double-error detecting) code. It can always distinguish a double bit error from a single bit error, and it detects more types of multiple bit errors than a bare Hamming code does.
It works like this: All valid code words are (a minimum of) Hamming distance 3 apart. The "Hamming distance" between two words is defined as the number of bits in corresponding positions that are different. Any single-bit error is distance one from a valid word, and the correction algorithm converts the received word to the nearest valid one.
If a double error occurs, the parity of the word is not affected, but the correction algorithm still corrects the received word, which is distance two from the original valid word, but distance one from some other valid (but wrong) word. It does this by flipping one bit, which may or may not be one of the erroneous bits. Now the word has either one or three bits flipped, and the original double error is now detected by the parity checker.
Note that this works even when the parity bit itself is involved in a single-bit or double-bit error. It isn't hard to work out all the combinations.
Think about the probability of an uncorrectable error occurring in each message. If you just send r bits, all errors are uncorrectable, so the chance of a successfully sent message is $$(1-P(bitError))^r$$ (in other words, all bits have to pass through with no error.) Now, say you spread the energy just a little to add k error correction bits, such that you can correct a single bit error. Then the chance of a single bit error does go up due to the weaker signal, but the chance of a successfully sent message becomes something like $$(1-P(higherBitError))^{r+k} + (r+k)(P(higherBitError)(1-P(higherBitError))^{r+k-1})$$ (In other words, it's successful if all bits pass through with no error as before. But it's also successful in the (r+k) possible situations where 1 bit has an error and the other r+k-1 bits don't.)
I'm not 100% sure my probability formulation is exactly correct, but you can see the idea: there are now more possible situations where you win. Depending on the values of r, k and how much the bit error probability increases, the error correction will often result in a higher probability of a successfully sent message.
Best Answer
I've only used a LUT (Look up table) to solve this at the receiving side, because it was quick and worked for me.
But this time I will research further, deeper into the abyss, of how to mathematically get the correct number.
So this will be a continuation from this answer, so please read that one first if you feel that "What is this mumbo jumbo he's talkin 'bout?"
Here's some code I wrote a couple of weeks back, it makes a LUT for the sender side, and then you simply insert your number into the LUT array and out pops the wanted block message that you will actually send.
And here's the output for the above code:
This means that if you want to send \$1100_2\$, then you look up row number \$1100_2 => 8+4 => 12_{10}\$. Which is according to the bit list above, \$11110000_2\$
Okay, everything is all good.
So let's say you receive \$11110000_2\$, how will you be able to tell that it was \$1100_2\$?
One way of doing it for Punctured Hadamard(k=3) is to simply matrix multiply your 8 bit block by the parity matrix.
$$ \tiny{ \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \end{pmatrix} × \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix} = \begin{pmatrix} \color{green}{0} & \color{green}{0} & \color{green}{0} & \color{green}{0} \\ \end{pmatrix} } $$
This tells you that what you received contains no error no bit has been flipped.
So after this, just simply send the data into a switch statement:
If, however, there is one bit wrong in the data sent, then the parity check multiplication will tell you which bit that is wrong, offset by 8. So if bit 2 is wrong, then the parity multiplication will give you the number \$1010_2\$. Subtract 8 and you get \$0010_2\$, this is the bit that should be flipped back. So do that, with a XOR operation, and then put it into the switch case above and you will receive your message that was sent.
If you however get a number that is less than 8 after the parity multplication, then it means that you have 2 errors, you can't identify which two bits that are wrong because the hamming distance for correction is only 1 with Punctured Hadamard(k=3). So how you deal with parity multplication that is less than 8 => 2 errors, is up to you. Either you ask for the data to be sent again, or you make some more sophisticated switch case like the one above which will give you further information if 2 bits are wrong. Though this will give you several answers, so if you want to only get one answer, then you will have to look at how you treat your data that is being sent. Maybe you will never have a \$1001_2\$ followed by a \$0110_2\$, then this means that you can deduct which of several answers that is not correct. But this also means that you will have to make some statistics on the data being sent. Oh well..
This is all fine and dandy for Punctured Hadamard k=3. You are talking about burst errors, in my opinion that is more like 4 errors in a row. This means that \$4 > \lfloor \frac{2^{k-1}-1}{2} \rfloor\$. After some calculations you will see that 2^{k-1} has to be at least 10, with an integer power and base 2 you will get 32. \$\lfloor \frac{2^{5-1}-1}{2} \rfloor = 7\$,\$ \lfloor \frac{2^{4-1}-1}{2} \rfloor = 3\$.
So we will use k = 5 and be able to correct 7 errors, and detect \$2^{5-1}-1=15\$
For clarity, the Punctured Hadamard that will be used will be:
\$[n,k,d]\$ = [\$2^{k},k+1,2^{k-1}\$], k=5, => [\$32,6,16\$]
This means our parity check matrix will have 6 columns and 64 (\$=2^6\$) rows. This also means that if we want to send 6 bits of data, then it will be contained in a 32 bit block.
I will not bore you all with a 6×64 matrix multiplied by a 1×6 matrix. Instead I will write what I'm doing.
Let's say I want to send the number \$43_{10} = 32 + 8 + 2 + 1 = 101011 _2\$, then the block message that will be sent will be this:
\$1001100101100110100110010110011010011001011001101001100101100110_2\$
Here are a couple of errors inserted into the block message, that we will see if we can identify.
(1) \$10011001\color{red}{1}11001101001100101100110..._2\$
(2) \$10011001\color{red}{1}\color{red}{0}1001101001100101100110..._2\$
(3) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}001101001100101100110..._2\$
(4) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}01101001100101100110..._2\$
(5) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}\color{red}{1}1101001100101100110..._2\$
(6) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}\color{red}{1}\color{red}{0}101001100101100110..._2\$
(7) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}\color{red}{1}\color{red}{0}\color{red}{0}01001100101100110..._2\$
(8) \$10011001\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}\color{red}{1}\color{red}{0}\color{red}{0}\color{red}{1}1001100101100110..._2\$
That's 8 of them, we should be able to correct 7 bits of errors, and detect 15 errors. I will now multiply these by the parity matrix and tell you the result.
(1) \$101000_2=40_{10}\$
(2) \$000001_2=1_{10}\$
(3) \$101011_2=43_{10}\$
(4) \$000000_2=0_{10}\$
(5) \$101100_2=44_{10}\$
(6) \$000001_2=1_{10}\$
(7) \$101111_2=47_{10}\$
(8) \$000000_2=0_{10}\$
Subtract 32 from 40, and you get 8. For (1) it was the 8th bit (from left) that had an error. You can pinpoint which one that is wrong.
for (2) there's 2 bits of errors and you are always below 32. You can't.... really pinpoint which two that are wrong... There's not enough information from the parity multiplication to deduce those two...
Hmmm... There's a couple of zeros... interesting which means that it's no errors... which there are...
The (4) above and (8) above was copied and compared to other block messages when I used the generator matrix for values of 0 to 63. There were none that matched. So (4) and (8) above is unique to the number 43. So if there are 4 errors.. then the parity multiplication will say 0... It feels as if I'm inventing the wheel... and failing.
Hmm, I'm out on deep water and have only used LUT's so far. And I've spent too much time on this as someone who has had a horrible teacher in this subject and I don't regularly work with this on a daily basis. => I'm not an expert in this subject. Oh well.
If I were to solve it with k=5 => block messages with 64 bits. Then I can't use a LUT with \$2^{64}\$ rows. That's just silly. In all honesty I'd probably use a switch statement that only covers 0 and 7 bits error. The first switch statement in this answer only covers 0 bits of error and hopes that you fixed the wrong bit if there is one before you insert it. You can easily just add more "case (1): 43, case (2): 43, case(3):43 and etc... for all... shapes of 7 bit errors...... No wait... this will give you a ridiculous amount of cases just for the number 43. The different combination of 7 bits of error in a 64 bit message is n choose k => 64 choose 7 => \${64 \choose 7}=313092960768\approx 313 \text{ billion}\$ different ways. That's.. a sick amount of cases just to solve 7 bits of error for the number 43... No... this is not the right way...
Or you just calculate the block message for each possible message, to a XOR compare between message received and block message and count the number of ones that differ, each one is an error. Choose the possible message with least ones. This can certainly be made with a LUT (like the C++ code above). At least it doesn't require 64*313 billion if statements...
But a more elegant way... Hmm, I actually have no idea.