HEC Tutorialby Charles Michael HeardCharles Michael Heard posted this tutorial on the cell-relay list on Mon Oct 10 10:04:15 PDT 1994 Keywords: ATM, HEC, CRC-8, Error Correcting Codes Next is Charles Michael Heard's 32 bit CRC Calculation Code in C In article <9409302337.AA06658@erl.LABS.TEK.COM>, maa@erl.labs.tek.com (Matthew Maa) writes: > In reading the BISDN spec for physical layer, it is clear > to me how to generate the HEC for the cell header. But > on the receiver side, when a new HEC is computed and compared > against the sender transmitted HEC, how does one know that > there is a single-bit or a multiple-bit error? Also, how > is the single erroneous bit position determined?First, a bit of the theory. The polynomial used to generate the HEC has two irreducible factors over the Galois field GF(2) -- x^8 + x^2 + x + 1 = (x + 1) * (x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1). The second factor is irreducible and of degree 7, so all of its roots reside in the Galois field GF(2^7). Moreover, it is a primitive polynomial, which means that consecutive powers of any of its roots generate all 127 of the non-zero elements of GF(2^7) -- a root being any x which satisfies the equation: x^7 = x^6 + x^5 + x^4 + x^3 + x^2 + 1. It is possible to represent elements of GF(2^7) as a sum of powers of x of degree six or less; if one does so then the linear feedback shift register depicted below mechanizes a multiplication by x. Since the powers of x are all distinct non-zero elements of GF(2^7), the practical implication is that if the shift register below is started in any non-zero state it will return to its original state 127 cycles later and not before.
+---+ +---+ +---+ +---+ +---+ +---+ +---+
+-|x^6|<-+-|x^5|<-+-|x^4|<-+-|x^3|<-+-|x^2|<-+-| x |<--| 1 |<-+-
| +---+ ^ +---+ ^ +---+ ^ +---+ ^ +---+ ^ +---+ +---+ ^
| | | | | | |
+--------+--------+--------+--------+--------+----------------+
|
|
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
+-|x^7|<--|x^6|<--|x^5|<--|x^4|<--|x^3|<--|x^2|<-+-| x |<-+-| 1 |<-+-
| +---+ +---+ +---+ +---+ +---+ +---+ ^ +---+ ^ +---+ ^
| | | |
+------------------------------------------------+--------+--------+
It turns out (as you can easily verify with a simple program) that there
are three distinct non-zero sequences of states generated by this register.
If the starting state is represented by the polynomial 1 (i.e., '1' in
the x^0 coefficient and '0' elsewhere) then the register cycles through
127 of the 128 possible odd-parity states. If the starting state is
represented by the polynomial x + 1 then the register cycles through all
127 non-zero even-parity states. If the starting state is represented by
the polynomial:
/********************************************************************/
#define HEC_GENERATOR 0x107 /* x^8 + x^2 + x + 1 */
#define COSET_LEADER 0x055 /* x^6 + x^4 + x^2 + 1 */
static unsigned char syndrome_table[256];
void gen_syndrome_table()
/* generate a table of CRC-8 syndromes for all possible input bytes */
{
register int i, j, syndrome;
for ( i = 0; i < 256; i++ )
{
syndrome = i;
for ( j = 0; j < 8; j++ )
{
if ( syndrome & 0x80 )
syndrome = ( syndrome << 1 ) ^ HEC_GENERATOR;
else
syndrome = ( syndrome << 1 );
}
syndrome_table[i] = (unsigned char) syndrome;
}
return;
}
void insert_hec(cell_header)
unsigned char cell_header[5];
/* calculate CRC-8 remainder over first four bytes of cell header */
/* exclusive-or with coset leader & insert into fifth header byte */
{
register unsigned char hec_accum = 0;
register int i;
for ( i = 0; i < 4; i++ )
hec_accum = syndrome_table [ hec_accum ^ cell_header[i] ];
cell_header [4] = hec_accum ^ COSET_LEADER;
return;
}
#define NO_ERROR_DETECTED -128
#define UNCORRECTIBLE_ERROR 128
static int err_posn_table[256];
void gen_err_posn_table()
/* Generate the error position table as a function of the syndrome. */
/* A negative value indicates that there is no error to correct. */
/* A value of 40 or greater indicates that an uncorrectible error */
/* has occurred, i.e., that the syndrome either indicates a double */
/* error pattern or points to a single-bit error position that is */
/* outside the header. Finally, a value between 0 and 39 indicates */
/* that a single-bit error occurred in that position (bit 0 being */
/* the header bit which was transmitted first). */
{
register unsigned char hec_accum;
register int i, j, k;
/* mark the NO_ERROR_DETECTED position */
err_posn_table[0] = NO_ERROR_DETECTED;
/* default remaining positions to UNCORRECTIBLE */
for ( i = 1; i < 256; i++ )
err_posn_table[i] = UNCORRECTIBLE_ERROR;
/* override w/err posn for syndromes indicating other single-bit errors */
for ( i = 0; i < 5; i++ )
{
for ( j = 0; j < 8; j++ )
{
if ( i < 4)
{
hec_accum = 0;
for ( k = 0; k < 4; k++ )
if ( k == i)
hec_accum = syndrome_table [ hec_accum ^ (0x80 >> j) ];
else
hec_accum = syndrome_table [ hec_accum ];
}
else
{
hec_accum = (0x80 >> j);
}
err_posn_table [ hec_accum ] = (i * 8) + j;
}
}
return;
}
int correct_header_err(cell_header)
unsigned char cell_header[5];
/* return HEC value calculated over first four bytes of cell header */
{
register unsigned char syndrome;
register int i, err_posn;
syndrome = 0;
for ( i = 0; i < 4; i++ )
syndrome = syndrome_table [ syndrome ^ cell_header[i] ];
syndrome ^= cell_header[4] ^ COSET_LEADER;
err_posn = err_posn_table [ syndrome ];
if ( err_posn < 0)
{
return NO_ERROR_DETECTED;
}
else
if ( err_posn < 40)
{
cell_header [ err_posn / 8 ] ^= (0x80 >> (err_posn % 8));
return err_posn;
}
else
{
return UNCORRECTIBLE_ERROR;
}
}
static unsigned char prototype_hdr[5] = { 0x0f, 0xff, 0xff, 0x02, 0x75};
void main ()
{
int i, j, k;
unsigned char cell_header[5];
gen_syndrome_table();
gen_err_posn_table();
for ( i = 0; i < 5; i++)
cell_header[i] = prototype_hdr[i];
insert_hec (cell_header);
printf("cell header w/inserted hec = %02x, %02x, %02x, %02x, %02x \n",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
j = correct_header_err(cell_header);
printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
printf("err posn = %d \n", j);
for (k = 0; k < 40 ; k++ )
{
for ( i = 0; i < 5; i++ )
{
if ( i == k / 8 )
cell_header[i] = prototype_hdr[i] ^ ( 0x80 >> ( k % 8) );
else
cell_header[i] = prototype_hdr[i];
}
printf("cell header w/inserted err = %02x, %02x, %02x, %02x, %02x \n",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
if ( (j = correct_header_err(cell_header)) != UNCORRECTIBLE_ERROR )
{
printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
printf("err posn = %d \n", j);
}
else
{
printf("err posn = %d => UNCORRECTIBLE ERROR \n", j);
}
}
for (k = 0; k < 40 ; k++ )
{
for ( i = 0; i < 5; i++ )
{
if ( i == k / 8 )
cell_header[i] =
prototype_hdr[i] ^ (( 0x181 >> ( k % 8) ) & 0xff);
else
cell_header[i] = prototype_hdr[i];
}
printf("cell header w/inserted err = %02x, %02x, %02x, %02x, %02x \n",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
if ( (j = correct_header_err(cell_header)) != UNCORRECTIBLE_ERROR )
{
printf("corrected cell header = %02x, %02x, %02x, %02x, %02x ",
cell_header[0], cell_header[1], cell_header[2], cell_header[3],
cell_header[4]);
printf("err posn = %d \n", j);
}
else
{
printf("err posn = %d => UNCORRECTIBLE ERROR \n", j);
}
}
return;
}