Decoding algebraic codes (BMS)

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

using DynamicPolynomials, MultivariateSeries
X = @polyvar x1 x2

(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 = monomials(X,0:2)

6-element MonomialVector{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}}:
 1
 x2
 x1
 x2²
 x1x2
 x1²

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

function vdm(P,L)
    [ (L[j]+0)(P[:,i])
        for  j in 1:length(L),i in 1:size(P,2) ]
end
W = vdm(P,M)

6×8 Matrix{Int64}:
 1   1   1   1  1   1  1   1
 1  -1   1  -1  1  -1  2  -2
 1   1  -1  -1  0   2  1   1
 1   1   1   1  1   1  4   4
 1  -1  -1   1  0  -2  2  -2
 1   1   1   1  0   4  1   1

We receive the following word:

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

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

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

s = W*r

6-element Vector{Int64}:
  0
  1
 -2
 -3
  3
  0

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

sigma = dual(M'*s)

dx2 - 2dx1 - 3dx2^2 + 3dx1*dx2

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

L1 = monomials(X,0:1)
H = hankel(sigma, L1, L1)

3×3 Matrix{Int64}:
  0   1  -2
  1  -3   3
 -2   3   0

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

using LinearAlgebra
le = nullspace(H); le/=le[3]
ple = dot(L1,le)

$ 2.9999999999999987 + 1.9999999999999984x2 + x1 $

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

er = [subs(ple,x1=>P[1,k], x2=>P[2,k]) for  k in 1:size(P,2)]

8-element Vector{Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Float64}}:
 5.999999999999997
 2.0
 3.9999999999999973
 2.220446049250313e-16
 4.999999999999997
 3.0
 7.999999999999996
 1.7763568394002505e-15

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

2-element Vector{Any}:
 4
 8

These are the following points of $P$:

E = hcat([P[:,ie[i]] for i in 1:length(ie)]...)

2×2 Matrix{Int64}:
 -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 Vector{Float64}:
 -0.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 Vector{Int64}:
  3
  3
  3
  0
 -6
 -2
  0
 -2

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

W*c

6-element Vector{Int64}:
 -1
  3
 -3
 -7
  5
 -1