길버트-바르샤모프 바운드

코딩 이론에서 길버트-바르샤모프 바인딩(에드가 길버트와^[1] 독립적으로 롬 바르샤모프^[2] 때문)은 (필수적으로 선형적이지 않은) 코드의 파라미터에 대한 제한이다.간혹 길버트-샤논-바르샤모프 바운드(또는 GSV 바운드)로 알려져 있지만, "길버트-바르샤모프 바운드"라는 명칭이 단연 최고 인기다.바르샤모프는 선형 코드에 확률론적 방법을 사용함으로써 이 경계를 증명했다.자세한 내용은 선형 코드에 바인딩된 Gilbert-Varshamov를 참조하십시오.

바운트 명세서

내버려두다

${\디스플레이 스타일 A_{q}(n,d)}$

길이 n과 최소 해밍 거리 d를 가진$$ q-ary 코드 $C{\displaystyle }$ ${\displaystyle C}$의 가능한 최대 크기를 나타낸다(q-ary 코드는 q 요소의 $F$$$\$displaystyle \mathb {F} _{q}).$

다음:

${\displaystyle A_{q}(n,d)\geqslant {\frac {q^{n}{n}{j=0}^{d-1}{\binom {n}{j-1}(q-1)^{j}}}}}}.}$

증명

$C{\displaystyle }$ ${\displaystyle C}$을(를) 최대 크기의$$ 길이 $n{\displaystyle }$ ${\displaystyle n}$ 및$$ 최소 해밍 거리 $d{\displaystyle }$ ${\displaystyle$ d$}$이(가) 되도록$$ 하십시오.

${\디스플레이 스타일 C =A_{q}(n,d)}$

Then for all ${\displaystyle x\in \mathbb {F} _{q}^{n}}$ , there exists at least one codeword ${\displaystyle c_{x}\in C}$ such that the Hamming distance ${\displaystyle d(x,c_{x})}$ between ${\displaystyle x}$ and ${\displaystyle c_{x}}$ satisfies

${\displaystyle d(x,c_{x})\leqslant d-1}$

그렇지 않으면 코드의 최소 해밍 $거리{\displaystyle }$ d ${\displaystyle d}$을(를) 유지하면서 코드에 x를 추가할 수 있으므로, ${\displaystyle C}$ $displaystyle C}$의 최대성에 대한 모순이다$.$

따라서$$ 전체 ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$은(는) 일부 $c{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle C}$ ${\displaystyle c\in C}$에서 중심을 갖는$$ 반경 ${\displaystyle \mathrm{d}}$- 1 ${\displaystyle d-1}$의 모든 볼 조합에 포함된다.$$

${\daystyle \mathb {F} _{q}^{n}=\빅컵 _{c\in C}B(c,d-1).}$

이제 각각의 공은 크기가 있다.

${\displaystyle \sum _{j=0}^{d-1}{\binom {n}{j}(q-1)^{j}}}}}{j}}}}}}}}}$

코드 워드의 $n{\displaystyle }$ ${\displaystyle d-1}$ 구성$$ 요소 중 최대$$ ${\displaystyle \mathrm{d}}$- 1 ${\displaystyle$ d-1$}$이(가) 가능한$$- ${\displaystyle 1}$ ${\displaystyle (q-1$)의$$ 다른 값(리콜: 코드는 q-ary: F $Q{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$의 값을 취함)으로 이탈하도록 허용할 수 있으므로${\displaystyle \mathb {F} _{q}^{n}}}.$그래서 우리는 추론한다.

${\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}}$

즉,

${\displaystyle A_{q}(n,d)=C \geqslant {\frac{q^{n}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}}.}$

프라임 파워 케이스의 개선

q prime power의 경우, $a{\displaystyle {}_{}}$ ${\displaystyle q_{}}$(${\displaystyle n}$ ,${\displaystyle }$d${\displaystyle }$) ${\displaystyle \ge }$ ${\displaystyle q^{}}$ k ${\$에 대한 바운드를 개선할 수 있다. 여기서 k는 다음 중 가장 큰 정수다.

${\displaystyle q^{k}{\frac {q^{n}{\sum _{j=0}^{d-2}{\binom{n-1}{j-1}(q-1)^{j}}}}}.}$

참고 항목

• 싱글톤 바운드
• 해밍 바운드
• 존슨 바운드
• 플롯킨 바운드
• 게리머 바운드
• 그레이-란킨 바운드
• 길버트-바르샤모프 선형 코드 바인딩
• 엘리아스-바살리고 바운드

참조