Ma'lumotlarni uzatish tizimlarini qurilish prinsiplari

n _va bo'lsin =4, n _gacha = 3, n = 7. Keyin, umuman olganda, shunday ko'rinadi quyidagicha: Xonalar pozitsiyalar 1 2 3 4 5 6 7
K ₁ K ₂ Va ₃ K ₃ Va ₂ Va ₁ Va ₀ belgilari ,
bu yerda VA _i - axborot belgilari.


Boshqaruv belgilarini aniqlash algoritmi

K ₁ qiymatini aniqlash. Barcha belgilarning yig'indisi moduli 2, shu jumladan K ₁ , 1, 3, 5, 7, 9, ... pozitsiyalarida joylashgan, birinchi tekshiruv bilan qoplangan, ya'ni.

K ₁  Va ₃  Va ₂  va ₀ . (3)
K _{1 belgisining qiymati} yig'indining (3) yo'qolishi sharti bilan aniqlanadi, ya'ni. paritet holatidan. Agar birliklar soni (K _{1 bo'lmasa} ) toq bo'lsa, K ₁ =1, juft bo'lsa, K ₁ =0 bo'ladi.
K ₂ qiymatini aniqlash. Barcha belgilarning yig'indisi moduli 2, shu jumladan K ₁ , ikkinchi tekshiruv bilan qoplangan pozitsiyalarga joylashtirilgan, ya'ni.
K ₂  Va ₃  Va ₁  va ₀ . (4)
K _{2 belgisining qiymati} yig'indining (4) yo'qolishi sharti bilan aniqlanadi, ya'ni. paritet holatidan. Agar birliklar soni (K _{2 bo'lmasa} ) toq bo'lsa, K ₂ =1, juft bo'lsa, K ₂ =0 bo'ladi.
K ₃ qiymatini aniqlash. Barcha belgilarning yig'indisi moduli 2, shu jumladan K ₃ , uchinchi tekshiruv bilan qoplangan pozitsiyalarga joylashtirilgan, ya'ni.
K ₃  Va ₂  Va ₁  va ₀ . (5)
K _{3 belgisi} ikkilik yig'indini (5) o'chirishi kerak.
Xuddi shunday, K ₄ , K ₅ va boshqa belgilar topiladi, faqat buning uchun to'rtinchi, beshinchi va boshqa tekshiruvlarni o'tkazish va tegishli miqdorlarni rasmiylashtirish kerak.
To'rtinchi vazifa.
Kod kombinatsiyalarini yarating. Buning uchun asl ortiqcha bo'lmagan ikkilik kodning barcha kombinatsiyalarini yozing va kod so'zining tartibidan foydalangan holda, shuningdek yig'indilar (3) asosida hisoblangan K _{m boshqaruv belgilarining qiymatlarini yozing. (4), (5) va hokazo, barcha} n _va kod birikmalarini yozing Hamming.
Beshinchi vazifaga kelsak - tekshirish algoritmini ishlab chiqish, u Hamming kodini dekodlash bilan bog'liq bo'lgani uchun quyida muhokama qilinadi.
Hamming kodini sintez qilish misolini ko'rib chiqing.
16 ta xabardan iborat ansambl bo'lsin va uni Hamming kodi bilan kodlash kerak ( d = 3).
Yechim:

1. 
   nazorat belgilar sonini aniqlang. Xabarlar ansambli N _va = 16 bo'lgani uchun, axborot belgilari soni n _va =lb16=4 ga teng. Shuning uchun foydalanish kerak formula
   

n _to  _ l b _ ( n _va
 bitta)  _ funt ( n _va
 1 ) _{  }  _ l b  5  3  _  funt _ sakkiz  3 .

Shunday qilib, n _k \u003d 3 , n \u003d n _va + n _k \u003d 4 + 3 \u003d 7.

2. 
   biz ushbu uchta nazorat belgisini joylashtirish kerak bo'lgan pozitsiyalarni aniqlaymiz. Bular 1, 2 va 4-pozitsiyalar bo'ladi (tab.ga qarang). 2).
   
3. 
   biz birinchi, ikkinchi va to'rtinchi ustunlarni to'ldirmasdan ikkilik ortiqcha bo'lmagan kodlarning kombinatsiyalari jadvalini tuzamiz. Hammasi bo'lib 16 ta kombinatsiya bo'ladi (1-jadval). 3).
   
4. 
   nazorat belgilarining qiymatlarini toping: nol kombinatsiyasi uchun hammasi Kj ₌ 0.
   

K _{1 belgisi uchun.}
K _{1 belgisining qiymati} tenglamadan aniqlanadi

K ₁  Va ₃  Va ₂  Va ₀ = 0.

a) K ₁ = 0
b) K ₁  0  0  1 =0; K ₁ = bitta
c) K ₁  0  0  0 =0; K ₁ = 0
d) K ₁  0  1  0 =0; K ₁ = 1
e) K ₁  0  1  0 =0; K ₁ = bitta
f) K ₁  0  1  1 =0; K ₁ = 0
3-jadval

Kombi	Xonalar	bitta	2	3	4	5	6	7	Dopol
millat	p/p	K 1	K 2	va 3	K 3	va 2	va 1	va 0	^Kqo'shimcha
a B C D E F	0 bitta 2 3 4 5 6 7 sakkiz 9 10 o'n bir 12 o'n uch 14 15	0 bitta 0 bitta bitta 0	0 bitta bitta 0 0 bitta	0 0 0 0 0 0 0 0 bitta bitta bitta bitta bitta bitta bitta bitta	0 bitta bitta 0 bitta 0	0 0 0 0 bitta bitta bitta bitta 0 0 0 0 bitta bitta bitta bitta	0 0 bitta bitta 0 0 bitta bitta 0 0 bitta bitta 0 0 bitta bitta	0 bitta 0 bitta 0 bitta 0 bitta 0 bitta 0 bitta 0 bitta 0 bitta	0 0 bitta bitta bitta bitta

₂ belgisi uchun .
K _{2 belgisining ma'nosi} tenglamadan aniqlanadi

K ₂  Va ₃  Va ₁  Va ₀ = 0.
a) K ₂ \u003d 0
b) K ₂  0  0  1 =0; K ₂ = bitta
c) K ₂  0  1  0 =0; K ₂ = bitta
d) K ₂  0  1  1 =0; K ₂ = 0
e) K ₂  0  0  0 =0; K ₂ = 0
f) K ₂  0  0  1 =0; K ₂ = bitta
K _{3 belgisi uchun.}
K _{3 belgisining ma'nosi} tenglamadan aniqlanadi

K ₃  Va ₂  Va ₁  Va ₀ = 0.

a) K ₃ \u003d 0
b) K ₃  0  0  1 =0; K ₃ = bitta
c) K ₃  0  1  0 =0; K ₃ = bitta
d) K ₃  0  1  1 =0; K ₃ = 0
e) K ₃  1  0  0 =0; K ₃ = bitta
f) K ₃  1  0  1 =0; K ₃ = 0
Jadvaldagi nazorat belgilarining qiymatini qo'yamiz. 3. Kod sintezlanadi.
Vazifa hal qilindi. (Talabaga mashq sifatida 3-jadvalni mustaqil ravishda bajarish taklif etiladi).
Olingan Xemming kodini d = 3 bilan misol tariqasida ishlatib, d = 4 bo'lgan Hamming kodi qanday tuzilganligini ko'rsatishimiz mumkin, bu esa ikkilamchi xatolarni aniqlash imkonini beradi. Bunday koddagi nazorat belgilarining soni yana bitta bo'lishi kerak, ya'ni. ko'rib chiqilayotgan misol uchun n _to = 3 + 1 = 4, shuning uchun kod sakkiz pozitsiyali bo'ladi.
Bunday kodni olish printsipi quyidagicha:

• 
  Har bir kod so'ziga bitta qo'shimcha tekshirish belgisi qo'shiladi, bu umumiy tekshirish imkonini beradi paritet;
  
• 
  qo'shimcha nazorat belgisining qiymati Xemming kodining har bir kombinatsiyasida (ya'ni nazorat belgilarini hisobga olgan holda) juft sonlar mavjudligiga qarab aniqlanadi. Shunday qilib, bizning jadvalimizda. 3 boshqa ustun paydo bo'ladi _Qo'shimchaga ; _
  
• 
  ushbu ustunni to'ldiring, ya'ni. boshqaruv belgilarining qiymatini aniqlang va ularni oxirgi (sakkizinchi) kodga joylashtiring lavozimlari:
  

a) K _qo'shish = 0 b) K _qo'shish = 0 c) K _qo'shish = 1 d) K _qo'shish = 1 e) K _qo'shish = 1 e) K _qo'shish = 1

8-ma'ruza

Hamming kodini dekodlash


d = 3 uchun Hamming kodini dekodlashni ko'rib chiqing (1-rasm):










Tuzatish uchun
Guruch. 1. Xemming kodini dekodlash algoritmining blok diagrammasi ( d = 3)

• 
  olingan kod so'zi bir qator paritet tekshiruvlaridan o'tkaziladi. Tekshiruvlar soni kod birikmasidagi va oldindan nazorat belgilarining soniga teng ma'lum;
  
• 
  bu boshqaruv belgilarining qanday pozitsiyalarda ekanligi ham oldindan ma'lum joylashtirilgan;
  
• 
  tegishli bandlar raqamlari cheklar;
  
• 
  har bir tekshirish natijasi ikkilik sonning mos keladigan raqami sifatida yoziladi, bu xato sindromi deb ataladi. Birinchi tekshiruv natijasida sindromning eng kam ahamiyatli raqami olinadi;
  
• 
  agar qabul qilingan kombinatsiya xatoliklarni o'z ichiga olmasa, har bir tekshiruv natijasi bo'ladi 0;
  
• 
  agar biron-bir pozitsiyada bitta xatolik mavjud bo'lsa, u holda bu pozitsiyani qamrab oluvchi paritet tekshiruvi 1 ni beradi, bu pozitsiyalardan birida xato mavjudligini ko'rsatadi;
  
• 
  barcha tekshiruvlar natijasida olingan ikkilik raqam (oxirgi tekshiruv sindromning eng muhim raqamini beradi), o'nlik ekvivalentda xatoning sonini ko'rsatadi. lavozimlar;
  
• 
  buzilgan belgini teskari belgi bilan almashtirib, tuzatamiz Xato;
  
• 
  nazorat belgilar (joylar ma'lum) o'chiriladi, qolgan kombinatsiyalar ishchilar.
  

d = 4 uchun Hamming kodining dekodlanishini ko'rib chiqing (2-rasm):
Tuzatish uchun
muvofiq

Sindrom
Guruch. 2. Hamming kodini dekodlash algoritmining blok diagrammasi ( d =4)

• 
  qabul qilingan kod birikmalari umumiy uchun tekshiriladi paritet;
  
• 
  birliklarning toq soni mavjudligini bildiradi xatolar;
  
• 
  xatoning joylashuvi ketma-ket qisman paritet tekshiruvlari orqali topiladi (qisman paritet tekshiruvlarida qo'shimcha tekshirish belgilari mavjud emas). ishtirok etish);
  
• 
  agar shaxsiy tekshiruvlar xatoni ko'rsatsa, lekin umumiy paritet tekshiruvi bunday bo'lmasa (3-rasm), bu qabul qilingan kombinatsiyada ikkita xatolik mavjudligini anglatadi, bu kodni tuzatib bo'lmaydi. imkon beradi.
  

"0"
"bir"




Частные провероки на четность
Xato

Общая проверка		"
отсутствует		"

1" ^{- xato, uning joyi} ko'rsatiladi
sindromi _0" - bor edi joy
ikki tomonlama ayb

Guruch. 3. Ikki marta xatolikni aniqlash uchun blok-sxema
d = 4 bo'lgan Hamming kodi ikki tomonlama xatolarni aniqlashga imkon beradi (lekin bunday xatolarni tuzatishga ruxsat bermaydi).
Misollar
Keling, bir nechta misollarni ko'rib chiqaylik.
Misol 1. d = 3 bo'lgan Hamming kodi bilan kodlangan "0100101" kod birikmasi uzatiladi "0100111" kombinatsiyasi qabul qilinadi. Xatolarni aniqlash jarayonini ko'rsating va uzatilgan ma'lumotlar kombinatsiyasini ko'rsating.
Yechim.

1. 
   Nazorat sonini aniqlang belgilar
   

n _k \u003d lb ( n +1) \u003d lb (7 + 1) \u003d 3. Shuning uchun tekshirishlar soni 3 ta.

2. 
   Birinchi tekshirish 1, 3, 5, 7 pozitsiyalarini qamrab oladi. Tekshirish beradi
   

0  0  1  1 =0. Shunday qilib, xato sindromining eng kam ahamiyatli raqamida
0 yoziladi.Ikkinchi tekshirish 2, 3, 6, 7 pozitsiyalarini qamrab oladi. Bu tekshirish 1  0 ni beradi.
 1  1 \u003d 1 (birliklar soni toq). Xato sindromining birinchi biti bo'lishi kerak

1 yoziladi. Uchinchi tekshirish 4, 5, 6, 7 pozitsiyalarini qamrab oladi. Bu tekshirish 0  1  1 ni beradi.
 1 =1 (birliklar soni toq). Xato sindromining ikkinchi (eng muhim) raqami 1 deb yozilishi kerak.

3. 
   Shunday qilib, xato sindromi "110" bo'lib, o'nlik songa to'g'ri keladi 6. Shuning uchun qabul qilingan kombinatsiyadagi xato oltinchi pozitsiyada sodir bo'ldi, bu erda "1" ni tuzatish kerak. "0".
   
4. 
   O'tkazilgan kombinatsiya "0100101". Axborot kombinatsiyasi 1, 2 va 4-o'rinlarda joylashgan nazorat belgilarini tashlash orqali olinadi, ya'ni. 01 0 0 101. Nihoyat olingan "0101".
   

Misol 2. “0101” axborot kombinatsiyasi uchun d = 3 bo'lgan Hamming kodini tuzing. Bu teskari vazifa.
Yechim.

1. 
   Axborot belgilarining soni n _va = 4. Boshqarish belgilarining sonini aniqlaymiz. Buning uchun biz foydalanamiz formula
   

n _k = ]lb {( n _va + 1) +]lb ( n _va + 1)[}[ = ]lb {(4 + 1) +]lb (4 + 1)[}[ =
=]lb (5 +]lb 5[)[=]lb (5 + 3)[ = 3.
Shunday qilib, nazorat belgilar soni n _k = 3 va ular 2 ^{m-1 pozitsiyalarini egallaydi} , ya'ni. Birinchisida K ₁ , ikkinchisida K ₂ , to'rtinchi pozitsiyalarda K _{3 .}

2. 
   Hamming kodli so'z tartibi shunday ko'rinadi
   

K ₁ K ₂ 0 K ₃ 1 0 1 .

3. 
   Boshqaruv belgilar jadvali asosida tenglamalar tuzib, boshqaruv belgilarining qiymatini aniqlaymiz pozitsiyalar
   

Avval K _{1 ni tekshiring}  0  1  1 = 0, bundan K ₁ = 0;
Ikkinchi tekshirish K ₂  0  0  1 = 0, bundan K ₂ = bitta;
Uchinchi tekshirish K ₃  1  0  1 = 0, bundan K ₃ = 0.

4. 
   Yakuniy tuzatish Hamming kodi "0100101". Misol 3. Quyidagi kod birikmalari kodda uzatiladi Hamming:
   

"1101001", "0001111", "0111100". Qabul qilingan "1001001", "0011111", "0110100". Ko'rsatish
xatolarni aniqlash jarayoni.
Yechim.

1. 
   Kombinatsiya qabul qilindi "1001001":
   

a) ikkilik son elementlarini aniqlash uchun tenglamalar tuzing - xato sindromi. Buning uchun jadvaldan birinchi, ikkinchi va uchinchi tekshiruvlar bilan qoplangan pozitsiyalar sonini yozamiz. Bizga ko'proq kerak emas, chunki tekshiruvlar soni kod kombinatsiyasidagi nazorat belgilarining soniga teng. Bizning holatda, kombinatsiyadagi belgilarning umumiy soni n = 7. Boshqarish belgilarining soni formuladan aniqlanadi va 3 ga teng, shuning uchun uchta tekshirish kifoya qiladi;
b) birinchi tekshiruv 1, 3, 5, 7 pozitsiyalarini qamrab oladi
1  0  0  1 =0.
Shuning uchun, ikkilik sonning eng kam ahamiyatli raqamida - xato sindromi, 0 yozilishi kerak;
c) ikkinchi tekshirish 2, 3, 6, 7 pozitsiyalarini qamrab oladi
0  0  0  1 =1.
Shuning uchun, xato sindromining birinchi bitida 1 yozilishi kerak; d) uchinchi tekshirish 4, 5, 6, 7 pozitsiyalarni qamrab oladi
1  0  0  1 =0.
Shuning uchun xato sindromining eng muhim (ikkinchi) raqami 0 yozilishi kerak.
Shunday qilib, ushbu kod birikmasi uchun xato sindromi 010 ni tashkil etadi, bu o'nlik raqamga to'g'ri keladi 2. Shuning uchun ikkinchi raqam xato.

2. 
   Ikkinchi kod birikmasi uchun "0001111":
   

0  1  1  1 =1.
0  1  1  1 =1.
1  1  1  1 =0.
Noto'g'ri toifa - uchinchi.

3. 
   Kod kombinatsiyasi uchun "" 0110100":
   

0  1  1  0 =0.
1  1  0  0 =0.
0  1  0  0 =1.
Noto'g'ri raqam - to'rtinchi.
misol. d = 4 bo'lgan Hamming kodi bilan kodlangan "01001011" kod birikmasi uzatiladi. Xatoni aniqlash jarayonini ko'rsating.
Yechim.
Qabul qilingan kombinatsiya "01001111":
a) umumiy paritetni tekshirish xato mavjudligini ko'rsatadi (birliklar soni juft);
b) xususiy cheklar boshqa misollarda bo'lgani kabi amalga oshiriladi. Tekshiruv summalarini tuzishda kod birikmalarining oxirgi birliklari (qo'shimcha tekshirish belgilari) hisobga olinmaydi.
2. Qabul qilingan kombinatsiya "01101111":
a) umumiy paritet tekshiruvi xato tuzatilmaganligini ko'rsatadi; b) shaxsiy cheklar (oxirgi belgi o'chiriladi)
Avval 0  1  1  1 = ni tekshiring bitta
Ikkinchi tekshirish 1  1  1  1 = 0
Uchinchi tekshirish 0  1  1  1 = bitta
Shunday qilib, shaxsiy tekshiruvlar xato mavjudligini aniqlaydi. U go'yo beshinchi o'rinni egallagan. Ammo umumiy tenglikni birinchi tekshirish xatoni tuzatmaganligi sababli, bu ikki tomonlama xatolik borligini anglatadi. Ushbu kod ikki tomonlama xatolikni tuzata olmaydi.
5-misol. “1101”, “1011” xabarlarini uzatish uchun tuzatuvchi Xemming kodining qanday birikmalari mavjud.
Yechim.

1. 
   Xabar uchun "1101":
   

a) n _va = 4; toping n _k = ]lb {( n _va + 1) +]lb ( n _va + 1)[}[ =3. b) kodli so'zning maketini tuzing
K ₁ K ₂ 1 K ₃ 1 0 1 .
c) nazorat belgilarining qiymatini tenglamalar asosida aniqlang Avval K 1ni _tekshiring  1  1  1 = 0, bundan K ₁ = bitta;
Ikkinchi tekshirish K ₂  1  0  1 = 0, bundan K ₂ = 0;
Uchinchi tekshirish K ₃  1  0  1 = 0, bu erdan K ₃ = 0. Kodlangan kombinatsiya "1010101" ga o'xshaydi.

2. 
   Xabar uchun "1011":
   

a) n _k \u003d 3;
b) K ₁ K ₂ 1 K ₃ 0 1 1;
c) Avval K _{1 ni tekshiring}  1  0  1 = 0, bundan K ₁ = 0;
Ikkinchi tekshirish K ₂  1  1  1 = 0, bundan K ₂ = 1;
Uchinchi tekshirish K ₃  0  1  1 = 0, bundan K ₃ = 0.
Kodlangan kombinatsiya "0110011".
Hamming kodlari shovqinga qarshi yuqori immunitetga ega va axborot uzatish kanallarida muvaffaqiyatli qo'llanilishi mumkin, agar statistika shuni ko'rsatadiki, bunday kanallarda ko'p sonli xatolar yuzaga kelishi ehtimoldan yiroq emas, aniqrog'i, agar bitta xatolar eng ehtimolli ekanligiga ishonish uchun asos bo'lsa.
To'g'ri, Hamming kodlarining yuqori shovqin immunitetiga sezilarli ortiqcha xarajat evaziga erishiladi.
Masalan, kod (7,4) uchun ortiqchalik l =( nn _va )/n=1-n _va /n=1-4/7 =0,429 Haqiqatan ham, Hammingga kiritilgan belgilarning umumiy soni yordamida kod birikmasi n=- n _va + n _to =7, 2 ^{7 = 128 ta xabarni} uzatish mumkin edi , ulardan faqat 2 ^{4 tasidan foydalanamiz.} = 16, ya'ni. taxminan 12,5%.