Error Correction and Detection

Frank Klemm's Error Correction Code Page

Introduction and Tables

The following tables contain the result of an brute force search of the best Error Correction Codes in 1992. The calculations were done on a large number of AIX workstations with 128 Mbyte RAM. Special thanks to the administrators of the Computer Center of the Friedrich Schiller University for not disabling my UNIX account.

Hamming distance	Codes
1	up to [ 17, 17; 1,2]
3	up to [16399,16384; 3,2]
5	up to [17904,17869; 5,2]
7	up to [ 629, 594; 7,2]
9	up to [ 145, 112; 9,2]
11	up to [ 76, 44;11,2]
13	up to [ 56, 23;13,2]
15	up to [ 59, 23;15,2]
17	up to [ 50, 13;17,2]
19	up to [ 48, 10;19,2]
21	up to [ 47, 8;21,2]
23	up to [ 41, 3;23,2]
25	up to [ 49, 4;25,2]
27	up to [ 48, 3;27,2]
29	up to [ 52, 3;29,2]
31	up to [ 55, 3;31,2]
33	up to [ 70, 7;33,2]
65	up to [ 135, 8;65,2]
129	up to [ 264, 9;129,2]

Even codes, derived by adding a parity bit:

Hamming distance	Codes
2	up to [ 18, 17; 2,2]
4	up to [16400,16384; 4,2]
6	up to [17905,17869; 6,2]
8	up to [ 630, 594; 8,2]
10	up to [ 146, 112;10,2]
12	up to [ 77, 44;12,2]
14	up to [ 57, 23;14,2]
16	up to [ 60, 23;16,2]
18	up to [ 51, 13;18,2]
20	up to [ 49, 10;20,2]
22	up to [ 48, 8;22,2]
24	up to [ 42, 3;24,2]
26	up to [ 50, 4;26,2]
28	up to [ 49, 3;28,2]
30	up to [ 53, 3;30,2]
32	up to [ 56, 3;32,2]
34	up to [ 71, 7;34,2]

Codes are written as [ c+d , d ; h , b ] - where

c is the number of control bits
d is the number of data bits
c+d is the number of all bits, i.e. data and control bits
h is the minimum hamming distance of the code
b is the base, for the usual used binary codes b=2

A [ 7, 4; 3, 2] code uses 7 total bits for transmitting 4 data bits with a hamming distance of at least 3.

Construction of other hamming distance:

H = 1
A hamming code of 1 don't need any control bits. All bits are data bits.
H = 3
A hamming code of 3 can be easily calculated. List all numbers with more than 1 binary digit unequal to zero (3, 5...7, 9...15, 17...31, ...)
H = 2n+2
Take the code for H=2n+1 and add a simple parity bit by counting the number of set bits in the control data.
If count is even, add a 1, if odd add a 0.
Compare [145,112; 9,2] and [146,112;10,2] code.

Encoding

Select a number of bits (d) you want to encode in one block and select a hamming distance (H). Hamming distance is selected from the correction capabilities you need. Start with a hamming distance of '1', and add:

a '1' for every error per block you want to detect
a '2' for every error per block you want to correct
an additional '1' if you want it nearly impossible to make 'falsely corrected errors'.

Last point is important if wrong corrected errors are much much worse than known uncorrected errors and if only one ECC correction layer with a low hamming distance is used. Now take from the table specified by your prefered hamming distance (H) the first d lines. These are containing:


000:  00000003F  .............................######   6
001:  0000001C7  ..........................###...###   9
002:  0000002D9  .........................#.##.##..#  10
003:  00000036A  .........................##.##.#.#.  10
004:  0000003B4  .........................###.##.#..  10
005:  0000004EB  ........................#..###.#.##  11
^     ^          ^                                    ^
data  ECC word   ECC word                             number of
bit#  in hex     in binary representation             needed bits

Encoding is done by XORing all ECC words where the corresponding data bit is set. Pseudo code looks like this:


/******************* code example 1 *****************/

const unsigned int  ECCwords [MAXLEN] = {
    0x0000003F, 0x000001C7, 0x000002D9, 0x0000036A, 0x000003B4, 0x000004EB,
    ...
};

unsigned int
ECC ( const unsigned char* data, size_t len )
{
    unsigned int  ecc = 0;
    size_t        i;

    for ( i = 0; i < len; i++ )
        if ( data [i>>3] & (0x80 >> (i&7)) )
            ecc ^= ECCword [i];

    return ecc;
}

For high speed implementation it is also possible to make a set of lookup tables:


/******************* code example 2 *****************/

const unsigned int  ECCwords [MAXLEN] = {
    0x0000003F, 0x000001C7, 0x000002D9, 0x0000036A, 0x000003B4, 0x000004EB,
    ...
};

unsigned int  ECCtable [8][256];

void
MakeLookupTables ( void )
{
    int i, j, k;

    memset ( ECCtable, 0, sizeof ECCtable );

    for ( i = 0; i < 8; i++ )
        for ( j = 0; j < 256; j++ )
            for ( k = 0; k < 8; k++ )
                if (j & (0x80 >> k))
                    ECCtable [i] [j] ^= ECCwords [8*i + k];
}

unsigned int
ECC64 ( const unsigned char* data )
{
    return ECCtable [0] [data[0]] ^
           ECCtable [1] [data[1]] ^
           ECCtable [2] [data[2]] ^
           ECCtable [3] [data[3]] ^
           ECCtable [4] [data[4]] ^
           ECCtable [5] [data[5]] ^
           ECCtable [6] [data[6]] ^
           ECCtable [7] [data[7]];
}

You have to transmit the d data bits and the c computed ECC bits. c is also taken from the table. It is the number of needed bits in the last line you have taken from the ECC tables.

Note that is nearly always useful to shuffle and invert bits by a defined method to reduce the chance of more error prone regular pattern and to reduce the chance of bit error burst which can't be corrected by ECC codes. But this is a fully different topic.

Last but not least a list of high efficient codes:

Data bits	ECC bits	Hamming distance
2ⁿ - n - 1	n + 1	4
9	9	6
12	10	6
19	11	6
27	12	6
40	13	6
56	14	6
79	15	6
105	16	6
140	17	6
186	18	6
248	19	6
323	20	6
423	21	6
552	22	6
717	23	6
927	24	6
6835	32	6
14167	35	6
12	12	8
38	18	8
94	24	8
350	32	8
90	32	10
7	20	12
20	25	12
6	26	16
n	2^n-1	2^n-2 + 2

Decoding

Decoding starts with a de-shuffling and de-inverting as pre-processing if you have used shuffling and inverting as post-processing in the encoding process.

The next stage is to calculate the ECC in the same way as in the encoding stage. You got back a number (error seed) which contains all information about detected errors.

If the transmission was error free, this error seed is 0 and you don't have to correct anything.

If 1 error occured, you got back a number in the ECCwords list or a power of 2. If you got back a number in the ECCwords list, the position in this table is the inverted bit. If you got back a power of 2 (a number with 1 bit set), a 1-bit-error occured in the ECC word and all data bits are likely correct.

For codes with larger hamming distances as 5, this can also be done for 2 bits, for a hamming distance of H this can be done exactly (H-1)/2 times. The codes in the tables are selected in a way that all codes are distant enough so every code can be related to a given set of (H-1)/2 of errors.

The geometric interpretation of these codes are 2^d spheres within a c+d dimensional space with the basic (0,1), where all spheres have at least a distance of H from each other. This is very easy to understand because of the finite dimensions of these spaces.

A simple decoding routines looks like that:


/******************* code example 3 *****************/

const unsigned int  ECCwords [MAXLEN] = {
    0x0000003F, 0x000001C7, 0x000002D9, 0x0000036A, 0x000003B4, 0x000004EB,
    ...
};

/*
 *  corrects data and return number of corrected bits,
 *  or -1 if correction is not possible
 */

int
ECC_correct ( unsigned char* data, size_t len, unsigned int ecc )
{
    unsigned int  tmp;
    size_t        i;
    size_t        j;

    /* calculate ECC */
    for ( i = 0; i < len; i++ )
        if ( data [i>>3] & (0x80 >> (i&7)) )
            ecc ^= ECCword [i];

    if (ecc == 0)
        return 0;

    for ( i = 0; i < len; i++ )
        if ( ecc == ECCword [i] ) {
            data [i>>3] ^= 0x80 >> (i&7);
            return 1;
        }
    for ( i = 0; i < ECCbits; i++ )
        if ( ecc == (1 << i) ) {
            return 1;
        }

    for ( j = 0; j < len; j++ ) {
        tmp = ECCword [j];
        for ( i = j+1; i < len; i++ )
            if ( ecc ^ tmp == ECCword [i] ) {
                data [j>>3] ^= 0x80 >> (j&7);
                data [i>>3] ^= 0x80 >> (i&7);
                return 2;
            }
        for ( i = 0; i < ECCbits; i++ )
            if ( ecc ^ tmp == (1 << i) ) {
                data [j>>3] ^= 0x80 >> (j&7);
                return 2;
            }
    }
    for ( j = 0; j < ECCbits; j++ ) {
        tmp = 1 << j;
        for ( i = 0; i < len; i++ )
            if ( ecc ^ tmp == ECCword [i] ) {
                data [i>>3] ^= 0x80 >> (i&7);
                return 2;
            }
        for ( i = j+1; i < ECCbits; i++ )
            if ( ecc ^ tmp == (1 << i) ) {
                return 2;
            }
    }

    return -1;
}

This method has several disadvantages:

Code inflation for higher correction levels
It is slow, especially if multi bit errors occure

First can be avoided by enlarging ECCwords by ECCbits entries which are containing the powers of 2 from 0 . . . ECCbits-1. It is possible to append these entries (easier to read) or to prepend (table can be used for different amounts of data bits).


/******************* code example 4 *****************/

const unsigned int  ECCwords [MAXLEN + ECCBITS] = {
    0x0000003F, 0x000001C7, 0x000002D9, 0x0000036A, 0x000003B4, 0x000004EB,
    ...
    0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
    ...
};

/*
 *  corrects data and return number of corrected bits,
 *  or -1 if correction is not possible
 */

int
ECC_correct ( unsigned char* data, unsigned int ecc )
{
    size_t        i;
    size_t        j;

    /* calculate ECC */
    for ( i = 0; i < MAXLEN; i++ )
        if ( data [i>>3] & (0x80 >> (i&7)) )
            ecc ^= ECCword [i];

    if (ecc == 0)
        return 0;

    for ( i = 0; i < MAXLEN+ECCBITS; i++ )
        if ( ecc == ECCword [i] ) {
            if (i < MAXLEN) data [i>>3] ^= 0x80 >> (i&7);
            return 1;
        }

    for ( j = 0; j < MAXLEN+ECCBITS-1; i++ )
        for ( i = j+1; i < MAXLEN+ECCBITS; i++ )
            if ( ecc ^ ECCword [j] == ECCword [i] ) {
                if (i < MAXLEN) data [i>>3] ^= 0x80 >> (i&7);
                if (j < MAXLEN) data [j>>3] ^= 0x80 >> (j&7);
                return 2;
            }

    return -1;
}

Advanced method are using:

Direct calculation of defect bits for H = 3 . . . 4
bsearch algorithms of the inner search loop (useful for larger d)
Multiplying the table with itself, instead of search using 4 for-loops within a table of n=122 entries you are now need only 2 for-loops using n(n-1)/2=7381 entries (useful for H > 6).
Lookup tables, if c is not too large.
Calculating hamming distance to all possible encoded data word and selecting the smallest (useful for large H).


/******************* code example 9 *****************/

const unsigned int  ECCwords [MAXLEN] = {
    0x0000003F, 0x000001C7, 0x000002D9, 0x0000036A, 0x000003B4, 0x000004EB,
    ...
};

unsigned int  ECCtable [1 << MAXLEN];

void
MakeLookupTables ( void )
{
    int i, j;

    memset ( ECCtable, 0, sizeof ECCtable );

    for ( i = 0; i < (1L << MAXLEN); i++ )
        for ( j = 0; j < MAXLEN; j++ )
            if ( i & (1L << j) )
                ECCtable [i] ^= ECCwords [j];
}


int
Hamming ( unsigned int x )
{
    x = ((x >> 1) & 0x55555555) + ((x >> 0) & 0x55555555);
    x = ((x >> 2) & 0x33333333) + ((x >> 0) & 0x33333333);
    x = ((x >> 4) & 0x07070707) + ((x >> 0) & 0x07070707);
    x = ((x >> 8) & 0x000F000F) + ((x >> 0) & 0x000F000F);
    x = ((x >>16) & 0x0000001F) + ((x >> 0) & 0x0000001F);
    return (int) x;
}


/*
 *  corrects data and return number of corrected bits
 */

int
ECC_correct ( unsigned int* data, unsigned int ecc )
{
    int           hamming
    size_t        i;
    size_t        j;
    unsigned int  code;
    int           H;
    int           tmp;

    if ( (ecc == ECCtable [*data]) )
        return 0;

    H    = Hamming (*data) + Hamming (ECCtable[0] ^ ecc);
    code = 0;

    for ( i = 1; i < (1L << MAXLEN); i++ ) {
        tmp = Hamming (i ^ *data) + Hamming (ECCtable[i] ^ ecc);
        if ( tmp < H ) {
            H    = tmp;
            code = i;
        }
        else if ( tmp == H )
            code = -1;
        }
    }
    if ( code == -1 )
        return -1;
    *data = code;
    return H;
}

Glossar and practical examples

Complete codes
Hamming limit
Explanation of tables
Interleaving
Modulation Codes
Transformation of BER
CD, ECC capabilities

Last modified: 2002-05-05 Visitors: