Dobre kody dekodowalne przez obwody liniowe?

27

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

2

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

2

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

Odpowiedzi:

2

$R$ $\epsilon>0$ $n$ $(1-R)(1-\epsilon)$ $n \ln \frac{1}{\epsilon}$

{1} Luby, Michael G. i in. „Praktyczne kody odporne na straty”. Materiały z dwudziestego dziewiątego dorocznego sympozjum ACM na temat teorii komputerów. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

— Ari Trachtenberg
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.