Хэммингийн код

Харилцаа холбоонд Хэммингийн код (Hamming Code) нь шугаман алдааг зүгшрүүлэх кодын бүлд хамаарах бөгөөд Ричард Хэмминг 1950 онд Хэмминг(7,4) кодыг зохиож боловсруулжээ. Хэммингийн код нь нэг битийн алдааг зүгшрүүлж, хоёр битийн алдааг илрүүлж чадна. Ялгаатай тал нь энгийн парити код нь алдааг зүгшрүүлж чадахгүй, зөвхөн алдааны сондгой дугаарыг илрүүлж чадна. Хэммингийн код нь эдгээр төгс коднуудаас илүү онцгой. Тухайлбал, Хэммингийн код нь блокын урт болон хамгийн бага хүрэх зайн хамтаар кодын хамгийн өндөр боломжтой үзүүлэлтийг олж чаддаг. Математикт Хэммингийн код нь хоёртын шугаман кодын ангилалд багтдаг. $r\geq 2$ байх бүхэл тоо бүрийн хувьд кодын блокын урт нь $n=2^{r}-1$ байх ба зурвасын урт нь $k=2^{r}-r-1$ байна. Иймээс Хэммингийн кодын хамгийн өндөр боломжтой үзүүлэлт нь $R=k/n=1-r/(2^{r}-1)$ хүрэх зай $3$ ба блокын урт байхад $2^{r}-1$ . Хэммингийн кодын парити шалгагч матриц нь шугаман хамааралгүй хос $r$ -ийн уртын бүх багануудын жагсаалтаас бүрдэнэ.

Түүх

1940-өөд оны үед Хэмминг Белл Лабд секундэд цикл давтамжтай цахилгаан механикийн Белл Модел V компьютер дээр ажиллаж байжээ. Машины оролт нь цохисон картууд байдаг бөгөөд уншилтын алдаа гардаг байлаа. Ажлын өдрүүдэд алдаа илэрвэл гэрлүүд асаж операторууд тулгарсан асуудлыг зүгшрүүлдэг байв. Ажил тарсны дараа болон амралтын өдрүүдээр оператор байхгүй байх тул машинууд дараагийн ажил руугаа шилждэг. Хэмминг тасалдалтай ажиллагааны тоо ихсэж карт уншигчийн найдваргүй ажиллагаа үгүй болоход өөрийнхөө програмыг дахин ачаалах ёстой ба амралтын өдрүүдээр ч ажиллаж байлаа. Үүнээс хэдэн жилийн дараа тэрээр алдаа зүгшрүүлэх асуудал дээр ажиллаж хүчирхэг алгоритмыг хөгжүүлэх болов. 1950 онд одоогийн бидний Хэммингийн код гэж нэрлэх болсон алгоритмаа нийтлүүлсэн. Өнөөдөр ECC memory (Error-correcting code memory) зэрэг алдаа зүгшрүүлэх програмуудад ихээр ашиглагдаж байна.

Хэммингийн кодоос өмнө

Хэммингийн кодоос өмнө хэд хэдэн энгийн алдаа илрүүлэх кодууд байсан боловч Хэммингийн код шиг үр ашигтай байж чадаагүй.

Парите

Парите нь өгөгдсөн өгөгдлөөс тэгш эсвэл сондгой ганц битийг нэмдэг. Хэрэв сондгой тооны битүүд дамжуулалтын үед өөрчлөгдвөл парите өөрчлөгдөх бөгөөд энэ цэгт алдаа илрэх болно (Энд тэмдэглэхэд паритегийн бит өөрөө өөрчлөгдсөн байж болно). Хамгийн энгийн зөвшилцөл бол паритегийн утга 1 бол өгөгдлөөс нэг сондгойг, 0 бол өгөгдлөөс нэг тэгш тоог шаардана. Хэрэв битийн тоо өөрчлөгдөж тэгш болвол шалгагч бит хүчинтэй болох бөгөөд алдаа нь илрэхгүй. Үүнээс гадна, парите нь тэгш бит дээр алдаа илэрсэн үед алдаа агуулсан битийг шаарддаггүй. Өгөгдөл нь бүрэн дүүрэн хэрэглэгдээгүй, санамсаргүйгээр дахин дамжуулагдах гэсэн шаардлагыг хангах ёстой. Шуугиантай дамжуулалтын орчинд амжилттай дамжуулалт хийгдэх нь урт хугацаа шаардаж болно. Гэхдээ энэ тохиолдохгүй ч байж болно. Хэдийгээр тийм боловч нэмэлт зардалд энэ аргын үр дүн зөвхөн ганц битийг ашиглах болсноос хойш парите шалгагчийн чанар муу болсон. Түүнчлэн парите шалгагч түүний байрлал мэдэгдэж байгаа үед худал илэрсэн битийг сэргээх боломжтой.

Хэммингийн код үүсгэх

Хэммингийн код (Алдаа илрүүлэн засдаг код): кодын зай нь 3-тай тэнцүү кодууд үүсдэг ба 1 битийн алдааг илрүүлж, засахаас гадна 2 битийн алдааг илрүүлнэ. Энэ кодыг үүсгэхдээ К оронтой мэдээллийн код буюу 2-тын бүх боломжит код дээр m оронтой хяналтын кодыг нэмж n оронтой кодыг үүсгэдэг.

Хэммингийн кодыг дараах дэс дарааллын дагуу үүсгэнэ.

Хяналтын кодын оронг тодорхойлно. /m=?/
Хяналтын кодын элементүүдийн мэдээллийн код дотор байрлалыг тодорхойлно.
Хяналтын кодын элементүүдийн утгыг тодорхойлно.

1. Хяналтын кодын оронгийн тоог тогтоохдоо Хэммингийн кодыг дамжуулах суваг нь тухайн кодын зөвхөн 1 оронд алдаа үүсгэдэг гэж үзнэ. Ийм учраас алдаагүй дамжуулагдсан хувилбарыг нь оролцуулбал, n оронтой кодыг дамжуулахад n+1 хувилбарын аль 1-г хүлээн авах болно. Тэгвэл хяналтын кодыг ашиглаад энэ бүх n+1 хувилбарыг кодолж болно. Ө/х: m оронтой хяналтын кодоор 2^m тооны хувилбарыг бүртгэж болох буюу эндээс хяналтын кодын орон тоо m-г дараах харьцаагаар тодорхойлно:

2^m≥n+1=k+m+1 (3.13)

2. Мэдээллийн код дахь хяналтын кодын байрлал нь зарчмын хувьд ямар нэгэн утга агуулаагүй. Ө/х: энэ кодыг мэдээллийн хаана ч байрлуулж болно. Тэгвэл Хэммингийн кодын хувьд элементийн алдааг илрүүлэхэд тохиромжтойг нь харгалазан хяналтын кодын элементүүдийг шинээр үүсэх кодын 2-н зэргээр тодорхойлогдох байранд байрлуулдаг.

Ө/х:  1, 2, 4, 8, 16, ... г.м

Кодын элементийн байрыг баруун талаас нь эхлэн дугаарлана. Харин үлдсэн бусад байранд нь мэдээллийн код байрлана. Тухайлбал n=7 оронтой Хэммингийн кодыг дараах форматаар үүсгэнэ. Эндээс мөр нь m-тэй тэнцүү байх хүснэгтийг дараах аргаар үүсгэнэ.

1	2	3	4	5	6	7
m1	m2	k4	m3	k3	k2	k1

/ хүснэгт3.11 /.

m1-н хувьд хоёртын кодынх нь бага оронд 1 байх бүх элементүүдийг,

m2-н хувьд дунд оронд 1 байх бүх элементүүдийг,

m3-н хувьд ахлах оронд 1 байх бүх элементүүдийг сонгож авна.

1	m1	0 0 1
2	m2	0 1 0
3	k4	0 1 1
4	m3	1 0 0
5	k3	1 0 1
6	k2	1 1 0
7	k1	1 1 1

3. Үүний тулд эхлээд Хэммингийн кодын элемент бүрийг 2-тын кодоор кодолно. Тухайлбал 7 оронтой Хэммингийн кодын хувьд дараах хүснэгтийг үүсгэнэ.

Эндээс мөр нь m-тэй тэнцүү байх хүснэгтийг дараах аргаар үүсгэнэ. / хүснэгт3.11 /.

# m1-н хувьд хоёртын кодынх нь бага оронд 1 байх бүх элементүүдийг,
# m2-н хувьд дунд оронд 1 байх бүх элементүүдийг, 
# m3-н хувьд ахлах оронд 1 байх бүх элементүүдийг сонгож авна.

Хүснэгт 3.11

m1	k4 k3 k1
m2	k4 k2 k1
m3	k3 k2 k1

Ерөнхий тохиолдолд /n-н тоо их байвал/ энэ хүснэгтийг үүсгэхдээ: 1-р мөрөнд шинээр үүсэх кодын 1-р байрнаас эхлэн 1 орон алгасуулан / 1, 3, 5, 7, 9... г.м байрны элементүүдийг/ 2-р мөрөнд 2-р байрнаас эхлэн 2 дараалсан элементийг 2 орон алгасуулан /2,3, 6,7, 10,11, 14,15,.. г.м байрны элементүүд/ 3-р мөрөнд 4-р байрнаас эхлэн 4 дараалсан элементийг 4 орон алгасуулан /4,5,6,7, 12,13,14,15 байрны элемент/ 4-р мөрөнд 8-р байрнаас эхлэн 8 дараалсан элементийг 8 орон алгасуулан /8,9,10,11,12,13,14,15/ сонгон авна. Ингээд хяналтын кодын элементийн утгыг тогтоохдоо 2 дахь хүснэгтийн 1 мөрний мэдээллийн кодын элементийг хооронд нь 2т-ын модулиар нэмнэ. Ө/х: өмнөх жишээнд:

m1=k4+k3+k1

m2=k4+k2+k1

m3=k3+k2+k1 гэж тодорхойлогдоно.

Жишээ нь: к=8 кодоос Хэммингийн код үүсгэх

2^m ≥ m+9 гэдгээс m=4 гэж гарна.  n=12 оронтой код үүснэ.

Кодын формат нь

1	2	3	4	5	6	7	8	9	10	11	12
m1	m2	k8	m3	k7	k6	k5	m4	k4	k3	k2	k1

Хэрвээ энэ шалгалтаар 1 гарч байвал мөр тус бүрийн шалгалтаар гарсан утгаар 2т-ын код үүснэ. Үүнд хамгийн эхний мөр нь 2т-ын кодын бага орон, хамгийн сүүлчийн мөр нь ахлах оронг заана. Энэ 2т-ын кодыг 10т-д шилжүүлбэл алдаа гарсан оронгийн дугаар гарч ирнэ. Ингээд энэ оронгийн утгыг эсрэг утгаар нь сольж Хэммингийн кодод гарсан алдааг засна.