Channel Coding/Decoding of Convolutional Codes - Revision history

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

2026-03-16T13:46:42Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:46, 16 March 2026
Line 184:		Line 184:
	[[File:P ID2700 KC T 3 4 S4b v1.png\|right\|frame\|Decoding example with three bit errors\|class=fit]]		[[File:P ID2700 KC T 3 4 S4b v1.png\|right\|frame\|Decoding example with three bit errors\|class=fit]]
	:$$\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )$$		:$$\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )$$
	:$$\Rightarrow \hspace{0.3cm}		:$$\Rightarrow \hspace{0.3cm}\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.$$
	\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.$$

	From the graph you can see here that the decoder decides for the correct path  $($dark background$)$  despite three bit errors.		From the graph you can see here that the decoder decides for the correct path  $($dark background$)$  despite three bit errors.
Line 196:		Line 195:
	[[File:P ID2704 KC T 3 4 S4c v1.png\|right\|frame\|Decoding example with four bit errors\|class=fit]]		[[File:P ID2704 KC T 3 4 S4c v1.png\|right\|frame\|Decoding example with four bit errors\|class=fit]]
	:$$\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )$$		:$$\underline{u} = \big (1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0\hspace{0.05cm}, 1 \hspace{0.05cm}, 0\hspace{0.05cm}, 0 \big )$$
	:$$\Rightarrow \hspace{0.3cm}		:$$\Rightarrow \hspace{0.3cm}\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.$$
	\underline{x} = \big (11\hspace{0.05cm}, 01\hspace{0.05cm}, 01\hspace{0.05cm}, 11\hspace{0.05cm}, 11\hspace{0.05cm}, 10\hspace{0.05cm}, 11 \hspace{0.05cm} \hspace{0.05cm} \big ) \hspace{0.05cm}.$$

	Unlike the last example,  a fourth bit error is added:  $\underline{y}_7 = (01).$		Unlike the last example,  a fourth bit error is added:  $\underline{y}_7 = (01).$
Line 400:		Line 398:
	All of these decoding schemes,  as well as the Viterbi algorithm as described so far,  provide  "hard decided"  output values   ⇒   $v_i ∈ \{0, 1\}$.  Often,  however,  information about the reliability of the decisions made would be desirable,  especially when there is a concatenated coding scheme with an outer and an inner code.<br>		All of these decoding schemes,  as well as the Viterbi algorithm as described so far,  provide  "hard decided"  output values   ⇒   $v_i ∈ \{0, 1\}$.  Often,  however,  information about the reliability of the decisions made would be desirable,  especially when there is a concatenated coding scheme with an outer and an inner code.<br>

	If the reliability of the bits decided by the inner decoder is known at least roughly,  this information can be used to  (significantly)  reduce the bit error probability of the outer decoder.  The  "soft output Viterbi algorithm"  $\rm(SOVA)$  proposed by  [[Biographies_and_Bibliographies/~~Lehrstuhlinhaber_des_LNT~~#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_~~.281993~~-2006~~.29~~\|$\text{Joachim Hagenauer}$]]  in  [Hag90]<ref name='Hag90'>Hagenauer, J.:  Soft Output Viterbi Decoder.  In: Technischer Report, Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR), 1990.</ref>  allows to specify a reliability measure in each case in addition to the decided symbols.		If the reliability of the bits decided by the inner decoder is known at least roughly,  this information can be used to  (significantly)  reduce the bit error probability of the outer decoder.  The  "soft output Viterbi algorithm"  $\rm(SOVA)$  proposed by  [[Biographies_and_Bibliographies/Chair_holders_of_the_LNT_since_1962#Prof._Dr.-Ing._Dr.-Ing._E.h._Joachim_Hagenauer_(1993-2006)\|$\text{Joachim Hagenauer}$]]  in  [Hag90]<ref name='Hag90'>Hagenauer, J.:  Soft Output Viterbi Decoder.  In: Technischer Report, Deutsche Forschungsanstalt für Luft- und Raumfahrt (DLR), 1990.</ref>  allows to specify a reliability measure in each case in addition to the decided symbols.

	Finally, we go into some detail about the  »<b>BCJR algorithm</b>«  named after its inventors L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv  [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.:  Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.  In: IEEE Transactions on Information Theory, Vol. IT-20, pp. 284-287, 1974.</ref>.		Finally, we go into some detail about the  »<b>BCJR algorithm</b>«  named after its inventors L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv  [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.:  Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.  In: IEEE Transactions on Information Theory, Vol. IT-20, pp. 284-287, 1974.</ref>.
Line 416:		Line 414:
	<u>Notes:</u>		<u>Notes:</u>
	#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.		#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.
	#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/~~Soft–in_Soft–out_Decoder~~#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.lnt.ei.tum.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>		#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/Soft-in_Soft-Out_Decoder#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.lnt.ei.tum.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>

Maintenance script: Add German interlanguage link

2026-03-16T12:27:34Z

Add German interlanguage link

← Older revision		Revision as of 14:27, 16 March 2026
Line 435:		Line 435:

	{{Display}}		{{Display}}
			[[de:Kanalcodierung/Decodierung_von_Faltungscodes]]

Maintenance script: Update domain links: en.lntwww.de → en.lntwww.lnt.ei.tum.de, www.lntwww.de → lntwww.lnt.ei.tum.de

2026-03-16T11:09:49Z

Update domain links: en.lntwww.de → en.lntwww.lnt.ei.tum.de, www.lntwww.de → lntwww.lnt.ei.tum.de

← Older revision		Revision as of 13:09, 16 March 2026
Line 416:		Line 416:
	<u>Notes:</u>		<u>Notes:</u>
	#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.		#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.
	#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>		#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.lnt.ei.tum.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>

Hwang at 14:53, 23 January 2023

2023-01-23T14:53:45Z

← Older revision		Revision as of 16:53, 23 January 2023
Line 403:		Line 403:

	Finally, we go into some detail about the  »<b>BCJR algorithm</b>«  named after its inventors L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv  [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.:  Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.  In: IEEE Transactions on Information Theory, Vol. IT-20, pp. 284-287, 1974.</ref>.		Finally, we go into some detail about the  »<b>BCJR algorithm</b>«  named after its inventors L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv  [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.:  Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.  In: IEEE Transactions on Information Theory, Vol. IT-20, pp. 284-287, 1974.</ref>.
	:While the Viterbi algorithm only estimates the total sequence   ⇒   [[Channel_Coding/Channel_Models_and_Decision_Structures#Definitions_of_the_different_optimal_receivers\|$\text{block-wise ML}$]],  the BCJR algorithm estimates a single bit considering the entire received sequence.  So this is a  "bit-wise maximum a posteriori decoding"   ⇒   [[Channel_Coding/Channel_Models_and_Decision_Structures#Definitions_of_the_different_optimal_receivers\|$\text{bit-wise MAP}$]].<br>		:While the Viterbi algorithm only estimates the total sequence   ⇒   [[Channel_Coding/Channel_Models_and_Decision_Structures#Definitions_of_the_different_optimal_receivers\|$\text{block-wise ML}$]],  the BCJR algorithm estimates a single bit considering the entire received sequence.  So this is a  "bit-wise maximum a-posteriori decoding"   ⇒   [[Channel_Coding/Channel_Models_and_Decision_Structures#Definitions_of_the_different_optimal_receivers\|$\text{bit-wise MAP}$]].<br>

Hwang at 10:32, 1 December 2022

2022-12-01T10:32:08Z

← Older revision		Revision as of 12:32, 1 December 2022
Line 412:		Line 412:
	*The   »<b>Viterbi algorithm</b> «  processes the trellis in only one direction  – the forward direction  – and computes the metrics  ${\it \Lambda}_i(S_{\mu})$  for each node.  After reaching the terminal node,  the surviving path is searched,  which identifies the most probable encoded sequence.<br>		*The   »<b>Viterbi algorithm</b> «  processes the trellis in only one direction  – the forward direction  – and computes the metrics  ${\it \Lambda}_i(S_{\mu})$  for each node.  After reaching the terminal node,  the surviving path is searched,  which identifies the most probable encoded sequence.<br>

	*In the   »<b>BCJR algorithm </b>«  the trellis is processed twice,  once in forward direction and then in backward direction.  Two metrics can then be specified for each node,  from which the ~~aposterori~~ probability can be determined for each bit}}.<br>		*In the   »<b>BCJR algorithm </b>«  the trellis is processed twice,  once in forward direction and then in backward direction.  Two metrics can then be specified for each node,  from which the a-posterori probability can be determined for each bit}}.<br>

	<u>~~Hints~~:</u>		<u>Notes:</u>
	#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.		#   This short summary is based on the textbook  [Bos99]<ref name='Bos99'>Bossert, M.:  Channel Coding for Telecommunications.  Wiley & Sons, 1999.</ref>.
	#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>		#   A description of the BCJR–algorithm follows also in section  [[Channel_Coding/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision\| "Hard Decision vs. Soft Decision"]]  [https://en.lntwww.de/Channel_Coding "in the fourth main chapter"]  "Iterative Decoding Methods".<br>

Hwang at 10:22, 1 December 2022

2022-12-01T10:22:13Z

← Older revision		Revision as of 12:22, 1 December 2022
Line 381:		Line 381:
	#But it is already certain that the most probable bit sequence is represented by one of the paths  ${\it \Phi}_9(S_0), \ \text{...} \ , \ {\it \Phi}_9(S_3)$.<br>		#But it is already certain that the most probable bit sequence is represented by one of the paths  ${\it \Phi}_9(S_0), \ \text{...} \ , \ {\it \Phi}_9(S_3)$.<br>
	#Since all four paths up to  $i = 3$  are identical,  the decision  "$v_1 = 0,\ v_2 = 0, \ v_3 = 0$"  is the the most probable.  Also at a later time no other decision would be made.		#Since all four paths up to  $i = 3$  are identical,  the decision  "$v_1 = 0,\ v_2 = 0, \ v_3 = 0$"  is the the most probable.  Also at a later time no other decision would be made.
	#Regarding the bits  $v_4, \ v_5, \ \text{...}$  one should not decide at this early stage.  Only the ~~forst~~ two zeros are safe,  not  $v_3 = 0$.		#Regarding the bits  $v_4, \ v_5, \ \text{...}$  one should not decide at this early stage.  Only the first two zeros are safe,  not  $v_3 = 0$.
	#If one had to make a constraint decision at time  $i = 9$  one would choose  ${\it \Phi}_9(S_0)$   ⇒   $\underline{v} = (0, 0, \text{. ..} \ , 0)$ since the metric  ${\it \Lambda}_9(S_0) = 14$  is larger than the comparison metrics.<br>		#If one had to make a constraint decision at time  $i = 9$  one would choose  ${\it \Phi}_9(S_0)$   ⇒   $\underline{v} = (0, 0, \text{. ..} \ , 0)$ since the metric  ${\it \Lambda}_9(S_0) = 14$  is larger than the comparison metrics.<br>
	#The forced decision at time  $i = 9$  leads to the correct result in this example,  see lower sketch.		#The forced decision at time  $i = 9$  leads to the correct result in this example,  see lower sketch.

Hwang at 10:15, 1 December 2022

2022-12-01T10:15:54Z

← Older revision		Revision as of 12:15, 1 December 2022
Line 371:		Line 371:
	$\text{Definition:}$  The   »<b>survivor</b>«   ${\it \Phi}_i(S_{\mu})$  is the continuous path from the start  $S_0$  $($at  $i = 0)$  to the node  $S_{\mu}$ at time  $i$.		$\text{Definition:}$  The   »<b>survivor</b>«   ${\it \Phi}_i(S_{\mu})$  is the continuous path from the start  $S_0$  $($at  $i = 0)$  to the node  $S_{\mu}$ at time  $i$.

	*It is recommended to search for paths in the backward direction}}.<br>		*It is recommended to search for paths in the backward direction.}}<br>

	The following graph shows the surviving paths for time points  $i = 6$  to  $i = 9$.  In addition,  the respective metrics  $($accumulated correlaltion values$)$  ${\it \Lambda}_i(S_{\mu})$  for all four states are given.		The following graph shows the surviving paths for time points  $i = 6$  to  $i = 9$.  In addition,  the respective metrics  $($accumulated correlaltion values$)$  ${\it \Lambda}_i(S_{\mu})$  for all four states are given.

Hwang at 09:57, 1 December 2022

2022-12-01T09:57:13Z

← Older revision		Revision as of 11:57, 1 December 2022
Line 266:		Line 266:
	*As for the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Decoding_examples_for_the_erroneous_case\|$\text{Trellis evaluation according to Example 1}$]]  based on the minimum Hamming distance and the error values  ${\it \Gamma}_i(S_{\mu})$		*As for the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Decoding_examples_for_the_erroneous_case\|$\text{Trellis evaluation according to Example 1}$]]  based on the minimum Hamming distance and the error values  ${\it \Gamma}_i(S_{\mu})$

	*~~the~~ the input sequence and the encoded sequence are		*the input sequence and the encoded sequence are
	:$$\underline{u} = \big (0\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0 \hspace{0.05cm} \big ) \hspace{0.3cm} ⇒ \hspace{0.3cm} \underline{x} = \big (00, 11, 10, 00, 01, 01, 11 \big ) \hspace{0.05cm}.$$		:$$\underline{u} = \big (0\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 1\hspace{0.05cm}, 1\hspace{0.05cm}, 0\hspace{0.05cm}, 0 \hspace{0.05cm} \big ) \hspace{0.3cm} ⇒ \hspace{0.3cm} \underline{x} = \big (00, 11, 10, 00, 01, 01, 11 \big ) \hspace{0.05cm}.$$
	[[File:P ID2663 KC T 3 4 S6 v1.png\|right\|frame\|Viterbi decoding based on correlation and metrics\|class=fit]]		[[File:P ID2663 KC T 3 4 S6 v1.png\|right\|frame\|Viterbi decoding based on correlation and metrics\|class=fit]]

Hwang at 09:52, 1 December 2022

2022-12-01T09:52:48Z

← Older revision		Revision as of 11:52, 1 December 2022
Line 242:		Line 242:
	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Conclusion:}$  Let us now interpret this last equation for some special cases:		$\text{Conclusion:}$  Let us now interpret this last equation for some special cases:
	*»'''Identical sequences'''«:   The Hamming distance is equal to  $0$  and the  correlation value is equal  $L$.<br>		*»'''Identical sequences'''«:   The Hamming distance is equal to  $0$  and the  correlation value is equal to  $L$.<br>

	*»'''Inverted sequences'''«:   The Hamming distance is equal to  $L$  and the  correlation value  is equal to  $-L$.<br>		*»'''Inverted sequences'''«:   The Hamming distance is equal to  $L$  and the  correlation value  is equal to  $-L$.<br>

Hwang at 09:49, 1 December 2022

2022-12-01T09:49:58Z

← Older revision		Revision as of 11:49, 1 December 2022
Line 242:		Line 242:
	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Conclusion:}$  Let us now interpret this last equation for some special cases:		$\text{Conclusion:}$  Let us now interpret this last equation for some special cases:
	*»'''Identical sequences'''«:   The Hamming distance is equal  $0$  and the  correlation value is equal  $L$.<br>		*»'''Identical sequences'''«:   The Hamming distance is equal to  $0$  and the  correlation value is equal  $L$.<br>

	*»'''Inverted sequences'''«:   The Hamming distance is equal to  $L$  and the  correlation value  is equal to  $-L$.<br>		*»'''Inverted sequences'''«:   The Hamming distance is equal to  $L$  and the  correlation value  is equal to  $-L$.<br>