A Reed-Solomon error-correcting code consisting of N symbols is guaranteed to detect up to N single-symbol replacements in an arbitrarily long input plus the ECC itself, and is also guaranteed to correct up to floor(N/2) single-symbol replacements in the same.
I can't claim to understand the math behind Reed-Solomon ECC, but I notice that all the implementations I could find operate on symbols in base 16, 64 or 256. This seems to suggest that 1024 etc. are also bases in which this scheme can operate with the right polynomial.
Is it possible to have an ECC scheme with exactly the above properties that operates on decimal symbols? Can Reed-Solomon be trivially adapted for this purpose?
(this question is prompted by my answer to a puzzling.SE question)
Asked By : romkyns
Answered By : Yuval Filmus
The property of Reed–Solomon codes that you mention is known as Maximum Distance Separability, and codes with this property are known as MDS codes. In coding theory the most popular type of code is a linear code, and these are only defined over alphabets which are prime powers. However, in the literature you can find some papers on MDS codes on arbitrary alphabets; I'll let you research that yourself.
For the specific case $N=1$, there is a very simple MDS code, namely checksum: you add to the original data a new digit whose value is the negated sum of the other digits (so that all new digits sum to zero). This code can detect any single error.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63661
0 comments:
Post a Comment
Let us know your responses and feedback