Decoding algebraic codes (BMS)

We consider the code $C$ formed by the words $m\in \mathbb{k}^l$ such that $ m.[f(P1), \ldots, f(Pl)]=0 $ where $f\in V\subset \mathbb{k}[x_1,...,x_n]$.

using TensorDec
X = @ring x1 x2

2-element Array{DynamicPolynomials.PolyVar{true},1}:
 x1
 x2

We consider the following points $P$ and the vector space $V$ spanned by the monomials $M$ of degree $\le 2$ in two variables $x_1, x_2$.

P = [
1   1;
1  -1;
-1  1;
-1 -1;
0   1; 
2  -1;
1   2;
1  -2]'

M = monoms(X,2)

6-element Array{DynamicPolynomials.Monomial{true},1}:
 1   
 x1  
 x2  
 x1² 
 x1x2
 x2²

The words of the code are the kernel of the following matrix:

using DynamicPolynomials
function vdm(P,L)
    [ Polynomial{true,Float64}(L[j])(P[:,i])
        for  j in 1:length(L),i in 1:size(P,2) ]
end
W = vdm(P,M)

6×8 Array{Float64,2}:
 1.0   1.0   1.0   1.0  1.0   1.0  1.0   1.0
 1.0   1.0  -1.0  -1.0  0.0   2.0  1.0   1.0
 1.0  -1.0   1.0  -1.0  1.0  -1.0  2.0  -2.0
 1.0   1.0   1.0   1.0  0.0   4.0  1.0   1.0
 1.0  -1.0  -1.0   1.0  0.0  -2.0  2.0  -2.0
 1.0   1.0   1.0   1.0  1.0   1.0  4.0   4.0

We receive the following word:

r = [3, 3, 3, 0, -6, -2, 0, -1]

8-element Array{Int64,1}:
  3
  3
  3
  0
 -6
 -2
  0
 -1

It is not a word of code $C$, since the following vector of syndroms is not zero:

s = W*r

6-element Array{Float64,1}:
  0.0
 -2.0
  1.0
  0.0
  3.0
 -3.0

We want to correct it. For that, we build the corresponding series of syndroms:

sigma = dual(M'*s)

3.0dx1*dx2 - 3.0dx2^2 + dx2 - 2.0dx1

The Hankel matrix of $\sigma$ in degree $\le 1$ is:

L1 = monoms(X,1)
H = hankel(sigma, L1, L1)

3×3 Array{Float64,2}:
  0.0  -2.0   1.0
 -2.0   0.0   3.0
  1.0   3.0  -3.0

An element in its kernel gives an error locator polynomial of degree $1$:

using LinearAlgebra
le = nullspace(H); le/=le[3]
ple = (L1'*le)[1]

0.5000000000000002x1 + x2 + 1.5

We check for which point in P, this polynomial vanishes. This will give the position where an error occurs:

er = le'*vcat(fill(1.,1,size(P,2)),P)

1×8 Array{Float64,2}:
 3.0  1.0  2.0  -2.22045e-16  2.5  1.5  4.0  0.0

ie = []
for i in 1:length(er)
    if isapprox(er[i],0.0;atol=1e-10) push!(ie, i) end
end
ie

2-element Array{Any,1}:
 4
 8

These are the following points of $P$:

E = ([P[j,ie[i]] for i in 1:length(ie), j in 1:size(P,1)])'

2×2 Adjoint{Int64,Array{Int64,2}}:
 -1   1
 -1  -2

To get the error, that is the weights, we solve the system: $E*\omega =[\sigma_{x_1}, \sigma_{x_2}]$:

cr = E\(W*r)[2:3]

2-element Array{Float64,1}:
  1.0
 -1.0

We can now correct the received message by removing the weights $cr$ at the positions of the errors $ie$:

c=copy(r)
for i in 1:length(ie) c[ie[i]]-= cr[i] end 
c

8-element Array{Int64,1}:
  3
  3
  3
 -1
 -6
 -2
  0
  0

We check that the corrected message is a word of the code:

W*c

6-element Array{Float64,1}:
 0.0
 0.0
 0.0
 0.0
 0.0
 0.0