CODEWITHSUNDEEP
encodingnetwork-programmingdecodeencode
Malek
Malek

Reputation: 1329

Network Error correction

I need to make simulator to simulate sending say 4-bit data word after converting it into a code-word then receiving it with the possibility of noise and error happening throughout the process . The simulator needs to correct at least 3 errors.

the problem is I've been reading for hours about error detection and correction and it only talks about correcting 1 bit of error at most !

Linear hamming distance tables wouldn't work well (performance-wise) on more than 1 bit error correction .

Is there anyway to do this ? I just need a guideline Thank you !

Upvotes: 0

Views: 209

Answers (1)

pjkundert
pjkundert

Reputation: 489

I presume you are looking for Forward Error Correction; where you pre-calculate some "parity" data, append it to your original data, and then on reception, you regenerate the original data (detecting/correcting errors) and discard the parity.

If you are using C/C++, Javascript or Python, you can use https://github.com/pjkundert/ezpwd-reed-solomon. This library (available for use under GPLv3, LGPL and Commercial licenses) provides a simple, very fast implementation of Reed-Solomon FEC encoding and decoding.

It supports "symbol" (data element) sizes from 2 to 16 bits. The maximum "codeword" (data + parity) size depends on the number of bits in the word. For example, for 4-bit symbols, the maximum codeword size is 15 symbols. So, each block of data could be from 1 to 14 symbols, with the remaining parity symbols (totalling 15) generated by the Reed-Solomon encoder to produce the R-S "codeword". Later, when the symbols are received, the Reed-Solomon decoder validates and/or corrects the "codeword", and discards the parity symbols.

In C++, you would need to unpack your binary data into 4-bit symbols (probably just an array or std::vector of unsigned char, where each char holds a value from 0 to 15).

Then, decide how much error you want to correct for. Each erroneous symbol requires 2 Reed-Solomon parity symbols, so to correct for 3 errors, you need 6 parity symbols. You would use your expected error rate to determine the maximum number of symbols you can group together before you would expect to see 3 erroneous symbols.

Lets say your maximum expected error rate is 15%. So, you'd be able to collect 20 symbols before you would expect 3 bad symbols. Since the 6 parity symbols can also be erroneous, they are included in the 20. So, ideally, you would like to take 14 data symbols, then add 6 parity symbols for a total of 20 symbols in a codeword.

Problem is, your maximum R-S codeword size is 15, for 4-bit symbols. R-S codecs always have a maximum codeword size, for N-bit symbols, of 2^N-1. Hence for 4-bit symbols, 2^4-1 is 15 -- hence, an RS(15,...) codec is what you'll be using. The second number is the payload size -- the number of non-parity symbols. Therefore, for 6 parity -- RS(15,9). So, you'll be getting a bit more error resolving power than you need, using an RS(15,9) codec, being able to resolve 3 errors in every 15 symbols.

So, cut up your data into 9-symbol chunks. Create an ezpwd::rs::RS<15,9> instance, and use its encode method to add the 6 parity symbols. Send that out in your simulation.

After your simulator adds some errors, receive 15-symbol chunks, and run each chunk through the decode method of your RS<15,9> codec. It will return the number of erroneous symbols corrected -- or throw an exception, if the error load exceeds the capacity of the Reed-Solomon encoding.

Have fun!

Upvotes: 1

Related Questions