Sidesüsteemid ja võrgud (0)

Sidesüsteemid ja -võrgud
Konvolutsioonkood
Vello Vanem
Tallinna Polütehnikum
Konvolutsioonkood
Plokkkoodi korral võtab kooder vastu k
bitise sõnumiploki ja väljastab nbitise
koodisõna
Koodisõnad moodustatakse plokikaupa, st
üks plokk kodeeritakse alles pärast
eelmise ploki kodeerimise lõppemist
Kevad 2009 Tallinna Polütehnikum 2
Konvolutsioonkood
Paljudel juhtudel esinevad sõnumibitid
jadana ja mitte plokkidena
Sellistel juhtudel tuleks plokkkoodidele
eelistada konvolutsioonkoode
Konvolutsioonkooder töötleb saabuvaid
sõnumijärjestusi pidevalt
Kevad 2009 Tallinna Polütehnikum 3
Konvolutsioonkood
Konvolutsioonkoodi kahendsümbolite
kooder kiirusega 1/n bitti sümboli kohta on
vaadeldav lõpliku automaadina, mis
koosneb Mjärgulisest nihkeregistrist ette
antud ühendustega moodul2 summaato
rite kaudu ja multiplekserist, mis muundab
summaatorite väljundid järjestikkoodiks
Kevad 2009 Tallinna Polütehnikum 4
Konvolutsioonkood
L bitine sümbolijärjestus muundatakse
koodris n(L + M) bitiseks väljundkoodiks
Kooditegur on seejuures avaldatav
r = L / n(L + M) bitti sümboli kohta
Kuna tavaliselt L >> M, saame lihtsustatult
r 1 / n bitti sümboli kohta
Kevad 2009 Tallinna Polütehnikum 5
Konvolutsioonkood
Konvolutsioonkoodi seotud pikkuseks,
väljendatuna sõnumibittides, on nihete arv,
mille jooksul üks sõnumibitt mõjustab koodri
väljundit
Mjärgulise nihkeregistriga koodri mälu on
võrdne M sõnumibitiga ja vaja läheb
K = M + 1 nihet selleks, et sõnumibitt
nihkeregistrisse siseneks ja sealt ka väljuks
Seega koodri seotud pikkus on K
Kevad 2009 Tallinna Polütehnikum 6
Konvolutsioonkood
Järgneval joonisel on konvolutsioonkoodi
koodri skeem, mille korral n = 2 ja K = 3
Koodri kooditegur r = 1/2
Kooder väljastab koodi iga sisendbiti järel
Kevad 2009 Tallinna Polütehnikum 7
Konvolutsioonkoodi kooder
Summaator mod2
Trakt 1
Sisend Väljund
T T
Trakt 2
Kevad 2009 Tallinna Polütehnikum 8
Konvolutsioonkood
Toodud koodri poolt genereeritav
konvolutsioonkood ei ole süstemaatiline
kood
Erinevalt plokkkoodidest on konvolutsioon
kodeerimise korral mittesüstemaatiliste
koodide kasutamine eelistatav võrrelduna
süstemaatiliste koodidega
Kevad 2009 Tallinna Polütehnikum 9
Konvolutsioonkood
Iga trakt, mis seostab konvolutsioonkoodri
väljundi koodri sisendiga on kirjeldatav
väljundi impulssreaktsioonina
Impulssreaktsioon kirjeldab vaadeldava
trakti väljundi reaktsiooni kui trakti sisendile
antakse ühesed (1) impulsid ja kõik koodri
trigerid olid algselt seisus 0
Kevad 2009 Tallinna Polütehnikum 10
Konvolutsioonkood
Iga konvolutsioonkoodri väljundi ja sisendi
vaheline trakt on analoogselt plokk
koodidega iseloomustatav ka moodustaja
polünoomiga, mis on formeeritav
impulssreaktsiooni ühikviite teisendusena
g(D) = g0 + g1D + g2D2 + ... + gMDM,
milles D tähistab ühikviite muutujat
Kevad 2009 Tallinna Polütehnikum 11
Näide
Vaatleme eeltoodud skeemiga konvolut
sioonkoodrit, millel on kaks trakti (1 ja 2)
Trakti 1 impulssreaktsioon on (1, 1, 1)
Sellele vastav moodustajapolünoom on
g(1)(D) = 1 + D + D2
Trakti 2 impulssreaktsioon on (1, 0, 1)
Kevad 2009 Tallinna Polütehnikum 12
Näide
Traktile 2 vastav moodustajapolünoom on
g(2)(D) = 1 + D2
Valime näiteks edastamiseks sõnumikoodi
(10011) ja selle polünoomkuju on
m(D) = 1 + D3 + D4
Trakt 1 väljundi saame korrutamistehtega
c(1)(D) = g(1)(D)m(D)
Kevad 2009 Tallinna Polütehnikum 13
Näide
Tulemuseks saame
c(1)(D) = (1 + D + D2)(1 + D3 + D4)
= 1 + D + D2 + D3 + D6
Trakt 1 väljundjärjestus on seega (1111001)
Analoogiliselt leiame trakt 2 kohta
c(2)(D) = g(2)(D)m(D)
Kevad 2009 Tallinna Polütehnikum 14
Näide
Tulemuseks saame
c(2)(D) = (1 + D2)(1 + D3 + D4)
= 1 + D2 + D3 + D4 + D5 + D6
Trakt 2 väljundjärjestus on seega
(1011111)
Multipleksides kaks väljundit, saame
kodeeritud järjestuse
c = (11, 10, 11, 11, 01, 01, 11)
Kevad 2009 Tallinna Polütehnikum 15
Näide
Sõnumijärjestusest pikkusega L = 5 bitti
kodeeritakse järjestus pikkusega
n(L + K 1) = 14 bitti
Selleks, et nihkeregister kodeerimise lõpus
jääks nullisesse lähteseisu lisatakse
sõnumijärjestusele K 1 = 2 nulli
Pikkusega K 1 nullist koosnevat järjestust
sõnumijärjestuse lõpus nimetatakse sõnumi
sabaks (tail of the message)
Kevad 2009 Tallinna Polütehnikum 16
Koodipuu, võre ja olekudiagramm
Traditsiooniliselt kujutatakse konvolutsioon
koodri omadusi graafilisel kujul kasutades
selleks ühte kolmest samaväärsest
diagrammist: koodipuu, võre või oleku
diagramm
Nende diagrammide kasutamist illustree
rime eeltoodud konvolutsioonkoodri töö
kirjeldamisega
Kevad 2009 Tallinna Polütehnikum 17
Koodipuu
Konvolutsioonkoodri graafilise kujutamise
diagrammidest alustame koodipuust
Koodipuu iga haru vastab ühele sisend
sümbolile, millele vastav väljundsümbol on
kujutatud sisendsümbolile vastava haru
peal
Sisendsümboleid (0 või 1) eristatakse haru
suuna järgi hargnemiskohas: "0" vastab
ülemine haru ja "1" vastab alumine haru
Kevad 2009 Tallinna Polütehnikum 18
Koodipuu 00 00
00 a 00 a
00 a 11 11 a 11
10 10
11 b
0 11 b
01 01
00 11 10 11
10 c 10 c
11 b 00 00 b 00
01 01
01 d 01 d
00 10 11 10
00 00
11 a 11 a
10 c 11 01 c 11
10 10
00 b 00 b
01 01
11 11 01 11
01 c
1 01 c
01 d 00 10 d 00
01 01
10 d 10 d
10 10
Kevad 2009 Tallinna Polütehnikum 19
Koodipuu 00 00
00 a 00 a
00 a 11 11 a 11
10 10
11 b
0 11 b
01 01
00 11 10 11
10 c 10 c
11 b 00 00 b 00
01 01
01 d 01 d
00 10 11 10
00 00
11 a 11 a
10 c 11 01 c 11
10 10
00 b 00 b
01 01
11 11 01 11
01 c
1 01 c
01 d 00 10 d 00
01 01
10 d 10 d
10 10
Kevad 2009 Tallinna Polütehnikum 20
Koodipuu
Liikumissuund koodipuus on vasakult
paremale vastavuses sisendsümbolite
järjestusele
Sisendbittide järjestusele vastava kodeeri
tud väljundsümboli saame vastavate
harude pealt
Näiteks sisendsümboli (10011) korral
saame kodeeritud sümboliks (11, 10, 11,
11, 01)
Kevad 2009 Tallinna Polütehnikum 21
Näide 10011 kodeerimine 00
00 a
11 a 11
10
0 11 b
01
10 11
10 c
00 b 00
01
01 d
00 11 10
00 00
11 a 10 11 a
10 c 11 01 c 11
10 01 10
00 b 00 b
01 01
11 11 01 11
01 c
1 01 c
01 d 00 10 d 00
01 01
10 d 10 d
10 10
Kevad 2009 Tallinna Polütehnikum 22
Koodipuu
Koodipuu diagrammilt nähtub, et puu harud
hakkavad korduma pärast kolme hargnemist
Sarnaste sümbolitega (a, b, c, d) tähistatud
sõlmed on sarnased
Seetõttu saame koodipuu kokku suruda
teisele kujule, mida nimetame võreks
Nimetus tuleneb sellest, et uus kuju on
puukujulise struktuuriga võre
Kevad 2009 Tallinna Polütehnikum 23
Võre
a 00 00 00 00 00 00 00 00
11 11 11 11 11 11
b 11 11 11 11 11 11
00 00 00 00
10 10
10 10 10
c
01 01 01 01 01
01 01 01 01 01
d 10 10 10 10
Tase j=0 1 2 3 4 5 L-1 L L+1 L+2
Kevad 2009 Tallinna Polütehnikum 24
Võre
Sisendsümbolid 0 ja 1 tähistatakse võre
kuju korral selliselt, et sisendsümbolile 0
vastav haru on märgitud pideva joonena ja
sisendsümbolile 1 vastav haru on märgitud
katkendliku (punktiir) joonena
Nagu koodipuu korral vastab ka võre korral
igale sisendjärjestusele konkreetne tee läbi
võre
Kevad 2009 Tallinna Polütehnikum 25
Võre
a 00 00 00 00 00 00 00 00
11 11 11 11 11 11
b 11 11 11 11 11 11
00 00 00 00
10 10
10 10 10
c
01 01 01 01 01
01 01 01 01 01
d 10 10 10 10
Tase j=0 1 2 3 4 5 L-1 L L+1 L+2
Sisendjärjestus 10011, väljundkood 11, 10, 11, 11, 01
Kevad 2009 Tallinna Polütehnikum 26
Võre
Võre on märgatavalt ülevaatlikum koodi
puust kuna toob selgemalt välja asjaolu, et
konvolutsioonkooder on vaadeldav lõpliku
automaadina
Konvolutsioonkoodri olek määratakse ära
koodri nihkeregistris olevate sõnumi
bittidega
Kahejärguline nihkeregister võimaldab
koodri neli (4) olekut (vt tabel)
Kevad 2009 Tallinna Polütehnikum 27
Konvolutsioonkoodri olekute tabel
Olek Kahendarv
a 00
b 10
c 01
d 11
Kevad 2009 Tallinna Polütehnikum 28
Olekudiagramm
Vaatleme võre tasemeid j ja j + 1,
kusjuures j 2, konvolutsioonkooder saab
olla olekutes a, b, c või d
Vasakpoolses veerus on toodud
konvolutsioonkoodri olekud tasemel j ja
parempoolses veerus tasemel j + 1
Kevad 2009 Tallinna Polütehnikum 29
Olekudiagramm
00 10
a a
11 11 d
b b 01 01
10
00
b c
10 00
c c 11
11
01 01 a
10
d d
00
Kevad 2009 Tallinna Polütehnikum 30
Olekudiagramm
Ühildades toodud veerud üheks, saamegi
konvolutsioonkoodri olekudiagrammi
Selle sõlmed määravad ära koodri neli
võimalikku olekut ning iga sõlm on seotud
kahe siseneva haruga ja kahe väljuva
haruga
Kevad 2009 Tallinna Polütehnikum 31
Olekudiagramm
Üleminekud ühest olekust teise sisend
sümboli 0 mõjul on märgitud pideva
joonega ja sisendsümboli 1 mõjul
katkendliku (punktiir) joonega
Iga haru juurde märgitud kood märgib
sellele üleminekule vastavat koodri
väljundkoodi
Kevad 2009 Tallinna Polütehnikum 32
Viterbi algoritm
Sümmeetrilise kahendkanali korral taan
dub maksimaalse tõepärsuse dekooder
minimaalse distantsi dekoodriks
Sellises dekoodris võrreldakse vastu
võetud vektorit r iga võimaliku edastatud
vektoriga c ja lähim neist valitakse
korrektselt vastuvõetud vektoriks
Kevad 2009 Tallinna Polütehnikum 33
Viterbi algoritm
Minimaalse distantsi dekooderis me
dekodeerime konvolutsioonkoodi valides
koodipuul tee (trakti), mille korral
kodeeritud järjestus erineb vastuvõetud
järjestusest kõige vähem
Koodipuu saame asendada koodi
esitusega võrena, kusjuures eeliseks on
asjaolu, et sisendjärjestuse suurenedes
võre sõlmede (olekute) hulk ei suurene
Kevad 2009 Tallinna Polütehnikum 34
Viterbi algoritm
Võre graafiliselt kujutiselt teame, et võre
iga sõlme võimalike sisendite arv on 2
Need kaks sisendit on samaväärsed
Minimaalse distantsi dekooder peab
langetama otsuse, milline neist kahest
sisendist alles jätta ilma toimimiskaota
Selliste otsustuste jada on see, mida
Viterbi algoritm teel mööda võre teeb
Kevad 2009 Tallinna Polütehnikum 35
Viterbi algoritm
Algoritm toimib arvutades erinevuste
suuruse (kaalu) iga võimaliku tee kohta
mööda võret
Konkreetse tee kaal on sellele vastava
kodeeritud järjestuse ja vastuvõetud
järjestuse Hammingi vahemaa
Iga võre sõlme (oleku) kohta algoritm
võrdleb kahte sisenevat teed
Kevad 2009 Tallinna Polütehnikum 36
Viterbi algoritm
Alles jäetakse väiksema erinevusega
(kaaluga) tee ja suurema erinevusega tee
jäetakse kõrvale
Seda arvutust tehakse võre iga taseme
(ajahetke) j kohta vahemikus M j L,
milles M on koodri mälu ja L on
sõnumibittide arv
Kevad 2009 Tallinna Polütehnikum 37
Viterbi algoritm. Näide
0 01 1 = 00 01
1 = 11 01
Tase j = 1
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 38
Viterbi algoritm. Näide
01 1 00
0 1
1
3
2
Tase j=2
2
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 39
Viterbi algoritm. Näide
01 1 00
0 1
11
1
3
10
2
01
Tase j=2
2
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 40
Viterbi algoritm. Näide
01 1 00
0 1
1
3
2
Tase j=2 2
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 41
Viterbi algoritm. Näide
01 1 00 1 01 01 1 00 1 01
0 2 0 2
3 3
1 3 1 3
2 2
3 3
2 5 2 5
2 2
2 3 2 3
Tase j=3 4 4
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 42
Viterbi algoritm. Näide
01 1 00 1 01 01 1 00 1 01
0 2 0 2
3
1 3 1 3
2 2
3
2 5 2
2
2
2 3 2
3
4
Tase j=3
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 43
Viterbi algoritm. Näide
01 1 00 1 01 2 00 2 0 01 1 00 1 01 2 00 2
0
4 4
1 3 2 4 1 3 2 4
2 2
2 3 2 3
4 4
Tase j=4 2 3 3 2 3 3
4 4
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 44
Viterbi algoritm. Näide
01 1 00 1 01 2 00 2 0 01 1 00 1 01 2 00 2
0
4
1 3 2 4 1 3 2 2
2
2 3 2 3
4
Tase j=4 2 3 3 2 3 3
4
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 45
Viterbi algoritm. Näide
0 01 1 00 1 01 2 00 2 00 2
5
1 2 2 4
3
2 3 3
4
Tase j=5 2 3 3
4
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 46
Viterbi algoritm. Näide
0 01 1 00 1 01 2 00 2 00 2
5
1 2 2 4
3
2 3 3
4
Tase j=5 2 3 3
4
Vastuvõetud bitijärjestus on 0100010000....
Kevad 2009 Tallinna Polütehnikum 47
Viterbi algoritm. Näide
0 01 1 00 1 01 2 00 2 00 2
1 2 2
3
2 3 3
Tase j=5 2 3 3
Vastuvõetud bitijärjestus on 0100010000....
Dekodeeritud kood on 00000....
Kevad 2009 Tallinna Polütehnikum 48
Lõplik automaat
Terminiga lõplik automaat tähistatakse
mudeleid, mida iseloomustavad järgmised
iseärasused:
mudeli sisendile antakse igal diskreetsel
ajamomendil t1, t2, ..., tj sisendsuurused x1, x2, ...
xm, mis on sisendtähestiku X sümbolid ehk
fikseeritud arv sisendtähestiku lõplikke väärtusi
Kevad 2009 Tallinna Polütehnikum 49
Lõplik automaat
mudeli väljundil saab olla n väljundsuurust y1,
y2, ... yn, mis on väljundtähestiku Y sümbolid
ehk fikseeritud arv väljundtähestiku lõplikke
väärtusi
igal ajamomendil saab mudel olla ainult ühes
võimalikest olekutest z1, z2, ... zN
mudeli oleku mingil ajamomendil määravad ära
selle ajamomendi sisendsuurus x ja eelmise
ajamomendi olek z
Kevad 2009 Tallinna Polütehnikum 50
Lõplik automaat
mudeli teisendab sisendsümboli x väljund
sümboliks y sõltuvalt mudeli olekust eelmisel
ajamomendil
automaate, mille väljundsümbol y määratakse
üheselt vaid sisendsümboliga x, nimetame
mäluta automaatideks
Kevad 2009 Tallinna Polütehnikum 51
Lõplik automaat
automaate, mille väljundsümbol y sõltub lisaks
sisendsümbolile x veel ka mudeli olekust z,
mis on määratud eelmiste ajamomentide
sisendsümbolitega, nimetame lõpliku mäluga
automaatideks
Kevad 2009 Tallinna Polütehnikum 52