Gute Codes, die von linearen Schaltkreisen decodiert werden können?

27

Ich suche nach fehlerkorrigierenden Codes des folgenden Typs:

  • Binärcodes mit konstanter Rate,

  • decodierbar aus einem konstanten Bruchteil von Fehlern durch einen Decodierer, der als eine Boolesche Schaltung der Größe implementiert werden kann , wobei die Codierungslänge ist.O(N)N

Einige Hintergrundinformationen:

Danke im Voraus!

Andy Drucker
quelle
2
Andy, zufällig bin ich auch vor einem Jahr auf dieses Problem gestoßen und bin nach einer kurzen Suche zu dem Schluss gekommen, dass die Frage offen war. Ich bin also auch neugierig, ob eine Antwort bekannt ist.
Arnab
2
Dieser ECCC-Bericht ist gerade erschienen. Ich habe es nicht überprüft, aber ich gehe davon aus, dass es auch eine -Schaltung gibt. Θ(NlogN)
Peter Shor
Ist eine -Decodierung im AWGN-Modell oder im Binärmodell möglich? O(N)
T ....
Gute Binärcodes, die vollständig linear zeitlich ( ) codierbar und decodierbar sind und eine Fehlerrate von wobei die Blocklänge des Codes ist, erfordern wahrscheinlich eine grundlegend neue Idee. Das bisher beste ist in Anlehnung an Satz in arxiv.org/pdf/1304.4321v2.pdf . Mal sehen, ob jemand die auf verbessert, in Codierungs- und Decodierungszeit, von der ich glaube, dass sie sein sollte möglich (auch mit ). Wenn Sie jedoch auf möglicherweise mehr als ein paar Tricks erforderlich. 2 - N N 1O(N)2NN1 2 - N 1 - μ N 1 + μ = 0 02N0.492N1μN1+ϵμ=0ϵ0
T ....
Schauen Sie sich die Expander-Codes an. Diese Codes erzielen eine lineare Zeitcodierung und -decodierung. Die Linearität richtet sich nach der Größe des Codeworts. Ich bin mir aber nicht sicher, ob sie mit linearen Schaltkreisen dekodiert werden können.
Vivek Bagaria

Antworten:

2

Sie sollten bei Tornado - Codes aussehen {1}, die für jede und und groß genug , um gestaltet werden kann , sich zu erholen (mit hoher Wahrscheinlichkeit) von einem Verlust von einem Bruchteil von Bits in der Zeit proportional zu (siehe Satz 1 in {1}).ϵ > 0 n ( 1 - R ) ( 1 - ϵ ) n ln 1Rϵ>0n(1R)(1ϵ)nln1ϵ


{1} Luby, Michael G. et al. "Praktische verlustresistente Codes." Vorträge des neunundzwanzigsten jährlichen ACM-Symposiums zur Theorie des Rechnens. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

Ari Trachtenberg
quelle