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

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

Заявление о границах

Напомним, что код имеет минимальное расстояние $d$ если любые два элемента в коде находятся на расстоянии не менее $d$ отдельно. Позволять

A_{q}(n,d)

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

Затем:

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

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

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

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

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

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

поскольку в противном случае мы могли бы добавить x в код, сохраняя при этом минимальное расстояние Хэмминга кода. $d$ – противоречие о максимальности $|C|$ .

Отсюда и весь $\mathbb {F} _{q}^{n}$ содержится в объединении всех шаров радиуса $d-1$ имеющий свой центр в каком-то $c\in C$ :

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

Теперь каждый шар имеет размер

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

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

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}

То есть:

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

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

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

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

См. также

Ссылки

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

[1] Гилберт, Э.Н. (1952), «Сравнение сигнальных алфавитов», Технический журнал Bell System , 31 (3): 504–522, doi : 10.1002/j.1538-7305.1952.tb01393.x .

[2] Варшамов Р. Р. (1957), "Оценка числа сигналов в кодах, исправляющих ошибки", Докл. Акад. Наук СССР , 117 : 739–741 .

[ 1 ]

[ 2 ]