Re: CRC, which error patterns can be detected?
- From: "jimmy" <rolf183@xxxxxxxxx>
- Date: Sun, 3 Jul 2005 23:18:03 -0500
"Jyrki Lahtonen" <lahtonen@xxxxxx> wrote in message
news:da2oha$1k7o$1@xxxxxxxxxxxxxxxxx
> Abelliae wrote:
>
> > 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.
> >
> Sigh. In my not so humble opinion the only way the OP's
> question made sense is the following: <problem> Suppose a
> message 'm' is being sent together with the 3 bit crc 'r'.
> These are concatenated to form a frame f=m|r. Due to
> transmission errors we receive f+e instead of f,
> where e is one of alternatives (cyclically shifted within
> the frame or not). Determine for each candidate e, whether
> the error is detected or not? </problem>
the operator "+" in f + e is "exclusive or" not "or" and not "and".
> Now the computation of the crc check is linear,
CRC uses "exclusive or", with "many to one" mapping.
> so f+e
> is a valid message, if and only if e (with zeros filled in)
> is a valid message (assuming that we don't do the standard
> tricks avoiding an acceptable all zeros frame).
f, f+e, and e all valid messages must have same remainders to be undetected.
> So the
> question CAN be answered with the knowledge of e alone.
> IOW the question is: Is 'e' an undetected error pattern
> or not?
>
> Yes, I know what a shift register sequence is. Do you know
> that a shift register simply computes a polynomial remainder
> (when the input sequence is treated as a polynomial and
> that is divided by the feedback polynomial)?
.....and.......
>
> The valid frames are the ones divisible by the feedback
> polynomial. Therefore an error pattern is undetected,
> if and only if it is divisible by the feedback polynomial
> itself.
not quite, need to seperate off the crc (r), and compair the r's.
View the encoding as seperating the entire message class into subclasses
(the number of different crcs) by the different remainders (r)
The error pattern is undetected if the errors remap the message back into
the same subclass (same remainder, same crc value)
ie, the remainders need to be different to detect errors.
>As the feedback polynomial (or check polynomial,
> whichever you want to call it) doesn't have x as a factor,
> e is divisible by the feedback polynomial, if and only if
> e shifted (iow multiplied by a power of x) is divisible.
Perhaps a way to state it is if e is divisible by fb polynomial with crc or
r of all zero, then it is an undetected error, as the final message r would
not change. (assuming f = m|r and (f+e)=m2|r (same r here) where m and m2
are two valid data in same crc subset, same crc or (r)) I have no problem
with shifting the error pattern around, if frame is loaded with all zeros.
>
> Cheers,
>
> Jyrki
.
- References:
- Re: CRC, which error patterns can be detected?
- From: Jyrki Lahtonen
- Re: CRC, which error patterns can be detected?
- Prev by Date: Re: Is this nonlinear ODE analytically solvable?
- Next by Date: x==x^2==x^3==x^4... mod N
- Previous by thread: Re: CRC, which error patterns can be detected?
- Next by thread: Re: Puny (punny) riddle
- Index(es):
Relevant Pages
|
