Channel Coding/Basics of Convolutional Coding - Revision history

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

2026-03-16T13:46:41Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:46, 16 March 2026
Line 115:		Line 115:

	*To generate two code bits  $x_i^{(1)}$  and  $x_i^{(2)}$  from a single information bit,  the convolutional encoder must include at least one memory element:		*To generate two code bits  $x_i^{(1)}$  and  $x_i^{(2)}$  from a single information bit,  the convolutional encoder must include at least one memory element:
	:$$k = 1\hspace{0.05cm}, \ n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1		:$$k = 1\hspace{0.05cm}, \ n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1\hspace{0.05cm}.$$
	\hspace{0.05cm}.$$

	*Taking into account the  $($half–infinite$)$  long information sequence  $\underline{u}$  the model results according to the lower graph.		*Taking into account the  $($half–infinite$)$  long information sequence  $\underline{u}$  the model results according to the lower graph.

Maintenance script: Add German interlanguage link

2026-03-16T12:27:38Z

Add German interlanguage link

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

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

Guenter at 16:02, 7 December 2022

2022-12-07T16:02:16Z

← Older revision		Revision as of 18:02, 7 December 2022
Line 144:		Line 144:

	*The two information bits are:		*The two information bits are:
	[[File:~~P ID2596 KC T 3 1 S3d v1~~.png\|right\|frame\|Convolutional encoder  $(k = 1, \ n = 2, \ m = 2)$  in two different representations ~~'''KORREKTUR: Schieberegister'''~~\|class=fit]]		[[File:EN_KC_T_3_1_S3d_neu.png\|right\|frame\|Convolutional encoder  $(k = 1, \ n = 2, \ m = 2)$  in two different representations\|class=fit]]

	::<math>x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>		::<math>x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>

Guenter at 17:48, 2 December 2022

2022-12-02T17:48:40Z

← Older revision		Revision as of 19:48, 2 December 2022
Line 97:		Line 97:

	However,  because of the large differences in description,  properties,  and especially decoding,  we consider convolutional codes to be something completely new in this learning tutorial.  The reasons for this are as follows:		However,  because of the large differences in description,  properties,  and especially decoding,  we consider convolutional codes to be something completely new in this learning tutorial.  The reasons for this are as follows:
	#   A block ~~coder '''KORREKTUR:~~ encoder~~'''~~ converts block-by-block information words of length  $k$  bits into code words of length  $n$  bits each.  In this case,  the larger its code word length  $n$,  the more powerful the block code is.  For a given code rate  $R = k/n$  this also requires a large information word length  $k$.<br>		#   A block encoder converts block-by-block information words of length  $k$  bits into code words of length  $n$  bits each.  In this case,  the larger its code word length  $n$,  the more powerful the block code is.  For a given code rate  $R = k/n$  this also requires a large information word length  $k$.<br>
	#   In contrast,  the correction capability of a convolutional code is essentially determined by its memory  $m$.  The code parameters  $k$  and  $n$  are mostly chosen very small here  $(1, \ 2, \ 3, \ \text{...})$.  Thus,  only very few and,  moreover,  very simple convolutional codes are of practical importance.<br>		#   In contrast,  the correction capability of a convolutional code is essentially determined by its memory  $m$.  The code parameters  $k$  and  $n$  are mostly chosen very small here  $(1, \ 2, \ 3, \ \text{...})$.  Thus,  only very few and,  moreover,  very simple convolutional codes are of practical importance.<br>
	#   Even with small values for  $k$  and  $n$,  a convolutional encoder transfers a whole sequence of information bits  $(k\hspace{0.05cm}' → ∞)$  into a very long sequence of code bits  $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$.  Such a code thus often provides a large correction capability as well.<br>		#   Even with small values for  $k$  and  $n$,  a convolutional encoder transfers a whole sequence of information bits  $(k\hspace{0.05cm}' → ∞)$  into a very long sequence of code bits  $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$.  Such a code thus often provides a large correction capability as well.<br>

Hwang at 13:57, 30 November 2022

2022-11-30T13:57:26Z

← Older revision		Revision as of 15:57, 30 November 2022
Line 144:		Line 144:

	*The two information bits are:		*The two information bits are:
	[[File:P ID2596 KC T 3 1 S3d v1.png\|right\|frame\|~~Faltungscoder~~  $(k = 1, \ n = 2, \ m = 2)$  in ~~zwei verschiedenen Darstellungen~~\|class=fit]]		[[File:P ID2596 KC T 3 1 S3d v1.png\|right\|frame\|Convolutional encoder  $(k = 1, \ n = 2, \ m = 2)$  in two different representations '''KORREKTUR: Schieberegister'''\|class=fit]]

	::<math>x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>		::<math>x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},</math>

Hwang at 11:39, 30 November 2022

2022-11-30T11:39:52Z

← Older revision		Revision as of 13:39, 30 November 2022
Line 97:		Line 97:

	However,  because of the large differences in description,  properties,  and especially decoding,  we consider convolutional codes to be something completely new in this learning tutorial.  The reasons for this are as follows:		However,  because of the large differences in description,  properties,  and especially decoding,  we consider convolutional codes to be something completely new in this learning tutorial.  The reasons for this are as follows:
	#   A block coder converts block-by-block information words of length  $k$  bits into code words of length  $n$  bits each.  In this case,  the larger its code word length  $n$,  the more powerful the block code is.  For a given code rate  $R = k/n$  this also requires a large information word length  $k$.<br>		#   A block coder '''KORREKTUR: encoder''' converts block-by-block information words of length  $k$  bits into code words of length  $n$  bits each.  In this case,  the larger its code word length  $n$,  the more powerful the block code is.  For a given code rate  $R = k/n$  this also requires a large information word length  $k$.<br>
	#   In contrast,  the correction capability of a convolutional code is essentially determined by its memory  $m$.  The code parameters  $k$  and  $n$  are mostly chosen very small here  $(1, \ 2, \ 3, \ \text{...})$.  Thus,  only very few and,  moreover,  very simple convolutional codes are of practical importance.<br>		#   In contrast,  the correction capability of a convolutional code is essentially determined by its memory  $m$.  The code parameters  $k$  and  $n$  are mostly chosen very small here  $(1, \ 2, \ 3, \ \text{...})$.  Thus,  only very few and,  moreover,  very simple convolutional codes are of practical importance.<br>
	#   Even with small values for  $k$  and  $n$,  a convolutional encoder transfers a whole sequence of information bits  $(k\hspace{0.05cm}' → ∞)$  into a very long sequence of code bits  $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$.  Such a code thus often provides a large correction capability as well.<br>		#   Even with small values for  $k$  and  $n$,  a convolutional encoder transfers a whole sequence of information bits  $(k\hspace{0.05cm}' → ∞)$  into a very long sequence of code bits  $(n\hspace{0.05cm}' = k\hspace{0.05cm}'/R)$.  Such a code thus often provides a large correction capability as well.<br>

Hwang at 11:38, 30 November 2022

2022-11-30T11:38:46Z

Hwang at 11:36, 30 November 2022

2022-11-30T11:36:58Z

← Older revision		Revision as of 13:36, 30 November 2022
Line 10:		Line 10:
	This third main chapter discusses   »'''convolutional codes'''«,   first described in 1955 by  [https://en.wikipedia.org/wiki/Peter_Elias $\text{Peter Elias}$]  [Eli55]<ref name='Eli55'>Elias, P.:  Coding for Noisy Channels.  In:  IRE Conv. Rec. Part 4, pp. 37-47, 1955.</ref>.		This third main chapter discusses   »'''convolutional codes'''«,   first described in 1955 by  [https://en.wikipedia.org/wiki/Peter_Elias $\text{Peter Elias}$]  [Eli55]<ref name='Eli55'>Elias, P.:  Coding for Noisy Channels.  In:  IRE Conv. Rec. Part 4, pp. 37-47, 1955.</ref>.

	*While for linear block codes  $($see  [[Channel_Coding/Objective_of_Channel_Coding#.~~23_Overview_on_The_First_Main_Chapter_~~.23\|$\text{first main chapter}$]]$)$  and Reed-Solomon codes  $($see  [[Channel_Coding/Some_Basics_of_Algebra#. 23_OVERVIEW_OF_THE_SECOND_MAIN_CHAPTER_.23\|$\text{second main chapter}$]]$)$  the code word length is  $n$  in each case,		*While for linear block codes  $($see  [[Channel_Coding/Objective_of_Channel_Coding#.23_OVERVIEW_OF_THE_FIRST_MAIN_CHAPTER_.23\|$\text{first main chapter}$]]$)$  and Reed-Solomon codes  $($see  [[Channel_Coding/Some_Basics_of_Algebra#.23_OVERVIEW_OF_THE_SECOND_MAIN_CHAPTER_.23\|$\text{second main chapter}$]]$)$  the code word length is  $n$  in each case,

	*the theory of convolutional codes is based on  "semi-infinite"  information and code sequences.  Similarly,  "maximum likelihood decoding"  using the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  per se yields the entire sequence.		*the theory of convolutional codes is based on  "semi-infinite"  information and code sequences.  Similarly,  "maximum likelihood decoding"  using the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  per se yields the entire sequence.

Guenter at 15:13, 22 November 2022

2022-11-22T15:13:56Z

← Older revision		Revision as of 17:13, 22 November 2022
Line 37:		Line 37:
	\hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.</math>		\hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.</math>

	Such a sequence without negative indices is called  semi–infinite.<br>		Such a sequence without negative indices is called  »'''semi–infinite'''«.<br>

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=

Guenter at 16:55, 16 November 2022

2022-11-16T16:55:31Z

← Older revision		Revision as of 18:55, 16 November 2022
Line 49:		Line 49:
	*the  $m$  previous information blocks  $\underline{u}_{i-1}$, ... , $\underline{u}_{i-m}$.<br>}}<br>		*the  $m$  previous information blocks  $\underline{u}_{i-1}$, ... , $\underline{u}_{i-m}$.<br>}}<br>

	[[File:~~EN_KC_T_3_1_S1~~.png\|right\|frame\|Dependencies for a convolutional encoder with  $m = 2$ ~~'''Korrektur'''~~\|class=fit]]		[[File:EN_KC_T_3_1_S1_neu.png\|right\|frame\|Dependencies for a convolutional encoder with  $m = 2$\|class=fit]]

	The diagram opposite illustrates this fact for the parameters		The diagram opposite illustrates this fact for the parameters

← Older revision		Revision as of 13:38, 30 November 2022
Line 12:		Line 12:
	*While for linear block codes  $($see  [[Channel_Coding/Objective_of_Channel_Coding#.23_OVERVIEW_OF_THE_FIRST_MAIN_CHAPTER_.23\|$\text{first main chapter}$]]$)$  and Reed-Solomon codes  $($see  [[Channel_Coding/Some_Basics_of_Algebra#.23_OVERVIEW_OF_THE_SECOND_MAIN_CHAPTER_.23\|$\text{second main chapter}$]]$)$  the code word length is  $n$  in each case,		*While for linear block codes  $($see  [[Channel_Coding/Objective_of_Channel_Coding#.23_OVERVIEW_OF_THE_FIRST_MAIN_CHAPTER_.23\|$\text{first main chapter}$]]$)$  and Reed-Solomon codes  $($see  [[Channel_Coding/Some_Basics_of_Algebra#.23_OVERVIEW_OF_THE_SECOND_MAIN_CHAPTER_.23\|$\text{second main chapter}$]]$)$  the code word length is  $n$  in each case,

	*the theory of convolutional codes is based on  "semi-infinite"  information and ~~code~~ sequences.  Similarly,  "maximum likelihood decoding"  using the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  per se yields the entire sequence.		*the theory of convolutional codes is based on  "semi-infinite"  information and encoded sequences.  Similarly,  "maximum likelihood decoding"  using the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  per se yields the entire sequence.


Line 102:		Line 102:
	#   There are efficient convolutional decoders,  for example the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  and the  [[Channel_Coding/Soft-in_Soft-Out_Decoder#BCJR_decoding:_Forward-backward_algorithm\| $\text{BCJR algorithm}$]],  which can process reliability information about the channel   ⇒   "soft decision input"  and provide reliability information about the decoding result   ⇒   "soft decision output".<br>		#   There are efficient convolutional decoders,  for example the  [[Channel_Coding/Decoding_of_Convolutional_Codes#Viterbi_algorithm_based_on_correlation_and_metrics\|$\text{Viterbi algorithm}$]]  and the  [[Channel_Coding/Soft-in_Soft-Out_Decoder#BCJR_decoding:_Forward-backward_algorithm\| $\text{BCJR algorithm}$]],  which can process reliability information about the channel   ⇒   "soft decision input"  and provide reliability information about the decoding result   ⇒   "soft decision output".<br>
	#   Please note:  The terms  "convolutional code"  and  "convolutional encoder"  should not be confused:		#   Please note:  The terms  "convolutional code"  and  "convolutional encoder"  should not be confused:
	::*The  "convolutional code"  ${\rm CC} \ (n, \ k, \ m)$   ⇒   $R = k/n$  is understood as  "the set of all possible ~~code~~ sequences  $\underline{x}$  $($at the output$)$  that can be generated with this code considering all possible information sequences  $\underline{u}$  $($at the input$)$".		::*The  "convolutional code"  ${\rm CC} \ (n, \ k, \ m)$   ⇒   $R = k/n$  is understood as  "the set of all possible encoded sequences  $\underline{x}$  $($at the output$)$  that can be generated with this code considering all possible information sequences  $\underline{u}$  $($at the input$)$".

	::*There are several  "convolutional encoders"  that realize the same  "convolutional code".<br>		::*There are several  "convolutional encoders"  that realize the same  "convolutional code".<br>
Line 180:		Line 180:
	#   The  "influence length"  $\nu$  is equal to the sum of all memory elements   ⇒   here  $\nu = 2$.<br>		#   The  "influence length"  $\nu$  is equal to the sum of all memory elements   ⇒   here  $\nu = 2$.<br>
	#  All memory elements are set to zero at the beginning of the coding  $($"initialization"$)$.		#  All memory elements are set to zero at the beginning of the coding  $($"initialization"$)$.
	#  The code defined herewith is the set of all possible ~~code~~ sequences  $\underline{x}$,  which result when all possible information sequences  $\underline{u}$  are entered.		#  The code defined herewith is the set of all possible encoded sequences  $\underline{x}$,  which result when all possible information sequences  $\underline{u}$  are entered.
	#  Both  $\underline{u}$  and  $\underline{x}$  are thereby (temporally) unbounded.<br>		#  Both  $\underline{u}$  and  $\underline{x}$  are thereby (temporally) unbounded.<br>

Line 215:		Line 215:
	x_4^{(3)}= u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.</math>		x_4^{(3)}= u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.</math>

	Thus the ~~code~~ sequence is after the multiplexer:     $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ \text{...})$.}}<br>		Thus the encoded sequence is after the multiplexer:     $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ \text{...})$.}}<br>

	== Exercises for the chapter==		== Exercises for the chapter==