Cell Relay Archive

["C. M. Heard/VVNET, Inc." <heard@vvnet.com>]

Rajagopalan Kothandaraman wrote:
>
> As u know, the ATM Cell header is protected by CRC with polynomial
> G(X) = X^8 + X^2 + X + 1. In ITU-T I.432, it is given that this code is
> capable of doing either single bit error correction or multi-bit error
> detection. I have a doubt reg single bit error correction.
>
> If R(X) is the received header with error E(X), then R(X) = T(X) + E(X).
> If we divide R by G, we would be getting a syndrome which coresponds to
> E/G.

More precisely, it is E mod G.

>      From this syndrome only, we can detect/correct single bit error. Suppose
> if single bit error occurred at MSB of cell header, then E(X) = X^39
> and hence E/G = X^39/(X^8 + X^2 + X + 1) = X^5 + X^4 + 1 which is 0x31.
> Conversely, if we get a syndrome value of 0x31, we may conclude that
> single bit error has occurred at MSB (x^39) position.

Correct.

> But, if E(X) = X^5 + X^4 + 1 (burst error of pattern 110001 in 5th byte),
> then also E/G = X^5 + X^4 + 1 which is 0x31 in value. We may wrongly
> conclude as per above paragraph that single bit error has occurred at
> MSB position. Considering the ambiquity discussed, how can one say that
> G(X) polynomial corrects single bit error properly? The problem lies in
> accurately classifying whether the error is single bit or multi-bit,
> leave alone single bit error correction.
>
> The probability is higher that i could be missing some important point.
> I would appreciate if anyone resolves the above issue for me.

Actually you have raised a very intelligent question.  As you have correctly
concluded, the particular error pattern in your example results in an
uncorrectible error.  No matter what you use -- whether it is used for
error correction or just for error detection -- there will always exist
such patterns.  The practical engineering question is whether the
probability of an undetected error is acceptably small.

The CRC-8 used for the ATM HEC is a Hamming code with all of the odd-weight
code words removed.  That can be seen by noting that the generator polynomial
has two irreducible factors:  a primitive degree 7 factor, which generates a
Hamming code, and a factor (x + 1), which forces all code words to have even
parity.  The minimum distance of this code is 4, which means that there exist
patterns of four errors which will turn one code word into another.  Such
error patterns cannot be detected even if error correction is turned off.
It also means that certain three-bit error patterns will turn a code word
into something which is distance 1 from another code word.  When single-bit
error correction is turned on, such patterns result in undetected errors, as
your example shows.  On the other hand, an error pattern with two bits will
always be detected, since the resulting pattern is always distance 2 from
any other code word.

The various ATM forum PHY specs differ in whether they permit header error
correction to be used.  PHYs that operate over fiber usually do, because
the error rates are very low and tend not to come in bursts.  PHYs that
use encoding that multiply errors -- e.g., 4B/5B or 8B/10B -- do not allow
header error correction to be used, because the probability of accepting a
bad cell is deemed to be too high.

Actually evaluating the probablity of undetected error can be quite hard.
In the case of a medium which has random (i.e., independent) bit errors
it is possible to do this if you know the weight distribution of the code,
by which I mean the number of error patterns of a given weight which
result in undetected errors (weight = number of errors in the pattern).
Since the cell header has only 40 bits (not the 127 which is the natural
length of the code) this has to be done numerically.  A technique for
doing this in the case where error correction is turned off is provided
in the following paper:

  T. Fujiwara, T. Kasami, A. Kitai, and S. Lin, "On the Undetected Error
  Probability for Shortened Hamming Codes", IEEE Trans. Commun. IT-33,
  570 (1985).

A somewhat less heavyeight place to start would be my ATM HEC tutorial,
which is available at ftp://ftp.vvnet.com/atm_hec/atm_hec.html or at
the cell-relay web site http://cell.onecall.net/.

> Thanx in advance,
> Raj

Hope this helps,

Mike
--
C. M. Heard/VVNET, Inc.
heard@vvnet.com