Зяблов связан

В теории кодирования граница Зяблова — это нижняя граница скорости $r$ и относительное расстояние $\delta$ которые достижимы с помощью каскадных кодов .

Заявление о границах

Связанное утверждает, что существует семейство $q$-арные (сцепленные, линейные) коды со скоростью $r$ и относительное расстояние $\delta$ в любое время

$r\leqslant \max \limits _{0\leqslant r'\leqslant 1-H_{q}(\delta )}r'\cdot \left(1-{\delta \over {H_{q}^{-1}(1-r')}}\right)$,

где $H_{q}$это $q$-арная функция энтропии

$H_{q}(x)=x\log _{q}(q-1)-x\log _{q}(x)-(1-x)\log _{q}(1-x)$.

Рисунок 1: Граница Зяблова. Для сравнения также отображается граница GV (которая дает достижимые параметры для общих кодов, которые не могут быть эффективно декодируемы).

Описание

Граница получается путем рассмотрения диапазона параметров, которые можно получить путем объединения «хорошего» внешнего кода. $C_{out}$ с «хорошим» внутренним кодом $C_{in}$. В частности, мы предполагаем, что внешний код соответствует границе Синглтона , т. е. он имеет скорость $r_{out}$и относительное расстояние $\delta _{out}$ удовлетворяющий $r_{out}+\delta _{out}=1$. Коды Рида-Соломона представляют собой семейство таких кодов, которые можно настроить на любую скорость. $r_{out}\in (0,1)$ и относительное расстояние $1-r_{out}$ (хотя и в алфавите, таком же большом, как длина кодового слова). Мы предполагаем, что внутренний код удовлетворяет границе Гилберта–Варшамова , т.е. имеет скорость $r_{in}$и относительное расстояние $\delta _{in}$ удовлетворяющий $r_{in}+H_{q}(\delta _{in})\geq 1$. Известно, что случайные линейные коды с высокой вероятностью удовлетворяют этому свойству, а явный линейный код, удовлетворяющий этому свойству, можно найти методом перебора (для которого требуется полином по времени от размера пространства сообщений).

Конкатенация $C_{out}$ и $C_{in}$, обозначенный $C_{out}\circ C_{in}$, имеет рейтинг $r=r_{in}\cdot r_{out}$ и относительное расстояние $\delta =\delta _{out}\cdot \delta _{in}\geq (1-r_{out})\cdot H_{q}^{-1}(1-r_{in}).$

Выражение $r_{out}$ как функция $\delta ,r_{in}$,

$r_{out}\geq 1-{\frac {\delta }{H^{-1}(1-r_{in})}}$

Затем оптимизация по выбору $r_{in}$, мы видим, что объединенный код может удовлетворить,

$r\geq \max \limits _{0\leq r_{in}\leq {1-H_{q}(\delta )}}r_{in}\cdot \left(1-{\delta \over {H_{q}^{-1}(1-r_{in})}}\right)$

См. рисунок 1, где показан график этой границы.

Заметим, что оценка Зяблова означает, что для любого $\delta >0$, существует (сцепленный) код с положительной скоростью и положительным относительным расстоянием.

Примечания

Мы можем построить код, который достигает границы Зяблова за полиномиальное время. В частности, мы можем построить явный асимптотически хороший код (по некоторым алфавитам) за полиномиальное время.

Линейные коды помогут нам завершить доказательство приведенного выше утверждения, поскольку линейные коды имеют полиномиальное представление. Пусть Cout будет $[N,K]_{Q}$ исправления ошибок Рида – Соломона , где Код $N=Q-1$ (оценочные баллы $\mathbb {F} _{Q}^{*}$ с $Q=q^{k}$, затем $k=\theta (\log N)$.

Нам нужно построить внутренний код, который лежит на границе Гилберта-Варшамова . Это можно сделать двумя способами

1. Выполнить исчерпывающий поиск по всем порождающим матрицам до тех пор, пока требуемое свойство не будет удовлетворено для $C_{in}$. Это связано с тем, что граница Варшамова утверждает, что существует линейный код, лежащий на границе Гилберта-Варшамона, который будет принимать $q^{O(kn)}$ время. С использованием $k=rn$ мы получаем $q^{O(kn)}=q^{O(k^{2})}=N^{O(\log N)}$, который сверху ограничен $nN^{O(\log nN)}$, квазиполиномиальная оценка времени.
2. Чтобы построить $C_{in}$ в $q^{O(n)}$ время и использование $(nN)^{O(1)}$ время в целом. Этого можно добиться, используя метод условного ожидания при доказательстве того, что случайный линейный код с высокой вероятностью лежит на границе.

Таким образом, мы можем построить код, который достигает границы Зяблова за полиномиальное время.

См. также

• Дорога Гилберта-Варшамова
• Синглтон связан

Ссылки и внешние ссылки

• Конспект лекций Массачусетского технологического института по основной теории кодирования - доктор Мадху Судан
• Конспект лекций по теории кодирования в Университете Буффало - доктор Атри Рудра
• Конспект лекций Вашингтонского университета по теории кодирования - доктор Венкатесан Гурусвами