7 Jul
2000
7 Jul
'00
9:12 a.m.
pete(a)dunnington.u-net.com (Pete Turnbull) wrote:
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---
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).
Although disks use the V41 polynomial (X^16 + X^12 + X^5 + 1) not CRC32.
True, I was just using it as an example.