WikiSort.ru - Не сортированное

Граница Варша́мова — Ги́лберта — неравенство, которое определяет предельные значения для параметров кодов (не обязательно линейных), полученное независимо Эдгаром Гилбертом^[en] и Ромом Варшамовым^[en]. Иногда употребляется название неравенство Гилберта — Шеннона — Варшамова, а в иноязычной научной литературе — неравенство Гилберта — Варшамова.

Формулировка

Пусть

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

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

Тогда

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

Когда ${\displaystyle q}$ является степенью простого числа, можно упростить неравенство до ${\displaystyle A_{q}(n,\;d)\geqslant q^{k}}$ , где ${\displaystyle k}$  — наибольшее целое число, для которого ${\displaystyle \displaystyle A_{q}(n,\;d)\geqslant \displaystyle {\frac {q^{n}}{\displaystyle \sum \limits _{j=0}^{d-2}\displaystyle {\binom {n-1}{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 x}$ , оставив расстояние Хэмминга ${\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)}$ других возможных значений. Поэтому верно следующее неравенство

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

То есть

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

(подставив ${\displaystyle |\mathbb {F} _{q}^{n}|=q^{n}}$ ).

Литература

• Gilbert E. N. A comparison of signalling alphabets // Bell System Technical Journal, 31:504-522 [1], 1952.
• Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок // Доклады Академии наук СССР, 117(5):739-741 [1], 1957.

См. также

• Граница Синглтона
• Граница Хэмминга
• Граница Джонсона
• Граница Плоткина