Re: CRC check indication of bad fiber
- 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