2024-02-26--array-decoding.ipynb

Kernel: Python 3 (ipykernel)

Let's create a $[5,2,3]_3$ code.

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

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

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

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])

3

# build the coset of C with representative v, and sort the vectors in order of
# increasing weight

def coset(v):
    c =  [ v + c for c in C ]
    c.sort(key = lambda x: weight(x))
    return list(c)

We build the array whose rows are the cosets of C.

Notice that vectors in W provide a full set of coset representatives.

lookup = [ coset(w) for w in W ]

In order to decode the vector v, we find the coset c containing v, and return v - c[0].

def decode(w):
    c = [x for x in lookup if w in x ][0]
    return w - c[0]

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

[((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)]

We should be able to correct (d-1)/2 = (3-1)/2 = 1 error.

# 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()]

[((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)])]

But: we shouldn't in general be able to correct 2 errors.

# 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 ]

[((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)]