Теория кодирования. Лекция 8

От декодирования списком и к однозначному декодированию

Теорема Зяблова и Пинскера о существование линейного кода размерности k с кодовыми словами длины n, допускающего декодирование списком размера O(1) на расстоянии e (достаточное условие V(n,e)<2(1-ε)(n-k)​​​​​​​ для произвольного ε>0). Коммуникационная задача передачи -битного x от Алисы к Бобу при условии, что Бобу заранее известно некоторое  на расстоянии  от . Нижняя оценка коммуникационной сложности h(a)n - o(n) (для a<1/2). Детерминированный 3-раундовый детерминированный коммуникационный протокол с коммуникационной сложностью h(a)n + o(n) для a<1/2 .

Страница лекции на сайте Computer Science клуба