Меню Главная Случайная статья Настройки Граница Варшамова — Гилберта Материал из https://ru.wikipedia.org Граница Варшамова — Гилберта — неравенство, определяющее предельные значения для параметров кодов (не обязательно линейных), полученное независимо Эдгаром Гилбертом[англ.] и Ромом Варшамовым. Иногда употребляется название неравенство Гилберта — Шеннона — Варшамова, а в иноязычной научной литературе — неравенство Гилберта — Варшамова. Содержание 1 Формулировка 2 Доказательство 3 Литература 4 См. также Формулировка Пусть ${\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 \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)\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. См. также Граница Синглтона Граница Хэмминга Граница Джонсона Граница Плоткина