m371: algebraic codes

1962 days ago by jonesbe

F = GF(2) MS = MatrixSpace(F, 2, 4) G = MS([[1,1,0,0],[0,0,1,1]]) C = LinearCode(G) 
       
       
Linear code of length 4, dimension 2 over Finite Field of size 2
Linear code of length 4, dimension 2 over Finite Field of size 2
C.minimum_distance() 
       
2
2
C.list() 
       
[(0, 0, 0, 0), (1, 1, 0, 0), (0, 0, 1, 1), (1, 1, 1, 1)]
[(0, 0, 0, 0), (1, 1, 0, 0), (0, 0, 1, 1), (1, 1, 1, 1)]
D = C.dual_code() D 
       
Linear code of length 4, dimension 2 over Finite Field of size 2
Linear code of length 4, dimension 2 over Finite Field of size 2
D.list() 
       
[(0, 0, 0, 0), (1, 1, 0, 0), (0, 0, 1, 1), (1, 1, 1, 1)]
[(0, 0, 0, 0), (1, 1, 0, 0), (0, 0, 1, 1), (1, 1, 1, 1)]
C.is_self_dual() 
       
True
True

Dilbert

Hamming Codes

C = HammingCode(3, GF(2)) C 
       
Linear code of length 7, dimension 4 over Finite Field of size 2
Linear code of length 7, dimension 4 over Finite Field of size 2
C.minimum_distance() 
       
3
3
C.list() 
       
[(0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 1, 1), (0, 1, 0, 0, 1, 0, 1),
(1, 1, 0, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1, 0), (1, 0, 1, 0, 1, 0, 1), (0,
1, 1, 0, 0, 1, 1), (1, 1, 1, 0, 0, 0, 0), (0, 0, 0, 1, 1, 1, 1), (1, 0,
0, 1, 1, 0, 0), (0, 1, 0, 1, 0, 1, 0), (1, 1, 0, 1, 0, 0, 1), (0, 0, 1,
1, 0, 0, 1), (1, 0, 1, 1, 0, 1, 0), (0, 1, 1, 1, 1, 0, 0), (1, 1, 1, 1,
1, 1, 1)]
[(0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 1, 1), (0, 1, 0, 0, 1, 0, 1), (1, 1, 0, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1, 0), (1, 0, 1, 0, 1, 0, 1), (0, 1, 1, 0, 0, 1, 1), (1, 1, 1, 0, 0, 0, 0), (0, 0, 0, 1, 1, 1, 1), (1, 0, 0, 1, 1, 0, 0), (0, 1, 0, 1, 0, 1, 0), (1, 1, 0, 1, 0, 0, 1), (0, 0, 1, 1, 0, 0, 1), (1, 0, 1, 1, 0, 1, 0), (0, 1, 1, 1, 1, 0, 0), (1, 1, 1, 1, 1, 1, 1)]
C.is_self_dual() 
       
False
False
D = C.dual_code() 
       
D.minimum_distance() 
       
4
4
C.gen_mat() 
       
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]
[1 0 0 0 0 1 1]
[0 1 0 0 1 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 1 1 1]
len(list(C)) 
       
16
16
D.gen_mat() 
       
[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]
[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]

Dilbert

C = HammingCode(7, GF(2)) C 
       
Linear code of length 127, dimension 120 over Finite Field of size 2
Linear code of length 127, dimension 120 over Finite Field of size 2
C = TernaryGolayCode() C 
       
Linear code of length 11, dimension 6 over Finite Field of size 3
Linear code of length 11, dimension 6 over Finite Field of size 3
C.minimum_distance() 
       
5
5
print best_known_linear_code_www(10,5,GF(2)) 
       
Construction of a linear code 
[10,5,4] over GF(2):
[1]:  [4, 1, 4] Cyclic Linear Code over GF(2)
     RepetitionCode of length 4
[2]:  [4, 3, 2] Cyclic Linear Code over GF(2)
     Dual of the RepetitionCode of length 4
[3]:  [8, 4, 4] Quasicyclic of degree 2 Linear Code over GF(2)
     PlotkinSum of [2] and [1]
[4]:  [8, 7, 2] Cyclic Linear Code over GF(2)
     Dual of the RepetitionCode of length 8
[5]:  [16, 11, 4] Linear Code over GF(2)
     PlotkinSum of [4] and [3]
[6]:  [10, 5, 4] Linear Code over GF(2)
     Shortening of [5] at { 11 .. 16 }

last modified: 2001-01-30
Construction of a linear code 
[10,5,4] over GF(2):
[1]:  [4, 1, 4] Cyclic Linear Code over GF(2)
     RepetitionCode of length 4
[2]:  [4, 3, 2] Cyclic Linear Code over GF(2)
     Dual of the RepetitionCode of length 4
[3]:  [8, 4, 4] Quasicyclic of degree 2 Linear Code over GF(2)
     PlotkinSum of [2] and [1]
[4]:  [8, 7, 2] Cyclic Linear Code over GF(2)
     Dual of the RepetitionCode of length 8
[5]:  [16, 11, 4] Linear Code over GF(2)
     PlotkinSum of [4] and [3]
[6]:  [10, 5, 4] Linear Code over GF(2)
     Shortening of [5] at { 11 .. 16 }

last modified: 2001-01-30

xkcd

Encoding / Decoding

C = HammingCode(3, GF(2)) C 
       
Linear code of length 7, dimension 4 over Finite Field of size 2
Linear code of length 7, dimension 4 over Finite Field of size 2
len(C) 
       
16
16
# converts codeword vectors to binary strings def codeword_to_string(w): res = '' for i in w: res += str(i) return res 
       
for w in C: print codeword_to_string(w) 
       
0000000
1000011
0100101
1100110
0010110
1010101
0110011
1110000
0001111
1001100
0101010
1101001
0011001
1011010
0111100
1111111
0000000
1000011
0100101
1100110
0010110
1010101
0110011
1110000
0001111
1001100
0101010
1101001
0011001
1011010
0111100
1111111
# Letters we can encode messages with chars = 'bcefghijlnopstu ' len(chars) 
       
16
16
msg = 'hi bob' 
       
zip( chars, C ) 
       
[('b', (0, 0, 0, 0, 0, 0, 0)), ('c', (1, 0, 0, 0, 0, 1, 1)), ('e', (0,
1, 0, 0, 1, 0, 1)), ('f', (1, 1, 0, 0, 1, 1, 0)), ('g', (0, 0, 1, 0, 1,
1, 0)), ('h', (1, 0, 1, 0, 1, 0, 1)), ('i', (0, 1, 1, 0, 0, 1, 1)),
('j', (1, 1, 1, 0, 0, 0, 0)), ('l', (0, 0, 0, 1, 1, 1, 1)), ('n', (1, 0,
0, 1, 1, 0, 0)), ('o', (0, 1, 0, 1, 0, 1, 0)), ('p', (1, 1, 0, 1, 0, 0,
1)), ('s', (0, 0, 1, 1, 0, 0, 1)), ('t', (1, 0, 1, 1, 0, 1, 0)), ('u',
(0, 1, 1, 1, 1, 0, 0)), (' ', (1, 1, 1, 1, 1, 1, 1))]
[('b', (0, 0, 0, 0, 0, 0, 0)), ('c', (1, 0, 0, 0, 0, 1, 1)), ('e', (0, 1, 0, 0, 1, 0, 1)), ('f', (1, 1, 0, 0, 1, 1, 0)), ('g', (0, 0, 1, 0, 1, 1, 0)), ('h', (1, 0, 1, 0, 1, 0, 1)), ('i', (0, 1, 1, 0, 0, 1, 1)), ('j', (1, 1, 1, 0, 0, 0, 0)), ('l', (0, 0, 0, 1, 1, 1, 1)), ('n', (1, 0, 0, 1, 1, 0, 0)), ('o', (0, 1, 0, 1, 0, 1, 0)), ('p', (1, 1, 0, 1, 0, 0, 1)), ('s', (0, 0, 1, 1, 0, 0, 1)), ('t', (1, 0, 1, 1, 0, 1, 0)), ('u', (0, 1, 1, 1, 1, 0, 0)), (' ', (1, 1, 1, 1, 1, 1, 1))]
encoder = dict(zip( chars, C )) print encoder['b'] print encoder['o'] 
       
(0, 0, 0, 0, 0, 0, 0)
(0, 1, 0, 1, 0, 1, 0)
(0, 0, 0, 0, 0, 0, 0)
(0, 1, 0, 1, 0, 1, 0)
# Convert a message string into a sequence of binary strings in the code. def encode(str): res = [] for c in str: res.append(codeword_to_string(encoder[c])) return res encode('hi bob') 
       
['1010101', '0110011', '1111111', '0000000', '0101010', '0000000']
['1010101', '0110011', '1111111', '0000000', '0101010', '0000000']