Оценка Гильберта – Варшамова для линейных кодов - Gilbert–Varshamov bound for linear codes

В Оценка Гильберта – Варшамова для линейных кодов относится к общему Граница Гилберта – Варшамова, что дает нижнюю оценку максимального числа элементов в код исправления ошибок заданной длины блока и минимального Вес Хэмминга через поле ${\displaystyle \mathbb {F} _{q}}$. Это может быть преобразовано в утверждение о максимальной скорости кода с данной длиной и минимальным расстоянием. Оценка Гилберта – Варшамова для линейные коды утверждает существование q-арные линейные коды для любого относительного минимального расстояния, меньшего заданной границы, которые одновременно имеют высокую скорость. Доказательство существования использует вероятностный метод, и, следовательно, не является конструктивным. Граница Гилберта – Варшамова является наиболее известной с точки зрения относительного расстояния для кодов по алфавитам размером меньше 49.^{[нужна цитата ]} Для более крупных алфавитов Коды гоппы иногда достигают асимптотически лучшего компромисса между скоростью и расстоянием, чем дается границей Гилберта-Варшамова.^[1]

Граничная теорема Гилберта – Варшамова.

Теорема: Позволять ${\displaystyle q\geqslant 2}$. Для каждого ${\displaystyle 0\leqslant \delta <1-{\tfrac {1}{q}}}$ и ${\displaystyle 0<\varepsilon \leqslant 1-H_{q}(\delta ),}$ существует код со скоростью ${\displaystyle R\geqslant 1-H_{q}(\delta )-\varepsilon }$ и относительное расстояние ${\displaystyle \delta .}$

Здесь ${\displaystyle H_{q}}$ это q-арная энтропийная функция, определяемая следующим образом:

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

Приведенный выше результат был доказан Эдгар Гилберт для общего кода с использованием жадный метод в качестве здесь. За линейный код, Ром Варшамов доказано с помощью вероятностный метод для случайного линейного кода. Это доказательство будет показано в следующей части.

Доказательство высокого уровня:

Чтобы показать существование линейного кода, который удовлетворяет этим ограничениям, вероятностный метод используется для построения случайного линейного кода. В частности, линейный код выбирается случайным образом путем выбора случайный матрица генератора ${\displaystyle G}$ в котором элемент выбран равномерно по полю ${\displaystyle \mathbb {F} _{q}^{n}}$. Так же Расстояние Хэмминга линейного кода равен минимальному весу кодовое слово. Итак, чтобы доказать, что линейный код, порожденный ${\displaystyle G}$ имеет расстояние Хэмминга ${\displaystyle d}$, мы покажем, что для любого ${\displaystyle m\in \mathbb {F} _{q}^{k}\smallsetminus \left\{0\right\},\operatorname {wt} (mG)\geq d}$ . Чтобы доказать это, мы докажем обратное; то есть вероятность того, что линейный код, сгенерированный ${\displaystyle G}$ имеет расстояние Хэмминга меньше, чем ${\displaystyle d}$ экспоненциально мала в ${\displaystyle n}$. Тогда вероятностным методом существует линейный код, удовлетворяющий теореме.

Формальное доказательство:

Используя вероятностный метод, чтобы показать, что существует линейный код, у которого расстояние Хэмминга больше, чем ${\displaystyle d}$, мы покажем, что вероятность что случайный линейный код, имеющий расстояние меньше, чем ${\displaystyle d}$ экспоненциально мала в ${\displaystyle n}$.

Мы знаем, что линейный код определяется с помощью матрица генератора. Итак, мы используем «матрицу генератора случайных чисел» ${\displaystyle G}$ как средство описания случайности линейного кода. Итак, матрица случайного генератора ${\displaystyle G}$ размера ${\displaystyle kn}$ содержит ${\displaystyle kn}$ элементы, которые выбираются независимо и равномерно по полю ${\displaystyle \mathbb {F} _{q}}$.

Напомним, что в линейный код, расстояние равно минимальному весу ненулевого кодового слова. Позволять ${\displaystyle \operatorname {wt} (y)}$ быть весом кодового слова ${\displaystyle y}$. Так

${\displaystyle {\begin{aligned}P&=\Pr _{{\text{random }}G}({\text{linear code generated by }}G{\text{ has distance}}<d)\\[6pt]&=\Pr _{{\text{random }}G}({\text{there exists a non-zero codeword }}y{\text{ in a linear code generated by }}G{\text{ such that }}\operatorname {wt} (y)<d)\\[6pt]&=\Pr _{{\text{random }}G}\left({\text{there exists }}0\neq m\in \mathbb {F} _{q}^{k}{\text{ such that }}\operatorname {wt} (mG)<d\right)\end{aligned}}}$

Последнее равенство следует из определения: если кодовое слово ${\displaystyle y}$ принадлежит линейному коду, порожденному ${\displaystyle G}$, тогда ${\displaystyle y=mG}$ для какого-то вектора ${\displaystyle m\in \mathbb {F} _{q}^{k}}$.

К Неравенство Буля, у нас есть:

${\displaystyle P\leqslant \sum _{0\neq m\in \mathbb {F} _{q}^{k}}\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d)}$

Теперь для данного сообщения ${\displaystyle 0\neq m\in \mathbb {F} _{q}^{k},}$ мы хотим вычислить

${\displaystyle W=\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d).}$

Позволять ${\displaystyle \Delta (m_{1},m_{2})}$ расстояние Хэмминга двух сообщений ${\displaystyle m_{1}}$ и ${\displaystyle m_{2}}$. Тогда для любого сообщения ${\displaystyle m}$, у нас есть: ${\displaystyle \operatorname {wt} (m)=\Delta (0,m)}$. Следовательно:

${\displaystyle W=\sum _{\{y\in \mathbb {F} _{q}^{n}|\Delta (0,y)\leqslant d-1\}}\Pr _{{\text{random }}G}(mG=y)}$

Из-за случайности ${\displaystyle G}$, ${\displaystyle mG}$ - равномерно случайный вектор из ${\displaystyle \mathbb {F} _{q}^{n}}$. Так

${\displaystyle \Pr _{{\text{random }}G}(mG=y)=q^{-n}}$

Позволять ${\displaystyle \operatorname {Vol} _{q}(r,n)}$ - объем шара Хэмминга радиуса ${\displaystyle r}$. Потом:^[2]

${\displaystyle P\leqslant q^{k}W=q^{k}\left({\frac {\operatorname {Vol} _{q}(d-1,n)}{q^{n}}}\right)\leqslant q^{k}\left({\frac {q^{nH_{q}(\delta )}}{q^{n}}}\right)=q^{k}q^{-n(1-H_{q}(\delta ))}}$

Выбирая ${\displaystyle k=(1-H_{q}(\delta )-\varepsilon )n}$, указанное выше неравенство принимает вид

${\displaystyle P\leqslant q^{-\varepsilon n}}$

Ну наконец то ${\displaystyle q^{-\varepsilon n}\ll 1}$, который экспоненциально мал по n, что мы и хотели раньше. Тогда вероятностным методом существует линейный код ${\displaystyle C}$ с относительным расстоянием ${\displaystyle \delta }$ и оценить ${\displaystyle R}$ по меньшей мере ${\displaystyle (1-H_{q}(\delta )-\varepsilon )}$, что завершает доказательство.

Комментарии

1. Приведенная выше конструкция Варшамова не является явной; то есть, в нем не указывается детерминированный метод построения линейного кода, удовлетворяющего границе Гилберта – Варшамова. Наивный способ сделать это - перебрать все матрицы генератора ${\displaystyle G}$ размера ${\displaystyle kn}$ над полем ${\displaystyle \mathbb {F} _{q}}$ и проверьте, удовлетворяет ли этот линейный код расстоянию Хэмминга. Это приводит к алгоритму экспоненциального времени для его реализации.
2. У нас также есть Строительство в Лас-Вегасе который берет случайный линейный код и проверяет, имеет ли этот код хорошее расстояние Хэмминга. Тем не менее, эта конструкция имеет экспоненциальное время работы.
3. При достаточно большом непростом q и некоторых диапазонах переменной δ оценка Гилберта-Варшамова улучшается с помощью Цфасман-Владут-Цинк.^[3]

Смотрите также

• Оценка Гилберта – Варшамова, полученная в результате конструкции Гильберта для общего кода
• Hamming Bound
• Вероятностный метод

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

1. Цфасман, M.A .; Владут, С.Г .; Цинк, Т. (1982). «Модульные кривые, кривые Шимуры и коды Гоппы лучше, чем граница Варшамова-Гилберта». Mathematische Nachrichten. 104.
2. Позднее неравенство происходит от верхняя граница объема шара Хэмминга В архиве 2013-11-08 в Wayback Machine
3. Стихтенот, Х. (2006). "Транзитивные и самодуальные коды, достигающие границы Цфасмана-Вла / spl breve / dut $ 80-Цинка". IEEE Transactions по теории информации. 52 (5): 2218–2224. Дои:10.1109 / TIT.2006.872986. ISSN  0018-9448.

• Лекция 11: Граница Гилберта – Варшамова. Курс теории кодирования. Профессор Атри Рудра
• Лекция 9: Оценка объема шара Хэмминга. Курс теории кодирования. Профессор Атри Рудра
• Примечания по теории кодирования: граница Гилберта – Варшамова. Венкатесан Гурусвами