Ma'lumotlarni uzatish tizimlarini qurilish prinsiplari

Ma'ruza 7

HAMMING KODLARI

Bir qator xatolarni tuzatuvchi kodlarni ishlab chiqish va yaratishda qabul qilingan kod birikmalarining paritetini tekshirishning turli usullari muhim rol o'ynaydi. 1950-yillarning boshlarida Xemming kodni taklif qildi, unda boshqaruv belgilari kod birikmasiga o'zboshimchalik bilan emas, balki qat'iy belgilangan joylarda joylashtirildi, bu, albatta, dekodlashni osonlashtirdi.

Uzatilgan kodlangan xabarning to'g'riligini tekshirish uchun tizim ishlab chiqildi, shu jumladan xato sindromini aniqlash algoritmi nafaqat xato mavjudligini, balki buzilgan kod pozitsiyasining sonini ham ko'rsatadi.
Hamming kodining ikkita modeli eng ko'p qo'llaniladi: bitta xatoni aniqlash va tuzatishga ega kod (minimal kod masofasi d =

3. 
   va bitta xatolik tuzatish va ikki marta xato aniqlash bilan kod ( d = 4). Xemming kodini sintez qilish uchun quyidagilarni hal qilish kerak vazifalar:
   
   1. 
      Berilgan talablarga javob beradigan nazorat belgilar sonini aniqlang shovqinga qarshi immunitet.
      
   2. 
      Kod kombinatsiyasining qaysi pozitsiyalarida boshqaruv belgilarini joylashtirish kerakligini va ma'lumotlar qaysi pozitsiyalarni egallashini aniqlang. belgilar.
      
   3. 
      Kod kombinatsiyasining tartibini yig'ib, har bir nazorat belgisining qiymatini aniqlang.
      
   4. 
      Boshqaruv va ma'lumotni o'z ichiga olgan kod birikmalarini kompilyatsiya qilish belgilar.
      
   5. 
      Mavjudligi va joylashishini aniqlashga imkon beruvchi cheklar algoritmini keltiring xatolar.
      

d = 3 bilan kod sintezi

Bunday holda, boshlang'ich, qoida tariqasida, n _{va axborot belgilarining soni hisoblanadi} ,

^{N va} xabarlar to'plami bilan belgilanadi
n kodli so'zdagi belgilarning umumiy sonini o'rnating .
Birinchi vazifa.
n _gacha bo'lgan nazorat belgilar sonini aniqlang .
^{ 2n va _} . Va lekin ha _ balki _

Buning uchun, agar n yoki n berilsa _va , mos keladigan formulalardan foydalanish kerak

n _dan  gacha _ funt ( n  1) _ ;

(bir)

n _to  _ l b _ ( n _va  1 )  _ l b ( n _va
 1 ) _{  }

, (2)

bu yerda ] b [ eng yaqin katta butun songa yaxlitlash belgisi.


Ikkinchi vazifa.
Ushbu tekshirish bitlari umumiy kod kombinatsiyasida joylashishi kerak bo'lgan joylarni aniqlang.
Boshqaruv belgilari noto'g'ri pozitsiyaning sonini ko'rsatadigan ikkilik raqamni (xato sindromi) hosil qilishi kerak.
Birinchi xususiy paritet tekshiruvi natijasida sindromning birinchi (eng past) bitining belgisi, ikkinchi tekshirish natijasida ikkinchisining belgisi va boshqalar olinadi.
Shunday qilib, agar xato sindromi ikkilik to'rt xonali son sifatida ifodalangan bo'lsa va uning yonida tegishli o'nli ekvivalentlar yozilsa, biz 1-jadvalni olamiz.

o'ninchi ekvivalent t	Sindrom xatolar
bitta 2 3 4 5 6 7 sakkiz 9	0001 0010 0011 0100 0101 0110 0111 1000 1001

Har bir paritet tekshiruvida qatnashgan pozitsiyalar sonini kichik jadval shaklida ketma-ket yozamiz.

Birinchi tekshiruv eng kam muhim raqamda birlikni o'z ichiga olgan pozitsiyalarni o'z ichiga olishi kerak. Jadval asosida. 1, u 1, 3, 5, 9, .... bo'ladi.
Ikkinchi tekshirish ikkinchi raqamda birlik bo'lgan pozitsiyalarni o'z ichiga olishi kerak. Jadvalga ko'ra 1 2, 3, 6, 7, .... bo'ladi.
Uchinchi tekshirishda 4, 5, 6, 7, pozitsiyalar.
Natijada 2-jadval.

Tekshirish raqami	Raqamlar pos-th, qamrovi-x bu tekshirish
Birinchidan	bitta	3	5	7	9
Ikkinchi	2	3	6	7
Uchinchi	4	5	6	7

_{m boshqaruv belgilarini} quyidagi joylarda joylashtirish kerak degan xulosaga kelishimiz mumkin : ₁ -pozitsiyada K 1, ya'ni. 20 ; ^_
₂ - pozitsiyada 2-ga, ya'ni. 2 ¹ ; ₄ - pozitsiyada 3-ga, ya'ni. 2 ² ; 8 - pozitsiyada _{4 -ga, ya'ni.} 2 ³ ; 2 _{m holatda} ^m gacha .
Uchinchi vazifa.
Boshqaruv belgilarining ma'nosini aniqlang. Hamming kodining sxemasi tuzilgan.