Cota de Singleton

Na teoria de códigos, a cota de Singleton, assim chamada em referência a R.C. Singleton, é uma limitação relativamente rude no tamanho de um código de blocos $C$ de comprimento $n$, tamanho $r$ e distância mínima $d$.

Determinação da cota

A distância mínima de um conjunto $C$ de palavras-código de comprimento $n$ é definido como

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

onde $d(x,y)$ é a distância de Hamming entre $x$ e $y$. A expressão $A_{q}(n,d)$ representa o maior número possível de palavras-código em um código de blocos q-ários de comprimento $n$ e distância mínima $d$.

Então a cota de Singleton estabelece que

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

Demonstração

Primeiramente observe que há $q^{n}$ palavras q-árias de comprimento $n$, uma vez que cada letra em tais palavras pode assumir um entre $q$ valores diferentes, independentemente das letras restantes.

Considere então um código de bloco q-ário $C$ arbitrário para o qual a distância mínima seja $d$. Claramente todas as palavras $c\in C$ são distintas. Se forem removidas as primeiras $d-1$ letras de cada palavra-código, então todas as palavras-código restantes devem ainda ser distintas duas a duas, já que todas as palavras-código originais de $C$ possuíam distância de Hamming no mínimo $d$ umas das outras. Então o tamanho do código permanece inalterado.

Cada uma das novas palavras-código obtidas possui comprimento

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

e então pode haver no máximo

$q^{n-d+1}$

delas. Assim, o código original $C$ compartilha a mesma limitação em seu tamanho $|C|$:

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

Códigos MDS

Códigos de bloco que atingem a igualdade na cota de Singleton são chamados Códigos MDS (separáveis pela distância máxima). Exemplos de tais códigos incluem códigos que são gerados apenas por uma palavra-código (distância mínima n), códigos que usam $(F_{q})^{n}$ inteiramente (distância mínima 1), códigos com um único símbolo de paridade (distância mínima 2) e seus códigos duais. Estes são chamados frequentemente de códigos MDS triviais.

No caso de alfabetos binários, existem apenas os códigos MDS triviais.

Exemplos de códigos MDS não triviais incluem os códigos de Reed–Solomon e suas versões estendidas.

Ver também

• Cota de Gilbert-Varshamov
• Cota de Plotkin
• Cota de Hamming
• Cota de Johnson
• Cota de Griesmer

Referências

• R.C. Singleton (1964). «Maximum distance q-nary codes». IEEE Trans. Inf. Theory. 10: 116–118. doi:10.1109/TIT.1964.1053661 

Further reading

• J.H. van Lint (1992). Introduction to Coding Theory. Col: GTM. 86 2nd ed. [S.l.]: Springer-Verlag. p. 61. ISBN 3-540-54894-7 
• F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. [S.l.]: North-Holland. pp. 33,37. ISBN 0-444-85193-3 
• L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.