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] |
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
Construction of other hamming distance:
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 bitsEncoding 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.
Data bits | ECC bits | Hamming distance |
2^{n} - 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 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 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:
/******************* 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; }
Complete codes
Hamming limit
Explanation of tables
Interleaving
Modulation Codes
Transformation of BER
CD, ECC capabilities