Варшамов-Гилбертийн хязгаар

Кодын онолд, ( [Edgar Gilbert1 бас тусдаа Rom Varshamov[2] хүний нэр ) нь кодын ( шугаман байх шаардлагагүй ) параметрын хязгаарлалт юм. Энэ нь заримдаа Gilbert–Shannon–Varshamov нэрлэгддэг ( GSV bound), гэхдээ Gilbert–Varshamov bound нэр нь илүү өргөн хэрэглэгддэг. Варшамов үүнийг шугаман кодочлол дахь магадлалын аргаар баталсан. Баталгааны талаар GV-linear-code илүү ихийг хараарай.

## Linear codes, GV bound
тодорхойлолт : {F}_q үсгэн код дахь N урттай блок K Хэмжээстэй шугаман код нь к хэмжээст {F}_q^n гийн С дэд вектор.
	           энэ нь [n,k] гэж тэмдэглэддэг. d хамгийн бага зайтай N урттай K хэмжээст шугаман код нь [n ,k  ,d ] код гэгддэг.
### Теором 
Gilbert- Varshamov bound: {F}_q Үсгэн кодод [n,k,d] код оршино, Дараах нөхцөл биелсэн тохиолдолд

  {q}^{n-k}-1>(q-1)\left(\frac{n-1}{1}\right)+ \dots +(q-1)^{d-2}\left(\frac{n-1}{d-2}\right)  

Хоёртын кодын хамгийн энгийн тохиолдолд, Дараах нөхцөл биелэж байвал

 {2}^{n-k}-1>\left(\frac{n-1}{1}\right)+ \dots + \left(\frac{n-1}{d-2}\right) 

F2 дахь [n,k,d] code оршино байна.

### Тайлбар 
Gv bound бол шугаман кодын параметеруудын хоорондох хамаарал юм түүнчлэн дээрх нөхцөлүүдийг хангаж байвал энэ нь заавал оршин байна. 
Gv bound үл-оршино гэдгийг батлах боломжгүй.Энэ нь Hamming bound-ийн яаг эсрэг нөхцөл юм.
Hamming bound ганцхан шугаман кодоос бусад бүх кодод хүчинтэй.( хэмжээсийш шугаман алгебрын тодорхойолотоор){v}_1...{v}_k
гэсэн сууриуд байдаг мөн бүх зүйлүүд дахин давтагдашгүйгээр нэг

 {C}_1{V}_1 + \dots + {C}_k{v}_k 

ШУГАМАН кодын комбинацаар илэрхийлэгдэх боломжтой болхоор   {F}_q  гийн [n ,k ,d ] код нь  {q}_k  гэсэн codeword Тэй. {C}_1  ийн хувьд q сонголт {C}_k  ийн хувьд q сонголт байна.

### Жишээ-1: 
[5,2,3] гэсэн код орших уу? 

[n ,k ,d] = [5, 2, 3] тэмдэглэгээ нь дараах утгатай block- ийн урт нь n = 5. Хэмжээс нь k=2. Хамгийн бага зай d= 3. 
үсгэн кодийн хэмжээ нь q=2. Хоёртын Gv bound нь

 {2}^{n-k}-1>\left(\frac{n-1}{1}\right)+ \dots +\left(\frac{n-1}{d-2}\right) 

 {2}^{5-2}-1>\left(\frac{5-1}{1}\right)+ \dots +\left(\frac{5-1}{3-2}\right) 

 {2}^{3}-1>\left(\frac{5-1}{1}\right)+ \dots +\left(\frac{5-1}{1}\right) 

 7>4 

Энэ нь үнэн болно . Тэгхээр тийм code оршино байна.

### Жишээ-2: 
[5,3,3] гэсэн код орших уу? 

[n ,k ,d] = [5, 3, 3] тэмдэглэгээ нь дараах утгатай block- ийн урт нь n = 5. Хэмжээс нь k=3. Хамгийн бага зай d= 3. 
үсгэн кодийн хэмжээ нь q=2. Хоёртын Gv bound нь

 {2}^{n-k}-1>\left(\frac{n-1}{1}\right)+ \dots +\left(\frac{n-1}{d-2}\right) 

 {2}^{5-3}-1>\left(\frac{5-1}{1}\right)+ \dots +\left(\frac{5-1}{3-2}\right) 

 {2}^{2}-1>\left(\frac{5-1}{1}\right)+ \dots +\left(\frac{5-1}{1}\right) 

 3>4 

Энэ нь худлаа болно . тийм болохоор бид ямар ч дүгнэлтэнд хүрэхгүй.
 
## Танилцуулга: 
A_q(n,d) - аар n урттай, d хамгийн бага Hamming жинтэй q-ary code С-гийн хамгийн их боломжит хэмжээг тэмдэглэе.  

тэгвэл ийм болно:
A_q(n,d) \geq \frac{q^n}{\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j}.

## Баталгаа: 
C-ийг n урттай мөн d гэх хамгийн бага Hamming зайтай нэг код гэе.
 
|C|=A_q(n,d).\,

Тэгвэл бүх x\in\mathbb{F}_q^n, яадаж нэг codeword c_x \in C оршино мөн x , c_x ийг хоорондох Hamming зай d(x,c_x) нь d(x,c_x)\leq d-1 нөхцөлийг хангана.   

Бусад тохиолдолд |C|-ийн хамгийн ихтэй зөрчилдөх кодийн хамгийн бага Hamming зай d-a тодорхойлж байхад бид x ийг кодруу нэмж болно.

Тиймээс d-1 радиустай c \in C хаа нэгтэй [төвтэй](https://en.wikipedia.org/wiki/Ball_(mathematics)) бөмбөлгүүдийн нэгдэл бүх \mathbb{F}_q^n харьяалагдана.

[бөмбөлөг](https://en.wikipedia.org/wiki/Ball_(mathematics)) бүрийн хэмжээ нь: 

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

Бөмбөгний төвтэй дүйцэх утгийг бусад (q-1) утгуудын нэг ( Код нь q-ary : утгуудаа \mathbb{F}_q^n аас авдаг )болгон өөрчлөхийн тулд бид нэг codeword-ын n хэсгийн d-1 болгон ихэсгэх боломжтой. Тиймээс бид дараах дүгнэлтийг хийнэ.

\begin{align}
|\mathbb{F}_q^n| & = |\cup_{c \in C} B(c,d-1)| \\
\\
& \leq \sum_{c \in C} |B(c,d-1)| \\
\\
& = |C|\sum_{j=0}^{d-1} \binom{n}{j}(q-1)^j \\
\\
\end{align}

That is:

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

(дараах баримтыг ашиглан: |\mathbb{F}_q^n|=q^n).

## Анхны тоон тохиолдолд сайжрал: 
q a анхны тоон зэргийн хувьд хязгаарлалтыг (bound) A_q(n,d)\ge q^k болгож сайжруулж болно. Үүнд k нь хамгийн их бүхэл тоо мөн энэ бүхэл тооний хувьд q^k  байна.

## Лавлах 
# Gilbert, E. N. (1952), "A comparison of signalling alphabets", Bell System Technical Journal 31: 504–522, doi:10.1002/j.1538-7305.1952.tb01393.x.
# Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Acad. Nauk SSSR 117: 739–741.

Ангилал:Кодын онол