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

Харилцаа холбоонд Хэммингийн код нь шугаман алдааг зүгшрүүлэх кодын бүлд хамаарах бөгөөд Ричард Хэмминг 1950 онд Хэмминг(7,4) кодыг зохиож боловсруулжээ. Хэммингийн код нь нэг битийн алдааг зүгшрүүлж, хоёр битийн алдааг илрүүлж чадна. Ялгаатай тал нь энгийн парити код нь алдааг зүгшрүүлж чадахгүй, зөвхөн алдааны сондгой дугаарыг илрүүлж чадна. Хэммингийн код нь эдгээр төгс коднуудаас илүү онцгой. Тухайлбал, Хэммингийн код нь блокын урт болон хамгийн бага хүрэх зайн хамтаар кодын хамгийн өндөр боломжтой үзүүлэлтийг олж чаддаг.

Математикт Хэммингийн код нь хоёртын шугаман кодын ангилалд багтдаг. $r \ge 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 бол өгөгдлөөс нэг тэгш тоог шаардана. Хэрэв битийн тоо өөрчлөгдөж тэгш болвол шалгагч бит хүчинтэй болох бөгөөд алдаа нь илрэхгүй. Үүнээс гадна, парите нь тэгш бит дээр алдаа илэрсэн үед алдаа агуулсан битийг шаарддаггүй. Өгөгдөл нь бүрэн дүүрэн хэрэглэгдээгүй, санамсаргүйгээр дахин дамжуулагдах гэсэн шаардлагыг хангах ёстой. Шуугиантай дамжуулалтын орчинд амжилттай дамжуулалт хийгдэх нь урт хугацаа шаардаж болно. Гэхдээ энэ тохиолдохгүй ч байж болно. Хэдийгээр тийм боловч нэмэлт зардалд энэ аргын үр дүн зөвхөн ганц битийг ашиглах болсноос хойш парите шалгагчийн чанар муу болсон. Түүнчлэн парите шалгагч түүний байрлал мэдэгдэж байгаа үед худал илэрсэн битийг сэргээх боломжтой.