Граница Гилберта – Варшамова - Gilbert–Varshamov bound

В теория кодирования, то Граница Гилберта – Варшамова (из-за Эдгар Гилберт^[1] и независимо Ром Варшамов^[2]) является пределом параметров a (не обязательно линейный ) код. Иногда его называют Гилберт–Шеннон –Варшамова граница (или Граница GSV), но название «граница Гилберта – Варшамова» является наиболее популярным. Варшамов доказал эту оценку, используя вероятностный метод для линейных кодов. Подробнее об этом доказательстве см. Оценка Гильберта – Варшамова для линейных кодов.

Заявление о привязке

Позволять

${\displaystyle A_{q}(n,d)}$

обозначают максимально возможный размер q-арный код ${\displaystyle C}$ с длиной п и минимальное расстояние Хэмминга d (а q-ary код - это код над поле ${\displaystyle \mathbb {F} _{q}}$ из q элементы).

Потом:

${\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

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

Позволять ${\displaystyle C}$ быть кодом длины ${\displaystyle n}$ и минимум Расстояние Хэмминга ${\displaystyle d}$ имеющий максимальный размер:

${\displaystyle |C|=A_{q}(n,d).}$

Тогда для всех ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ , существует хотя бы одно кодовое слово ${\displaystyle c_{x}\in C}$ такое, что расстояние Хэмминга ${\displaystyle d(x,c_{x})}$ между ${\displaystyle x}$ и ${\displaystyle c_{x}}$ удовлетворяет

${\displaystyle d(x,c_{x})\leqslant d-1}$

так как иначе мы могли бы добавить Икс к коду при сохранении минимального расстояния Хэмминга кода ${\displaystyle d}$ - противоречие о максимальности ${\displaystyle |C|}$.

Следовательно, весь ${\displaystyle \mathbb {F} _{q}^{n}}$ содержится в союз из всех мячи радиуса ${\displaystyle d-1}$ имея свои центр некоторые ${\displaystyle c\in C}$ :

${\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).}$

Теперь у каждого шара есть размер

${\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

поскольку мы можем разрешить (или выберите ) вплоть до ${\displaystyle d-1}$ из ${\displaystyle n}$ компоненты кодового слова для отклонения (от значения соответствующего компонента шара центр ) одному из ${\displaystyle (q-1)}$ возможные другие значения (напомним: код q-ичный: принимает значения в ${\displaystyle \mathbb {F} _{q}^{n}}$). Отсюда выводим

${\displaystyle q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\left|\bigcup _{c\in C}B(c,d-1)\right|\leqslant \sum _{c\in C}|B(c,d-1)|=|C|\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}$

То есть:

${\displaystyle A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}$

Усовершенствование в случае основной мощности

За q простая степень, можно улучшить привязку к ${\displaystyle A_{q}(n,d)\geq q^{k}}$ куда k - наибольшее целое число, для которого

${\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}.}$

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

• Граница синглтона
• Граница Хэмминга
• Джонсон связан
• Плоткин граница
• Граница Грисмера
• Граница Грея – Рэнкина
• Оценка Гильберта – Варшамова для линейных кодов
• Элиас-Бассалыго

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

1. Гилберт, Э. (1952), «Сравнение сигнальных алфавитов», Технический журнал Bell System, 31: 504–522, Дои:10.1002 / j.1538-7305.1952.tb01393.x.
2. Варшамов, Р. Р. (1957), "Оценка количества сигналов в кодах с исправлением ошибок", Докл. Акад. АН СССР, 117: 739–741.