Dual of BCH - независимый источник - Dual of BCH is an independent source

Определенная семья Коды BCH обладают особенно полезным свойством, которое рассматривается как линейные операторы, их дуальные операторы превращает их вклад в ${displaystyle ell }$-Мудрый независимый источник. То есть набор векторов из входа векторное пространство отображаются на ${displaystyle ell }$разумно независимый источник. Доказательство этого факта ниже в виде следующей леммы и следствия полезно при дерандомизации алгоритма для ${displaystyle 1-2^{-ell }}$-приближение к МАКСЭКСАТ.

Лемма

Позволять ${displaystyle Csubseteq F_{2}^{n}}$ линейный код такой, что ${displaystyle C^{perp }}$ имеет расстояние больше, чем ${displaystyle ell +1}$. потом ${displaystyle C}$ является ${displaystyle ell }$разумно независимый источник.

Доказательство леммы

Достаточно показать, что при любом ${displaystyle k imes l}$ матрица M, куда k Больше или равно л, такие что ранг M является л, для всех ${displaystyle xin F_{2}^{k}}$, ${displaystyle xM}$ принимает каждое значение в ${displaystyle F_{2}^{l}}$ такое же количество раз.

С M имеет звание л, мы можем написать M как две матрицы одинакового размера, ${displaystyle M_{1}}$ и ${displaystyle M_{2}}$, куда ${displaystyle M_{1}}$ имеет ранг, равный л. Это означает, что ${displaystyle xM}$ можно переписать как ${displaystyle x_{1}M_{1}+x_{2}M_{2}}$ для некоторых ${displaystyle x_{1}}$ и ${displaystyle x_{2}}$.

Если мы рассмотрим M написано относительно основы, где первый л строки - единичная матрица, тогда ${displaystyle x_{1}}$ везде есть нули ${displaystyle M_{2}}$ имеет ненулевые строки, и ${displaystyle x_{2}}$ везде есть нули ${displaystyle M_{1}}$ имеет ненулевые строки.

Теперь любое значение у, куда ${displaystyle y=xM}$, можно записать как ${displaystyle x_{1}M_{1}+x_{2}M_{2}}$ для некоторых векторов ${displaystyle x_{1},x_{2}}$.

Мы можем переписать это как:

${displaystyle x_{1}M_{1}=y-x_{2}M_{2}}$

Фиксация стоимости последнего ${displaystyle k-l}$ координаты${displaystyle x_{2}in F_{2}^{k}}$ (обратите внимание, что есть ровно ${displaystyle 2^{k-l}}$такой выбор), мы можем снова переписать это уравнение как:

${displaystyle x_{1}M_{1}=b}$ для некоторых б.

С ${displaystyle M_{1}}$ имеет ранг, равный л, есть ровно одно решение ${displaystyle x_{1}}$, поэтому общее количество решений ровно ${displaystyle 2^{k-l}}$, доказывая лемму.

Следствие

Напомним, что BCH_2,м,d является ${displaystyle [n=2^{m},n-1-lceil {d-2}/2ceil m,d]_{2}}$ линейный код.

Позволять ${displaystyle C^{perp }}$ быть BCH_{2, журналп,ℓ+1}. потом ${displaystyle C}$ является ${displaystyle ell }$разумно независимый источник размера ${displaystyle O(n^{lfloor ell /2floor })}$.

Доказательство следствия

Измерение d из C просто ${displaystyle lceil {(ell +1-2)/{2}}ceil log n+1}$. Так ${displaystyle d=lceil {(ell -1)}/2ceil log n+1=lfloor ell /2floor log n+1}$.

Итак, мощность ${displaystyle C}$ рассматривается как набор просто${displaystyle 2^{d}=O(n^{lfloor ell /2floor })}$, доказывая Следствие.

Рекомендации

Заметки по теории кодирования в Университете Буффало

Заметки по теории кодирования в MIT