hamming burst error detection [closed]

Question

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?

Answer 1

---

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.

#include <iostream>
#include <bitset>

using namespace std;
#define k 3
uint8_t to_hadamard[2<<k];
void init_hadamard(){
  for(int i=0;i<(2<<k);++i){
    for(int j=(1<<k);j<(2<<k);++j){
        int temp=(i&j);
        for(int l=0;l<k;++l){
            temp = (temp>>1)^(temp&1);
        }
        to_hadamard[i]<<=1;
        to_hadamard[i]|=temp;
    }
  }
}

int main(){
    init_hadamard();

    for(int i=0;i<(2<<k);++i){
        cout << (bitset<(1<<k)>)(int) to_hadamard[i] << endl;   
    }
    return 0;
}

And here's the output for the above code:

00000000
01010101
00110011
01100110
00001111
01011010
00111100
01101001
11111111
10101010
11001100
10011001
11110000
10100101
11000011
10010110

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:

switch(data){
    case 0b00000000: message = 0; break;
    case 0b01010101: message = 1; break;
    case 0b00110011: message = 2; break;
    case 0b01100110: message = 3; break;
    case 0b00001111: message = 4; break;
    case 0b01011010: message = 5; break;
    case 0b00111100: message = 6; break;
    case 0b01101001: message = 7; break;
    case 0b11111111: message = 8; break;
    case 0b10101010: message = 9; break;
    case 0b11001100: message = 10; break;
    case 0b10011001: message = 11; break;
    case 0b11110000: message = 12; break;
    case 0b10100101: message = 13; break;
    case 0b11000011: message = 14; break;
    case 0b10010110: message = 15; break;
}

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.