Statistikk og Simulering

Prosjekt 3

Veke 7. Simulering av kommunikasjonssystem

7.2. Veke 7. Simulering av kommunikasjonssystem

  7.2.1 Simulering av kommunikasjonssystemet
  Simuleringsresultat
  7.2.2 Feilrettande kodar
  7.2.3 Simulator med koding
  7.2.4 Diskusjon

pict

Figur 4: Coding system for simulation.

Figur 4 viser kommunikasjonssystemet som me skal simulera.

$\vec{m}$ er meldinga (klartekst) (m for message).
$\vec{c}$ er kodeordet (c for codeword) som vert sendt på kanalen. Det er lenger enn meldinga. Redundansen vert brukt til å korrigera for feil.
$\vec{r}$ er det mottekne ordet (r for received). Dersom kanalen er feilfri får me $\vec{r} = \vec{c}$ .
$\hat{\vec{m}}$ er den dekoda meldinga (hatten $ˆ$ tyder estimat). Dersom $\hat{\vec{m}} \neq \vec{m}$ har me ein dekodingsfeil.

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ølve.

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

Viktig. Me implementerer kvar boks i systemet som ein funksjon (m-fil). Kvar m-fil bør ikkje bruka globale variablar heller skriva utdata på skjermen anna enn ved feilsøking. Kommunikasjon med boksen (funksjonen) skjer ved inn- og utparametrar. Dette gjer at boksane kan brukast igjen i fleire simuleringar.

7.2.1. Simulering av kommunikasjonssystemet

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

Skriv ein funksjon (m-fil) som tek ordlengda $k$ som argument og returnerer eit tilfeldig meldingsord $\vec{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 16 (Den binærsymmetriske kanalen) Den binærsymmetriske kanalen med bitfeilsannsyn $p$ (BSC $(p)$ ) tek ein kodeord $\vec{c} = (c_{1}, c_{2}, \dots, c_{k})$ som input og returnerer eit motteke ord $\vec{r} = (r_{1}, r_{2}, \dots, r_{k})$ .

Kanalen lagar ein tilfeldig feilvektor $\vec{e} = (e_{1}, e_{2}, \dots, e_{k})$ ved å dra kvar bit $e_{i}$ uavhengig slik at $P (e_{i} = 1) = p$ og $P (e_{i} = 0) = 1 - p$ .

Det mottekne order er

\vec{r} = \vec{c} + \vec{e} mod 2 .

Oppgåve 7.2 (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 $\vec{e}$ . Lag gjerne ein eigen funksjon for det.
2.: Returner $\vec{r} = \vec{m} + \vec{e} mod 2$ .

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

Simuleringsresultat Kvar melding som me sender på kanalen er eitt forsøk. Oppgåva for Compare-boksen er å rekna ut det resultatet som me ynskjer å observera frå forsøket. Der er to vanlege alternativ:

Ordfeil: Eitt ord vert sendt i førsøket. Dersom $\vec{m} = \hat{\vec{m}}$ har me null ordfeil. Dersom $\vec{m} \neq \hat{\vec{m}}$ har me éin ordfeil.
Bitfeil: Ordet består av $k$ bits. Kvar bit ${\hat{m}}_{i}$ som er ulik den sendte biten $m_{i}$ gjev éin bitfeil. Talet på bitfeil er ofte eit interessant resultat.

Lat oss testa eit ukoda system før me innfører feilretting. Då har me

\begin{align} n & = k, & (21) \\ \vec{c} & = \vec{m}, & (22) \\ \hat{\vec{m}} & = \vec{r} . & (23) \end{align}

Definisjon 17 (Hamming-vekta) Hamming-vekta $w (\vec{x})$ på ein vektor $\vec{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.)

Merknad 7 Talet på bitfeil er hammigvekta $w (\hat{\vec{m}} - \vec{m})$ .

Oppgåve 7.3 Skriv ein Compare-funksjon som returnerer talet på ordfeil i simuleringa. Input må vera den sendte og den dekoda meldinga.

Oppgåve 7.4 Lag ein funksjon som testar det ukoda systemet $m$ gongar med ordlengd $k$ og returnerer talet på ordfeil. Test funksjonen med nokre ulike ordlengder $k$ . Bruk bitfeilsannsyn $p = 0,1$ . Ser det rimeleg ut?

Korleis utviklar ordefeiltalet seg når du aukar $k$ ?

Oppgåve 7.5 Skriv ein Compare-funksjon som returnerer talet på bitfeil i simuleringa. Input må vera den sendte og den dekoda meldinga.

Hint Du kan rekna ut feilordet fyrst, å bruka absoluttverdi og sum for å løysa problemet.

Oppgåve 7.6 Lag ein funksjon som testar det ukoda systemet $m$ gongar med ordlengd $k$ og registrerer talet på bitfeil.

Test funksjonen og plot bitfeiltala som histogram. Prøv nokre ulike ulike ordlengder $k$ og ulike bitfeilsannsyn $p$ .

7.2.2. Feilrettande kodar

pict

Figur 5: Channel with coding.

Feilrettande kodar vert brukt for å hindra kommunikasjonsfeil, som vist i figur 5. Vha. kodeteori er det mogleg å kommunisera påliteleg over svært dårlege kanalar; dvs. sjølv om bitfeilsannsynet $p$ er neste 50%, er det mogleg å få neglisjerbar ordfeilsannsyn. Prisen ein betaler er at svært få meldingsbits, krev mange bits på kanalen.

Her er to kodesystem som me kan testa:

[7, 4] Hamming-kode
- Kodar: hammingenc.m
- Dekodar: hammingdec.m
[31, 11] BCH-kode
- Kodar: bchenc.m
- Dekodar: bchdec.m

Parametrane åt kodane er $[n, k]$ , der $n$ er lengda på kodeordet (sendt på kanalen) og $k$ er lengda på meldinga. Hamming-koden over tek altso $4$ bits inn, og lagar eit 7-bits kodeord.

Oppgåve 7.7 Last ned kodaren og dekodaren for hammingkoden, og test dei i Matlab.

1.: Generer ei tilfeldig fire-bits melding $\vec{m}$ .
2.: Kod meldinga med hammingenc(m) og få kodeordet $\vec{c}$ . Korleis ser det ut?
3.: Dekod $\vec{c}$ slik at du får $\hat{\vec{m}}$ . Er $\hat{\vec{m}}$ lik $\vec{m}$ eller ikkje?
4.: Lag eit kodeord med éin bitfeil, og prøv å dekoda det: 1 c1 = mod(c + [0 0 0 1 0 0 0],2) 2 m1 = hammingdec(c1)Samanlikn resultatet med den opprinnelege melding $\vec{m}$ . Er det korrekt dekoda?

Begge testane i øvinga skal gje eit dekoda ord lik det opprinnelege ordet $\vec{m}$ . I det fyrste tilfellet har du ingen bitfeil på kanalen, og i det andre har du éin. Hammingkoden dekodar alltid korrekt når der er høgst éin bitfeil.

7.2.3. Simulator med koding

Ta fram att simulatoren frå forrige veke. I dag skal me utvida han med koding som i figur 5. Dvs. at me må leggja til koding mellom meldingsgeneratoren og kanalen, og dekoding mellom kanalen og samanlikninga. Dette skal me gjera to gongar; både med hammingkoden og BCH-koden.

Oppgåve 7.8 Skriv ein funksjon som simulerer $m$ forsøk med hammingkoden på BSC, og som tel antall bitfeil $X$ . Funksjonen må ta $p$ (bitfeilsannsynet) som innparameter og returnera ein observasjon av $X$ . (Hugs at meldinga alltid er $k = 4$ bits med hammingkoden.) Simuler $m = 100$ sendte meldingar med bitfeilsannsyn $π = 0,1$ og plot eit histogram for $X$ .

Oppgåve 7.9 Skriv liknande funksjonar, tilsvarande forrige oppgåve, for BCH-koden og for ordfeil. Totalt skal du ha fire systemsimulatorar:

1.: Bitfeil i Hamming-koden.
2.: Bitfeil i BCH-koden.
3.: Ordfeil i Hamming-koden.
4.: Ordfeil i BCH-koden.

Tenk gjennom API-et slik at du bruker parametrane konsistent i alle fire funksjonane.

Test gjerne alle fire funksjonane med ulike parametrar dersom du har tid. Det viktigste er derimot å ha dei fire systemsimulatorane klare, slik at me kan bruka dei til statistisk analyse neste veke.

7.2.4. Diskusjon

Fylgjande er ein alternativ, og svært vanleg, definisjon på BCH-kanalen.

Definisjon 18 (Den binærsymmetriske kanalen) Den binærsymmetriske kanalen med bitfeilsannsyn $p$ (BSC $(p)$ ) tek ein meldingsord $\vec{m} = (m_{1}, m_{2}, \dots . m_{n})$ som input og returnerer eit motteke ord $\vec{r} = (r_{1}, r_{2}, \dots, r_{n})$ , der kvar bit $r_{i}$ er lik $m_{i}$ med sannsyn $1 - p$ og ulik (feil) med sannsyn $1 - p$ . Kvar bit er uavhengig av alle foregåande bits.

Oppgåve 7.10 (Ekstra, Diskusjon) Er Definisjon 16 og 18 ekvivalent? Korleis kan du vera sikker?