Eksamiküsimused ja vastused 2009 (0)

EKSAMIKÜSIMUSED 2009
1. Infoedastussüsteemi struktuurskeemid. Üksikute osade: infoallikas , kooder ,
edastuskanal jne ühtsed kirjeldused. Infoedastuse põhiseadused.
(Slaididelt: paragrahv 1)
Struktuurskeem :
info allikas -> kodeerimine -> edastuskanal -> dekodeerimine -> info tarbija
Info allikas – edastamisele kuuluvad teatud sõnumid ajalise järjestikuse jadana, siia lisandub ideaalne vaatleja, kes saab sõnumis aru; info allikad on pidevad (elektrilised signaalid ) ja diskreetsed (lõplik arv teateid, diskreetsed allikad võivad olla lihtallikad ja kahendallikad); diskreetsed lihtallikad võivad olla mäluta (üksteiele järgnevad sümbolid on teineteisest statistiliselt sõltumatud) või mäluga (sümbolid on stat. sõltuvad); diskreetsel kahendallikal on kaks võimalikku väljundsümbolit – null ja üks;
Kodeerimine – kooder on sobituste kogu;
Edastuskanal – edastuskanalil on välismõjud; edastuskanal on tehniliste vahendite kogum, toimib teatud reaalses füüsikalises keskkonnas, kus on mürad ja häired; edastuskanalid võivad samuti olla pidevad ja diskreetsed; pidev kanal on primaarne ning ta kutsub oma omadustega esile diskreetse kanali; edastuskanali sisendis moodustatakse vajalikud kanalisignaalid;
Dekodeerimine – kasutatakse ära kodeerimisel tekkinud lisaväärtused;
Info tarbija – on passiivne, tagada tuleb usaldusväärsus;
Kirjeldused:
Infoallika ja edastuskanali kirjeldused käituvad ühtsetes ühikutes. Infoallika teated esinevad mingi juhuslikkusega.
Kanali läbilaskevõime on kanali väljundis saadava info hulga ülemine piir ajaühikus.
Infoallikat iseloomustavad: infoallika entroopia , infotekke kiirus
Edastuskanalit iseloomustavad: kanali läbilaskevõime, sümboli vigasuse tõenäosus kanalis ;
Põhiteoreem:
R(x) ≤ CK – ε, ε≻ 0, siis on olemas selline kooder, et vigasuse tõenäosus läheneb nullile .
R(x) on infotekkekiirus
Ck – kanali läbilaskevõime
2. Diskreetsed infoallikad. Erinevad liigid. Kirjeldused.
(Slaidid: paragrahv 1 slaidid 14-17 ja paragrahv 2)
Diskreetne viitab sellele, et teateid on lõplik arv.
Diskreetsed infoallikad on:

lihtallikad – koosneb sümbolitest, on mäluga ja mäluta allikad
Kui üks sümbol ei mõjuta järgmiste esinemise tõenäosust on tegemist mäluta allikaga, näiteks tekst on mäluga allikas.
Markovi allikas – täht mõjutab järgmise tähe aga mitte enam ülejärgmise tähe esinemist ehk Markovi allikas on ilma järelmõjuta

kahendallikad – sümbolid null ja üks
Diskreetseid infoallikad kirjeldatakse seisundite tabeliga (sümbol, selle esinemise tõenäosus). Seisundiks ongi genereeritud sümbol. Seisundite tabel on täielik, kui tõenäosuste summa on üks. Kirjelduseks kasutatakse ka mõistet entroopia,mis on allika määramatuse mõõt. Näiteks kui kahe sümboli esinemise tõenäosused on võrdsed, siis määramatus on kõrge ehk rakse on määratleda milline sümbol järgmisena tuleb.
Liiane allikas on allikas, mille puhul väljastatavate elementaarsete sümbolite esinevuse tõenäosused ei ole võrdsed.

Pidevad infoallikad. Erinevad liigid . Kirjeldused.
(Slaididelt paragrahv 3, slaidid 1-4, 10)
Pidevad infoallika väljundiks on näiteks elektrilised signaalid, mil juhtudel ajas muutub pinge ja vool ehk tegemist on juhusliku ajas muutuva protsessiga. Sellise pideva signaali kirjeldamiseks kasutatakse väljavõtteid signaalist.
Olgu x väljavõtte juhuslik väärtus, millel on tõenäosustiheduse jaokstusseadus w(x). Tõenäosus, et x satub ajaintervalli Δx on w(x)* Δx. Signaali väärtusi võetakse pidevast signaalist teatud ajaintervallide järel: diskreertimise ajaintervall peab olema 1/(2ΔFx), kus Fx on elektrilise signaali spektrilaius. Võib järeldada, et pidevat signaali ei saa esitada lõpmatult täpselt. Täpselt võib kirjeldada vaid üht signaali väljavõtet.
Pideva signaali entroopia:
ΔFk on signaali spektri laius
Tx on signaali pikkus
δe2 on esitamistäpsus
δx2 allika võimsus
!!! Gaussi kanal kuulub pidevate kanalite hulka. Gaussi kanali strukuur : sisendis on sisendsignaal -> väljundis on sisendsignaal + müra.
!!! 4. Entroopia mõiste, mõõtühikud ja omadused. Milleks kasutada.
(Slaididelt paragrahv 2, slaidid 2,3,11, 12)
Mõiste:
Entroopia on allika määramatuse mõõt. Näiteks kui kahe sümboli esinemise tõenäosused on võrdsed, siis määramatus on kõrge ehk rakse on määratleda milline sümbol järgmisena tuleb.
Omadused:
Entroopia on suurem nullist. Entroopia on null kui leidub selline sümbol, mille esinemise tõenäosus on null. Entroopia on maksimaalne, kui kõigi sümbolite esinemise tõenäosused on võrdsed.
Entroopiat mõõdetakse bittides.
5. Tingliku entroopia mõiste ja omadused. Kuidas kasutada.
(Slaididelt paragrahv 2, slaidid 2,3,11, 12)
Tinglik entroopia tähendab informatsiooni hulka, mille me saame ühe suuruse Y teada saamisel, eelduselt et suuruse X tegelik väärtus on juba teada. (Y tingimusel X).
Kui X ja Y on sõltumatud, siis: H(Y | X) = H(Y)
Tingliku entroopia põhimõte: Oletame, et on vaja teada H(X,Y) bitti informatsiooni, kui teame X väärtust on meil H(X) bitti informatsiooni teada ning H(Y/X) bitti infot on teadmata. H(Y/X) leidmisel saame ülejäänud H(Y/X) bitti infot ka teada.
6. Diskreetse kahese allika infotekkekiirus ja liiasus.
(Slaididelt paragrahv 2 slaid 2,7)
Diskreetne kahendallikas annab välja vaid sümboleid null ja üks.
Tema entroopia avaldub: H(X) = -[P(x1)*log2P(x1) + P(x2)*log2P(x2)], kus P(x1)=P(0) on esimese sümboli esinemise tõenäosus ja P(x2)=P(1) on teise sümboli esinemise tõenäosus.
!!! Liiasus - sümbolite esinemise tõenäosused ei ole võrdsed, kui liiasus on nullist erinev
Liiasus avaldub:
U(x) = [ Hmax (X) – H(X)] / Hmax(X) = 1 - H(X)
Hmax(X) on infoallika maksimaalne entroopia ehk entroopia juhul kui kõik sümbolid esinevad võrdsete tõenäosustega. Hmax(X) = -(0.5*log20.5 + 0.5*log20.5 ) = 1
!!! infotekkekiirus?
7. Diskreetse liitallika infotekkekiirus ja liiasus.
(Slaididelt paragrahv 5 slaid 12; paragrahv 5, slaid 5)
Diskreetse liitallika entroopia avaldub H(X + Y) = H(Y) + HY(X). Tingimusel, et kõigi sümbolite tekkeaeg on samasugune ühe allika jaoks τx ja teise allika jaoks τy , siis infotekkekiirus avaldub:
!!!R(X) = H(X + Y) /(τx +τy )
Liitallika liiasus:
U(X) = [Hmax(X + Y) - H(X + Y)] / Hmax(X + Y), kus maksimaalne entroopia leitakse, kui kõigi võimalike sümbolite esinemise tõenäosused on võrdsed.
8. Diskreetne Markovi allikas. Infotekkekiirus ja liiasus.
(Slaidid: paragrahv 2, slaidid 21 -25)
Markovi allikas on selline, et sõltuvuses on ainult kaks kõrvuti asetsevat teadet.
H(X0, X1, X2, X3...) = H(X0) + Hx0(X1) + Hx1(X2) + Hx2(X3) ...
Infotekke kiirus Markovi allikal:
Rm(X) = [H(X0) + k*HXn(Xk)] / k* τx , kus n on k-1 ning k on teadete arv ning τx on sümbolite tekke aeg.
Liiasus: U(X) = [Hmax(X0, X1, X2, X3...) - H(X0, X1, X2, X3...] / Hmax(X0, X1, X2, X3...)
9. Entroopia mõiste kasutamine edastuskanali kirjeldamiseks.
Entroopia on määratud sümbolite esinemise tõenäosustega, seega iseloomustab entroopia edastuse vigasust.
!!! 10. Infoedastuse põhiteoreem.
(Slaididelt paragrahv 1, slaid 9)
Põhiteoreem:
R(x) ≤ CK – ε, ε≺ 0, siis on olemas selline kodeermisviis, mis kindlustab lõpliku edastuskiiruse korral edastuskanalis edastuse usaldatavuse tõenäosuse lähenemise ühele.
R(x) on infotekkekiirus
!!! 11. Müravaba kanali läbilaskevõime.
(Slaididelt paragrahv 1, slaid 8; paragrahv 5, slaid 5)
Müravaba tähendab, et vigasid ei ole, kõik jõuab vastuvõtjani. Seega läbilaskevõime on:
= sup
!!! Ik on signaali infohulk ajaintervallis ja Tk on ajaintervall. Kui puuduvad mürad, siis kogu infohulk, mis edastati jõuab vastuvõtjasse. Põhimõtteliselt võivad lisanduda vaid välised häired. Kogu sisendsignaal edastatakse. (Infohulga kohta paragrahv 2a slaididelt)
12. Pideva edastuskanali läbilaskevõime.
(Slaididelt paragrahv 6, slaid 8-10, 13-15)
Pidev edastuskanal on selline, milles toimuvad protsessid on pidevad või siis vaadeldakse protsesse vaadeldakse pidevalt. Kanali sisendis on mingi signaal koos edasi kantavate parameetrite koguga ning kanali väljundis on edastatud signaal koos mürade (peamiselt tingitud kanali seadmetest) ja häiretega (seadmete välised).
Pideva edastuskanali läbilaskevõime avaldub:
Δfk on edastuskanali ribalaius
δ2 = Δfk *N0 müra dispersioon ehk müra keskmine võimsus
Ps on sisendsignaali võimsus
I2=
I on pidevsignaali iga väljavõtte kohta saadud infohulk, see infohulk on normaaljaotusega.
Kanali läbilaskevõime sõltub signaali ja müra suhtest :
!!! 13. Infoedastus pidevas edastuskanalis: kanalisignaalide valiku kriteerium .
(Slaididelt paragrahv 7, slaid 2,6,7)
Infoedastus pidevas kanalis toimub liinikoodide (ehk liinisignaalide ehk kanalisignaalide) abil. Liinikoodid on lõpliku pikkuse ja teatud kujuga signaalid.
Kanali signaalid peab kindlasti valima nii, et neid oleks võimalik eristada. Signaalid on eristatavad kui on kindlustatud nende vaheline ruutkeskmine kaugus. Signaali sümbolite pikkused on ühesugused.
Signaalide vaheline kaugus :
d012=(p.s. integraal nullist tauni)
14. Otsene kanalisignaalide valik ja erinevate otseste modulatsioonidega saavutatav
signaalidevaheline kaugus. (slaididelt 7)
Otsest meetodit kahendkanali jaoks nimetatakse ka digitaalseks edastamiseks. Kanalisignaalideks on s(t)=s0(t) ja s1(t), kus t=[0...τ] ja τ on sümboli/kanalisignaali pikkus e aeg, mille jooksul edastatakse kanalis üks sümbol. Edastamine toimub ajas järjsetikku.
Kanalisignaalid tuleb valida nii, et oleks kindlustatud nende vaheline ruutkeskmine kaugus. Neid peab saama eristada.
Signaalide vaheline kaugus on määrtud valemiga d01^2=∫( s0(t)- s1(t)) ^2dt. Integraal on vahemikust 0-st τ-ni. Kui see peaks võrduma 0ga, pole signaale võimalik eristada. Kui
s1(t)=-s0(t), siis on kaugus suurim.
15 Sümbolitejada eelnev töötlemine ja suhteline faasmodulatsioon. (slaididelt 7)
Suhtelise signaalide valiku korral kodeeritakse sümbolite jada üle. Saadud ülekodeeritud sümbolitejada moduleeritakse näiteks faasmodulatsiooniga – suhteline modulatsioon. Selline toiming viib sisse sümbolite omavahelise sõltuvuse ja vähendab kanalisignaalide spektri laiust. Sellise liinisignaaliga kanal on mäluga edastuskanal. Sümbolitevaheline sõltuvus võib osutuda kasulikuks müradega edastuskanali korral.
16. Kahe signaali optimaalne eristamine.(8 Pideva edastuskanali häirekindlus)
Sõltub sellest, kuidas on valitud liinikoodid ja kuidas teostatakse nende vastuvõttu erinevate mürade ja häiretega foonil. Sümbolite kaupa vastuvõtul, võetakse iga sümbol vastu eraldi. Kui esimese sümboli vastuvõtmine on lõpetatud, viiakse vastuvõtj algseisundisse ja võetakse vastu teine sümbol jne. Vastuvõtu poolel on vaja kindlaks teha, kumb signaalidest edastati: s(t)+n(t)=s0(t) või s1(t) +n(t), kus t=[0...τ]. τ on otsustusaja kestus. Sümboli väärtust saab fikseerida signaali lõpus või signaali keskel. Vastuvõtja analüüsib signaali ja müra segu ja selle alusel võtab vastu otsuse, kas sisendis oli signaal, mis kandis edasi sümbolit 0 või sümbolit 1. Signaali ja müra segu s0(t)+n(t) muutub mõjuva müra tõttu sarnasemaks signaalile s1(t) ja vastupidi. Vastuvõtja hakkab valesti otsustama – eksima – nullid tuvastatakse ühtedena ja ühed asenduvad nullidega. Optimaalsel vastuvõtul tuleb vigasuse tõenäosus μ ajada miinimumi, kas otseselt või funktsioonide abil.
17 Kahe täiesti teada oleva signaali optimaalse eristaja struktuurskeem.(8 Pideva edastuskanali häirekindlus)
Koherentne vastuvõtt=täiesti teadaolev vastuvõtt. Ainuke teadmata fakt vastuvõtu poolel on see, kumb signaalidest oli edastatud. Kas see, mis kandis edasi sümbolit 1 või see, mis kandis edasi sümbolit 0. See on täpselt teada olevate signaalide eristamise ülesanne. Sellist vastuvõttu iseloomustavad häirekindluse kõverad on parimad. Algoritmiks on see, et arvutatakse mõlema signaali ruutkeskmised kaugused ja võrreldakse neid. Optimaalse vastuvõtja struktuure sab muuta, avaldades vastuvõetud signaali ja tugisignaalide vahelise kauguste valemid. Struktuurskeem on slaidil 20.
18. M- modulatsiooniga signaalide optimaalse eristaja struktuurskeem .(8 Pideva edastuskanali häirekindlus)
Kui vastuvõetud signaal ei ole binaarne , kasutame M-kanalist korrelatsioonvastuvõtjat. Sümbol fikseeritakse signaali lõpus ja valik toimub suurima saavtatud väärtuse järgi. M-modulatsiooniga signaalide reaalne vastuvõtja on enamasti kahekanaliline. Struktuurskeem on slaidil 34.
19. Optimaalse eristaja häirekindluse kõverad. (8 Pideva edastuskanali häirekindlus)
Optimaalne vastuvõtja on reaalsest B dB parem. Kui B=logρr/ρo., kus ρ on signaal/müra suhe.
Häirekindluse kõverad sõltuvad sellest mis me teame ja mida vastu võtame. Kui teame signaalide kujusid jne kanalis, aga ei tea kumb neist on -> täielikult teada olevate signaalide eristamise ülesanne. Saab rehkendada piirväärtusliku häirekindluse kõvera järgi. SNRid on ühesugused, kumb annab halvema vigasuse tõenäosuse. Kõige vasakpoolsem joon on parim.
20. Pideva edastuskanali häirekindlust määravad faktorid. .(8 Pideva edastuskanali häirekindlus)
Oodatavate signaalide algusmomendid, pikkus, keskmine sagedus, algfaas. Leiame tõenäosus, millega tegelik sisendsignaal esineb tõenäosemalt kui teine. Leiame juhusliku suuruse jaotusseaduse – Gaussi. Seejärel leiame tema autokorrelatsioonifunktsiooni kaudu keskväärtuse. Siit leiame sümboli vigasuse tõenäosuse.
21. Koodide liigitus vigasid korrigeerivate toimingute järgi.(10. Koodide liigid)
Koodid jagunevad vigasid avastavateks ja vigasid parandatavateks koodideks. Vigasid avastavad on need koodid, kus koodi detekteerimisel saab vastuse, kas koodsõna on vale või õige (nt paariskood, ühtlase kaaluga kood). Vigasid parandavad koodid jagunevad ühekordseid, kahekordseid jne vigu parandatavateks. Koodisõna jaotatakse informatiivseteks ja liiaseteks sümboliteks. Liiaste sümbolitega peab olema võimalik tähistada kõik vigased koodiseisundid.
Effektiivsed koodid, mida kasutatakse liiaste diskreetsete infoallikate sobitamiseks müravabade edastuskanalitega. Häirekindlad ehk korrigeerivad koodid, mida kasutatakse tavaliselt diskreetse infoallika sobitamiseks mäluta müradega (st vigasid tekitavate) edastuskanalitega. Mäluga edastuskanalite korral kasutatakse erili vigade pakette korrigeerivaid koode.
22. Shannon – Fano kood.(5. Diskreetse müravaba edastuskanali sobitamine liiase deiskreetse infoallikaga)
Effektiivne kood. Kõik kodeeritud teated järjestatakse esinemistõenäosuste vähenevasse ritta . Kõik kodeeritud teated vähenevas reas jaotatakse 2 rühma nii, et mõlema rühma summaarsed esinemistõenäosused oleks lähedase väärtusega 0,5le. Esimesele poolrühmale omistatakse esimene sümbol 0 ja teisele poolrühmale 1. Esimesed poolrühmad jaotatakse kumbki kaheks alamrühmaks nii, et mõlema alamrühma summaarsed tõenäosused oleks võrdsed 0,25le. Esimestele alamrühma teadetele teadetele omistatakse koodsümbol 0 ja teisele 1. Jaotust jätkatakse tõenäosustega 1/(2^k) seni kuni igas viimases alamrühmas on ainult üks kodeeritav teade. Madal häirekindlus.
23. Huffmani kood (5. Diskreetse müravaba edastuskanali sobitamine liiase deiskreetse infoallikaga)
Effektiivne kood. Kõik kodeeritavad teated järjestatakse esinemistõenäosuste vähenevasse ritta. Rea kahe viimase teate tõenäosused liidetakse ja moodustatakse uus vähenev rida. Järjestamist korratakse kuni jääb alles ainult üks järjestatud element. Moodustatakse koodpuu, arvestades liidetud tedete uusi asukohti. Koodipuu liikumistele omistatakse sümbolid 0 ja 1.
24. Häirekindlate koodide koostamise põhialused.(9. Kodeerimise põhialused, 10. Koodide liigid)
On sellised koodid, millistesse on sisse viidud korrastatult liiasus nii, et tekiksid koodi omadused korrigeerida kindlat tüüpi sümbolite edastusel tekkinud vigasid. Tavaliselt on häirekindlad koodid ühtlased. Häirekindlad koodid on võimelised avastama teatud kordsusega vigu, parandama teatud kordsusega vigu, taastama kustutusi. Kui koodi alus on m ja koodsõna pikkus on n, siis erinevate koodsõnade arv on NY=m^n. Koodi liiasuse sisseviimine tähendab seda, et koodidena kasutatakse vähem NX Bernoulli katsete seeriale lähedane.Kombinatsioonide arv n-st q kaupa*müü astmes q* (1-müü)astmes n-q.
N=k+r. 1+summa q=1st n-ni tõenosusus 1. Otsene ehk tavaline
ja 2. Faktorringis

Lõplik korpus on kinnine liitmistehete ja korrutustehete suhtes. See tähendab,et korpuse elementide liitmisel ja korrutamisel saame sellesse korpusesse kuuluva elemendi.

Igale elemendile a leidub liitmise suhtes pöördelement –a. Igale nullist erinevale elemendile leidub korrutamise suhtes pöörelement a-1 . See võimaldab defineerida lisaks liitmisele ja korrutamisele ka lahutamise ja jagamise nullist erineva elemendiga: a-b= a+ (-b) ja a/b=a*b-1 . Niisiis võib väita, et lõplik korpus on selline elementide kogu, mis on kinnine nelja peamise aritmeetilise tehte suhtes, v.a. jagamine nulliga.
Aritmeetiliste tehete suhtes kehtib assotsiatiivsus [a+ (b+ c)= (a+ b)+ c] , distributiivsus
[a* (b +c )= a *b + a *c], kommutatiivsus a+ b= b +a ja a *b =b *a.
Nii korrutamine kui liitmine toimub modulo 2 järgi.
41. Hulkliikmete liitmine, kui kordajad kuuluvad lõplikku korpusesse GF (2m ).
(raamat lk.14-16 ja loengumaterjalid 13- (10.märts))
See ei ole tavaline liitmine ja korrutamine, vaid selline mille tulemuseks loetakse jääki: nt. 3*mod74=5 (3*4=12 ja 12-7=5). Liitmine toimub positsiooniliselt, kordajad liituvad modulo 2 järgi.
Hulkliikmete liitmine: Korpuses GF(2) on elemente kaks 0 ja 1 ja nende liitmine toimub modulo 2: 0+modulo20=0, 0+modulo21=1, 1+modulo20=1, 1+modulo21=0
42. Hulkliikmetejagamine, kui kordajad kuuluvad lõplikku korpusesse GF (2m )
(natuke on mainitud loengus nr.13 ja raamat lk. 18-19)
Jagamine on kahel viisil, kas tavaline (tulemuseks on jagatis ) või faktorringis (tulemuseks on jääk).
Otsene jagamine: Q(z)/g(z)=f(z)
Nt. jagame koodi 1111111 koodiga 1011 saame 1111111/1011=1101
Hulkliikmete jagamine tabeli kujul:
1111111 jagaja hulkliige : 1011
1011 1101
1001
1011
01011
1011
0000
(jääk)
Või nii, et jagamise tulemuseks on otsese jagamise jääk: (1111111/1011)mod g(z)=0000, kus taandava hulkliikme rollis fm(z) rollis on hulkliige g(z)
43. Hulkliikmete juured
(raamat lk.45-46 ja loeng 14(alates slaid 12))
Tekitava hulkliikme juured on ka kõikide lubatud koodsõnade hulkliikmete juurteks. Lubatud koodsõnade hulkliikmete juured kuuluvad korpusesse GF(2m). Arvesse võttes tsükkelkoodi omadust 3. On sellisteks juurteks tekitava hulkliikme gr(z) juured.
Kõik korpuse GF(2m) korrastatud elemendid on hulkliikme (zn+1) juured, kui n=2m-1.
44. Eraldamatute tsükkelkoodide koostamise algoritm . Kasutuse eelised ja puudused.
(raamat lk.38-40)
Infosümbolite asukohad lubatud koodsõnas ei ole määratlevad. Konkreetseid algsete infosümbolite väärtusi ei ole koodsõnas.
Algoritm: yn-1(z)= xk-1(z)gr(z), kus siis
yn-1(z)- on lubatud koodsõna
xk-1(z)- on infokood
gr (z) - on tekitav hulkliige.
* Tekitav hulkliige rahuldab võrrandit: g(z)h(z)=zn-1.
h(z)- on kontrollhulkliige.
*Tekitav hulkliige on taandamatu korpuses GF(2). See tähendab,et tema juurteks ehk nullkohtadeks ei ole 0 ega 1. g3(z)=z2+z+1, kui 0: g3(z=0)=02+0+1≠0 ja kui 1: g3(z=1)=12+1+1≠0.
*Tekitav hulkliige on normeeritud. S.t et tekitava hulkliikme vanima ja noorima järgu kordajad on 1-d.
*Tekitava hulkliikme kaal on mitte väiksem kui vigade parandamiseks/avastamiseks vajalik koodi minimaalne kaugus. S.t. et w(gr(z)) ≥ dmin
*Tekitavaks hulkliikmeks võib olla mingi hulkliikme (zn-1) ühiskordsetest, mis rahuldab eelpool esitatuid tingimusi -> g1(z)*g2(z)*.....*gb(z)= zn-1
45. Eraldatavate tsükkelkoodide koostamise algoritm. Kasutuse eelised ja puudused.
(raamat lk.41-42)
Infosümbolid säilitavad kodeerimise käigus oma asendi koodiplokis.
Infosümbolite asukoht on vastuvõtupoolel teada. a)Mistahes suvalise infokoodi hulkliige korrutatakse: xk-1(z)*zr
b) Nihutatud infokoodi hulkliige jagatakse tekitava hulkliikmega gr(z): xk-1(z)*zr/ gr(z)= Q(z)+Rr-1(z)
c) Saadud jääk liidetakse nihutatud koodsõnale ja saadakse lubatud koodsõna:
yn-1(z)= xk-1(z)zr + Rr-1(z)
Tsükkelkoodidel on head vigu parandavad omadused. Kui kasutada dekodeerimisel sündroomi, siis praktiliselt peaks see toimima nii,et igale konkreetsele sündroomi koodile vastab konkreetne viga. Selline dekodeerimine ei sobi mitmekordsete vigade parandamiseks.
46. Tsükkelkoodid ühekordsete vigade parandamiseks. Näide.
(raamat lk.39-42)
Tsükkelkoodid on sellised lineaarsed plokk -koodid, mis moodustavad nn. tsüklilise rühma, s.t kõik tsükliliselt ümberpaigutatud koodid on lubatud koodid.
Leiame lubatud koodsõnad eraldamatu tsükkelkoodi (7,4) jaoks, mis parandab ühekordseid vigu. Jaotame n=7=4+3. Valime tekitava hulkliikme g3(z) kui ühe hulkliikme (z7+1).
Kuna z7+1=(z+1)*(z3+z+1)*(z3+z2+1),
Siis võime tekitavaks hulkliikmeks valida ükskõik kumma parempoolses avaldises olevast kahest tegurist. Esimene tegur ei sobi , kuna tema aste ei rahulda ettearvutatud r=3 väärtust. Pealegi on hulkliige taandatav korpusesse GF(2). Valime g3(z)= z3+z+1.
47. Ühe- ja mitmekordsete vigade parandamine.
( loengumaterjal 15)
Tsükkelkoodid võivad parandada nii: juhuslikke vigu, BCH koode, RS koode, Goppa koode, ruut-resiideid koode, vigade pakette, Fire koode. Tsükkelkoodidel on head vigasid parandavad omadused. Kui kasutada kodeerimisel sündroomi (e. kontrollarvu), siis praktiliselt peaks see toimima nii,et igale konkreetsele koodile vastab konkreetne viga. Selline dekodeerimine ei sobi mitmekordsete vigade parandamiseks.
48. BCH koodi vigasid parandavad omadused.
(loengumaterjalid 15 ja 16)
Eriti tähtsa häirekindlate koodide klassi moodustavad BCH koodid, mis on mitmekordseid vigu avastavad ja parandavad hulkliikmelised koodid. Nimetatud koode võib pidada Hammingi koodide üldistuseks mitmekordsete vigade parandamiseks.
Mitmekordsete vigade parandamine on raskendatud erinevate mitmekordsete vigade suure arvu tõttu, mis välisatb otsese vigade oaranduse kontrollarvu järgi.
Kuna sümboli alsed vigasuse tõenäosused on väikesed, esinevad ühekordsed vead koodiplokkides kõige suurema tõenäosusega.
Erinevate vigade arv kasvab koodiploki pikkuse kasvades väga kiiresti. BSC koodid on lineaarsed algebralised koodid. BSC koodid koostatakse parandama vigu kuni kordsusega q. S.t.,et parandatakse kõik vead kuni kordsusega q (q kaasa arvatud), olgu q=3, siis parandatakse kõik vead kordsusega 1, kordsusega 2 ja kordsusega 3.
49. Eraldatava BCH koodi koostamine. Ja 50. Eraldamatu BCH koodi koostamine.
(raamat lk.57-60 ja loeng 16)
Primitiivsete ja mitteprimitiivsete BCH koodide koostamise reeglid on järgmised:

Valitakse sobiv koodi pikkus n=2m-1

Sõltuvalt vajadusest määratakse parandavate vigade kordsus 1.

Leitakse korpuse GF(2m) primitiivne element γ.

Leitakse korpuse GF(2m) primitiivse elemendi γ minimaalne hulkliige M(z).

Korrastatakse korpuse GF(2m) elemendid ßi ,i=[1,..,2m-1] primitiivse elemendi γ minimaalse hulkliikme M(z) abil.

Moodustatakse tekitav hulkliige gr(z):
gr(z)= VÜK [Mη(z)* Mη+1(z)*…* Mη+2I(z)]
VÜK-vähim ühiskordne
Kui tekitav hulkliige on moodustatud, võib BCH koodi koostada kas eraldamatu või eraldatava (süstemaatilise) koodina, vastavalt algoritmidele:
Eraldamatu BCH-vastavalt eraldamatu tsükkelkoodi algoritmile -> Algoritm: yn-1(z)= xk-1(z)gr(z)
Eraldatav BCH- vastavalt siis yn-1(z)= xk-1(z)zr + Rr-1(z)
51. BCH koodi dekodeerimise põhivõtted.
(raamat lk. 61-71)
*Dekodeerimiseks vajalikud võrrandid saame siis, kui on valitud vastavate omadustega tekitav hulkliige.
*Kuna vastuvõtu poolel pole teada vea reaalne kordsus ja vigaste sümbolite asukohad, siis järelikult peaks dekodeerimise käigus saama lisainfot vea reaalsest kordsusest.
*Kui BCH kood on kooostatud kuni q kordsete vigade parandamiseks, siis peab algebraliste dekodeerimisalgoritmide võimalikkuses olema tagatud q sellise võrrandi koostamise võimalus, et võrrandisüsteemi lahendamisega oleks kindlustatud q tundmatu väärtuste määramine. Need väärtused on vigaste sümbolte asukohtade numbrid .
Loetleme BCH koodi kõikide lubatud koodsõnade omadused, mis kindlustavad BCH koodide dekodeerimise:

Kõik lubatud koodsõnad jaguvad jäägita tekitava hulkliikmega gr(z).

Kõik tekitava hulkliikme gr(z) juured on ka kõikide lubatud koodsõnade juurteks

BCH koodi dekodeerimisel on võimalik moodustada sündroom (e. kontrollarv), mis koosneb I komponendist

BCH koodi dekodeerimisega on võimalik parandada ja avastada kõiki I ja vähemakordseid vigu, mis rikuvad lubatud koodsõnade omadusi 1. ja 2.
BCH koodide dekodeerimise peamisi tehteid on kaks:

Sündroomi (e.kontrollarvu) komponentide moodustamine vastavalt võrrandile n=2m-1. Selleks leitakse vastuvõetud koodsõna y*(z)=y(z)+e(z) väärtus oletatavate lubatud koodsõnade juurte ß1,ß2,ß3,ß4,… ß2I-1 kohal: C1,C2,C3 ja C4.

Vigaste sümbolite asukohtade määramine.
Vigade parandamiseks olulisimad tehted :

Kontrollarvu komponentide arvutamine

Lokaatorhulkliikme koostamine koos kordajate arvutustega

Lokaatorhulkliikme juure leidmine etteantud korrastusega laiendatud arvkorpuse elementide hulgast. Sõltuvalt lokaatorhulkliikme kujust saame siis erineva nummerdamisega vigase sümboli asukoha.

Paranduskoodi e`(z) moodustamine, mis on lihtne kahendkoodide jaoks: vigaste sümbolite kohale tuleb paigutada ühed. Teised sümbolid on nullid.
Parandus toimub vastuvõetud koodsõna ja paranduskoodi positsioonilise summeerimisega.
52. Vandermondi võrrand, selle lahendamine ja tema seos koodide dekodeerimisega.
(raamat lk.63-65- raamatus on väga hästi seletatud)
Lahendiks on lokaatorhulkliige, mille, kordajad. Kui suur, mis tüüpi. Kuulub mittelin võrrandite klassi. Esimene rida koosneb ühtedest. Vigaste sümbolite asukohad annavad C1. Hea: esimene, kolmas, viies, seitsmes aste jne. Kui õnnestuks vahele panna teine, neljas, ..., saaks lahendada. Vandermondi maatriks * tundmatu ja võtta trasp ühikmaatriks = C0. -> b0 on kõik 1-d, jne... Ruudud annavad c2-e. Laiendame. Kõikide astmete vigaste sümbolite asukohad astmega 0 annavad c0-i. Võrrandil on olemas lahendus. Lahenduseks on lokaatorhulkliige. Kordajad leitakse lineaarsest võrrandisüsteemist. Kuuluvad GF(2)
53. Lokaatorhulkliige ja tema kujud ja omadused.
(Loeng 16, slaidid 24-29)
Lokaatorhulkliige on polünoom, mille abil on võimalik BCH koodide dekodeerimisel lahendada Vandermonde´i võrrandisüsteem ja seega määrata vigaste sümbolite asukohad. Lokaatorhulkliikmed koostatakse vastavalt q suurusele (eeldatavale vigade kordsusele) ja kahel eri kujul:
1.
2.
Hulkliikemete kordajate väärtused saame leida, lahendades järgmise võrrandisüsteemi:
Leides hulkliikmete kordajate väärtused , siis määravad mõlemal juhul vigaste sümbolite asukoha ära hulkliikme juured:
Esimene lokaatorhulkliige näitab vigase sümboli asukoha alustades nummerdamist alates noorimast järgust, teine lokaatorhulkliige aga vanimast.
54, 55. Eraldatava ja eraldamatu BCH koodi dekodeerimisetapid.
(Loeng 16 , slaidid 39 – 42)

Kontrollarvu komponentide arvutamine

Lokaatorhulkliikme koostamine koos kordajate arvutustega

Lokaatorhulkliikme juurte leidmine etteantud korrastusega laiendatud arvkorpuse elementide hulgast

Paranduskoodi koostamine
Eraldatavate BCH koodide puhul on see lihtne. Paranduskood tuleb koostada lihtsalt nii, et muudetakse sümbolites kus on vead, 0-d 1-deks ja vastupidi.
Eraldamatute BCH koodide saame parandatud infosümbolid sooritades veel ühe tehte:
56. RS koodide kirjeldus. Erinevus ja samasus BCH koodidega
(Loeng 17 ,sisuliselt kõik slaidid)
RS koodide hulkliikmete kordajad on määratud korpuse GF(2m) elementidega.
GF(2m) korpuse elemendid korrastatakse mingi m- astmelise hulkliikmega (tavaliselt korpuse GF(2m) primitiivse elemendi minimaalse hulkliikmega. Järelikult on RS koodide hulkliikmete kordajad m kahendsümbolist koosnevad vektorid i , kus nummerdamine toimub järgmiste arvudega : [0,...,2m-2] .
RS koodides loetakse veakordsuseks koodsõna vigaste hulkliikmete kordajate arvu Q – vigaste plokkide arvu. Kui ploki pikkus on m , siis võivad seal vigased olla mistahes kahendsümbolid. RS koodide puhul, erinevalt kahendkoodidest, tuleb lisaks kindlaks teha ka vea suurus. RS kood parandab kõik vead kuni kordsusega Q.
Et oleks võimalik parandada kõik vead kuni kordsusega Q, siis selleks koostatakse primitiivne kood pikkusega n = 2m-1 = k+r (kus k on infoplokkide ja r liiaste plokkide arv) .. Infobittide k jaotusi võib valida erinevalt: k = [1,...,n] – saame erinevate vigasid avastavate ja parandavate omadustega RS koodid. Vastavalt k väärtusele võime kindlustada r = 2Q : saamegi koostada koodi, mis parandab kuni Q kordseid vigu (max koodikaugus on D = 2Q+1). Koodi hulkliikmete aritmeetiliste tehete teostamisel kasutatakse korpuse GF(2m) elementide korrutamise ja liitmise reegleid.
Tekitavaks hulkliikmeks kasutatakse 2Q-nda astme polünoomi (struktuur toodud järgmises punktis).
Lubatud koodsõnad infokoodi Xk-1(z) jaoks leitakse infokoodi ja 2Q-nda astme tekitava polünoomi korrutisest :
(eraldamatu koodi korral). Tsüklilise koodi eraldatava algoritmi korral nihutatakse kõigepealt infokoodi 2Q ploki võrra vanemate järkude suunas ja seejärel jagatakse läbi tulemust tekitava 2Q-nda astme hulkliikmega.
Erinevused ja samasused BCH koodidega.
RS koodid on BCH koodide alamhulk : mittebinaarsed primitiivsed BCH koodid. Mõlemad koodid suudavad parandada kuni Q kordseid vigu ja tegelikku vigade kordsust saab leida alles peale koodi vastuvõttu. Mõlemas koodis kasutakse korrastatud elemente korpusest GF(2m) –> mõlemad koodid koosnevad hulkliikmetest. Mõlemaid koode kasutatakse tavaliselt suhteliselt lühikeste koodide kodeerimiseks.
57. RS koodide tekitava hulkliikme struktuur
(Loeng 17 , slaid 18)
Näiteks kahekordseid vigu (Q=2) parandava koodi tekitav hulkliige on :
58. Simplekskoodi mõiste. Omadused.
(Loeng 18, slaidid 1-4, 9-23)
Simplekskoodide puhul on tegu koodidega, kus kus lubatud koodsõnad moodustavad simpleksi : kõikide lubatud koodsõnade yi, yj vahelised kaugused on võrdsed – dij (yi,yj) = const – just nagu simplekssignaalide korral, kus signaalide vahe on konstantne .
Omadused :
1. Saab kasutada duaalsetena Hammingi koodidele : tekitava maatriksina G kasutame kontrollmaatriksit H
2. Kasutades tekitavas maatriksis korpuse GF(2m) korrastatud elemente, saame koodi pikkuseks n = 2m-1 , kus infosümbolite arv k=m, koodikaugus D=2m-1 ja koodi liiasus U(K)=(n-k)/n *100 %
3. Simplekskoodi lubatud koodisõnade 0-de ja 1-de paigutus on suvaline. Seetõttu kutsutakse neid koodisõnu pseudojuhuslikeks jadadeks ( või ka m-jadadeks, või siis maksimaalse pikkusega jadadeks). Selle tõestuseks vaatleme poolsuletud jada :

Simplekskoodidel on hea häirekindlus.
Ülejäänud omadused (puudutavad m-jadasid) on toodud punktis 63.
59. Krüpteerimise põhialused
(Loeng 19, kõik slaidid)
Krüptograafia – 2 haru:

Krüptoloogia – salakirja koostamine

Krüptoanalüüs – salakirja taastamine algseks kirjaks
Krüptograafia tegeleb edastatavate andmete kodeerimise ja salastamisega ja salastatud andmete taastamisega originaalandmeteks. Algandmeid, mis kuuluvad krüpteerimisele, nimetatakse algtekstiks, peale krüpteerimist saame salateksti ehk krüptiteksti.
Seosed:
Andmete salastamise muutuste kogu nimetatakse krüpteerimise algoritmiks, seadet, mis seda teostab krüpteriks. Originaalsete andmete taastamine – dekrüpteerimine - on võimalik, kui on olemas üks või mitu krüpteri parameetrit ehk „võtit“. Krüptianalüüs tegeleb krüptigrammi lahtimuukimisega, kui võtit ei ole.
Krüptograafia kindlustab 3 peamist andmeedastuse teenuse eelist :

Salastatus .

Autentsus

Andmete stabiilsus – andmed ei muutu edastamise käigus, neid ei saa rikkuda või võltsida jne.
Liigitused :
60. Plokk krüpter
(loeng 20, slaidid 9-11)
Plokk krüpter on sümmeetriline krüpter. Algtekst jagatakse kindla bittide arvuga plokkideks krüpteeritakse samuti kindla pikkusega salajase võtmega. Dekrüpteerimine toimub analoogselt, kasutades sama võtit ja sama krüpteri loogikat teispidises järjekorras. Plokkide suuruseks võetakse tavaliselt mingi kindel arv – üldjuhul kas 64 bitti (vanemad süsteemid) või 128 bitti. Sama algteksti krüptimine annab alati samasuguse krüpteeritud väljundi.
Tuntuim plokk- krüpetri algoritm on DES.
Järgnev tekst on mõeldud kasutamiseks omal vastutusel ja sihtgrupina pean silmas eelkõige hardcore Urve Madari austajaid. Selle lisamisel on proua Urve Madaril teie eksamitöös seda punkti väga amüseeriv lugeda, kuna DES algoritm kirjeldab oivaliselt, kuidas üks plokk-krüpter oma tööd teeb, ja see võib selle aine lõppresultaati mõjutada positiivses suunas. Kes läheb tulevikus magistriõppesse saab siit hea näo kirja, juhul kui ta plaanib võtta selliseid ained nagu Häirekindlus või Infohankesüsteemid (soovitan soojalt, nendes on unustamatu jalgrattamatkavõimalus või väljasõiduvõimalus Ämarisse või Laekverre imetoredate radarite juurde) . Aga samas on see ka muidu selline asi, mida on alati tore ka niisama teada. Keegi mäletab veel Alice ´it Bob´i ja Trudy´t Paluoja tunnist ?
DES algoritm
Algoritmi põhistruktuur on toodud ära alumisel joonisel. F plokid tähistavad seal Feisteli funktsioone, punane ring ristiga tavalist XOR tehet. IP on algpermutatsioonide koostamine, FP lõpp-permutatsioonide oma. Antud näites jagatakse alginfo 64 bitistesse blokkidesse. Võtmena kasutatakse 64 bitist jada, millest kasutusse läheb 56 ( 8 bitti on paarsusbitid).
Fikseeritud permutasioonid muudavad algsete infobittide asukohti. Peale permutasiooni jagatakse 64 bitine kood kaheks 32 bitiseks osaks. Üks osa läbib Feisteli funktsiooniga plokki ja liidetakse XORiga teisele otsa, ning kogu asi läheb vastupidi käima (vt. joonist). Nõnda käib see 16 korda, kuni tehakse lõpus veel üks kindel permutatsioon ja saamegi krüpteeritud info.
Feisteli funktsioon.

32 bitine pool-plokk kasvatatakse 48 bitiseks, kasutades osade bittide duplikatsioone (joonisel plokk E).

56 bitisest võtmest kombineeritakse 48 bitine alamvõti.

Alamvõti ja 48 bitine info liidetakse kokku XOR tehtega , väljundiks on 48 biti pikkune tulemus.

See tulemus jagatakse 8-ks 6 biti pikkuseks osaks.

Iga kuuebitine osa läbib joonisel S-ploki ( substitution box) , kus toimub tema teisendamine 4 bitiseks. Seda saab teostada näiteks maatriksite vms. sarnase tabeli alusel.

Saame nüüd uueks tulemuseks jällegi 32 bitise jada.

Selle tulemusega teostame fikseeritud permutatsiooni, et asja veelgi rohkem turvaliseks teha. Nagu näha, seisnebki algoritmi turvalisus kõigepealt plokis E teatud bittide duplikatsioonide võrra 32 bitisest jadast 48 bitise kasvatatamises, S-plokkides toimuvast teisendusest maatriksite alusel ja lõpus toimuvast fikseeritud permutatsioonist. Sellega saab asja ajada päris sogaseks.
Alamvõtmete koostamine toimub järgmist algoritmi kasutades.
Siin