Difference between revisions of "Aufgaben:Exercise 3.7: Comparison of Two Convolutional Encoders"

From LNTwww
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Codebeschreibung mit Zustands– und Trellisdiagramm}}
+
{{quiz-Header|Buchseite=Channel_Coding/Code_Description_with_State_and_Trellis_Diagram}}
  
[[File:P_ID2672__KC_A_3_7.png|right|frame|Zwei Faltungscodierer mit den Parametern  $n = 2, \ k = 1, \ m = 2$]]
+
[[File:P_ID2672__KC_A_3_7.png|right|frame|Two convolutional encoders with parameters  $n = 2, \ k = 1, \ m = 2$]]
Die Grafik zeigt zwei Rate–$1/2$–Faltungscodierer, jeweils mit dem Gedächtnis  $m = 2$:
+
The graph shows two rate $1/2$ convolutional encoders, each with memory  $m = 2$:
* Der Coder  $\rm A$  weist die Übertragungsfunktionsmatrix $\mathbf{G}(D) = (1 + D^2, \ 1 + D + D^2)$ auf.
+
* The coder  $\rm A$  has the transfer function matrix $\mathbf{G}(D) = (1 + D^2, \ 1 + D + D^2)$.
* Beim Coder  $\rm B$  sind die beiden Filter (oben und unten) vertauscht, und es gilt : $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$.
+
* In the coder  $\rm B$  the two filters (top and bottom) are interchanged, and it holds : $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$.
  
  
Der untere Coder  $\rm B$  wurde im Theorieteil schon ausführlich behandelt.  
+
The lower encoder  $\rm B$  has already been treated in detail in the theory part.  
  
In der vorliegenden Aufgabe sollen Sie zunächst das Zustandsübergangsdiagramm für Coder  $\rm A$  ermitteln und anschließend die Unterschiede und die Gemeinsamkeiten zwischen den beiden Zustandsdiagrammen herausarbeiten.  
+
In the present exercise, you are to first determine the state transition diagram for coder  $\rm A$  and then work out the differences and the similarities between the two state diagrams.  
  
  
Line 17: Line 17:
  
  
''Hinweise:''
+
Hints:
* Die Aufgabe gehört zum Kapitel  [[Channel_Coding/Codebeschreibung_mit_Zustands%E2%80%93_und_Trellisdiagramm| Codebeschreibung mit Zustands– und Trellisdiagramm]].
+
*This exercise belongs to the chapter  [[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram| "Code description with state– and trellis diagram"]].
*Bezug genommen wird insbesondere auf die Abschnitte
+
*Reference is made in particular to the sections.
**  [[Channel_Coding/Codebeschreibung_mit_Zustands–_und_Trellisdiagramm#Zustandsdefinition_f.C3.BCr_ein_Speicherregister|Zustandsdefinition für ein Speicherregister]]  sowie
+
**  [[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram#State_definition_for_a_memory_register|"State definition for a memory register"]]  and.
**  [[Channel_Coding/Codebeschreibung_mit_Zustands–_und_Trellisdiagramm#Darstellung im_Zustands.C3.BCbergangsdiagramm|Darstellung im Zustandsübergangsdiagramm]].
+
**  [[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram#Representation_in_the_state_transition_diagram|"Representation in the state transition diagram"]].
  
  
===Fragebogen===
+
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
{Es gelte&nbsp; $\underline{u} = (0, \, 1, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$. Welche Sequenzen erzeugt Coder &nbsp;$\rm A$?
+
{&nbsp; $\underline{u} = (0, \, 1, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ holds. Which sequences does Coder &nbsp;$\rm A$ generate?
 
|type="[]"}
 
|type="[]"}
 
+ $\underline{x}^{(1)} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$,
 
+ $\underline{x}^{(1)} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, \text{...}\hspace{0.05cm})$,
Line 33: Line 33:
 
+ $\underline{x}^{(2)} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$.
 
+ $\underline{x}^{(2)} = (0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1, \, 1, \, \text{...}\hspace{0.05cm})$.
  
{Welche der genannten Zustandsübergänge gibt es bei Coder &nbsp;$\rm A$?
+
{Which of the above state transitions exist in encoder &nbsp;$\rm A$?
 
|type="[]"}
 
|type="[]"}
 
+ $s_i = S_0, \ u_i = 0 \ &#8658; \ s_{i+1} = S_0; \hspace{1cm} s_i = S_0, \ u_i = 1 \ &#8658; \ s_{i+1} = S_1$.
 
+ $s_i = S_0, \ u_i = 0 \ &#8658; \ s_{i+1} = S_0; \hspace{1cm} s_i = S_0, \ u_i = 1 \ &#8658; \ s_{i+1} = S_1$.
Line 40: Line 40:
 
+ $s_i = S_3, \ u_i = 0 \ &#8658; \ s_{i+1} = S_2; \hspace{1cm} s_i = S_3, \ u_i = 1 \ &#8658; \ s_{i+1} = S_3$.
 
+ $s_i = S_3, \ u_i = 0 \ &#8658; \ s_{i+1} = S_2; \hspace{1cm} s_i = S_3, \ u_i = 1 \ &#8658; \ s_{i+1} = S_3$.
  
{Wie unterscheiden sich die beiden Zustandsübergangsdiagramme?
+
{How do the two state transition diagrams differ?
 
|type="[]"}
 
|type="[]"}
- Es sind andere Zustandsübergänge möglich.
+
- Other state transitions are possible.
- Bei allen acht Übergängen stehen andere Codesequenzen.
+
- All eight transitions have different code sequences.
+ Unterschiede gibt es nur für die Codesequenzen&nbsp; $(01)$&nbsp; und&nbsp; $(10)$.
+
+ Differences exist only for the code sequences&nbsp; $(01)$&nbsp; and&nbsp; $(10)$.
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
  [[File:P_ID2673__KC_A_3_7a_neu.png|right|frame|Berechnung der Codesequenz]]  
+
  [[File:P_ID2673__KC_A_3_7a_neu.png|right|frame|Calculation of the code sequence]]  
'''(1)'''&nbsp; Die Berechnung basiert auf den Gleichungen
+
'''(1)'''&nbsp; The calculation is based on the equations.
 
:$$x_i^{(1)} = u_i + u_{i&ndash;2},$$
 
:$$x_i^{(1)} = u_i + u_{i&ndash;2},$$
 
:$$x_i^{(2)} = u_i + u_{i&ndash;1} + u_{i&ndash;2}.$$
 
:$$x_i^{(2)} = u_i + u_{i&ndash;1} + u_{i&ndash;2}.$$
*Zu Beginn sind die beiden Speicher ($u_{i&ndash;1}$ und $u_{i&ndash;2}$) mit Nullen vorbelegt &nbsp;&#8658;&nbsp; $s_1 = S_0$.  
+
*Initially, the two memories ($u_{i&ndash;1}$ and $u_{i&ndash;2}$) are preallocated with zeros &nbsp;&#8658;&nbsp; $s_1 = S_0$.  
*Mit $u_1 = 0$ ergibt sich $\underline{x}_1 = (00)$ und $s_2 = S_0$.  
+
*With $u_1 = 0$, we get $\underline{x}_1 = (00)$ and $s_2 = S_0$.  
*Mit $u_2 = 1$ erhält man die Ausgabe $\underline{x}_2 = (11)$ und den neuen Zustand $s_3 = S_3$.
+
*With $u_2 = 1$ one obtains the output $\underline{x}_2 = (11)$ and the new state $s_3 = S_3$.
  
  
Aus nebenstehendem Berechnungsschema erkennt man die Richtigkeit der <u>Lösungsvorschläge 1 und 4</u>.
+
From the adjacent calculation scheme one recognizes the correctness of the <u>proposed solutions 1 and 4</u>.
  
  
 
+
[[File:P_ID2674__KC_A_3_7b.png|right|frame|State transition diagram of encoder &nbsp;$\rm A$]]
[[File:P_ID2674__KC_A_3_7b.png|right|frame|Zustandsübergangsdiagramm von Coder &nbsp;$\rm A$]]
+
'''(2)'''&nbsp; <u>All proposed solutions</u> are correct:
'''(2)'''&nbsp; <u>Alle Lösungsvorschläge</u> sind richtig:
+
*This can be seen by evaluating the table at '''(1)'''.  
*Dies erkennt man durch Auswertung der Tabelle bei '''(1)'''.  
+
*The results are shown in the adjacent graph.
*Die Ergebnisse sind in nebenstehender Grafik dargestellt.
 
 
<br clear=all>
 
<br clear=all>
[[File:P_ID2675__KC_A_3_7c.png|right|frame|Zustandsübergangsdiagramm von Coder &nbsp;$\rm B$]]
+
[[File:P_ID2675__KC_A_3_7c.png|right|frame|State transition diagram of encoder &nbsp;$\rm B$]]
'''(3)'''&nbsp; Richtig ist nur die <u>Aussage 3</u>:  
+
'''(3)'''&nbsp; Correct is only <u>statement 3</u>:  
*Rechts ist das Zustandsübergangsdiagramm von Coder &nbsp;$\rm B$&nbsp; skizziert. Herleitung und Tnterpretation siehe Abschnitt [[Channel_Coding/Codebeschreibung_mit_Zustands–_und_Trellisdiagramm#Darstellung im_Zustands.C3.BCbergangsdiagramm|Darstellung im Zustandsübergangsdiagramm]].
+
*The state transition diagram of Coder &nbsp;$\rm B$&nbsp; is sketched on the right. For derivation and interpretation, see section [[Channel_Coding/Code_Description_with_State_and_Trellis_Diagram#Representation_in_the_state_transition_diagram|"Representation in the state transition diagram"]].
*Vertauscht man die beiden Ausgabebits $x_i^{(1)}$ und $x_i^{(2)}$, so kommt man vom Faltungscodierer &nbsp;$\rm A$&nbsp; zum Faltungscodierer&nbsp; $\rm B$&nbsp; (und umgekehrt).
+
*If we swap the two output bits $x_i^{(1)}$ and $x_i^{(2)}$, we get from the convolutional encoder &nbsp;$\rm A$&nbsp; to the convolutional encoder&nbsp; $\rm B$&nbsp; (and vice versa).
  
  

Revision as of 16:00, 3 October 2022

Two convolutional encoders with parameters  $n = 2, \ k = 1, \ m = 2$

The graph shows two rate $1/2$ convolutional encoders, each with memory  $m = 2$:

  • The coder  $\rm A$  has the transfer function matrix $\mathbf{G}(D) = (1 + D^2, \ 1 + D + D^2)$.
  • In the coder  $\rm B$  the two filters (top and bottom) are interchanged, and it holds : $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$.


The lower encoder  $\rm B$  has already been treated in detail in the theory part.

In the present exercise, you are to first determine the state transition diagram for coder  $\rm A$  and then work out the differences and the similarities between the two state diagrams.




Hints:


Questions

1

  $\underline{u} = (0, \, 1, \, 1, \, 1, \, 0, \, 1, \, 0, \, 0, \, \text{...}\hspace{0.05cm})$ holds. Which sequences does Coder  $\rm A$ generate?

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

2

Which of the above state transitions exist in encoder  $\rm A$?

$s_i = S_0, \ u_i = 0 \ ⇒ \ s_{i+1} = S_0; \hspace{1cm} s_i = S_0, \ u_i = 1 \ ⇒ \ s_{i+1} = S_1$.
$s_i = S_1, \ u_i = 0 \ ⇒ \ s_{i+1} = S_2; \hspace{1cm} s_i = S_1, \ u_i = 1 \ ⇒ \ s_{i+1} = S_3$.
$s_i = S_2, \ u_i = 0 \ ⇒ \ s_{i+1} = S_0; \hspace{1cm} s_i = S_2, \ u_i = 1 \ ⇒ \ s_{i+1} = S_1$.
$s_i = S_3, \ u_i = 0 \ ⇒ \ s_{i+1} = S_2; \hspace{1cm} s_i = S_3, \ u_i = 1 \ ⇒ \ s_{i+1} = S_3$.

3

How do the two state transition diagrams differ?

Other state transitions are possible.
All eight transitions have different code sequences.
Differences exist only for the code sequences  $(01)$  and  $(10)$.


Solution

Calculation of the code sequence

(1)  The calculation is based on the equations.

$$x_i^{(1)} = u_i + u_{i–2},$$
$$x_i^{(2)} = u_i + u_{i–1} + u_{i–2}.$$
  • Initially, the two memories ($u_{i–1}$ and $u_{i–2}$) are preallocated with zeros  ⇒  $s_1 = S_0$.
  • With $u_1 = 0$, we get $\underline{x}_1 = (00)$ and $s_2 = S_0$.
  • With $u_2 = 1$ one obtains the output $\underline{x}_2 = (11)$ and the new state $s_3 = S_3$.


From the adjacent calculation scheme one recognizes the correctness of the proposed solutions 1 and 4.


State transition diagram of encoder  $\rm A$

(2)  All proposed solutions are correct:

  • This can be seen by evaluating the table at (1).
  • The results are shown in the adjacent graph.


State transition diagram of encoder  $\rm B$

(3)  Correct is only statement 3:

  • The state transition diagram of Coder  $\rm B$  is sketched on the right. For derivation and interpretation, see section "Representation in the state transition diagram".
  • If we swap the two output bits $x_i^{(1)}$ and $x_i^{(2)}$, we get from the convolutional encoder  $\rm A$  to the convolutional encoder  $\rm B$  (and vice versa).