Channel Coding/Decoding of Convolutional Codes - Revision history

Hwang at 14:53, 23 January 2023

2023-01-23T14:53:45Z

Hwang at 10:32, 1 December 2022

2022-12-01T10:32:08Z

Hwang at 10:22, 1 December 2022

2022-12-01T10:22:13Z

Hwang at 10:15, 1 December 2022

2022-12-01T10:15:54Z

Hwang at 09:57, 1 December 2022

2022-12-01T09:57:13Z

Hwang at 09:52, 1 December 2022

2022-12-01T09:52:48Z

Hwang at 09:49, 1 December 2022

2022-12-01T09:49:58Z

Hwang at 16:33, 30 November 2022

2022-11-30T16:33:33Z

Hwang at 16:31, 30 November 2022

2022-11-30T16:31:04Z

Hwang at 16:29, 30 November 2022

2022-11-30T16:29:19Z

← Older revision		Revision as of 14: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>

@@ Line 412: / Line 412: @@
 *The &nbsp; &raquo;<b>Viterbi algorithm</b> &laquo;&nbsp; processes the trellis in only one direction&nbsp; &ndash; the forward direction&nbsp; &ndash; and computes the metrics&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; for each node.&nbsp; After reaching the terminal node,&nbsp; the surviving path is searched,&nbsp; which identifies the most probable encoded sequence.<br>
-*In the &nbsp; &raquo;<b>BCJR algorithm </b>&laquo;&nbsp; the trellis is processed twice,&nbsp; once in forward direction and then in backward direction.&nbsp; Two metrics can then be specified for each node,&nbsp; from which the aposterori probability can be determined for each bit}}.<br>
+*In the &nbsp; &raquo;<b>BCJR algorithm </b>&laquo;&nbsp; the trellis is processed twice,&nbsp; once in forward direction and then in backward direction.&nbsp; Two metrics can then be specified for each node,&nbsp; from which the a-posterori probability can be determined for each bit}}.<br>
-<u>Hints:</u>
+<u>Notes:</u>
 # &nbsp; This short summary is based on the textbook&nbsp;   [Bos99]<ref name='Bos99'>Bossert, M.:&nbsp; Channel Coding for Telecommunications.&nbsp; Wiley & Sons, 1999.</ref>.
 # &nbsp; A description of the BCJR&ndash;algorithm follows also in section&nbsp; [[Channel_Coding/Soft–in_Soft–out_Decoder#Hard_Decision_vs._Soft_Decision| "Hard Decision vs. Soft Decision"]]&nbsp; [https://en.lntwww.de/Channel_Coding "in the fourth main chapter"]&nbsp; "Iterative Decoding Methods".<br>

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

@@ Line 371: / Line 371: @@
 $\text{Definition:}$&nbsp;  The &nbsp; &raquo;<b>survivor</b>&laquo; &nbsp; ${\it \Phi}_i(S_{\mu})$&nbsp; is the continuous path from the start&nbsp; $S_0$&nbsp; $($at&nbsp; $i = 0)$&nbsp; to the node&nbsp; $S_{\mu}$ at time&nbsp; $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&nbsp; $i = 6$&nbsp; to&nbsp; $i = 9$.&nbsp; In addition,&nbsp; the respective metrics&nbsp; $($accumulated correlaltion values$)$&nbsp; ${\it \Lambda}_i(S_{\mu})$&nbsp; for all four states are given.

@@ Line 266: / Line 266: @@
 *As for the&nbsp; [[Channel_Coding/Decoding_of_Convolutional_Codes#Decoding_examples_for_the_erroneous_case|$\text{Trellis evaluation according to Example 1}$]]&nbsp; based on the minimum Hamming distance and the error values&nbsp; ${\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} &rArr; \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]]

@@ Line 242: / Line 242: @@
 {{BlaueBox|TEXT=
 $\text{Conclusion:}$&nbsp;  Let us now interpret this last equation for some special cases:
-*&raquo;'''Identical sequences'''&laquo;: &nbsp; The Hamming distance is equal to&nbsp; $0$&nbsp; and the&nbsp; correlation value is equal&nbsp; $L$.<br>
+*&raquo;'''Identical sequences'''&laquo;: &nbsp; The Hamming distance is equal to&nbsp; $0$&nbsp; and the&nbsp; correlation value is equal to&nbsp; $L$.<br>
 *&raquo;'''Inverted sequences'''&laquo;: &nbsp; The Hamming distance is equal to&nbsp; $L$&nbsp; and the&nbsp; correlation value&nbsp; is equal to&nbsp; $-L$.<br>

@@ Line 213: / Line 213: @@
 == Relationship between Hamming distance and correlation ==
 <br>
-Especially for the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80. 93_BSC|$\text{BSC model}$]]&nbsp; $($but also for any other binary channel&nbsp; &#8658; &nbsp; input&nbsp; $x_i &#8712; \{0,1\}$,&nbsp; output $y_i &#8712; \{0,1\}$&nbsp; such as the&nbsp; [[Digital_Signal_Transmission/Burst_Error_Channels#Channel_model_according_to_Gilbert-Elliott|$\text{Gilbert&ndash;Elliott model}$]]$)$&nbsp; provides
+Especially for the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|$\text{BSC model}$]]&nbsp; $($but also for any other binary channel&nbsp; &#8658; &nbsp; input&nbsp; $x_i &#8712; \{0,1\}$,&nbsp; output $y_i &#8712; \{0,1\}$&nbsp; such as the&nbsp; [[Digital_Signal_Transmission/Burst_Error_Channels#Channel_model_according_to_Gilbert-Elliott|$\text{Gilbert&ndash;Elliott model}$]]$)$&nbsp; provides
 *the Hamming distance&nbsp; $d_{\rm H}(\underline{x}, \ \underline{y})$&nbsp; exactly the same information about the similarity of the input sequence&nbsp; $\underline{x}$&nbsp; and the output sequence&nbsp; $\underline{y}$&nbsp;

@@ Line 190: / Line 190: @@
 *So there is not always a wrong decision,&nbsp; if more than&nbsp; $d_{\rm F}/2$&nbsp; bit errors occurred.
-*But with statistical distribution of the three bit errors,nbsp; wrong decision would be more frequent than right.}}<br>
+*But with statistical distribution of the three bit errors,&nbsp; wrong decision would be more frequent than right.}}<br>
 {{GraueBox|TEXT=

@@ Line 188: / Line 188: @@
 From the graph you can see here that the decoder decides for the correct path&nbsp; $($dark background$)$&nbsp; despite three bit errors.
-*So there is not always a wrong decision,nbsp; if more than&nbsp; $d_{\rm F}/2$&nbsp; bit errors occurred.
+*So there is not always a wrong decision,&nbsp; if more than&nbsp; $d_{\rm F}/2$&nbsp; bit errors occurred.
 *But with statistical distribution of the three bit errors,nbsp; wrong decision would be more frequent than right.}}<br>