De bons codes décodables par des circuits de taille linéaire?

27

Je recherche des codes correcteurs d'erreurs du type suivant:

  • codes binaires à débit constant,

  • décodable à partir d'une fraction constante d'erreurs, par un décodeur réalisable en tant que circuit booléen de taille , où est la longueur de codage.O(N)N

Quelques antécédents:

Merci d'avance!

Andy Drucker
la source
2
Et par coïncidence, j'ai également rencontré ce problème il y a environ un an et après une brève recherche, j'ai conclu que la question était ouverte. Donc, je suis également curieux de savoir si une réponse est connue.
arnab
2
Ce rapport des CETC vient de sortir. Je n'ai pas vérifié, mais je m'attends à ce qu'il donne également le circuit . Θ(NlogN)
Peter Shor
Le décodage réalisable dans le modèle AWGN ou le modèle binaire? O(N)
T ....
De bons codes binaires qui sont complètement linéaires ( ) codables et décodables et atteignent un taux d'erreur où est la longueur de bloc du code nécessite probablement une idée fondamentalement nouvelle. Jusqu'à présent, le meilleur est dans la ligne du théorème dans arxiv.org/pdf/1304.4321v2.pdf . Voyons si quelqu'un améliore le temps de codage et de décodage de à en qui, je pense, devrait être possible (même avec ). Cependant, amener à peut nécessiter plus de quelques astuces. O(N)2NN12N0.492N1μN1+ϵμ=0ϵ0
T ....
Jetez un œil aux codes Expander. Ces codes réalisent un codage et un décodage temporels linéaires. La linéarité correspond à la taille du mot de code. Mais je ne sais pas s'ils peuvent être décodés à l'aide de circuits linéaires.
Vivek Bagaria

Réponses:

2

Vous devriez regarder les codes Tornado {1}, qui, pour tout et et suffisamment grand peuvent être conçus pour récupérer (avec une forte probabilité) d'une perte de fraction de bits dans le temps proportionnelle à (voir Théorème 1 dans {1}).Rϵ>0n(1R)(1ϵ)nln1ϵ


{1} Luby, Michael G. et al. "Codes pratiques résistants aux pertes." Actes du vingt-neuvième symposium annuel de l'ACM sur la théorie de l'informatique. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

Ari Trachtenberg
la source