Channel Coding/Decoding of Linear Block Codes - Revision history

Maintenance script: Add German interlanguage link

2026-03-16T12:27:33Z

Add German interlanguage link

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

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

Guenter at 16:17, 30 November 2022

2022-11-30T16:17:28Z

← Older revision		Revision as of 18:17, 30 November 2022
Line 141:		Line 141:
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 3:}$  Starting from the systematic  $\text{(5, 2, 3)}$  code  $\mathcal{C} = \big \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \big \}$  the syndrome decoding procedure is now described in detail.		$\text{Example 3:}$  Starting from the systematic  $\text{(5, 2, 3)}$  code  $\mathcal{C} = \big \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \big \}$  the syndrome decoding procedure is now described in detail.
	[[File:~~EN_KC_T_1_5_S3b_neu1~~.png\|right\|frame\|Example  $\text{(5, 2, 3)}$ syndrome table with cosets ~~'''KORREKTUR: ""'''~~\|class=fit]]		[[File:EN_KC_T_1_5_S3b_neu2.png\|right\|frame\|Example  $\text{(5, 2, 3)}$ syndrome table with cosets\|class=fit]]
	*The generator matrix and the parity-check matrix are:		*The generator matrix and the parity-check matrix are:

Guenter at 09:39, 22 November 2022

2022-11-22T09:39:42Z

← Older revision		Revision as of 11:39, 22 November 2022
Line 87:		Line 87:

	Comparing the syndrome with the  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix\|$\text{parity-check equations}$]]  of the Hamming code,  we see that		Comparing the syndrome with the  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix\|$\text{parity-check equations}$]]  of the Hamming code,  we see that
	*most likely the fourth symbol  $(x_4 = u_4)$  of the code word has been ~~corrupted '''KORREKTUR:~~ falsified~~'''~~,<br>		*most likely the fourth symbol  $(x_4 = u_4)$  of the code word has been falsified,<br>

	*the code word estimator will thus yield the result  $\underline{z} = (0, 1, 1, 0, 0, 0, 1)$,<br>		*the code word estimator will thus yield the result  $\underline{z} = (0, 1, 1, 0, 0, 0, 1)$,<br>

	*the decision is correct only if only one bit was ~~corrupted '''KORREKTUR:~~ falsified~~'''~~ during transmission.<br><br>		*the decision is correct only if only one bit was falsified during transmission.<br><br>

	Below are the required corrections for the  $\text{(7, 4, 3)}$  Hamming code resulting from the calculated syndrome  $\underline{s}$  corresponding to the columns of the parity-check matrix:		Below are the required corrections for the  $\text{(7, 4, 3)}$  Hamming code resulting from the calculated syndrome  $\underline{s}$  corresponding to the columns of the parity-check matrix:
Line 200:		Line 200:
	<br>		<br>
	We now consider the  [[Digital_Signal_Transmission/Error_Probability_for_Baseband_Transmission#Definition_of_the_bit_error_rate\|$\text{bit error rate}$]]  for the following constellation:		We now consider the  [[Digital_Signal_Transmission/Error_Probability_for_Baseband_Transmission#Definition_of_the_bit_error_rate\|$\text{bit error rate}$]]  for the following constellation:
	[[File:EN_KC_T_1_5_S4.png\|right\|frame\|Bit error rate for the  $\text{(7, 4, 3)}$ Hamming code ~~'''Korrektur''' Gainn~~\|class=fit]]		[[File:EN_KC_T_1_5_S4.png\|right\|frame\|Bit error rate for the  $\text{(7, 4, 3)}$ Hamming code\|class=fit]]
	#Hamming code  $\text{HC (7, 4, 3)}$,<br>		#Hamming code  $\text{HC (7, 4, 3)}$,<br>
	#AWGN–channel, characterized by the quotient  $E_{\rm B}/N_0$  (in dB),<br>		#AWGN–channel, characterized by the quotient  $E_{\rm B}/N_0$  (in dB),<br>

Hwang at 11:27, 18 November 2022

2022-11-18T11:27:05Z

← Older revision		Revision as of 13:27, 18 November 2022
Line 250:		Line 250:
	The graphic shows the system model and gives exemplary values for the individual vectors.		The graphic shows the system model and gives exemplary values for the individual vectors.
	*The left part of the picture  (yellow background)  is valid for  "BSC"  with one bit error  $(0 → 1)$  at the third bit.		*The left part of the picture  (yellow background)  is valid for  "BSC"  with one bit error  $(0 → 1)$  at the third bit.
	*The right part of the picture  (green background)  is for  "BEC"  and shows two  ~~Erasures~~  $(\rm 1 → E)$  at the second and the fourth bit.		*The right part of the picture  (green background)  is for  "BEC"  and shows two  erasures  $(\rm 1 → E)$  at the second and the fourth bit.
	[[File:EN_KC_T_1_5_S5.png\|right\|frame\|Error correction with BSC and BEC]]		[[File:EN_KC_T_1_5_S5.png\|right\|frame\|Error correction with BSC and BEC]]

Hwang at 11:22, 18 November 2022

2022-11-18T11:22:30Z

← Older revision		Revision as of 13:22, 18 November 2022
Line 194:		Line 194:
	$\text{Conclusion:}$  From these examples it is already clear that the  »'''syndrome decoding means a considerable effort'''«,  if one cannot use certain properties e.g. cyclic codes.		$\text{Conclusion:}$  From these examples it is already clear that the  »'''syndrome decoding means a considerable effort'''«,  if one cannot use certain properties e.g. cyclic codes.

	*For large block code lengths, this method fails completely. Thus, to decode a  [https://en.wikipedia.org/wiki/BCH_code $\text{BCH ~~codes~~}$]  $($the abbreviation stands for their inventors '''B'''ose, '''C'''haudhuri, '''H'''ocquenghem$)$  with code parameters  $n = 511$,  $k = 259$  and  $d_{\rm min} = 61$,  one has to evaluate and store exactly  $2^{511-259} \approx 10^{76}$ error patterns of length  $511$.		*For large block code lengths, this method fails completely. Thus, to decode a  [https://en.wikipedia.org/wiki/BCH_code $\text{BCH code}$]  $($the abbreviation stands for their inventors '''B'''ose, '''C'''haudhuri, '''H'''ocquenghem$)$  with code parameters  $n = 511$,  $k = 259$  and  $d_{\rm min} = 61$,  one has to evaluate and store exactly  $2^{511-259} \approx 10^{76}$ error patterns of length  $511$.
	*Happily,  however,  there are special decoding algorithms for these and also for other codes of large block length,  which lead to success with less effort}}.		*Happily,  however,  there are special decoding algorithms for these and also for other codes of large block length,  which lead to success with less effort}}.

Hwang at 11:18, 18 November 2022

2022-11-18T11:18:02Z

← Older revision		Revision as of 13:18, 18 November 2022
Line 141:		Line 141:
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 3:}$  Starting from the systematic  $\text{(5, 2, 3)}$  code  $\mathcal{C} = \big \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \big \}$  the syndrome decoding procedure is now described in detail.		$\text{Example 3:}$  Starting from the systematic  $\text{(5, 2, 3)}$  code  $\mathcal{C} = \big \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \big \}$  the syndrome decoding procedure is now described in detail.
	[[File:EN_KC_T_1_5_S3b_neu1.png\|right\|frame\|Example  $\text{(5, 2, 3)}$ syndrome table with cosets\|class=fit]]		[[File:EN_KC_T_1_5_S3b_neu1.png\|right\|frame\|Example  $\text{(5, 2, 3)}$ syndrome table with cosets '''KORREKTUR: ""'''\|class=fit]]
	*The generator matrix and the parity-check matrix are:		*The generator matrix and the parity-check matrix are:

Hwang at 11:17, 18 November 2022

2022-11-18T11:17:05Z

← Older revision		Revision as of 13:17, 18 November 2022
Line 123:		Line 123:

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Conclusion:}$  Note that the error vector  $\underline{e}$  as well as the received vector  $\underline{y}$  is an element of  ${\rm GF}(2^n)$  unlike the syndrome  $\underline{s} \in {\rm GF}(2^m)$  with number  $m = n-k$  of parity-check equations. This means,  ~~That~~		$\text{Conclusion:}$  Note that the error vector  $\underline{e}$  as well as the received vector  $\underline{y}$  is an element of  ${\rm GF}(2^n)$  unlike the syndrome  $\underline{s} \in {\rm GF}(2^m)$  with number  $m = n-k$  of parity-check equations. This means,  that
	*the association between the syndrome  $\underline{s}$  and the error vector  $\underline{e}$  is not unique,  but		*the association between the syndrome  $\underline{s}$  and the error vector  $\underline{e}$  is not unique,  but

Hwang at 11:11, 18 November 2022

2022-11-18T11:11:44Z

← Older revision		Revision as of 13:11, 18 November 2022
Line 108:		Line 108:


	Under this assumption,  we briefly summarize the results of the last ~~pages~~:		Under this assumption,  we briefly summarize the results of the last sections:
	*Syndrome decoding is a realization possibility of maximum likelihood decoding of block codes.  One decides on the code word  $\underline{x}_i$   with the least Hamming distance to the received word  $\underline{y}$:		*Syndrome decoding is a realization possibility of maximum likelihood decoding of block codes.  One decides on the code word  $\underline{x}_i$   with the least Hamming distance to the received word  $\underline{y}$:

Hwang at 11:06, 18 November 2022

2022-11-18T11:06:03Z

← Older revision		Revision as of 13:06, 18 November 2022
Line 87:		Line 87:

	Comparing the syndrome with the  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix\|$\text{parity-check equations}$]]  of the Hamming code,  we see that		Comparing the syndrome with the  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix\|$\text{parity-check equations}$]]  of the Hamming code,  we see that
	*most likely the fourth symbol  $(x_4 = u_4)$  of the code word has been corrupted,<br>		*most likely the fourth symbol  $(x_4 = u_4)$  of the code word has been corrupted '''KORREKTUR: falsified''',<br>

	*the code word estimator will thus yield the result  $\underline{z} = (0, 1, 1, 0, 0, 0, 1)$,<br>		*the code word estimator will thus yield the result  $\underline{z} = (0, 1, 1, 0, 0, 0, 1)$,<br>

	*the decision is correct only if only one bit was corrupted during transmission.<br><br>		*the decision is correct only if only one bit was corrupted '''KORREKTUR: falsified''' during transmission.<br><br>

	Below are the required corrections for the  $\text{(7, 4, 3)}$  Hamming code resulting from the calculated syndrome  $\underline{s}$  corresponding to the columns of the parity-check matrix:		Below are the required corrections for the  $\text{(7, 4, 3)}$  Hamming code resulting from the calculated syndrome  $\underline{s}$  corresponding to the columns of the parity-check matrix:

Hwang at 10:59, 18 November 2022

2022-11-18T10:59:28Z

← Older revision		Revision as of 12:59, 18 November 2022
Line 17:		Line 17:
	*The vector  $\underline{v}$  after decoding  (at the sink)  should match the information word  $\underline{u}$  as well as possible.		*The vector  $\underline{v}$  after decoding  (at the sink)  should match the information word  $\underline{u}$  as well as possible.

	*That is:   The  '''block error probability'''  should be as small as possible:		*That is:   The  »'''block error probability'''«  should be as small as possible:
	::<math>{ \rm Pr(block\:error)} = { \rm Pr}( \underline{v} \ne \underline{u}) \stackrel{!}{=} { \rm minimum}\hspace{0.05cm}.</math>		::<math>{ \rm Pr(block\:error)} = { \rm Pr}( \underline{v} \ne \underline{u}) \stackrel{!}{=} { \rm minimum}\hspace{0.05cm}.</math>

Line 44:		Line 44:
	\hspace{0.05cm}.</math>		\hspace{0.05cm}.</math>

	A bit error at position  $i$   ⇒   $y_i ≠ x_i$  is expressed by the  '''error coefficient'''  $e_i = 1$.<br>		A bit error at position  $i$   ⇒   $y_i ≠ x_i$  is expressed by the  »'''error coefficient'''«  $e_i = 1$.<br>

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Definition:}$  The  '''syndrome'''  $\underline{s} = (s_0, s_1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, s_{m-1})$  is calculated  (as row resp. column vector)  from the received word  $\underline{y}$  and the parity-check matrix  $\boldsymbol{\rm H}$  as follows:		$\text{Definition:}$  The  »'''syndrome'''«  $\underline{s} = (s_0, s_1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, s_{m-1})$  is calculated  (as row resp. column vector)  from the received word  $\underline{y}$  and the parity-check matrix  $\boldsymbol{\rm H}$  as follows:

	::<math>\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H} }^{\rm T}\hspace{0.3cm}{\rm bzw.}\hspace{0.3cm}		::<math>\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H} }^{\rm T}\hspace{0.3cm}{\rm bzw.}\hspace{0.3cm}
Line 192:		Line 192:

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Conclusion:}$  From these examples it is already clear that the  '''syndrome decoding means a considerable effort''',  if one cannot use certain properties e.g. cyclic codes.		$\text{Conclusion:}$  From these examples it is already clear that the  »'''syndrome decoding means a considerable effort'''«,  if one cannot use certain properties e.g. cyclic codes.

	*For large block code lengths, this method fails completely. Thus, to decode a  [https://en.wikipedia.org/wiki/BCH_code $\text{BCH codes}$]  $($the abbreviation stands for their inventors '''B'''ose, '''C'''haudhuri, '''H'''ocquenghem$)$  with code parameters  $n = 511$,  $k = 259$  and  $d_{\rm min} = 61$,  one has to evaluate and store exactly  $2^{511-259} \approx 10^{76}$ error patterns of length  $511$.		*For large block code lengths, this method fails completely. Thus, to decode a  [https://en.wikipedia.org/wiki/BCH_code $\text{BCH codes}$]  $($the abbreviation stands for their inventors '''B'''ose, '''C'''haudhuri, '''H'''ocquenghem$)$  with code parameters  $n = 511$,  $k = 259$  and  $d_{\rm min} = 61$,  one has to evaluate and store exactly  $2^{511-259} \approx 10^{76}$ error patterns of length  $511$.
Line 216:		Line 216:

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Definition:}$  We refer as  '''coding gain'''  of a considered system configuration,		$\text{Definition:}$  We refer as  »'''coding gain'''«  of a considered system configuration,
	*characterized by its code and		*characterized by its code and
	*the way it is decoded,		*the way it is decoded,