error correction code

Question

Is there any technique which can detect and correct all error bits. To my knowledge 100% error correction is not possible but is there any technique that possibly exists? And can hamming code correct only 1 bit error or more? what is the simplest error detection coding technique based on hardware complexity?

Answer 1

It is not possible to correct 'all' error bits, as then you would not have to transmit or store any information. The point of error correcting codes is to control the error rate. Let's say you have a medium with an error rate of 1 error in 1000 bits. With forward error correction of some sort, you can lower the error rate to 1 in 1000000 or better at the expense of some overhead for the coding. However, the code you use well only be able to correct errors under certain circumstances. Say, up to two bad bits per code word. However, you can calculate the probability of getting more than two errors per code word, a situation that will produce an error despite the code, and this becomes the new error rate.

As for Hamming codes, Hamming(7,4) is the most common example. This generates 3 parity bits for every 4 data bits (so the rate is 4/7, a little bit better than 1/2). This code can correct any single-bit error. It is possible to use a longer block length as in Hamming(15,11) and Hamming(31,26) to get a higher rate (less overhead). However, Hamming codes can only correct a single bit error in the entire block. So for Hamming(7,4) this would be 1 error in any 7-bit codeword. For Hamming(31,26) this would be one bit in any 31-bit codeword.

Other coding methods have different capabilities. For example, the Golay code G24 encodes 12 data bits in 24 code bits (rate 1/2) but can correct any 3 bit error or detect any 7 bit error.

Reed-solomon codes are another type of code. Reed-solomon codes add t symbols to each block and can detect up to t errors or correct up to t/2 errors. CDs use two layers of reed-solomon encoding along with interleaving to correct errors caused by scratches. RS(28,24) is used to encode 24 bit data blocks. The resulting 28 bit blocks are interleaved so that a large local group of errors will cause correctable single-bit errors in multiple codewords. Then the data is encoded with RS(32,28). Both RS(28,24) and RS(32,28) can correct up to 2 bit errors. Finally the 32 bit words are interleaved again with a different pattern. This means that a scratch that causes a long series of back-to-back bit errors will affect bits in different code words, allowing the errors to be corrected.

More powerful codes include Turbo codes and LDPC codes. These can be used to get arbitrarily close to the channel capacity of a given link (theoretical maximum achievable rate) and are used by NASA's Deep Space Network, among other things.

Simplest code to implement is probably Hamming(7,4), but this may or may not be appropriate for your application.

Answer 2

One's ability to correct "all error bits" will depend upon one's ability to characterize all combinations of bit errors that might possibly arise. If one can ensure that all errors with a non-trivial likelihood of occurring will have certain characteristics, and one will be able to handle all errors with those characteristics, then one will be able to handle all errors which have a non-trivial likelihood of occurring. Generally, if one wishes to use a certain size of packet to convey a certain amount of useful data (payload), more specific knowledge regarding the types of errors that can occur will reduce the size of packet necessary to carry a given payload.

If one has rather specific knowledge, the packet may only need to be a little larger than the payload. If one's knowledge is vague, the packet may exceed the payload size by many orders of magnitude. If the knowledge is too vague, it's possible no size of packet would be large enough to ensure reliable transmission.

Answer 3

You can answer this question by reducing it to its simplest case: I send you a bit, and then I tell you it might be wrong. What is the value that I sent you? There's no way to know.

The same applies to any larger collection of bits, in the worst case. If enough of the bits (including up to 100%) are unknown, then there's no way to figure out what they should have been.