Aufgaben:Exercise 3.11: Viterbi Receiver and Trellis Diagram - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:55:05Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:55, 16 March 2026
Line 91:		Line 91:

	[[Category:Digital Signal Transmission: Exercises\|^3.8 Viterbi Receiver^]]		[[Category:Digital Signal Transmission: Exercises\|^3.8 Viterbi Receiver^]]
	[[de:Aufgaben:3.~~11_Viterbi~~-~~Empfänger_und_Trellisdiagramm~~]]		[[de:Aufgaben:Aufgabe 3.11: Viterbi-Empfänger und Trellisdiagramm]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:30:44Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:30, 16 March 2026
Line 78:		Line 78:

	'''(3)'''  From the continuous paths at  $\nu = 5$  it can be seen:		'''(3)'''  From the continuous paths at  $\nu = 5$  it can be seen:
	:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}		:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}\hspace{0.05cm},\hspace{0.2cm} a_{4}\hspace{0.15cm}\underline {=0}\hspace{0.05cm},\hspace{0.2cm} a_{5}\hspace{0.15cm}\underline {=0} \hspace{0.05cm}.$$
	a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}
	\hspace{0.05cm},\hspace{0.2cm} a_{4}\hspace{0.15cm}\underline {=0}
	\hspace{0.05cm},\hspace{0.2cm} a_{5}\hspace{0.15cm}\underline {=0} \hspace{0.05cm}.$$

Maintenance script: Add German interlanguage link

2026-03-16T12:31:59Z

Add German interlanguage link

← Older revision		Revision as of 14:31, 16 March 2026
Line 94:		Line 94:

	[[Category:Digital Signal Transmission: Exercises\|^3.8 Viterbi Receiver^]]		[[Category:Digital Signal Transmission: Exercises\|^3.8 Viterbi Receiver^]]
			[[de:Aufgaben:3.11_Viterbi-Empfänger_und_Trellisdiagramm]]

Guenter at 13:00, 5 July 2022

2022-07-05T13:00:44Z

← Older revision		Revision as of 15:00, 5 July 2022
Line 25:		Line 25:
	* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:		* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:
	:$${\rm Pr} (a_\nu = 0) = {\rm Pr} (a_\nu = 1)= 0.5.$$		:$${\rm Pr} (a_\nu = 0) = {\rm Pr} (a_\nu = 1)= 0.5.$$
	* The topic is also covered with the interactive SWF applet  [[Applets:Viterbi\|"Properties of the Viterbi Receiver"]].

Guenter at 12:37, 4 July 2022

2022-07-04T12:37:04Z

← Older revision		Revision as of 14:37, 4 July 2022
Line 61:		Line 61:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  The <u>first two solutions</u> are correct:		'''(1)'''  The  <u>first two solutions</u>  are correct:
	*The signal $m(t)$ after the matched filter $H_{\rm MF}(f)$ has the largest possible signal-to-interference power ratio.		*The signal  $m(t)$  after the matched filter  $H_{\rm MF}(f)$  has the largest possible signal-to-interference power ratio  $\rm (SNR)$.
	* However, the noise components of the sequence $〈m_{\rm \nu}〉$ are (strongly) correlated due to the spectral shaping.		* However,  the noise components of the sequence  $〈m_{\rm \nu}〉$  are (strongly) correlated due to the spectral shaping.
	*The task of the discrete-time decorrelation filter with the frequency response $H_{\rm DF}(f)$ is to dissolve these ~~bonds~~, which is why the name "whitening filter" is also used for $H_{\rm DF}(f)$.		*The task of the discrete-time decorrelation filter with the frequency response  $H_{\rm DF}(f)$  is to dissolve these bindings,  which is why the name  "whitening filter"  is also used for  $H_{\rm DF}(f)$.
	*However, this is possible only at the cost of increased noise power   ⇒   consequently, the last proposed solution does not apply.		*However,  this is possible only at the cost of increased noise power   ⇒   consequently,  the last proposed solution does not apply.



	'''(2)'''  The two arrows arriving at $\underline {\nu = 1}$ are each drawn in blue and indicate the symbol $a_1 = 0$. Thus, the initial symbol $a_1$ is already fixed at this point. Similarly, the symbols $a_3 = 1$ and $a_5 = 0$ are already fixed at ~~the timesn~~ $\underline {\nu = 3}$ and $\underline {\nu = 5}$, respectively.		'''(2)'''  The two arrows arriving at   $\underline {\nu = 1}$  are each drawn in blue and indicate the symbol  $a_1 = 0$.  Thus,  the initial symbol  $a_1$  is already fixed at this point.  Similarly,  the symbols  $a_3 = 1$  and  $a_5 = 0$  are already fixed at times  $\underline {\nu = 3}$  and  $\underline {\nu = 5}$,  respectively.

	In contrast, at time $\nu = 2$, a decision regarding symbol $a_2$ is not possible.		In contrast,  at time $\nu = 2$,  a decision regarding symbol  $a_2$  is not possible.
	*Under the hypothesis that the following symbol $a_3 = 0$ would result in symbol $a_2 = 1$ (at "$0$" a red path arrives, thus coming from "$1$").		*Under the hypothesis that the following symbol  $a_3 = 0$  would result in symbol  $a_2 = 1$  $($at  "$0$"  a red path arrives,  thus coming from  "$1$"$)$.
	* In contrast, the hypothesis $a_3 = 1$ leads to the result $a_2 = 0$ (the path arriving at "$1$" is blue).		* In contrast,  the hypothesis  $a_3 = 1$  leads to the result  $a_2 = 0$  $($the path arriving at  "$1$"  is blue$)$.

			The situation is similar at time  $\nu = 4$.

	~~The situation is similar at time $\nu = 4$.~~

			'''(3)'''  From the continuous paths at  $\nu = 5$  it can be seen:
	'''(3)'''  From the continuous paths at $\nu = 5$ it can be seen:
	:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}		:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}
	a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}		a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}
Line 86:		Line 85:


	'''(4)'''  Only the <u>second statement</u> is correct:		'''(4)'''  Only the  <u>second statement</u>  is correct:
	*Since the source symbols "$0$" and "$1$" were assumed to be equally probable, the ML receiver (Viterbi) is identical to the MAP receiver.		*Since the source symbols  "$0$"  and  "$1$"  were assumed to be equally probable,  the ML receiver  (Viterbi)  is identical to the MAP receiver.
	*A threshold decision (which makes a symbol-by-symbol decision at each clock) has the same ~~error probability~~ as the Viterbi receiver only if there is no intersymbol interference.		*A threshold decision  $($which makes a symbol-by-symbol decision at each clock$)$  has the same BER as the Viterbi receiver only if there is no intersymbol interference.
	*This is obviously not the case here, otherwise it should be possible to make a final decision at every time $\nu$.		*This is obviously not the case here,  otherwise it should be possible to make a final decision at every time  $\nu$.
	*The first statement is also ~~not true~~. Indeed, this would mean that the Viterbi receiver can have error probability $0$ in the presence of ~~statistical~~ noise. This is not possible for information-theoretic reasons.		*The first statement is also false.  Indeed,  this would mean that the Viterbi receiver can have error probability  $0$  in the presence of AWGN noise.  <br>This is not possible for information-theoretic reasons.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter at 12:16, 4 July 2022

2022-07-04T12:16:06Z

← Older revision		Revision as of 14:16, 4 July 2022
Line 21:		Line 21:
	*The exercise belongs to the chapter  [[Digital_Signal_Transmission/Viterbi_Receiver\|"Viterbi Receiver"]].		*The exercise belongs to the chapter  [[Digital_Signal_Transmission/Viterbi_Receiver\|"Viterbi Receiver"]].

	*Reference is also made to the section  [[Digital_Signal_Transmission/Optimal_Receiver_Strategies#~~MAP_and_Maximum~~.E2.80.~~93Likelihood_decision_rule~~\|"~~MAP~~ and Maximum–Likelihood decision rule"]].		*Reference is also made to the section  [[Digital_Signal_Transmission/Optimal_Receiver_Strategies#Maximum-a-posteriori_and_maximum.E2.80.93likelihood_decision_rule\|"Maximum-a-posteriori and Maximum–Likelihood decision rule"]].

	* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:		* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:

Guenter at 12:13, 4 July 2022

2022-07-04T12:13:38Z

← Older revision		Revision as of 14:13, 4 July 2022
Line 2:		Line 2:
	{{quiz-Header\|Buchseite=Digital_Signal_Transmission/Viterbi_Receiver}}		{{quiz-Header\|Buchseite=Digital_Signal_Transmission/Viterbi_Receiver}}

	[[File:P_ID1475__Dig_A_3_11.png\|right\|frame\|Trellis diagram for a precursor]]		[[File:P_ID1475__Dig_A_3_11.png\|right\|frame\|Trellis diagram <br>for one precursor]]
	The Viterbi receiver allows a low-effort realization of the maximum likelihood decision rule. It contains the system components listed below:		The Viterbi receiver allows a low-effort realization of the maximum likelihood decision rule.  It contains the system components listed below:
	* a matched filter adapted to the basic transmission pulse with frequency response  $H_{\rm MF}(f)$  and output signal   $m(t)$,		* A matched filter adapted to the basic transmission pulse with frequency response  $H_{\rm MF}(f)$  and output signal   $m(t)$,
	* a sampler spaced at the symbol duration (bit duration)  $T$, which converts the continuous-time signal   $m(t)$  into the discrete-time sequence   $〈m_{\rm \nu}〉$,
	* a decorrelation filter with frequency response   $H_{\rm DF}(f)$  for removing statistical ties between the noise components of the sequence   $〈d_{\rm \nu}〉$,
	* the Viterbi decision, which uses a trellis-based algorithm to obtain the sink symbol sequence  $〈v_{\rm \nu}〉$.

			* a sampler spaced at the symbol duration  $T$,  which converts the continuous-time signal   $m(t)$  into the discrete-time sequence   $〈m_{\rm \nu}〉$,

			* a decorrelation filter with frequency response   $H_{\rm DF}(f)$  for removing statistical ties between noise components of the sequence   $〈d_{\rm \nu}〉$,

			* the Viterbi decision,  which uses a trellis-based algorithm to obtain the sink symbol sequence  $〈v_{\rm \nu}〉$.

	The graph shows the simplified trellis diagram of the two states "$0$" and "$1$" for time points   $\nu ≤ 5$. This diagram is obtained as a result of evaluating the two minimum total error quantities   ${\it \Gamma}_{\rm \nu}(0)$  and  ${\it \Gamma}_{\rm \nu}(1)$  corresponding to   [[Aufgaben:Exercise_3.11Z:_Maximum_Likelihood_Error_Variables\|"Exercise 3.11Z"]].

			The graph shows the simplified trellis diagram of the two states  "$0$"  and  "$1$"  for time points   $\nu ≤ 5$.  This diagram is obtained as a result of evaluating the two minimum accumulated metrics   ${\it \Gamma}_{\rm \nu}(0)$  and  ${\it \Gamma}_{\rm \nu}(1)$  corresponding to   [[Aufgaben:Exercise_3.11Z:_Maximum_Likelihood_Error_Variables\|Exercise 3.11Z]].




			Notes:
			*The exercise belongs to the chapter  [[Digital_Signal_Transmission/Viterbi_Receiver\|"Viterbi Receiver"]].

	~~''Notes:''~~
	*The exercise belongs to the chapter   [[Digital_Signal_Transmission/Viterbi_Receiver\|"Viterbi Receiver"]].
	*Reference is also made to the section  [[Digital_Signal_Transmission/Optimal_Receiver_Strategies#MAP_and_Maximum.E2.80.93Likelihood_decision_rule\|"MAP and Maximum–Likelihood decision rule"]].		*Reference is also made to the section  [[Digital_Signal_Transmission/Optimal_Receiver_Strategies#MAP_and_Maximum.E2.80.93Likelihood_decision_rule\|"MAP and Maximum–Likelihood decision rule"]].

	* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:  ${\rm Pr} (a_\nu = 0) = {\rm Pr} (a_\nu = 1)= 0.5.$		* All quantities here are to be understood normalized. Also assume unipolar and equal probability amplitude coefficients:
	* The topic is also covered in the interactive applet  [[Applets:Viterbi\|"Properties of the Viterbi Receiver"]].		:$${\rm Pr} (a_\nu = 0) = {\rm Pr} (a_\nu = 1)= 0.5.$$
			* The topic is also covered with the interactive SWF applet  [[Applets:Viterbi\|"Properties of the Viterbi Receiver"]].


Line 31:		Line 34:
	+ The matched filter  $H_{\rm MF}(f)$  is mainly used for noise power limitation.		+ The matched filter  $H_{\rm MF}(f)$  is mainly used for noise power limitation.
	+ The decorrelation filter removes ties between samples.		+ The decorrelation filter removes ties between samples.
	- The noise power is only affected by  $H_{\rm MF}(f)$, not by  $H_{\rm DF}(f)$.		- The noise power is only affected by  $H_{\rm MF}(f)$,  not by  $H_{\rm DF}(f)$.

	{At what times  $\nu$  can we finally decide the current symbol  $a_{\rm \nu}$?		{At what times  $\nu$  can we finally decide the current symbol  $a_{\rm \nu}$?
Line 41:		Line 44:
	+ $\nu = 5.$		+ $\nu = 5.$

	{What is the sequence decided by the Viterbi receiver?		{What is the total sequence decided by the Viterbi receiver?
	\|type="{}"}		\|type="{}"}
	$a_1 \ = \ $ { 0. }		$a_1 \ = \ $ { 0. }

Guenter at 11:53, 8 June 2022

2022-06-08T11:53:49Z

← Older revision		Revision as of 13:53, 8 June 2022
Line 92:		Line 92:


	[[Category:Digital Signal Transmission: Exercises\|^3.8 ~~Basis Functions & Vector Spaces~~^]]		[[Category:Digital Signal Transmission: Exercises\|^3.8 Viterbi Receiver^]]

Guenter at 11:52, 8 June 2022

2022-06-08T11:52:51Z

← Older revision		Revision as of 13:52, 8 June 2022
Line 92:		Line 92:


	[[Category:Digital Signal Transmission: Exercises\|^3.8 ~~Viterbi Receiver~~^]]		[[Category:Digital Signal Transmission: Exercises\|^3.8 Basis Functions & Vector Spaces^]]

Hwang at 08:47, 8 June 2022

2022-06-08T08:47:01Z

← Older revision		Revision as of 10:47, 8 June 2022
Line 33:		Line 33:
	- The noise power is only affected by  $H_{\rm MF}(f)$, not by  $H_{\rm DF}(f)$.		- The noise power is only affected by  $H_{\rm MF}(f)$, not by  $H_{\rm DF}(f)$.

	{~~Zu welchen Zeiten~~  $\nu$  ~~kann man das aktuelle Symbol~~  $a_{\rm \nu}$  ~~endgültig entscheiden?~~		{At what times  $\nu$  can we finally decide the current symbol  $a_{\rm \nu}$?
	\|type="[]"}		\|type="[]"}
	+ $\nu = 1,$		+ $\nu = 1,$
Line 41:		Line 41:
	+ $\nu = 5.$		+ $\nu = 5.$

	{~~Wie lautet die vom~~ Viterbi~~–Empfänger entschiedene Folge~~?		{What is the sequence decided by the Viterbi receiver?
	\|type="{}"}		\|type="{}"}
	$a_1 \ = \ $ { 0. }		$a_1 \ = \ $ { 0. }
Line 49:		Line 49:
	$a_5 \ = \ $ { 0. }		$a_5 \ = \ $ { 0. }

	{~~Welche der folgenden Aussagen sind zutreffend~~?		{Which of the following statements are true?
	\|type="[]"}		\|type="[]"}
	- ~~Es ist sicher, dass die erkannte Folge auch gesendet wurde~~.		- It is certain that the detected sequence was also sent.
	+ ~~Ein~~ MAP~~–Empfänger hätte die gleiche Fehlerwahrscheinlichkeit~~.		+ A MAP receiver would have the same error probability.
	- ~~Schwellenwertentscheidung ist gleich gut wie dieser Maximum–Likelihood–Empfänger~~.		- Threshold decision is the same as this maximum likelihood receiver.
	</quiz>		</quiz>

	===~~Musterlösung~~===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  ~~Richtig sind die~~ <u>~~beiden ersten Lösungsvorschläge~~</u>:		'''(1)'''  The <u>first two solutions</u> are correct:
	*~~Das Signal~~ $m(t)$ ~~nach dem Matched–Filter~~ $H_{\rm MF}(f)$ ~~weist das größtmögliche Signal–zu–Störleistungsverhältnis auf~~.		*The signal $m(t)$ after the matched filter $H_{\rm MF}(f)$ has the largest possible signal-to-interference power ratio.
	* ~~Die Störanteile der Folge~~ $〈m_{\rm \nu}〉$ ~~sind aber aufgrund der spektralen Formung~~ (~~stark~~) ~~korreliert~~.		* However, the noise components of the sequence $〈m_{\rm \nu}〉$ are (strongly) correlated due to the spectral shaping.
	*~~Aufgabe des zeitdiskreten Dekorrelationsfilters mit dem Frequenzgang~~ $H_{\rm DF}(f)$ ~~ist es~~, ~~diese Bindungen aufzulösen, weshalb für~~ $H_{\rm DF}(f)$ ~~auch der Name "Whitening–Filter" verwendet wird~~.		*The task of the discrete-time decorrelation filter with the frequency response $H_{\rm DF}(f)$ is to dissolve these bonds, which is why the name "whitening filter" is also used for $H_{\rm DF}(f)$.
	*~~Dies ist allerdings nur auf Kosten einer erhöhten Störleistung möglich~~   ⇒   ~~der letzte Lösungsvorschlag trifft demnach nicht zu~~.		*However, this is possible only at the cost of increased noise power   ⇒   consequently, the last proposed solution does not apply.



	'''(2)'''  ~~Die beiden bei~~ $\underline {\nu = 1}$ ~~ankommenden Pfeile sind jeweils blau gezeichnet und kennzeichnen das Symbol~~ $a_1 = 0$. ~~Somit ist bereits zu diesem Zeitpunkt das Ausgangssymbol~~ $a_1$ ~~festgelegt~~. ~~Ebenso stehen die Symbole~~ $a_3 = 1$ ~~und~~ $a_5 = 0$ ~~bereits zu den Zeitpunkten~~ $\underline {\nu = 3}$ ~~bzw.~~ $\underline {\nu = 5}$ ~~fest~~.		'''(2)'''  The two arrows arriving at $\underline {\nu = 1}$ are each drawn in blue and indicate the symbol $a_1 = 0$. Thus, the initial symbol $a_1$ is already fixed at this point. Similarly, the symbols $a_3 = 1$ and $a_5 = 0$ are already fixed at the timesn $\underline {\nu = 3}$ and $\underline {\nu = 5}$, respectively.

	~~Dagegen ist zum Zeitpunkt~~ $\nu = 2$ ~~eine Entscheidung bezüglich des Symbols~~ $a_2$ ~~nicht möglich~~.		In contrast, at time $\nu = 2$, a decision regarding symbol $a_2$ is not possible.
	*~~Unter der Hypothese, dass das nachfolgende Symbol~~ $a_3 = 0$ ~~sein wird, würde sich Symbol~~ $a_2 = 1$ ~~ergeben~~ (~~bei~~ "$0$" ~~kommt ein roter Pfad an~~, ~~also von~~ "$1$" ~~kommend~~).		*Under the hypothesis that the following symbol $a_3 = 0$ would result in symbol $a_2 = 1$ (at "$0$" a red path arrives, thus coming from "$1$").
	* ~~Dagegen führt die Hypothese~~ $a_3 = 1$ ~~zum Ergebnis~~ $a_2 = 0$ (~~der bei~~ "$1$" ~~ankommende Pfad ist blau~~).		* In contrast, the hypothesis $a_3 = 1$ leads to the result $a_2 = 0$ (the path arriving at "$1$" is blue).


	~~Ähnlich verhält es sich zum Zeitpunkt~~ $\nu = 4$.		The situation is similar at time $\nu = 4$.


	'''(3)'''  ~~Aus den durchgehenden Pfaden bei~~ $\nu = 5$ ~~ist ersichtlich~~:		'''(3)'''  From the continuous paths at $\nu = 5$ it can be seen:
	:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}		:$$a_{1}\hspace{0.15cm}\underline {=0} \hspace{0.05cm},\hspace{0.2cm}
	a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}		a_{2}\hspace{0.15cm}\underline { =0} \hspace{0.05cm},\hspace{0.2cm}a_{3}\hspace{0.15cm}\underline {=1}
Line 83:		Line 83:


	'''(4)'''  ~~Richtig ist nur die~~ <u>~~zweite Aussage~~</u>:		'''(4)'''  Only the <u>second statement</u> is correct:
	*~~Da die Quellensymbole~~ "$0$" ~~und~~ "$1$" ~~als gleichwahrscheinlich vorausgesetzt wurden~~, ~~ist der~~ ML~~–Empfänger~~ (Viterbi) ~~identisch mit dem~~ MAP~~–Empfänger~~.		*Since the source symbols "$0$" and "$1$" were assumed to be equally probable, the ML receiver (Viterbi) is identical to the MAP receiver.
	*~~Ein Schwellenwertentscheider~~ (~~der zu jedem Takt eine symbolweise Entscheidung trifft~~) ~~hat nur dann die gleiche Fehlerwahrscheinlichkeit wie der~~ Viterbi~~–Empfänger, wenn es keine Impulsinterferenzen gibt~~.		*A threshold decision (which makes a symbol-by-symbol decision at each clock) has the same error probability as the Viterbi receiver only if there is no intersymbol interference.
	*~~Dies ist hier offensichtlich nicht der Fall~~, ~~sonst müsste zu jedem Zeitpunkt~~ $\nu$ ~~eine endgültige Entscheidung getroffen werden können~~.		*This is obviously not the case here, otherwise it should be possible to make a final decision at every time $\nu$.
	*~~Die erste Aussage trifft ebenfalls nicht zu~~. ~~Das würde nämlich bedeuten~~, ~~dass der~~ Viterbi~~–Empfänger bei Vorhandensein von statistischem Rauschen die Fehlerwahrscheinlichkeit~~ $0$ ~~haben kann~~. ~~Dies ist aus informationstheoretischen Gründen nicht möglich~~.		*The first statement is also not true. Indeed, this would mean that the Viterbi receiver can have error probability $0$ in the presence of statistical noise. This is not possible for information-theoretic reasons.
	{{ML-Fuß}}		{{ML-Fuß}}