Связано Гилберт–Варшамов

В теории кодирования граница Гилберта –Варшамова (от Эдгара Гилберта [1] и независимо Рома Варшамова [2] ) — это граница размера (не обязательно линейного ) кода . Иногда ее называют границей Гилберта– Шеннона –Варшамова (или границей GSV ), но название «граница Гилберта–Варшамова» на сегодняшний день является наиболее популярным. Варшамов доказал эту границу, используя вероятностный метод для линейных кодов. Подробнее об этом доказательстве см. в разделе Граница Гилберта–Варшамова для линейных кодов .

Заявление о связанности

Напомним, что код имеет минимальное расстояние , если любые два элемента в коде находятся на расстоянии не менее одного расстояния друг от друга. Пусть г {\displaystyle д} г {\displaystyle д}

А д ( н , г ) {\displaystyle A_{q}(n,d)}

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

Затем:

А д ( н , г ) ⩾ д н ∑ дж = 0 г − 1 ( н дж ) ( д − 1 ) дж . {\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}

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

Пусть — код длины и минимального расстояния Хэмминга, имеющий максимальный размер: С {\displaystyle С} н {\displaystyle n} г {\displaystyle д}

| С | = А д ( н , г ) . {\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}}

г ( х , с х ) ⩽ г − 1 {\displaystyle d(x,c_{x})\leqslant d-1}

поскольку в противном случае мы могли бы добавить x к коду, сохранив при этом минимальное расстояние Хэмминга кода – противоречие с максимальностью . г {\displaystyle д} | С | {\displaystyle |С|}

Следовательно, все содержится в объединении всех шаров радиуса, имеющих центр в некотором  : Ф д н {\displaystyle \mathbb {F} _{q}^{n}} г − 1 {\displaystyle d-1} с ∈ С {\displaystyle c\in C}

Ф д н = ⋃ с ∈ С Б ( с , г − 1 ) . {\displaystyle \mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).}

Теперь каждый мяч имеет размер

∑ дж = 0 г − 1 ( н дж ) ( д − 1 ) дж {\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}

поскольку мы можем разрешить (или выбрать ) до компонентов кодового слова отклоняться (от значения соответствующего компонента центра шара ) к одному из возможных других значений (напомним: код является q-ичным: он принимает значения в ). Следовательно, мы выводим г − 1 {\displaystyle d-1} н {\displaystyle n} ( д − 1 ) {\displaystyle (q-1)} Ф д н {\displaystyle \mathbb {F} _{q}^{n}}

д н = | Ф д н | = | ⋃ с ∈ С Б ( с , г − 1 ) | ⩽ ∑ с ∈ С | Б ( с , г − 1 ) | = | С | ∑ дж = 0 г − 1 ( н дж ) ( д − 1 ) дж {\displaystyle q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\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}}

То есть:

А д ( н , г ) = | С | ⩾ д н ∑ дж = 0 г − 1 ( н дж ) ( д − 1 ) дж . {\displaystyle A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}.}

Улучшение в корпусе основной мощности

Для q — степени простого числа можно улучшить границу до , где k — наибольшее целое число, для которого А д ( н , г ) ≥ д к {\displaystyle A_{q}(n,d)\geq q^{k}}

д к < д н ∑ дж = 0 г − 2 ( н − 1 дж ) ( д − 1 ) дж . {\displaystyle q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1 )^{j}}}.}

Смотрите также

Ссылки

  1. ^ Гилберт, EN (1952), «Сравнение алфавитов сигнализации», Bell System Technical Journal , 31 (3): 504–522, doi :10.1002/j.1538-7305.1952.tb01393.x.
  2. ^ Варшамов, Р. Р. (1957), «Оценка числа сигналов в кодах, исправляющих ошибки», ДАН СССР , 117 : 739–741.
Взято с "https://en.wikipedia.org/w/index.php?title=Gilbert–Varshamov_bound&oldid=1191935893"