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