- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

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

Date: Fri Jul 7 16:12:32 2000

pete_at_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---

True, I was just using it as an example.

Received on Fri Jul 07 2000 - 16:12:32 BST

*
This archive was generated by hypermail 2.3.0
: Fri Oct 10 2014 - 23:32:56 BST
*