Thread Links |
Date Links |
||||
---|---|---|---|---|---|

Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |

*To*: "Salzman,Mike" <msalzman@xxxxxxxxxx>*Subject*: Re: CRC check indication of bad fiber*From*: Rich Taborek <rtaborek@xxxxxxxxxxxxxxxx>*Date*: Fri, 21 May 1999 01:45:26 -0700*CC*: HSSG_reflector <stds-802-3-hssg@xxxxxxxx>*Organization*: Transcendata, Inc.*References*: <001401bea35e$f230f2a0$147b1287@xxxxxxxxxx> <37459DDC.3339@xxxxxxxxxxxxxxxx>*Reply-To*: rtaborek@xxxxxxxxxxxxxxxx*Sender*: owner-stds-802-3-hssg@xxxxxxxxxxxxxxxxxx

>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 >it. > >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. Mike, 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 used - 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, Rich ------------------------------------------------------------- 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 http://www.transcendata.com 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 UPDATED DRAFT PROOF OF ROBUSTNESS v.2 7/24/96 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. OBJECTIVES - - - - - - 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. CHANGES SINCE FIRST VERSION - - - - - - - - - - - - - - 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). HOW A PACKET IS CODED - - - - - - - - - - - 802.3 packet format (this table requires a fixed-width font, like Courier) 802.3 packet 8B10B codes ------ ----------- IDLE I1 I1 I1 I1 I1 K1 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... T 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 data. 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. [K29.7]. 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 packet. NOTE: If we use packet bursting, then sometimes a packet is preceeded by "R", not "I". That case is also considered. BASIC FACTS ABOUT ERROR DETECTION ------------------------------------------------- (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 themselves. (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. PROOF OF ERROR DETECTION CAPABILITY: 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 EOP. 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 word. 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 intact. Let us next treat error patterns affecting the EOP code word. 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 word. We must transform the T into an R of the opposite disparity. |(+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 disparity.] Each of the other two changes may be accomplished with only one error. We therefore need 5 errors to complete this pattern. OTHER CASES: 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. CONCLUSION: No pattern of three or fewer errors can cause an undetected packet error. A NOTE OF THANKS... - - - - -- - - - 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). A NOTE OF HUMILITY - - - - - - - - - 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

**References**:**RE: CRC check indication of bad fiber***From:*Michael M. Salzman

- Prev by Date:
**RE: more on : IEEE 802.3 Requirements** - Next by Date:
**Re: CRC check indication of bad fiber** - Prev by thread:
**RE: CRC check indication of bad fiber** - Next by thread:
**RE: CRC check indication of bad fiber** - Index(es):