Я ищу коды с исправлением ошибок следующего типа:
двоичные коды с постоянной скоростью,
декодируется из некоторой постоянной доли ошибок декодером, реализуемым в виде логической схемы размера , где N - длина кодирования.
Немного предыстории:
Шпильман, в линейном время кодируемого и декодируемых коды , исправляющие ошибки , дал коды декодируемый в время в модели RAM логарифмических затрат , а также проигрываться O ( N журнал N ) -sized цепей.
Guruswami и Indyk дали улучшенную конструкцию в кодируемых / декодируемых кодах за линейное время с почти оптимальной скоростью . Они не анализируют полученную сложность схемы, хотя я считаю, что она также равна .
Заранее спасибо!
co.combinatorics
it.information-theory
coding-theory
Энди Друкер
источник
источник
Ответы:
{1} Luby, Michael G. и соавт. «Практические коды устойчивости к потерям». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений. ACM, 1997: http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/losscodes.pdf
источник