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