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

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

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

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

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

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

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

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

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

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

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

Линейный код определяется его матрицей-генератором , которую мы выбираем в качестве случайной матрицы-генератора; то есть матрица элементов, которые выбираются независимо и равномерно по полю . ${\displaystyle k\times n}$ ${\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}}$

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

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

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

Комментарии

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

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

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

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

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

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