Singleton grænse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. oktober 2016; checks kræver 2 redigeringer .

Singleton-grænsen (opkaldt efter R.C. Singleton) sætter en grænse for magten af en kode med tegn fra længdefeltet og minimum Hamming-afstand . $C$ $\mathbb {F} _{q}$ $n$ $d$

Lad betegne den maksimalt mulige kardinalitet af -ary længde kode ( -ary code er en kode over et felt af elementer). Lad den mindste Hamming-afstand mellem to kodeord være , det vil sige for alle to kodeord og . $A_q(n,\;d)$ $q$ $n$ $q$ $q$ $d$ $\mathrm D_H(w,\;w')\geqslant d$ $w$ $w'$

Derefter

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

Bevis

Først og fremmest skal du bemærke, at den øvre grænse for den maksimale kardinalitet af enhver -ær længdekode er lig med , da hver komponent i et givet kodeord kan antage en af forskellige værdier uafhængigt af de andre komponenter. $q$ $n$ $q^{n}$ $q$

Lad være en -ic-kode. Så er alle ordene i koden forskellige fra hinanden. Hvis vi sletter de første tegn i hvert ord, skal alle resterende kodeord forblive forskellige, da Hamming-afstanden mellem kodeord er mindst . Derfor forblev kodens kraft efter sletning af tegn den samme. $C$ $q$ $c\in C$ $d-1$ $C$ $d$ $d-1$

Ny ordlængde

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

og dermed den maksimalt mulige kardinalitet af en sådan kode er

q^{n-d+1}.

Herfra følger den øvre grænse for magten for den originale kode :

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

Linjekoder

I tilfælde af linjekoder kan man skrive Singleton bundet som

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

eller

k\leqslant n-d+1.

Lineære koder, som ligheden gælder , kaldes adskillelige koder med en maksimal afstand eller MDS-koder. Velkendte repræsentanter for denne familie af koder er Reed-Solomon-koden og koderne dannet af den. $k=n-d+1$

Litteratur

RC Singleton. Maksimal afstand q-nary koder. IEEE Transactions on Information Theory , 10:116-118 [1, 11], 1964.
Y. Komamiya. Anvendelse af logisk matematik til informationsteori. Proceedings of the 3rd Japanese National Congress for Applied Mathematics , 437 [1], 1953.

Singleton grænse

Bevis

Linjekoder

Litteratur

Se også