Décodage généralisé à distance minimale

En théorie du codage , le décodage à distance minimale généralisée (GMD) fournit un algorithme efficace pour décoder les codes concaténés , basé sur l'utilisation d'un décodeur d'erreurs et d'effacements pour le code externe .

Un algorithme de décodage naïf pour les codes concaténés ne peut être optimal car il ne tient pas compte des informations fournies par le décodage par maximum de vraisemblance (MLD). Autrement dit, dans cet algorithme naïf, les mots de code internes reçus sont traités de la même manière, indépendamment de la différence entre leurs distances de Hamming . Intuitivement, le décodeur externe devrait accorder plus de confiance aux symboles dont les codages internes sont proches du mot reçu. En 1966, David Forney a conçu un algorithme plus performant, appelé décodage par distance minimale généralisée (GMD), qui exploite mieux ces informations. Cette méthode consiste à mesurer la confiance de chaque mot de code reçu et à supprimer les symboles dont la confiance est inférieure à une valeur cible. L'algorithme de décodage GMD fut l'un des premiers exemples de décodeurs à décision souple . Nous présenterons trois versions de cet algorithme : les deux premières sont des algorithmes randomisés et la dernière est un algorithme déterministe .

Installation

Distance de Hamming : Étant donné deux vecteurs ${\displaystyle u,v\in \Sigma ^{n <semantics><mrow><mstyle><mi>vous</mi><mo>,</mo><mi>v</mi><mo>∈</mo><msup><mi>Σ</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle u,v\in \Sigma ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle u <semantics><mrow><mstyle><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle u}</annotation></semantics></math><img src=$ ${\displaystyle v <semantics><mrow><mstyle><mi>v</mi></mstyle></mrow><annotation>{\displaystyle v}</annotation></semantics></math><img src=$ ${\displaystyle \Delta (u,v) <semantics><mrow><mstyle><mi>Δ</mi><mo>(</mo><mi>vous</mi><mo>,</mo><mi>v</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \Delta (u,v)}</annotation></semantics></math><img src=$ ${\displaystyle u <semantics><mrow><mstyle><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle u}</annotation></semantics></math><img src=$ ${\displaystyle v <semantics><mrow><mstyle><mi>v</mi></mstyle></mrow><annotation>{\displaystyle v}</annotation></semantics></math><img src=$
Distance minimale : Soit ${\displaystyle C\subseteq \Sigma ^{n <semantics><mrow><mstyle><mi>C</mi><mo>⊆</mo><msup><mi>Σ</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle C\subseteq \Sigma ^{n}}</annotation></semantics></math><img src=$ ${\displaystyle C <semantics><mrow><mstyle><mi>C</mi></mstyle></mrow><annotation>{\displaystyle C}</annotation></semantics></math><img src=$ ${\displaystyle d=\min \Delta (c_{1},c_{2}) <semantics><mrow><mstyle><mi>d</mi><mo>=</mo><mo>min</mo><mi>Δ</mi><mo>(</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>c</mi><mrow><mn>2</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle d=\min \Delta (c_{1},c_{2})}</annotation></semantics></math><img src=$ ${\displaystyle c_{1} eq c_{2}\in C <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mo>≠</mo><msub><mi>c</mi><mrow><mn>2</mn></mrow></msub><mo>∈</mo><mi>C</mi></mstyle></mrow><annotation>{\displaystyle c_{1} eq c_{2}\in C}</annotation></semantics></math><img src=$
Concaténation de code : Étant donné ${\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K <semantics><mrow><mstyle><mi>m</mi><mo>=</mo><mo>(</mo><msub><mi>m</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>m</mi><mrow><mi>K</mi></mrow></msub><mo>)</mo><mo>∈</mo><mo>[</mo><mi>Q</mi><msup><mo>]</mo><mrow><mi>K</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}</annotation></semantics></math><img src=$

{\displaystyle C_{ ext{out}}=[Q]^{K} o [Q]^{N},\qquad C_{ ext{in}}:[q]^{k} o [q]^{n}, <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>=</mo><mo>[</mo><mi>Q</mi><msup><mo>]</mo><mrow><mi>K</mi></mrow></msup><mo>→</mo><mo>[</mo><mi>Q</mi><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup><mo>,</mo><mspace></mspace><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>:</mo><mo>[</mo><mi>q</mi><msup><mo>]</mo><mrow><mi>k</mi></mrow></msup><mo>→</mo><mo>[</mo><mi>q</mi><msup><mo>]</mo><mrow><mi>n</mi></mrow></msup><mo>,</mo></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}=[Q]^{K} o [Q]^{N},\qquad C_{ ext{in}}:[q]^{k} o [q]^{n},}</annotation></semantics></math></span><img src=

et leurs distances sont

{\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math></span><img src=

{\displaystyle d <semantics><mrow><mstyle><mi>d</mi></mstyle></mrow><annotation>{\displaystyle d}</annotation></semantics></math></span><img src=

{\displaystyle C_{ ext{out}}\circ C_{ ext{in}}(m)=(C_{ ext{in}}(C_{ ext{out}}(m)_{1}),\ldots ,C_{ ext{in}}(C_{ ext{out}}(m)_{N})) <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>∘</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><mi>m</mi><mo>)</mo><mo>=</mo><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>(</mo><mi>m</mi><msub><mo>)</mo><mrow><mn>1</mn></mrow></msub><mo>)</mo><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>(</mo><mi>m</mi><msub><mo>)</mo><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}\circ C_{ ext{in}}(m)=(C_{ ext{in}}(C_{ ext{out}}(m)_{1}),\ldots ,C_{ ext{in}}(C_{ ext{out}}(m)_{N}))}</annotation></semantics></math></span><img src=

{\displaystyle C_{ ext{out}}(m)=((C_{ ext{out}}(m)_{1},\ldots ,(m)_{N})). <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>(</mo><mi>m</mi><mo>)</mo><mo>=</mo><mo>(</mo><mo>(</mo><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>(</mo><mi>m</mi><msub><mo>)</mo><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><mo>(</mo><mi>m</mi><msub><mo>)</mo><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}(m)=((C_{ ext{out}}(m)_{1},\ldots ,(m)_{N})).}</annotation></semantics></math></span><img src=

{\displaystyle C_{ ext{out <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}}</annotation></semantics></math></span><img src=

{\displaystyle K=O(\log N) <semantics><mrow><mstyle><mi>K</mi><mo>=</mo><mi>O</mi><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>N</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle K=O(\log N)}</annotation></semantics></math></span><img src=

{\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math></span><img src=

Décodage par maximum de vraisemblance (MLD) : le MLD est une méthode de décodage pour les codes correcteurs d’erreurs, qui produit le mot de code le plus proche du mot reçu selon la distance de Hamming. La fonction MLD est notée : ${\displaystyle D_{MLD}:\Sigma ^{n} o C <semantics><mrow><mstyle><msub><mi>D</mi><mrow><mi>M</mi><mi>L</mi><mi>D</mi></mrow></msub><mo>:</mo><msup><mi>Σ</mi><mrow><mi>n</mi></mrow></msup><mo>→</mo><mi>C</mi></mstyle></mrow><annotation>{\displaystyle D_{MLD}:\Sigma ^{n} o C}</annotation></semantics></math><img src=$ ${\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y) <semantics><mrow><mstyle><mi>y</mi><mo>∈</mo><msup><mi>Σ</mi><mrow><mi>n</mi></mrow></msup><mo>,</mo><msub><mi>D</mi><mrow><mi>M</mi><mi>L</mi><mi>D</mi></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo><mo>=</mo><mi>arg</mi><mo>⁡</mo><munder><mo>min</mo><mrow><mi>c</mi><mo>∈</mo><mi>C</mi></mrow></munder><mi>Δ</mi><mo>(</mo><mi>c</mi><mo>,</mo><mi>y</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}</annotation></semantics></math><img src=$
Fonction de densité de probabilité : Une distribution de probabilité ${\displaystyle \Pr <semantics><mrow><mstyle><mo>Pr</mo></mstyle></mrow><annotation>{\displaystyle \Pr }</annotation></semantics></math><img src=$ ${\displaystyle S <semantics><mrow><mstyle><mi>S</mi></mstyle></mrow><annotation>{\displaystyle S}</annotation></semantics></math><img src=$ ${\displaystyle S <semantics><mrow><mstyle><mi>S</mi></mstyle></mrow><annotation>{\displaystyle S}</annotation></semantics></math><img src=$ ${\displaystyle \Pr[A]\geq 0 <semantics><mrow><mstyle><mo>Pr</mo><mo>[</mo><mi>UN</mi><mo>]</mo><mo>≥</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle \Pr[A]\geq 0}</annotation></semantics></math><img src=$ ${\displaystyle A,\Pr[S]=1 <semantics><mrow><mstyle><mi>UN</mi><mo>,</mo><mo>Pr</mo><mo>[</mo><mi>S</mi><mo>]</mo><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle A,\Pr[S]=1}</annotation></semantics></math><img src=$ ${\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B] <semantics><mrow><mstyle><mo>Pr</mo><mo>[</mo><mi>UN</mi><mo>∪</mo><mi>B</mi><mo>]</mo><mo>=</mo><mo>Pr</mo><mo>[</mo><mi>UN</mi><mo>]</mo><mo>+</mo><mo>Pr</mo><mo>[</mo><mi>B</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}</annotation></semantics></math><img src=$ ${\displaystyle A <semantics><mrow><mstyle><mi>UN</mi></mstyle></mrow><annotation>{\displaystyle A}</annotation></semantics></math><img src=$ ${\displaystyle B <semantics><mrow><mstyle><mi>B</mi></mstyle></mrow><annotation>{\displaystyle B}</annotation></semantics></math><img src=$
Espérance statistique : La valeur espérée d'une variable aléatoire discrète ${\displaystyle X <semantics><mrow><mstyle><mi>X</mi></mstyle></mrow><annotation>{\displaystyle X}</annotation></semantics></math><img src=$

{\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x]. <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><mi>X</mi><mo>]</mo><mo>=</mo><munder><mo>∑</mo><mrow><mi>x</mi></mrow></munder><mo>Pr</mo><mo>[</mo><mi>X</mi><mo>=</mo><mi>x</mi><mo>]</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x].}</annotation></semantics></math></span><img src=

Algorithme aléatoire

Considérez le mot reçu ${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N <semantics><mrow><mstyle><mrow><mi>y</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>y</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>∈</mo><mo>[</mo><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation></semantics></math><img src=$ ${\displaystyle C_{ ext{out <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}}</annotation></semantics></math><img src=$

Décodeur aléatoire donné : ${\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N <semantics><mrow><mstyle><mrow><mi>y</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>y</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>∈</mo><mo>[</mo><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}</annotation></semantics></math><img src=$

Pour chaque ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$ ${\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i}) <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>=</mo><mi>M</mi><mi>L</mi><msub><mi>D</mi><mrow><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mrow></msub><mo>(</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i})}</annotation></semantics></math><img src=$
Ensemble ${\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{ frac {d}{2}}) <semantics><mrow><mstyle><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>min</mo><mo>(</mo><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>,</mo><mrow><mstyle><mfrac><mi>d</mi><mn>2</mn></mfrac></mstyle></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{ frac {d}{2}})}</annotation></semantics></math><img src=$
Pour chaque ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$ ${\displaystyle 2\omega _{i} \over d <semantics><mrow><mfrac><mstyle><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mstyle><mi>d</mi></mfrac></mrow><annotation>{\displaystyle 2\omega _{i} \over d}</annotation></semantics></math><img src=$ ${\displaystyle y_{i}''\leftarrow ?, <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>←</mo><mo>?</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle y_{i}''\leftarrow</annotation></semantics></math>?,} <img src=$ ${\displaystyle y_{i}''=y_{i}' <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup></mstyle></mrow><annotation>{\displaystyle y_{i}''=y_{i}'}</annotation></semantics></math><img src=$
Erreurs d'exécution et algorithme d'effacement pour ${\displaystyle C_{ ext{out <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'') <semantics><mrow><mstyle><msup><mrow><mi>y</mi></mrow><mo>″</mo></msup><mo>=</mo><mo>(</mo><msubsup><mi>y</mi><mrow><mn>1</mn></mrow><mo>″</mo></msubsup><mo>,</mo><mo>…</mo><mo>,</mo><msubsup><mi>y</mi><mrow><mi>N</mi></mrow><mo>″</mo></msubsup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation></semantics></math><img src=$

Théorème 1. Soit y un mot reçu tel qu'il existe un mot de code. ${\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{ ext{out}}\circ {C_{ ext{in}}}\subseteq [q^{n}]^{N <semantics><mrow><mstyle><mrow><mi>c</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>⋯</mo><mo>,</mo><msub><mi>c</mi><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>∈</mo><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>∘</mo><mrow><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mrow><mo>⊆</mo><mo>[</mo><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{ ext{out}}\circ {C_{ ext{in}}}\subseteq [q^{n}]^{N}}</annotation></semantics></math><img src=$ tel que ${\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{ frac {Dd}{2 <semantics><mrow><mstyle><mi>Δ</mi><mo>(</mo><mrow><mi>c</mi></mrow><mo>,</mo><mrow><mi>y</mi></mrow><mo>)</mo><mo><</mo><mrow><mstyle><mfrac><mrow><mi>D</mi><mi>d</mi></mrow><mn>2</mn></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{ frac {Dd}{2}}}</annotation></semantics></math><img src=$ L'algorithme GMD déterministe produit ensuite les résultats suivants : ${\displaystyle \mathbf {c} <semantics><mrow><mstyle><mrow><mi>c</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} }</annotation></semantics></math><img src=$

Notez qu'un algorithme de décodage naïf pour les codes concaténés peut corriger jusqu'à ${\displaystyle { frac {Dd}{4 <semantics><mrow><mstyle><mrow><mstyle><mfrac><mrow><mi>D</mi><mi>d</mi></mrow><mn>4</mn></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle { frac {Dd}{4}}}</annotation></semantics></math><img src=$

Lemme 1. Supposons que l'hypothèse du théorème 1 soit vérifiée. Et si

{\displaystyle \mathbf {y} '' <semantics><mrow><mstyle><msup><mrow><mi>y</mi></mrow><mo>″</mo></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {y} ''}</annotation></semantics></math></span><img src=

{\displaystyle e' <semantics><mrow><mstyle><msup><mi>e</mi><mo>′</mo></msup></mstyle></mrow><annotation>{\displaystyle e'}</annotation></semantics></math></span><img src=

{\displaystyle s' <semantics><mrow><mstyle><msup><mi>s</mi><mo>′</mo></msup></mstyle></mrow><annotation>{\displaystyle s'}</annotation></semantics></math></span><img src=

{\displaystyle \mathbf {c} <semantics><mrow><mstyle><mrow><mi>c</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} }</annotation></semantics></math></span><img src=

l'étape 1 , puis

{\displaystyle \mathbb {E} [2e'+s']<D. <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><mn>2</mn><msup><mi>e</mi><mo>′</mo></msup><mo>+</mo><msup><mi>s</mi><mo>′</mo></msup><mo>]</mo><mo><</mo><mi>D</mi><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [2e'+s']<D.}</annotation></semantics></math></span><img src=

Remarque. Si ${\displaystyle 2e'+s'<D <semantics><mrow><mstyle><mn>2</mn><msup><mi>e</mi><mo>′</mo></msup><mo>+</mo><msup><mi>s</mi><mo>′</mo></msup><mo><</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle 2e'+s'<D}</annotation></semantics></math><img src=$ L'algorithme de l'étape 2 produira alors le résultat suivant : ${\displaystyle \mathbf {c} <semantics><mrow><mstyle><mrow><mi>c</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {c} }</annotation></semantics></math><img src=$ le théorème 1 , mais peut s'avérer crucial pour le développement de futures variantes de l'algorithme.

Démonstration du lemme 1. Pour tout ${\displaystyle 1\leq i\leq N, <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi><mo>,</mo></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N,}</annotation></semantics></math><img src=$ ${\displaystyle e_{i}=\Delta (y_{i},c_{i}). <semantics><mrow><mstyle><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mi>Δ</mi><mo>(</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>,</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\displaystyle e_{i}=\Delta (y_{i},c_{i}).}</annotation></semantics></math><img src=$

${\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1) <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>N</mi></mrow></munderover><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub><mo><</mo><mrow><mfrac><mrow><mi>D</mi><mi>d</mi></mrow><mn>2</mn></mfrac></mrow><mspace></mspace><mspace></mspace><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)}</annotation></semantics></math><img src=$ ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$

${\displaystyle {\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{ ext{in}}(y_{i}'') eq c_{i}\ { ext{and}}\ y_{i}'' eq ?\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>X</mi><mrow><msubsup><mi></mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup></mrow><mo>=</mo><mn>1</mn></mtd><mtd><mi></mi><mo>⇔</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><mo>?</mo></mtd></mtr><mtr><mtd><mi>X</mi><mrow><msubsup><mi></mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup></mrow><mo>=</mo><mn>1</mn></mtd><mtd><mi></mi><mo>⇔</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>)</mo><mo>≠</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mtext> </mtext><mrow><mtext>et</mtext></mrow><mtext> </mtext><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>≠</mo><mo>?</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{ ext{in}}(y_{i}'') eq c_{i}\ { ext{and}}\ y_{i}'' eq</annotation></semantics></math><img src=$ chaque ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$

${\displaystyle \mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}} ight]\leqslant {2e_{i} \over d}\qquad \qquad (2) <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mrow><mo>[</mo><mrow><mn>2</mn><mi>X</mi><mrow><msubsup><mi></mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>+</mo><mi>X</mi><mrow><msubsup><mi></mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup></mrow></mrow></mrow><mo>]</mo></mrow><mo>⩽</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mspace></mspace><mspace></mspace><mo>(</mo><mn>2</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}} ight]\leqslant {2e_{i} \over d}\qquad \qquad (2)}</annotation></semantics></math><img src=$

${\displaystyle e'=\sum _{i}X_{i}^{e}\quad { ext{and}}\quad s'=\sum _{i}X_{i}^{?}. <semantics><mrow><mstyle><msup><mi>e</mi><mo>′</mo></msup><mo>=</mo><munder><mo>∑</mo><mrow><mi>je</mi></mrow></munder><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mspace></mspace><mrow><mtext>et</mtext></mrow><mspace></mspace><msup><mi>s</mi><mo>′</mo></msup><mo>=</mo><munder><mo>∑</mo><mrow><mi>je</mi></mrow></munder><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle e'=\sum _{i}X_{i}^{e}\quad { ext{and}}\quad s'=\sum _{i}X_{i}^{?}.}</annotation></semantics></math><img src=$

${\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D. <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><mn>2</mn><msup><mi>e</mi><mo>′</mo></msup><mo>+</mo><msup><mi>s</mi><mo>′</mo></msup><mo>]</mo><mo>⩽</mo><mrow><mfrac><mn>2</mn><mi>d</mi></mfrac></mrow><munder><mo>∑</mo><mrow><mi>je</mi></mrow></munder><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub><mo><</mo><mi>D</mi><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.}</annotation></semantics></math><img src=$ ${\displaystyle i <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle i}</annotation></semantics></math><img src=$ Cas 1 ), ${\displaystyle i <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle i}</annotation></semantics></math><img src=$ Cas 2 ) :

Cas 1 : ${\displaystyle (c_{i}=C_{ ext{in}}(y_{i}')) <semantics><mrow><mstyle><mo>(</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (c_{i}=C_{ ext{in}}(y_{i}'))}</annotation></semantics></math><img src=$

Notez que si ${\displaystyle y_{i}''=? <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><mo>?</mo></mstyle></mrow><annotation>{\displaystyle y_{i}''=?}</annotation></semantics></math><img src=$ ${\displaystyle X_{i}^{e}=0 <semantics><mrow><mstyle><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle X_{i}^{e}=0}</annotation></semantics></math><img src=$ ${\displaystyle \Pr[y_{i}''=?]={ frac {2\omega _{i}}{d <semantics><mrow><mstyle><mo>Pr</mo><mo>[</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><mo>?</mo><mo>]</mo><mo>=</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle \Pr[y_{i}''=?]={ frac {2\omega _{i}}{d}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={ frac {2\omega _{i}}{d}}, <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup><mo>]</mo><mo>=</mo><mo>Pr</mo><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup><mo>=</mo><mn>1</mn><mo>]</mo><mo>=</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={ frac {2\omega _{i}}{d}},}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0 <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>]</mo><mo>=</mo><mo>Pr</mo><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>=</mo><mn>1</mn><mo>]</mo><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}</annotation></semantics></math><img src=$

De plus, par définition, nous avons

${\displaystyle \omega _{i}=\min \left(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{ frac {d}{2}} ight)\leqslant \Delta (C_{ ext{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i <semantics><mrow><mstyle><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>min</mo><mrow><mo>(</mo><mrow><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>,</mo><mrow><mstyle><mfrac><mi>d</mi><mn>2</mn></mfrac></mstyle></mrow></mrow><mo>)</mo></mrow><mo>⩽</mo><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>=</mo><mi>Δ</mi><mo>(</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>=</mo><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle \omega _{i}=\min \left(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{ frac {d}{2}} ight)\leqslant \Delta (C_{ ext{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i}}</annotation></semantics></math><img src=$ Cas 2 : ${\displaystyle (c_{i} eq C_{ ext{in}}(y_{i}')) <semantics><mrow><mstyle><mo>(</mo><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>≠</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (c_{i} eq C_{ ext{in}}(y_{i}'))}</annotation></semantics></math><img src=$

Dans ce cas, ${\displaystyle \mathbb {E} [X_{i}^{?}]={ frac {2\omega _{i}}{d <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup><mo>]</mo><mo>=</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [X_{i}^{?}]={ frac {2\omega _{i}}{d}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{ frac {2\omega _{i}}{d}}. <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>]</mo><mo>=</mo><mo>Pr</mo><mo>[</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>=</mo><mn>1</mn><mo>]</mo><mo>=</mo><mn>1</mn><mo>−</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{ frac {2\omega _{i}}{d}}.}</annotation></semantics></math><img src=$

Depuis ${\displaystyle c_{i} eq C_{ ext{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>je</mi></mrow></msub><mo>≠</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub><mo>+</mo><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>⩾</mo><mi>d</mi></mstyle></mrow><annotation>{\displaystyle c_{i} eq C_{ ext{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}</annotation></semantics></math><img src=$ ${\displaystyle (\omega _{i}=\Delta (C_{ ext{in}}(y_{i}'),y_{i})<{ frac {d}{2}}) <semantics><mrow><mstyle><mo>(</mo><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo><</mo><mrow><mstyle><mfrac><mi>d</mi><mn>2</mn></mfrac></mstyle></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\omega _{i}=\Delta (C_{ ext{in}}(y_{i}'),y_{i})<{ frac {d}{2}})}</annotation></semantics></math><img src=$

Enfin, cela implique

${\displaystyle \mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}. <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><mn>2</mn><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mi>e</mi></mrow></msubsup><mo>+</mo><msubsup><mi>X</mi><mrow><mi>je</mi></mrow><mrow><mo>?</mo></mrow></msubsup><mo>]</mo><mo>=</mo><mn>2</mn><mo>−</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mo>≤</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>e</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}.}</annotation></semantics></math><img src=$ ${\displaystyle C_{ ext{out}}\circ C_{ ext{in <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>∘</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}\circ C_{ ext{in}}}</annotation></semantics></math><img src=$

Algorithme aléatoire modifié

Notez que, dans la version précédente de l'algorithme GMD à l'étape « 3 », nous n'avons pas réellement besoin d'utiliser une aléatorité « fraîche » pour chaque ${\displaystyle i <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle i}</annotation></semantics></math><img src=$ même aléatoire pour chaque itération . ${\displaystyle i <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle i}</annotation></semantics></math><img src=$

Décodeur_aléatoire_modifié donné : ${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N <semantics><mrow><mstyle><mrow><mi>y</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>y</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>∈</mo><mo>[</mo><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation></semantics></math><img src=$ ${\displaystyle heta \in [0,1] <semantics><mrow><mstyle><mi>θ</mi><mo>∈</mo><mo>[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>]</mo></mstyle></mrow><annotation>{\displaystyle heta \in [0,1]}</annotation></semantics></math><img src=$ ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$

Ensemble ${\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i}) <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>=</mo><mi>M</mi><mi>L</mi><msub><mi>D</mi><mrow><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mrow></msub><mo>(</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i})}</annotation></semantics></math><img src=$
Calculer ${\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{d \over 2}) <semantics><mrow><mstyle><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>min</mo><mo>(</mo><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>,</mo><mrow><mfrac><mi>d</mi><mn>2</mn></mfrac></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{d \over 2})}</annotation></semantics></math><img src=$
Si ${\displaystyle heta <{ frac {2\omega _{i}}{d <semantics><mrow><mstyle><mi>θ</mi><mo><</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle heta <{ frac {2\omega _{i}}{d}}}</annotation></semantics></math><img src=$ ${\displaystyle y_{i}''\leftarrow ?, <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>←</mo><mo>?</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle y_{i}''\leftarrow</annotation></semantics></math>?,} <img src=$ ${\displaystyle y_{i}''=y_{i}' <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup></mstyle></mrow><annotation>{\displaystyle y_{i}''=y_{i}'}</annotation></semantics></math><img src=$
Erreurs d'exécution et algorithme d'effacement pour ${\displaystyle C_{ ext{out <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'') <semantics><mrow><mstyle><msup><mrow><mi>y</mi></mrow><mo>″</mo></msup><mo>=</mo><mo>(</mo><msubsup><mi>y</mi><mrow><mn>1</mn></mrow><mo>″</mo></msubsup><mo>,</mo><mo>…</mo><mo>,</mo><msubsup><mi>y</mi><mrow><mi>N</mi></mrow><mo>″</mo></msubsup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation></semantics></math><img src=$

Pour la démonstration du lemme 1 , nous utilisons uniquement le caractère aléatoire pour montrer que

${\displaystyle \Pr[y_{i}''=?]={2\omega _{i} \over d}. <semantics><mrow><mstyle><mo>Pr</mo><mo>[</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><mo>?</mo><mo>]</mo><mo>=</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \Pr[y_{i}''=?]={2\omega _{i} \over d}.}</annotation></semantics></math><img src=$

${\displaystyle \Pr[y_{i}''=?]=\Pr \left[ heta \in \left[0,{ frac {2\omega _{i}}{d}} ight] ight]={ frac {2\omega _{i}}{d}}. <semantics><mrow><mstyle><mo>Pr</mo><mo>[</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><mo>?</mo><mo>]</mo><mo>=</mo><mo>Pr</mo><mrow><mo>[</mo><mrow><mi>θ</mi><mo>∈</mo><mrow><mo>[</mo><mrow><mn>0</mn><mo>,</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow></mrow><mo>]</mo></mrow></mrow><mo>]</mo></mrow><mo>=</mo><mrow><mstyle><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mstyle></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \Pr[y_{i}''=?]=\Pr \left[ heta \in \left[0,{ frac {2\omega _{i}}{d}} ight] ight]={ frac {2\omega _{i}}{d}}.}</annotation></semantics></math><img src=$ ${\displaystyle heta <semantics><mrow><mstyle><mi>θ</mi></mstyle></mrow><annotation>{\displaystyle heta }</annotation></semantics></math><img src=$ lemme 1 peut également servir à montrer que … ${\displaystyle \mathbb {E} [2e'+s']<D <semantics><mrow><mstyle><mrow><mi>E</mi></mrow><mo>[</mo><mn>2</mn><msup><mi>e</mi><mo>′</mo></msup><mo>+</mo><msup><mi>s</mi><mo>′</mo></msup><mo>]</mo><mo><</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle \mathbb {E} [2e'+s']<D}</annotation></semantics></math><img src=$ ${\displaystyle heta <semantics><mrow><mstyle><mi>θ</mi></mstyle></mrow><annotation>{\displaystyle heta }</annotation></semantics></math><img src=$ ${\displaystyle [0,1] <semantics><mrow><mstyle><mo>[</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>]</mo></mstyle></mrow><annotation>{\displaystyle [0,1]}</annotation></semantics></math><img src=$

Algorithme déterministe

Laisser ${\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\ <semantics><mrow><mstyle><mi>Q</mi><mo>=</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>}</mo><mo>∪</mo><mo>{</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mn>1</mn></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mo>,</mo><mo>…</mo><mo>,</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>N</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow><mo>}</mo></mstyle></mrow><annotation>{\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}</annotation></semantics></math><img src=$ ${\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2}) <semantics><mrow><mstyle><mi>je</mi><mo>,</mo><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>min</mo><mo>(</mo><mi>Δ</mi><mo>(</mo><mrow><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup></mrow><mo>,</mo><mrow><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub></mrow><mo>)</mo><mo>,</mo><mrow><mfrac><mi>d</mi><mn>2</mn></mfrac></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}</annotation></semantics></math><img src=$

${\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\ <semantics><mrow><mstyle><mi>Q</mi><mo>=</mo><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>}</mo><mo>∪</mo><mo>{</mo><msub><mi>q</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>q</mi><mrow><mi>m</mi></mrow></msub><mo>}</mo></mstyle></mrow><annotation>{\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}}</annotation></semantics></math><img src=$ ${\displaystyle q_{1}<\cdots <q_{m <semantics><mrow><mstyle><msub><mi>q</mi><mrow><mn>1</mn></mrow></msub><mo><</mo><mo>⋯</mo><mo><</mo><msub><mi>q</mi><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle q_{1}<\cdots <q_{m}}</annotation></semantics></math><img src=$ ${\displaystyle m\leq \left\lfloor {\frac {d}{2}} ight floor <semantics><mrow><mstyle><mi>m</mi><mo>≤</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>d</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow></mstyle></mrow><annotation>{\displaystyle m\leq \left\lfloor {\frac {d}{2}} ight floor }</annotation></semantics></math><img src=$ ${\displaystyle heta \in [q_{i},q_{i+1}] <semantics><mrow><mstyle><mi>θ</mi><mo>∈</mo><mo>[</mo><msub><mi>q</mi><mrow><mi>je</mi></mrow></msub><mo>,</mo><msub><mi>q</mi><mrow><mi>je</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>]</mo></mstyle></mrow><annotation>{\displaystyle heta \in [q_{i},q_{i+1}]}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {y} ''. <semantics><mrow><mstyle><msup><mrow><mi>y</mi></mrow><mo>″</mo></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \mathbf {y} ''.}</annotation></semantics></math><img src=$ ${\displaystyle heta \in Q <semantics><mrow><mstyle><mi>θ</mi><mo>∈</mo><mi>Q</mi></mstyle></mrow><annotation>{\displaystyle heta \in Q}</annotation></semantics></math><img src=$

Décodeur déterministe donné : ${\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N <semantics><mrow><mstyle><mrow><mi>y</mi></mrow><mo>=</mo><mo>(</mo><msub><mi>y</mi><mrow><mn>1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>N</mi></mrow></msub><mo>)</mo><mo>∈</mo><mo>[</mo><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mo>]</mo><mrow><mi>N</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation></semantics></math><img src=$ ${\displaystyle heta \in Q <semantics><mrow><mstyle><mi>θ</mi><mo>∈</mo><mi>Q</mi></mstyle></mrow><annotation>{\displaystyle heta \in Q}</annotation></semantics></math><img src=$

Calculer ${\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i}) <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>=</mo><mi>M</mi><mi>L</mi><msub><mi>D</mi><mrow><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mrow></msub><mo>(</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle y_{i}'=MLD_{C_{ ext{in}}}(y_{i})}</annotation></semantics></math><img src=$ ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$
Ensemble ${\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{d \over 2}) <semantics><mrow><mstyle><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub><mo>=</mo><mo>min</mo><mo>(</mo><mi>Δ</mi><mo>(</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub><mo>(</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup><mo>)</mo><mo>,</mo><msub><mi>y</mi><mrow><mi>je</mi></mrow></msub><mo>)</mo><mo>,</mo><mrow><mfrac><mi>d</mi><mn>2</mn></mfrac></mrow><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \omega _{i}=\min(\Delta (C_{ ext{in}}(y_{i}'),y_{i}),{d \over 2})}</annotation></semantics></math><img src=$ ${\displaystyle 1\leq i\leq N <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>je</mi><mo>≤</mo><mi>N</mi></mstyle></mrow><annotation>{\displaystyle 1\leq i\leq N}</annotation></semantics></math><img src=$
Si ${\displaystyle heta <{2\omega _{i} \over d <semantics><mrow><mstyle><mi>θ</mi><mo><</mo><mrow><mfrac><mrow><mn>2</mn><msub><mi>ω</mi><mrow><mi>je</mi></mrow></msub></mrow><mi>d</mi></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle heta <{2\omega _{i} \over d}}</annotation></semantics></math><img src=$ ${\displaystyle y_{i}''\leftarrow ?, <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>←</mo><mo>?</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle y_{i}''\leftarrow</annotation></semantics></math>?,} <img src=$ ${\displaystyle y_{i}''=y_{i}' <semantics><mrow><mstyle><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>″</mo></msubsup><mo>=</mo><msubsup><mi>y</mi><mrow><mi>je</mi></mrow><mo>′</mo></msubsup></mstyle></mrow><annotation>{\displaystyle y_{i}''=y_{i}'}</annotation></semantics></math><img src=$
Exécuter l'algorithme de détection des erreurs et des effacements pour ${\displaystyle C_{ ext{out <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'') <semantics><mrow><mstyle><msup><mrow><mi>y</mi></mrow><mo>″</mo></msup><mo>=</mo><mo>(</mo><msubsup><mi>y</mi><mrow><mn>1</mn></mrow><mo>″</mo></msubsup><mo>,</mo><mo>…</mo><mo>,</mo><msubsup><mi>y</mi><mrow><mi>N</mi></mrow><mo>″</mo></msubsup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation></semantics></math><img src=$ ${\displaystyle c_{ heta <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>θ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle c_{ heta }}</annotation></semantics></math><img src=$ ${\displaystyle C_{ ext{out}}\circ C_{ ext{in <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>∘</mo><msub><mi>C</mi><mrow><mtext>dans</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle C_{ ext{out}}\circ C_{ ext{in}}}</annotation></semantics></math><img src=$
Parmi tous les ${\displaystyle c_{ heta <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mi>θ</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle c_{ heta }}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {y} <semantics><mrow><mstyle><mrow><mi>y</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {y} }</annotation></semantics></math><img src=$

Chaque boucle de 1 à 4 peut être exécutée en temps polynomial ; l'algorithme ci-dessus peut également être calculé en temps polynomial. Plus précisément, chaque appel à un décodeur d'erreurs et d'effacements de ${\displaystyle <dD/2 <semantics><mrow><mstyle><mo><</mo><mi>d</mi><mi>D</mi><mrow><mo>/</mo></mrow><mn>2</mn></mstyle></mrow><annotation>{\displaystyle <dD/2}</annotation></semantics></math><img src=$ ${\displaystyle O(d) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>d</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(d)}</annotation></semantics></math><img src=$ ${\displaystyle O(NQn^{O(1)}+NT_{ ext{out}}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>N</mi><mi>Q</mi><msup><mi>n</mi><mrow><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></msup><mo>+</mo><mi>N</mi><msub><mi>T</mi><mrow><mtext>dehors</mtext></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(NQn^{O(1)}+NT_{ ext{out}})}</annotation></semantics></math><img src=$ ${\displaystyle T_{ ext{out <semantics><mrow><mstyle><msub><mi>T</mi><mrow><mtext>dehors</mtext></mrow></msub></mstyle></mrow><annotation>{\displaystyle T_{ ext{out}}}</annotation></semantics></math><img src=$