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 MultivariateSeries
X = @ring x1 x2

2-element Vector{DynamicPolynomials.PolyVar{true}}:
 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 Vector{DynamicPolynomials.Monomial{true}}:
 1
 x1
 x2
 x1²
 x1x2
 x2²

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

using DynamicPolynomials
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  0   2  1   1
 1  -1   1  -1  1  -1  2  -2
 1   1   1   1  0   4  1   1
 1  -1  -1   1  0  -2  2  -2
 1   1   1   1  1   1  4   4

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
 -2
  1
  0
  3
 -3

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

sigma = dual(M'*s)

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

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

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

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

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 Matrix{Float64}:
 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 Vector{Any}:
 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(::Matrix{Int64}) with eltype 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}:
  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 Vector{Int64}:
  3
  3
  3
 -1
 -6
 -2
  0
  0

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

W*c

6-element Vector{Int64}:
 0
 0
 0
 0
 0
 0