Хэммингийн хил

Математик, компьютерийн шинжлэх ухаан , кодчилолын онолын салбарт Хэммингийн хил нь дурын бүлэг кодын хувьд параметрийн хязгаарлалт юм: Энэ нь бид бүгдийн мэддэгчилэн савлах бөмбөгний дууны хил эсвэл агуулгын хүрээллийн хилээр Хэммингийн хэмжигдэхүүн дэх бүх боломжит үгнүүдийн эзэлхүүнийг мэдээллэнэ. Энэ нь кодчилсон үгнүүд дэх ямар нэг алдааг засахад ашиглах зай нь чухал ач тусыг тогтоосон хязгаар юм. Энэ кодыг/Хэммингийн хил/ гэх ба үүнийг алдаагүй код хэмээн нэрлэжээ.

Алдааг засах кодуудын үндэс

Анхны мэдээ болон кодчилсон хувилбар нь аль аль нь “q” үсгээр тэмдэглэгдсэн байна. Кодчилсон үг бүр ‘’n’’ үсгийг агуулна Анхны мэдээ /Урт m/ нь n үсгээс жижиг байна. Зурвас нь кодчилолын алгоритмд нь n үсгээр- захидал кодчилогдох ба хувирах нь дуу чимээ ихтэй суваг дамжуулж , эцэст нь хүлээн авагч тайлан уншина.

Кодыг тайлан уншиж сурснаар үйл явц нь хүчин төгөлдөр кодчилсон үг " хамгийн ойр " N - захидал хүлээн авсан мөр шиг , зүгээр л үгэнд дурдсан ойлгогдохгүй кодчилсон байдаг. Математикийн талаас мэдээнд урт m болон qm тохиромжтой мэдээллүүд байдаг болох ба зурвас бүр урт m вектороор илэрхийлнэ.

Баримтлах хил

Кодчилол схем нь n- хэмжээст вектор руу m- хэмжээст вектор хөрвүүлдэг. qm хүчин төгөлдөр үгийг кодлох боломжтой , гэхдээ кодчилсон үг дамжуулагдаж байгаа бол дуу чимээтэй суваг n үсэг нь нэг буюу түүнээс дээш гажуудуулж болох учраас Код ойлгогдохгүй кодчилсон ( үг ) -ийн аль нэг нь хүлээн авч болзошгүй.

Түүнчлэн Хэмминг байна::

$\ A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}$

Үүнд

$t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .$

Баталгаа

$d$ -ийн тодорхойлсноор, $t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor$ нь хамгийн их алдаатай кодчилсон үг дамжуулах явцад хийж, үүний дараа нь хамгийн бага зайд тайлан уншиж сурснаар кодыг зөв тайлан уншина, (өөрөөр хэлбэл , энэ нь илгээсэн тэр кодчилсон үгнүүдийг хүлээн авсан гэдэг үгийг тайлан уншсан гэсэн үг юм). Иймээс код нь $t$ бүхий алдааг засах боломжтой байх ёстой.

Тухайн кодчилсон үг нь $c\in C$ байна, $t$ -ын хажууд радиустай өгөгдөлийг хамтатгана. Өгөгдлийн хослол бүрт /Хэммингийн салбар/ $t$ алдааг засах шинж төлөвгүй байх ба m -өгөгдөл бүр нь /өгөгдлийн дуу авиа ба өөр үг, утга/ агуулдаг. Бид $n$ болон $t$ ээс дээш бүрэлдэхүүн хэсгүүдээс /өгөгдлийн гол бүрэлдэхүүний тохирох кодлох үгийн утгаас/ хамруулах болон сонгон авч болох ба энэ нь кодчилсон үг байна. $(q-1)$ өгөгдөл нь бусад шинж чанарын нэг нь $q$ өгөгдөлийг дахин оруулах нь ${\mathcal {A}}_{q}^{n}$ ийм утгыг агуулна/

$m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}$

$A_{q}(n,d)$ өгөгдөл нь $C$ дэх хамгийн их тоот кодчилсон үгнүүд ба өгөгдлүүдийн хамгийн зөв зүйтэй дугаарлалт юм. Мөн хоёр өгөгдөл нь нийтлэг ижил үгийг агуулна. Бид кодлогдсон үгнүүдийг ажигласнаар өгөгдлүүд дэх кодчилсон үгнүүд нь өгөгдлийн үгнүүдийн гол хэсэгт байрладгийг ажиглаж болох ба өгөгдөл бүрийг тодорхойлмогц ${\mathcal {A}}_{q}^{n}$ нь дэд хэсэг нь ( $|{\mathcal {A}}_{q}^{n}|=q^{n}$ өгөгдөлүүдийг) тодорхойлно:

$A_{q}(n,d)\times m=A_{q}(n,d)\times {\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}\leq q^{n}.$

Шалтгаан:

$A_{q}(n,d)\leq {\frac {q^{n}}{\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}}.$

Нийт радиус болон гол радиус

Загвар:Гол сэдэв

$A_{q}(n,d)$ код нь (${\mathcal {A}}_{q}^{n}$ дэд хэсэг)C кодыг хамарсан хамгийн бага утга баC бүхий кодчилсон үг бүр дээр ${\mathcal {A}}_{q}^{n}$ элемент бүрийн төв радиус-т r ”-өгөгдлийг бүрэлдэхүүн хэсэгт заавал агуулна. C-ийн бүлэг өгөгдлийн кодчилсон үгэнд s радиусын өгөгдөлийг кодчилсон үг бүрийн C өгөгдлийн хэсэг бүрт төв радиуст байрлуулна.

Хэммингийн хилийн баталгааг эндээс харж болно: $t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor$, Үүнд:

s ≤ t болон t ≤ r байна.

Тиймээс, s ≤ r болон s = r = tтэнцүү чанарыг агуулна. Тэнцүү чанарыг хангах гэдэг нь Хэммингийн хилийг агуулсан байна гэсэн үг юм.

Алдаагүй кодлох

Хэммингийн хилийг агуулсан кодыг алдаагүй код гэж нэрлэдэг. Кодчилсон жишээнд зөвхөн нэг үгийг кодолсон кодыг оруулахад $\scriptstyle {\mathcal {A}}_{q}^{n}$ нь тэр кодыг төлөөлж болно. . Өөр нэг жишээ бол мэдээ бүрийн тэмдэг нь кодчилсон үг бол q = 2 ыг ашиглах ба сондгой тогтмол тооны давтагдсан үед кодыг давтан өгнө. Ерөнхийдөө эдгээр жишээнүүдийг ердийн жижиг алдаагүй код гэж нэрлэдэг. 1973 онд Хэммингийн код буюу Голай кодын параметрүүд ямар нэгэн ач холбогдолгүй ердийн цагаан толгойн үсгээр нэрлэгдэн батлагдсан байна Golay code.

Алдаагүй код нь бүлэгт өгөгдлийнt г хамруулсан нь кодчилсон үгэнд Хэммингийн радиусын өгөгдлийн зайг бөглөж нэг утга илэрхийлж болно (t ”-өгөгдөл нь Гол радиус=бүлэг радиус утгыг илэрхийлнэ). Заримдаа алдаагүй код нь зарим давхардлыг хийх ба кодчилсон үгэнд Хэммингийн радиусын өгөгдлийн t хэсэгт байх ба радиус нь t+1 -ийг үүсгэх орон зайн өгөгдөл юм. Үүнийг тайлбарлах өөр нэг арга нь код нь заримдаа- алдаагүй байвал гол радиус нь бүлэг радиусаас илүү чанартай байна.