VIRHEENKORJAUS JA -ILMAISU
Kanavakoodaus
TIETOLIIKENNE- LABORATORIO
B. Sklar, Digital Communications
LABORATORIO
Shannon–Hartleyn-laki
• Otsikon lain mukaan ideaalisen (analogisen) kanavan kapasiteetti (kohina valkoista Gaussin kohinaa) on
– missä B on kaistanleveys ja S/N on signaali-kohinasuhde
• Siirtojärjestelmän perusresurssit ovat tämän mukaan lähetysteho (määrää signaali-kohinasuhteen) ja kaistanleveys
– suorituskykyä mitataan virhetodennäköisyyden avulla – käytännössä suorituskykyä ei saada täysin ideaaliseksi
• järjestelmän monimutkaisuus asettaa rajoituksia
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
= +
log 1
2S bit/s
C B
N
S = E
bR
b= teho N = N
0B
3 (135)
TIETOLIIKENNE- LABORATORIO
Tiedonsiirron perusresurssit
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
LÄHETYSTEHO
MONIMUTKAISUUS
KAISTANLEVEYS
VIRHETODENNÄKÖISYYS
4 (135)
LABORATORIO
Tiedonsiirron perusresurssit
• Perusresursseja pyritään käyttämään säästeliäästi
• Siirtojärjestelmät jaetaan tehorajoitettuihin ja kaistarajoitettuihin
– tehorajoitetuissa järjestelmissä lähetystehoa on niukasti mutta kaistanleveyttä runsaasti
• esim. avaruustietoliikennejärjestelmät
– kaistarajoitetuissa järjestelmissä tilanne on päinvastainen
• esim. analoginen puhelinkanava
• Perusresursseja pyritään säästämään erilaisilla modulaatio- ja koodausmenetelmillä
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
5 (135)
TIETOLIIKENNE- LABORATORIO
Tiedonsiirron perusresurssit
KOODAUS
MODULOINTI KANAVA DEKOODAUS
DEMODULOINTI
Monimutkaisuus
Lähetysteho
Kaistanleveys
Signaali-kohinasuhde
Virhetodennäköisyys Monimutkaisuus
LABORATORIO
Tiedonsiirron perusresurssit
• Tavoitteet ovat ristiriitaiset
– esim. lähetystehon pienentäminen pienentää lähettimen tehonkulutusta ja kokoa, mutta
• virhetodennäköisyys kasvaa ellei kaistanleveyttä tai käytetyn koodaus- tai modulointimenetelmän monimutkaisuutta lisätä
• Jotkut järjestelmät ovat sekä kaista- että tehorajoitettuja
• Tällöin järjestelmän suunnittelussa on oltava erityisen huolellinen
– käytettävä koodaus- ja modulaatiomenetelmät on yhdistettävä
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
7 (135)
TIETOLIIKENNE- LABORATORIO
Erilaisia koodausjärjestelmiä
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009 KANAVAKOODAUSMENETELMÄT
FEC-MENETELMÄT ARQ-MENETELMÄT
8 (135)
LABORATORIO
Erilaisia koodausjärjestelmiä
• FEC (forward error correction)
– virheen ilmaisu ja korjaus dekooderissa – ei tarvita paluukanavaa,
• reaaliaikainen toiminta
– käytössä tehorajoitetuissa järjestelmissä
• ARQ (automatic repeat request)
– virheen ilmaisu ja virheellisen lohkon toistopyyntö – vaatii paluukanavan
• toiminta ei reaaliaikainen
– sekä teho- että kaistarajoitettuihin järjestelmiin soveltuva menetelmä
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
9 (135)
TIETOLIIKENNE- LABORATORIO
Erilaisia koodausjärjestelmiä
KOODERI KANAVA FEC ⊕ ⊕ ⊕ ⊕
Virheenkorjaus
ARQ KANAVA
KOODERI
PALUU-
KANAVA
NAK = negative acknowledgement ACK= positive acknowledgementLABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Kanavakoodien jako
KANAVAKOODIT
LOHKOKOODIT KONVOLUUTIOKOODIT
11 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Kanavakoodaus
• Kanavakoodauksessa signaaliin lisätään sellaista systemaattista redundanssia (ns. ylimäärää), että sitä voidaan käyttää tehokkaasti virheen ilmaisuun ja korjaukseen dekooderissa
• Redundanssi lisätään pariteettibittien avulla
• esimerkkinä viitenumeron ja tilinumeron tarkisteen laskeminen
• Nämä pariteettibitit lasketaan informaatiobiteistä erityisillä kanavakoodausalgoritmeilla
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
koodaus
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
koodaus
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
koodaus
(mod-2-summa)
LOHKOKOODI
12 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Merkinnät
• Redundanssi tuo signaaliin tietynlaisen muistiominaisuuden
• Jos kanavassa syntyy bittivirhe tai -virheitä, muistia hyväksikäyttäen virhe voidaan ilmaista ja mahdollisesti korjata
• Merkinnät:
– n = lohkon pituus (koodisanan tai koodin pituus)
– k = informaatiobittien lukumäärä (informaatiosanan pituus) – n – k = pariteettibittien lukumäärä
– R c = k/n = koodisuhde (koodinopeus)
• informaatiobittien suhteellinen osuus kaikista biteistä
13 (135)
TIETOLIIKENNE- LABORATORIO
Lohko- ja konvoluutiokoodien ero
• Jos pariteettibitit lasketaan vain samaan lohkoon sisältyvien informaatiobittien avulla, kysymyksessä on lohkokoodi
• Jos pariteettibitteihin vaikuttavat myös aikaisempien lohkojen informaatiobitit, kysymyksessä on
konvoluutiokoodi
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
k informaatio- bittiä
(n–k) pariteetti- bittiä n bitin koodilohko
koodaus (mod-2-summa)
KONVOLUUTIOKOODI
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Perusteita
• Erilaisia koodisanoja on siis 2 n kpl – kooderi käyttää niistä vain 2
kkpl – n > k
• Kanavassa koodisanaan saattaa tulla virheitä
– vastaanotettu koodisana voi olla mikä tahansa 2
n:stä koodisanasta
• Dekoodaus tapahtuu kahdessa vaiheessa – virheellinen lohko täytyy ensin ilmaista
– sen jälkeen virheen (virheiden) paikka täytyy määrittää
• virhe korjataan invertoimalla virheellinen bitti
15 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Perusteita
• Virheen korjaaminen (virheen paikallistaminen) on paljon monimutkaisempaa kuin virheen ilmaisu
• ARQ-järjestelmässä virhettä ei korjata
– virheellinen lohko pyydetään lähettämään uudestaan
• Virheen ilmaisu perustuu siihen, että dekooderi laskee pariteettibitit uudestaan ja vertaa niitä vastaanotettuihin pariteettibitteihin
k n
–k
vertailu
virheen ilmaisu
virheen
korjaus +
MOD-2 (XOR)
16 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Perusteita
• Merkintä (n,k)-koodi tarkoittaa kanavakoodia, jonka lohkonpituus on n ja informaatiobittien lukumäärä k
• Samaa merkintää käytetään sekä lohko- että konvoluutiokoodeille
• Jos lähteen nopeus on R s bit/s, niin kooderin lähdössä nopeus on
– jossa R c = k/n on koodisuhde
bit/s
c s
s
R
R R k n ⋅ =
17 (135)
TIETOLIIKENNE- LABORATORIO
Perusteita
• Koska n/k > 1, bittinopeus kasvaa kanavakooderissa – johtuu redundanssin lisäämisestä
• Samalla yhden bitin energia pienenee
– pidetään koodisanan energiaa samana
• Kanavassa siis syntyy enemmän virheitä kuin koodaamattomassa järjestelmässä
• Koodinkorjauskyvyn ansiosta kuitenkin dekooderin lähdössä tilanne on enemmän kuin kompensoitu
c b
b
R
n k
c
= ε ⋅ = ε ⋅
ε
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Perusteita
• Dekooderin tulossa virhesuhteen (virheellisten bittien osuus kaikista biteistä) on yleensä oltava , muuten dekooderi ei toimi asianmukaisesti
• Monimutkaisia koodeja käytettäessä virhesuhde 0,1 – 0,2 voidaan vielä hyväksyä
• Rajan yläpuolella dekooderi ei vastaanota riittävästi oikeita bittejä ja dekooderi itse asiassa alkaa lisätä virheitä (kynnysilmiö)
dekooderi
102
) (e ≤ −
P P(e)<<10−2
(joskus 0,1 - 0,2 voidaan hyväksyä)
10
−2≤
19 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Perusteita
• Kanavakoodauksessa siis signaalin kaistanleveys
kasvaa (jos informaationopeus halutaan säilyttää), mutta virhesuhde paranee
• Samalla lähetysteholla päästään pienempään virhesuhteeseen kaistanleveyden kustannuksella
20 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Shannonin raja
• Kirjassa Sklar, Digital Communications, Fundamentals and Applications, Second Edition (s. 528) on osoitettu, että jatkuvan kanavan kapasiteetti on positiivinen (C > 0), kun signaali-kohinasuhde bittiä kohti on
• Tätä alarajaa sanotaan Shannonin rajaksi, jota ei voida millään koodaus- tai modulaatiomenetelmällä alittaa
• Raja on johdettu kvantisoimattomalle pehmeälle päätöksenteolle
• Kovan päätöksenteon raja on 2 dB suurempi dB
6 , ˆ 1 log
1
2 0
b
> = −
e N
E
21 (135)
TIETOLIIKENNE- LABORATORIO
Shannonin raja
koodaamaton antipodaalinen järjestelmä (esim. binäärinen PSK)
0 2 4 6 8 10
10-6 10-4 10-2 10-1
–2 P(e)
raja P(e) = 1/2 koodattu järjestelmä
=
0
erfc b
2 ) 1
( N
e E P
koodausvahvistus kovan päätöksenteon raja (+0,4 dB)
Shannonin raja (–1,6 dB)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Koodausvahvistus
• Koodausvahvistus tarkoittaa koodauksella saavutettua etua signaali-kohinasuhteessa
– Koodausvahvistus riippuu virhetodennäköisyydestä (ja tietysti koodista)
• Esim. edellä olevassa tilanteessa on teoriassa mahdollista saavuttaa koodausvahvistus 11,2 dB (kun P(e) = 10 -5 ) kvantisoimatonta pehmeää päätöksentekoa käytettäessä
• Kovaa päätöksentekoa käytettäessä menetetään
koodausvahvistuksesta 2 dB ja kolmen bitin kvantisoinnissa (Q = 8) 0,25 dB
• Huom. koodausvahvistus tulee kaistanleveyden kustannuksella
23 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodit
• Koodien toiminta perustuu modulo-2-aritmetiikkaan
• Lineaarisessa kooderissa käytetään vain mod-2-summaimia eli XOR-piirejä (exclusive or = ehdoton tai)
k n – k
n
mod-2
+ 0 1 0 0 1 1 1 0
· 0 1
0 0 0
1 0 1
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
24 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodit
• Esim. (n,n–1)-koodi
– informaatiosana 0110011 – koodisana 0110011 – informaatiosana 0000111 – koodisana 0000111
pariteettibitti (parillinen pariteetti)
1 0
25 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodit
• Koodi on systemaattinen, jos informaatiobitit sisältyvät sellaisenaan koodisanaan
• Koodi on lineaarinen, jos pariteettibitit lasketaan informaatiobittien lineaarisena kombinaationa
– modulo-2-summana
• Lineaarisessa koodissa saa käyttää vain XOR- operaatioita
– ei esim. AND-operaatioita
• Merk. u = [u 1 , u 2 , … , u k ] informaatiosana
x = [x 1 , x 2 , … , x n ] koodisana
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodit
• Esim. Toistokoodi (n = 3)
• Esim. (3,2)-koodi
u
1x
3x
2x
10 ↔ ↔ ↔ ↔ 000 1 ↔ ↔ ↔ ↔ 111
u
2x
3x
2x
100 ↔ ↔ ↔ ↔ 000 01 ↔ ↔ ↔ ↔ 011 10 ↔ ↔ ↔ ↔ 101 11 ↔ ↔ ↔ ↔ 110 u
1⊕
⊕
⊕
⊕
u
1u
2x
1x
2x
3(3,1)-koodi
1 0
1 1 0
27 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodit
• Esim. Hamming-koodi ((7,4)-koodi)
• Koska koodit ovat systemaattisia, tarvitsee laskea vain n – k pariteettibittiä
u
1x
2x
4x
3u
2u
4x
7x
6x
5u
3⊕⊕
⊕⊕
x
1⊕⊕
⊕⊕
⊕⊕
⊕⊕
28 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin generoijamatriisi
• Generoijamatriisi (generoiva matriisi) määrittelee kooderin rakenteen
• Esim. (7,4)-Hamming-koodi
u
1x
2x
4x
3u
2u
4x
7x
6x
5u
3⊕⊕⊕
⊕
x
1⊕⊕
⊕⊕
⊕⊕
⊕⊕
=
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1 G
x
1x
2x
3x
4x
5x
6x
7u
1u
2u
3u
429 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodin generoijamatriisi
• Koodisana x lasketaan informaatiosanasta u seuraavasti:
x = uG
• Jos u = (1100), niin
( )
( )
( )
( )
7 4 4
1
0 1 0 0 0 1 1
1 1 1 0 0 1 0
1 0 1 0 0 0 1
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1 0 0 1 1
×
×
=
+
=
x =
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
(7,4)-Hamming-koodi
Informaatiosanat Koodisanat
Onko koodi systemaattinen?
On se
31 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin generoijamatriisi
• Koodisana saadaan siis laskemalla yhteen generoijamatriisin ne rivit, jotka vastaavat informaatiosanan ykkösiä
• Systemaattisen koodin generoijamatriisi on muotoa G = [ I k | P ]
– jossa I
kon yksikkömatriisi (k x k-matriisi) P on k x (n – k)-matriisi (pariteettimatriisi)
32 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lineaarisen lohkokoodin ominaisuuksia
1. Jokainen koodisana on generoijamatriisin tiettyjen rivien summa
2. Lohkokoodin koodisanat saadaan selville laskemalla kaikki mahdolliset generoijamatriisin rivien summat 3. Kahden koodisanan summa on koodisana
(superpositioperiaate)
4. Nollasana on aina koodisana
• Nimitys lineaarinen koodi tarkoittaa sitä, että kaikki koodisanat voidaan laskea generoijamatriisin rivien lineaarisena kombinaationa
33 (135)
TIETOLIIKENNE- LABORATORIO
Käsitteitä
• Hamming-paino = koodisanan sisältämien ykkösten lukumäärä
x = (00010001011) Hamming-paino = 4
• Hamming-etäisyys = kahden koodisanan välinen ero = kahden koodisanan summan Hamming-paino
x 1 = (00010001011) x 2 = (00100010110)
x 1 + x 2 =(00110011101) Hamming-etäisyys = 6
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Käsitteitä
– koodisanat poikkeavat toisistaan kuudessa bittipaikassa
• merk. d 12 = 6
• huom. 0 ≤ d ij ≤ n
• Minimietäisyys = koodin koodisanojen välisistä Hamming-etäisyyksistä pienin
– merk. d min
– lineaarisen lohkokoodin minimietäisyys on sama kuin minimietäisyys nollasanasta ts. nollasanaa lähimpänä olevan koodisanan Hamming-paino
35 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Käsitteitä
• Esim. (7,4)-Hamming-koodi
koodisana
7 1
1 1 1 1 1 1
4 0
0 1 0 1 1 1
4 1
0 0 1 0 1 1
3 0
1 0 0 0 1 1
3 0
0 0 1 1 0 1
4 1
1 0 0 1 0 1
4 0
1 1 1 0 0 1
3 1
0 1 0 0 0 1
4 0
1 0 1 1 1 0
3 1
0 0 0 1 1 0
3 0
0 1 1 0 1 0
4 1
1 1 0 0 1 0
4 1
0 1 1 1 0 0
3 0
1 1 0 1 0 0
3 1
1 0 1 0 0 0
0 0
0 0 0 0 0 0
Hamming-paino
36 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Käsitteitä
– painojakauma
– taulukosta nähdään, että koodin minimietäisyys on d min = 3
• Huom. Lineaarisen lohkokoodin painojakauma on samalla etäisyysjakauma mistä tahansa koodisanasta
paino koodisanojen lkm.
0 1
3 7
4 7
7 1
37 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Kova päätöksenteko, kanavamalli
+
e y
x x = lähetetty koodisana
y = vastaanotettu sana e = virhesana
y = x + e
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Virheen ilmaisu
– verrataan vastaanotettuja pariteettibittejä (n – k kpl) dekooderissa laskettuihin pariteettibitteihin
– virhe on tapahtunut, jos yksikin vastaanotettu pariteettibitti on erilainen kuin informaatiobiteistä dekooderissa laskettu
k 010
011
001 +
=
mod-2-summa
oiresana (syndrome)
mod-2
s = n y =
39 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Jos oiresana s = 0, niin virhe on tapahtunut
• Oiresana voidaan laskea pariteetintarkistusmatriisin H avulla:
– jossa matriisi H T on matriisin H transpoosi
s = y H T
1
x(n–k) 1
xn n
x(n–k)
(n-k)xn nx(n-k)
40 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Esim. (7,4)-Hamming-koodi. Oiresanan s = (s 1 , s 2 , s 3 ) bitit saadaan seuraavasti: y = (y 1 , y 2 , … , y 7 )
kooderi
x 5 = u 1 + u 2 + u 3 x 6 = u 2 + u 3 + u 4 x 7 = u 1 + u 2 + u 4
dekooderi
s 1 = (y 1 + y 2 + y 3 ) + y 5 s 2 = (y 2 + y 3 + y 4 ) + y 6 s 3 = (y 1 + y 2 + y 4 ) + y 7
=
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1 G
x
1x
2x
3x
4x
5x
6x
7u
1u
2u
3u
4 (n-k)xn( T n k )
1 0 0 1 0 1 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
=
−
= P I
H
y1 y2 y3 y4 y5 y6 y7 s1 s2 s3 kxn
lasketaan pariteetti- bitit uudestaan
verrataan vastaanotettuihin vastaaviin bitteihin
41 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodin virheen ilmaisu- ja korjauskyky
( )
( 1 2 3 5 2 3 4 6 1 2 4 7 )
) ( 7 1
6 5 4 3 2 1
1 0 0
0 1 0
0 0 1
1 1 0
0 1 1
1 1 1
1 0 1
y y y y y y y y y y y y
y y y y y y y
k n n n
+ + + +
+ + +
+ +
=
=
−
×
s
×s = y H T
1
x(n–k) 1
xn n
x(n–k)
, ,
) , , ( s 1 s 2 s 3
=
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Esim.
• Tulos on voimassa yleisesti: GH T = 0 G = (I k P) H = (P T I n–k ) x = uG s = yH T
0
GH =
=
×
×
3 7 7
4 T
1 0 0
0 1 0
0 0 1
1 1 0
0 1 1
1 1 1
1 0 1
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1
pariteetintarkistusmatriisi
"pariteettimatriisi"
4x3
43 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Ominaisuus:
– oiresana s = yH T on nollasana, jos ja vain jos y on koodisana
• Ominaisuus:
– dekooderi voi ilmaista kaikki virhesanat e, jotka eivät ole koodisanoja
• s = yH T = (x + e)H T = xH T + eH T = eH T
• jos e on koodisana, niin oiresana on nollasana
44 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Teoreema
– jos lineaarisen lohkokoodin minimietäisyys on d min , niin koodi voi ilmaista kaikki virhesanat, joiden paino on enintään d min –1
d
mind
min–1
x y x
45 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodin virheen ilmaisu- ja korjauskyky
• s = yH T = (x + e)H T = xH T + eH T = eH T
• Erilaisia oiresanoja on 2 n–k kpl
• Erilaisia vastaanotettuja sanoja on 2 n kpl
• Jokaista oiresanaa kohti on siis 2 k kpl vastaanotettua sanaa
• Selitys:
– virhesanaan e voi lisätä minkä tahansa koodisanan x (2
kkpl) eikä oiresana silti muutu
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Teoreema 10.2
– jos lineaarisen lohkokoodin minimietäisyys on d min , niin koodi voi korjata kaikki virhesanat, joiden paino on enintään t = [(d min –1)/2],
• [ ] tarkoittaa tässä kokonaislukuosaa
– koodia sanotaan tällöin t virhettä korjaavaksi koodiksi
d
mind
min
−
− =
= 2
1 2
1
minmin
d
t d
−
=
−
= 2
1 1 2
min
min
d
t d
47 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin virheen ilmaisu- ja korjauskyky
• Koodinsuunnittelun tavoite on käyttää redundanssia mahdollisimman suuren minimietäisyyden
saavuttamiseksi
d
mind
min–1 (ilmaisu)
[(d
min–1)/2]
(korjaus)
1 0 0
2 1 0
3 2 1
4 3 1
5 4 2
6 5 2
7 6 3
48 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin taulukkohakudekoodaus
• Esim. (7,4)-Hamming-koodi
oiresana virhesana 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0
1 0 0
0 1 0
0 0 1
1 1 0
0 1 1
1 1 1
1 0 1
H
T=
49 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodin taulukkohakudekoodaus
– jos y = (1101010), niin
– dekoodaustaulukosta ê = (0001000) – korjattu sana on = y + ê = (1100010)
( ) ( 011 )
1 0 0
0 1 0
0 0 1
1 1 0
0 1 1
1 1 1
1 0 1
1101010
T =
=
= yH s
x ˆ
korjaus
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lohkokoodin taulukkohakudekoodaus
– koska taulukkohakudekoodaus on monimutkainen, (jos n – k on suuri) käytetään käytännössä erilaisia
dekoodausalgoritmeja
– dekoodaus saadaan yksinkertaiseksi valitsemalla koodi sopivasta koodiperheestä
51 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Koodiperheiden kehitys
52 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Hamming-koodit
• s = yH T = (x + e)H T = eH T
• Oiresanaan lasketaan mukaan ne H:n sarakkeet (H T :n rivit), joita vastaava virhesanan bitti on ykkönen
• Etsitään sellaista matriisia H (eli samalla matriisia G), joka korjaa yhden virheen
• Huom. H:n sarakkeet ovat itse asiassa oiresanoja
• Jos jokin H:n sarakkeista olisi nollasana, virhettä tuossa paikassa ei voitaisi ilmaista
• Jos taas kaksi H:n saraketta olisi samanlaisia, virhettä jommassakummassa näistä paikoista ei voitaisi korjata, koska oiresanat olisivat samoja
53 (135)
TIETOLIIKENNE- LABORATORIO
Hamming-koodit
• Johtopäätös:
– lohkokoodi voi korjata yhden virheen, jos ja vain jos H:n sarakkeet ovat kaikki erilaisia eikä yksikään ole nollasana
• Hamming-koodit ovat koodeja, joilla H:n sarakkeet (n kpl) muodostavat kaikki mahdolliset (n – k):n bitin sekvenssit paitsi nollasekvenssin
• H on (n–k) x n-matriisi, joten Hamming-koodilla n = 2 n–k – 1
• Merkitään m = n – k
• Hamming-koodit ovat siis (2 m –1,2 m –1– m)-koodeja
m = 2,3,…
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Hamming-koodit
m (n,k) r c = k/n
1 (1,0) 0
2 (3,1) 0,333
3 (7,4) 0,571
4 (15,11) 0,733
5 (31,26) 0,839
6 (63,57) 0,905
ei koodi
koodisuhde kasvaa
55 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Hamming-koodit
• Esim. (15,11)-koodin pariteetintarkistusmatriisi
– jos virhesana on e = (001000000000000), oiresanaksi tulee s = eH T = (0011)
• oiresana ilmoittaa tässä tapauksessa suoraan binäärisessä muodossa virheellisen bitin paikan
– dekoodaus on suoraviivaista
15
1
40 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
×
H =
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
56 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Hamming-koodit
– koodi ei ole kuitenkaan systemaattinen
– systemaattinen muoto saadaan yksinkertaisesti järjestelemällä sarakkeet uudelleen
– koska Hamming-koodi korjaa yhden virheen, sen minimietäisyyden täytyy olla d min = 3
=
1 0 0 0 1 0 1 0 1 0 1 1 0 1 1
0 1 0 0 1 1 0 0 1 1 0 1 1 0 1
0 0 1 0 1 1 1 1 0 0 0 1 1 1 0
0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 H
3 5 6 7 9 10 11 12 13 14 15 8 4 2 1
57 (135)
TIETOLIIKENNE- LABORATORIO
Lohkokoodeja
Hamming-koodi
Maksimipituuskoodi simplex-koodi
Laajennettu maksimipituuskoodi ortogonaalinen koodi
Reed–Müller-koodi (r = 1) biortogonaalinen koodi duaalikoodi
lisää pariteettibitti
lisää vastakkaiset koodisanat
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Lineaarinen lohkokoodi on syklinen, jos ja vain jos minkä tahansa koodisanan syklisesti siirretty versio on myös koodisana
• Syklisten koodien ominaisuuksia:
– koodaus ja dekoodaus suhteellisen yksinkertaista
• takaisinkytketyt siirtorekisterit käytössä
– matemaattinen käsittely polynomialgebraa käyttäen
59 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Esim. (7,4)-Hamming-koodi on syklinen
0001011 → 1000101 → 1100010 → 0110001 0010110 ← 0101100 ← 1011000
0011101 → 1001110 → 0100111 → 1010011 0111010 ← 1110100 ← 1101001
1111111 0000000
60 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Koodisana x = (x n–1 , x n–2 , … , x 0 ) esitetään koodipolynomin
x(D) = x n–1 D n–1 + x n–2 D n–2 + ··· + x 1 D + x 0 avulla
• Kertoimet x n–1 , x n–2 , … , x 0 ovat binäärisiä – nollia ja ykkösiä
61 (135)
TIETOLIIKENNE- LABORATORIO
Sykliset koodit
• Esim. Hamming-koodi on syklinen – (7,4)-koodilla on
– merk.
+ +
+ +
+ + +
+ + + +
=
+ +
+ +
+ + +
+ +
=
1 D D
) 1 D D ( D
) 1 D D )(
1 (D
) 1 D D )(
1 D D (
1 D D
D D D
1 D D D
1 D D ) D (
3 3 3 2
3 3
3 2 4
2 5
2 6
G
=
1 1 0 1 0 0 0
0 1 1 0 1 0 0
1 1 1 0 0 1 0
1
0
1
0
0
0
1
G
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Kaikki koodipolynomit ovat siis jaollisia polynomilla g(D) = D 3 + D + 1
• Tämä polynomi on koodin generoijapolynomi
• Teoreema
– syklisen (n,k)-koodin generoijapolynomi g(D) on polynomin D
n+ 1 tekijä
– kääntäen: jokainen polynomin D
n+ 1 tekijä, jonka asteluku on (n – k), generoi syklisen (n,k)-koodin
63 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Taulukossa 10.5 on esitetty polynomin D
n+ 1 tekijöitä oktaalimuodossa
– esim. toisella rivillä (n = 9) on
6 = 110 = 1 + D 7 = 111 = 1 + D + D 2 444 = 100100100 = 1 + D 3 + D 6
huom. järjestys
64 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
– siten D 9 + 1 = (D + 1)(D 2 + D + 1)(D 6 + D 3 + 1)
– mitä muita koodeja on vielä mahdollista muodostaa?
• Taulukossa 10.5 on vain parittomia n:n arvoja
• Jos n = 2m on parillinen, D n + 1 jaetaan ensin tekijöihin D n + 1 = D 2m + 1 =(D m + 1)(D m + 1)
ja katsotaan taulukosta polynomin D m +1 tekijät
– jos m on parillinen, menetelmää jatketaan, kunnes tullaan parittomaan astelukuun
(9,8)-koodi (9,7)-koodi (9,3)-koodi
65 (135)
TIETOLIIKENNE- LABORATORIO
Sykliset koodit
• Taulukosta 10.5 havaitaan, että polynomin D n + 1 tekijöihin kuuluu aina polynomi D + 1
• Tämä polynomi generoi (n,n–1)-koodin, jossa on vain yksi pariteettibitti (koodisanan pariteetti on aina parillinen), ja koodi on syklinen
• Tietyillä n:n arvoilla (n = 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, …) jako tekijöihin on helppo:
D n + 1 =(D + 1)(D n–1 + D n–2 + ··· + D + 1)
• Nämä n:n arvot on jätetty pois taulukosta 10.5
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Sykliset koodit
• Esim. n = 3
– D 3 + 1 = (D + 1)(D 2 + D + 1) D 2 + D +1
D + 1 D 3 +1
D 3 + D 2
D 2 +1
D 2 + D D + 1 D + 1 0
67 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
koodipolynomin muodostaminen
x(D) = D
n–ku(D) + r(D)
systemaattinen koodi
r(D) on jakojäännös, kun D
n–ku(D) jaetaan g(D):llä
68 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
• x(D) = D n–k u(D) + r(D)
D 3 u(D) = D 3 (D 3 + D 2 + 1) = D 6 + D 5 + D 3 D 3 + D 2 + D + 1
D 3 + D + 1 D 6 + D 5 + D 3 D 6 + D 4 + D 3
D 5 + D 4
D 5 + D 3 + D 2 D 4 + D 3 + D 2 D 4 + D 2 + D
D 3 + D
D 3 + D + 1 1 x(D) = D 6 + D 5 + D 3 +1
D6D5D4D3D2 D1 D0=1
69 (135)
TIETOLIIKENNE- LABORATORIO
Syklisten koodien koodausalgoritmit
– x = (1101001), koodi on systemaattinen
• Syklisen koodin generointi perustuu kertoja- ja jakajapiirien käyttöön
• Piirit koostuvat yhteenlaskupiireistä, muistielementeistä
(kiikkupiireistä) ja vakiolla kertojista
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
⊕ a a
modulo-2-summain (XOR-piiri)
muistielementti (kiikkupiiri), jonka muistissa binääriluku a (piirin lähtö on siis luku a)
vakiolla kertoja (kertoo binääriluvulla a)
a
= 1
a
= 0
D Q
Q a a
71 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
• Esim. Piirrä piiri, joka kertoo polynomilla D n–k = D 3 ja jakaa polynomilla g(D) = D 3 + D + 1
⊕ ⊕
lähtö
r
0r
1r
2tulo u
i0 1 2 3
72 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
• Tämä piiri muodostaa perustan systemaattisen syklisen (7,4)-koodin generoinnille
• Piirin etuna on se, että jakojäännös (pariteettibitti) voidaan lukea rekisteristä ulos heti, kun informaatiobitit on luettu sisään
u i r 0 r 1 r 2
0 – 0 0 0
1 1 1 1 0
2 1 1 0 1
3 0 1 0 0
4 1 1 0 0 jakojäännös (001)
73 (135)
TIETOLIIKENNE- LABORATORIO
Syklisten koodien koodausalgoritmit
• Toiminta kooderina:
⊕ ⊕
A B
A B
lähde
kanava
B
A
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Syklisten koodien koodausalgoritmit
• Toiminta
– informaatiobitit luetaan siirtorekisteriin ja samanaikaisesti kanavaan
• kytkimet asennossa A
– neljän kellopulssin jälkeen kytkimet siirretään asentoon B ja luetaan pariteettibitit kanavaan
• huom. takaisinkytkentä täytyy katkaista, jotta pariteettibitit eivät muuttuisi
• Edellä esitetty kooderi sisältää (n – k) muistielementtiä
• Piiriä voidaan käyttää mille tahansa sykliselle koodille, jonka generoijapolynomi on tunnettu
75 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
• Kanavassa koodipolynomiin x(D) summautuu virhepolynomi e(D), vastaanotettu polynomi on
• Jaetaan vastaanotettu polynomi koodin generoijapolynomilla:
• y(D) on koodipolynomi, jos ja vain jos polynomi s(D) = 0
• Tämä polynomi (asteluku enintään n – k – 1) on y(D):n oirepolynomi
y(D) = x(D) + e(D)
y(D) = m(D)g(D) + s(D)
osamäärä jakojäännös
) D (
) D ) ( D ) ( D (
) D (
g m s g
y = +
76 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
• Virheen ilmaisu tapahtuu siis jakamalla y(D) generoijapolynomilla g(D) ja tutkimalla, onko jakojäännös eli oirepolynomi s(D) = 0
• Virhe on tapahtunut, jos s(D) ≠ 0
77 (135)
TIETOLIIKENNE- LABORATORIO
Virheen ilmaisu ja korjaus
÷
÷
÷
÷ g(D) ⊕ ÷ ÷ ÷ ÷ g(D)
D
n–ku(D) s(D)
e(D)
x(D) y(D)
G ⊕ H T
u s
e
generoijamatriisi pariteetin- tarkastusmatriisi
x y
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
• Esim.
– generoijapolynomi on g(D) = D 3 + D + 1 – vastaanotettu sekvenssi y(D) = D 6 + D 5 + 1
• y = (1100001) – oirepolynomi s(D) = ?
79 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
D 3 + D 2 + D
D 3 + D + 1 D 6 + D 5 + 1
D 6 + D 4 + D 3
D 5 + D 4 + D 3 + 1 D 5 + D 3 + D 2
D 4 + D 2 + 1 D 4 + D 2 + D
D + 1 = s(D)
s = (011)
s
2s
1s
080 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
– oiresanan laskeminen (jakajapiiri):
⊕ ⊕
0 1 2 3
s
0s
1s
2y s
0s
1s
2– 0 0 0
1 1 0 0
1 1 1 0
0 0 1 1
0 1 1 1
0 1 0 1
0 1 0 0
1 1 1 0 s(D) = D + 1
81 (135)
TIETOLIIKENNE- LABORATORIO
Virheen ilmaisu ja korjaus
y s0 s1 s2 b c
lähtö
0 – 0 0 0 – –
1 1 1 1 0 – –
2 1 1 0 1 – –
3 0 1 0 0 – –
4 0 0 1 0 – –
5 0 0 0 1 – –
6 0 1 1 0 – –
7 1 1 0 1 – –
8 – 1 0 0 1 0 1
9 – 0 1 0 1 0 1
10 – 0 0 1 0 0 0
11 –
0 0 00 1 1
12 –
0 0 00 0 0
13 –
0 0 00 0 0
14 – 1 0 1
x
ˆ
oiresanan laskeminen
oiresanan
siirtäminen
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
⊕
s
0⊕ s
1s
2⊕
B A
A
B c
b 1 0 0 0 0 1 1
0 0 1
x ˆ
&
kanava
83 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Virheen ilmaisu ja korjaus
– toiminta:
1. luetaan vastaanotettu sana y oiresanageneraattoriin ja puskuriin (kytkimet asennossa A)
2. siirretään kytkimet asentoon B ja siirretään oiresanaa ja puskuria
• Edellä esitetty dekooderi on ns. Meggit-dekooderi, jota voidaan soveltaa myös useamman virheen
korjaamiseen
• Menetelmää sanotaan myös virheen "vangitsemiseksi"
– error trapping
84 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Erityisiä syklisiä koodeja
• BCH-koodit (Bose-Chaudhuri-Hocquenghem) – korjaavat t virhettä
– generoijapolynomit taulukossa 10.7 (eniten merkitsevä bitti vasemmalla, päinvastoin kuin aikaisemmassa taulukossa) – esim. rivillä 3
• m = 4, n = 15, n – k = 15 – 7 = 8, t = 2
• 721 → 111 010 001 → g(D) = D 8 + D 7 + D 6 + D 4 +1
85 (135)
TIETOLIIKENNE- LABORATORIO
Erityisiä syklisiä koodeja
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Erityisiä syklisiä koodeja
– vrt. taulukon 10.5 mukaan syklisen koodin generoijapolynomit ovat (n = 15)
• 6 → 110 → g 1 (D) = 1 + D
• 7 → 111 → g 2 (D) = 1 + D + D 2
• 46 → 100 110 → g 3 (D) = 1 + D 3 + D 4
• 62 → 110 010 → g 4 (D) = 1 + D + D 4
• 76 → 111 110 → g 5 (D) = 1 + D + D 2 + D 3 + D 4 – BCH-koodin generoijapolynomi on
g(D) = g 4 (D)g 5 (D)
= (D 4 + D + 1)(D 4 + D 3 +D 2 + D +1)
= D 8 + D 7 + D 6 + D 5 + D 4 + D 5 + D 4 + D 3 + D 2 + D + D 4 + D 3 + D 2 + D +1
= D 8 + D 7 + D 6 + D 4 + 1
87 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Erityisiä syklisiä koodeja
– BCH-koodit ovat tärkeitä käytännössä
• riittävän yksinkertaiset dekoodausalgoritmit
• parametriarvot melko vapaasti valittavissa
• kun n on enintään muutamia satoja, monet BCH-koodeista ovat lähes parhaita mahdollisia koodeja
• Reed–Salomon-koodit – ei-binäärisiä BCH-koodeja
• m bittiä muodostavat symbolin – erilaisia symboleita 2
m= q kpl
88 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Erityisiä syklisiä koodeja
– koodi korjaa t symbolivirhettä (mt bittivirhettä) – sopivat hyvin ryöppyvirheiden korjaamiseen – käytetään myös ketjukoodien ulkokoodina
n kpl
m m m m m m m
k kpl
n = 2
m– 1 symbolia = m · (2
m– 1) bittiä n – k = 2t symbolia = 2mt bittiä
89 (135)
TIETOLIIKENNE- LABORATORIO
Ryöppyvirheiden ilmaisu ja korjaus
• Kanava ei ole muistiton, esim. magneettinauha yms., häipyvä kanava, pulssimainen häiriö kanavassa
– virheet eivät tapahdu toisistaan riippumatta
• Tällöin satunnaisvirheitä korjaava koodi on tehoton
virhetyypit
satunnaisvirheet ryöppyvirheet
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Ryöppyvirheiden ilmaisu ja korjaus
• Eri mahdollisuuksia
1. ryöppyvirheitä korjaavat koodit
• sykliset koodit (esim. fire-koodi)
• ketjukoodit 2. lomittimien käyttö
• Taulukossa 10.9 on lueteltu tehokkaita syklisiä ja lyhennettyjä syklisiä koodeja ryöppyvirheiden korjaamiseen
• Generoijapolynomit ovat oktaalimuodossa, suurinta astelukua vastaava termi vasemmalla
91 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Ryöppyvirheiden ilmaisu ja korjaus
92 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Ryöppyvirheiden ilmaisu ja korjaus
• Esim. taul. 10.9 (31,25)-koodi
– 161 → 001110001 → g(D) = D 6 + D 5 + D 4 + 1
93 (135)
TIETOLIIKENNE- LABORATORIO
Lomittimet
• Satunnaisvirheitä korjaavaa koodia voidaan käyttää myös kanavassa, jossa syntyy ryöppyvirheitä
• Virheet on kuitenkin ensin tehtävä satunnaisiksi lomittimen ja vastalomittimen avulla
kooderi lomitin kanava vastalomitin dekooderi
(n,k)-koodi (in,ik)-koodi ryöppy- virheitä
satunnaisia
virheitä
(i = lomitteluaste)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Lomittimet
• Esim.
– (15,5)-BCH-koodi, t = 3, i = 5
– jos lomitteluaste i = 5, saadaan (75,25)-koodi, joka korjaa edelleen 3 satunnaisvirhettä tai virheryöpyn, jonka pituus on enintään it = 5 · 3 = 15 virhettä
• On olemassa useita erilaisia tapoja toteuttaa lomittelu – lohkolomittelu
– konvoluutiolomittelu
• Lomittelua voi esiintyä myös useassa eri tasossa (vrt.
esim. CD-levy)
95 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Konvoluutiokoodit
• Konvoluutiokoodit ovat lineaarisia koodeja, jotka toimivat yleensä vähintään yhtä hyvin kuin lohkokoodit
• Konvoluutiokoodien koodimatematiikka ei ole niin pitkälle kehittynyt kuin lohkokoodeilla
1 1
2 2
k
0n
0konvoluutiokooderi
muistissa N – 1 aikaisempaa lohkoa
(n
0,k
0)-koodi koodisuhde r
c= k
0/n
0N = vaikutuspituus (constraint length) v = (N – 1)k
0= muistin koko
n
0, k
0ja N pieniä kokonaislukuja
96 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Konvoluutiokoodit
nämä kytkennät määrittelevät konvoluutiokoodin → generaattorivektorit 1 2 ··· k
01 2 ··· k
01 2 ··· k
01 2 N
u
1 2 ··· n
0x
⊕ ⊕ ⊕
97 (135)
TIETOLIIKENNE- LABORATORIO
Konvoluutiokoodit
• Kooderi ottaa aina sisään k 0 bittiä ja laskee N:n lohkon avulla n 0 bittiä
• Lohkokoodilla vaikutuspituus N = 1
• Lohkokoodi on siis konvoluutiokoodin rajatapaus
konvoluutiokoodit
lohkokoodit
N > 1
N = 1
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Konvoluutiokoodit
• Esim. (3,1)-koodi, vaikutuspituus N = 3
⊕ ⊕ ⊕
u
x
kommutaattori (korvaa toisen siirtorekisterin)
99 (135)
TIETOLIIKENNE- LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Konvoluutiokoodit
100 (135)
LABORATORIO
Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009
Konvoluutiokoodit
• Esim. (3,1)-koodi, N = 3
⊕ ⊕ ⊕
u
x
generaattorivektorit:
g
1= (100) g
2= (110) g
3= (111)
n
0kpl
k
0N kpl
101 (135)
TIETOLIIKENNE- LABORATORIO