Aufgaben:Aufgabe 3.6: Zustandsübergangsdiagramm: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(8 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Codebeschreibung mit Zustands– und Trellisdiagramm}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Codebeschreibung mit Zustands– und Trellisdiagramm}}
  
[[Datei:P_ID2648__KC_A_3_6.png|right|frame|Einfacher Rate–1/2–Faltungscodierer]]
+
[[Datei:P_ID2648__KC_A_3_6.png|right|frame|Einfache Realisierung eines Rate–$1/2$–Faltungscodierers]]
Eine Beschreibungsmöglichkeit für Faltungscodierer bietet das so genannte <i>Zustandsübergangsdiagramm</i>- Beinhaltet der Coder $m$ Speicherregister &#8658; Einflusslänge $\nu = m + 1$, so gibt es nach der aktuellen Speicherbelegung verschiedene Zustände $S_{\mu}$ mit $0 &#8804; \mu &#8804; 2^m \, &ndash;1$, wobei für den Index gilt:
+
Eine Beschreibungsmöglichkeit für Faltungscodierer bietet das so genannte <i>Zustandsübergangsdiagramm</i>. Beinhaltet der Coder&nbsp; $m$&nbsp; Speicherregister &nbsp; &#8658; &nbsp; Einflusslänge&nbsp; $\nu = m + 1$, so gibt es nach der aktuellen Speicherbelegung verschiedene Zustände&nbsp; $S_{\mu}$ mit $0 &#8804; \mu &#8804; 2^m -1$, wobei für den Index gilt:
 
:$$\mu = \sum_{l = 1}^{m} \hspace{0.1cm}2^{l-1} \cdot u_{i-l}
 
:$$\mu = \sum_{l = 1}^{m} \hspace{0.1cm}2^{l-1} \cdot u_{i-l}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Diese Art der Coderbeschreibung soll auf den oben skizzierten Faltungscodierer der Rate $R = 1/2$ angewendet werden.
+
Diese Art der Coderbeschreibung soll auf den oben skizzierten Faltungscodierer der Rate&nbsp; $R = 1/2$&nbsp; angewendet werden.
  
''Hinweis:''
+
 
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm| Codebeschreibung mit Zustands&ndash; und Trellisdiagramm]].
+
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm| Codebeschreibung mit Zustands&ndash; und Trellisdiagramm]].
 +
*Bezug genommen wird insbesondere auf den Abschnitt&nbsp; [[Kanalcodierung/Codebeschreibung_mit_Zustands–_und_Trellisdiagramm#Zustandsdefinition_f.C3.BCr_ein_Speicherregister|Zustandsdefinition für ein Speicherregister]].
  
  
Zeile 17: Zeile 25:
 
{Wieviele Zustände weist dieser Faltungscodierer auf?
 
{Wieviele Zustände weist dieser Faltungscodierer auf?
 
|type="{}"}
 
|type="{}"}
${\rm Anzahl \ der \ Zustände} \ = \ ${ 2 3% }
+
${\rm Anzahl \ der \ Zustände} \ = \ ${ 2 }
  
 
{Kommt man von jedem Zustand zu allen anderen Zuständen?
 
{Kommt man von jedem Zustand zu allen anderen Zuständen?
Zeile 24: Zeile 32:
 
- Nein.
 
- Nein.
  
{Welche Aussagen gelten für den Übergang von $s_i = S_1$ zu $s_{i+1} = S_0$?
+
{Welche Aussagen gelten für den Übergang von&nbsp; $s_i = S_1$&nbsp; nach&nbsp; $s_{i+1} = S_0$?
 
|type="[]"}
 
|type="[]"}
+ Das aktuelle Informationsbit muss $u_i = 0$ sein.
+
+ Das aktuelle Informationsbit muss&nbsp; $u_i = 0$&nbsp; sein.
- Das aktuelle Informationsbit muss $u_i = 1$ sein.
+
- Das aktuelle Informationsbit muss&nbsp; $u_i = 1$&nbsp; sein.
+ Die zugehörige Codesequenz lautet $\underline{x}_i = (01)$.
+
+ Die zugehörige Codesequenz lautet&nbsp; $\underline{x}_i = (01)$.
- Die zugehörige Codesequenz lautet $\underline{x}_i = (10)$.
+
- Die zugehörige Codesequenz lautet&nbsp; $\underline{x}_i = (10)$.
  
{Welche Aussagen gelten für den Übergang von $s_i = S_1$ zu $s_{i+1} = S_1$?
+
{Welche Aussagen gelten für den Übergang von&nbsp; $s_i = S_1$&nbsp; nach&nbsp; $s_{i+1} = S_1$?
 
|type="[]"}
 
|type="[]"}
- Das aktuelle Informationsbit muss $u_i = 0$ sein.
+
- Das aktuelle Informationsbit muss&nbsp; $u_i = 0$&nbsp; sein.
+ Das aktuelle Informationsbit muss $u_i = 1$ sein.
+
+ Das aktuelle Informationsbit muss&nbsp; $u_i = 1$&nbsp; sein.
- Die zugehörige Codesequenz lautet $\underline{x}_i = (01)$.
+
- Die zugehörige Codesequenz lautet&nbsp; $\underline{x}_i = (01)$.
+ Die zugehörige Codesequenz lautet $\underline{x}_i = (10)$.
+
+ Die zugehörige Codesequenz lautet&nbsp; $\underline{x}_i = (10)$.
  
 
{Welche Informationssequenzen sind möglich?
 
{Welche Informationssequenzen sind möglich?
 
|type="[]"}
 
|type="[]"}
+ $\underline{u} = (1, \, 1, \, 0, \, 0, \, 1 \, 1, \, ...)$,
+
+ $\underline{u} = (1, \, 1, \, 0, \, 0, \, 1 \, 1, \, \text{...}\hspace{0.05cm})$,
+ $\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, ...)$.
+
+ $\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, \text{...}\hspace{0.05cm})$.
  
 
{Welche Codesequenzen sind möglich?
 
{Welche Codesequenzen sind möglich?
 
|type="[]"}
 
|type="[]"}
+ $\underline{x} = (11, \, 10, \, 01, \, 00, \, 11, \, 10, \, ...)$,
+
+ $\underline{x} = (11, \, 10, \, 01, \, 00, \, 11, \, 10, \, \text{...}\hspace{0.05cm})$,
- $\underline{x} = (11, \, 00, \, 10, \, 01, \, 11, \, 00, \, ...)$.
+
- $\underline{x} = (11, \, 00, \, 10, \, 01, \, 11, \, 00, \, \text{...}\hspace{0.05cm})$.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; [[Datei:P_ID2649__KC_A_3_6a_neu.png|right|frame|Ersatzschaltbild des betrachteten Coders]] Wie aus dem nebenstehenden Ersatzschaltbild hervorgeht, beinhaltet der Codierer nur ein Speicherelement &#8658; Gedächtnis $m = 1$. Damit gibt es $2^m \ \underline{= 2}$ Zustände, nämlich
+
[[Datei:P_ID2649__KC_A_3_6a_neu.png|right|frame|Ersatzschaltbild des betrachteten Codierers]]  
 +
'''(1)'''&nbsp; Wie aus dem nebenstehenden Ersatzschaltbild hervorgeht, beinhaltet der Codierer nur ein Speicherelement &nbsp; <br>&#8658; &nbsp; Gedächtnis $m = 1$. Damit gibt es $2^m \ \underline{= 2}$ Zustände, nämlich
 
* den Zustand $S_0 \ \Rightarrow \ u_{i&ndash;1} = 0$,
 
* den Zustand $S_0 \ \Rightarrow \ u_{i&ndash;1} = 0$,
 
* den Zustand $S_1 \ \Rightarrow \ u_{i&ndash;1} = 1$.
 
* den Zustand $S_1 \ \Rightarrow \ u_{i&ndash;1} = 1$.
  
  
'''(2)'''&nbsp; Von jedem Zustand gehen $2^k = 2$ Pfeile zu verschiedenene Zuständen ab. Da es nur zwei Zustände gibt, ist die Antwort <u>JA</u> richtig.
+
 
 +
'''(2)'''&nbsp; Von jedem Zustand gehen $2^k = 2$ Pfeile zu verschiedenenen Zuständen ab.  
 +
*Da es nur zwei Zustände gibt, ist die Antwort <u>JA</u> richtig.
  
  
'''(3)'''&nbsp; Das zum Zeitpunkt $i$ anliegende Informationsbit $u_i$ ist hinsichtlich des darauf folgenden Zeitpunkts $(j = i + 1)$ das vorherige Bit $(u_{j&ndash;1})$. Damit gilt $s_{i+1} = u_i$. Nur mit $u_i = 0$ kommt man von $s_i = S_1$ nach $s_{i+1} = S_0$ &#8658; <u>Lösungsvorschlag 1</u>.
 
  
Aus $s_i = S_1$ &#8658; $u_{i&ndash;1} = 1$ folgt weiter:
+
'''(3)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 3</u>:
 +
*Das zum Zeitpunkt $i$ anliegende Informationsbit $u_i$ ist hinsichtlich des darauf folgenden Zeitpunkts $(j = i + 1)$ das vorherige Bit $(u_{j&ndash;1})$.
 +
*Damit gilt $s_{i+1} = u_i$. Nur mit $u_i = 0$ kommt man von $s_i = S_1$ nach $s_{i+1} = S_0$ &nbsp; &#8658; &nbsp; <u>Lösungsvorschlag 1</u>.
 +
*Aus $s_i = S_1$ &#8658; $u_{i&ndash;1} = 1$ folgt weiter &nbsp; &#8658; &nbsp; <u>Lösungsvorschlag 3</u>:
 
:$${x}_i^{(1)} = u_i = 0\hspace{0.05cm},\hspace{0.2cm}{x}_i^{(2)} = u_i + u_{i-1}= 0+1 = 1   
 
:$${x}_i^{(1)} = u_i = 0\hspace{0.05cm},\hspace{0.2cm}{x}_i^{(2)} = u_i + u_{i-1}= 0+1 = 1   
 
\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\underline{x}_i = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm})
 
\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\underline{x}_i = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm})
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
 
+
*Den Lösungsvorschlag 4 hätte man von Anfang an ausschließen können. Die Grafik auf dem Angabenblatt zeigt eindeutig, dass der Coder systematisch ist: $x_i^{(1)} = u_i$. Die Kombination $u_i = 0$ und $\underline{x}_i = (1, 0)$ würde dem widersprechen.
Richtig ist also zusätzlich noch der <u>Lösungsvorschlag 3</u>. Den Lösungsvorschlag 4 hätte man von Anfang an ausschließen können. Die Grafik auf dem Angabenblatt zeigt eindeutig, dass der Coder systematisch ist: $x_i^{(1)} = u_i$. Die Kombination $u_i = 0$ und $\underline{x}_i = (1, 0)$ würde dem widersprechen.
 
  
  
'''(4)'''&nbsp; Auf ähnlichem Lösungsweg wie in der Teilaufgabe (3) gelangt man zum Ergebnis, dass hier die <u>Lösungsvorschläge 2 und 4</u> zutreffen. Damit ergeben sich das folgende Zustandsübergangsdiagramm (links) und das daraus ableitbare Trellisdiagramm:
 
  
[[Datei:P_ID2650__KC_A_3_6d.png|center|frame|Zustand– und Trellisdiagramm]]
+
[[Datei:P_ID2650__KC_A_3_6d.png|right|frame|Zustands– und Trellisdiagramm für den betrachteten Codierer]]
 +
'''(4)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 2 und 4</u>:
 +
*Auf ähnlichem Lösungsweg wie in der Teilaufgabe '''(3)''' gelangt man zum Ergebnis, dass hier das  aktuelle Informationsbit $u_i = 1$ sein muss.
 +
*Die zugehörige Codesequenz lautet $\underline{x}_i = (10)$.
 +
*Damit ergeben sich das folgende Zustandsübergangsdiagramm (links) und das daraus ableitbare Trellisdiagramm:
 +
*Rote Pfeile kennzeichnen das Informationsbit $u_i = 0$, während bei blauen Pfeilen $u_i = 1$ anzusetzen ist.
  
Rote Pfeile kennzeichnen das Informationsbit $u_i = 0$, während bei blauen Pfeilen $u_i = 1$ anzusetzen ist.
 
  
  
Zeile 80: Zeile 95:
  
 
'''(6)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>. Ausgehend vom Zustand $S_0$ kommt man  
 
'''(6)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>. Ausgehend vom Zustand $S_0$ kommt man  
* mit $u_1 = 1$ zum Zustand $S_1$, Ausgabe $11$,
+
* mit $u_1 = 1$ zum Zustand $S_1$, Ausgabe &bdquo;$11$&rdquo;,
* mit $u_2 = 1$ zum Zustand $S_1$, Ausgabe $10$,
+
* mit $u_2 = 1$ zum Zustand $S_1$, Ausgabe &bdquo;$10$&rdquo;,
* mit $u_3 = 0$ zum Zustand $S_0$, Ausgabe $01$,
+
* mit $u_3 = 0$ zum Zustand $S_0$, Ausgabe &bdquo;$01$&rdquo;,
* mit $u_4 = 0$ zum Zustand $S_0$, Ausgabe $00$,
+
* mit $u_4 = 0$ zum Zustand $S_0$, Ausgabe &bdquo;$00$&rdquo;,
* mit $u_5 = 1$ zum Zustand $S_1$, Ausgabe $11$,
+
* mit $u_5 = 1$ zum Zustand $S_1$, Ausgabe &bdquo;$11$&rdquo;,
* mit $u_6 = 1$ zum Zustand $S_1$, Ausgabe $10$.
+
* mit $u_6 = 1$ zum Zustand $S_1$, Ausgabe &bdquo;$10$&rdquo;.
  
  
 
Dagegen ist die zweite Codesequenz nicht möglich:
 
Dagegen ist die zweite Codesequenz nicht möglich:
 
* Die Ausgabe &bdquo;$11$&rdquo; bedeutet, dass man bei $S_0$ gestartet ist und mit $u_1 = 1$ zum Zustand $S_1$ kommt.
 
* Die Ausgabe &bdquo;$11$&rdquo; bedeutet, dass man bei $S_0$ gestartet ist und mit $u_1 = 1$ zum Zustand $S_1$ kommt.
* Im Zustand $S_1$ sind dann aber nur die Ausgaben &bdquo;$01$&rdquo; und &bdquo;$10$&rdquo; möglich, nicht jedoch &bdquo;$00$&rdquo.
+
* Im Zustand $S_1$ sind dann aber nur die Ausgaben &bdquo;$01$&rdquo; und &bdquo;$10$&rdquo; möglich, nicht jedoch &bdquo;$00$&rdquo;.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^3.3 Codebeschreibung mit Zustands– und Trellisdiagramm^]]
+
[[Category:Aufgaben zu  Kanalcodierung|^3.3 Zustands– und Trellisdiagramm^]]

Aktuelle Version vom 7. Juni 2019, 14:09 Uhr

Einfache Realisierung eines Rate–$1/2$–Faltungscodierers

Eine Beschreibungsmöglichkeit für Faltungscodierer bietet das so genannte Zustandsübergangsdiagramm. Beinhaltet der Coder  $m$  Speicherregister   ⇒   Einflusslänge  $\nu = m + 1$, so gibt es nach der aktuellen Speicherbelegung verschiedene Zustände  $S_{\mu}$ mit $0 ≤ \mu ≤ 2^m -1$, wobei für den Index gilt:

$$\mu = \sum_{l = 1}^{m} \hspace{0.1cm}2^{l-1} \cdot u_{i-l} \hspace{0.05cm}.$$

Diese Art der Coderbeschreibung soll auf den oben skizzierten Faltungscodierer der Rate  $R = 1/2$  angewendet werden.





Hinweise:


Fragebogen

1

Wieviele Zustände weist dieser Faltungscodierer auf?

${\rm Anzahl \ der \ Zustände} \ = \ $

2

Kommt man von jedem Zustand zu allen anderen Zuständen?

Ja.
Nein.

3

Welche Aussagen gelten für den Übergang von  $s_i = S_1$  nach  $s_{i+1} = S_0$?

Das aktuelle Informationsbit muss  $u_i = 0$  sein.
Das aktuelle Informationsbit muss  $u_i = 1$  sein.
Die zugehörige Codesequenz lautet  $\underline{x}_i = (01)$.
Die zugehörige Codesequenz lautet  $\underline{x}_i = (10)$.

4

Welche Aussagen gelten für den Übergang von  $s_i = S_1$  nach  $s_{i+1} = S_1$?

Das aktuelle Informationsbit muss  $u_i = 0$  sein.
Das aktuelle Informationsbit muss  $u_i = 1$  sein.
Die zugehörige Codesequenz lautet  $\underline{x}_i = (01)$.
Die zugehörige Codesequenz lautet  $\underline{x}_i = (10)$.

5

Welche Informationssequenzen sind möglich?

$\underline{u} = (1, \, 1, \, 0, \, 0, \, 1 \, 1, \, \text{...}\hspace{0.05cm})$,
$\underline{u} = (1, \, 0, \, 1, \, 0, \, 1, \, 0, \, \text{...}\hspace{0.05cm})$.

6

Welche Codesequenzen sind möglich?

$\underline{x} = (11, \, 10, \, 01, \, 00, \, 11, \, 10, \, \text{...}\hspace{0.05cm})$,
$\underline{x} = (11, \, 00, \, 10, \, 01, \, 11, \, 00, \, \text{...}\hspace{0.05cm})$.


Musterlösung

Ersatzschaltbild des betrachteten Codierers

(1)  Wie aus dem nebenstehenden Ersatzschaltbild hervorgeht, beinhaltet der Codierer nur ein Speicherelement  
⇒   Gedächtnis $m = 1$. Damit gibt es $2^m \ \underline{= 2}$ Zustände, nämlich

  • den Zustand $S_0 \ \Rightarrow \ u_{i–1} = 0$,
  • den Zustand $S_1 \ \Rightarrow \ u_{i–1} = 1$.


(2)  Von jedem Zustand gehen $2^k = 2$ Pfeile zu verschiedenenen Zuständen ab.

  • Da es nur zwei Zustände gibt, ist die Antwort JA richtig.


(3)  Richtig sind die Lösungsvorschläge 1 und 3:

  • Das zum Zeitpunkt $i$ anliegende Informationsbit $u_i$ ist hinsichtlich des darauf folgenden Zeitpunkts $(j = i + 1)$ das vorherige Bit $(u_{j–1})$.
  • Damit gilt $s_{i+1} = u_i$. Nur mit $u_i = 0$ kommt man von $s_i = S_1$ nach $s_{i+1} = S_0$   ⇒   Lösungsvorschlag 1.
  • Aus $s_i = S_1$ ⇒ $u_{i–1} = 1$ folgt weiter   ⇒   Lösungsvorschlag 3:
$${x}_i^{(1)} = u_i = 0\hspace{0.05cm},\hspace{0.2cm}{x}_i^{(2)} = u_i + u_{i-1}= 0+1 = 1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\underline{x}_i = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \hspace{0.05cm}. $$
  • Den Lösungsvorschlag 4 hätte man von Anfang an ausschließen können. Die Grafik auf dem Angabenblatt zeigt eindeutig, dass der Coder systematisch ist: $x_i^{(1)} = u_i$. Die Kombination $u_i = 0$ und $\underline{x}_i = (1, 0)$ würde dem widersprechen.


Zustands– und Trellisdiagramm für den betrachteten Codierer

(4)  Richtig sind die Lösungsvorschläge 2 und 4:

  • Auf ähnlichem Lösungsweg wie in der Teilaufgabe (3) gelangt man zum Ergebnis, dass hier das aktuelle Informationsbit $u_i = 1$ sein muss.
  • Die zugehörige Codesequenz lautet $\underline{x}_i = (10)$.
  • Damit ergeben sich das folgende Zustandsübergangsdiagramm (links) und das daraus ableitbare Trellisdiagramm:
  • Rote Pfeile kennzeichnen das Informationsbit $u_i = 0$, während bei blauen Pfeilen $u_i = 1$ anzusetzen ist.


(5)  Beide Lösungsvorschläge sind richtig. Für die Informationssequenzen gibt es (außer binär) keine weiteren Beschränkungen.


(6)  Richtig ist der Lösungsvorschlag 1. Ausgehend vom Zustand $S_0$ kommt man

  • mit $u_1 = 1$ zum Zustand $S_1$, Ausgabe „$11$”,
  • mit $u_2 = 1$ zum Zustand $S_1$, Ausgabe „$10$”,
  • mit $u_3 = 0$ zum Zustand $S_0$, Ausgabe „$01$”,
  • mit $u_4 = 0$ zum Zustand $S_0$, Ausgabe „$00$”,
  • mit $u_5 = 1$ zum Zustand $S_1$, Ausgabe „$11$”,
  • mit $u_6 = 1$ zum Zustand $S_1$, Ausgabe „$10$”.


Dagegen ist die zweite Codesequenz nicht möglich:

  • Die Ausgabe „$11$” bedeutet, dass man bei $S_0$ gestartet ist und mit $u_1 = 1$ zum Zustand $S_1$ kommt.
  • Im Zustand $S_1$ sind dann aber nur die Ausgaben „$01$” und „$10$” möglich, nicht jedoch „$00$”.