1VIRHEENKORJAUS JA-ILMAISU

(1)

VIRHEENKORJAUS JA -ILMAISU

Kanavakoodaus

TIETOLIIKENNE- LABORATORIO

Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009 B. Sklar, Digital Communications

2 (135)

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

2

S bit/s C B

N

S = E

_b

R

_b

= teho N = N

₀

B

3 (135)

Tiedonsiirron perusresurssit

LÄHETYSTEHO

MONIMUTKAISUUS

KAISTANLEVEYS

VIRHETODENNÄKÖISYYS

4 (135)

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ä

Tiedonsiirron perusresurssit

KOODAUS

MODULOINTI KANAVA DEKOODAUS

DEMODULOINTI

Monimutkaisuus Lähetysteho

Kaistanleveys

Signaali-kohinasuhde

Virhetodennäköisyys Monimutkaisuus

(2)

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)

Erilaisia koodausjärjestelmiä

Langattomien tietoliikennejärjestelmien perusteet: Kanavakoodaus Timo Kokkonen Kevät 2009 KANAVAKOODAUSMENETELMÄT

FEC-MENETELMÄT ARQ-MENETELMÄT

8 (135)

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ä

Erilaisia koodausjärjestelmiä

KOODERI KANAVA FEC ⊕ ⊕ ⊕ ⊕

Virheenkorjaus

ARQ KANAVA

KOODERI

PALUU-

KANAVA

NAK = negative acknowledgement ACK= positive acknowledgement

10 (135)

Kanavakoodien jako

KANAVAKOODIT

LOHKOKOODIT KONVOLUUTIOKOODIT

11 (135)

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-

koodaus

k informaatio-

koodaus

(mod-2-summa) LOHKOKOODI

12 (135)

(3)

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)

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-

koodaus (mod-2-summa) KONVOLUUTIOKOODI

14 (135)

Perusteita

• Erilaisia koodisanoja on siis 2

ⁿ

kpl – kooderi käyttää niistä vain 2

^k

kpl – n > k

• Kanavassa koodisanaan saattaa tulla virheitä – vastaanotettu koodisana voi olla mikä tahansa 2

ⁿ

: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)

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)

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 ⋅ =

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

= ε ⋅ = ε ⋅

ε

(4)

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⁻²

(joskus 0,1 - 0,2 voidaan hyväksyä)

10

⁻2

≤

19 (135)

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)

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)

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)

22 (135)

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)

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

(5)

Lohkokoodit

• Esim. (n,n–1)-koodi – informaatiosana 0110011 – koodisana 0110011 – informaatiosana 0000111 – koodisana 0000111

pariteettibitti (parillinen pariteetti)

1 0

25 (135)

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 ₁ , u ₂ , … , u

_k

] informaatiosana x = [x ₁ , x ₂ , … , x

_n

] koodisana

26 (135)

Lohkokoodit

• Esim. Toistokoodi (n = 3)

• Esim. (3,2)-koodi

u

1

x

3

x

2

x

1

0 ↔ ↔ ↔ ↔ 000 1 ↔ ↔ ↔ ↔ 111

u

2

x

₃

x

₂

x

₁

00 ↔ ↔ ↔ ↔ 000 01 ↔ ↔ ↔ ↔ 011 10 ↔ ↔ ↔ ↔ 101 11 ↔ ↔ ↔ ↔ 110 u

1

⊕⊕⊕

⊕

u1u2 x1x2x3

(3,1)-koodi

1 0

1 1 0

27 (135)

Lohkokoodit

• Esim. Hamming-koodi ((7,4)-koodi)

• Koska koodit ovat systemaattisia, tarvitsee laskea vain n – k pariteettibittiä

u

1

x

2

x

4

x

3

u

2

u

4

x

7

x

6

x

5

u

3

⊕

⊕⊕

⊕

x

1

⊕

28 (135)

Lohkokoodin generoijamatriisi

• Generoijamatriisi (generoiva matriisi) määrittelee kooderin rakenteen

• Esim. (7,4)-Hamming-koodi

u

1

x

2

x

4

x

3

u

2

u

4

x

7

x

6

x

5

u

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

1

x

2

x

3

x

4

x

5

x

6

x

7

u

1

u

₂

u

3

u

₄

Lohkokoodin generoijamatriisi

• Koodisana x lasketaan informaatiosanasta u seuraavasti:

x = uG

• Jos u = (1100), niin

( )

17

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 =

(6)

(7,4)-Hamming-koodi

Informaatiosanat Koodisanat

Onko koodi systemaattinen?

On se

31 (135)

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

k

on yksikkömatriisi (k

^x

k-matriisi) P on k

^x

(n – k)-matriisi (pariteettimatriisi)

32 (135)

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)

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

₁

= (00010001011) x

2

= (00100010110)

x

1

+ x

2

=(00110011101) Hamming-etäisyys = 6

34 (135)

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)

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)

(7)

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)

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

38 (135)

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)

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

x

n n

x

(n–k)

(n-k)xn nx(n-k)

40 (135)

Lohkokoodin virheen ilmaisu- ja korjauskyky

• Esim. (7,4)-Hamming-koodi. Oiresanan s = (s ₁ , s ₂ , s ₃ ) bitit saadaan seuraavasti: y = (y ₁ , y ₂ , … , y ₇ )

kooderi x

₅

= u

₁

+ u

₂

+ u

₃

x

6

= u

2

+ u

3

+ u

4

x

7

= u

1

+ u

2

+ u

4

dekooderi

s

₁

= (y

₁

+ y

₂

+ y

₃

) + y

₅

s

₂

= (y

₂

+ y

₃

+ y

₄

) + y

₆

s

₃

= (y

₁

+ y

₂

+ y

₄

) + y

₇



 









 







=

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

1

x

2

x

3

x

4

x

5

x

6

x

7

u

1

u

2

u

₃

u

4 (n-k)xn

(

nk

)

T

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 pariteettibitit uudestaan

verrataan vastaanotettuihin vastaaviin bitteihin

Lohkokoodin virheen ilmaisu- ja korjauskyky

( )

(

₁ ₂ ₃ ₅ ₂ ₃ ₄ ₆ ₁ ₂ ₄ ₇

)

) ( 1

7 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

^x

n n

x

(n–k)

, ,

) , , ( s

₁

s

₂

s

₃

=

(8)

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)

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)

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

min

d

min

–1

x y x

45 (135)

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

ⁿ

kpl

• Jokaista oiresanaa kohti on siis 2

^k

kpl vastaanotettua sanaa

• Selitys:

– virhesanaan e voi lisätä minkä tahansa koodisanan x (2

^k

kpl) eikä oiresana silti muutu

46 (135)

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

min

d

_min







 −

− =

=

2 1 2

1

_min

min d

t d 





 −

=

−

=

2 1 1 2

min

min d

t d

47 (135)

Lohkokoodin virheen ilmaisu- ja korjauskyky

• Koodinsuunnittelun tavoite on käyttää redundanssia mahdollisimman suuren minimietäisyyden

saavuttamiseksi

d_min d_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)

(9)

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)

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

50 (135)

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)

Koodiperheiden kehitys

52 (135)

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

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,…

(10)

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)

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

4

0 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)

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)

Lohkokoodeja

Hamming-koodi

Maksimipituuskoodi simplex-koodi

Laajennettu maksimipituuskoodi ortogonaalinen koodi

Reed–Müller-koodi (r = 1) biortogonaalinen koodi duaalikoodi

lisää pariteettibitti

lisää vastakkaiset koodisanat

58 (135)

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)

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)

(11)

Sykliset koodit

• Koodisana x = (x _n–1 , x _n–2 , … , x ₀ ) esitetään koodipolynomin

x(D) = x _n–1 D ^n–1 + x _n–2 D ^n–2 + ··· + x ₁ D + x ₀ avulla

• Kertoimet x _n–1 , x _n–2 , … , x ₀ ovat binäärisiä – nollia ja ykkösiä

61 (135)

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

62 (135)

Sykliset koodit

• Kaikki koodipolynomit ovat siis jaollisia polynomilla g(D) = D ³ + D + 1

• Tämä polynomi on koodin generoijapolynomi

• Teoreema

– syklisen (n,k)-koodin generoijapolynomi g(D) on polynomin D

ⁿ

+ 1 tekijä

– kääntäen: jokainen polynomin D

ⁿ

+ 1 tekijä, jonka asteluku on (n – k), generoi syklisen (n,k)-koodin

63 (135)

Sykliset koodit

• Taulukossa 10.5 on esitetty polynomin D

ⁿ

+ 1 tekijöitä oktaalimuodossa

– esim. toisella rivillä (n = 9) on

6 = 110 = 1 + D 7 = 111 = 1 + D + D

²

444 = 100100100 = 1 + D

³

+ D

⁶

huom. järjestys

64 (135)

Sykliset koodit

– siten D

⁹

+ 1 = (D + 1)(D

²

+ D + 1)(D

⁶

+ D

³

+ 1)

– mitä muita koodeja on vielä mahdollista muodostaa?

• Taulukossa 10.5 on vain parittomia n:n arvoja

• Jos n = 2m on parillinen, D

ⁿ

+ 1 jaetaan ensin tekijöihin D

ⁿ

+ 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

Sykliset koodit

• Taulukosta 10.5 havaitaan, että polynomin D

ⁿ

+ 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

ⁿ

+ 1 =(D + 1)(D

^n–1

+ D

^n–2

+ ··· + D + 1)

• Nämä n:n arvot on jätetty pois taulukosta 10.5

(12)

Sykliset koodit

• Esim. n = 3

– D

³

+ 1 = (D + 1)(D

²

+ D + 1) D

²

+ D +1

D + 1 D

³

+1

D

³

+ D

²

D

²

+1

D

²

+ D D + 1 D + 1 0

67 (135)

Syklisten koodien koodausalgoritmit

koodipolynomin muodostaminen

x(D) = D

^n–k

u(D) + r(D)

systemaattinen koodi

r(D) on

jakojäännös, kun D

^n–ku(D)

jaetaan g(D):llä

68 (135)

Syklisten koodien koodausalgoritmit

• x(D) = D

^n–k

u(D) + r(D)

D

³

u(D) = D

³

(D

³

+ D

²

+ 1) = D

⁶

+ D

⁵

+ D

³

D

³

+ D

²

+ D + 1

D

³

+ D + 1 D

⁶

+ D

⁵

+ D

³

D

⁶

+ D

⁴

+ D

³

D

⁵

+ D

⁴

D

⁵

+ D

³

+ D

²

D

⁴

+ D

³

+ D

²

D

⁴

+ D

²

+ D

D

³

+ D

D

³

+ D + 1 1 x(D) = D

⁶

+ D

⁵

+ D

³

+1

D⁶D⁵D⁴D³D²D¹D⁰=1

69 (135)

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

70 (135)

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)

Syklisten koodien koodausalgoritmit

• Esim. Piirrä piiri, joka kertoo polynomilla D ^n–k = D ³ ja jakaa polynomilla g(D) = D ³ + D + 1

⊕ ⊕

lähtö

r

0

r

1

r

₂

tulo u

_i

0 1 2 3

72 (135)

(13)

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

₀

r

₁

r

₂

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)

Syklisten koodien koodausalgoritmit

• Toiminta kooderina:

⊕ ⊕

A B

lähde

kanava

B A

74 (135)

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)

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)

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

Virheen ilmaisu ja korjaus

÷

÷ g(D) ⊕ ÷ ÷ ÷ ÷ g(D)

D

^n–k

u(D) s(D)

e(D)

x(D) y(D)

G ⊕ H ^T

u s

e

generoijamatriisi pariteetin- tarkastusmatriisi

x y

(14)

Virheen ilmaisu ja korjaus

• Esim.

– generoijapolynomi on g(D) = D

³

+ D + 1 – vastaanotettu sekvenssi y(D) = D

⁶

+ D

⁵

+ 1

• y = (1100001) – oirepolynomi s(D) = ?

79 (135)

Virheen ilmaisu ja korjaus D ³ + D ² + D

D ³ + D + 1 D ⁶ + D ⁵ + 1

D ⁶ + D ⁴ + D ³

D ⁵ + D ⁴ + D ³ + 1 D ⁵ + D ³ + D ²

D ⁴ + D ² + 1 D ⁴ + D ² + D

D + 1 = s(D)

s = (011)

s2s1s0

80 (135)

Virheen ilmaisu ja korjaus

– oiresanan laskeminen (jakajapiiri):

⊕ ⊕

0 1 2 3

s0 s1 s2

y s0 s1 s2

– 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)

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 0 0 1 1

12 – 0 0 0 0 0 0

13 – 0 0 0 0 0 0

14 – 1 0 1

xˆ

oiresanan laskeminen

oiresanan siirtäminen

82 (135)

Virheen ilmaisu ja korjaus

⊕

s0 s1 s2

⊕

B A

A

B

c

b 1 0 0 0 0 1 1

0 0 1

x ˆ

&

kanava

83 (135)

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)

(15)

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

⁸

+ D

⁷

+ D

⁶

+ D

⁴

+1

85 (135)

Erityisiä syklisiä koodeja

86 (135)

Erityisiä syklisiä koodeja

– vrt. taulukon 10.5 mukaan syklisen koodin generoijapolynomit ovat (n = 15)

• 6 → 110 → g

₁

(D) = 1 + D

• 7 → 111 → g

₂

(D) = 1 + D + D

²

• 46 → 100 110 → g

₃

(D) = 1 + D

³

+ D

⁴

• 62 → 110 010 → g

₄

(D) = 1 + D + D

⁴

• 76 → 111 110 → g

₅

(D) = 1 + D + D

²

+ D

³

+ D

⁴

– BCH-koodin generoijapolynomi on

g(D) = g

₄

(D)g

₅

(D)

= (D

⁴

+ D + 1)(D

⁴

+ D

³

+D

²

+ D +1)

= D

⁸

+ D

⁷

+ D

⁶

+ D

⁵

+ D

⁴

+ D

⁵

+ D

⁴

+ D

³

+ D

²

+ D + D

⁴

+ D

³

+ D

²

+ D +1

= D

⁸

+ D

⁷

+ D

⁶

+ D

⁴

+ 1

87 (135)

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)

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ä

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

(16)

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)

Ryöppyvirheiden ilmaisu ja korjaus

92 (135)

Ryöppyvirheiden ilmaisu ja korjaus

• Esim. taul. 10.9 (31,25)-koodi

– 161 → 001110001 → g(D) = D

⁶

+ D

⁵

+ D

⁴

+ 1

93 (135)

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)

94 (135)

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)

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

k0 n0

konvoluutiokooderi

muistissa N – 1 aikaisempaa lohkoa

(n

0

,k

0

)-koodi koodisuhde r

c

= k

0

/n

0

N = vaikutuspituus (constraint length) v = (N – 1)k

0

= muistin koko n

0

, k

0

ja N pieniä kokonaislukuja

96 (135)

(17)

Konvoluutiokoodit

nämä kytkennät määrittelevät konvoluutiokoodin

→

generaattorivektorit 1 2

···

k

0

1 2

···

k

0

1 2

···

k

0

1 2 N

u

1 2

···

n

0

x

⊕ ⊕ ⊕

97 (135)

Konvoluutiokoodit

• Kooderi ottaa aina sisään k ₀ bittiä ja laskee N:n lohkon avulla n ₀ bittiä

• Lohkokoodilla vaikutuspituus N = 1

• Lohkokoodi on siis konvoluutiokoodin rajatapaus konvoluutiokoodit

lohkokoodit

N > 1 N = 1

98 (135)

Konvoluutiokoodit

• Esim. (3,1)-koodi, vaikutuspituus N = 3

⊕ ⊕ ⊕

u

x

kommutaattori (korvaa toisen siirtorekisterin)

99 (135)

Konvoluutiokoodit

100 (135)

Konvoluutiokoodit

• Esim. (3,1)-koodi, N = 3

⊕ ⊕ ⊕

u

x

generaattorivektorit:

g

₁

= (100) g

₂

= (110) g

₃

= (111)

n0

kpl

k0Nkpl