Blokiniai kodai
a0,a1…ak-1 – informacinis masyvasPapildžius informacini masyvą kontroliniais kodais c0,c1…cn-1, gausim sisteminį blokinį kodą:a0,a1…ak-1 c0,c1…cn-1n – bendras simbolių kiekisk – informacinių simbolių kiekisr – kontrolinių simbolių kiekisn-k=rVieni nuo sisteminiai kodai skiriasi kontrolinių simbolių sudarymo algoritmais.Vieni iš plačiai paplitusių sisteminių kodų – tiesiniai sisteminiai kodai. Jų kontroliniai kodai išreiškiami informacinių kodų pirmo laipsnio laipsniniais polinomais.• Tiesiniai sisteminiai dvejetainiai kodai išreiškiami: Cv=x0*a0+x1*a1+…+xk*ak; Cv=(nuo j=0 iki k-1)jv*aj; v=0…r-1 jv – dvejetainis koeficientasTarkime turime tiesinį kodą:(5,3)21=1 11=1 01=020=1 10=0 00=1C1=a2+a1C0=a2+a0Kombinacijos nuo000 C1=0 C0=0 0000001 C1=1 C0=1 00111010…111• Matricinis sisteminių kodų sudarymasVisas sisteminio kodo leidžiamas kombinacijas galima gauti turint pradines kombinacijas. Tos pradinės kombinacijos turi tenkinti sąlygas:• Neturi būti nulinės kombinacijos pradinėse kombinacijose• Kodinis atstumas tarp dviejų pradinių kombinacijų neturi būti mažesnis kaip dmin• Kiekviena pradinė kombinacija turi turėti kaip dmin vienetų skaičių.
a11 a12 … a1k b11 b12 … b1r a21 a22 … a2k b21 b22 … b2rPn,k= ………………………… ak1 ak2 … akk bk1 bk2 … bkr Informacinis Patikras Uk HpPn,k= Uk *HpPatikros matricos sudarymo sąlygos:• Vienetukų kiekis patikros matricoje turi būti ne mažesnis kaip dmin-1• Suma patikros matricos dviejų eilučių turi būti ne mažesnė kaip dmin-2Kontrolinių simbolių skaičiavimas tiesiniams kodams, naudojant patikros matricą:Sudaroma transponuota patikros matrica: b11 b21 … bk1 b12 b22 … bk2 Hp’= …………… bk1 bk2 … bkrPozicijos Hp’ pirmoje eilutėje turinčios vienetukus, nustatomos informacinės skiltys, kurios turi dalyvauti formuojant kodinės informacijos kontrolinę skiltį.Antros eilutės vienetukai nustatys formuojant antrąją kontrolinę skiltį.Dekoduojant sisteminius kodus, pakartotinai taikoma tokia pati kontrolinių bitų taisyklė, kaip ir perduodant . Todėl priėmimo vietoje tarpusavyje lyginamos dvi kontrolinių bitų grupės. Viena iš jų tiesiogiai priimta kontrolinių bitų grupė, kita grupė nustatoma pakartotinai dekoduojant kodo žodį.
Jeigu perduotas kodo žodis nebuvo iškraipytas ir klaidingų ženklų nėra, tai pakartotinai nustatyti kontroliniai ženklai bus gauti tokie patys kaip nustatė siuntėjas.O visi sindromo ženklai bus lygus nuliui. Jeigu perduodant įvyko klaida, sindromo kode atsiras vienetų.Jeigu kodo žodyje yra 1 arba 3 arba bet koks nelyginis vienetų skaičius, tik tada galima nustatyti, kad yra klaida, bet jos vietos nustatyti negalima.Kodų tipo perteklumas:kpert=r/nKodas su elementų padvigubinimuKiekvienam informaciniam simboliui įvedamas papildomas simbolis. Papildymas:1 papildomas 0 – 100 papildomas 1 – 01Perteklumo koeficientaskpert=0.5, nes gaunama dvigubai daugiau simbolių.Kodas atitinka visas klaidas išskyrus tas, kai klaidos yra poriniuose elementuose.
Inversinis kodasJo sudarymo pagrindas pradinės kodinės kombinacijos metodas. Tais atvejais kada pradinė kombinacija turi lyginį vienetukų skaičių, antra kombinacija tiksliai atitinka pradinę. Jeigu nelyginę – pakartojimas vykdomas invertuotame pavidale.kpert=0.5 Aptinka praktiškai visas kombinacijos klaidas. Nebus aptiktos, kai bus iškraipomi 2,4,6 ir t.t. elementų.
Cikliniai kodaiJie priskiriami tiesinių sisteminių kodų klasei. Esminė jų ypatybė – cikliškai perstatant leistinojo žodžio simbolius, gaunamas kitas leistinasis kodo žodis.Ciklinių kodų sudarymasKai pasirinktas konkretus generuojantysis polinomas (3 skilčių ir daugiau), tai ciklinį kodo žodį nusakantis polinomas sudaromas iš dviejų dalių. M(x) – informacinę kodo žodžio dalį atitinkantis polinomasR(x) – liekana [gaunama dalijant xn-k*M(x)/G(x)]G(x) – generuojantis polinomasF(x)= xn-k*M(x) + R(x)Aparatūriniu būdu kodavimą vykdo koderis – sudarytas iš postūmių registrų ir sumatorių.
R – postūmio registrai
Realiai schemoje sumatoriai būna tik prieš tas registrų skiltis prie kurių generuojančio polinomo koeficientai lygus vienetui. Grįžtamo ryšio kilpa uždaryta. Jungiklis J1 įjungtas, J2 apatinėje padėtyje.Koderio veikimas: per k taktų informacinis kodas per jungiklį J1 patenka I koderį.Cikliniai koderiai ir dekoderiai yra paprasčiausi.Klaidų aptikimas: priėmus kodo žodį, klaidos aptinkamos vykdant procedūrą analogišką kodavimui.
Matematinis klaidų aptikimo algoritmas pagrįstas tuo, kad kiekvieną ciklinio kodo žodį aprašantis polinomas dalijasi iš generuojančio polinomo be liekanos.Jeigu dalijant gaunama liekana, tai reiškia kad priimant įsivėlė klaida..Dalybos liekana atitinkantis kodas – sindromas.Aparatūriniu būdu klaidos aptinkamos pakartotinai koduojant priimtą kodo žodį. Koduojama tokiu pat koderiu kaip ir perduodant. Skirtumas tas, kad J2 visai nenaudojamas, J1 visą laiką įjungtas.Skirtingų nenulinių liekanų galimas skaičius:2n-1 sindromo kodas dar padeda nustatyti ir klaidingai priimtų klaidų vietas kode. Tam reikia sudaryti lentelę: (7,4)1 0 0 0 1 0 10 1 0 0 1 1 1 0 0 1 0 1 1 0Iteratyviniai kodaiJuose kodavimo operacijos vykdomos su simbolių visuma išdėstyta pagal keletą koordinačių:k=gklkl – informacinių simbolių kiekis vienoje koordinatėje.g – koordinačių kiekisdmin=g*dmin*ldmin*l – minimalus atstumas tarp kodų vienoje koordinatėje.
Dvimatis kodas su lygiškumo kontrole pagal stulpelius ir eilutesLygiškumo kontrolė – rašomas 0 arba 1 pagal vienetukų skaičių (lyginis ar nelyginis)Tokio kodo dmin=4Šis kodas aptinka visas nelygiško kartotinumo klaidas.Klaidų taisymas: jei neišpildoma lygiškumo sąlyga i-tajai eilutei ir j- tajam stulpeliui, tai simbolis pakeičiamas priešingu, esantis i – tosios eilutės ir j – tojo stulpelio susikirtime.Tokie daugiamačiai kodai nepaplito, o dvimačiai plačiau naudojami.Trūkumas didelis perteklumas.
Nepertraukiami kodaiNepertraukiami (rekurentiniai) kodai nuo kitų skiriasi tuo, kad kodavimo ir dekodavimo operacijos juose vyksta nepertraukiamai (simbolių seka į blokus nedalijama).Simboliai formuojami sudedant du (ar daugiau) informacinius simbolius perstumtus vienas kito atžvilgiu per tam tikrą atstumą (tl) – sudėties žingsnį.Labiausiai paplitęs grandininis rekurentinis kodas, dėl paprasto kodavimo ir dekodavimo. Jame patikros simbolis formuojamas iš gretimų informacinių simbolių. Kodo perteklumas 0.5.Priėmimo gale atskyrus kontrolinius (patikros) simbolius iš gautų informacinių vėl formuojami kontroliniai simboliai. Klaidos bus ištaisomos tada, jei du iš trijų simbolių einančių paskui kitą bus priimti teisingai.
Konvoliuciniai kodai, jų pavadinimą nusako sąsaja su konvoliuciniu integralu:x(t)=m(t-)g()dSkaitmenine forma ####Schemos veikimas: per vieną taktą įrašomas vienas informacinis simbolis, o išėjimas sukasi trigubai didesniu greičiuĮĖJIMAS R1 R2 R3 IŠĖJIMAS 0 0 0 0 000 1 1 0 0 111 0 0 1 0 001 0 0 0 1 011Tokio tipo kodai naudojami žmogaus kalbai koduoti.
Kodų efektyvumasInformacijos perdavimo sistemose korekciniai kodai naudojami klaidoms aptikti, klaidoms taisyti, klaidoms aptikti ir taisyti.Todėl ir kodų efektyvumas vertinamas rodikliais, kurie nusako kodo įtaka informacijos perdavimui. Teoriškai ir eksperimentiškai įvertinami:• Efektyvumo rodikliai, kurie susiję su klaidų sumažėjimu• Kita efektyvumo forma – kodo nulemti energetiniai išlošiai. Šie du rodikliai tarpusavyje susiję, nes kiekvienas klaidos pašalinimas, gali būti perskaičiuojamas į energijos išlošį.