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

Кодын онолд, ( Edgar Gilbert[1] бас тусдаа 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)\ge \frac{q^n}{\sum _{j=0}^{d-1}(\genfrac{}{}{0ex}{}{n}{j})(q-1{)}^j}$.

Баталгаа:

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

Тэгвэл бүх $x\in {𝔽}_q^n,$ яадаж нэг codeword $c_x\in C$ оршино мөн x , $c_x$ ийг хоорондох Hamming зай $d(x,c_x)$ нь $d(x,c_x)\le d-1$ нөхцөлийг хангана.
Бусад тохиолдолд |C|-ийн хамгийн ихтэй зөрчилдөх кодийн хамгийн бага Hamming зай d-a тодорхойлж байхад бид x ийг кодруу нэмж болно.
Тиймээс d-1 радиустай $c\in C$ хаа нэгтэй төвтэй бөмбөлгүүдийн нэгдэл бүх ${𝔽}_q^n$ харьяалагдана.
бөмбөлөг бүрийн хэмжээ нь:
$\sum _{j=0}^{d-1}(\genfrac{}{}{0ex}{}{n}{j})(q-1{)}^j$
Бөмбөгний төвтэй дүйцэх утгийг бусад (q-1) утгуудын нэг ( Код нь q-ary : утгуудаа ${𝔽}_q^n$ аас авдаг )болгон өөрчлөхийн тулд бид нэг codeword-ын n хэсгийн d-1 болгон ихэсгэх боломжтой. Тиймээс бид дараах дүгнэлтийг хийнэ.

$\begin{array}{cc}|{𝔽}_q^n|& =|{\cup }_{c\in C}B(c,d-1)|\\ \\ & \le \sum _{c\in C}|B(c,d-1)|\\ \\ & =|C|\sum _{j=0}^{d-1}(\genfrac{}{}{0ex}{}{n}{j})(q-1{)}^j\\ \\ \end{array}$
That is:

$A_q(n,d)\ge \frac{q^n}{\sum _{j=0}^{d-1}(\genfrac{}{}{0ex}{}{n}{j})(q-1{)}^j}$
(дараах баримтыг ашиглан:$|{𝔽}_q^n|=q^n).$

Анхны тоон тохиолдолд сайжрал:

q a анхны тоон зэргийн хувьд хязгаарлалтыг (bound) $A_q(n,d)\ge q^k$ болгож сайжруулж болно. Үүнд k нь хамгийн их бүхэл тоо мөн энэ бүхэл тооний хувьд $q^k<\frac{q^n}{\sum _{j=0}^{d-2}(\genfrac{}{}{0ex}{}{n-1}{j})(q-1{)}^j}$ байна.

Лавлах

1. 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.
2. Varshamov, R. R. (1957), "Estimate of the number of signals in error correcting codes", Dokl. Acad. Nauk SSSR 117: 739–741.