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 de comprimento , tamanho e distância mínima .

Determinação da cota[editar | editar código-fonte]

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

onde é a distância de Hamming entre e . A expressão representa o maior número possível de palavras-código em um código de blocos q-ários de comprimento e distância mínima .

Então a cota de Singleton estabelece que

Demonstração[editar | editar código-fonte]

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

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

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

e então pode haver no máximo

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

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 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]

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

Further reading