Code de bloc

En théorie du codage , les codes en blocs constituent une grande famille de codes correcteurs d'erreurs qui codent les données en blocs. Il existe un grand nombre d'exemples de codes en blocs, dont beaucoup ont une large gamme d'applications pratiques. La définition abstraite des codes en blocs est utile sur le plan conceptuel car elle permet aux théoriciens du codage, aux mathématiciens et aux informaticiens d'étudier les limites de tous les codes en blocs de manière unifiée. Ces limites prennent souvent la forme de limites qui relient différents paramètres du code en blocs les uns aux autres, tels que son débit et sa capacité à détecter et à corriger les erreurs.

Les codes de Reed-Solomon , les codes de Hamming , les codes de Hadamard , les codes d'expansion , les codes de Golay , les codes de Reed-Muller et les codes polaires sont des exemples de codes en blocs . Ces exemples appartiennent également à la classe des codes linéaires et sont donc appelés codes en blocs linéaires . Plus particulièrement, ces codes sont connus sous le nom de codes en blocs algébriques ou de codes en blocs cycliques, car ils peuvent être générés à l'aide de polynômes booléens.

Les codes de blocs algébriques sont généralement décodés en dur à l'aide de décodeurs algébriques.

Le terme code en bloc peut également désigner tout code correcteur d'erreurs qui agit sur un bloc de bits de données d'entrée pour produire des bits de données de sortie . Par conséquent, le codeur en bloc est un dispositif sans mémoire . Selon cette définition, des codes tels que les codes turbo , les codes convolutionnels terminés et d'autres codes décodables de manière itérative (codes de type turbo) seraient également considérés comme des codes en bloc. Un codeur convolutionnel non terminé serait un exemple de code non en bloc (sans trame), qui possède une mémoire et est plutôt classé comme un code arborescent . ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle (n,k) <semantics> <mrow> <mstyle> <mo>(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle (n,k)}</annotation> </semantics> </math><img src=$

Cet article traite des « codes de blocs algébriques ».

Le code du bloc et ses paramètres

Les codes correcteurs d'erreurs sont utilisés pour transmettre de manière fiable des données numériques sur des canaux de communication peu fiables et sujets au bruit de canal . Lorsqu'un expéditeur souhaite transmettre un flux de données potentiellement très long à l'aide d'un code de bloc, il divise le flux en morceaux de taille fixe. Chaque morceau de ce type est appelé message et la procédure donnée par le code de bloc code chaque message individuellement dans un mot de code, également appelé bloc dans le contexte des codes de bloc. L'expéditeur transmet ensuite tous les blocs au récepteur, qui peut à son tour utiliser un mécanisme de décodage pour (espérons-le) récupérer les messages d'origine à partir des blocs reçus éventuellement corrompus. Les performances et le succès de la transmission globale dépendent des paramètres du canal et du code de bloc.

Formellement, un code de bloc est un mappage injectif

{\displaystyle C:\Sigma ^{k} o \Sigma ^{n <semantics> <mrow> <mstyle> <mi>C</mi> <mo>:</mo> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> <mo>→</mo> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle C:\Sigma ^{k}\à \Sigma ^{n}}</annotation> </semantics> </math></span><img src=

Ici, est un ensemble fini et non vide et et sont des entiers. La signification et l'importance de ces trois paramètres et d'autres paramètres liés au code sont décrites ci-dessous. ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

L'alphabet Σ

Le flux de données à encoder est modélisé comme une chaîne sur un alphabet . La taille de l'alphabet est souvent écrite sous la forme . Si , alors le code en bloc est appelé code en bloc binaire . Dans de nombreuses applications, il est utile de considérer comme une puissance première , et de l'identifier au corps fini . ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle |\Sigma | <semantics> <mrow> <mstyle> <mrow> <mo>|</mo> </mrow> <mi>Σ</mi> <mrow> <mo>|</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle |\Sigma |}</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle q=2 <semantics> <mrow> <mstyle> <mi>q</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle q=2}</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle \mathbb {F} _{q <semantics> <mrow> <mstyle> <msub> <mrow> <mi>F</mi> </mrow> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \mathbb {F} _{q}}</annotation> </semantics> </math><img src=$

La longueur du messagek

Les messages sont des éléments de , c'est-à-dire des chaînes de longueur . Le nombre est donc appelé longueur de message ou dimension d'un code de bloc. ${\displaystyle m <semantics> <mrow> <mstyle> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle m}</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma ^{k <semantics> <mrow> <mstyle> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle \Sigma ^{k}}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$

La longueur du blocn

La longueur de bloc d'un code de bloc est le nombre de symboles dans un bloc. Par conséquent, les éléments de sont des chaînes de longueur et correspondent à des blocs qui peuvent être reçus par le récepteur. Par conséquent, ils sont également appelés mots reçus. Si pour un message , alors est appelé le mot de code de . ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle 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 \Sigma ^{n <semantics> <mrow> <mstyle> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle \Sigma ^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle c=C(m) <semantics> <mrow> <mstyle> <mi>c</mi> <mo>=</mo> <mi>C</mi> <mo>(</mo> <mi>m</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle c=C(m)}</annotation> </semantics> </math><img src=$ ${\displaystyle m <semantics> <mrow> <mstyle> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle m}</annotation> </semantics> </math><img src=$ ${\displaystyle c <semantics> <mrow> <mstyle> <mi>c</mi> </mstyle> </mrow> <annotation>{\displaystyle c}</annotation> </semantics> </math><img src=$ ${\displaystyle m <semantics> <mrow> <mstyle> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle m}</annotation> </semantics> </math><img src=$

Le tauxR

Le débit d'un code de bloc est défini comme le rapport entre la longueur de son message et la longueur de son bloc :

{\displaystyle R=k/n <semantics> <mrow> <mstyle> <mi>R</mi> <mo>=</mo> <mi>k</mi> <mrow> <mo>/</mo> </mrow> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle R=k/n}</annotation> </semantics> </math></span><img src=

Un débit élevé signifie que la quantité réelle de messages par bloc transmis est élevée. Dans ce sens, le débit mesure la vitesse de transmission et la quantité mesure la surcharge qui se produit en raison du codage avec le code de bloc. C'est un simple fait théorique de l'information que le débit ne peut pas dépasser, car les données ne peuvent en général pas être compressées sans perte. Formellement, cela découle du fait que le code est une carte injective. ${\displaystyle 1-R <semantics> <mrow> <mstyle> <mn>1</mn> <mo>−</mo> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle 1-R}</annotation> </semantics> </math><img src=$ ${\displaystyle 1 <semantics> <mrow> <mstyle> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle 1}</annotation> </semantics> </math><img src=$ ${\displaystyle C <semantics> <mrow> <mstyle> <mi>C</mi> </mstyle> </mrow> <annotation>{\displaystyle C}</annotation> </semantics> </math><img src=$

La distanced

La distance ou distance minimale d d'un code en bloc est le nombre minimal de positions dans lesquelles deux mots de code distincts diffèrent, et la distance relative est la fraction . Formellement, pour les mots reçus , notons la distance de Hamming entre et , c'est-à-dire le nombre de positions dans lesquelles et diffèrent. La distance minimale du code est alors définie comme ${\displaystyle \delta <semantics> <mrow> <mstyle> <mi>δ</mi> </mstyle> </mrow> <annotation>{\displaystyle \delta }</annotation> </semantics> </math><img src=$ ${\displaystyle d/n <semantics> <mrow> <mstyle> <mi>d</mi> <mrow> <mo>/</mo> </mrow> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle d/n}</annotation> </semantics> </math><img src=$ ${\displaystyle c_{1},c_{2}\in \Sigma ^{n <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> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle c_{1},c_{2}\dans \Sigma ^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta (c_{1},c_{2}) <semantics> <mrow> <mstyle> <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 \Delta (c_{1},c_{2})}</annotation> </semantics> </math><img src=$ ${\displaystyle c_{1 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle c_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle c_{2 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle c_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle c_{1 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle c_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle c_{2 <semantics> <mrow> <mstyle> <msub> <mi>c</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle c_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</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 _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [C(m_{1}),C(m_{2})] <semantics> <mrow> <mstyle> <mi>d</mi> <mo>:=</mo> <munder> <mo>min</mo> <mrow> <mfrac> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>∈</mo> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> </mrow> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>≠</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </mfrac> </mrow> </munder> <mi>Δ</mi> <mo>[</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>,</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>]</mo> </mstyle> </mrow> <annotation>{\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [C(m_{1}),C(m_{2})]}</annotation> </semantics> </math></span><img src=

Comme tout code doit être injectif , deux mots de code quelconques seront en désaccord sur au moins une position, donc la distance de tout code est d'au moins . De plus, la distance est égale au poids minimum pour les codes de blocs linéaires car : ${\displaystyle 1 <semantics> <mrow> <mstyle> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle 1}</annotation> </semantics> </math><img src=$

{\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m eq \mathbf {0} }w[C(m)]=w_{\min <semantics> <mrow> <mstyle> <munder> <mo>min</mo> <mrow> <mfrac> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>∈</mo> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> </mrow> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>≠</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </mfrac> </mrow> </munder> <mi>Δ</mi> <mo>[</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>,</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>]</mo> <mo>=</mo> <munder> <mo>min</mo> <mrow> <mfrac> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>∈</mo> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> </mrow> <mrow> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>≠</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> </mfrac> </mrow> </munder> <mi>Δ</mi> <mo>[</mo> <mrow> <mn>0</mn> </mrow> <mo>,</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>+</mo> <mi>C</mi> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>]</mo> <mo>=</mo> <munder> <mo>min</mo> <mrow> <mfrac> <mrow> <mi>m</mi> <mo>∈</mo> <msup> <mi>Σ</mi> <mrow> <mi>k</mi> </mrow> </msup> </mrow> <mrow> <mi>m</mi> <mo>≠</mo> <mrow> <mn>0</mn> </mrow> </mrow> </mfrac> </mrow> </munder> <mi>w</mi> <mo>[</mo> <mi>C</mi> <mo>(</mo> <mi>m</mi> <mo>)</mo> <mo>]</mo> <mo>=</mo> <msub> <mi>w</mi> <mrow> <mo>min</mo> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1} eq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m eq \mathbf {0} }w[C(m)]=w_{\min }}</annotation> </semantics> </math></span><img src=

Une distance plus grande permet une meilleure détection et correction des erreurs. Par exemple, si nous considérons uniquement les erreurs qui peuvent modifier les symboles du mot de code envoyé mais ne jamais les effacer ou les ajouter, alors le nombre d'erreurs est le nombre de positions dans lesquelles le mot de code envoyé et le mot reçu diffèrent. Un code avec une distance d permet au récepteur de détecter jusqu'à erreurs de transmission puisque le changement de position d'un mot de code ne peut jamais produire accidentellement un autre mot de code. De plus, si pas plus de erreurs de transmission ne se produisent, le récepteur peut décoder de manière unique le mot reçu en un mot de code. En effet, chaque mot reçu a au plus un mot de code à une distance de . Si plus de erreurs de transmission se produisent, le récepteur ne peut pas décoder de manière unique le mot reçu en général car il peut y avoir plusieurs mots de code possibles. Une façon pour le récepteur de faire face à cette situation est d'utiliser le décodage de liste , dans lequel le décodeur génère une liste de tous les mots de code dans un certain rayon. ${\displaystyle d-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle d-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle (d-1)/2 <semantics> <mrow> <mstyle> <mo>(</mo> <mi>d</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle (d-1)/2}</annotation> </semantics> </math><img src=$ ${\displaystyle (d-1)/2 <semantics> <mrow> <mstyle> <mo>(</mo> <mi>d</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle (d-1)/2}</annotation> </semantics> </math><img src=$ ${\displaystyle (d-1)/2 <semantics> <mrow> <mstyle> <mo>(</mo> <mi>d</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle (d-1)/2}</annotation> </semantics> </math><img src=$

Notation populaire

La notation décrit un code de bloc sur un alphabet de taille , avec une longueur de bloc , une longueur de message et une distance . Si le code de bloc est un code de bloc linéaire, les crochets dans la notation sont utilisés pour représenter ce fait. Pour les codes binaires avec , l'index est parfois supprimé. Pour les codes séparables à distance maximale , la distance est toujours , mais parfois la distance précise n'est pas connue, n'est pas triviale à prouver ou à énoncer, ou n'est pas nécessaire. Dans de tels cas, le composant peut être manquant. ${\displaystyle (n,k,d)_{q <semantics> <mrow> <mstyle> <mo>(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>)</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle (n,k,d)_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma <semantics> <mrow> <mstyle> <mi>Σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$ ${\displaystyle [n,k,d]_{q <semantics> <mrow> <mstyle> <mo>[</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>]</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle [n,k,d]_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle q=2 <semantics> <mrow> <mstyle> <mi>q</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle q=2}</annotation> </semantics> </math><img src=$ ${\displaystyle d=n-k+1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d=n-k+1}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$

Parfois, notamment pour les codes non bloquants, la notation est utilisée pour les codes qui contiennent des mots de code de longueur . Pour les codes bloquants avec des messages d'une longueur supérieure à un alphabet de taille , ce nombre serait . ${\displaystyle (n,M,d)_{q <semantics> <mrow> <mstyle> <mo>(</mo> <mi>n</mi> <mo>,</mo> <mi>M</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>)</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle (n,M,d)_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle M <semantics> <mrow> <mstyle> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle M}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle k <semantics> <mrow> <mstyle> <mi>k</mi> </mstyle> </mrow> <annotation>{\displaystyle k}</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle M=q^{k <semantics> <mrow> <mstyle> <mi>M</mi> <mo>=</mo> <msup> <mi>q</mi> <mrow> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle M=q^{k}}</annotation> </semantics> </math><img src=$

Exemples

Comme mentionné ci-dessus, il existe un grand nombre de codes correcteurs d'erreurs qui sont en fait des codes en bloc. Le premier code correcteur d'erreurs était le code Hamming(7,4) , développé par Richard W. Hamming en 1950. Ce code transforme un message composé de 4 bits en un mot de code de 7 bits en ajoutant 3 bits de parité. Ce code est donc un code en bloc. Il s'avère qu'il s'agit également d'un code linéaire et qu'il a une distance de 3. Dans la notation abrégée ci-dessus, cela signifie que le code Hamming(7,4) est un code. ${\displaystyle [7,4,3]_{2 <semantics> <mrow> <mstyle> <mo>[</mo> <mn>7</mn> <mo>,</mo> <mn>4</mn> <mo>,</mo> <mn>3</mn> <msub> <mo>]</mo> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle [7,4,3]_{2}}</annotation> </semantics> </math><img src=$

Les codes de Reed-Solomon sont une famille de codes avec et étant une puissance première . Les codes de rang sont une famille de codes avec . Les codes d'Hadamard sont une famille de codes avec et . ${\displaystyle [n,k,d]_{q <semantics> <mrow> <mstyle> <mo>[</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>]</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle [n,k,d]_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle d=n-k+1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d=n-k+1}</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle [n,k,d]_{q <semantics> <mrow> <mstyle> <mo>[</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>]</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle [n,k,d]_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle d\leq n-k+1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>≤</mo> <mi>n</mi> <mo>−</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d\leq n-k+1}</annotation> </semantics> </math><img src=$ ${\displaystyle [n,k,d]_{2 <semantics> <mrow> <mstyle> <mo>[</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo>,</mo> <mi>d</mi> <msub> <mo>]</mo> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle [n,k,d]_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle n=2^{k-1 <semantics> <mrow> <mstyle> <mi>n</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle n=2^{k-1}}</annotation> </semantics> </math><img src=$ ${\displaystyle d=2^{k-2 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow> <mi>k</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle d=2^{k-2}}</annotation> </semantics> </math><img src=$

Propriétés de détection et de correction des erreurs

Un mot de code peut être considéré comme un point dans l' espace de dimension α et le code est le sous-ensemble de . Un code a une distance signifie que , il n'y a pas d'autre mot de code dans la boule de Hamming centrée à avec un rayon , qui est défini comme la collection de mots de dimension α dont la distance de Hamming à n'est pas supérieure à . De même, avec une distance (minimum) a les propriétés suivantes : ${\displaystyle c\in \Sigma ^{n <semantics> <mrow> <mstyle> <mi>c</mi> <mo>∈</mo> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle c\in \Sigma ^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma ^{n <semantics> <mrow> <mstyle> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle \Sigma ^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ ${\displaystyle \Sigma ^{n <semantics> <mrow> <mstyle> <msup> <mi>Σ</mi> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle \Sigma ^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$ ${\displaystyle \forall c\in {\mathcal {C <semantics> <mrow> <mstyle> <mi>∀</mi> <mi>c</mi> <mo>∈</mo> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \forall c\in {\mathcal {C}}}</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-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle 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-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ ${\displaystyle d <semantics> <mrow> <mstyle> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle d}</annotation> </semantics> </math><img src=$

${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ ${\displaystyle d-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</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-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle d-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$
${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ ${\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor <semantics> <mrow> <mstyle> <mstyle> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor }</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-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor <semantics> <mrow> <mstyle> <mstyle> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor }</annotation> </semantics> </math><img src=$ ${\displaystyle y <semantics> <mrow> <mstyle> <mi>y</mi> </mstyle> </mrow> <annotation>{\displaystyle y}</annotation> </semantics> </math><img src=$ ${\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor <semantics> <mrow> <mstyle> <mstyle> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor }</annotation> </semantics> </math><img src=$ ${\displaystyle y <semantics> <mrow> <mstyle> <mi>y</mi> </mstyle> </mrow> <annotation>{\displaystyle y}</annotation> </semantics> </math><img src=$ ${\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor <semantics> <mrow> <mstyle> <mstyle> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor }</annotation> </semantics> </math><img src=$
Afin de décoder en présence de plus de 10 erreurs, on peut utiliser le décodage de liste ou le décodage de vraisemblance maximale . ${\displaystyle (d-1)/2 <semantics> <mrow> <mstyle> <mo>(</mo> <mi>d</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle (d-1)/2}</annotation> </semantics> </math><img src=$
${\displaystyle {\mathcal {C <semantics> <mrow> <mstyle> <mrow> <mrow> <mi>C</mi> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\mathcal {C}}}</annotation> </semantics> </math><img src=$ effacement, on entend que la position du symbole effacé est connue. La correction peut être réalisée par décodage par passage : lors du passage, la position effacée est remplie par le symbole et la correction d'erreur est effectuée. Il doit y avoir un passage pour lequel le nombre d'erreurs ne dépasse pas et donc les effacements peuvent être corrigés. ${\displaystyle d-1 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle d-1}</annotation> </semantics> </math><img src=$ ${\displaystyle q <semantics> <mrow> <mstyle> <mi>q</mi> </mstyle> </mrow> <annotation>{\displaystyle q}</annotation> </semantics> </math><img src=$ ${\displaystyle i^{th <semantics> <mrow> <mstyle> <msup> <mi>i</mi> <mrow> <mi>t</mi> <mi>h</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle i^{th}}</annotation> </semantics> </math><img src=$ ${\displaystyle i^{th <semantics> <mrow> <mstyle> <msup> <mi>i</mi> <mrow> <mi>t</mi> <mi>h</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle i^{th}}</annotation> </semantics> </math><img src=$ ${\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor <semantics> <mrow> <mstyle> <mstyle> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>d</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mstyle> </mstyle> </mrow> <annotation>{\displaystyle extstyle \left\lfloor {{d-1} \over 2} ight floor }</annotation> </semantics> </math><img src=$

Limites inférieures et supérieures des codes de blocs

Famille de codes

${\displaystyle C=\{C_{i}\}_{i\geq 1 <semantics> <mrow> <mstyle> <mi>C</mi> <mo>=</mo> <mo>{</mo> <msub> <mi>C</mi> <mrow> <mi>i</mi> </mrow> </msub> <msub> <mo>}</mo> <mrow> <mi>i</mi> <mo>≥</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C=\{C_{i}\}_{i\geq 1}}</annotation> </semantics> </math><img src=$ famille de codes , où est un code à croissance monotone . ${\displaystyle C_{i <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle (n_{i},k_{i},d_{i})_{q <semantics> <mrow> <mstyle> <mo>(</mo> <msub> <mi>n</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>k</mi> <mrow> <mi>i</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>d</mi> <mrow> <mi>i</mi> </mrow> </msub> <msub> <mo>)</mo> <mrow> <mi>q</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle (n_{i},k_{i},d_{i})_{q}}</annotation> </semantics> </math><img src=$ ${\displaystyle n_{i <semantics> <mrow> <mstyle> <msub> <mi>n</mi> <mrow> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle n_{i}}</annotation> </semantics> </math><img src=$

Le taux de la famille de codes C est défini comme ${\displaystyle R(C)=\lim _{i o \infty }{k_{i} \over n_{i <semantics> <mrow> <mstyle> <mi>R</mi> <mo>(</mo> <mi>C</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>lim</mo> <mrow> <mi>i</mi> <mo>→</mo> <mi>∞</mi> </mrow> </munder> <mrow> <mfrac> <msub> <mi>k</mi> <mrow> <mi>i</mi> </mrow> </msub> <msub> <mi>n</mi> <mrow> <mi>i</mi> </mrow> </msub> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle R(C)=\lim _{i o \infty }{k_{i} \over n_{i}}}</annotation> </semantics> </math><img src=$

La distance relative de la famille de codes C est définie comme ${\displaystyle \delta (C)=\lim _{i o \infty }{d_{i} \over n_{i <semantics> <mrow> <mstyle> <mi>δ</mi> <mo>(</mo> <mi>C</mi> <mo>)</mo> <mo>=</mo> <munder> <mo>lim</mo> <mrow> <mi>i</mi> <mo>→</mo> <mi>∞</mi> </mrow> </munder> <mrow> <mfrac> <msub> <mi>d</mi> <mrow> <mi>i</mi> </mrow> </msub> <msub> <mi>n</mi> <mrow> <mi>i</mi> </mrow> </msub> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \delta (C)=\lim _{i o \infty }{d_{i} \over n_{i}}}</annotation> </semantics> </math><img src=$

Pour explorer la relation entre et , un ensemble de limites inférieures et supérieures de codes de blocs sont connues. ${\displaystyle R(C) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>(</mo> <mi>C</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle R(C)}</annotation> </semantics> </math><img src=$ ${\displaystyle \delta (C) <semantics> <mrow> <mstyle> <mi>δ</mi> <mo>(</mo> <mi>C</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle \delta (C)}</annotation> </semantics> </math><img src=$

Hamming lié

{\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2} ight floor }{\binom {n}{i}}(q-1)^{i} ight] <semantics> <mrow> <mstyle> <mi>R</mi> <mo>≤</mo> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> </mrow> <mo>⋅</mo> <msub> <mi>log</mi> <mrow> <mi>q</mi> </mrow> </msub> <mo>⋅</mo> <mrow> <mo>[</mo> <mrow> <munderover> <mo>∑</mo> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mrow> <mo>⌊</mo> <mrow> <mfrac> <mrow> <mi>δ</mi> <mo>⋅</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>⌋</mo> </mrow> </mrow> </munderover> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> <mfrac> <mi>n</mi> <mi>i</mi> </mfrac> <mrow> <mo>)</mo> </mrow> </mrow> </mrow> <mo>(</mo> <mi>q</mi> <mo>−</mo> <mn>1</mn> <msup> <mo>)</mo> <mrow> <mi>i</mi> </mrow> </msup> </mrow> <mo>]</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2} ight floor }{\binom {n}{i}}(q-1)^{i} ight]}</annotation> </semantics> </math></span><img src=

Singleton lié

La limite du singleton est que la somme du taux et de la distance relative d'un code de bloc ne peut pas être beaucoup plus grande que 1 :

{\displaystyle R+\delta \leq 1+{\frac {1}{n <semantics> <mrow> <mstyle> <mi>R</mi> <mo>+</mo> <mi>δ</mi> <mo>≤</mo> <mn>1</mn> <mo>+</mo> <mrow> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle R+\delta \leq 1+{\frac {1}{n}}}</annotation> </semantics> </math></span><img src=

En d'autres termes, chaque code de bloc satisfait l'inégalité . Les codes de Reed-Solomon sont des exemples non triviaux de codes qui satisfont la limite du singleton avec égalité. ${\displaystyle k+d\leq n+1 <semantics> <mrow> <mstyle> <mi>k</mi> <mo>+</mo> <mi>d</mi> <mo>≤</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle k+d\leq n+1}</annotation> </semantics> </math><img src=$

Plotkin lié

Pour , . En d’autres termes, . ${\displaystyle q=2 <semantics> <mrow> <mstyle> <mi>q</mi> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle q=2}</annotation> </semantics> </math><img src=$ ${\displaystyle R+2\delta \leq 1 <semantics> <mrow> <mstyle> <mi>R</mi> <mo>+</mo> <mn>2</mn> <mi>δ</mi> <mo>≤</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle R+2\delta \leq 1}</annotation> </semantics> </math><img src=$ ${\displaystyle k+2d\leq n <semantics> <mrow> <mstyle> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mi>d</mi> <mo>≤</mo> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle k+2d\leq n}</annotation> </semantics> </math><img src=$

Pour le cas général, les limites de Plotkin suivantes sont valables pour tout objet de distance d : ${\displaystyle C\subseteq \mathbb {F} _{q}^{n <semantics> <mrow> <mstyle> <mi>C</mi> <mo>⊆</mo> <msubsup> <mrow> <mi>F</mi> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation>{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}</annotation> </semantics> </math><img src=$

Si ${\displaystyle d=\left(1-{1 \over q} ight)n,|C|\leq 2qn <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mi>q</mi> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> <mi>n</mi> <mo>,</mo> <mrow> <mo>|</mo> </mrow> <mi>C</mi> <mrow> <mo>|</mo> </mrow> <mo>≤</mo> <mn>2</mn> <mi>q</mi> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle d=\left(1-{1 \over q} ight)n,|C|\leq 2qn}</annotation> </semantics> </math><img src=$
Si $\left(1-{1 \over q} ight)n,|C|\leq {qd \over {qd-\left(q-1 ight)n d > (1 - \frac{1}{q}) n, | C | \leq \frac{q d}{q d - (q - 1) n}$ \gauche(1-{1 \sur q}\droite)n,|C|\leq {qd \sur {qd-\gauche(q-1\droite)n}}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c7f86db97e98cad2b6e5401d8cebaa8721477d1">

Pour tout code q -aire de distance , ${\displaystyle \delta <semantics> <mrow> <mstyle> <mi>δ</mi> </mstyle> </mrow> <annotation>{\displaystyle \delta }</annotation> </semantics> </math><img src=$ ${\displaystyle R\leq 1-\left({q \over {q-1}} ight)\delta +o\left(1 ight) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>≤</mo> <mn>1</mn> <mo>−</mo> <mrow> <mo>(</mo> <mrow> <mfrac> <mi>q</mi> <mrow> <mi>q</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>)</mo> </mrow> <mi>δ</mi> <mo>+</mo> <mi>o</mi> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle R\leq 1-\left({q \over {q-1}} ight)\delta +o\left(1 ight)}</annotation> </semantics> </math><img src=$

Lien Gilbert-Varshamov

${\displaystyle R\geq 1-H_{q}\left(\delta ight)-\epsilon <semantics> <mrow> <mstyle> <mi>R</mi> <mo>≥</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>H</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>δ</mi> <mo>)</mo> </mrow> <mo>−</mo> <mi>ϵ</mi> </mstyle> </mrow> <annotation>{\displaystyle R\geq 1-H_{q}\left(\delta ight)-\epsilon }</annotation> </semantics> </math><img src=$ q -aire. ${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta ight) <semantics> <mrow> <mstyle> <mn>0</mn> <mo>≤</mo> <mi>δ</mi> <mo>≤</mo> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mi>q</mi> </mfrac> </mrow> <mo>,</mo> <mn>0</mn> <mo>≤</mo> <mi>ϵ</mi> <mo>≤</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>H</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>δ</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta ight)}</annotation> </semantics> </math><img src=$ ${\displaystyle H_{q}\left(x ight)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x ight)\cdot \log _{q}{\left(1-x ight) <semantics> <mrow> <mstyle> <msub> <mi>H</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>x</mi> <mo>)</mo> </mrow> <mtext> </mtext> <mrow> <mover> <mo>=</mo> <munder> <mrow></mrow> <mrow> <mi>d</mi> <mi>e</mi> <mi>f</mi> </mrow> </munder> </mover> </mrow> <mtext> </mtext> <mo>−</mo> <mi>x</mi> <mo>⋅</mo> <msub> <mi>log</mi> <mrow> <mi>q</mi> </mrow> </msub> <mo>⁡</mo> <mrow> <mfrac> <mi>x</mi> <mrow> <mi>q</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>−</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mrow> <mo>)</mo> </mrow> <mo>⋅</mo> <msub> <mi>log</mi> <mrow> <mi>q</mi> </mrow> </msub> <mo>⁡</mo> <mrow> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mi>x</mi> </mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle H_{q}\left(x ight)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x ight)\cdot \log _{q}{\left(1-x ight)}}</annotation> </semantics> </math><img src=$

Johnson lié

Définir . Soit le nombre maximal de mots de code dans une boule de Hamming de rayon e pour tout code de distance d . ${\displaystyle J_{q}\left(\delta ight)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q} ight)\left(1-{\sqrt {1-{q\delta \over {q-1}}}} ight) <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>δ</mi> <mo>)</mo> </mrow> <mtext> </mtext> <mrow> <mover> <mo>=</mo> <munder> <mrow></mrow> <mrow> <mi>d</mi> <mi>e</mi> <mi>f</mi> </mrow> </munder> </mover> </mrow> <mtext> </mtext> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mn>1</mn> <mi>q</mi> </mfrac> </mrow> </mrow> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <msqrt> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mrow> <mi>q</mi> <mi>δ</mi> </mrow> <mrow> <mi>q</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> </mrow> </msqrt> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle J_{q}\left(\delta ight)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q} ight)\left(1-{\sqrt {1-{q\delta \over {q-1}}}} ight)}</annotation> </semantics> </math><img src=$
${\displaystyle J_{q}\left(n,d,e ight) <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <mi>n</mi> <mo>,</mo> <mi>d</mi> <mo>,</mo> <mi>e</mi> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle J_{q}\left(n,d,e ight)}</annotation> </semantics> </math><img src=$ ${\displaystyle C\subseteq \mathbb {F} _{q}^{n <semantics> <mrow> <mstyle> <mi>C</mi> <mo>⊆</mo> <msubsup> <mrow> <mi>F</mi> </mrow> <mrow> <mi>q</mi> </mrow> <mrow> <mi>n</mi> </mrow> </msubsup> </mstyle> </mrow> <annotation>{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}</annotation> </semantics> </math><img src=$

Alors nous avons la borne de Johnson : , si ${\displaystyle J_{q}\left(n,d,e ight)\leq qnd <semantics> <mrow> <mstyle> <msub> <mi>J</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <mi>n</mi> <mo>,</mo> <mi>d</mi> <mo>,</mo> <mi>e</mi> </mrow> <mo>)</mo> </mrow> <mo>≤</mo> <mi>q</mi> <mi>n</mi> <mi>d</mi> </mstyle> </mrow> <annotation>{\displaystyle J_{q}\left(n,d,e ight)\leq qnd}</annotation> </semantics> </math><img src=$ ${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\, ight)=J_{q}\left({d \over n} ight) <semantics> <mrow> <mstyle> <mrow> <mfrac> <mi>e</mi> <mi>n</mi> </mfrac> </mrow> <mo>≤</mo> <mrow> <mfrac> <mrow> <mi>q</mi> <mo>−</mo> <mn>1</mn> </mrow> <mi>q</mi> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow> <mrow> <mn>1</mn> <mo>−</mo> <mrow> <msqrt> <mn>1</mn> <mo>−</mo> <mrow> <mfrac> <mi>q</mi> <mrow> <mi>q</mi> <mo>−</mo> <mn>1</mn> </mrow> </mfrac> </mrow> <mo>⋅</mo> <mrow> <mfrac> <mi>d</mi> <mi>n</mi> </mfrac> </mrow> </msqrt> </mrow> </mrow> <mspace></mspace> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <msub> <mi>J</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <mfrac> <mi>d</mi> <mi>n</mi> </mfrac> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\, ight)=J_{q}\left({d \over n} ight)}</annotation> </semantics> </math><img src=$

Liaison Elias–Bassalygo

{\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta ight) ight)+o\left(1 ight) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>=</mo> <mrow> <mfrac> <mrow> <msub> <mi>log</mi> <mrow> <mi>q</mi> </mrow> </msub> <mo>⁡</mo> <mrow> <mrow> <mo>|</mo> </mrow> <mi>C</mi> <mrow> <mo>|</mo> </mrow> </mrow> </mrow> <mi>n</mi> </mfrac> </mrow> <mo>≤</mo> <mn>1</mn> <mo>−</mo> <msub> <mi>H</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mrow> <msub> <mi>J</mi> <mrow> <mi>q</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>δ</mi> <mo>)</mo> </mrow> </mrow> <mo>)</mo> </mrow> <mo>+</mo> <mi>o</mi> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta ight) ight)+o\left(1 ight)}</annotation> </semantics> </math></span><img src=

Empaquetages et réseaux de sphères

Les codes en blocs sont liés au problème de l'empilement de sphères , qui a reçu une certaine attention au fil des ans. En deux dimensions, il est facile de le visualiser. Prenez un tas de pièces de monnaie à plat sur la table et poussez-les ensemble. Le résultat est un motif hexagonal comme un nid d'abeille. Mais les codes en blocs reposent sur davantage de dimensions qui ne peuvent pas être facilement visualisées. Le puissant code Golay utilisé dans les communications dans l'espace lointain utilise 24 dimensions. S'il est utilisé comme code binaire (ce qui est généralement le cas), les dimensions font référence à la longueur du mot de code tel que défini ci-dessus.

La théorie du codage utilise le modèle de sphère à N dimensions. Par exemple, combien de pièces de monnaie peuvent être empilées dans un cercle sur une table ou en 3 dimensions, combien de billes peuvent être empilées dans un globe. D'autres considérations entrent en jeu dans le choix d'un code. Par exemple, l'empilement d'hexagones dans la contrainte d'une boîte rectangulaire laissera de l'espace vide aux coins. Au fur et à mesure que les dimensions augmentent, le pourcentage d'espace vide diminue. Mais à certaines dimensions, l'empilement utilise tout l'espace et ces codes sont les codes dits parfaits. Il existe très peu de ces codes.

Une autre propriété est le nombre de voisins qu'un seul mot de code peut avoir. Prenons encore l'exemple des centimes. Nous empilons d'abord les centimes dans une grille rectangulaire. Chaque centime aura 4 voisins proches (et 4 aux coins qui sont plus éloignés). Dans un hexagone, chaque centime aura 6 voisins proches. Respectivement, en trois et quatre dimensions, l'empilement maximal est donné par les 12 faces et les 24 cellules avec respectivement 12 et 24 voisins. Lorsque nous augmentons les dimensions, le nombre de voisins proches augmente très rapidement. En général, la valeur est donnée par les nombres de baisers .

Le résultat est que le nombre de façons dont le bruit peut amener le récepteur à choisir un voisin (et donc une erreur) augmente également. Il s'agit d'une limitation fondamentale des codes en blocs, et en fait de tous les codes. Il peut être plus difficile de provoquer une erreur sur un seul voisin, mais le nombre de voisins peut être suffisamment important pour que la probabilité d'erreur totale en souffre réellement.