On 2012-08-03, Syd Rumpo <usenet@nononono.co.uk> wrote:> I've used that in a memory system, where CRCs were cheap and fast and > bit errors scarce. Is there a faster way to correct than the > suck-it-and-see method outlined above? I couldn't find one, but I'm no > expert.ECC memory uses a Hamming code, the payload and hash are interleaved such that the computed hash gives the address of the error bit, Hash computation is done by XORING th addresses of all the set bits. Address 0 is not used, and the hash goes into the bits that are powers of two. except for address zero all the other addresses are for payload. -- ⚂⚃ 100% natural --- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---
CRC codes
Started by ●August 2, 2012
Reply by ●August 3, 20122012-08-03
Reply by ●August 4, 20122012-08-04
On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:>In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote: > >(snip, I wrote) >>>CRCs are also used as hash functions in comparisons. That allows >>>one to quickly determine that two things are different, or that >>>they might be the same. > >> They are, but they're a mediocre choice at best. SHA-1, for example, >> is usually no slower than a CRC (in software), while taking less >> memory and not being nearly as easy to spoof. > >Certainly there are some cases where spoofing is important. > >The usual implentations of the unix diff command use a hash. >At least for comparing ones own files, one shouldn't need to >worry about spoofing.True, but my point was more along the lines of does CRC32 have any actual advantages over SHA-1 for this sort of task? Probably CRC32 would have an advantage in startup/completion overhead on small datasets. Other than that...?
Reply by ●August 4, 20122012-08-04
On 2012-08-04, Robert Wessel <robertwessel2@yahoo.com> wrote:> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt ><gah@ugcs.caltech.edu> wrote: > >>In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote: >> >>(snip, I wrote) >>>>CRCs are also used as hash functions in comparisons. That allows >>>>one to quickly determine that two things are different, or that >>>>they might be the same. >> >>> They are, but they're a mediocre choice at best. SHA-1, for example, >>> is usually no slower than a CRC (in software), while taking less >>> memory and not being nearly as easy to spoof.It depends on if you want to just detect errors or be able to fix them as well (or even know where they occured).SHA1 is good for detecting errors ( and making sure that some malicious person has not inserted a deliberate error such that it is undetectable by the hash) but it is not good at knowing what the errors was or correcting it.>> >>Certainly there are some cases where spoofing is important. >> >>The usual implentations of the unix diff command use a hash. >>At least for comparing ones own files, one shouldn't need to >>worry about spoofing. > > > True, but my point was more along the lines of does CRC32 have any > actual advantages over SHA-1 for this sort of task? Probably CRC32 > would have an advantage in startup/completion overhead on small > datasets. Other than that...?
Reply by ●August 4, 20122012-08-04
On Sat, 04 Aug 2012 16:32:15 GMT, unruh <unruh@invalid.ca> wrote:>On 2012-08-04, Robert Wessel <robertwessel2@yahoo.com> wrote: >> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt >><gah@ugcs.caltech.edu> wrote: >> >>>In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote: >>> >>>(snip, I wrote) >>>>>CRCs are also used as hash functions in comparisons. That allows >>>>>one to quickly determine that two things are different, or that >>>>>they might be the same. >>> >>>> They are, but they're a mediocre choice at best. SHA-1, for example, >>>> is usually no slower than a CRC (in software), while taking less >>>> memory and not being nearly as easy to spoof. > >It depends on if you want to just detect errors or be able to fix them >as well (or even know where they occured).SHA1 is good for detecting >errors ( and making sure that some malicious person has not inserted a >deliberate error such that it is undetectable by the hash) but it is not >good at knowing what the errors was or correcting it.But neither is CRC.
Reply by ●August 4, 20122012-08-04
On Sat, 04 Aug 2012 11:55:00 -0500, Robert Wessel <robertwessel2@yahoo.com> wrote:>On Sat, 04 Aug 2012 16:32:15 GMT, unruh <unruh@invalid.ca> wrote: > >>On 2012-08-04, Robert Wessel <robertwessel2@yahoo.com> wrote: >>> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt >>><gah@ugcs.caltech.edu> wrote: >>> >>>>In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote: >>>> >>>>(snip, I wrote) >>>>>>CRCs are also used as hash functions in comparisons. That allows >>>>>>one to quickly determine that two things are different, or that >>>>>>they might be the same. >>>> >>>>> They are, but they're a mediocre choice at best. SHA-1, for example, >>>>> is usually no slower than a CRC (in software), while taking less >>>>> memory and not being nearly as easy to spoof. >> >>It depends on if you want to just detect errors or be able to fix them >>as well (or even know where they occured).SHA1 is good for detecting >>errors ( and making sure that some malicious person has not inserted a >>deliberate error such that it is undetectable by the hash) but it is not >>good at knowing what the errors was or correcting it. > > >But neither is CRC.Right. Since CRCs don't include error location capability it isn't really good for that task. They can be brute-forced to fix a single bit error as previously described in this thread (which requires assuming that there was only one bit in error), but they are not generally used for error correction because they suck at it. From a system perspective for most communication systems CRCs are used for residual error detection (e.g., for cases where retransmission can be used) and FEC is used for channel error correction. The jobs are different. Eric Jacobsen Anchor Hill Communications www.anchorhill.com
Reply by ●August 4, 20122012-08-04
"Robert Wessel" <robertwessel2@yahoo.com> wrote in message news:ofhm18lasc532t7r817qua8m9g0qd75sd2@4ax.com...> On Fri, 03 Aug 2012 05:58:24 +0300, upsidedown@downunder.com wrote: > >>On Thu, 2 Aug 2012 19:21:18 -0700 (PDT), RichD >><r_delaney2001@yahoo.com> wrote: >> >>>I notice that the disk drive industry uses CRC error correction >>>codes. Can anybody tell me where these come from, do they >>>have their own standards? >> >>The disk drive industry use CRC error _detection_ codes, not CRC >>_correction_ codes. The drive industry is only interested if the data >>block is completely OK or if it is faulty. >> >> A faulty disk block usually contains a large burst error, which would >>be impossible to correct anyway, even with advanced ECCs, unless the >>data is interleaved between several blocks or even disk drives (RAID). >>The deinterleaving will convert a burst error to random errors which >>may recoverable with a suitable ECC. >> >>In principle, the ordinary CRCs could be used to correct _one_ bit >>error in a message or block. If the CRC check fails, invert each bit >>at a time in the message frame and recalculate CRC, until a match is >>found :-). This make sense only if the error probability is very low >>and it is a single bit error and when the retransmission delay would >>be unacceptable due to half-duplex delay in space communication. > > > That's wrong. These days all physical (hard) disk blocks have large > error checking/correcting blocks attached, and at current densities, > its rare (to the point of non-existence) that a block reads completely > cleanly. The Seagate Cheetah's, for example, can correct error bursts > up to 320 bits. The newer Savio's can correct bursts up to 520 bits. > And both of those are with 512 byte sectors. Non-enterprise drives > are a bit skimpier, though.CRC cant correct large block errors, other codes can.
Reply by ●August 4, 20122012-08-04
"Eric Jacobsen" <eric.jacobsen@ieee.org> wrote in message news:501d5a71.96136458@www.eternal-september.org...> On Sat, 04 Aug 2012 11:55:00 -0500, Robert Wessel > <robertwessel2@yahoo.com> wrote: > >>On Sat, 04 Aug 2012 16:32:15 GMT, unruh <unruh@invalid.ca> wrote: >> >>>On 2012-08-04, Robert Wessel <robertwessel2@yahoo.com> wrote: >>>> On Fri, 3 Aug 2012 16:45:38 +0000 (UTC), glen herrmannsfeldt >>>><gah@ugcs.caltech.edu> wrote: >>>> >>>>>In comp.dsp Robert Wessel <robertwessel2@yahoo.com> wrote: >>>>> >>>>>(snip, I wrote) >>>>>>>CRCs are also used as hash functions in comparisons. That allows >>>>>>>one to quickly determine that two things are different, or that >>>>>>>they might be the same. >>>>> >>>>>> They are, but they're a mediocre choice at best. SHA-1, for example, >>>>>> is usually no slower than a CRC (in software), while taking less >>>>>> memory and not being nearly as easy to spoof. >>> >>>It depends on if you want to just detect errors or be able to fix them >>>as well (or even know where they occured).SHA1 is good for detecting >>>errors ( and making sure that some malicious person has not inserted a >>>deliberate error such that it is undetectable by the hash) but it is not >>>good at knowing what the errors was or correcting it. >> >> >>But neither is CRC. > > Right. Since CRCs don't include error location capability it isn't > really good for that task. They can be brute-forced to fix a single > bit error as previously described in this thread (which requires > assuming that there was only one bit in error), but they are not > generally used for error correction because they suck at it. >a check sum can be used faster than CRC for one bit correction (brute forced). check sum horzontal and vertical can correct one bit error fast. need odd parity too.
Reply by ●August 4, 20122012-08-04
"Scott Fluhrer" <sfluhrer@ix.netcom.com> wrote in message news:1344009733.580710@rcdn-nntpcache-3...> > "Syd Rumpo" <usenet@nononono.co.uk> wrote in message > news:jvgdvu$3jt$1@dont-email.me... >> On 03/08/2012 03:58, upsidedown@downunder.com wrote: >> >> <snip> >> >>> In principle, the ordinary CRCs could be used to correct _one_ bit >>> error in a message or block. If the CRC check fails, invert each bit >>> at a time in the message frame and recalculate CRC, until a match is >>> found :-). This make sense only if the error probability is very low >>> and it is a single bit error and when the retransmission delay would >>> be unacceptable due to half-duplex delay in space communication. >> >> >> I've used that in a memory system, where CRCs were cheap and fast and bit >> errors scarce. Is there a faster way to correct than the suck-it-and-see >> method outlined above? I couldn't find one, but I'm no expert. > > Well, with CRC's, if you flip a bit at a specific position (say, bit 7) of > the input, a specific pattern of bits will flip in the CRC (and yes, for > any decent CRC, this specific pattern will differ for every position). > So, what you do is exclusive-or the CRC you received and the CRC you > calculated, and look that result in a table of precomupted error vectors > (for example, what the error vector would look like if we flipped bit 7). > This will tell you immediately what single bit error we got, and which bit > needed to be flipped (if any, the error might have been in the CRC itself) >not so. the crc is too short, out of a codeword set 2^128 (128 bits) and a crc of 16 bits 2^16 , you will have the same crc generated for 128/16 or 8 codewords> -- > poncho > >
Reply by ●August 4, 20122012-08-04
As was mentioned previously, burst errors are handled by interleaving schem= es so that a long burst of errors is spread over time so that it is present= ed to the ecc block as a sequence of single bit errors surrounded by good d= ata. There is no ecc that I know of that could handle a long burst error wi= thout interleaving.=20 Note that the severe inter-symbol interference problem mentioned earlier in= regard to disk drive read channels is partly solved by viterbi algorithms = in conjunction with channel coding schemes.=20 Bob
Reply by ●August 5, 20122012-08-05
On Sat, 4 Aug 2012 20:21:36 -0500, "Youdidnt buildthat" <invalid@invalid.com> wrote:> >"Scott Fluhrer" <sfluhrer@ix.netcom.com> wrote in message >news:1344009733.580710@rcdn-nntpcache-3... >> >> "Syd Rumpo" <usenet@nononono.co.uk> wrote in message >> news:jvgdvu$3jt$1@dont-email.me... >>> On 03/08/2012 03:58, upsidedown@downunder.com wrote: >>> >>> <snip> >>> >>>> In principle, the ordinary CRCs could be used to correct _one_ bit >>>> error in a message or block. If the CRC check fails, invert each bit >>>> at a time in the message frame and recalculate CRC, until a match is >>>> found :-). This make sense only if the error probability is very low >>>> and it is a single bit error and when the retransmission delay would >>>> be unacceptable due to half-duplex delay in space communication. >>> >>> >>> I've used that in a memory system, where CRCs were cheap and fast and bit >>> errors scarce. Is there a faster way to correct than the suck-it-and-see >>> method outlined above? I couldn't find one, but I'm no expert. >> >> Well, with CRC's, if you flip a bit at a specific position (say, bit 7) of >> the input, a specific pattern of bits will flip in the CRC (and yes, for >> any decent CRC, this specific pattern will differ for every position). >> So, what you do is exclusive-or the CRC you received and the CRC you >> calculated, and look that result in a table of precomupted error vectors >> (for example, what the error vector would look like if we flipped bit 7). >> This will tell you immediately what single bit error we got, and which bit >> needed to be flipped (if any, the error might have been in the CRC itself) >> > >not so. >the crc is too short, > out of a codeword set 2^128 (128 bits) and a crc of 16 bits 2^16 , you will >have the same crc generated for 128/16 or 8 codewordsNo, if you have a 128 bit block and a 16 bit check code, you'll get the same check code for approximately 2**(128-16) blocks (aka 2**112).
