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

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

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

Пусть

A_{q} (n, d)

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

Тогда

A_{q} (n, d) ⩾ \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}} .

Когда $q$ является степенью простого числа, можно упростить неравенство до $A_{q} (n, d) ⩾ q^{k}$ , где $k$ — наибольшее целое число, для которого $A_{q} (n, d) ⩾ \frac{q^{n}}{\sum_{j = 0}^{d - 2} (\binom{n - 1}{j}) (q - 1)^{j}}$ .

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

Пусть $C$ — код максимальной мощности при длине $n$ и расстоянии Хэмминга $d$ :

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

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

d (x, c_{x}) ⩽ d - 1,

потому как в противном случае мы могли бы расширить код с помощью слова $x$ , оставив расстояние Хэмминга $d$ неизменным, что противоречит предположению относительно максимальной мощности $| C |$ .

Поэтому поле $𝔽_{q}^{n}$ можно упаковать объединением множеств всех сфер радиуса $d - 1$ с центром в $c \in C$ :

𝔽_{q}^{n} = ⋃_{c \in C} B (c, d - 1) .

Объём каждого шара

\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j},

потому что мы можем позволить (или выбрать) не более чем $(d - 1)$ -му из $n$ компонентов кодового слова принять одно из $(q - 1)$ других возможных значений. Поэтому верно следующее неравенство

| 𝔽_{q}^{n} | = | ⋃_{c \in C} B (c, d - 1) | ⩽ \sum_{c \in C} | B (c, d - 1) | = | C | \sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j} .

То есть

A_{q} (n, d) ⩾ \frac{q^{n}}{\sum_{j = 0}^{d - 1} (\binom{n}{j}) (q - 1)^{j}}

(подставив $| 𝔽_{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.

См. также

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

Содержание

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

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

Литература

См. также

Навигация

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

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

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

Литература

См. также

Навигация

Поиск