CoCalc -- 2024-02-26--syndrome-decoding.ipynb

GitHub Repository: gmcninch-tufts/2024-Sp-Math190
Path: blob/main/course-contents/notebooks/2024-02-26--syndrome-decoding.ipynb
⁴⁶⁹ views

Kernel: Python 3 (ipykernel)

In [67]:

K = GF(3);
V = VectorSpace(K,5)

C= V.subspace([V([1,0,1,1,0]),
               V([0,1,1,0,1])])

G = MatrixSpace(K,2,5).matrix(C.basis())
G

A = MatrixSpace(K,2,3).matrix([b[2:5] for b in G])


H=block_matrix([[-A.transpose(),MatrixSpace(K,3,3).one()]],
               subdivide=False)  

def weight(v):
    r = [x for x in v if x != 0]
    return len(r)

min([ weight(v) for v in C if v != 0])

H

Out[67]:

[2 2 1 0 0]
[2 0 0 1 0]
[0 2 0 0 1]

In [68]:

lookup = { tuple(H*v):v for v in V if weight(v) < 2 }
lookup

Out[68]:

{(0, 0, 0): (0, 0, 0, 0, 0),
 (2, 2, 0): (1, 0, 0, 0, 0),
 (1, 1, 0): (2, 0, 0, 0, 0),
 (2, 0, 2): (0, 1, 0, 0, 0),
 (1, 0, 1): (0, 2, 0, 0, 0),
 (1, 0, 0): (0, 0, 1, 0, 0),
 (2, 0, 0): (0, 0, 2, 0, 0),
 (0, 1, 0): (0, 0, 0, 1, 0),
 (0, 2, 0): (0, 0, 0, 2, 0),
 (0, 0, 1): (0, 0, 0, 0, 1),
 (0, 0, 2): (0, 0, 0, 0, 2)}

In [69]:

def decode(v):
    return v-lookup[tuple(H*v)]

In [70]:

[ (decode(c), c==decode(c)) for c in C ]

Out[70]:

[((0, 0, 0, 0, 0), True),
 ((1, 0, 1, 1, 0), True),
 ((2, 0, 2, 2, 0), True),
 ((0, 1, 1, 0, 1), True),
 ((1, 1, 2, 1, 1), True),
 ((2, 1, 0, 2, 1), True),
 ((0, 2, 2, 0, 2), True),
 ((1, 2, 0, 1, 2), True),
 ((2, 2, 1, 2, 2), True)]

In [77]:

# consider "error vectors" of weight 1

[ (e,[(c+e, decode(c+e), decode(c+e) ==  c) for c in C]) for e in V.basis()]

Out[77]:

[((1, 0, 0, 0, 0),
  [((1, 0, 0, 0, 0), (0, 0, 0, 0, 0), True),
   ((2, 0, 1, 1, 0), (1, 0, 1, 1, 0), True),
   ((0, 0, 2, 2, 0), (2, 0, 2, 2, 0), True),
   ((1, 1, 1, 0, 1), (0, 1, 1, 0, 1), True),
   ((2, 1, 2, 1, 1), (1, 1, 2, 1, 1), True),
   ((0, 1, 0, 2, 1), (2, 1, 0, 2, 1), True),
   ((1, 2, 2, 0, 2), (0, 2, 2, 0, 2), True),
   ((2, 2, 0, 1, 2), (1, 2, 0, 1, 2), True),
   ((0, 2, 1, 2, 2), (2, 2, 1, 2, 2), True)]),
 ((0, 1, 0, 0, 0),
  [((0, 1, 0, 0, 0), (0, 0, 0, 0, 0), True),
   ((1, 1, 1, 1, 0), (1, 0, 1, 1, 0), True),
   ((2, 1, 2, 2, 0), (2, 0, 2, 2, 0), True),
   ((0, 2, 1, 0, 1), (0, 1, 1, 0, 1), True),
   ((1, 2, 2, 1, 1), (1, 1, 2, 1, 1), True),
   ((2, 2, 0, 2, 1), (2, 1, 0, 2, 1), True),
   ((0, 0, 2, 0, 2), (0, 2, 2, 0, 2), True),
   ((1, 0, 0, 1, 2), (1, 2, 0, 1, 2), True),
   ((2, 0, 1, 2, 2), (2, 2, 1, 2, 2), True)]),
 ((0, 0, 1, 0, 0),
  [((0, 0, 1, 0, 0), (0, 0, 0, 0, 0), True),
   ((1, 0, 2, 1, 0), (1, 0, 1, 1, 0), True),
   ((2, 0, 0, 2, 0), (2, 0, 2, 2, 0), True),
   ((0, 1, 2, 0, 1), (0, 1, 1, 0, 1), True),
   ((1, 1, 0, 1, 1), (1, 1, 2, 1, 1), True),
   ((2, 1, 1, 2, 1), (2, 1, 0, 2, 1), True),
   ((0, 2, 0, 0, 2), (0, 2, 2, 0, 2), True),
   ((1, 2, 1, 1, 2), (1, 2, 0, 1, 2), True),
   ((2, 2, 2, 2, 2), (2, 2, 1, 2, 2), True)]),
 ((0, 0, 0, 1, 0),
  [((0, 0, 0, 1, 0), (0, 0, 0, 0, 0), True),
   ((1, 0, 1, 2, 0), (1, 0, 1, 1, 0), True),
   ((2, 0, 2, 0, 0), (2, 0, 2, 2, 0), True),
   ((0, 1, 1, 1, 1), (0, 1, 1, 0, 1), True),
   ((1, 1, 2, 2, 1), (1, 1, 2, 1, 1), True),
   ((2, 1, 0, 0, 1), (2, 1, 0, 2, 1), True),
   ((0, 2, 2, 1, 2), (0, 2, 2, 0, 2), True),
   ((1, 2, 0, 2, 2), (1, 2, 0, 1, 2), True),
   ((2, 2, 1, 0, 2), (2, 2, 1, 2, 2), True)]),
 ((0, 0, 0, 0, 1),
  [((0, 0, 0, 0, 1), (0, 0, 0, 0, 0), True),
   ((1, 0, 1, 1, 1), (1, 0, 1, 1, 0), True),
   ((2, 0, 2, 2, 1), (2, 0, 2, 2, 0), True),
   ((0, 1, 1, 0, 2), (0, 1, 1, 0, 1), True),
   ((1, 1, 2, 1, 2), (1, 1, 2, 1, 1), True),
   ((2, 1, 0, 2, 2), (2, 1, 0, 2, 1), True),
   ((0, 2, 2, 0, 0), (0, 2, 2, 0, 2), True),
   ((1, 2, 0, 1, 0), (1, 2, 0, 1, 2), True),
   ((2, 2, 1, 2, 0), (2, 2, 1, 2, 2), True)])]

In [72]:

# consider an "error vector" with weight 2
f = V([0,1,1,0,0])

[ (c+f, decode(c+f), decode(c+f) == c) for c in C ]

Out[72]:

[((0, 1, 1, 0, 0), (0, 1, 1, 0, 1), False),
 ((1, 1, 2, 1, 0), (1, 1, 2, 1, 1), False),
 ((2, 1, 0, 2, 0), (2, 1, 0, 2, 1), False),
 ((0, 2, 2, 0, 1), (0, 2, 2, 0, 2), False),
 ((1, 2, 0, 1, 1), (1, 2, 0, 1, 2), False),
 ((2, 2, 1, 2, 1), (2, 2, 1, 2, 2), False),
 ((0, 0, 0, 0, 2), (0, 0, 0, 0, 0), False),
 ((1, 0, 1, 1, 2), (1, 0, 1, 1, 0), False),
 ((2, 0, 2, 2, 2), (2, 0, 2, 2, 0), False)]

In [ ]:

Product

Resources

Company