git.sesse.net Git - hamming/blob - hamming.txt

   1 (15,11) Hamming code:
   2
   3
   4  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
   5 p1 p2 D1 p1 D2 D3 D4 p4 D5 D6 D7 D8 D9 DA DB
   6 --    xx    xx    xx    xx    xx    xx    xx
   7    -- xx       xx xx       xx xx       xx xx
   8          -- xx xx xx             xx xx xx xx
   9                      -- xx xx xx xx xx xx xx
  10
  11 p1 = D1 ^ D2 ^ D4 ^ D5 ^ D7 ^ D9 ^ D11
  12 p2 = D1 ^ D3 ^ D4 ^ D6 ^ D7 ^ D10 ^ D11
  13 p3 = D2 ^ D3 ^ D4 ^ D8 ^ D9 ^ D10 ^ D11
  14 p4 = D5 ^ D6 ^ D7 ^ D8 ^ D9 ^ D10 ^ D11
  15
  16    D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB
  17 p1 xx xx    xx xx    xx    xx    xx
  18 p2 xx    xx xx    xx xx       xx xx
  19 p3    xx xx xx          xx xx xx xx
  20 p4             xx xx xx xx xx xx xx
  21
  22 Add an extra parity bit p5 for detecting double-bit errors; this is simply
  23 the XOR of all the bits, _including_ the other parity bits (see Wikipedia).
  24
  25 Strategy: lookup tables. Table of 2048 values -> 5 parity bits should be very
  26           cheap (consume 2kB of RAM for unsigned char, fits nicely into L1
  27           cache and all). Do we want to encode extra information here? Probably
  28           not worth it at all...
  29
  30 Expansion to (31,26):
  31
  32  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
  33 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
  34 --    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx    xx
  35    -- xx       xx xx       xx xx       xx xx       xx xx       xx xx       xx xx       xx xx
  36          -- xx xx xx             xx xx xx xx             xx xx xx xx             xx xx xx xx
  37                      -- xx xx xx xx xx xx xx                         xx xx xx xx xx xx xx xx
  38                                              -- xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
  39
  40 Reordering:
  41
  42    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
  43 p1 xx xx     xx xx    xx    xx     xx xx    xx    xx    xx     xx    xx    xx    xx
  44 p2 xx     xx xx    xx xx       xx  xx    xx xx       xx xx        xx xx       xx xx
  45 p3    xx  xx xx          xx xx xx  xx          xx xx xx xx              xx xx xx xx
  46 p4              xx xx xx xx xx xx  xx                       xx xx xx xx xx xx xx xx
  47 p5                                    xx xx xx xx xx xx xx  xx xx xx xx xx xx xx xx
  48
  49 Last bit is the parity of all the data bits _and_ the parity bits, which means it gets
  50 counted as follows (?):
  51
  52 p6 xx xx  xx    xx xx    xx        xx xx xx    xx       xx  xx       xx    xx xx
  53
  54 Converted to bitmasks:
  55
  56 p1: 03 6a d5 55
  57 p2: 02 d9 b3 33
  58 p3: 01 c7 8f 0f
  59 p4: 00 3f 80 ff
  60 p5: 00 00 7f ff
  61 p6: 03 b4 e9 96
  62
  63
  64 Finally, expansion to truncated (127,120) -> (71,64):
  65
  66    ab-c---d-------e---------------f-------------------------------g-------
  67 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
  68 p2  -x xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx  xx  xx
  69 p3    -xxx    xxxx    xxxx    xxxx    xxxx    xxxx    xxxx    xxxx    xxxx
  70 p4        -xxxxxxx        xxxxxxxx        xxxxxxxx        xxxxxxxx
  71 p5                -xxxxxxxxxxxxxxx                xxxxxxxxxxxxxxxx
  72 p6                                -xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  73 p7                                                                -xxxxxxx
  74
  75 Reordering:
  76
  77    ----------------------------------------------------------------
  78 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
  79 p2 xxx x xx xxxx xx xx xx xx x xx xx xx xx xx xx xx xx xx xx xx  xx
  80 p3  xxx   xxxx   xxxx    xxxx   xxxx    xxxx    xxxx    xxxx   xxxx
  81 p4     xxxxxxx       xxxxxxxx       xxxxxxxx        xxxxxxxx
  82 p5            xxxxxxxxxxxxxxx               xxxxxxxxxxxxxxxx
  83 p6                           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
  84 p7                                                          xxxxxxx
  85
  86 Bit masks, with extra computed parity bit:
  87
  88 p1: 0xDAB5556AAAAAAAD5
  89 p2: 0xEB7B6DADB6DB6DB3
  90 p3: 0x71E3C3C78787878F
  91 p4: 0x0FE03FC07F807F80
  92 p5: 0x001FFFC0007FFF80
  93 p6: 0x0000003FFFFFFF80
  94 p7: 0x000000000000007F
  95 p8: 0xB02DC4C0E409C0E9
  96