Re: CRC, which error patterns can be detected?


"Jyrki Lahtonen" <lahtonen@xxxxxx> wrote in message
news:da05ko$rfc$1@xxxxxxxxxxxxxxxxx
>
> > It is still wrong.
> > You are solving a different problem that what is stated.
> > CRC is calculated on frame boundries, not on error pattern boundries.
> > Example of 11 being an error pattern, that exists in 1011, also 1101,
and
> > 11101 and 111
> > CRC codes are also prime, so simple division of error pattern and CRC is
> > just wrong.
> > Find this in any good code book
> > Good luck.
> >
> >
>
> Admittedly I did assume (from the context) that we were
> given the entire error pattern (preceding/trailing zeros
> thrown out). In that case it does not matter, whether the
> error pattern occurs at the end of the frame, at the
> beginning, or in the middle. That's what the word "cyclic"
> in CRC stands for, after all!

Not so.
They are different binary numbers and depend upon frame size.
You assumed a frame size. Which one must to make any sence out of the
problem.
And then filled in with zeros, which reduces the problem to simple binary
division.
CRC stands for cyclic reduncance check, named for the way it is calculated
using shift registers, not error patterns.


>
> Translations into algebra: e(x) is divisible by the check
> polynomial, if and only if x^t*e(x) is. This is because the
> check polynomial has a non-zero constant term, and we have
> unique factorization in Z_2[x].
>
> Yet another translation:
> the error string 00000000000000000000000000011
> is detected by a CRC whenever
> 11000000000000000000000000000
> or
> 00000000000001100000000000000
> is. Similarly
> 00000000000000000000000001011
> passes the CRC check whenever
> 10110000000000000000000000000
> or
> 00000000000010110000000000000
> does.
> This is also explained in any half decent coding
> theory book.

That is not error detection, it is pattern or code word detection.

If I have 00101000101110100110011001011011
Will your CRC code detect an error?
(first part - where is the CRC code - assume it is the last 3 bits on the
end - 011)
What does that mean? that the message word set has been devided up into 16
subsets which all have the same CRC code at the end.
(one is redundant)


>
> I am well aware that practical implementations
> of CRCs include tricks that avoid the all zero
> frame being accepted. But, come on! We're talking
> about a 3-bit CRC here.

How many primes are there, 3 bit CRCs?
(how many 16 bit prime CRC are there? How come industry only uses the first
two?)
Look that up in your book, better yet look it up in "shift regester
sequences", one of the first.

>That is about as non-standard
> as yEnc. This was obviously just an exercise in
> a course /textbook explaining the use of a check
> polynomial.

It is reviewing simple binary devision, an great oversimplification of how
CRCs are really used

>
> For extra credit we could also study those few
> cases, where the listed error patterns occur on
> a frame boundary (and are thus split into two
> distinct error patterns for the purposes of CRC).
> I leave that to you as an extra exercise.

The shift register gets zeroed out at EOF, so the short answer to your
question is no.

The purpose of CRC is to generate a check code based upon the data being
sent such that when recalculated on the recieve side you can detect if an
error was introduced (well some of them) However in this case, it is just
simple binary division.

>
> Or have you got another reasonable interpretation
> of this exercise? (solvable with the given data
> alone) Let's hear it!

>
> Cheers,
>
> Jyrki Lahtonen, PhD


.

Relevant Pages

  • Re: CRC, which error patterns can be detected?
    ... >> They are different binary numbers and depend upon frame size. ... >> CRC stands for cyclic reduncance check, named for the way it is ... > is a valid message, if and only if e ... Therefore an error pattern is undetected, ...
    (sci.math)
  • Re: CRC, which error patterns can be detected?
    ... CRC is calculated on frame boundries, not on error pattern boundries. ... CRC codes are also prime, so simple division of error pattern and CRC is just wrong. ... In that case it does not matter, whether the error pattern occurs at the end of the frame, at the beginning, or in the middle. ...
    (sci.math)
  • Re: CRC, which error patterns can be detected?
    ... CRC is calculated on frame boundries, not on error pattern boundries. ... CRC codes are also prime, so simple division of error pattern and CRC is ...
    (sci.math)
  • Re: crc on only data or including the address
    ... >For that i am implementing ethernet packet generator in the fpga. ... >am sending 64 bytes of frame from the fpga with the most significand ... Actually, what is sent is the FCS, which is bit reversed ... >2) Is CRC implemented on only data or on whole frame? ...
    (comp.arch.fpga)
  • Re: Suggestions for custom application-layer protocol?
    ... CRC is detected, the end of the first frame is known and it can now be ... The slave only needs to be able to ... updated CRC accumulator must be compared with the two most recently ...
    (comp.os.linux.embedded)