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 ${\displaystyle C}$ de comprimento ${\displaystyle n}$, tamanho ${\displaystyle r}$ e distância mínima ${\displaystyle d}$.

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

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

onde ${\displaystyle d(x,y)}$ é a distância de Hamming entre ${\displaystyle x}$ e ${\displaystyle y}$. A expressão ${\displaystyle 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 ${\displaystyle n}$ e distância mínima ${\displaystyle d}$.

Então a cota de Singleton estabelece que

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

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

Considere então um código de bloco q-ário ${\displaystyle C}$ arbitrário para o qual a distância mínima seja ${\displaystyle d}$. Claramente todas as palavras ${\displaystyle c\in C}$ são distintas. Se forem removidas as primeiras ${\displaystyle 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 ${\displaystyle C}$ possuíam distância de Hamming no mínimo ${\displaystyle d}$ umas das outras. Então o tamanho do código permanece inalterado.

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

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

e então pode haver no máximo

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

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

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

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 ${\displaystyle (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.^[1]

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

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

• 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  A referência emprega parâmetros obsoletos |coautor= (ajuda)
• L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.