Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm wondering to detect all the errors (i.e. their positions) in a codeword $(c_0, c_1, \cdots, c_{n-1})\in Q$ where $Q$ is an alphabet set with size $q$, i.e., to know whether $c_i$ is faulty or not, without asking for the exact initial value. Is it possible to achieve higher code rate than the ECC which corrects errors?

If so, could you show me or point me to some examples? For those famous ECCs such as BCH, Reed-Solomon Codes, LDPC codes, do they have the corresponding error locating versions which can have the higher rates?

share|improve this question
    
This is not a research question, and would fit better on math stack exchange. Whether you use a code to detect to correct errors is a function of the decoding algorithm, not the code. As for your actual question, a code the allows up to $e$ error to be corrected will detect up to $2e+1$. –  Chris Godsil Jun 6 '12 at 0:01
2  
The $2e+1$ is by the standard definition, but this question has a nonstandard definition of error detection. –  Douglas Zare Jun 6 '12 at 2:04
1  
I suppose if the alphabet has size 2, then this nonstandard definition of error detection is the standard definition of error correction. –  Gerry Myerson Jun 6 '12 at 3:28
    
Guys, sorry for misusing the term. Yes, the "detection code" I meant is actually "error locating codes". I just edited the question and the title to use "locating" instead of "detection". –  Kelvin Lee Jun 6 '12 at 16:49

1 Answer 1

up vote 4 down vote accepted

A bit of terminology:

An error-detection-code usually means something else. An error-detection-code is expected to raise a flag if something is wrong, IOW if the received sequence is not a valid codeword, or yet IOW at least one of the symbols $c_i$ is incorrect. It is NOT about telling that, for example, $c_{235}$, $c_{1123}$ and $c_{4095}$ are wrong but the rest are ok. A common (but not the only) technique for error-detection is a cyclic redundancy check aka CRC. To learn more look up CRC-polynomials.

As Chris Godsil points out, a code with minimum Hammind distance $2e+1$, thus guaranteed to be able to correct any $e$ errors at unknown locations, is also guaranteed to detect the presence of any pattern up to $2e$ errors. Simply because the received vectors will then not be a valid codeword - there are no other valid codewords within Hamming distance $2e$.

Some good error correcting codes (such as RS-codes) can also correct erasures = unknown errors at known locations. This is handy in e.g. CD-players, because the scratches can be detected, their locations are known, and can be filled in be an erasure-correcting-code. For example an RS-code with minimum distance $d$ can correct up to $d-1$ erasurers. This follows basically from Lagrange's interpolation polynomial formula: the words of an RS-code with length $n$ and minimum distance $d$ can be viewed as graphs of polynomials of degree $\le n-d$. With at most $d-1$ erasures, we know the value of such a polynomial at $n-d+1$ points and can fully recover it. The same does not hold for all error-correcting-codes, though.

You seem to be asking for codes that can find the error locations but not the error values. As Gerry Myerson promptly pointed out, if your alphabet is binary, this amounts to error correction, because the error can have only one value (= the bit has been toggled). Otherwise this does not match with any of the above concepts. For lack of a better term, let's call this an error-locating-code. It seems to me that to be able to locate all patterns of up to $e$ errors, you still need the code to have minimum Hamming distance at least $2e+1$. For if the minimum distance is at most $2e$ you can find vectors in-between two nearby codewords that differ from both at at most $e$ positions, and hence would be torn between two alternative sets of error locations. This argument suggests to me that a code capable of locating $e$ error will also be able to correct $e$ errors.

The scene may change somewhat, if you are only interested in success at high probability. I don't know.

But I'm a bit curious. What kind of an application did you have in mind? Rarely is a single symbol important, or if it is (say matters of national security or some such) we need the entire message to be correct, in which case the usual error-detection will get the job done. High reliability for bulk data is often achieved by some kind of a catenated scheme. Thinks of the data places in a matrix. Do error-correction column per column. If successfull, mark the data reliable. If not, mark it erased (=suspect). Then do erasure-correction row by row. This is actually how CD-players do it (I was just kidding earlier).

share|improve this answer
    
First, thanks for the nice answer! I'm sorry for misusing the term "detection" which causes the confusion. Yes, I actually meant "locating". Right, I think the error locating codes and ecc which detect/correct the same number of errors will have the same rate. As for the error locating codes, the decoders can just go ahead and enumerate all the possible values at those faulty positions to and find a correct codeword as the enumeration space is finite. I don't have any application in my mind, I was just wondering whether using such a locating code will be more beneficial than using a ECC... –  Kelvin Lee Jun 6 '12 at 17:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.