|
6-ma'ruza
ARALGANLARGA QARSHI KURSHUVCHI QO'SHISHNI YO'Q QILISH USULLARI
Shovqinga qarshi kodlash.
dan himoya qilishning guruh usullari xatolar.
Ma'lumotlarni uzatish tizimlarini teskari tomondan tashkil etish ulanish.
Xatolarni tuzatish kodlash tamoyillari
Xatolarni tuzatuvchi kodlarning uch turi mavjud:
aniqlash bilan xatolar;
tuzatish bilan xatolar;
aniqlash va tuzatish bilan xatolar.
Xatolarni tuzatuvchi kodlarni yaratish printsipi shundan iboratki, barcha mumkin bo'lgan N kod birikmalari ikki guruhga bo'linadi: ruxsat etilgan N va (foydali ma'lumotlarni uzatish uchun mo'ljallangan) va taqiqlangan N ga (nazorat maqsadlarida foydalaniladigan ma'lumotlarni uzatish uchun mo'ljallangan).
Ruxsat etilgan va taqiqlangan kod birikmalari shunday tanlanadiki, har qanday aralashuv natijasida ruxsat etilgan kombinatsiyalar taqiqlanganlarga aylanadi. Keyin qabul qiluvchi tomonda xatolar mavjudligi fakti doimo aniqlanadi.
Keling, xatolarni tuzatish kodlarining asosiy xususiyatlarini ko'rib chiqaylik.
Kodning ahamiyati n. Kodning qiymati kod kombinatsiyasining uzunligi sifatida tushuniladi.
Axborot belgilarining soni n va . Kod kombinatsiyasida alifboning tegishli harfini bevosita ifodalovchi axborot belgilari hisoblanadi.
n gacha bo'lgan nazorat belgilar soni . Axborotni nazorat qilish (tuzatish) uchun xizmat qiluvchi qo'shimcha belgilar
n k \u003d n - n va .
Kodning ortiqchaligi l. Kodning ortiqchaligi deganda kodli soʻz uzunligining unga boshqaruv belgilarining kiritilishi hisobiga nisbatan koʻpayishi tushuniladi.
l = (n - n va ) / n = 1 - n va / n.
Kod masofasi d. Kod masofasi - ruxsat etilgan ikkita kod birikmasi orasidagi minimal masofa. Ikkilik xabarlar uchun
ruxsat etilgan ikkita kod kombinatsiyasining modulli ikkita yig'indisi natijasida olingan ikkiliklarning soni bilan belgilanadi.
Kod masofasini tanlash uchun odatda tengsizlikdan foydalaniladi
d _ r + s + 1, (*)
bu erda r - bu kod aniqlay oladigan xatolar soni ;
s - bu kod tuzatishga imkon beradigan xatolar soni va
r s.
Xatolarni tuzatish kodlarining sintezi
Xatolarni to'g'rilash kodini sintez qilish vazifasini quyidagicha shakllantirish mumkin: N va uzatilgan xabarlar to'plami berilgan , kodning shovqin-to'g'riligiga qo'yiladigan talablar ko'rsatilgan. Belgilangan talablarni eng tejamkor (minimal ortiqcha ma'noda) bajarilishini ta'minlaydigan kodni sintez qilish kerak.
Buning uchun siz quyidagilarni aniqlashingiz kerak:
n - kod so'zining uzunligi (bit chuqurligi kod);
kod masofasi d ;
nazorat belgilarining minimal talab qilinadigan soni n gacha va ular qiymatlar;
berilgan xabarlar to'plamini uzatish uchun zarur bo'lgan axborot belgilari soni n va ;
olingan cheklarning soni va tartibi xabarlar.
Bundan tashqari, boshqaruv va axborot belgilarini joylashtirish kerak bo'lgan pozitsiyalarni belgilash, sintezlangan kodning ortiqchaligini hisoblash va uni nazariy chegara bilan solishtirish, kodlovchilarni amaliy amalga oshirishdagi qiyinchiliklarni baholash kerak.
n va axborot belgilarining soni aniqlanadi , keyin - n gacha .
Axborot belgilarining soni uzatilgan xabarlar to'plamidan kelib chiqqan holda aniqlanadi
Boshqaruv belgilar sonini aniqlash uchun n to quyidagicha bahslashing.
n dan _ boshqaruv belgilari n ning kuchiga 2 ni tashkil qilishi mumkin Ikkilik kombinatsiyalar, ular "ha" yoki "yo'q" kabi javoblarni berishi kerak savollar:
Ushbu kod so'zi to'g'ri qabul qilinganmi? ?
Agar unda xatolik mavjud bo'lsa, n ta pozitsiyadan qaysi biri, shu jumladan boshqaruvchi? (Buni amalga oshirish uchun siz n pozitsiyani so'roq qilishingiz kerak, ya'ni n ni o'rnatishingiz kerak savollar.)
T ak va m bir tarzda , 2 n gacha _ d v o ich s _ kombinatsiyalangan va milliy _ _ _ _ _ kerak _ _ _ berish etydan _ _ yo'q _ uni o'zgartir _ Qanaqasiga ustida n
+ 1 savol, ya'ni.
2n dan _gacha
n 1. (2)
и к
Chunki n = n + n , keyin 2n _
2n va _ 2n dan _gacha
, bu erdan, (2) ni hisobga olgan holda, quyidagicha
2n _ 2n va _ ( n 1 ) ( 3 )
yoki
2n _
N va ( n 1). (4)
Paritet kodi
Shovqinni to'g'irlamaydigan kodda ortiqcha narsa yo'q ( n = n va va l =0) va uning barcha belgilari informatsiondir. Bunday kodning kod masofasi d 1 ga teng va u nafaqat tuzatishga, balki xatolarni aniqlashga ham qodir emas.
Manba kodining shovqinga chidamliligini yaxshilash uchun quyidagi usul taklif qilinishi mumkin (jadvalga qarang)
Boshlang'ich
kombinator
|
Qarama-qarshi
ramzi
|
Interferentsiya th
kod
|
bitta
|
2
|
3
|
000
|
0
|
0000
|
001
|
bitta
|
0011
|
010
|
bitta
|
0101
|
011
|
0
|
0110
|
yuz
|
bitta
|
1001
|
101
|
0
|
1010
|
110
|
0
|
1100
|
111
|
bitta
|
1111
|
Keling, jadvalda asl ortiqcha bo'lmagan kodning barcha kod birikmalarini tartibda (1-ustun) joylashtiramiz va quyidagi printsip bo'yicha boshqaruv belgilari ustunini (2-ustun) tuzamiz: agar kod so'zida birliklar soni bo'lsa. manba kodi toq bo'lsa, boshqaruv belgisi uni juftlikka to'ldirishi kerak.
d =2 bo'lgan xatoni to'g'rilash kodini olishimizni ko'rish oson . Bunday kod bitta xatoni aniqlay oladi. Haqiqatan ham, (*) tengsizlikda biz r = 1 va s = 0, keyin d =2 ni qo'yishimiz kerak.
Shuning uchun, ishonchli bo'lmagan manba kodi, boshqaruv belgilarini qo'shish orqali (har bir so'zda bittadan) xatolarni to'g'rilaydigan, xatolarni aniqlaydigan kodga aylanadi. Boshqacha qilib aytadigan bo'lsak, kodning shovqinga qarshiligi ortiqcha xarajatlar evaziga olinadi.
Olingan kodda ortiqcha mavjud
l \u003d (n - n va ) / n \u003d 1 - n va / n \u003d 1 - 3/4 \u003d 0,25.
Bunday kod paritet tekshiruviga ega kod deb ataladi (paritetni tekshirishga ega kod ham xuddi shunday tarzda tashkil etilishi mumkin). g'alati).
Xatoni aniqlashning ma'nosi shundaki, qabul qiluvchi tomon olingan kombinatsiyani juft sonli birliklar uchun tekshiradi. Agar undagi birliklar soni g'alati bo'lsa, u "rad etilgan", chunki kod birikmasida xatolik yuz berdi. Bu uchun asos so'roq qilish.
Ko'rib chiqilayotgan kod xatolarni tuzatishning eng oddiy kodidir, ammo paritetni tekshirish printsipi ko'plab juda murakkab xatolarni tuzatish kodlarida qo'llaniladi.
Do'stlaringiz bilan baham: | 
