Singleton bunden - Singleton bound

I kodningsteori , den bundna Singleton , uppkallad efter Richard Collom Singleton, är en relativt oren övre gräns för storleken av en godtycklig blockkod med blocklängden , storlek och minsta avstånd . Det är också känt som Joshibound . bevisad av Joshi (1958) och ännu tidigare av Komamiya (1953) . ${\ displaystyle C}$${\ displaystyle n}$${\ displaystyle M}$${\ displaystyle d}$

Uttalande av den bundna

Minsta avståndet för en uppsättning kodord med längd definieras som ${\ displaystyle C}$${\ displaystyle n}$

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

var är Hamming -avståndet mellan och . Uttrycket representerar det maximala antalet möjliga kodord i en -ary -blockkod av längd och minsta avstånd  . ${\ displaystyle d (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle A_ {q} (n, d)}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle d}$

Sedan säger Singleton bound att

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

Bevis

Observera först att antalet -ary -ord av längd är , eftersom varje bokstav i ett sådant ord kan ta ett av olika värden, oberoende av de återstående bokstäverna. ${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle q^{n}}$${\ displaystyle q}$

Låt oss nu vara en godtycklig -ary blockkod med minimiavstånd . Alla kodord är uppenbara. Om vi punkterar koden genom att radera de första bokstäverna i varje kodord, måste alla resulterande kodord fortfarande vara parvis olika, eftersom alla de ursprungliga kodorden har Hammingavstånd åtminstone från varandra. Således är storleken på den ändrade koden densamma som den ursprungliga koden. ${\ displaystyle C}$${\ displaystyle q}$${\ displaystyle d}$${\ displaystyle c \ i C}$${\ displaystyle d-1}$${\ displaystyle C}$${\ displaystyle d}$

De nyligen erhållna kodorden har vardera längd

${\ displaystyle n- (d-1) = n-d+1}$,

och därmed kan det finnas de flesta av dem. Eftersom det var godtyckligt måste denna gräns hålla den största möjliga koden med dessa parametrar, alltså: ${\ displaystyle q^{n-d+1}}$${\ displaystyle C}$

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

Linjära koder

Om är en linjär kod med blocklängd , dimension och minimiavstånd över det ändliga fältet med element, då är det maximala antalet kodord och Singleton -gränsen innebär: ${\ displaystyle C}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle q}$${\ displaystyle q^{k}}$

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

så att

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

som vanligtvis skrivs som

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

I det linjära kodfallet kan ett annat bevis på Singleton -gränsen erhållas genom att observera att rangordningen för paritetskontrollmatrisen är . Ett annat enkelt bevis följer av att observera att raderna i vilken generatormatris som helst i standardform har högst vikt . ${\ displaystyle nk}$${\ displaystyle n-k+1}$

Historia

Den vanliga citeringen för detta resultat är Singleton (1964) , men bevisades tidigare av Joshi (1958) . Enligt Welsh (1988 , s. 72) finns resultatet i ett 1953 -papper från Komamiya (1953)

MDS -koder

Linjära blockkoder som uppnår jämlikhet i Singleton -gränsen kallas MDS -koder (maximalt avstånd som kan separeras) . Exempel på sådana koder inkluderar koder som bara har två kodord ( hel- nollordet och hel -ett-ordet med minimalt avstånd ), koder som använder hela (minsta avstånd 1), koder med en enda paritetssymbol (minimum avstånd 2) och deras dubbla koder . Dessa kallas ofta triviala MDS -koder. ${\ displaystyle n}$${\ displaystyle (\ mathbb {F} _ {q})^{n}}$

När det gäller binära alfabet finns endast triviala MDS -koder.

Exempel på icke-triviala MDS-koder inkluderar Reed-Solomon-koder och deras utökade versioner.

MDS -koder är en viktig klass av blockkoder eftersom de för de fasta och har de största felkorrigerings- och detekteringsfunktionerna. Det finns flera sätt att karakterisera MDS -koder: ${\ displaystyle n}$${\ displaystyle k}$

Sats : Låt vara en linjär [ ] kod över . Följande är likvärdiga: ${\ displaystyle C}$${\ displaystyle n, k, d}$${\ displaystyle \ mathbb {F} _ {q}}$

• ${\ displaystyle C}$ är en MDS -kod.
• Alla kolumner i en generatormatris för är linjärt oberoende .${\ displaystyle k}$${\ displaystyle C}$
• Alla kolumner i en paritetskontrollmatris för är linjärt oberoende.${\ displaystyle nk}$${\ displaystyle C}$
• ${\ displaystyle C^{\ perp}}$ är en MDS -kod.
• Om är en generatormatris för i standardform, då varje kvadrat submatris av är nonsingular .${\ displaystyle G = (I | A)}$${\ displaystyle C}$${\ displaystyle A}$
• Med tanke på alla koordinatpositioner finns det ett (minsta vikt) kodord vars stöd är just dessa positioner.${\ displaystyle d}$

Den sista av dessa karakteriseringar tillåter, med hjälp av MacWilliams -identiteter , en uttrycklig formel för den fullständiga viktfördelningen av en MDS -kod.

Sats : Låt vara en linjär [ ] MDS -kod över . Om anger antalet kodord i vikt , då ${\ displaystyle C}$${\ displaystyle n, k, d}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle A_ {w}}$${\ displaystyle C}$${\ displaystyle 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}.}$

Bågar i projektiv geometri

Det linjära oberoende av kolumnerna i en generatormatris av en MDS -kod tillåter konstruktion av MDS -koder från objekt i begränsad projektiv geometri . Låt vara det ändliga projektiva utrymmet av (geometrisk) dimension över det ändliga fältet . Låt oss vara en uppsättning punkter i detta projektiva utrymme representerade med homogena koordinater . Forma matrisen vars kolumner är de homogena koordinaterna för dessa punkter. Sedan, ${\ displaystyle PG (N, q)}$${\ displaystyle N}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle K = \ {P_ {1}, P_ {2}, \ dots, P_ {m} \}}$${\ displaystyle (N+1) \ gånger m}$${\ displaystyle G}$

Sats : är en (spatial) -arc om och bara om generatormatrisen för en MDS -kod är över .${\ displaystyle K}$${\ displaystyle m}$${\ displaystyle G}$${\ displaystyle [m, N+1, mN]}$${\ displaystyle \ mathbb {F} _ {q}}$

Se även

• Gilbert – Varshamov bunden
• Plotkin bunden
• Hamming bunden
• Johnson bunden
• Griesmer bunden

Anteckningar

Referenser

• 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), "Tillämpning av logisk matematik på informationsteori", Proc. 3: e Japan. Nat. Cong. Appl. Matematik. : 437
• Ling, San; Xing, Chaoping (2004), Coding Theory / A First Course , Cambridge University Press, ISBN 0-521-52923-9
• MacWilliams, FJ ; Sloane, NJA (1977), The Theory of Error-Correcting Codes , North-Holland, s.  33, 37 , ISBN 0-444-85193-3
• Pless, Vera (1998), Introduktion till teorin om felkorrigerande koder (3: e upplagan), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Coding and Information Theory , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
• Singleton, RC (1964), "Maximum distance q-nary codes", IEEE Trans. Inf. Teori , 10 (2): 116–118, doi : 10.1109/TIT.1964.1053661
• Vermani, LR (1996), Elements of algebraic coding theory , Chapman & Hall
• Welsh, Dominic (1988), Codes and Cryptography , Oxford University Press, ISBN 0-19-853287-3

Vidare läsning

• JH van Lint (1992). Introduktion till kodteori . GTM . 86 (andra upplagan). Springer-Verlag. sid. 61 . ISBN 3-540-54894-7.
• Niederreiter, Harald ; Xing, Chaoping (2001). "6. Applikationer till algebraisk kodningsteori". Rationella punkter på kurvor över ändliga fält. Teori och tillämpningar . London Mathematical Society Lecture Note Series. 285 . Cambridge : Cambridge University Press . ISBN 0-521-66543-4. Zbl  0971.11033 .