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