Chenar singleton

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 octombrie 2016; verificările necesită 2 modificări .

Limita Singleton (numită după R.C. Singleton) pune o limită a puterii unui cod cu caractere din câmpul de lungime și distanța Hamming minimă . $C$ $\mathbb {F} _{q}$ $n$ $d$

Să notăm cardinalitatea maximă posibilă a codului de lungime -ary ( codul -ary este un cod peste un câmp de elemente). Fie distanța Hamming minimă dintre două cuvinte cod , adică pentru oricare două cuvinte cod și . $A_q(n,\;d)$ $q$ $n$ $q$ $q$ $d$ $\mathrm D_H(w,\;w')\geqslant d$ $w$ $w'$

Apoi

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

Dovada

În primul rând, rețineți că limita superioară a cardinalității maxime a oricărui cod de lungime -ary este egală cu , deoarece fiecare componentă a unui anumit cuvânt de cod poate lua una dintre valori diferite, independent de celelalte componente. $q$ $n$ $q^{n}$ $q$

Fie un cod -ic. Apoi toate cuvintele din cod sunt diferite unele de altele. Dacă ștergem primele caractere ale fiecărui cuvânt, atunci toate cuvintele de cod rămase trebuie să rămână diferite, deoarece distanța Hamming dintre cuvintele de cod este de cel puțin . Prin urmare, puterea codului după ștergerea caracterelor a rămas aceeași. $C$ $q$ $c\în C$ $d-1$ $C$ $d$ $d-1$

Lungime nouă a cuvântului

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

și deci cardinalitatea maximă posibilă a unui astfel de cod este

q^{n-d+1}.

Din aceasta urmează limita superioară a puterii pentru codul original :

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

Coduri de linie

În cazul codurilor de linie , se poate scrie limita Singleton ca

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

k\leqslant n-d+1.

Codurile liniare pentru care este valabilă egalitatea se numesc coduri separabile cu o distanță maximă sau coduri MDS. Reprezentanți cunoscuți ai acestei familii de coduri sunt codul Reed-Solomon și codurile formate din acesta. $k=n-d+1$

Literatură

RC Singleton. Distanța maximă q-nary coduri. IEEE Transactions on Information Theory , 10:116-118 [1, 11], 1964.
Y. Komamiya. Aplicarea matematicii logice la teoria informației. Proceedings of the 3rd Japanese National Congress for Applied Mathematics , 437 [1], 1953.

Chenar singleton

Dovada

Coduri de linie

Literatură

Vezi și