{ "cells": [ { "cell_type": "markdown", "id": "3a290ee6", "metadata": {}, "source": [ "# IMAO - Codes correcteurs" ] }, { "cell_type": "markdown", "id": "aa467af6", "metadata": {}, "source": [ "## Matrices des codes" ] }, { "cell_type": "code", "execution_count": 1, "id": "9fb238d7", "metadata": {}, "outputs": [], "source": [ "%display latex" ] }, { "cell_type": "code", "execution_count": 2, "id": "1cc523d2", "metadata": {}, "outputs": [], "source": [ "F2=FiniteField(2)" ] }, { "cell_type": "markdown", "id": "8c888470", "metadata": {}, "source": [ "Matrices G" ] }, { "cell_type": "code", "execution_count": 3, "id": "fd8c36bb", "metadata": {}, "outputs": [], "source": [ "def get_G1():\n", " G1=matrix(F2,9,8)\n", " for i in range(8):\n", " G1[i,i]=1\n", " for i in range(8):\n", " G1[8,i]=1\n", " return G1" ] }, { "cell_type": "code", "execution_count": 4, "id": "d15d30d2", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrrr}\n", "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrrr}\n", "1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\\\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 0 0 0 0 0 0 0]\n", "[0 1 0 0 0 0 0 0]\n", "[0 0 1 0 0 0 0 0]\n", "[0 0 0 1 0 0 0 0]\n", "[0 0 0 0 1 0 0 0]\n", "[0 0 0 0 0 1 0 0]\n", "[0 0 0 0 0 0 1 0]\n", "[0 0 0 0 0 0 0 1]\n", "[1 1 1 1 1 1 1 1]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G1=get_G1();G1" ] }, { "cell_type": "code", "execution_count": 5, "id": "8a32424a", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{r}\n", "1 \\\\\n", "1 \\\\\n", "1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{r}\n", "1 \\\\\n", "1 \\\\\n", "1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1]\n", "[1]\n", "[1]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G2=matrix(F2,3,1,[1,1,1]);G2" ] }, { "cell_type": "code", "execution_count": 6, "id": "2748dcf2", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rr}\n", "1 & 0 \\\\\n", "0 & 1 \\\\\n", "1 & 0 \\\\\n", "1 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rr}\n", "1 & 0 \\\\\n", "0 & 1 \\\\\n", "1 & 0 \\\\\n", "1 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 0]\n", "[0 1]\n", "[1 0]\n", "[1 1]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G3=matrix(F2,4,2,[1,0,0,1,1,0,1,1]);G3" ] }, { "cell_type": "code", "execution_count": 7, "id": "ac13a283", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 1 \\\\\n", "1 & 1 & 0 & 1 \\\\\n", "1 & 0 & 1 & 1 \\\\\n", "0 & 1 & 1 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "0 & 0 & 0 & 1 \\\\\n", "1 & 1 & 0 & 1 \\\\\n", "1 & 0 & 1 & 1 \\\\\n", "0 & 1 & 1 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 0 0 0]\n", "[0 1 0 0]\n", "[0 0 1 0]\n", "[0 0 0 1]\n", "[1 1 0 1]\n", "[1 0 1 1]\n", "[0 1 1 1]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G4=matrix(F2,7,4,[1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,1]);G4" ] }, { "cell_type": "markdown", "id": "ecc97e06", "metadata": {}, "source": [ "## Image" ] }, { "cell_type": "code", "execution_count": 8, "id": "64232151", "metadata": {}, "outputs": [], "source": [ "def image(G):\n", " (n,k)=G.dimensions()\n", " U=VectorSpace(F2,k)\n", " return [G*m for m in U]" ] }, { "cell_type": "code", "execution_count": 9, "id": "61e6b88e", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}256\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}256$$" ], "text/plain": [ "256" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(image(G1))" ] }, { "cell_type": "code", "execution_count": 10, "id": "20495a7d", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0\\right), \\left(1,\\,1,\\,1\\right)\\right]\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0\\right), \\left(1,\\,1,\\,1\\right)\\right]$$" ], "text/plain": [ "[(0, 0, 0), (1, 1, 1)]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "image(G2)" ] }, { "cell_type": "code", "execution_count": 11, "id": "c0a16f99", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,1,\\,1\\right), \\left(0,\\,1,\\,0,\\,1\\right), \\left(1,\\,1,\\,1,\\,0\\right)\\right]\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,1,\\,1\\right), \\left(0,\\,1,\\,0,\\,1\\right), \\left(1,\\,1,\\,1,\\,0\\right)\\right]$$" ], "text/plain": [ "[(0, 0, 0, 0), (1, 0, 1, 1), (0, 1, 0, 1), (1, 1, 1, 0)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "image(G3)" ] }, { "cell_type": "code", "execution_count": 12, "id": "8f6f2dd0", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,0,\\,0,\\,1,\\,1,\\,0\\right), \\left(0,\\,1,\\,0,\\,0,\\,1,\\,0,\\,1\\right), \\left(1,\\,1,\\,0,\\,0,\\,0,\\,1,\\,1\\right), \\left(0,\\,0,\\,1,\\,0,\\,0,\\,1,\\,1\\right), \\left(1,\\,0,\\,1,\\,0,\\,1,\\,0,\\,1\\right), \\left(0,\\,1,\\,1,\\,0,\\,1,\\,1,\\,0\\right), \\left(1,\\,1,\\,1,\\,0,\\,0,\\,0,\\,0\\right), \\left(0,\\,0,\\,0,\\,1,\\,1,\\,1,\\,1\\right), \\left(1,\\,0,\\,0,\\,1,\\,0,\\,0,\\,1\\right), \\left(0,\\,1,\\,0,\\,1,\\,0,\\,1,\\,0\\right), \\left(1,\\,1,\\,0,\\,1,\\,1,\\,0,\\,0\\right), \\left(0,\\,0,\\,1,\\,1,\\,1,\\,0,\\,0\\right), \\left(1,\\,0,\\,1,\\,1,\\,0,\\,1,\\,0\\right), \\left(0,\\,1,\\,1,\\,1,\\,0,\\,0,\\,1\\right), \\left(1,\\,1,\\,1,\\,1,\\,1,\\,1,\\,1\\right)\\right]\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left[\\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,0,\\,0,\\,1,\\,1,\\,0\\right), \\left(0,\\,1,\\,0,\\,0,\\,1,\\,0,\\,1\\right), \\left(1,\\,1,\\,0,\\,0,\\,0,\\,1,\\,1\\right), \\left(0,\\,0,\\,1,\\,0,\\,0,\\,1,\\,1\\right), \\left(1,\\,0,\\,1,\\,0,\\,1,\\,0,\\,1\\right), \\left(0,\\,1,\\,1,\\,0,\\,1,\\,1,\\,0\\right), \\left(1,\\,1,\\,1,\\,0,\\,0,\\,0,\\,0\\right), \\left(0,\\,0,\\,0,\\,1,\\,1,\\,1,\\,1\\right), \\left(1,\\,0,\\,0,\\,1,\\,0,\\,0,\\,1\\right), \\left(0,\\,1,\\,0,\\,1,\\,0,\\,1,\\,0\\right), \\left(1,\\,1,\\,0,\\,1,\\,1,\\,0,\\,0\\right), \\left(0,\\,0,\\,1,\\,1,\\,1,\\,0,\\,0\\right), \\left(1,\\,0,\\,1,\\,1,\\,0,\\,1,\\,0\\right), \\left(0,\\,1,\\,1,\\,1,\\,0,\\,0,\\,1\\right), \\left(1,\\,1,\\,1,\\,1,\\,1,\\,1,\\,1\\right)\\right]$$" ], "text/plain": [ "[(0, 0, 0, 0, 0, 0, 0),\n", " (1, 0, 0, 0, 1, 1, 0),\n", " (0, 1, 0, 0, 1, 0, 1),\n", " (1, 1, 0, 0, 0, 1, 1),\n", " (0, 0, 1, 0, 0, 1, 1),\n", " (1, 0, 1, 0, 1, 0, 1),\n", " (0, 1, 1, 0, 1, 1, 0),\n", " (1, 1, 1, 0, 0, 0, 0),\n", " (0, 0, 0, 1, 1, 1, 1),\n", " (1, 0, 0, 1, 0, 0, 1),\n", " (0, 1, 0, 1, 0, 1, 0),\n", " (1, 1, 0, 1, 1, 0, 0),\n", " (0, 0, 1, 1, 1, 0, 0),\n", " (1, 0, 1, 1, 0, 1, 0),\n", " (0, 1, 1, 1, 0, 0, 1),\n", " (1, 1, 1, 1, 1, 1, 1)]" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "image(G4)" ] }, { "cell_type": "markdown", "id": "a748394d", "metadata": {}, "source": [ "## Distance" ] }, { "cell_type": "code", "execution_count": 13, "id": "b24abd2e", "metadata": {}, "outputs": [], "source": [ "def poids_Hamming(x):\n", " d=0\n", " for i in range(len(x)):\n", " if x[i]!=0:\n", " d=d+1\n", " return d" ] }, { "cell_type": "code", "execution_count": 14, "id": "0811ee6a", "metadata": {}, "outputs": [], "source": [ "def distance(G):\n", " C=image(G)\n", " d=Infinity\n", " for x in C:\n", " if x!=0:\n", " d=min(d,poids_Hamming(x))\n", " return d" ] }, { "cell_type": "code", "execution_count": 15, "id": "30450d88", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}2\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$$" ], "text/plain": [ "2" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance(G1)" ] }, { "cell_type": "code", "execution_count": 16, "id": "3c080d5e", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}3\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}3$$" ], "text/plain": [ "3" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance(G2)" ] }, { "cell_type": "code", "execution_count": 17, "id": "3bfa4984", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}2\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}2$$" ], "text/plain": [ "2" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance(G3)" ] }, { "cell_type": "code", "execution_count": 18, "id": "a8b5bcdc", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}3\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}3$$" ], "text/plain": [ "3" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "distance(G4)" ] }, { "cell_type": "markdown", "id": "b27b98b2", "metadata": {}, "source": [ "## MDS ?" ] }, { "cell_type": "code", "execution_count": 19, "id": "6a381047", "metadata": {}, "outputs": [], "source": [ "def est_mds(G):\n", " (n,k)=G.dimensions()\n", " d=distance(G)\n", " return d==n-k+1" ] }, { "cell_type": "code", "execution_count": 20, "id": "e0d9746f", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_mds(G1)" ] }, { "cell_type": "code", "execution_count": 21, "id": "35b31fc1", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_mds(G2)" ] }, { "cell_type": "code", "execution_count": 22, "id": "97f00142", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{False}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{False}$$" ], "text/plain": [ "False" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_mds(G3)" ] }, { "cell_type": "code", "execution_count": 23, "id": "3066c925", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{False}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{False}$$" ], "text/plain": [ "False" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_mds(G4)" ] }, { "cell_type": "markdown", "id": "5b0424dd", "metadata": {}, "source": [ "## Systematique" ] }, { "cell_type": "code", "execution_count": 24, "id": "c1955854", "metadata": {}, "outputs": [], "source": [ "def est_systematique(G):\n", " (n,k)=G.dimensions()\n", " return G.submatrix(0,0,k,k).is_one()" ] }, { "cell_type": "code", "execution_count": 25, "id": "922eef4f", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_systematique(G1)" ] }, { "cell_type": "code", "execution_count": 26, "id": "6e0154ca", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_systematique(G2)" ] }, { "cell_type": "code", "execution_count": 27, "id": "43911308", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_systematique(G3)" ] }, { "cell_type": "code", "execution_count": 28, "id": "9ba5ab95", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}$$" ], "text/plain": [ "True" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "est_systematique(G4)" ] }, { "cell_type": "markdown", "id": "c8545a38", "metadata": {}, "source": [ "## Matrice de contrôle" ] }, { "cell_type": "code", "execution_count": 29, "id": "41497ca5", "metadata": {}, "outputs": [], "source": [ "def matrice_controle(G):\n", " (n,k)=G.dimensions()\n", " GG=G.submatrix(k,0,n-k,k)\n", " H=matrix(F2,n-k,n)\n", " H.set_block(0,0,GG)\n", " H.set_block(0,k,identity_matrix(F2,n-k))\n", " return H" ] }, { "cell_type": "code", "execution_count": 30, "id": "b390c40f", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrrrr}\n", "1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 1 1 1 1 1 1 1 1]" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrice_controle(G1)\n" ] }, { "cell_type": "code", "execution_count": 31, "id": "49743182", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "1 & 0 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "1 & 0 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 1 0]\n", "[1 0 1]" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrice_controle(G2)" ] }, { "cell_type": "code", "execution_count": 32, "id": "373f15ea", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 1 & 0 \\\\\n", "1 & 1 & 0 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 1 & 0 \\\\\n", "1 & 1 & 0 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 0 1 0]\n", "[1 1 0 1]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrice_controle(G3)" ] }, { "cell_type": "code", "execution_count": 33, "id": "ce80d2cf", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrr}\n", "1 & 1 & 0 & 1 & 1 & 0 & 0 \\\\\n", "1 & 0 & 1 & 1 & 0 & 1 & 0 \\\\\n", "0 & 1 & 1 & 1 & 0 & 0 & 1\n", "\\end{array}\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrrrrrr}\n", "1 & 1 & 0 & 1 & 1 & 0 & 0 \\\\\n", "1 & 0 & 1 & 1 & 0 & 1 & 0 \\\\\n", "0 & 1 & 1 & 1 & 0 & 0 & 1\n", "\\end{array}\\right)$$" ], "text/plain": [ "[1 1 0 1 1 0 0]\n", "[1 0 1 1 0 1 0]\n", "[0 1 1 1 0 0 1]" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrice_controle(G4)" ] }, { "cell_type": "markdown", "id": "dac4d52e", "metadata": {}, "source": [ "## Table de décodage" ] }, { "cell_type": "code", "execution_count": 34, "id": "42ceba02", "metadata": {}, "outputs": [], "source": [ "def table_decodage(G):\n", " H=matrice_controle(G)\n", " (n,k)=G.dimensions()\n", " d=distance(G)\n", " table={}\n", " E=VectorSpace(F2,n)\n", " for e in E:\n", " s=H*e\n", " s.set_immutable() # Transfome le vecteur s en vecteur que l'on ne pourra plus modifier\n", " if s in table: # Une erreur est deja affecte au syndrome\n", " f=table[s] # On recupere l'erreur affecte\n", " if poids_Hamming(e)\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1\\right) : \\left(1,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right)\\right\\}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1\\right) : \\left(1,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right)\\right\\}$$" ], "text/plain": [ "{(0): (0, 0, 0, 0, 0, 0, 0, 0, 0), (1): (1, 0, 0, 0, 0, 0, 0, 0, 0)}" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "table_decodage(G1)" ] }, { "cell_type": "code", "execution_count": 36, "id": "9eba1c40", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0\\right) : \\left(0,\\,0,\\,0\\right), \\left(1,\\,1\\right) : \\left(1,\\,0,\\,0\\right), \\left(1,\\,0\\right) : \\left(0,\\,1,\\,0\\right), \\left(0,\\,1\\right) : \\left(0,\\,0,\\,1\\right)\\right\\}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0\\right) : \\left(0,\\,0,\\,0\\right), \\left(1,\\,1\\right) : \\left(1,\\,0,\\,0\\right), \\left(1,\\,0\\right) : \\left(0,\\,1,\\,0\\right), \\left(0,\\,1\\right) : \\left(0,\\,0,\\,1\\right)\\right\\}$$" ], "text/plain": [ "{(0, 0): (0, 0, 0), (1, 1): (1, 0, 0), (1, 0): (0, 1, 0), (0, 1): (0, 0, 1)}" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "table_decodage(G2)" ] }, { "cell_type": "code", "execution_count": 37, "id": "a48511ea", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1\\right) : \\left(1,\\,0,\\,0,\\,0\\right), \\left(0,\\,1\\right) : \\left(0,\\,1,\\,0,\\,0\\right), \\left(1,\\,0\\right) : \\left(0,\\,0,\\,1,\\,0\\right)\\right\\}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1\\right) : \\left(1,\\,0,\\,0,\\,0\\right), \\left(0,\\,1\\right) : \\left(0,\\,1,\\,0,\\,0\\right), \\left(1,\\,0\\right) : \\left(0,\\,0,\\,1,\\,0\\right)\\right\\}$$" ], "text/plain": [ "{(0, 0): (0, 0, 0, 0),\n", " (1, 1): (1, 0, 0, 0),\n", " (0, 1): (0, 1, 0, 0),\n", " (1, 0): (0, 0, 1, 0)}" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "table_decodage(G3)" ] }, { "cell_type": "code", "execution_count": 38, "id": "e7f21062", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1,\\,0\\right) : \\left(1,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,1\\right) : \\left(0,\\,1,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(0,\\,1,\\,1\\right) : \\left(0,\\,0,\\,1,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1,\\,1\\right) : \\left(0,\\,0,\\,0,\\,1,\\,0,\\,0,\\,0\\right), \\left(0,\\,0,\\,1\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,1\\right), \\left(0,\\,1,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,1,\\,0\\right), \\left(1,\\,0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,1,\\,0,\\,0\\right)\\right\\}\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left\\{\\left(0,\\,0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1,\\,0\\right) : \\left(1,\\,0,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,0,\\,1\\right) : \\left(0,\\,1,\\,0,\\,0,\\,0,\\,0,\\,0\\right), \\left(0,\\,1,\\,1\\right) : \\left(0,\\,0,\\,1,\\,0,\\,0,\\,0,\\,0\\right), \\left(1,\\,1,\\,1\\right) : \\left(0,\\,0,\\,0,\\,1,\\,0,\\,0,\\,0\\right), \\left(0,\\,0,\\,1\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,0,\\,1\\right), \\left(0,\\,1,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,0,\\,1,\\,0\\right), \\left(1,\\,0,\\,0\\right) : \\left(0,\\,0,\\,0,\\,0,\\,1,\\,0,\\,0\\right)\\right\\}$$" ], "text/plain": [ "{(0, 0, 0): (0, 0, 0, 0, 0, 0, 0),\n", " (1, 1, 0): (1, 0, 0, 0, 0, 0, 0),\n", " (1, 0, 1): (0, 1, 0, 0, 0, 0, 0),\n", " (0, 1, 1): (0, 0, 1, 0, 0, 0, 0),\n", " (1, 1, 1): (0, 0, 0, 1, 0, 0, 0),\n", " (0, 0, 1): (0, 0, 0, 0, 0, 0, 1),\n", " (0, 1, 0): (0, 0, 0, 0, 0, 1, 0),\n", " (1, 0, 0): (0, 0, 0, 0, 1, 0, 0)}" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "table_decodage(G4)" ] }, { "cell_type": "markdown", "id": "b98de566", "metadata": {}, "source": [ "## Décodage" ] }, { "cell_type": "code", "execution_count": 39, "id": "99d9df4e", "metadata": {}, "outputs": [], "source": [ "def decode(G,m):\n", " m=vector(F2,m)\n", " (n,k)=G.dimensions()\n", " H=matrice_controle(G)\n", " d=distance(G)\n", " ec=(d-1)/2\n", " table=table_decodage(G)\n", " s=H*m\n", " s.set_immutable()\n", " if s==0:\n", " return m[:k]\n", " else:\n", " e=table[s]\n", " if poids_Hamming(e)<=ec:\n", " m=m+e\n", " return m[:k]\n", " print(\"Correction impossible\")" ] }, { "cell_type": "code", "execution_count": 40, "id": "397a535a", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1,\\,0,\\,1,\\,0,\\,1,\\,0,\\,1,\\,0\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1,\\,0,\\,1,\\,0,\\,1,\\,0,\\,1,\\,0\\right)$$" ], "text/plain": [ "(1, 0, 1, 0, 1, 0, 1, 0)" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "decode(G1,[1,0,1,0,1,0,1,0,0])" ] }, { "cell_type": "code", "execution_count": 41, "id": "6b35fa02", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1\\right)$$" ], "text/plain": [ "(1)" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "decode(G2,[1,0,1])" ] }, { "cell_type": "code", "execution_count": 42, "id": "510c8107", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Correction impossible\n" ] } ], "source": [ "decode(G3,[1,1,0,0])" ] }, { "cell_type": "code", "execution_count": 43, "id": "23b8b24d", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\[\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1,\\,1,\\,1,\\,1\\right)\\]" ], "text/latex": [ "$$\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(1,\\,1,\\,1,\\,1\\right)$$" ], "text/plain": [ "(1, 1, 1, 1)" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "decode(G4,[1,0,1,1,1,1,1])" ] }, { "cell_type": "code", "execution_count": null, "id": "b90e7c90", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.4", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.9" } }, "nbformat": 4, "nbformat_minor": 5 }