Граница Варша́мова — Ги́лберта — неравенство, определяющее предельные значения для параметров кодов (не обязательно
Шеннона
— Варшамова, а в иноязычной научной литературе —
неравенство Гилберта — Варшамова.
Формулировка
Пусть
![{\displaystyle A_{q}(n,\;d)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a10eb2d6fa35037b88a4fd8698e14b2477b919e)
обозначает максимально возможную мощность
-чного кода
длины
и расстояния Хэмминга
(
-чным кодом является код с символами из поля
, состоящего из
элементов).
Тогда
![{\displaystyle A_{q}(n,\;d)\geqslant {\frac {q^{n}}{\displaystyle \sum \limits _{j=0}^{d-1}\displaystyle {\binom {n}{j}}(q-1)^{j}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e0f0351b5dc520cc275058e478f43017cef89c7)
Когда
является степенью простого числа, можно упростить неравенство до
, где
— наибольшее целое число, для которого
.
Доказательство
Пусть
— код максимальной мощности при длине
и расстоянии Хэмминга
:
![{\displaystyle |C|=A_{q}(n,\;d).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/173d3910a5ccb9549e6e608f53a0fd09677bdcea)
Тогда для любого
существует по крайней мере одно кодовое слово
, так что расстояние Хэмминга
между
и
удовлетворяет
![{\displaystyle d(x,\;c_{x})\leqslant d-1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f617574bf088acd7d4b6cda22b536b34d91a3ec)
потому как в противном случае мы могли бы расширить код с помощью слова
, оставив
расстояние Хэмминга
![{\displaystyle d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab)
неизменным, что противоречит предположению относительно максимальной мощности
![{\displaystyle |C|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f9114ede7c5dd63e8b1cbd051e11d343b233f4)
.
Поэтому поле
можно упаковать объединением множеств всех сфер радиуса
с центром в
:
![{\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,\;d-1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4793162d5e2273a062013fae1520426f7181341a)
Объём каждого шара
![{\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa8cc2f513710fbb1f70702bae8ba212e0664441)
потому что мы можем позволить (или
выбрать
) не более чем
![{\displaystyle (d-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d220ad260fcc368cb5c1e92a8253f33695f20940)
-му из
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
компонентов кодового слова принять одно из
![{\displaystyle (q-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab0d9983d7458bc6724c7b8f8270be2a20c7ade2)
других возможных значений. Поэтому верно следующее неравенство
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f35a6fa7de81ac866640974b885c99d3421729f3)
То есть
![{\displaystyle A_{q}(n,\;d)\geqslant {\frac {q^{n}}{\sum \limits _{j=0}^{d-1}\displaystyle {\binom {n}{j}}(q-1)^{j}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd5fe3dd1ecc7ea47ae1b52b436d5e5d2aa9d084)
(подставив
).
Литература
- Gilbert E. N. A comparison of signalling alphabets // Bell System Technical Journal, 31:504-522 [1], 1952.
- Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок // Доклады Академии наук СССР, 117(5):739-741 [1], 1957.
См. также