error correction
-
I need some error correction for an integer of 32 bits. I've found several solutions, like 'reed solomon', 'FEC', 'parity bit'. But all of those are for a lot of bits. I just need error correction for 32 bits and the error correction should be maximum 24 bits. Does any of you have any idea of how to clear this problem and which of the error corrections I should use (or even create one myself)?
-
I need some error correction for an integer of 32 bits. I've found several solutions, like 'reed solomon', 'FEC', 'parity bit'. But all of those are for a lot of bits. I just need error correction for 32 bits and the error correction should be maximum 24 bits. Does any of you have any idea of how to clear this problem and which of the error corrections I should use (or even create one myself)?
Hello, http://en.wikipedia.org/wiki/Hamming_code - that one is pretty easy, scalable (you decide of length of data chunk, longer chunk - lesser bits will be taken for correction purposes). Why parity bit is for lot of bits? You can use 1 parity bit for 2 bits of data, for 20 bits, for 200... (of course it will be less effective). Btw - Hamming codes can correct error bits, not only check if data is not corrupted.
-
Hello, http://en.wikipedia.org/wiki/Hamming_code - that one is pretty easy, scalable (you decide of length of data chunk, longer chunk - lesser bits will be taken for correction purposes). Why parity bit is for lot of bits? You can use 1 parity bit for 2 bits of data, for 20 bits, for 200... (of course it will be less effective). Btw - Hamming codes can correct error bits, not only check if data is not corrupted.
I see, hamming_code would be great indeed (thank you). But it's only possible for single error correction. In the best case I would like to correct every bit, but that's impossible, but I would like to have the highest efficiency. I'm now busy with trying parity, horizontal + vertical + diagonal. And then check if the parity's are ok. But is there another way than the hamming? Because I think this one is not really efficient.
-
I see, hamming_code would be great indeed (thank you). But it's only possible for single error correction. In the best case I would like to correct every bit, but that's impossible, but I would like to have the highest efficiency. I'm now busy with trying parity, horizontal + vertical + diagonal. And then check if the parity's are ok. But is there another way than the hamming? Because I think this one is not really efficient.
Hello, Actually, I think that Hamming is very efficient for what it offers (especially for longer streams, you add 1 bit for every *2 bits of data), if you need more bits corrected - use shorter version etc. If I have understand you well and by
Deresen wrote:
trying parity, horizontal + vertical + diagonal
you mean putting input into matrix and adding parity bits to every row/column, then you won't be able to fix any bits if you will have 2 errors (this is sometimes true, sometimes not, but still, you can't guarantee correcting 2 bits) and the cost of parity bits is much higher then using hamming. You can also google for Convolutional code, but I don't know much about them, so I can't guarantee it is what you have been lookng for.
-
I need some error correction for an integer of 32 bits. I've found several solutions, like 'reed solomon', 'FEC', 'parity bit'. But all of those are for a lot of bits. I just need error correction for 32 bits and the error correction should be maximum 24 bits. Does any of you have any idea of how to clear this problem and which of the error corrections I should use (or even create one myself)?
whats wrong with Reed-Solomon? If I understand your requirements, you need an RS(4,1) code over GF(2^8) or RS(8,2) over GF(2^4), and because the codeword size is small you can use Euclid's algorithm to efficiently compute the key equation rather than Berlekamp-Massey (modified). check this link out: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction[^]
-
I need some error correction for an integer of 32 bits. I've found several solutions, like 'reed solomon', 'FEC', 'parity bit'. But all of those are for a lot of bits. I just need error correction for 32 bits and the error correction should be maximum 24 bits. Does any of you have any idea of how to clear this problem and which of the error corrections I should use (or even create one myself)?
What is the expected nature of errors? Is there a significant likelihood of having multiple independent bit errors, or would bit errors more likely be concentrated? Correcting multiple independent bit errors is very hard; it is clearly impossible to do two-bit correction on 32 bits of data with less than 11 bits of ECC data (using 42 bits to code a 32-bit word, allowing for zero, one, or two errors, there would be 1,765 ways each code word could be represented; a 10-bit ECC would only allow for 1,024). On the other hand, if all bit errors will be localized in some particular fashion, error detection and correction becomes much simpler. For example, if all errors will be within a single byte, one can store a parity byte along with enough parity information to detect errors in each byte. If a problem is indicated with any byte, the parity byte will allow it to be corrected.
-
whats wrong with Reed-Solomon? If I understand your requirements, you need an RS(4,1) code over GF(2^8) or RS(8,2) over GF(2^4), and because the codeword size is small you can use Euclid's algorithm to efficiently compute the key equation rather than Berlekamp-Massey (modified). check this link out: http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction[^]
To be honest, I did not really understand the reed solomon error correction. And I've read this '2 byte errors per 32-byte block', this also means 2 bits per 32 bits. And that's to less for me. The big problem is that I also have to check the error correction, if that is right. So I have to correct that stream also. Is this a possibility with reed solomon? And could you please give a small example of how the reed solomon works, for instance with a byte?
-
To be honest, I did not really understand the reed solomon error correction. And I've read this '2 byte errors per 32-byte block', this also means 2 bits per 32 bits. And that's to less for me. The big problem is that I also have to check the error correction, if that is right. So I have to correct that stream also. Is this a possibility with reed solomon? And could you please give a small example of how the reed solomon works, for instance with a byte?
Reed-Solomon does provide the ability to detect errors and also correct them, RS is actually quite trivial to understand and implement, RS operates off-of a basis type which is called a symbol. A symbol can be any size from 2-bits and up. My suggestions were based on two symbol sizes, either an 8-bit or 4-bit symbol size. The 4-bit symbol size would be recommended in your case, as it means 8 symbols per your data block (32-bits). The proposed code of RS(8,2) over GF(2^4) means any two of the 8 symbols can have any number of bit errors (1-4 bits of error/burst error), from this upto both symbols of error can be accurately DETECTED and CORRECTED. Further more if you happen to know which bits are in error you can increase the correction capabilities 2 fold via erasure correction methods. If you're familiar with C++ the following library has RS code examples for various bit sizes: http://www.schifra.com/downloads.html[^]
-
Reed-Solomon does provide the ability to detect errors and also correct them, RS is actually quite trivial to understand and implement, RS operates off-of a basis type which is called a symbol. A symbol can be any size from 2-bits and up. My suggestions were based on two symbol sizes, either an 8-bit or 4-bit symbol size. The 4-bit symbol size would be recommended in your case, as it means 8 symbols per your data block (32-bits). The proposed code of RS(8,2) over GF(2^4) means any two of the 8 symbols can have any number of bit errors (1-4 bits of error/burst error), from this upto both symbols of error can be accurately DETECTED and CORRECTED. Further more if you happen to know which bits are in error you can increase the correction capabilities 2 fold via erasure correction methods. If you're familiar with C++ the following library has RS code examples for various bit sizes: http://www.schifra.com/downloads.html[^]