Хэлэлцүүлэг:Хэммингийн код

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

Хэммингийн код(Алдаа илрүүлэн засдаг код): кодын зай нь 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т-д шилжүүлбэл алдаа гарсан оронгийн дугаар гарч ирнэ. Ингээд энэ оронгийн утгыг эсрэг утгаар нь сольж Хэммингийн кодод гарсан алдааг засна.

Хэммингийн код үүсгэх[edit source]

Хэммингийн код(Алдаа илрүүлэн засдаг код): кодын зай нь 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т-д шилжүүлбэл алдаа гарсан оронгийн дугаар гарч ирнэ. Ингээд энэ оронгийн утгыг эсрэг утгаар нь сольж Хэммингийн кодод гарсан алдааг засна.