8
$\begingroup$

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)

| cite | improve this question | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Compare to the case of credit card numbers: en.wikipedia.org/wiki/Luhn_algorithm $\endgroup$ – Aaron Brick Sep 20 '16 at 3:42
  • $\begingroup$ That also links to Verhoeff algorithm and Damm algorithm which improve on Luhn by detecting every transposition in adjacent digits using just a single decimal check digit. Impressive! Luhn only detects some, while the simple mod 10 checksum detects none (but for short numbers mod 10 checksum can be checked mentally, which could be useful) $\endgroup$ – Roman Starkov Sep 20 '16 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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