A taxa de correção de erros é enganosa

10

Na teoria da codificação, 'quão bom é um código' significa quantos erros de canal podem ser corrigidos, ou melhor, o nível máximo de ruído com o qual o código pode lidar.

Para obter códigos melhores, os códigos são projetados usando um alfabeto grande (em vez de um código binário). E então, o código é bom se puder lidar com uma grande taxa de "símbolos" errados.

Por que isso não é considerado trapaça? Quero dizer, não devemos nos preocupar apenas com o que acontece quando "traduzimos" cada símbolo em uma string binária? A "taxa de erro de bit" é diferente da taxa de "erro de símbolo". Por exemplo, a taxa de erro de bits não pode exceder 1/2, enquanto (se eu entendi isso corretamente), com alfabeto grande o suficiente, o erro de símbolo pode ir até . Isso ocorre porque restringimos artificialmente o canal para alterar apenas "símbolos" em vez de bits ou porque o código é realmente melhor?1 1-ϵ

information-theory coding-theory Tocou.
fonte
11
Por que você se restringiria a códigos binários se o seu meio / tecnologia de transmissão puder lidar com muito mais?
Raphael
@Raphael Ajudaria se você pudesse justificar seu argumento com alguns exemplos práticos de tecnologias da vida real que lidam com símbolos não binários e publique isso como resposta.
Mohammad Alaggan 24/03
@ M.Alaggan: Não sou especialista nisso; Eu acho que se você pode codificar 0/1 em uma portadora de onda, também pode codificar muito mais símbolos, transmitindo mais informações por intervalo de tempo. Surpreenderia-me se a tecnologia moderna não fizesse isso (pense em multiplexação de código), mas não posso citar um exemplo concreto.
Raphael
@Raphael Acho que você está certo, os atuais canais de comunicação digital funcionam com símbolos maiores, mas não mais do que, digamos, 256 bits por símbolo (o que é bastante raro para redes sem fio, mas pode ser comum para cabos). Mas o tamanho do símbolo é limitado a tamanhos muito pequenos e não pode (praticamente) crescer à vontade.
Ran G.

Respostas:

8

Muitos códigos amplamente usados ​​para dados binários são códigos concatenados, compostos usando dois códigos de correção de erros. O código interno está sobre um alfabeto binário e o código externo está sobre um alfabeto cujos símbolos correspondem às palavras de código do código interno. Isso permite que você use o poder superior de tamanhos maiores de alfabeto para codificar mensagens binárias sem "trapacear".

A definição padrão de distância mínima é natural quando se considera códigos concatenados, bem como na teoria dos códigos em tamanhos grandes de alfabeto. Seria apenas "trapaça" se você usasse esses números para comparar um código binário com um código de alfabeto grande que codifica a entrada binária sem usar também um código interno; os teóricos da codificação são espertos o bastante para não fazer isso (e acredito que, desde que os códigos concatenados foram inventados, os códigos de alfabeto grande costumam ser usados ​​junto com um código interno, mas os códigos de alfabeto grande também são muito bons para corrigir erros em canais rajados, como como CDs, pois um grande número de erros consecutivos de bits afetará apenas alguns "símbolos").

Peter Shor
fonte
Peter, obrigado pela resposta. Para um código concatenado, não é verdade que a taxa de erro (bit) não pode exceder 1/2? então esse método nos permite chegar mais perto de 1/2, mantendo a decodificação eficiente, certo?
Ran G.
@Ran: Para um código binário , a taxa de erro de bits não pode exceder 1/2. Códigos concatenados não precisam ser binários. Mas isso é nitpicking; seu comentário está essencialmente correto.
Peter Shor