Aufgaben:Exercise 3.10Z: Maximum Likelihood Decoding of Convolutional Codes

• Return to book

Betrachtetes Systemmodell

Der Viterbi–Algorithmus stellt die bekannteste Realisierungsform für die Maximum–Likelihood–Decodierung eines Faltungscodes dar. Wir gehen hier von folgendem Modell aus:

• Die Informationssequenz $\underline{u}$ wird durch einen Faltungscode in die Codesequenz $\underline{x}$ umgesetzt. Es gelte $u_i ∈ \{0, \, 1\}$. Dagegen werden die Codesymbole bipolar dargestellt: $x_i ∈ \{–1, \, +1\}$.
• Der Kanal sei durch das BSC–Modell gegeben  ⇒  $y_i ∈ \{–1, \, +1\}$ oder es wird der AWGN–Kanal vorausgesetzt  ⇒  reellwertige $y_i$.
• Bei gegebener Empfangssequenz $\underline{y}$ entscheidet sich der Viterbi–Algorithmus für die Codesequenz $\underline{z}$ entsprechend

$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.$$

Dies entspricht dem Maximum–a–posteriori (MAP)–Kriterium. Sind die Informationssequenzen $\underline{u}$ gleichwahrscheinlich, so geht dieses in das etwas einfachere Maximum–Likelihood–Kriterium über:

$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{y} \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) \hspace{0.05cm}.$$

Als weiteres Ergebnis gibt der Viterbi–Algorithmus zusätzlich die Sequenz $\underline{\upsilon}$ als Schätzung für die Informationssequenz $\underline{u}$ aus.

In dieser Aufgabe soll der Zusammenhang zwischen der Hamming–Distanz $d_{\rm H}(\underline{x}, \, \underline{y})$ sowie der Euklidischen Distanz

$$d_{\rm E}(\underline{x} \hspace{0.05cm}, \hspace{0.1cm}\underline{y}) = \sqrt{\sum_{i=1}^{L} \hspace{0.2cm}(x_i - y_i)^2}\hspace{0.05cm}$$

ermittelt werden. Anschließend ist das obige ML–Kriterium mit

• der Hamming–Distanz $d_{\rm H}(\underline{x}, \, \underline{y})$,
• der Euklidischen Distanz $d_{\rm E}(\underline{x}, \, \underline{y})$, und
• dem Korrelationswert $〈 x \cdot y 〉$ zu formulieren.

Hinweise:

• Die Aufgabe bezieht sich auf die Theorieseite 6 des Kapitels .
• Zur Vereinfachung wird auf Tilden und Apostroph verzichtet.
• Weitere Informationen zu diesem Thema finden Sie auf folgenden Seiten dieses Buches:
  • MAP– und ML–Kriterium,
  • ML–Entscheidung beim BSC–Kanal,
  • ML–Entscheidung beim AWGN–Kanal,
  • Decodierung linearer Blockcodes – Seite 1.

Fragebogen

1

Wie hängen $d_{\rm H}(\underline{x}, \, \underline{y})$ und $d_{\rm E}(\underline{x}, \, \underline{y})$ beim BSC–Modell zusammen?

	Es gilt $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}(\underline{x}, \, \underline{y})$.
	Es gilt $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})$.
	Es gilt $d_{\rm H}(\underline{x}, \, \underline{y}) = d_{\rm E}^2(\underline{x}, \, \underline{y})/4$.

2

Welche der Gleichungen beschreiben die ML–Decodierung beim BSC–Modell? Die Minimierung/Maximierung bezieht sich jeweils auf alle $\underline{x} ∈ C$.

	$\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,
	$\underline{z} = \arg \min {d_{\rm E}(\underline{x}, \, \underline{y})}$,
	$\underline{z} = \arg \min {d_{\rm H}^2(\underline{x}, \, \underline{y})}$,

3

Welche Gleichung beschreibt die ML–Entscheidung beim BSC–Modell?

	$\underline{z} = \arg \min 〈 \underline{x} \cdot \underline{y} 〉$,
	$\underline{z} = \arg \max 〈 \underline{x} \cdot \underline{y} 〉$.

4

Welche Gleichungen gelten für die ML–Entscheidung beim AWGN?

	$\underline{z} = \arg \min {d_{\rm H}(\underline{x}, \, \underline{y})}$,
	$\underline{z} = \arg \min {d_{\rm E}(\underline{x}, \, \underline{y})}$,
	$\underline{z} = \arg \max 〈 \underline{x} \cdot \underline{y} 〉$.

Musterlösung

Solution

(1)  (2)  (3)  (4)  (5)