Singleton lié - Singleton bound

Dans la théorie du codage , la borne Singleton , du nom de Richard Collom Singleton, est une borne supérieure relativement grossière de la taille d'un code de bloc arbitraire avec une longueur de bloc , une taille et une distance minimale . Il est également connu sous le nom de Joshibound . prouvé par Joshi (1958) et même plus tôt par Komamiya (1953) . ${\style d'affichage C}$${\style d'affichage n}$${\style d'affichage M}$${\style d'affichage d}$

Déclaration du lié

La distance minimale d'un ensemble de mots de code de longueur est définie comme ${\style d'affichage C}$${\style d'affichage n}$

${\displaystyle d=\min _{\{x,y\in C:x\neq y\}}d(x,y)}$

où est la distance de Hamming entre et . L'expression représente le nombre maximal de mots de code possibles dans un code de bloc -aire de longueur et de distance minimale  . ${\style d'affichage d(x,y)}$${\style d'affichage x}$${\style d'affichage y}$${\style d'affichage A_{q}(n,d)}$${\style d'affichage q}$${\style d'affichage n}$${\style d'affichage d}$

Ensuite, la borne de Singleton indique que

${\displaystyle A_{q}(n,d)\leq q^{n-d+1}.}$

Preuve

Observez d'abord que le nombre de mots -aires de longueur est , puisque chaque lettre d'un tel mot peut prendre une valeur différente, indépendamment des lettres restantes. ${\style d'affichage q}$${\style d'affichage n}$${\style d'affichage q^{n}}$${\style d'affichage q}$

Soit maintenant un code de bloc arbitraire de distance minimale . De toute évidence, tous les mots de code sont distincts. Si nous perforons le code en supprimant les premières lettres de chaque mot de code, alors tous les mots de code résultants doivent toujours être différents deux à deux, car tous les mots de code d'origine ont une distance de Hamming au moins les uns des autres. Ainsi, la taille du code modifié est la même que celle du code d'origine. ${\style d'affichage C}$${\style d'affichage q}$${\style d'affichage d}$${\style d'affichage c\en C}$${\style d'affichage d-1}$${\style d'affichage C}$${\style d'affichage d}$

Les mots de code nouvellement obtenus ont chacun une longueur

${\style d'affichage n-(d-1)=n-d+1}$,

et ainsi, il peut y en avoir au maximum . Étant donné qu'elle était arbitraire, cette limite doit être valable pour le plus grand code possible avec ces paramètres, ainsi : ${\displaystyle q^{n-d+1}}$${\style d'affichage C}$

${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$

Codes linéaires

Si est un code linéaire avec une longueur de bloc , une dimension et une distance minimale sur le corps fini avec des éléments, alors le nombre maximal de mots de code est et la borne de Singleton implique : ${\style d'affichage C}$${\style d'affichage n}$${\style d'affichage k}$${\style d'affichage d}$${\style d'affichage q}$${\displaystyle q^{k}}$

${\displaystyle q^{k}\leq q^{n-d+1}}$,

pour que

${\displaystyle k\leq n-d+1}$,

qui s'écrit généralement comme

${\displaystyle d\leq n-k+1}$.

Dans le cas du code linéaire, une preuve différente de la borne de Singleton peut être obtenue en observant que le rang de la matrice de contrôle de parité est . Une autre preuve simple découle de l'observation que les lignes de toute matrice génératrice sous forme standard ont au plus un poids . ${\displaystyle nk}$${\style d'affichage n-k+1}$

Histoire

La citation habituelle donnée pour ce résultat est Singleton (1964) , mais a été prouvée plus tôt par Joshi (1958) . Selon Welsh (1988 , p. 72) le résultat peut être trouvé dans un article de 1953 de Komamiya (1953)

Codes MDS

Les codes de blocs linéaires qui atteignent l'égalité dans la limite Singleton sont appelés codes MDS (distance maximale séparable) . Des exemples de tels codes incluent des codes qui n'ont que deux mots de code (le mot tout zéro et le mot tout un, ayant ainsi une distance minimale ), les codes qui utilisent la totalité de (distance minimale 1), les codes avec un seul symbole de parité (minimum distance 2) et leurs doubles codes . Ceux-ci sont souvent appelés codes MDS triviaux . ${\style d'affichage n}$${\displaystyle (\mathbb {F} _{q})^{n}}$

Dans le cas des alphabets binaires, seuls les codes MDS triviaux existent.

Des exemples de codes MDS non triviaux incluent les codes Reed-Solomon et leurs versions étendues.

Les codes MDS sont une classe importante de codes de bloc car, pour un et , ils ont les plus grandes capacités de correction et de détection d'erreurs. Il existe plusieurs manières de caractériser les codes MDS : ${\style d'affichage n}$${\style d'affichage k}$

Théorème : Soit un code [ ] linéaire sur . Les éléments suivants sont équivalents : ${\style d'affichage C}$${\style d'affichage n,k,d}$${\displaystyle \mathbb {F} _{q}}$

• ${\style d'affichage C}$ est un code MDS.
• Toutes les colonnes d'une matrice génératrice pour sont linéairement indépendantes .${\style d'affichage k}$${\style d'affichage C}$
• Toutes les colonnes d'une matrice de contrôle de parité pour sont linéairement indépendantes.${\displaystyle nk}$${\style d'affichage C}$
• ${\displaystyle C^{\perp }}$ est un code MDS.
• Si est une matrice génératrice de sous forme standard, alors chaque sous-matrice carrée de est non singulière .${\style d'affichage G=(I|A)}$${\style d'affichage C}$${\style d'affichage A}$
• Étant donné toutes les positions de coordonnées, il existe un mot de code (poids minimum) dont le support est précisément ces positions.${\style d'affichage d}$

La dernière de ces caractérisations permet, en utilisant les identités MacWilliams , une formule explicite pour la distribution de poids complète d'un code MDS.

Théorème : Soit un code MDS linéaire [ ] sur . Si désigne le nombre de mots de code en poids , alors ${\style d'affichage C}$${\style d'affichage n,k,d}$${\displaystyle \mathbb {F} _{q}}$${\style d'affichage A_{w}}$${\style d'affichage C}$${\style d'affichage w}$

${\displaystyle A_{w}={\binom {n}{w}}\sum _{j=0}^{wd}(-1)^{j}{\binom {w}{j}}(q ^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{wd}(-1)^{j}{ \binom {w-1}{j}}q^{wdj}.}$

Arcs en géométrie projective

L'indépendance linéaire des colonnes d'une matrice génératrice d'un code MDS permet une construction de codes MDS à partir d'objets en géométrie projective finie . Soit l'espace projectif fini de dimension (géométrique) sur le corps fini . Soit un ensemble de points dans cet espace projectif représenté avec des coordonnées homogènes . Former la matrice dont les colonnes sont les coordonnées homogènes de ces points. Puis, ${\style d'affichage PG(N,q)}$${\style d'affichage N}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle K=\{P_{1},P_{2},\dots ,P_{m}\}}$${\style d'affichage (N+1)\fois m}$${\style d'affichage G}$

Théorème : est un -arc (spatial) si et seulement si est la matrice génératrice d'un code MDS sur .${\style d'affichage K}$${\style d'affichage m}$${\style d'affichage G}$${\style d'affichage [m,N+1,mN]}$${\displaystyle \mathbb {F} _{q}}$

Voir également

• Gilbert-Varshamov lié
• Plotkin lié
• Hamming lié
• Johnson lié
• Griesmer lié

Remarques

Les références

• Joshi, DD (1958), "A Note on Upper Bounds for Minimum Distance Codes", Information and Control , 1 (3) : 289-295, doi : 10.1016/S0019-9958(58)80006-6
• Komamiya, Y. (1953), "Application des mathématiques logiques à la théorie de l'information", Proc. 3e Japon. Nat. Cong. Appl. Math. : 437
• Ling, San ; Xing, Chaoping (2004), Théorie du codage / Un premier cours , Cambridge University Press, ISBN 0-521-52923-9
• MacWilliams, FJ ; Sloane, NJA (1977), La théorie des codes de correction d'erreurs , North-Holland, pp.  33, 37 , ISBN 0-444-85193-3
• Pless, Vera (1998), Introduction à la théorie des codes de correction d'erreurs (3e éd.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Codage et théorie de l'information , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
• Singleton, RC (1964), "Codes q-naires à distance maximale", IEEE Trans. Inf. Théorie , 10 (2) : 116–118, doi : 10.1109/TIT.1964.1053661
• Vermani, LR (1996), Éléments de théorie du codage algébrique , Chapman & Hall
• Gallois, Dominic (1988), Codes et cryptographie , Oxford University Press, ISBN 0-19-853287-3

Lectures complémentaires

• JH van Lint (1992). Introduction à la théorie du codage . GTM . 86 (2e éd.). Springer-Verlag. p. 61 . ISBN 3-540-54894-7.
• Niederreiter, Harald ; Xing, Chaoping (2001). "6. Applications à la théorie du codage algébrique". Points rationnels sur des courbes sur des corps finis. Théorie et applications . Série de notes de cours de la London Mathematical Society. 285 . Cambridge : Cambridge University Press . ISBN 0-521-66543-4. Zbl  0971.11033 .