Cota de Singleton

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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| \le A_q(n,d) \leq q^{n-d+1}.

Códigos MDS[editar | editar código-fonte]

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.1

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

Ver também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Veja por exemplo Vermani (1996), Proposição 9.2.
  2. Veja por exemplo MacWilliams & Sloane, Capítulo 11.

Referências[editar | editar código-fonte]

Further reading