Хорошие коды декодируются линейными цепями?

27

Я ищу коды с исправлением ошибок следующего типа:

  • двоичные коды с постоянной скоростью,

  • декодируется из некоторой постоянной доли ошибок декодером, реализуемым в виде логической схемы размера , где N - длина кодирования.O(N)N

Немного предыстории:

Заранее спасибо!

Энди Друкер
источник
2
Энди, по совпадению, я тоже сталкивался с этим вопросом около года назад и после недолгих поисков пришел к выводу, что вопрос открыт. Итак, мне также любопытно, если ответ известен.
Арнаб
2
Этот отчет ECCC только что вышел. Я не проверял, но я ожидаю, что это также дает цепь. Θ(NlogN)
Питер Шор
Возможно ли декодирование в модели AWGN или в двоичной модели? O(N)
T ....
Хорошие двоичные коды, которые полностью линейно кодируются ( ) и могут быть декодированы и достигают частоты ошибок 2 - N, где N - длина блока кода, вероятно, требуют некоторой принципиально новой идеи. На данный момент лучшее из этого - в соответствии с теоремой 1 в arxiv.org/pdf/1304.4321v2.pdf . Давайте посмотрим , если кто - то улучшает 2 - Н 0,49 до 2 - N 1 - М в там в N 1 + ε кодирование и декодирование время , которое я считаю , должно быть возможно (даже сO(N)2NN12N0.492N1μN1+ϵ ). Тем не менее, доведение ϵ до 0 может потребовать больше, чем несколько хитростей. μ=0ϵ0
T ....
Посмотрите на коды Expander. Эти коды обеспечивают линейное временное кодирование и декодирование. Линейность зависит от размера кодового слова. Но я не уверен, что их можно декодировать с помощью линейных схем.
Вивек Багария

Ответы:

2

Rϵ>0n(1R)(1ϵ)nln1ϵ


{1} Luby, Michael G. и соавт. «Практические коды устойчивости к потерям». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf

Ари Трахтенберг
источник