Оценка Гилберта–Варшамова для линейных кодов

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

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

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

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

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

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

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

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

Официальное доказательство:

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

Линейный код определяется его порождающей матрицей , которую мы выбираем случайной. $k\times n$ матрица генератора; то есть матрица $kn$ элементы, которые выбираются независимо и равномерно по полю $\mathbb {F} _{q}$.

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

${\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}}$

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

По неравенству Буля имеем:

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

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

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

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

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

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

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

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

$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 ))}$

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

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

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

Комментарии

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

См. также

• Граница Гилберта–Варшамова благодаря конструкции Гилберта для общего кода
• Хэмминг связан
• Вероятностный метод

Ссылки

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