Gilbert–Varshamov bound

Чөлөөт нэвтэрхий толь — Википедиагаас
Jump to navigation Jump to search

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

Linear codes, GV bound[засварлах | edit source]

тодорхойлолт : үсгэн код дахь N урттай блок K Хэмжээстэй шугаман код нь к хэмжээст гийн С дэд вектор. энэ нь [n,k] гэж тэмдэглэддэг. d хамгийн бага зайтай N урттай K хэмжээст шугаман код нь [n ,k ,d ] код гэгддэг.

Теором[засварлах | edit source]

Gilbert- Varshamov bound: Үсгэн кодод [n,k,d] код оршино, Дараах нөхцөл биелсэн тохиолдолд

 

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

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

Тайлбар[засварлах | edit source]

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

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

Жишээ-1:[засварлах | edit source]

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

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

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

Жишээ-2:[засварлах | edit source]

[5,3,3] гэсэн код орших уу?

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

Энэ нь худлаа болно . тийм болохоор бид ямар ч дүгнэлтэнд хүрэхгүй.

Танилцуулга:[засварлах | edit source]

- аар n урттай, d хамгийн бага Hamming жинтэй q-ary code С-гийн хамгийн их боломжит хэмжээг тэмдэглэе.


тэгвэл ийм болно: .


Баталгаа:[засварлах | edit source]

C-ийг n урттай мөн d гэх хамгийн бага Hamming зайтай нэг код гэе.


Тэгвэл бүх яадаж нэг codeword оршино мөн x , ийг хоорондох Hamming зай нь нөхцөлийг хангана.
Бусад тохиолдолд |C|-ийн хамгийн ихтэй зөрчилдөх кодийн хамгийн бага Hamming зай d-a тодорхойлж байхад бид x ийг кодруу нэмж болно.
Тиймээс d-1 радиустай хаа нэгтэй төвтэй бөмбөлгүүдийн нэгдэл бүх харьяалагдана.
бөмбөлөг бүрийн хэмжээ нь:

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



That is:


(дараах баримтыг ашиглан:

Анхны тоон тохиолдолд сайжрал:[засварлах | edit source]

q a анхны тоон зэргийн хувьд хязгаарлалтыг (bound) болгож сайжруулж болно. Үүнд k нь хамгийн их бүхэл тоо мөн энэ бүхэл тооний хувьд байна.

Лавлах[засварлах | edit source]

  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.