Add an implementation of the (72,64) Hamming codes.

[hamming] / hamming.txt

diff --git a/hamming.txt b/hamming.txt
index aa9e9471206fd584c816f340d451289ce75e1d13..511ab5a1614c2f21d1bd4351adf12888f5f8b845 100644 (file)
--- a/hamming.txt
+++ b/hamming.txt
@@ -26,3 +26,71 @@ 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: 0xED3A65B4CB4B34E9
+