Die Grafik zeigt vier Symbolfolgen $\langle q_\nu \rangle $mit jeweilger Länge $N = 60$. Die Quellensymbole sind jeweils $\rm A$ und $\rm B$. Daraus folgt direkt, dass für den Entscheidungsgehalt aller betrachteten Quellen $H_0 = 1 \; \rm bit/Symbol$ gilt. Die Symbole $\rm A$ und $\rm B$ treten jedoch nicht gleichwahrscheinlich auf, sondern mit den Wahrscheinlichkeiten $p_{\rm A}$ und $p_{\rm B}$.
The graphic on the right shows four symbol sequences $\langle q_\nu \rangle $, each with length $N = 60$. The source symbols are $\rm A$ and $\rm B$.
*It follows directly that $H_0 = 1 \; \rm bit/symbol$ applies to the decision content of all sources considered.
*However, the symbols $\rm A$ and $\rm B$ do not occur with equal probability, but with the probabilities $p_{\rm A}$ and $p_{\rm B}$.
Die folgende Tabelle zeigt neben $H_0$ noch die Entropienäherungen
* $H_1$, basierend auf $p_{\rm A}$ und $p_{\rm B}$ (Spalte 2),
* $H_2$, basierend auf Zweiertupel (Spalte 3),
* $H_3$, basierend auf Dreiertupel (Spalte 4),
* $H_4$, basierend auf Vierertupel (Spalte 5),
* die tatsächliche Entropie $H$, die sich aus $H_k$ durch den Grenzübergang für $k \to \infty$ ergibt (letzte Spalte).
In addition to $H_0$ , the table below shows the entropy approximations
* the actual entropy $H$, which is obtained from $H_k$ by the boundary transition for $k \to \infty$ (last column).
Zwischen diesen Entropien bestehen folgende Größenrelationen: $H \le$ ... $\le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$
*Nicht bekannt ist die Zuordnung zwischen den Quellen '''Q1''', '''Q2''', '''Q3''', '''Q4''' und den in der Grafik gezeigten gezeigten Symbolfolgen (Schwarz, Blau, Rot, Grün).
The following size relations exist between these entropies: $H \le$ ... $\le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$
*Es ist lediglich bekannt, dass die Quelle '''Q4''' einen Wiederholungscode beinhaltet. Aufgrund der Tatsache, dass bei der entsprechenden Symbolfolge jedes zweite Symbol keinerlei Information lierfert, ist $H_0 = 0.5 \; \rm bit/Symbol$. Zudem sind die Entropienäherungen $H_1 = 1 \; \rm bit/Symbol$ (gleichwahrscheinliche Symbole) und $H_4 \approx 0.789 \; \rm bit/Symbol$ gegeben
Zu bestimmen sind für diese Nachrichtenquelle schließlich noch die Entropienäherungen $H_2$ und $H_3$.
*What is not known is the correlation between the sources $\rm Q1$, $\rm Q2$, $\rm Q3$, $\rm Q4$ and the symbol sequences shown in the graph <br>(black, blue, red, green).
*It is only known that source $\rm Q4$ contains a repetition code. Due to the fact that in the corresponding symbol sequence every second symbol does not lier any information, the final entrpy value is $H = 0.5 \; \rm bit/symbol$.
*In addition, the entropy approximations $H_1 = 1 \; \rm bit/symbol$ and $H_4 \approx 0.789 \; \rm bit/symbol$ are given.
[[File:Inf_A_1_3b_vers2.png|Quellenentropie und Näherungen in „bit/Symbol”]]
Finally, the entropy approximations $H_2$ and $H_3$ are to be determined for the source $\rm Q4$ .
''Hinweise:''
[[File:EN_Inf_A_1_3b_v2.png|left|frame|Source entropy and approximations in "bit/symbol"]]
*Die Aufgabe gehört zum Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
<br clear=all>
''Hints:''
*Für die $k$–te Entropienäherung gilt bei Binärquellen ($M = 2$) mit der Verbundwahrscheinlichkeit $ p_i^{(k)}$ eines $k$–Tupels:
*This task belongs to the chapter [[Information_Theory/Discrete_Sources_with_Memory|Discrete Sources with Memory]].
*For the $k$–th entropy approximation, the following holds for binary sources $(M = 2)$ with the composite probability $ p_i^{(k)}$ of a $k$–tuple:
{Von welcher Quelle stammt die schwarze Symbolfolge?
{What is the source of the <u>black symbol sequence</u>?
|type="[]"}
|type="()"}
- Q1,
- $\rm Q1$,
- Q2,
- $\rm Q2$,
+ Q3,
+ $\rm Q3$,
- Q4.
- $\rm Q4$.
{Von welcher Quelle stammt die blaue Symbolfolge?
{What is the source of the <u>blue symbol sequence</u>?
|type="[]"}
|type="()"}
+ Q1,
+ $\rm Q1$,
- Q2,
- $\rm Q2$,
- Q3,
- $\rm Q3$,
- Q4.
- $\rm Q4$.
{Von welcher Quelle stammt die rote Symbolfolge?
{What is the source of the <u>red symbol sequence</u>?
|type="[]"}
|type="()"}
- Q1,
- $\rm Q1$,
+ Q2,
+ $\rm Q2$,
- Q3,
- $\rm Q3$,
- Q4.
- $\rm Q4$.
{Berechnen Sie die Entropienäherung $H_2$ des Wiederholungscodes '''Q4'''.
{Calculate the entropy approximation $H_2$ of the repetition code $\rm Q4$.
|type="{}"}
|type="{}"}
$H_2 \ = $ { 0.906 3% } $\ \rm bit/Symbol$
$H_2 \ = \ $ { 0.906 3% } $\ \rm bit/symbol$
{Berechnen Sie die Entropienäherung $H_3$ des Wiederholungscodes '''Q4'''.
{Calculate the entropy approximation $H_3$ of the repetition code $\rm Q4$.
|type="{}"}
|type="{}"}
$H_3 \ = $ { 0.833 3% } $\ \rm bit/Symbol$
$H_3 \ = \ $ { 0.833 3% } $\ \rm bit/symbol$
Line 72:
Line 74:
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)''' Die schwarze Binärfolge stammt von der <u>Quelle '''Q3'''</u>, da die Symbole gleichwahrscheinlich sind ⇒ $H_1 = H_0$ und keine statistischen Bindungen zwischen den Symbolen bestehen ⇒ $H=$ .... $= H_2 = H_1$.
'''(1)''' The black binary sequence comes from the source $\underline{\rm Q3}$,
*since the symbols are equally probable ⇒ $H_1 = H_0$, and
*there are no statistical bindings between the symbols ⇒ $H=$ ... $= H_2 = H_1$.
'''(2)''' Man erkennt bei der blauen Binärfolge, dass $\rm A$ sehr viel häufiger auftritt als $\rm B$, so dass $H_1 < H_0$ gelten muss. Entsprechend der Tabelle erfüllt nur die <u>Quelle '''Q1'''</u> diese Bedingung. Aus $H_1 = 0.5 \; \rm bit/Symbol$ kann man die Symbolwahrscheinlichkeiten $p_{\rm A} = 0.89$ und $p_{\rm B} = 0.11$ ermitteln.
'''(2)''' It can be seen in the blue binary sequence that $\rm A$ occurs much more frequently than $\rm B$, so that $H_1 < H_0$ must hold.
*According to the table, only source $\underline{\rm Q1}$ fulfils this condition.
*From $H_1 = 0.5 \; \rm bit/symbol$ one can determine the symbol probabilities $p_{\rm A} = 0.89$ and $p_{\rm B} = 0.11$ .
'''(3)''' Durch Ausschlussverfahren kommt man für die rote Binärfolge zum <u>Quelle '''Q2'''</u>: Die Quelle '''Q1''' gehört nämlich zur blauen Folge, '''Q3''' zur schwarzen und '''Q4''' zum Wiederholungscode und damit offensichtlich zur grünen Symbolfolge. Die rote Symbolfolge weist folgende Eigenschaften auf:
* Wegen $H_1 = H_0$ sind die Symbole gleichwahrscheinlich: $p_{\rm A} = p_{\rm B} = 0.5$.
* Wegen $H < H_1$ bestehen statistische Bindungen innerhalb der Folge. Diese erkennt man daran, dass es zwischen $\rm A$ und $\rm B$ mehr Übergänge als bei statistischer Unabhängigkeit gibt.
'''(4)''' Bei der grünen Symbolfolge (Quelle '''Q4''') sind die Symbole $\rm A$ und $\rm B$ gleichwahrscheinlich:
'''(3)''' By exclusion procedure one arrives at the result $\underline{\rm Q2}$ for the red binary sequence:
[[File:P_ID2247__Inf_A_1_3d.png|right|Symbolfolgen eines binären Wiederholungscodes]]
*The source $\rm Q1$ belongs to the blue sequence, $\rm Q3$ to the black and $\rm Q4$ to the repetition code and thus obviously to the green symbol sequence.
*The red symbol sequence has the following properties:
\hspace{0.05cm}.$$
:* Because of $H_1 = H_0$ , the symbols are equally probable: $p_{\rm A} = p_{\rm B} = 0.5$.
Zur $H_2$-Ermittlung betrachtet man Zweiertupel. Die Verbundwahrscheinlichkeiten $p_{\rm AA}$, $p_{\rm AB}$, $p_{\rm PA}$ und $p_{\rm BB}$ können daraus berechnet werden. Aus der Skizze erkennt man:
:* Because of $H < H_1$, there are statistical bindings within the sequence.
* Die Kombinationen $\rm AB$ und $\rm BA$ sind nur dann möglich, wenn ein Tupel bei geradzahligem $\nu$ beginnt. Für die Verbundwahrscheinlichkeiten $p_{\rm AB}$ und $p_{\rm BA}$ gilt dann:
*This can be recognised by the fact that there are more transitions between $\rm A$ and $\rm B$ than with statistical independence.
'''(4)''' In the green symbol sequence $($source $\rm Q4)$ , the symbols $\rm A$ and $\rm B$ are equally likely:
und daraus zur Entropienäherung
[[File:P_ID2247__Inf_A_1_3d.png|right|frame|Symbol sequences of a binary repetition code]]
To determine $H_2$, one considers two-tuples. The composite probabilities $p_{\rm AA}$, $p_{\rm AB}$, $p_{\rm BA}$ and $p_{\rm BB}$ can be calculated from this. You can see from the sketch:
\hspace{0.05cm}.$$
* The combinations $\rm AB$ and $\rm BA$ are only possible if a tuple starts at even $\nu$ . For the composite probabilities $p_{\rm AB}$ and $p_{\rm BA}$ then holds:
Zur Berechnung von$H_4$ ergeben sich folgende $16$ Wahrscheinlichkeiten:
*Even the approximation $H_4 = 0.789\,{\rm bit/Symbol}$ still deviates significantly from the final entropy value $H = 0.5\,{\rm bit/symbol}$ .
*The repetition code obviously cannot be modelled by a Markov source. If $\rm Q4$ were a Markov source, then the following would have to apply:
Man erkennt: Auch die Näherung $H_4 = 0.789\,{\rm bit/Symbol}$ weicht noch weit vom Entropie-Endwert $H = 0.5\,{\rm bit/Symbol}$ ab.
''Hinweis:'' Der Wiederholungscode kann offensichtlich nicht durch eine Markovquelle modelliert werden. Wäre '''Q4''' eine Markovquelle, so müsste nämlich gelten:
The graphic on the right shows four symbol sequences $\langle q_\nu \rangle $, each with length $N = 60$. The source symbols are $\rm A$ and $\rm B$.
It follows directly that $H_0 = 1 \; \rm bit/symbol$ applies to the decision content of all sources considered.
However, the symbols $\rm A$ and $\rm B$ do not occur with equal probability, but with the probabilities $p_{\rm A}$ and $p_{\rm B}$.
In addition to $H_0$ , the table below shows the entropy approximations
$H_1$, based on $p_{\rm A}$ und $p_{\rm B}$ (column 2),
$H_2$, based on two-tuples (column 3),
$H_3$, based on three-tuples (column 4),
$H_4$, based on four-tuples (column 5),
the actual entropy $H$, which is obtained from $H_k$ by the boundary transition for $k \to \infty$ (last column).
The following size relations exist between these entropies: $H \le$ ... $\le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$
What is not known is the correlation between the sources $\rm Q1$, $\rm Q2$, $\rm Q3$, $\rm Q4$ and the symbol sequences shown in the graph (black, blue, red, green).
It is only known that source $\rm Q4$ contains a repetition code. Due to the fact that in the corresponding symbol sequence every second symbol does not lier any information, the final entrpy value is $H = 0.5 \; \rm bit/symbol$.
In addition, the entropy approximations $H_1 = 1 \; \rm bit/symbol$ and $H_4 \approx 0.789 \; \rm bit/symbol$ are given.
Finally, the entropy approximations $H_2$ and $H_3$ are to be determined for the source $\rm Q4$ .
(1) The black binary sequence comes from the source $\underline{\rm Q3}$,
since the symbols are equally probable ⇒ $H_1 = H_0$, and
there are no statistical bindings between the symbols ⇒ $H=$ ... $= H_2 = H_1$.
(2) It can be seen in the blue binary sequence that $\rm A$ occurs much more frequently than $\rm B$, so that $H_1 < H_0$ must hold.
According to the table, only source $\underline{\rm Q1}$ fulfils this condition.
From $H_1 = 0.5 \; \rm bit/symbol$ one can determine the symbol probabilities $p_{\rm A} = 0.89$ and $p_{\rm B} = 0.11$ .
(3) By exclusion procedure one arrives at the result $\underline{\rm Q2}$ for the red binary sequence:
The source $\rm Q1$ belongs to the blue sequence, $\rm Q3$ to the black and $\rm Q4$ to the repetition code and thus obviously to the green symbol sequence.
The red symbol sequence has the following properties:
Because of $H_1 = H_0$ , the symbols are equally probable: $p_{\rm A} = p_{\rm B} = 0.5$.
Because of $H < H_1$, there are statistical bindings within the sequence.
This can be recognised by the fact that there are more transitions between $\rm A$ and $\rm B$ than with statistical independence.
(4) In the green symbol sequence $($source $\rm Q4)$ , the symbols $\rm A$ and $\rm B$ are equally likely:
To determine $H_2$, one considers two-tuples. The composite probabilities $p_{\rm AA}$, $p_{\rm AB}$, $p_{\rm BA}$ and $p_{\rm BB}$ can be calculated from this. You can see from the sketch:
The combinations $\rm AB$ and $\rm BA$ are only possible if a tuple starts at even $\nu$ . For the composite probabilities $p_{\rm AB}$ and $p_{\rm BA}$ then holds:
