Décodage des codes BCH

Approximants de Padé

Introduction : approximation rationnelle

Pour représenter une valeur numérique, on passe par des approximations rationnelles. On peut

  • écrire un développement binaire ou décimal

    \[\pi \approx 3.1415926535...\]

    ce qui correspond à prendre des fractions de dénominateur fixé \(10^n\)

    \[\pi \approx \frac{31415926535}{10^{10}}\]

  • autoriser des dénominateurs quelconques, par exemple

    \[\begin{cases} \pi \approx &\frac{22}7 = 3.142... \\ \pi \approx &\frac{315}{113} = 3.1415922... \end{cases}\]

Cette représentation est souvent beaucoup plus économique, car il existe des fractions qui approximent très bien la valeur.

C’est également très utile dans le cas où on cherche à approcher une grandeur en minimisant le dénominateur :

  • en horlogerie, les rapports se traduisent en engrenages, on veut minimisant le nombre de dents

  • en musique, pour mettre une quinte juste et une octave dans une gamme tempérée on doit exprimer le rapport de fréquences \(\alpha = \log(3)/\log(2)\) comme multiple d’un intervalle de base. On obtient

    • \(\alpha\approx \frac{8}5\) : gamme à 5 tons

    • \(\alpha\approx \frac{19}{12}\) : 12 demi-tons de la gamme tempérée usuelle

    • \(\alpha\approx \frac{84}{53}\) : 53 commas du piano

Avec des fractions quelconques le travail arithmétique sur les expressions devient compliqué (additionner des fractions, les dénominateurs explosent..).

Pour calculer une réduite sous forme de fraction, on a deux techniques très simples :

  • l’algorithme des fractions continues, à partir d’un développement décimal

  • la simplification des fractions par l’algorithme d’Euclide.

Partons de l’approximation \(\pi\approx \frac{314}{100}\), et cherchons à remplacer cette fraction par une autre fraction beaucoup plus simple.

Une relation de Bezout entre \(314\) et \(100\) donne

\[314\times 7 - 100 \times 22 = -2\]

d’où

\[\frac{314}{100}-\frac{22}{7} = -\frac{2}{700}\]

La fraction \(\frac{22}7\) est une excellente approximation de \(\frac{314}{100}\), et donc de \(\pi\).

Plus généralement, on cherche \(\frac{3141592}{10^6}-\frac{v}{u}=\epsilon\), on écrit l’algorithme d’Euclide

\[3141592 u_k + 10^6 v_k = r_k\]
A = [3141592,1,0;10^6,0,1]
A=[0,1;1,-(A[1,1]\A[2,1])]*A \\ lancer plusieurs fois

On obtient les lignes:

[141592  1 -3]
[8856  -7   22]
[8752 106 -333]
[104 -113    355]
[ 16 9598 -30153]

La ligne la plus intéressante est celle pour laquelle tous les termes sont à peu près de la même taille

\[-3141592\times 113 + 10^6\times 355 = 104\]

Qui donne \(\frac{3141592}{10^6}-\frac{355}{113}=\frac{104}{113\times 10^6}\).

On en déduit, puisque \(\abs{\pi-\frac{3141592}{10^6}}\leq 10^{-6}\), que

\[\abs{\pi - \frac{355}{113}} \leq \frac{2}{10^6}.\]

C’est une excellente approximation, le dénominateur a moitié moins de chiffres que le dénominateur initial \(10^6\).

De manière générale, cette technique permet

  • en partant de \(2n\) chiffres d’une valeur \(\alpha\)

  • d’obtenir une fraction dont le dénominateur a moins de \(n\) chiffres

  • et qui approxime \(\alpha\) à \(10^{-n}\).

Le cas des polynômes

Padé

Soit \(A\in\F_q[x]\) un polynôme de degré \(n+1\), et \(B\in\F_q[x]\) de degré \(\leq n\). Alors pour tout \(1\leq k\leq n\), il existe deux polynômes \(R,V\neq 0,0\) tels que \(\deg(R)\leq k\), \(\deg(V)\leq n-k\), et

\[BV\equiv R\bmod A.\]

De plus, le quotient \(R/V\) est unique.

Démonstration

Existence : les coefficients de \(V\) et \(R\) sont solution d’un système linéaire à \(n+1\) équations et \((n-k+1)+(k+1)=n+2\) inconnues, il y a donc une solution non nulle.

Unicité : si \(R,V\) et \(R',V'\) sont deux solutions, alors \(BVV'-BV'V=RV'-R'V=0\bmod A\), avec \(\deg(A)=n+1\) et \(\deg(RV'-R'V)\leq n\), donc \(RV'=RV\) et la fraction est bien unique.

Le couple \((R,V)\) est appelé \((k,n-k)\)-approximant de Padé de \(B\) modulo \(A\).

On peut le déterminer en \(O(n^3)\) opérations en résolvant le système linéaire qui le définit. Une meilleure méthode consiste à l’obtenir lors de l’algorithme d’Euclide étendu.

Proposition

Soient \(A\) et \(B\) comme ci-dessus. On effectue l’algorithme d’Euclide étendu

\[AU_j+BV_j=R_j\]

Alors il existe \(j\) tel que \(\deg(V_j)\leq n-k\) et \(\deg(R_j)\leq k\).

Démonstration

La suite \(\deg(R_j)\) est décroissante. Soit donc \(j\) l’indice tel que \(\deg(R_{j-1})>k\geq \deg(R_j)\). Alors d’après le lemme ci-dessous, on a \(\deg(V_j)< n+1-k\), d’où le résultat.

Lemme

Au cours de l’algorithme d’Euclide étendu étendu, on a

\[\deg A = \deg V_j + \deg R_{j-1}.\]

Démonstration

On a \(A=R_0\) et puisque la suite \(\deg R_k\) est strictement décroissante \(\deg R_{k-1} = \deg Q_k+\deg R_k\), d’où

\[\deg A = \deg Q_1+\dots \deg Q_{k-1}+\deg R_{k-1}.\]

De même, \(V_0=0\), \(V_1=1\), puis la suite \(\deg V_k\) est strictement croissante et \(\deg Q_k+\deg V_k = \deg V_{k+1}\), d’où

\[\deg V_k= \deg Q_{k_1}+\dots Q_{1}.\]

Ce qui conclut.

Décodage des codes BCH

Soit \(C\) un code BCH de distance prévue \(\delta=2t+1\), et \(\alpha\) tel que

\[c(x)\in C \Leftrightarrow \forall 0\leq i\lt 2t, c(\alpha^{a+i})=0\]

Soit \(c(x)\) le mot transmis, et \(y(x) = c(x)+e(x)\) le mot reçu, où l’on écrit \(e(x)=\sum_{i\in T}e_ix^i\), avec \(\card T\leq t\).

On définit alors le polynôme syndrome

\[S(x) = \sum_{l=0}^{2t-1} y(\alpha^{a+l})x^{l}\]

ainsi que le polynôme localisateur de l’erreur

\[E(x) = \prod_{i\in T} (1-\alpha^ix)\]

Si l’on calcule \(S(x)\) en fonction de l’erreur, on a

\[\begin{aligned} S(x) &= \sum_{l=0}^{2t-1} e(\alpha^{a+l})x^{l} \\ &= \sum_{l=0}^{2t-1} \sum_{i\in T}e_i \alpha^{i(a+l)}x^{l} \\ &= \sum_{i\in T} e_i\alpha^{ia} \sum_{l=0}^{2t-1} (\alpha^{i}x)^{l} \\ &= \sum_{i\in T} e_i\alpha^{ia} \frac{1-(\alpha^{i}x)^{2t}}{1-\alpha^{i}x} \end{aligned}\]

On note

\[R(x) = \sum_{i\in T} e_i\alpha^{ia} \prod_{j\in T\setminus i} (1-\alpha^j x)\]

de sorte que \(S,E\) et \(R\) satisfont l’équation de Padé

\[S(x)E(x) \equiv R(x) \bmod x^{2t}.\]

Par hypothèse, les degrés satisfont les conditions, de sorte que la solution est unique.

Les racines de \(E(X)\) donnent les indices des erreurs, dont on peut déterminer la valeur via la formule

\[e_k = -\frac{R(\alpha^{-k})}{E'(\alpha^{-k})}.\]

Démonstration

On vérifie simplement : pour \(k\in T\)

\[\begin{aligned} R(\alpha^{-k}) &= \sum_{i\in T} e_i\alpha^i \prod_{j\in T\setminus i} (1-\alpha^{j-k}) \\ &= e_k\alpha^k \prod_{j\in T\setminus k} (1-\alpha^{j-k}) \end{aligned}\]

et

\[\begin{aligned} E'(\alpha^{-k}) &= \sum_{i\in T} -\alpha^i \prod_{j\in T\setminus i} (1-\alpha^{j-k}) \\ &= -\alpha^k \prod_{j\in T\setminus k} (1-\alpha^{j-k}) \end{aligned}\]

Décodage des codes de Reed-Solomon

C’est un cas particulier, les calculs se font dans \(\F_q\) ce qui est agréable.

On peut également poser directement le problème du décodage sur la présentation en termes d’évaluation :

Soient \(a_1,\dots a_n\) dans \(\F_q\), et \(C\) le code d’évaluation aux points \(a_i\).

Soit \(c(x)\) de degré \(<k\) le mot envoyé, et \(y(x)\) de degré \(<n\) le mot reçu. On pose \(T=\set{i, y(a_i)\neq c(a_i)}\), et on pose \(e(x)=\prod_{i\in T} (x-a_i)\), de sorte que

\[\forall i, c(a_i)e(a_i) = y(a_i)e(a_i).\]

Si l’on définit \(r(x) = c(x)e(x)\) et \(A(x)=\prod_{1\leq i\leq n} (x-a_i)\), on a donc la relation

\[y(x)e(x)\equiv r(x)\bmod A(x),\]

où

\[\deg(y(x))\lt n \\ \deg(e(x))\leq t \\ \deg(r(x))\lt k+t \\ \deg(A(x))=n\]

On résout donc par approximation de Padé.