[PLUG-TALK] way off topic - CRC error correction, proper choice of algorithm

Keith Lofstrom keithl at kl-ic.com
Wed Jan 2 06:26:14 UTC 2008


> Keith Lofstrom wrote:
> > This will amuse some of you that do numerical computation.  The rest
> > of you can ignore it.  I am posting here so that it will get into the
> > public records.  It has little to do with Linux, though it may come
> > in handy for folks doing error correction on data records.
> > 
> > I am generating some long bit strings that may rarely develop one bit
> > error, and very rarely develop two.  I want to use a cheap error 
> > correction test and permutation (changing one or two bits) to do the
> > error correction.  
> 
> [snip]
> 
On Tue, Jan 01, 2008 at 10:06:14PM -0800, M. Edward (Ed) Borasky wrote:
> Why do I think you've re-invented some wheel here? ;)

A lot of people work on error correction schemes of various sorts;
Vitterbi, Reed-Muller, Hamming, 2-D and 3-D block correction, etc. 
Most schemes are expensive, and are poorly suited to my application,
which involves correcting error bits in a secret message, where the
actual message bits remain hidden during the correction process.  A
32 bit CRC on a 2048 bit message reduces crypto strength by only 32
bits, while many of the other methods reveal far more.

The literature notes the problems with CRC for double error correction,
but I have not seen solutions.  So I found one, cheezy and empirical
but usable.  If you can find other references to CRC for double error
correction (harder than mere detection!), I would be interested.  

Keith

-- 
Keith Lofstrom          keithl at keithl.com         Voice (503)-520-1993
KLIC --- Keith Lofstrom Integrated Circuits --- "Your Ideas in Silicon"
Design Contracting in Bipolar and CMOS - Analog, Digital, and Scan ICs



More information about the PLUG-talk mailing list