{ "metadata": { "name": "Somme_Controle" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Somme de contr\u00f4le et transmissions de donn\u00e9es" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Probl\u00e9matique" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les \u00e9changes de donn\u00e9es num\u00e9riques sont omnipr\u00e9sentes dans notre quotidien. Lorsque l'on veut trasmettre une information par courrier \u00e9lectronique, proc\u00e9der \u00e0 une r\u00e9servation en ligne, effectuer une recherche par moteur de recherche ou m\u00eame lors de l'ex\u00e9cution de n'importe quelle t\u00e2che informatique mettant donc en jeu la m\u00e9moire RAM, des informations sont d'abord stock\u00e9es puis \u00e9mises et enfin re\u00e7ues.\n", "\n", "Comment garantir la fiabilit\u00e9 des transferts, c'est-\u00e0-dire comment s'assurer que l'information re\u00e7ue est conforme \u00e0 l'information \u00e9mise ?\n", "\n", "Le probl\u00e8me est diff\u00e9rent du probl\u00e8me de cryptographie, qui consiste \u00e0 coder des donn\u00e9es pour assurer leur confidentialit\u00e9. Dans le cas pr\u00e9sent, on veut simplement partager des donn\u00e9es publiques et optimiser les transferts en terme de garantie de l'information." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Somme de contr\u00f4le : mise en place" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il existe plusieurs principes pour tester la fiabilit\u00e9 des donn\u00e9es transmises, orincipes plus ou moins compliqu\u00e9s et performants.\n", "\n", "On appelle **somme de contr\u00f4le** (en anglais *checksum*) la quantit\u00e9 ajout\u00e9e \u00e0 l'information (cette quantit\u00e9 est aussi appel\u00e9e *empreinte*) pour ensuite la traiter.\n", "\n", "L'id\u00e9e commune est de modifier l'information de d\u00e9part, avant son transfert en lui ajoutant d'autres informations qui pourront par la suite \u00eatre interpr\u00e9t\u00e9es pour redonner un message et surtout tester si il y a eu une erreur lors de la transmission." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Le bit de parit\u00e9" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Le bit de parit\u00e9 : \u00e9mission du message" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consid\u00e9rons une information \u00e0 transmettre. Comme toutes les donn\u00e9es num\u00e9riques, celle-ci est codable en **bits** de $0$ et de $1$. On le voit ais\u00e9ment \u00e0 travers le code **ASCII** pouvant coder sur huit bits, donc sur un **octet** $2^8=256$ objets diff\u00e9rents, ces objets \u00e9tant ici des symboles alphanum\u00e9riques.\n", "\n", "Voici le principe de contr\u00f4le par un bit de parit\u00e9.\n", "\n", "L'information \u00e0 transmettre est donc une liste de $0$ et de $1$.\n", "\n", "On partage cette liste en octets, par tranches de $8$ bits, quitte \u00e0 laisser \u00e0 la fin un octet partiel non totalement remplie que l'on remplit alors de $0$.\n", "\n", "A chaque tranche de huit bits, on compte le nombre de $1$ par tranche et on ajoute une $0$ ou un $1$ en plus de fa\u00e7on que dans chaque tranche de maintenant neuf bits figure un nombre pair de $1$. Le bit rajout\u00e9 \u00e0 chaque tranche s'appelle le **bit de parit\u00e9**.\n", "\n", "Ainsi, le message :\n", "\n", "100011100010100101000010110\n", "\n", "deviendra \n", "\n", "10001110 00101001 01000010 11000000\n", "\n", "pour avoir finalement quatre octets de codage.\n", "\n", "On ajoute \u00e0 chaque tranche le **bit de parit\u00e9**, ce qui donne :\n", "\n", "10001110 0 00101001 1 01000010 0 11000000 0\n", "\n", "On transmet finalement un message avec plus de bits de codage qu'avant." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voici un script Python permettant de trouver et d'incorporer dans un message binaire les bits de parit\u00e9 :" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def Bit_Parite(L) :\n", " L_Temp=[int(x) for x in L]\n", " n=len(L)\n", " r=n%8\n", " L_Temp.extend([0 for k in range((8-r)*int(r!=0))])\n", " ## on rajoute (8-r) z\u00e9ros si r non nul et aucun z\u00e9ros si r nul\n", " L_Parite=[]\n", " for k in range(len(L_Temp)//8) :\n", " Tranche=L_Temp[8*k:8*(k+1)].copy()\n", " L_Parite.extend(Tranche)\n", " L_Parite.extend([\" \",len([x for x in Tranche if x==1])%2,\" \"])\n", " \n", " Chaine_Recalib,Chaine_Fin=\"\",\"\"\n", " for x in L_Temp :\n", " Chaine_Recalib=Chaine_Recalib+str(x)\n", " for x in L_Parite[:-1] :\n", " Chaine_Fin=Chaine_Fin+str(x)\n", " return [Chaine_Recalib,Chaine_Fin ] " ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 11 }, { "cell_type": "code", "collapsed": false, "input": [ "\n", "L=\"101110010110100101000101101011111\"\n", "Res=Bit_Parite(L)\n", "print(\"Message initial :\")\n", "print(L)\n", "print(\"Message recalibr\u00e9 par octet :\")\n", "print(Res[0])\n", "print(\"Message transform\u00e9 par ajout de bits de parit\u00e9 :\")\n", "print(Res[1])" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Message initial :\n", "101110010110100101000101101011111\n", "Message recalibr\u00e9 par octet :\n", "1011100101101001010001011010111110000000\n", "Message transform\u00e9 par ajout de bits de parit\u00e9 :\n", "10111001 1 01101001 0 01000101 1 10101111 0 10000000 1\n" ] } ], "prompt_number": 12 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Le bit de parit\u00e9 : r\u00e9ception du message" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Imaginons que l'on re\u00e7oive un message de la forme suivante, en sachant qu'il a fait l'objet d'une somme de contr\u00f4le par bits de parit\u00e9 par tranche d'octets :\n", "\n", "110001010001001001001001010010011110\n", "\n", "Pour retrouver le message initial, on aura d\u00e9j\u00e0 un nombre de bits multiple de $9$. On d\u00e9coupe par tranches de neuf bits :\n", "\n", "110001010 001001001 001001010 010011110\n", "\n", "Ensuite, on supprime le dernier bit de chaque tranche, ce qui donne la cha\u00eene suivante :\n", "\n", "11000101 00100100 00100101 01001111\n", "\n", "et finalement le message d'origine :\n", "\n", "11000101001001000010010101001111\n", "\n", "On peut remarquer que le message d'origine \u00e9tait stock\u00e9 exactement sur quatre octets car le message fini par un $1$, donc n'a pas fait l'objet d'une compl\u00e9tion par des $0$.\n", "\n", "Cependant, comment peut-on exploiter les bits de chaque tranche supprim\u00e9 ? Il s'agit de calculer la parit\u00e9 du nombre de $1$ par tranches de neuf bits dans le message re\u00e7u.\n", "\n", "La premi\u00e8re tranche comporte quatre $1$, ce qui est conforme \u00e0 l'utilit\u00e9 du bit de parit\u00e9.\n", "\n", "Seules les troisi\u00e8me et quatri\u00e8me tranches comportent un nombre impair de $1$ : il y a eu une erreur de transmission au moins pour ces tranches.\n", "\n", "Le message re\u00e7u n'est en fait pas le message d'origine, avec probablement deux erreurs (au moins) situ\u00e9es plut\u00f4t dans le seconde moiti\u00e9 du message. \n", "\n", "Quelles sont les erreurs commises ? \n", "\n", "On ne peut pas le savoir avec le peu de renseignements dont on dispose.\n", "\n", "Y a-t-il eu seulement deux erreurs de bits ?\n", "\n", "On ne peut pas non plus l'assurer, comme le t\u00e9moigne l'exemple suivant :\n", "\n", "message re\u00e7u :\n", "\n", "101010100\n", "\n", "message interpr\u00e9t\u00e9 d'origine :\n", "\n", "10101010\n", "\n", "message r\u00e9el d'origine :\n", "\n", "01010101\n", "\n", "Il y a eu seulement un d\u00e9calage des donn\u00e9es, ce d\u00e9calage passant finalement inaper\u00e7u par le test de contr\u00f4le de parit\u00e9. Ce d\u00e9calage engendre finalement beaucoup d'erreurs de transmission, alors que le bit de parti\u00e9 indiquerait plut\u00f4t une transmission fiable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Examinons maintenant d'autres syst\u00e8mes de sommes de contr\u00f4le." ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Le code de Hamming" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Code correcteur, fonction d'encodage" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On note $\\mathbb{F}_2$ le corps fini $\\mathbb{Z}/2\\mathbb{Z}$.\n", "\n", "Chaque bit d'information est cod\u00e9 par un $0$ ou un $1$, donc chaque bit d'information est en fait un \u00e9l\u00e9ment de $\\mathbb{F}_2$.\n", "\n", "Soient $k\\leq n$ deux entiers strictement positifs. On note :\n", "\n", "$\\quad$ $\\rhd$ $E=\\mathbb{F}_2^k$\n", "\n", "$\\quad$ $\\rhd$ $F=\\mathbb{F}_2^n$\n", "\n", "de sorte que les ensembles $E$ et $F$ sont des $\\mathbb{F}_2$-espaces vectoriels de dimensions respectives $k$ et $n$.\n", "\n", "On appelle **code correcteur** sur l'alphabet $\\mathbb{F}_2$, toute application $\\varphi:E\\to F$ injective.\n", "\n", "En pratique, si $\\vec{x}$ est un \u00e9l\u00e9ment de $E$ correspondant \u00e0 un message d'information de longueur $k$, alors $\\varphi(\\vec{x})=\\vec{y}$ est le message **encod\u00e9** \u00e0 partir du message $\\vec{x}$.\n", "\n", "A partir de la donn\u00e9e du message encod\u00e9 $\\vec{y}$, on peut retrouver par injectivit\u00e9 toute l'information du message initial $\\vec{x}$. Souvent, les composantes de $\\vec{x}$ sont pr\u00e9sentes dans les composantes de $\\vec{y}$, et les $(n-k)$ composantes suppl\u00e9mentaires dans $\\vec{y}$ forment ce qu'on appelle la **redondance**.\n", "\n", "\n", "La fonction $\\varphi$ est aussi appel\u00e9e la fonction d'**encodage**.\n", "\n", "On dit que le code est **lin\u00e9aire** si l'application $\\varphi$ est $\\mathbb{F}_2$-lin\u00e9aire (c'est-\u00e0-dire lin\u00e9aire sur le corps $\\mathbb{F}_2$). \n", "\n", "On rappelle que l'application $\\varphi$ appartient \u00e0 ${\\cal L}(E)$, o\u00f9 $E$ et $F$ sont des $\\mathbb{F}_2$-espaces vectoriels si : $\\forall (\\vec{u},\\vec{v})\\in E^2$, $\\varphi(\\vec{u}+\\vec{v})=\\varphi(\\vec{u})+\\varphi(\\vec{v})$.\n", "\n" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Distance sur $\\mathbb{F}_2^q$ et boules" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $q$ dans $\\mathbb{N}^*$. On pose ${\\cal E}$ l'espace vectoriel $E=\\mathbb{F}_2^q$.\n", "\n", "L'application $\\delta:{\\cal E}^2\\mapsto \\mathbb{R}$ telle que : $\\forall (\\vec{u},\\vec{v})\\in {\\cal E}^2$, $\\delta(\\vec{u},\\vec{v})={\\rm Card}(\\lbrace i\\in\\lbrace 1,\\cdots,q\\rbrace~|~\\vec{u}_i\\neq \\vec{v}_i\\rbrace)$ est une **distance** car :\n", "\n", "$\\qquad$ $\\rhd$ $\\delta$ prend ses valeurs dans $[0,+\\infty[$ (en fait dans $\\mathbb{N}$)\n", "\n", "$\\qquad$ $\\rhd$ l'assertion $\\delta(\\vec{u},\\vec{v})=0$ est \u00e9quivalente \u00e0 $\\vec{u}=\\vec{v}$\n", "\n", "$\\qquad$ $\\rhd$ on a l'in\u00e9galit\u00e9 triangulaire : $\\delta(\\vec{u},\\vec{w})\\leq \\delta(\\vec{u},\\vec{v})+\\delta(\\vec{v},\\vec{w})$, car en notant $A$, $B$ et $C$ respectivement les ensembles d'indices $i$ tels que $u_i\\neq v_i$, tels que $v_i\\neq w_i$ et tels que $u_i\\neq w_i$, alors on a clairement $\\overline{A}\\cap \\overline{B}\\subset \\overline{C}$.\n", "\n", "En prenant les cardinaux, on obtient :\n", "\n", "$\\qquad$ $q-\\delta(\\vec{u},\\vec{w})={\\rm Card}(\\overline{C})\\geq {\\rm Card}(\\overline{A}\\cap \\overline{B})={\\rm Card}(\\overline{A})+{\\rm Card}(\\overline{B})-{\\rm Card}(\\overline{A}\\cup \\overline{B})\\geq q-\\delta(\\vec{u},\\vec{v})+q-\\delta(\\vec{v},\\vec{w})-q$,\n", "\n", "puis ce qu'il faut.\n", "\n", "On peut d\u00e8s lors d\u00e9finir les **boules ferm\u00e9es** : la boule ferm\u00e9e de centre $\\vec{c}$ et de rayon $r\\geq 0$ est l'ensemble :\n", "\n", "$\\qquad$ $\\lbrace \\vec{u}\\in {\\cal E}~|~\\delta(\\vec{c},\\vec{u})\\leq r\\rbrace$.\n", "\n", "La distance entre deux vecteurs est donc le nombre de composantes diff\u00e9rentes entre ces vecteurs.\n", "\n", "\n", "On remarque ainsi que la boule de rayon $1$ et de centre $\\vec{c}$ est exactement form\u00e9e des vecteurs $\\vec{u}$ o\u00f9 au maximum une seule composante a \u00e9t\u00e9 modifi\u00e9e par rapport \u00e0 $\\vec{c}$. Toutes les boules de rayon $1$ dans l'espace ${\\cal E}=\\mathbb{F}_2^q$ sont donc de cardinal $1+q$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Capacit\u00e9 corrective d'un code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $\\varphi:E\\to F$ un code correcteur, c'est-\u00e0-dire une application injective entre duex espaces vectoriels $E=\\mathbb{F}_2^k$ et $F=\\mathbb{F}_2^n$.\n", "\n", "Soit $t\\in\\mathbb{N}^*$.\n", "\n", "On dispose de la distance $\\delta$ sur l'espace $F$, pour lesquelles les boules ferm\u00e9es de rayon $1$ compte exactement $1+n$ \u00e9l\u00e9ments. Dans toute la suite, pour tout vecteur $\\vec{v}$ de $F$, on note $B(\\vec{v},1)$ la boule ferm\u00e9e de centre $\\vec{v}$ et de rayon $1$.\n", "\n", "On dit que le code $\\varphi$ a une **capacit\u00e9 corrective \u00e9gale \u00e0 $t$** si l'entier $t$ est le plus grand entier v\u00e9rifiant la propri\u00e9t\u00e9 suivante :\n", "\n", "$\\qquad$ lorsque $\\vec{u}$ varie dans $E$, les boules ferm\u00e9es $B(\\varphi(\\vec{u}),t)$ sont disjointes les unes des autres dans l'espace $F$.\n", "\n", "En pratique, les \u00e9l\u00e9ments $\\vec{u}$ de $E$ correspondent \u00e0 l'information \u00e9mise sur $k$ bits et les vecteurs $\\varphi(\\vec{u})$ correspondent \u00e0 l'information re\u00e7ue avec la redondance due \u00e0 la somme de contr\u00f4le des $(n_k)$ bits suppl\u00e9mentaires.\n", "\n", "Lorsque le r\u00e9cepteur re\u00e7oit une information, il n'est pas toujours oblig\u00e9 que le vecteur re\u00e7u $\\vec{v} \\in F$ appartienne \u00e0 l'image ${\\rm Im}(\\varphi)$. Ceci est le cas lorsque par exemple il n'y a eu aucune erreur lors du transfert. Il se peut parfois que certains transistors (composants \u00e9lectroniques dont on ne peut assurer la fiabilit\u00e9 \u00e0 $100\\%$ \u00e9changent un $0$ ou un $1$ avec un $1$ ou un $0$. Dans ce cas, le vecteur $\\vec{v}$ peut ne pas appartenir \u00e0 l'image de l'application $\\varphi$.\n", "\n", "On part alors du principe que le vecteur \u00e9mis $\\vec{u}$ est celui pour lequel il y a eu le moins d'erreurs possibles lors du transfert. Ainsi, en ayant re\u00e7u le vecteur $\\vec{v}$, on consid\u00e8re que le vecteur \u00e9mis $\\vec{u}$ est un vecteur de $E$ pour lequel la distance $\\delta(\\vec{v},\\varphi(\\vec{u}))$ est minimale.\n", "\n", "Lorsque le code $\\varphi$ a une capacti\u00e9 corrective \u00e9gale \u00e0 $t$, alors on peut retrouver sans faille le message d'origine \u00e0 condition que le transfert d'information n'ait occasionn\u00e9 un nombre d'erreurs inf\u00e9rieur ou \u00e9gal \u00e0 $t$. Dans ce cas, il n'y aura qu'un seul vecteur $\\vec{u}$ dans $E$ tel que $\\delta(\\varphi(\\vec{u}),\\vec{v})\\leq t$, car si il y avait un second vecteur possible $\\vec{w}$, alors les boules $B(\\varphi(\\vec{u},t))$ et $B(\\varphi(\\vec{w}),t))$ ne seraient pas disjointes car contiendraient le vecteur re\u00e7u $\\vec{v}$.\n" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Distance minimale d'un code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $\\varphi:E\\to F$ un code correcteur.\n", "\n", "On dit que le code $\\varphi$ a une **distance minimale \u00e9gale \u00e0 $\\delta_0$** si :\n", "\n", "$\\qquad$ $\\delta_0=\\min\\lbrace \\delta(\\varphi(\\vec{u}),\\varphi(\\vec{v}))\\in\\mathbb{N}~;~\\vec{u}\\neq \\vec{v} \\mbox{ dans }E\\rbrace$.\n", "\n", "Par injectivit\u00e9 de l'application $\\varphi$, on sait que tout code correcteur a une distance minimale strictement positive.\n", "\n", "Il s'agit du nombre minimal de composantes diff\u00e9rentes entre deux messages cod\u00e9s diff\u00e9rents." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Lien entre capacit\u00e9 corrective et distance minimale" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec les notations d\u00e9j\u00e0 utilis\u00e9es, on dispose de la propri\u00e9t\u00e9 suivante :\n", "\n", "$\\qquad$ la capacit\u00e9 corrective $t$ d'un code est le plus grand entier strictement inf\u00e9rieur \u00e0 $\\displaystyle \\frac{\\delta_0}{2}$, o\u00f9 $\\delta_0$ est la distance minimale du code.\n", "\n", "Voici la d\u00e9monstration :\n", "\n", " $\\bullet$ on note $\\tau$ le plus grand entier strictement inf\u00e9rieur \u00e0 $\\displaystyle \\frac{\\delta_0}{2}$\n", "\n", "$\\bullet$ si $k=t+1$, il existe par maximalit\u00e9 de $t$ deux boules ferm\u00e9es $B(\\varphi(\\vec{u}),k)$ et $B(\\varphi(\\vec{v}),k)$ diff\u00e9rentes et non disjointes. On choisit $\\vec{w}$ un vecteur dans leur intersection. On en d\u00e9duit par in\u00e9galit\u00e9 triangulaire :\n", "\n", "$\\qquad$ $\\delta(\\varphi(\\vec{u}),\\varphi(\\vec{v})\\leq \\delta(\\varphi(\\vec{u}),\\vec{w})+\\delta(\\vec{w},\\varphi(\\vec{v}))\\leq 2~k$\n", "\n", "Ainsi, l'entier $2~k$ doit \u00eatre sup\u00e9rieur ou \u00e9gal \u00e0 $\\delta_0$ ce qui impose $\\displaystyle k\\geq \\frac{\\delta_0}{2}> \\tau$.\n", "\n", "L'in\u00e9galit\u00e9 $t+1>\\tau$ am\u00e8ne alors la premi\u00e8re in\u00e9galit\u00e9 : $t\\geq \\tau$.\n", "\n", "$\\bullet$ l'entier $T=\\tau+1$ v\u00e9rifie : $\\displaystyle T\\geq \\frac{\\delta_0}{2}$. Par minimalit\u00e9 de $\\delta_0$, on trouve deux vecteurs diff\u00e9rents $\\vec{u}$ et $\\vec{v}$ dans $E$ tels que : $\\delta(\\varphi(\\vec{u}),\\varphi(\\vec{v}))=\\delta_0$.\n", "\n", "On pose $\\vec{U}=\\varphi(\\vec{u})$ et $\\vec{V}=\\varphi(\\vec{v})$. On va montrer que les boules ferm\u00e9es $B(\\vec{U},T)$ et $B(\\vec{V},T)$ ne sont pas disjointes.\n", "\n", "En effet, les vecteurs $\\vec{U}$ et $\\vec{V}$ comportent chacun $n$ composantes et il y a exactement $\\delta_0$ composantes diff\u00e9rentes entre ces deux vecteurs.\n", "\n", "On distingue deux cas :\n", "\n", "$\\qquad$ $\\qquad$ $\\rhd$ **premier cas** : l'entier $\\delta_0$ est pair \u00e9gal \u00e0 $\\delta_0=2~s$. Alors, $T=s$ car $\\tau=s-1$. On note $I$ l'ensemble des indices $i$ entre $1$ et $q$ tels que $\\vec{U}_i=\\vec{V}_i$. On choisit dans $\\lbrace 1,\\cdots,n\\rbrace \\setminus I$ une partie $J$ de cardinal $s$ et on pose le vecteur $\\vec{W}$ tel que $\\vec{W}_i=\\vec{U}_i$ si $i \\notin J$ et $\\vec{W}_i=\\vec{U}_i+1$ si $i\\in J$. Les vecteurs $\\vec{U}$ et $\\vec{W}$ ont exactement $s$ composantes diff\u00e9rentes et les vecteurs $\\vec{W}$ et $ \\vec{V}$ \u00e9galement (pour tous les indices de $\\lbrace 1,\\cdots,n\\rbrace \\setminus (I\\cup J)$ \u00e9galement de cardinal $s$).\n", "\n", "Les deux boules ferm\u00e9es contiennent $\\vec{W}$ (elles sont en fait tangentes en $\\binom{2~s}{s}$ \u00e9l\u00e9ments).\n", "\n", "$\\qquad$ $\\qquad$ $\\rhd$ **second cas** : l'entier $\\delta_0$ est impair \u00e9gal \u00e0 $\\delta_0=2~s+1$. Alors $\\tau=s$ et $T=s+1$. ON choisit parmi les $2~s+1$ composantes diff\u00e9rentes entre $\\vec{U}$ et $\\vec{V}$, un ensemble de composantes de cardinal $s$ et on modifie pour ces $s$ indices, les composantes du vecteur $\\vec{U}$ pour obtenir un vecteur $\\vec{W}$ tel que $\\delta_0(\\vec{U},\\vec{W})=s$. On en d\u00e9duit $\\delta_0(\\vec{V},\\vec{W})=s+1$ et les boules $B(\\vec{U},T)$ et $B(\\vec{V},T)$ ne sont pas disjointes.\n", "\n", "En conclusion, dans tous les cas, l'entier $T$ est strictement sup\u00e9rieur \u00e0 $t$, ce qui d\u00e9montre l'in\u00e9galit\u00e9 inverse : $\\tau\\geq t$, et finalement l'\u00e9galit\u00e9 $t=\\tau$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "In\u00e9galit\u00e9 de Hamming pour une capacit\u00e9 corrective \u00e9gale \u00e0 $1$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On se place ici dans le cas d'un code $\\varphi:\\mathbb{F}_2^k\\to \\mathbb{F}_2^n$, avec une distance minimale \u00e9gale \u00e0 $\\delta_0=3$ et donc une capacit\u00e9 corrective \u00e9gale \u00e0 $t=1$. Il s'agit d'un code pouvant corriger une erreur de transmission.\n", "\n", "Les boules $B(\\varphi(\\vec{u}),1)$ sont disjointes lorsque le vecteur $\\vec{u}$ d\u00e9crit $E=\\mathbb{F}_2^k$. En calculant le cardinal de cette r\u00e9union disjointes de boules, on obtient l'in\u00e9galit\u00e9 suivante :\n", "\n", "$\\qquad$ $\\qquad$ $2^k\\times (1+n)\\leq 2^n=\\{\\rm Card}(F)$\n", "\n", "et donc : $1+n\\leq 2^{n-k}$.\n", "\n", "Cette in\u00e9galit\u00e9 porte le nom d'in\u00e9galit\u00e9 de Hamming" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Code parfait de distance minimale \u00e9gale \u00e0 $3$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On dit qu'un code $\\varphi:E=\\mathbb{F}_2^k\\to F=\\mathbb{F}_2^n$ de distance minimale \u00e9gale \u00e0 $3$ est **parfait** si :\n", "\n", "$\\qquad $ $1+n=2^{n-k}$.\n", "\n", "Cela signifie que les boules $B(\\varphi(\\vec{u}),1)$ lorsque $\\vec{u}$ d\u00e9crit $E$ forment une partition de l'ensemble $F$. \n", "\n", "Cela signifie \u00e9galement que le cardinal de la r\u00e9union de ces boules ferm\u00e9es de rayon $1$ est \u00e9gal \u00e0 $2^n$. Ceci sera un moyen commode d\u00e9 v\u00e9rifier qu'on a affaire \u00e0 un code parfait.\n", "\n", "Lorsque l'on a affaire \u00e0 un code parfait, les boules de centre $\\varphi(\\vec{u})$ et de rayon $1$ lorsque $\\vec{u}$ varie dans $E$ forment une partition de l'ensemble $F$. Autrement dit, la transmission ne produit jamais plus d'une alt\u00e9ration du message initial. \n", "\n", "Dans le cas d'un code parfait, s'il y a erreur de transmission sur un message vectoris\u00e9 $\\vec{u}$, il n'y aura qu'une seule composante $u_i$ \u00e0 modifier. Etant donn\u00e9 un message re\u00e7u $\\vec{w}$, ce vecteur $\\vec{w}$ appartiendra \u00e0 une seul boule de la partition, boule de centre $\\varphi(\\vec{u})$ et on pourra assurer que le message \u00e9mis \u00e9tait le vecteur $\\vec{u}$." ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Codes de Hamming $[n,k,3]$ ou $(n,k)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On dit qu'un code correcteur $\\varphi:E=\\mathbb{F}_2^k\\to F=\\mathbb{F}_2^n$ est un **code de Hamming** si les conditions suivantes sont r\u00e9alis\u00e9es :\n", "\n", "$\\quad$ $\\longrightarrow$ l'application $\\varphi$ est lin\u00e9aire et injective\n", "\n", "$\\quad$ $\\longrightarrow$ l'application $\\varphi$ est de distance minimale \u00e9gale \u00e0 $3$ ou de mani\u00e8re \u00e9quivalente, le code correcteur a une capacit\u00e9 corrective \u00e9gale \u00e0 $1$\n", "\n", "$\\quad$ $\\longrightarrow$ le code $\\varphi$ est parfait, c'est-\u00e0-dire que : $1+n=2^{n-k}$.\n", "\n", "Habituellement, un tel code est not\u00e9 $[n,k,3]$ ou plus simplement $(n,k)$, car on peut montrer qu'\u00e0 isomorphisme pr\u00e8s, il n'existe qu'un seul code de Hamming de param\u00e8tres $(n,k)$.\n", "\n", "Voici la liste de tous les codes de Hamming : ce sont les codes de param\u00e8tres $(2^q-1,2^q-q-1)$, lorsque $q$ d\u00e9crit $\\mathbb{N}^*$. Ceci se montre facilement que l'entier $n$ est n\u00e9cessairement de la forme $2^q-1$, avec $q=n-k$ :" ] }, { "cell_type": "code", "collapsed": false, "input": [ "def Codes_Hamming(N) :\n", " \"\"\" retourne la liste de tous les codes de Hamming avec n inf\u00e9rieur ou \u00e9gal \u00e0 N \"\"\"\n", " L=[]\n", " q=2\n", " while 2**q-1