Bons códigos decodificáveis ​​por circuitos de tamanho linear?

27

Estou procurando códigos de correção de erros do seguinte tipo:

  • códigos binários com taxa constante,

  • decodificável a partir de uma fração constante de erros, por um decodificador implementável como um circuito booleano de tamanho , em que N é o comprimento da codificação.O(N)N

Alguns antecedentes:

Desde já, obrigado!

Andy Drucker
fonte
2
Andy, coincidentemente, eu também me deparei com essa questão há um ano e, após uma breve pesquisa, concluí que a pergunta estava aberta. Então, eu também estou curioso se uma resposta é conhecida.
arnab
2
Este relatório do ECCC acabou de ser publicado. Eu não verifiquei, mas espero que também dê um circuito . Θ(NlogN)
quer
A decodificação de possível no modelo AWGN ou no modelo binário? O(N)
T ....
Bons códigos binários que são codificados e decodificáveis ​​por tempo completamente linear ( ) e atingem uma taxa de erro 2 - N em que N é o comprimento do bloco do código provavelmente requerem alguma idéia fundamentalmente nova. O melhor até agora está na linha do teorema 1 em arxiv.org/pdf/1304.4321v2.pdf . Vamos ver se alguém melhora a 2 - N 0,49 para 2 - N 1 - μ lá em N 1 + ε codificação e descodificação tempo que creio deve ser possível (mesmo comO(N)2NN12-N0,492-N1-μN1+ϵ ). No entanto, trazer ϵ para 0 pode precisar de mais do que alguns truques. μ=0 0ϵ0 0
T ....
Dê uma olhada nos códigos do expansor. Esses códigos atingem codificação e decodificação de tempo linear. A linearidade é escrita com o tamanho da palavra de código. Mas não tenho certeza se eles podem ser decodificados usando circuitos lineares.
Vivek Bagaria

Respostas:

2

Você deve observar os códigos Tornado {1}, que, para qualquer e ϵ > 0 e n suficientemente grande, podem ser projetados para se recuperar (com alta probabilidade) de uma perda de uma fração ( 1 - R ) ( 1 - ϵ ) de bits no tempo proporcional a n ln 1Rϵ>0 0n(1-R)(1-ϵ) (consulte o Teorema 1 em {1}).nem1ϵ


{1} Luby, Michael G., et al. "Códigos práticos de resiliência a perdas." Anais do vigésimo nono simpósio anual da ACM sobre Teoria da Computação. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

Ari Trachtenberg
fonte