{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decoding algebraic codes (BMS)\n",
    "\n",
    "We consider the code $C$ formed by the words $m\\in \\mathbb{k}^l$ such that \n",
    "$$\n",
    "m.[f(P_1), \\ldots, f(P_l)]=0\n",
    "$$ \n",
    "where $f\\in V\\subset \\mathbb{k}[x_1,...,x_n]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{DynamicPolynomials.PolyVar{true},1}:\n",
       " x1\n",
       " x2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using TensorDec\n",
    "X = @ring x1 x2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Array{DynamicPolynomials.Monomial{true},1}:\n",
       " 1   \n",
       " x1  \n",
       " x2  \n",
       " x1² \n",
       " x1x2\n",
       " x2² "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = [\n",
    "1   1;\n",
    "1  -1;\n",
    "-1  1;\n",
    "-1 -1;\n",
    "0   1; \n",
    "2  -1;\n",
    "1   2;\n",
    "1  -2]'\n",
    "\n",
    "M = monoms(X,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The words of the code are the kernel of the following matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6×8 Array{Float64,2}:\n",
       " 1.0   1.0   1.0   1.0  1.0   1.0  1.0   1.0\n",
       " 1.0   1.0  -1.0  -1.0  0.0   2.0  1.0   1.0\n",
       " 1.0  -1.0   1.0  -1.0  1.0  -1.0  2.0  -2.0\n",
       " 1.0   1.0   1.0   1.0  0.0   4.0  1.0   1.0\n",
       " 1.0  -1.0  -1.0   1.0  0.0  -2.0  2.0  -2.0\n",
       " 1.0   1.0   1.0   1.0  1.0   1.0  4.0   4.0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using DynamicPolynomials\n",
    "function vdm(P,L)\n",
    "    [ Polynomial{true,Float64}(L[j])(P[:,i])\n",
    "        for  j in 1:length(L),i in 1:size(P,2) ]\n",
    "end\n",
    "W = vdm(P,M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We receive the following word:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8-element Array{Int64,1}:\n",
       "  3\n",
       "  3\n",
       "  3\n",
       "  0\n",
       " -6\n",
       " -2\n",
       "  0\n",
       " -1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = [3, 3, 3, 0, -6, -2, 0, -1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is not a word of code $C$, since the following vector of syndroms is not zero:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Array{Float64,1}:\n",
       "  0.0\n",
       " -2.0\n",
       "  1.0\n",
       "  0.0\n",
       "  3.0\n",
       " -3.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = W*r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to correct it. For that, we build the corresponding series of syndroms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0dx1*dx2 - 3.0dx2^2 + dx2 - 2.0dx1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sigma = dual(M'*s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Hankel matrix of $\\sigma$ in degree $\\le 1$ is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3×3 Array{Float64,2}:\n",
       "  0.0  -2.0   1.0\n",
       " -2.0   0.0   3.0\n",
       "  1.0   3.0  -3.0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L1 = monoms(X,1)\n",
    "H = hankel(sigma, L1, L1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An element in its kernel gives an error locator polynomial of degree $1$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "0.5000000000000002x1 + x2 + 1.5"
      ],
      "text/plain": [
       "0.5000000000000002x1 + x2 + 1.5"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using LinearAlgebra\n",
    "le = nullspace(H); le/=le[3]\n",
    "ple = (L1'*le)[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We check for which point in P, this polynomial vanishes. This will give the position where an error occurs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1×8 Array{Float64,2}:\n",
       " 3.0  1.0  2.0  -2.22045e-16  2.5  1.5  4.0  0.0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "er = le'*vcat(fill(1.,1,size(P,2)),P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Any,1}:\n",
       " 4\n",
       " 8"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ie = []\n",
    "for i in 1:length(er)\n",
    "    if isapprox(er[i],0.0;atol=1e-10) push!(ie, i) end\n",
    "end\n",
    "ie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the following points of $P$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Adjoint{Int64,Array{Int64,2}}:\n",
       " -1   1\n",
       " -1  -2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E = ([P[j,ie[i]] for i in 1:length(ie), j in 1:size(P,1)])'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get the error, that is the weights, we solve the system: $E*\\omega =[\\sigma_{x_1}, \\sigma_{x_2}]$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2-element Array{Float64,1}:\n",
       "  1.0\n",
       " -1.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cr = E\\(W*r)[2:3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now correct the received message by removing the weights $cr$ at the positions of the errors $ie$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8-element Array{Int64,1}:\n",
       "  3\n",
       "  3\n",
       "  3\n",
       " -1\n",
       " -6\n",
       " -2\n",
       "  0\n",
       "  0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c=copy(r)\n",
    "for i in 1:length(ie) c[ie[i]]-= cr[i] end \n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We check that the corrected message is a word of the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Array{Float64,1}:\n",
       " 0.0\n",
       " 0.0\n",
       " 0.0\n",
       " 0.0\n",
       " 0.0\n",
       " 0.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "W*c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Julia 1.0.0",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}