Keywords: ATM, HEC, CRC-8, Error Correcting Codes
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 |<-+-
| +---+ ^ +---+ ^ +---+ ^ +---+ ^ +---+ ^ +---+ +---+ ^
| | | | | | |
+--------+--------+--------+--------+--------+----------------+
As is demonstrated in many textbooks (e.g., Berlekamp, Algebraic Coding
Theory) a feedback shift register like the one above implements a
polynomial long division if one supplies the coefficients of the dividend
at the input to the modulo-2 adder at the first stage. Suppose we send
messages with at most 120 information bits and appended a 7-bit CRC using
this shift register -- so that the code words we transmit all represent
polynomials which are divisible by:x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
When the message is checked on receipt it is run through the division circuit. The remainder -- or syndrome, as it is sometimes called -- is zero if there are no errors. Because the shift register is linear, what remains in the shift register when there are errors is the remainder that would be present if only the error polynomial (with coefficients in error positions) were applied at the input. Suppose that we transmit exactly N bits including the CRC (where N does not exceed 127) and that there is exactly one error in the message which is received. Number the bits so that bit 0 is the last bit transmitted and bit N-1 is the first bit transmitted. Suppose that the error occurs at bit position M (where M < N). Then the syndrome which remains in the register at the end will be just what would be in the register after M shifts starting with '1' in the x^0 position and '0' elsewhere. Since M < N < 127, the syndrome is unique for every value of N, and therefore can be used to locate the error. In other words, this code is a single error correcting Hamming code. The columns of the check matrix are just the successive states of the feedback shift register starting with '1' in the x^0 position.
One of the weaknesses of a Hamming code is that if two errors occur then the correction algorithm suggested above -- inverting the message bit position corresponding to the syndrome -- will actually introduce a third error. One way to guard against that is to toss out all odd-parity code words. This can be done by including a factor of x + 1 in the generating polynomial, since all polynomials divisible by x + 1 have even parity. Note that this increases the number of check bits from 7 to 8 so we must at the same time reduce the maximum number of information bits to 119 in order to keep the code word size equal to 127. We would use the shift register below to calculate the 8-bit CRC.
+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+
+-|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:x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
then the register remains in that state forever. Suppose once again that we transmit exactly N bits including the CRC (where N does not exceed 127) and as before number the bits so that bit 0 is the last bit transmitted and bit N-1 is the first bit transmitted. If a single error occurs at bit position M < N then the syndrome which remains in the register at the end will be the odd parity pattern which would result from cycling the register M times starting from the state represented by the polynomial 1. Since M < N < 127, the syndrome once again is unique for every value of N and can be used to locate the error. If a double error occurs then the syndrome will have even parity. In this case the error cannot be corrected unless we can assume something about the distribution of errors -- e.g., that they are adjacent(*). But one can distinguish distinguish this case from a single error and discard the message.
In the C program attached below I have mechanized this stuff by means of table lookup algorithms. In order to perform the CRC-8 calculations a byte at a time (using an adaptation of the algorithm described by Avram Perez, Byte-wise CRC Calculations, IEEE Micro 3, 40 (1983)) I use a table of syndromes for all possible 8-bit error patterns ("syndrome_table"). In order to correct the errors I use a table of error positions corresponding to each possible syndrome -- with an 'uncorrectible' indication put there for each syndrome which does not correspond to a possible single bit error position. The latter case can occur not only because the syndrome has the wrong parity but also if it happens to point to a bit position which does not exist. The main program runs through selected cases with no errors, single errors, and double errors to demonstrate the machinery in action. CAUTION: for programming convenience I have chosen to number header bit positions from 0 to 39, with bit 0 being the header bit which was transmitted first. This is different from the numbering convention used above.
(*) N. M. Abramson, A Class of Systematic Codes for Non-Independent Errors, IRE Trans. Info. Theory, December 1959.
/********************************************************************/
#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;
}