Difference between revisions of "Aufgaben:Exercise 2.3: Algebraic Sum of Binary Numbers"

From LNTwww
Line 1: Line 1:
  
{{quiz-Header|Buchseite=Stochastische Signaltheorie/Binomialverteilung
+
{{quiz-Header|Buchseite=Theory_of_Stochastic_Signals/Binomial_Distribution
 
}}
 
}}
  
[[File:EN_Sto_A_2_3.png|right|frame|Betrachteter Zufallsgenerator]]
+
[[File:EN_Sto_A_2_3.png|right|frame|Considered random generator]]
Ein Zufallsgenerator gibt zu jedem Taktzeitpunkt  $(\nu)$  eine binäre Zufallszahl  $x_\nu$  ab,  die  $0$  oder  $1$  sein kann.  
+
A random number generator outputs a binary random number   $x_\nu$  at each clock time  $(\nu)$ , which can be  $0$  or  $1$ .
*Der Wert "1" tritt mit Wahrscheinlichkeit  $p = 0.25$  auf.  
+
*The value "1" occurs with probability  $p = 0.25$ .  
*Die einzelnen Werte   $x_\nu$  seien statistisch voneinander unabhängig.
+
*The individual values   $x_\nu$  are statistically independent of each other.
  
  
Die Binärzahlen werden in ein Schieberegister mit  $I = 6$  Speicherzellen abgelegt.  
+
The binary numbers are stored in a shift register withnbsp; $I = 6$  memory cells.
  
Zu jedem Taktzeitpunkt wird der Inhalt dieses Schieberegisters um eine Stelle nach rechts verschoben und jeweils die algebraische Summe  $y_\nu$  der Schieberegisterinhalte gebildet:
+
At each clock instant, the contents of this shift register are shifted one place to the right and the algebraic sum  $y_\nu$  of the shift register contents is formed in each case:
 
:$$y_{\nu}=\sum\limits_{i=0}^{5}x_{\nu-i}=x_{\nu}+x_{\nu-1}+\ \text{...} \ +x_{\nu-5}.$$
 
:$$y_{\nu}=\sum\limits_{i=0}^{5}x_{\nu-i}=x_{\nu}+x_{\nu-1}+\ \text{...} \ +x_{\nu-5}.$$
  
Line 20: Line 20:
  
  
''Hinweise:''
+
Hints:
*Die Aufgabe gehört zum  Kapitel  [[Theory_of_Stochastic_Signals/Binomialverteilung|Binomialverteilung]].
+
*The exercise belongs to the chapter  [[Theory_of_Stochastic_Signals/Binomial_Distribution|binomial distribution]].
 
   
 
   
*Zur Kontrolle Ihrer Ergebnisse können Sie das interaktive Applet  [[Applets:Binomial-_und_Poissonverteilung_(Applet)|Binomial– und Poissonverteilung]]  benutzen.
+
*To check your results you can use the interactive applet  [[Applets:Binomial-_und_Poissonverteilung_(Applet)|Binomial and Poisson distribution]] .
  
  
Line 29: Line 29:
  
  
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Werte kann die Summe&nbsp; $y$&nbsp; annehmen?&nbsp; Was ist der gr&ouml;&szlig;tm&ouml;gliche Wert?
+
{What values can the sum&nbsp; $y$&nbsp; take?&nbsp; What is the largest possible value?
 
|type="{}"}
 
|type="{}"}
 
$y_\max \ = \ $  { 6 3% }
 
$y_\max \ = \ $  { 6 3% }
  
  
{Berechnen Sie die Wahrscheinlichkeit, dass&nbsp; $y$&nbsp; gr&ouml;&szlig;er als&nbsp; $2$&nbsp; ist.
+
{Calculate the probability that&nbsp; $y$&nbsp; is greater than&nbsp; $2$&nbsp;.
 
|type="{}"}
 
|type="{}"}
 
${\rm Pr}(y > 2) \ = \ $ { 0.169 3% }
 
${\rm Pr}(y > 2) \ = \ $ { 0.169 3% }
  
  
{Wie gro&szlig; ist der Mittelwert der Zufallsgr&ouml;&szlig;e&nbsp; $y$&nbsp;?
+
{What is the mean value of the random variable&nbsp; $y$&nbsp;?
 
|type="{}"}
 
|type="{}"}
 
$m_y \ =$ { 1.5 3% }
 
$m_y \ =$ { 1.5 3% }
  
  
{Ermitteln Sie die Streuung der Zufallsgr&ouml;&szlig;e&nbsp; $y$.  
+
{Find the ***standard deviation*** of the random variable&nbsp; $y$.  
 
|type="{}"}
 
|type="{}"}
 
$\sigma_y \ = \ $ { 1.061 3% }
 
$\sigma_y \ = \ $ { 1.061 3% }
  
  
{Sind die Zufallszahlen&nbsp; $y_\nu$&nbsp; statistisch unabh&auml;ngig?&nbsp; Begr&uuml;nden Sie Ihr Ergebnis.
+
{Are the random numbers&nbsp; $y_\nu$&nbsp; statistically independent?&nbsp; Justify your result.
 
|type="[]"}
 
|type="[]"}
- Die Zufallszahlen sind statistisch unabh&auml;ngig.
+
- The random numbers are statistically independent.
+ Die Zufallszahlen sind statistisch abh&auml;ngig.
+
+ The random numbers are statistically dependent.
  
  
{Wie groß ist die bedingte Wahrscheinlichkeit, dass&nbsp; $y_\nu$&nbsp; wieder gleich&nbsp; $\mu$&nbsp; ist, wenn vorher&nbsp; $y_{\nu-1} = \mu$&nbsp; aufgetreten ist?&nbsp; $(\mu = 0, \ 1, \ \text{...} \ , \ I)$.
+
{What is the conditional probability that&nbsp; $y_\nu$&nbsp; equals&nbsp; $\mu$&nbsp; again if&nbsp; $y_{\nu-1} = \mu$&nbsp; occured previously?&nbsp; $(\mu = 0, \ 1, \ \text{...} \ , \ I)$.
 
|type="{}"}
 
|type="{}"}
 
${\rm Pr}(y_\nu = \mu \hspace{0.05cm} | \hspace{0.05cm} y_{\nu-1} = \mu ) \ = \ $ { 0.625 3% }
 
${\rm Pr}(y_\nu = \mu \hspace{0.05cm} | \hspace{0.05cm} y_{\nu-1} = \mu ) \ = \ $ { 0.625 3% }
Line 65: Line 65:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
 
'''(1)'''&nbsp; In jeder Zelle kann eine&nbsp; $0$&nbsp; oder eine&nbsp; $1$&nbsp; stehen.&nbsp; Deshalb kann die Summe alle ganzzahligen Werte zwischen&nbsp; $0$&nbsp; und&nbsp; $6$&nbsp; annehmen:
 
'''(1)'''&nbsp; In jeder Zelle kann eine&nbsp; $0$&nbsp; oder eine&nbsp; $1$&nbsp; stehen.&nbsp; Deshalb kann die Summe alle ganzzahligen Werte zwischen&nbsp; $0$&nbsp; und&nbsp; $6$&nbsp; annehmen:

Revision as of 14:03, 10 December 2021

Considered random generator

A random number generator outputs a binary random number   $x_\nu$  at each clock time  $(\nu)$ , which can be  $0$  or  $1$ .

  • The value "1" occurs with probability  $p = 0.25$ .
  • The individual values  $x_\nu$  are statistically independent of each other.


The binary numbers are stored in a shift register withnbsp; $I = 6$  memory cells.

At each clock instant, the contents of this shift register are shifted one place to the right and the algebraic sum  $y_\nu$  of the shift register contents is formed in each case:

$$y_{\nu}=\sum\limits_{i=0}^{5}x_{\nu-i}=x_{\nu}+x_{\nu-1}+\ \text{...} \ +x_{\nu-5}.$$




Hints:



Questions

1

What values can the sum  $y$  take?  What is the largest possible value?

$y_\max \ = \ $

2

Calculate the probability that  $y$  is greater than  $2$ .

${\rm Pr}(y > 2) \ = \ $

3

What is the mean value of the random variable  $y$ ?

$m_y \ =$

4

Find the ***standard deviation*** of the random variable  $y$.

$\sigma_y \ = \ $

5

Are the random numbers  $y_\nu$  statistically independent?  Justify your result.

The random numbers are statistically independent.
The random numbers are statistically dependent.

6

What is the conditional probability that  $y_\nu$  equals  $\mu$  again if  $y_{\nu-1} = \mu$  occured previously?  $(\mu = 0, \ 1, \ \text{...} \ , \ I)$.

${\rm Pr}(y_\nu = \mu \hspace{0.05cm} | \hspace{0.05cm} y_{\nu-1} = \mu ) \ = \ $


Solution

(1)  In jeder Zelle kann eine  $0$  oder eine  $1$  stehen.  Deshalb kann die Summe alle ganzzahligen Werte zwischen  $0$  und  $6$  annehmen:

$$y_{\nu}\in\{0,1,\ \text{...} \ ,6\}\hspace{0.3cm}\Rightarrow\hspace{0.3cm} y_{\rm max} \hspace{0.15cm} \underline{= 6}.$$


(2)  Es liegt eine Binomialverteilung vor.  Daher gilt mit  $p = 0.25$:

$${\rm Pr}(y =0)=(1-p)^{\it I}=0.75^6=0.178,$$
$${\rm Pr}(y=1)=\left({ I \atop {1}}\right)\cdot (1-p)^{I-1}\cdot p= \rm 6\cdot 0.75^5\cdot 0.25=0.356,$$
$${\rm Pr}(y=2)=\left({ I \atop { 2}}\right)\cdot (1-p)^{I-2}\cdot p^{\rm 2}= \rm 15\cdot 0.75^4\cdot 0.25^2=0.297,$$
$$\Rightarrow \hspace{0.3cm}{\rm Pr}(y>2)=1-{\rm Pr}(y=0)-{\rm Pr}( y=1)-{\rm Pr}( y=2)\hspace{0.15cm} \underline{=\rm 0.169}.$$


(3)  Nach der allgemeinen Gleichung gilt für den Mittelwert der Binomialverteilung:

$$m_y= I\cdot p\hspace{0.15cm} \underline{=\rm 1.5}.$$


(4)  Entsprechend gilt für die Streuung der Binomialverteilung:

$$\sigma_y=\sqrt{ I \cdot p \cdot( 1- p)} \hspace{0.15cm} \underline{= \rm 1.061}.$$


(5)  Richtig ist der Lösungsvorschlag 2:

  • Ist  $y_\nu = 0$, so können zum nächsten Zeitpunkt nur die Werte  $0$  und  $1$  folgen, nicht aber  $2$, ... , $6$.
  • Das heißt:   Die Folge  $ \langle y_\nu \rangle$  weist (starke) statistische Bindungen auf.


(6)  Die gesuchte Wahrscheinlichkeit ist identisch mit der Wahrscheinlichkeit dafür, dass das neue Binärsymbol gleich dem aus dem Schieberegister herausgefallenen Symbol ist. Daraus folgt:

$${\rm Pr} (y_{\nu} = \mu\hspace{0.05cm}| \hspace{0.05cm} y_{\nu-{1}} = \mu) = {\rm Pr}(x_{\nu}= x_{\nu-6}). $$
  • Da die Symbole  $x_\nu$  statistisch voneinander unabhängig sind, kann hierfür auch geschrieben werden:
$${\rm Pr}(x_{\nu} = x_{\nu-6}) = {\rm Pr}\big[(x_{\nu}= 1)\hspace{0.05cm}\cap\hspace{0.05cm}(x_{\nu-6}= 1)\hspace{0.05cm}\cup \hspace{0.05cm}(x_\nu=0)\hspace{0.05cm}\cap\hspace{0.05cm}(x_{\nu-6} =0)\big]= p^{2}+(1- p)^{2}=\rm 0.25^2 + 0.75^2\hspace{0.15cm} \underline{ = 0.625}. $$