Statistikk og Simulering

Økt 5. Feilrettande kodar

Klasseromstimen

6.2. Klasseromstimen

6.2.1. Ein kommunikasjonsmodell eller to

pict


Figur 1: Communication system.

All digital kommunikasjon er offer for støy. Dvs. at det mottekne signalet ikkje er identisk med det sendte signalet. Kodeteori er løysinga på dette problemet. Ved å koda meldingane er det som regel råd å finna (estimera) den korrekte bodskapen, sjølv om der er feil i overføringa.

Figuren viser dette. Meldinga vert koda som kodeordet c før han vert sendt på kanalen. Det mottekne signalet r som kjem ut frå kanalen er sjelden identisk med c, men når me dekodar so får me eit estimat m̂ for den opprinnelege melding m. Det store spørsmålet, som me ofte treng statistikk for å svara på, kva er feilsannsynet P(mm̂)?

Definisjon 6 (Binary Symmetric Channel)

pict


Figur 2: The binary symmetric channel.

Mange kanalar vert modellert additivt. Dvs. at det mottekne signalet r er summen av det sendte signale s og ein feilvektor e.

Den binærsymmetriske kanalen (BSC), dvs. at s, r, og e er binære (vektorar over GF(2) = {0, 1}), og addisjon er modulo 2. På BSC er feilvektoren e generert tilfeldig, med uavhengige bits, der kvar bit X har sannsyn P(X = 1) = p for feil, og P(X = 0) = 1 p for korrekt overføring. Me skriv gjerne BSC(p) for ein binærsymmetrisk kanal med feilsannsyn p.

Figuren viser dette skjematisk. PRNG står for «Pseudo-Random Number Generator», dvs. slumptalsgenerator.

6.2.2. Matlab

Me skal simulera den binærsymmetriske kanalen BSC(p) i Matlab. Stort sett ser me på n-bits ord. Målet me simuleringa er å studera sannsynsfordelinga for ulike feilhendingar. Funksjonane som me skriv her kan gjenbrukast i meir kompliserte simuleringar seinare.

Oppgåve 6.1 Skriv ein funksjon (m-fil) som tekn ordlengda n, og returnerer eit tilfeldig meldingsord s. Meldingsorda skal vera uniformt fordelte.

Test funksjonen eit par gongar. Er resultata rimelege?

Oppgåve 6.2 Skriv ein funksjon (m-fil) som tekn ordlengda n og feilsannsynet p, og returnerer eit tilfeldig feilord e. Her skal kvar bit X ha sannsynsfordeling P(X = 1) = p og P(X = 0) = 1 p.

Test funksjonen eit par gongar. Er resultata rimelege?

Definisjon 7 (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.)

Oppgåve 6.3 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.

6.2.3. 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}.

Før me studerer sannsynsfordeling åt Z analytisk neste veke, skal me simulera observasjonar av Z for ulike verdiar av n. Slike simuleringar av stokastiske prosessar er kjent som Monte Carlo-simulering og er mykje brukt i fysikk og ingeniørfag.

Oppgåve 6.4 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 6.5 Skriv ein funksjon som tek tre argument, og gjer m simuleringar av eit n-bits ord på BSC(p). Returverdien skal vera ein array med m observasjonar av Z.

Oppgåve 6.6 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.

Funksjonen for å plotta eit histogram av ein diskret variabel i matlab er

1  histogram(z,’BinMethod’,’integers’) der z er ein array av alle observasjonane.

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

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

Oppgåve 6.9 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?