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

Кодын онолд, ( 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)\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$ хаа нэгтэй төвтэй бөмбөлгүүдийн нэгдэл бүх $\mathbb {F} _{q}^{n}$ харьяалагдана.
бөмбөлөг бүрийн хэмжээ нь:
$\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}$
Бөмбөгний төвтэй дүйцэх утгийг бусад (q-1) утгуудын нэг ( Код нь q-ary : утгуудаа $\mathbb {F} _{q}^{n}$ аас авдаг )болгон өөрчлөхийн тулд бид нэг codeword-ын n хэсгийн d-1 болгон ихэсгэх боломжтой. Тиймээс бид дараах дүгнэлтийг хийнэ.

${\begin{aligned}|\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{aligned}}$
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)\geq q^{k}$ болгож сайжруулж болно. Үүнд k нь хамгийн их бүхэл тоо мөн энэ бүхэл тооний хувьд $q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {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.