Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: CRC check indication of bad fiber

>Mike Salzman wrote:
>Hi, I am treading on thin ice here, but I think that you may not be off
>the hook yet.  The CRC is designed to detect up to (from memory...) 3
>bit errors in a packet.
>I suppose that if a robust scrambler let through a packet that had more
>than 3 bits scrambled it is conceivable that the CRC might not detect
>In the days of the 1Gig session, Howie Johnson went through an elaborate
>proof to show that the underlying code would catch any such escape
>condition.  However, that was a block code with a strong inherent
>protection of multibit errors.


I think the underlying proof of Howie's you're referring to has to do
with PCS coding error robustness. This was based on the use of 8B/10B
coding, and the selection of specific data and special code-group
combinations which would greatly reduce the probability that  some
combination of errors would result in an undetected (data integrity)
error. The latter error bypassing detection by either 8B/10B and CRC. I
have Howie's proof only as an email. I'll enclose it below FYI.

The CRC used for GbE is able to detect

- all single and double-bit errors
- all odd numbers of errors
- all burst errors less than or equal to the degree of the polynomial
- most burst errors greater than the degree of the polynomial used

The key to 1000BASE-X error robustness is that the PCS efficiently maps
8B/10B code-groups with knowledge of the limitations of CRC-32 in a
fashion which reduces the probability of these limitations. Howie did a
fantastic job!

Once again, I'm advocating that we carefully consider the ramifications
of changing to an alternate coding scheme, including scrambling. All
layers of a system need to be considered as a system is only as strong
as its weakest link.
I don't intend to imply that SONET is weaker or stronger than 1000BASE-X
in terms of error robustness. However, I do imply that any change in
coding techniques must be carefully considered.

CRC codes have been used for years to detect data errors on interfaces,
and their operation and capabilities are well understood. Two codes that
have found wide use are CRC–16 and CRC–32. As the names imply, CRC–16
makes use of a 16-bit LFSR, while CRC–32 uses a 32-bit LFSR.

Best Regards,

Richard Taborek Sr.    Tel: 650 210 8800 x101 or 408 370 9233       
Principal Architect         Fax: 650 940 1898 or 408 374 3645
Transcendata, Inc.           Email: rtaborek@xxxxxxxxxxxxxxxx 
1029 Corporation Way     
Palo Alto, CA 94303-4305    Alt email: rtaborek@xxxxxxxxxxxxx


Date: Thu, 25 Jul 1996 17:51:34 -0700 (PDT)
To: stds-802-3-hssg@xxxxxxxx
From: "Howard W. Johnson" <howiej@xxxxxxxxxxxx>
Subject: proof of error robustness (last try?)

RE: SOP/EOP codes

I offer the following proof of the robusteness of our
SOP/EOP code selection for Gigabit Ethernet. Please review
it carefully, and let me know if you spot any errors.

- - - - - -
Use 8B10B codes as outlined by Rich Taborek in his
presentation to the May, 1995 802.3 interim.

Check to see if any pattern of 3 or fewer errors can cause
an undetected bad packet.

- - - - - - - - - - - - - -
6/24/96 update to remove references to the packet LENGTH
field. Also permit packet to be preceded by "RRR" pattern,
instead of IDLE.
7/24/96 update to reflect change in assignments of 810B T
and R patterns (this helps correct an error in the last clause of
the proof, which has now been fixed).

- - - - - - - - - - -
802.3 packet format (this table requires a
fixed-width font, like Courier)

     packet         8B10B codes
     ------         -----------

     IDLE           I1
0    PREAMBLE       S
1    PREAMBLE       Data = 10101010
2    PREAMBLE       Data = 10101010
3    PREAMBLE       Data = 10101010
4    PREAMBLE       Data = 10101010
5    PREAMBLE       Data = 10101010
6    PREAMBLE       Data = 10101010
7    SFD            Data = 10101011
8    DA             Data = DA...
     LLC DATA       Data = LLC DATA...
     FCS1           Data = FCS1 octet...
     FCS2           Data = FCS2 octet...
     FCS3           Data = FCS3 octet...
     FCS4           Data = FCS4 octet...
                    R    (First R required)
                    R    (additional R's optionally
                    R     needed to extend carrier,
                    R     and to round out the whole
                    R     packet to an even number
                    R     of octets)
     IDLE           I1/I3
     IDLE           I1
     IDLE           I1
     IDLE           I1

   I1 Repeating 16-bit sequence used to signal IDLE.  This
      sequence, like the "JK" sequence used in 100BASE-TX,
      incorporates a word-sync pattern recognizable by the
      low-level hardware. The first octet is always [K28.5].
   S  Start-of-packet indicator. [K27.7]
   PREAMBLE     Like 100BASE-X, we just encode the
      historical preamble sequence and send it as regular
   SFD     The historical Ethernet SFD is coded and sent
      just like regular data.
   DA, SA, LENGTH, LLC Data, FCS fields are all coded and
      sent just like regular data.
   T  First octet of required end-of-packet sequence.
   R  Second octet of end-of-packet sequence. [K23.7]. (a
      valid end-of-packet can be [T,R,R] or [T,R,I]).
   R  To accommodate carrier extension in half-duplex mode,
      additional R characters are appended to the packet.
   R  If needed to align the I1 onto an even octet boundary,
      another additional R character may be appended to the
NOTE: If we use packet bursting, then sometimes a packet is
preceeded by "R", not "I". That case is also considered.

(1) The IEEE 802 functional objectives ask that we be able
to detect any combination of 3 errors, occurring anywhere
within the packet, including errors in the SOP/EOP codes

(2) Any individual error occurring in a data word will
produce either: (a) a detectable violation of the DC balance
criteria, or (b) a burst of no more than 8 bits in error in
the decoded data stream.

(3) Any odd number of errors occurring in the data or
preamble fields will be dectected as: (a) a detectable
violation of the DC balance criteria

(4) The EOP code has been selected to have different
encodings for positive and negative disparity. The EOP code
itself does not **change** the running disparity, but it
permits detection of the correctness of the running
disparity (in 802.3 terms, it can be used to check the DC
balance). In effect, the EOP code provides one huge parity
bit on the whole packet.

(5) The following Hamming distance calculations apply:
T and R differ in at least 2 bits
R and I differ in at least 3 bits
I and S differ in at least 5 bits
R and S differ in at least 2 bits
T and Data differ in some cases by only 1 bit
R and Data differ in some cases by only 1 bit
In the case that any Data word and the R code word come from
columns of the coding table having opposite disparity, the
distance between R and Data is at least 2. If the Data has a
weight of 6 or 4 (non-balanced), the distance is at least 3.

Let us first treat errors occurring in the data field.

     Any pattern of three errors occurring in the data field
     will be detected by the parity-like capability of the
     Any pattern of two or fewer errors occurring in the
     data field will result in two or fewer bursts of eight
     errors.  Up to a packet length of 1518 octets, the CRC
     properly detects all combinations of two eight-bit
     errors (this property has been verified by direct
     enumeration of the possibilities).
Let us next treat error patterns affecting the SOP code

     We assume the receiver expects a clean transition from
     an uncorrupted IDLE pattern to an uncorrupted "S". If
     either the SOP or its preceding IDLE are corrupted, the
     receiver reports the packet as bad.
     We need not contemplate any patterns involving odd
     numbers of errors, because they will always result in a
     detectable DC code violation. Therefore, we need not
     consider patterns of 3 errors. That leaves us with
     patterns involving 1 or 2 errors.
     For packets preceded by IDLE, if the Hamming distance
     between the IDLE and the "S" pattern is at least three,
     then no pattern of two or fewer errors can produce an
     undetectable change to the position of the "S". The
     Hamming distance between the IDLE and "S" patterns in
     this proposal (K28.5 and K23.7) is five.
     For packets preceded by "RRRR", we need to analyze the
     Hamming distance between the "RRRR" sequence and the
     packet header, which starts with "S". This distance is
     also three.  That is, the sequence RRRSD may only be
     transformed into RRSDD by a pattern of three or more
     errors. Also, RRRSD may only be transformed into RRRRS
     by a pattern of three or more errors.
     The only cases left to analyze are those in which one,
     two or three errors affect some combination of the EOP
     code and the data field. In other words, we may now
     assume that the SOP is correctly placed, and framing is
Let us next treat error patterns affecting the EOP code

     The three-word sequence [T,R,R] or {T,R,I] must be
     received intact to qualify as a valid EOP sequence. We
     will enumerate below the various possible errors that
     could occur, and show why at least 3 errors are
     required in most cases. In the remaining cases, we will
     compute the probability of error.

CASE 1: (advance by one)
|DDDDTRRR - DDDTRRRR| = |D-T| + |T-R| + |R-R|
     Consider if D has weight 5
     |D-T| = 2
     |R-T| = 2
     The difference totals at least 4, so we are done.
     Consider if D has weight 6 (similar proof for weight 4)
     Then |D-T| = 1.
     Now we have replaced a weight 6 word with a weight 5
     We must transform the T into an R of the opposite
     |(+T+) - (-R-)| = 8, and also
     |(-T-) - (+R+)| = 8, so we are done.

CASE 2: (advance by two)
     |DDDDTRRR - DDTRRRRR| = |D-T| + |D-R| + |T-R|
     |D-R| = 1
     |D-T| = 1
     |T-R| = 2
     The difference totals at least 4, so we are done.

CASE 3: (advance by three or more)
     |DDDDD - DDTRR| = |D-T| + |D-R| + |D-R|
     We need to change three octets. If the weight of any of
     the three D patterns is 5 (balanced weight), then it
     will take two errors to change that D into either T or
     R (because both T and R also have weight 5). With at
     least one error in each of the other two D positions,
     we have a total of four errors.
     Therefore, we now need only consider cases where all
     three D words have non-balanced weight (6 or 4).
     There are two patterns of consequence:
     (+D-)(-D+)(+D-) => (+T+)(+R+)(+R+)
     (-D+)(+D-)(-D+) => (-T-)(-R-)(-R-)
     In either case, we must turn one of the D's into an R
     of opposite disparity.  It turns out that for any non-
     balanced D word to change into a R of opposite
     disparity, it takes 3 errors. [NOTE--I checked this
     property by exhaustive enumeration. Also note that T
     does not have this property. There **are** non-balanced
     D patterns that are distance one from a T of opposite
     Each of the other two changes may be accomplished with
     only one error. We therefore need 5 errors to complete
     this pattern.

     To delay the TRR pattern by N positions involves
     changing TRR patterns into DDD patterns in a way
     completely analogous to the DDD to TRR changes we have
     just analyzed. No new cases appear.

No pattern of three or fewer errors can cause an undetected
packet error.

- - - - -- - - -
I would like to thank the many individuals who have already
forwarded their helpful suggestions and insightful comments
regarding this proposal (especially Rich Taborek and
Jonathan Thatcher).

- - - - - - - - -
I would greatly appreciate any comments you may have about
this draft proof. Let's not just assume that one person can
run through a proof of this complexity the first time
without error.

---------- * END OF PROPOSAL * ----------------
Howard W. Johnson,  Olympic Technology Group, Inc. 
U.S. tel (206) 556 0800 // fax 206 881 6149 // email howiej@xxxxxxxxxxxx