|
9-ma'ruza
SIKLIK KODLAR
Tsiklik kodlar tizimli ajratiladigan kodlarga tegishli. Ushbu kodlarning ikkita xarakterli xususiyati e'tiborni tortadi.
Birinchidan, deyarli cheksiz tuzatish imkoniyatlari, bu ularni statistik tahlil aloqa kanalida paydo bo'lish imkoniyatini ko'rsatadigan murakkab shovqin muhitida ayniqsa jozibador qiladi.
bir nechta va ayniqsa portlash xatolari, ya'ni. Xemming kodlari ma'lum bir shovqin immunitetini ta'minlay olmaydigan sharoitlar.
Ikkinchi xususiyat - tsiklik kodlar uchun kodlash va dekodlash qurilmalarini muhandislik tatbiq etishning o'ta soddaligi.
Belgilangan afzalliklar hozirgi vaqtda tsiklik kodlarning juda keng tarqalganligiga olib keldi.
Tsiklik kodlarning nazariy asoslari
Tsiklik kodlarni ishlab chiqish, ularni sintez qilish usullari, kodlash va dekodlash algoritmlarini ishlab chiqishning nazariy asosi mavhum algebra sohasi bo'lib, u guruhlar algebrasi deb ataladi, shuning uchun tsiklik kodlar ba'zan guruh kodlari deb ataladi.
Kodlash va dekodlash uchun ikkilik polinomlar algebrasi (koeffitsientlari 0 va 1 bo'lgan polinomlar) yoki ular aytganidek, ikkilik maydon ustidagi ko'phadlar Galois maydonidan foydalaniladi. Galua maydoni GF(2) bilan belgilanadi.
Maydon - bu turli tabiatli elementlardan tashkil topgan to'plam bo'lib, ular uchun ikkita asosiy amal qonunlari aniqlanadi: qo'shish va ko'paytirish. Ushbu asosiy operatsiyalar kommutativlik va assotsiativlik qonunlarini qondirishi kerak.
Qo'shishni ko'paytirish
a + b = b + a - kommutativlik - ab = ba
a + (b + c) \u003d (a + b) + c - assotsiativlik - a (bc) \u003d (ab) cyu
Ushbu operatsiyalar taqsimot qonuni bilan bog'liq
[(a +) c = ac + bc],
Bundan tashqari, qo'shish teskari operatsiyaga ega - ayirish.
Bu amallarning ikkalasi ham yopilish shartiga ega boʻlishi kerak: maʼlum toʻplamning ikkita elementini qoʻshish natijasida a va b , faqat shunday elementni olish mumkin c , u ham shu toʻplamga tegishli,
bular. agar a G, b G, va a + b = c, keyin c G. Xuddi shu narsa ikkinchi operatsiyaga ham tegishli.
Haqiqatan ham, agar qo'shish (yoki ko'paytirish) natijasida berilgan to'plamga tegishli bo'lmagan elementni olish mumkin deb hisoblasak, ya'ni. agar yopish talablari bajarilmasa, u holda ushbu operatsiyalar natijasida kodlashda biz qabul qilingan kodlash tizimidan tashqariga chiqishimiz mumkin.
Savol tug'ilishi mumkin: bu algebraik fikrlashning ko'rib chiqilayotgan xatolarni tuzatish kodlash muammosiga qanday aloqasi bor? Bu eng to'g'ridan-to'g'ri ko'rinadi.
Har bir kod birikmasi ba'zi bir mavhum o'zgaruvchining tegishli darajasidagi ko'phad sifatida ifodalanishi mumkin x .
Masalan, kombinatsiya "10101" - 1 2 4 + 0 2 3 + 1 2 2 + 0 2 1 + 1 2 0 balki bo'l shaklida yozilgan polinom
1 x 4 + 0 x 3 + 1 x 2 + 0 x 1 + 1 x 0 = x 4 + x 2 +1.
Biz mavhum o'zgaruvchining koeffitsientlari x 1 yoki 0 ekanligini ko'ramiz, ya'ni. GF(2) ning elementlari va darajalari raqamlar soniga mos keladi. Ta
o'nli sonlardagi bir xil birikma 21 raqamiga to'g'ri keladi. Shunday qilib, biz ikkilik ko'phadlarning turli ko'rinishlarini olamiz.
x 4 + x 2 +1 21 10101.
Tsiklik kodlar shu bilan tavsiflanadiki, berilgan kodning barcha kombinatsiyalari bitta boshlang'ich kombinatsiyadan tsiklik o'ngdan chapga siljish yo'li bilan tuzilishi mumkin, eng chap qatorning belgisi esa eng kam ahamiyatli raqam joyiga - oxirigacha siljiydi. kombinatsiya. Masalan, "10101" asl kombinatsiyasi:
siljish 01011
siljish 10110
siljish 01101
siljish 11010
5 smenali 10101,
bular. asl kombinatsiya takrorlanadi. Bu xususiyat ushbu kodlarning nomini tushuntiradi - tsiklik.
Kod so'zining tsiklik siljishi mos keladigan ko'phadni x ga ko'paytirishga o'xshaydi:
000101 0 x 5 + 0 x 4 + 0 x 3 + 1 x 2 + 0 x 1 + 1 x 0 = x 2 + bitta;
001010 0 x 5 + 0 x 4 + 1 x 3 + 0 x 2 + 1 x 1 + 0 x 0 = x 3 + X;
010100 0 x 5 + 1 x 4 + 0 x 3 + 1 x 2 + 0 x 1 + 0 x 0 = x 4 + x 2 ;
101000 1 x 5 + 0 x 4 + 1 x 3 + 0 x 2 + 0 x 1 + 0 x 0 = x 5 + x 3 ;
(x 2 + 1) x x 3 + x 001010; (x 3 + x) x x 4 + x 2 010100; (x 4 + x 2 ) x x 5 + x 3 101000.
Agar polinom darajasi kod sig'imiga yetsa, u holda x da nol darajaga "o'tkazish" sodir bo'ladi va tsikl takrorlanadi. Tsiklik kodli enkoderlarda bu operatsiya eng muhim raqamning yacheyka chiqishini nol raqamli katakning kirishiga ulash orqali amalga oshiriladi. Har qanday ikkita qo'shni birikmaning Modulo 2 qo'shilishi birinchi a'zoning birikmasiga mos keladigan ko'phadni x + 1 ko'phadga ko'paytirish operatsiyasiga ekvivalent bo'ladi, agar o'xshash a'zolarni qisqartirish moduli 2 amalga oshirilsa.
Misol: 000101
001010
001111
x 2 + 0 + 1 000101
x + bitta
x 2 + 0 + bitta
x 3 + 0 + X
x 3 + x 2 + x + 1 001111.
Shunday qilib, siklik kodning har qanday kod so'zini maxsus tanlangan ko'phadni qandaydir boshqa ko'phadga ko'paytirish orqali olish mumkin.
Do'stlaringiz bilan baham: |
