Decoding methods for linear error-correcting codes.

Methods implemented:

  • nearest neighbor
  • syndrome

AUTHOR:

  • David Joyner (2009-02-01): initial version

Todo

Add lots more methods!

sage.coding.decoder.coset_leader(C, v)

The vector v represents a received word, so should be in the same ambient space V as C. Returns an element of the syndrome of v of lowest weight.

EXAMPLES:

sage: C = codes.HammingCode(2,GF(3)); C
Linear code of length 4, dimension 2 over Finite Field of size 3
sage: V = VectorSpace(GF(3), 4)
sage: v = V([0, 2, 0, 1])
sage: from sage.coding.decoder import coset_leader
sage: coset_leader(C, v)
((0, 0, 1, 0), 1)
sage: coset_leader(C, v)[0]-v in C
True
sage.coding.decoder.decode(C, v, algorithm='syndrome')

The vector v represents a received word, so should be in the same ambient space V as C. Returns an element in C which is closest to v in the Hamming metric.

Methods implemented include “nearest neighbor” (essentially a brute force search) and “syndrome”.

EXAMPLES:

sage: C = codes.HammingCode(2,GF(3))
sage: V = VectorSpace(GF(3), 4)
sage: v = V([0, 2, 0, 1])
sage: v in C
False
sage: from sage.coding.decoder import decode
sage: c = decode(C, v);c
(0, 2, 2, 1)
sage: c in C
True
sage: c = decode(C, v, algorithm="nearest neighbor");c
(0, 2, 2, 1)
sage: C = codes.HammingCode(3,GF(3)); C
Linear code of length 13, dimension 10 over Finite Field of size 3
sage: V = VectorSpace(GF(3), 13)
sage: v = V([2]+[0]*12)
sage: decode(C, v)  # long time (9s on sage.math, 2011)
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sage.coding.decoder.syndrome(C, v)

The vector v represents a received word, so should be in the same ambient space V as C. Returns the elements in V (including v) which belong to the syndrome of v (ie, the coset v+C, sorted by weight).

EXAMPLES:

sage: C = codes.HammingCode(2,GF(3)); C
Linear code of length 4, dimension 2 over Finite Field of size 3
sage: V = VectorSpace(GF(3), 4)
sage: v = V([0, 2, 0, 1])
sage: from sage.coding.decoder import syndrome
sage: syndrome(C, v)
 [(0, 0, 1, 0), (0, 2, 0, 1), (2, 0, 0, 2), (1, 1, 0, 0), (2, 2, 2, 0), (1, 0, 2, 1), (0, 1, 2, 2), (1, 2, 1, 2), (2, 1, 1, 1)]