Dobre kody dekodowalne przez obwody liniowe?

Szukam kodów korygujących błędy następującego typu:

kody binarne o stałej szybkości,
dekodowalny z pewnej stałej części błędów za pomocą dekodera możliwego do zaimplementowania jako logiczny obwód o rozmiarze , gdzie jest długością kodowania. $O(N)$ $N$

Trochę tła:

Spielman, w liniowych kodowalnych i dekodowalnych kodach korygujących błędy , dał kody dekodowalne w czasie w modelu RAM o koszcie logarytmicznym , a także dekodowalne przez obwody o rozmiarze . $O(N)$ $O(N \log N)$
Guruswami i Indyk dali ulepszoną konstrukcję w kodowaniu / dekodowaniu w czasie liniowym z prawie optymalną szybkością . Nie analizują wynikowej złożoności obwodu, chociaż uważam, że jest to również . $\Theta(N \log N)$

Z góry dziękuję!

co.combinatorics it.information-theory coding-theory Andy Drucker
źródło

Andy, przypadkiem, natknąłem się na ten problem około rok temu i po krótkiej analizie doszedłem do wniosku, że pytanie jest otwarte. Jestem więc ciekawy, czy odpowiedź jest znana.

arnab

Właśnie ukazał się ten raport ECCC . Nie sprawdziłem, ale spodziewam się, że daje również obwód

Θ (N \log N)

$\Theta(N \log N)$

Peter Shor,

Czy dekodowanie

możliwe w modelu AWGN lub modelu binarnym?

O (N)

$O(N)$

T ....

O (N)

$O(N)$

2^{- N}

$2^{-N}$

N

$N$

1

$1$

2^{- N^{0.49}}

$2^{-N^{0.49}}$

2^{- N^{1 - μ}}

$2^{-N^{1-\mu}}$

N^{1 + ϵ}

$N^{1+\epsilon}$

μ = 0

$\mu=0$

ϵ

$\epsilon$

0

$0$

Zobacz kody ekspanderów. Kody te zapewniają liniowe kodowanie i dekodowanie w czasie. Liniowość zależy od wielkości słowa kodowego. Ale nie jestem pewien, czy można je zdekodować za pomocą obwodów liniowych.

Vivek Bagaria

Dobre kody dekodowalne przez obwody liniowe?

Odpowiedzi: