Tim's own version of the Catweasel/Compaticard/whatever

From: Dwight Elvey <elvey_at_hal.com>
Date: Fri Jul 7 16:12:32 2000

pete_at_dunnington.u-net.com (Pete Turnbull) wrote:
>
> > CRC's are quite good at fixing a single small burst.
>
> Dwight, I think you're confusing CRC (Cyclic Redundancy Check) with ECC
> (Error Correction Code). CRC is very good at detecting errors, including
> bursts of errors that might slip by simpler checks, but AFAIK tells you
> next to nothing about where they occurred. ECC tells you enough to correct
> small errors. I've not heard of anyone using CRCs for correction (not
> directly, anyway).
>

Hi
 ECC can use CRC's. ECC can also use other types of generating
signitures that can be used. I hope someone on this group
will code this up to try because it is an interesting demonstration
of error correction. I don't recall the burst size that a CRC16
can correct but like other CRC's, it can correct some size,
without aliasing. To demonstrate it for youself, you can
flip one bit in a data set. After combining the final CRC
with the data's CRC, you usually have all zero or 1's, depending
on the seed. How you find the bad bit in the data is tricky but
not all that hard. There are three ways that I know of but
for a program, #1 is the most straight forward.

1. You play the CRC backwards with zeros replacing the data.
 when you get to the point that there is only one bit as a 1
 entering the CRC and the rest is zero's, you have found the
 count backwards that the error was at in the data.
2. You can play the CRC forward until is wraps around ( only
 2^16-1 maximum for CRC16 ), feeding zero's in as data.
 As you get to 2^16 -1 -DataSize, you watch for the single
 bit being one again, as you did before. That count into the
 data will be the error location.
3. If the polymonial you use is not prime, you can divide
 it into it's prime factors and find the playing forward
 each factor and watching for the 1 and all zero's pattern.
 ( The largest factor needs to have a cycle length longer that
 the data size or this doesn't work. ) You then multiply the
 counts by large prime numbers and divide by the least common
 denominator. This is called the Chinese Remaindor method.
 I also recall that one of the factors must be X+1 but I
 don't recall why.

 Anyway, the reason these all work it that you can take
a pattern of all 0's and set one bit to a 1 and the CRC
sum with the check CRC sum will be the same as the
CRC done with the data and the correct CRC. In otherwords,
the bit location is encoded in the CRC result since only one
bit location will cause that sum.
Dwight

---snip---
>
> Although disks use the V41 polynomial (X^16 + X^12 + X^5 + 1) not CRC32.

 True, I was just using it as an example.
Received on Fri Jul 07 2000 - 16:12:32 BST