Singleton gräns

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 oktober 2016; kontroller kräver 2 redigeringar .

Singleton-gränsen (uppkallad efter R.C. Singleton) sätter en gräns för kraften i en kod med tecken från längdfältet och minsta Hamming-avstånd . $C$ $\mathbb {F} _{q}$ $n$ $d$

Låt beteckna den maximala möjliga kardinaliteten av -ary längdkod ( -ary code är en kod över ett fält av element). Låt det minsta Hamming-avståndet mellan två kodord vara , det vill säga för alla två kodord och . $A_q(n,\;d)$ $q$ $n$ $q$ $q$ $d$ $\mathrm D_H(w,\;w')\geqslant d$ $w$ $w'$

Sedan

A_q(n,\;d)\leqslant q^{n-d+1}.

Bevis

Först och främst, notera att den övre gränsen för den maximala kardinaliteten för någon -är längdkod är lika med , eftersom varje komponent i ett givet kodord kan anta ett av olika värden oberoende av de andra komponenterna. $q$ $n$ $q^{n}$ $q$

Låt vara en -ic-kod. Då är alla ord i koden olika. Om vi raderar de första tecknen i varje ord, måste alla återstående kodord förbli olika, eftersom Hamming-avståndet mellan kodorden är minst . Därför förblev kraften i koden efter borttagningen av tecken densamma. $C$ $q$ $c\in C$ $d-1$ $C$ $d$ $d-1$

Ny ordlängd

n-(d-1)=n-d+1,

och därför är den maximala möjliga kardinaliteten för en sådan kod

q^{n-d+1}.

Från detta följer den övre gränsen för makten för den ursprungliga koden :

A_q(n,\;d)\leqslant q^{n-d+1}.

Radkoder

När det gäller linjekoder kan man skriva Singleton bound som

q^k\leqslant q^{n-d+1}

eller

k\leqslant n-d+1.

Linjära koder för vilka likheten gäller kallas separerbara koder med ett maximalt avstånd eller MDS-koder. Välkända representanter för denna kodfamilj är Reed-Solomon-koden och koderna som bildas av den. $k=n-d+1$

Litteratur

RC Singleton. Maximalt avstånd q-nary-koder. IEEE Transactions on Information Theory , 10:116-118 [1, 11], 1964.
Y. Komamiya. Tillämpning av logisk matematik på informationsteori. Proceedings of the 3rd Japanese National Congress for Applied Mathematics , 437 [1], 1953.

Singleton gräns

Bevis

Radkoder

Litteratur

Se även