(15,11) Hamming code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 p1 p2 D1 p1 D2 D3 D4 p4 D5 D6 D7 D8 D9 DA DB -- xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx p1 = D1 ^ D2 ^ D4 ^ D5 ^ D7 ^ D9 ^ D11 p2 = D1 ^ D3 ^ D4 ^ D6 ^ D7 ^ D10 ^ D11 p3 = D2 ^ D3 ^ D4 ^ D8 ^ D9 ^ D10 ^ D11 p4 = D5 ^ D6 ^ D7 ^ D8 ^ D9 ^ D10 ^ D11 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB p1 xx xx xx xx xx xx xx p2 xx xx xx xx xx xx xx p3 xx xx xx xx xx xx xx p4 xx xx xx xx xx xx xx Add an extra parity bit p5 for detecting double-bit errors; this is simply the XOR of all the bits, _including_ the other parity bits (see Wikipedia). Strategy: lookup tables. Table of 2048 values -> 5 parity bits should be very cheap (consume 2kB of RAM for unsigned char, fits nicely into L1 cache and all). Do we want to encode extra information here? Probably not worth it at all... Expansion to (31,26): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 p1 p2 D1 p1 D2 D3 D4 p4 D5 D6 D7 D8 D9 DA DB p5 DC DD DE DF DG DH DI DJ DK DL DM DN DO DP DQ -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Reordering: D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF DG DH DI DJ DK DL DM DN DO DP DQ p1 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p2 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p3 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p4 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p5 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Last bit is the parity of all the data bits _and_ the parity bits, which means it gets counted as follows (?): p6 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Converted to bitmasks: p1: 03 6a d5 55 p2: 02 d9 b3 33 p3: 01 c7 8f 0f p4: 00 3f 80 ff p5: 00 00 7f ff p6: 03 b4 e9 96 Finally, expansion to truncated (127,120) -> (71,64): ab-c---d-------e---------------f-------------------------------g------- p1 - x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x p2 -x xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p3 -xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx p4 -xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx p5 -xxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx p6 -xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx p7 -xxxxxxx Reordering: ---------------------------------------------------------------- p1 xx xx x x xx x x x x x x xx x x x x x x x x x x x x x x xx x x x p2 x xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx p3 xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx p4 xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx p5 xxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx p6 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx p7 xxxxxxx Bit masks, with extra computed parity bit: p1: 0xDAB5556AAAAAAAD5 p2: 0xB66CCCD9999999B3 p3: 0x71E3C3C78787878F p4: 0x0FE03FC07F807F80 p5: 0x001FFFC0007FFF80 p6: 0x0000003FFFFFFF80 p7: 0x000000000000007F p8: 0xB02DC4C0E409C0E9