Aufgaben:Exercise 3.10: Metric Calculation

• Return to book

Only partially evaluated trellis

In the  "theory section"  of this chapter, the calculation of the branch metrics  ${\it \Gamma}_i(S_{\mu})$  has been discussed in detail, based on the Hamming distance  $d_{\rm H}(\underline{x}\hspace{0.05cm}', \ \underline{y}_i)$  between the possible codewords  $\underline{x}\hspace{0.05cm}' ∈ \{00, \, 01, \, 10, \, 11\}$  and the 2–bit–words  $\underline{y}_i$  received at time  $i$  is based.

The exercise deals exactly with this topic. In the adjacent graph

• the considered trellis is shown– valid for the code with rate  $R = 1/2$,  memory  $m = 2$  and  $\mathbf{G}(D) = (1 + D + D^2, \ 1 + D^2)$,
• are the received words  $\underline{y}_1 = (01), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ \underline{y}_7 = (11)$  indicated in the rectangles,
• are all branch metrics  ${\it \Gamma}_0(S_{\mu}), \hspace{0.05cm}\text{ ...} \hspace{0.05cm} , \ {\it \Gamma}_4(S_{\mu})$  already entered.

For example, the branch metric  ${\it \Gamma}_4(S_0)$  with  $\underline{y}_4 = (01)$  as the minimum of the two comparison values

• ${\it \Gamma}_3(S_0) + d_{\rm H}((00), \ (01)) = 3 + 1 = 4$, and
• ${\it \Gamma}_3(S_2) + d_{\rm H}((11), \ (01)) = 2 + 1 = 3$.

The surviving branch – here from  ${\it \Gamma}_3(S_2)$  to  ${\it \Gamma}_4(S_0)$  – is drawn solid, the eliminated branch from  ${\it \Gamma}_3(S_0)$  to  ${\it \Gamma}_4(S_0)$  dotted. Red arrows represent the information bit $u_i = 0$, blue arrows $u_i = 1$.

In the subtask (4) the relationship between

• the  ${\it \Gamma}_i(S_{\mu})$ minimization and
• the  ${\it \Lambda}_i(S_{\mu})$ maximization.

shall be worked out. Here, we refer to the nodes  ${\it \Lambda}_i(S_{\mu})$  as metrics, where the metric increment over the predecessor nodes results from the correlation value  $〈\underline{x}_i\hspace{0.05cm}', \, \underline{y}_i 〉$ . For more details on this topic, see the following theory pages:

• "Relationship between Hamming distance and correlation"
• "Viterbi algorithm based on correlation and metrics"
• "Viterbi decision for non–terminated convolutional codes".

Hints:

• The exercise refers to the chapter  "Decoding Convolutional Codes".
• For the time being, the search of surviving paths is not considered. This will be dealt with for the same example in the later  "Exercise 3.11".

Questions

1

Wie lauten die Fehlergrößen für den Zeitpunkt  $i = 5$?

${\it \Gamma}_5(S_0) \ = \ $

${\it \Gamma}_5(S_1) \ = \ $

${\it \Gamma}_5(S_2) \ = \ $

${\it \Gamma}_5(S_3) \ = \ $

2

Wie lauten die Fehlergrößen für den Zeitpunkt  $i = 6$?

${\it \Gamma}_6(S_0) \ = \ $

${\it \Gamma}_6(S_2) \ = \ $

3

Welcher Endwert ergibt sich bei diesem Trellis, basierend auf  ${\it \Gamma}_i(S_{\mu})$?

	Es gilt  ${\it \Gamma}_7(S_0) = 3$.
	Dieser Endwert lässt auf eine fehlerfreie Übertragung schließen.
	Dieser Endwert lässt auf drei Übertragungsfehler schließen.

4

Welche Aussagen sind für die  ${\it \Lambda}_i(S_{\mu})$–Auswertung zutreffend?

	Die Metriken  ${\it \Lambda}_i(S_{\mu})$  liefern gleiche Informationen wie  ${\it \Gamma}_i(S_{\mu})$.
	Für alle Knoten gilt  ${\it \Lambda}_i(S_{\mu}) = 2 \cdot \big [i \, –{\it \Gamma}_i(S_{\mu})\big ]$.
	Für die Metrikzuwächse gilt  $〈 \underline{x}_i', \, \underline{y}_i 〉 ∈ \{0, \, 1, \, 2\}$.

Musterlösung

Solution

(1)  Bei allen Knoten $S_{\mu}$ muss eine Entscheidung zwischen den beiden ankommenden Zweigen getroffen werden. Ausgewählt wird dann jeweils der Zweig, der zur (minimalen) Fehlergröße ${\it \Gamma}_5(S_{\mu})$ geführt hat. Mit $\underline{y}_5 = (01)$ erhält man:

$${\it \Gamma}_5(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$

$${\it \Gamma}_5(S_1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_0) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_2) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$

$${\it \Gamma}_5(S_2) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] = {\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 2+0 \right ] \hspace{0.15cm}\underline{= 2}\hspace{0.05cm},$$

$${\it \Gamma}_5(S_3) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{4}(S_1) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{4}(S_3) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+0\hspace{0.05cm},\hspace{0.05cm} 2+2 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$

Die linke Grafik zeigt das endgültig ausgewertete ${\it \Gamma}_i(S_{\mu})$–Trellis.

Ausgewertete Trellisdiagramme

(2)  Zum Zeitpunk $i = 6$ ist bereits die Terminierung wirksam und es gibt nur noch zwei Fehlergrößen. Für diese erhält man mit $\underline{y}_6 = (01)$:

$${\it \Gamma}_6(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{5}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{5}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+1\hspace{0.05cm},\hspace{0.05cm} 2+1 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm},$$

$${\it \Gamma}_6(S_2) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{5}(S_1) + d_{\rm H} \big ((10)\hspace{0.05cm},\hspace{0.05cm} (01) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{5}(S_3) + d_{\rm H} \big ((01)\hspace{0.05cm},\hspace{0.05cm} (01) \big ) \right ] ={\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 3+0 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$

(3)  Der Endwert ergibt sich zu

$${\it \Gamma}_7(S_0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}{\rm min} \left [{\it \Gamma}_{6}(S_0) + d_{\rm H} \big ((00)\hspace{0.05cm},\hspace{0.05cm} (11) \big )\hspace{0.05cm},\hspace{0.2cm}{\it \Gamma}_{6}(S_2) + d_{\rm H} \big ((11)\hspace{0.05cm},\hspace{0.05cm} (11) \big ) \right ] ={\rm min} \left [ 3+2\hspace{0.05cm},\hspace{0.05cm} 3+0 \right ] \hspace{0.15cm}\underline{= 3}\hspace{0.05cm}.$$

Beim BSC–Modell kann man aus ${\it \Gamma}_7(S_{\mu}) = 3$ darauf schließen, dass drei Übertragungsfehler aufgetreten sind   ⇒   Lösungsvorschläge 1 und 3.

(4)  Richtig sind die Aussagen 1 und 2:

• Die Maximierung der Metriken ${\it \Lambda}_i(S_{\mu})$ entsprechend der rechten Skizze in obiger Grafik liefert das gleiche Ergebnis wie die links dargestellte Minimierung der Fehlergrößen ${\it \Gamma}_i(S_{\mu})$. Auch die überlebenden und gestrichenen Zweige sind in beiden Grafiken identisch.
• Die angegebene Gleichung ist ebenfalls richtig, was hier nur am Beispiel $i = 7$ gezeigt wird:

$${\it \Lambda}_7(S_0)) = 2 \cdot \big [i - {\it \Gamma}_7(S_0) \big ] = 2 \cdot \big [7 - 3 \big ] \hspace{0.15cm}\underline{= 8}\hspace{0.05cm}.$$

• Die letzte Aussage ist falsch. Vielmehr gilt  $〈x_i', \, y_i〉 ∈ \{–2, \, 0, \, +2\}$.

Hinweis: In der Aufgabe 3.11 wird für das gleiche Beispiel die Pfadsuche demonstiert, wobei von den ${\it \Lambda}_i(S_{\mu})$–Metriken gemäß der rechten Grafik ausgegangen wird.