Русская Википедия:Граница Варшамова — Гилберта
Граница Варша́мова — Ги́лберта — неравенство, определяющее предельные значения для параметров кодов (не обязательно линейных), полученное независимо Шаблон:Iw и Ромом Варшамовым. Иногда употребляется название неравенство Гилберта — Шеннона — Варшамова, а в иноязычной научной литературе — неравенство Гилберта — Варшамова.
Формулировка
Пусть
- <math>A_q(n,\;d)</math>
обозначает максимально возможную мощность <math>q</math>-чного кода <math>C</math> длины <math>n</math> и расстояния Хэмминга <math>d</math> (<math>q</math>-чным кодом является код с символами из поля <math>\mathbb{F}_q</math>, состоящего из <math>q</math> элементов).
Тогда
- <math>A_q(n,\;d)\geqslant\frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j}.</math>
Когда <math>q</math> является степенью простого числа, можно упростить неравенство до <math>A_q(n,\;d)\geqslant q^k</math>, где <math>k</math> — наибольшее целое число, для которого <math>\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}</math>.
Доказательство
Пусть <math>C</math> — код максимальной мощности при длине <math>n</math> и расстоянии Хэмминга <math>d</math> :
- <math>|C|=A_q(n,\;d).</math>
Тогда для любого <math>x\in\mathbb{F}_q^n</math> существует по крайней мере одно кодовое слово <math>c_x \in C</math>, так что расстояние Хэмминга <math>d(x,\;c_x)</math> между <math>x</math> и <math>c_x</math> удовлетворяет
- <math>d(x,\;c_x)\leqslant d-1,</math>
потому как в противном случае мы могли бы расширить код с помощью слова <math>x</math>, оставив расстояние Хэмминга <math>d</math> неизменным, что противоречит предположению относительно максимальной мощности <math>|C|</math>.
Поэтому поле <math>\mathbb{F}_q^n</math> можно упаковать объединением множеств всех сфер радиуса <math>d-1</math> с центром в <math>c\in C</math>:
- <math>\mathbb{F}_q^n =\bigcup_{c\in C}B(c,\;d-1).</math>
Объём каждого шара
- <math>\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j,</math>
потому что мы можем позволить (или выбрать) не более чем <math>(d-1)</math>-му из <math>n</math> компонентов кодового слова принять одно из <math>(q-1)</math> других возможных значений. Поэтому верно следующее неравенство
- <math>|\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.</math>
То есть
- <math>A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j}</math>
(подставив <math>|\mathbb{F}_q^n|=q^n</math>).
Литература
- Gilbert E. N. A comparison of signalling alphabets // Bell System Technical Journal, 31:504-522 [1], 1952.
- Варшамов Р. Р. Оценка числа сигналов в кодах с коррекцией ошибок // Доклады Академии наук СССР, 117(5):739-741 [1], 1957.
См. также
