Statistikk og Simulering

Veke 5. Feilsannsyn og binomialfordeling

Simulering av kommunikasjonssystem

5.4. Simulering av kommunikasjonssystem

Dette er starten på eit simuleringsprosjekt som vil gå over 2–3 veker.

Oppgåve 5.17 (Hovudspørsmål) Kva er sannsynet for dekodingsfeil (ordfeil) når du sender eit ord koda med ein [31, 11] BCH-kode over BSC med bitfeilsannsyn pe?

For å svare på hovudspørsmålet må be byggja opp simulatoren steg for steg. Den fyrste delen vil ta for seg sjølve simuleringa av eit kommunikasjonssystem utan feilkorrigerande kodar. Neste veke vil me leggja til koding og dekoding, og til slutt skal me sjå på estimeringa. Øvinga er eit realistisk døme på bruk av stokastisk simulering, sokalt Monte Carlo-simulering, i ingeniørfag. Rett nok er komponentane som bruker i systemet vel enkle, men kvar enkelt kan utan vanskar bytast ut med ein meir komplisert modell. Systemmodellen er eksakt slik ein kan sjå han i forsking og utvikling.

NB! Dersom du ikkje vert ferdig i løpet av labøkta, er det viktig at du arbeider videre heime. Neste veke skal me byggja vidare på arbeidet frå i dag.

Dersom du vert tidleg ferdig, so er det lov å ta fatt på øvinga neste veke.

5.4.1. Simulering av kommunikasjonssystemet

pict


Figur 3: Coding system for simulation.

Figur 3 viser kommunikasjonssystemet som me skal simulera. Me må modellera og simulera kjelda (source) som genererer tilfeldige meldingar og kanalen (BSC) som tilfører støy mellom sendar og mottakar. Til koding og dekoding kan me bruka implementasjonar av eit ekte kodesystem som me ynskjer å testa. Desse skal me difor ikkje modellera, og me treng ikkje implementera dei sjølv.

«Compare»-boksen er ikkje ein del av kommunikasjonssystemet, men vert brukt av simulatoren for å sjekka resultatet av kvart forsøk og telja feil.

Oppgåve 5.18 (Kjeldesimulator) Ein reknar normalt med at meldinga m er uniformt fordelt, over mengda av alle binærvektorar av lengd n. Dersom meldinga ikkje er uniformt fordelt, løner det seg å komprimera ho fyrst.

Skriv ein funksjon (m-fil) som tekn ordlengda n som argument og returnerer eit tilfeldig meldingsord m.

Test funksjonen eit par gongar. Er resultata rimelege?

Når det gjeld kanalmodellen, so skal me simulera ein svært enkel modell, den binærsymmetriske kanalen BSC(p). I røynda er der stor skilnad mellom ulike kanalar. Trådlaust nettverk er forskjellig frå kabla nett, som igjen er ulikt lagringsmedium som optiske og magnetiske plater. Stasjonære antennar er òg svært ulikt mobilt utstyr. Dette kan ein lære meir om i kurs i telekommunikasjon og i kodeteori. Her klarer me oss med den enkle modellen, og fokuserer på simulering og statistikk.

Definisjon 13 (Den binærsymmetriske kanalen) Den binærsymmetriske kanalen med bitfeilsannsyn p (BSC(p)) tek ein meldingsord m = (m1,m2,.mn) som input og returnerer eit motteke ord r = (r1,r2,,rn), der kvar bit ri er lik mi med sannsyn 1 p og ulik (feil) med sannsyn 1 p. Kvar bit er uavhengig av alle foregåande bits.

Definisjon 14 (Feilvektor) Lat m = (m1,m2,.mn) vera ein binær meldiga og r = (r1,r2,,rn) det mottekne ordet etter at meldinga er sendt over ein kanal. Me definerer feilvektoren e = r mmod 2.

Oppgåve 5.19 (Diskusjon) Kva sannsynsfordeling har feilvektoren e når me sender n bits over BSC(p)? Er sannsynsfordelinga avhengig av meldinga m?

Oppgåve 5.20 (Kanalsimulator) Me skal implementera ein funksjon (m-fil) som tek ein meldingsvektor og eit bitfeilsannsyn p som argument og returnerer ein motteken vektor med same lengd, som om han var sendt over BSC(p). Dette kan gjerast på ulike måtar; det fylgjande er eit forslag:

1.
Trekk ein tilfeldig feilvektor e. Lag gjerne ein eigen funksjon for det.
2.
Returner r = m + emod 2.

Test funksjonen/funksjonane eit par gongar. Er resultata rimelege?

Simuleringsresultat

Definisjon 15 (Hamming-vekt) Hamming-vekta w(x) på ein vektor x er talet på bits som er ulik 0. (Dvs., for ein binær vektor, er Hamming-vekta lik talet på bits som er 1.)

Når me studerer kommunikasjonssystem, er der to ulike heuristikkar som er interessante
Bitfeil
Hammingvekta åt feilvektoren w(e), gjev talet på bitfeil i overføringa av eitt ord.
Ordfeil
Dersom det mottekne ordet er ulik meldinga, dvs. rm, so er der skjedd éin ordfeil.

I denne øvinga skal me konsentrera oss om å telja bitfeil.

Oppgåve 5.21 Skriv ein funksjon (m-fil) som reknar ut Hamming-vekta for ein binærvektor e.

Test funksjonen eit par gongar. Er resultata korrekte?

Hint Du kan bruka sum-funksjonen her.

Oppgåve 5.22 Lag ein funksjon som tek eit meldingsord m og eit motteke ord r og returnerer hammingvekta åt feilvektoren e = m rmod 2. Test funksjonen eit par gongar. Er resultata korrekte?

Ein simulator Me skal studera eit scenario der me sender n-bits ord over BSC(p), og tel talet på bitfeil Z. Utfallsrommet er altso Z {0, 1,,n}. Merk at me simulerer utan koding; me får koma tilbake til kokding og dekoding neste veke.

Oppgåve 5.23 Lat oss fyrst simulera éin observasjon av Z. Bruk funksjonane du implementerte over, og vis korleis du kombinerer dei for å simulera 10 bits på BSC(0,1). Du treng ikkje meir enn éi kodeline for å gjera dette.

Oppgåve 5.24 Skriv ein funksjon som tek tre argument, og gjer m simuleringar av eit n-bits ord på BSC(p). Returverdien skal vera ei matrise med m observasjonar av Z.

Oppgåve 5.25 Bruk funksjonen over og simuler 10-bits ord på BSC(0,1), og teikn eit histogram for talet på feil. Prøv med m = 10, 100, 1000 simuleringar. Samanlikn dei tre histogramma.

Oppgåve 5.26 Bruk funksjonen over og simuler 10-bits ord på BSC(p) for ulike verdiar av p. Bruk m = 100 simuleringar go p = 0,01,0,05,0,1. Teikn eit histogram for kvar verdi av p og samanlikn.

Oppgåve 5.27 Bruk funksjonen over og simuler n-bits ord på BSC(0,1) for ulike verdiar av n. Bruk m = 100 simuleringar go n = 5, 10, 25. Teikn eit histogram for kvar verdi av n og samanlikn.

Oppgåve 5.28 Svar på fylgjande vha. simuleringane dine frå dei tre siste oppgåvene. Gjer gjerne fleire simuleringar dersom du kjenner at det vil hjelpa.

1.
Kva trur du gjennomsnittet for Z er for gjevne verdiar av n og p?
2.
Sjå på spreidinga i histogramma. Aukar eller minkar spreidinga når p aukar?
3.
Aukar eller minkar spreidinga når n aukar?
4.
Aukar eller minkar spreidinga når m aukar?

Oppgåve 5.29 Gjenta øving 5.25, 5.26 og 5.27, men rekn ut gjennomsnitt (mean) og standardavvik (std) i staden for å plotta histogram. Er tala rimelege samanlikna med teorien for binomialfordelinga?

5.4.2. Teoretisk fordeling i Matlab

The probability distribution function (PDF) I Matlab kan du skriva pdf(’binom’,x,n,p) for å finna sannsynet P(Z = x) for Z B(n,p). PDF står for probability distribution function.

Oppgåve 5.30 Gå tilbake til overføringa av fire-bits ord over BSC(0.1). Lat Z vera talet på bitfeil. Bruk Matlab for å finna sannsynet P(Z = 0), som fylgjer

1  pdf(’binom’,0,4,0.1) Samanlikn svaret med di eiga utrekning tysdag.

På same måte, finn P(Z = z) for z = 1, 2, 3, 4, og samanlikn med di eiga utrekning.

Oppgåve 5.31 Lat Z B(4,0,1). Me skal visualisera sannsynsfordelinga for Z i Matlab.

Fyrst, merk at me kan bruk pdf på ein vektor eller matrise. Køyr fylgjande i Matlab

1  zv = 0:4 
2  pv = pdf(’binom’,zv,4,0.1)
Vektoren zv er utfallsrommet. Den andre lina reknar ut P(Z = z) for z = 0, 1, 2, 3, 4 og returnerer ein vektor.

No kan me plotta fordelinga

1  bar(zv,pv) 
2  figure 
3  plot(zv,pv)
I den midterste lina opnar figure eit nytt figurvindauga slik at du kan sjå begge plotta ved sidan av kvarandre.

Oppgåve 5.32 Bruk teknikken over og plott den teoretiske fordeling for talet på bitfeil når du sender n = 10 bits over BSC(p) for p = 0,01,0,05,0,1. Samanlikn plottet med histogramma du fekk i oppgåve 5.26. Kva ser du?

The cummulative distribution function (CDF) The pdf function (for a discrete distribution) gives you the probability P(X = x). Another important function is cdf (Cummulative Distribution Function) which gives the probability P(X x).

Oppgåve 5.33 Suppose you send a word of 1000 bits over a BSC bit bit error probability p = 0.02. What is the probability of getting at most ...

1.
2% bit errors?
2.
5% bit errors?

(Use matlab to find the answer.)