{ "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 }