Channel Coding/Examples of Binary Block Codes - Revision history

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

2026-03-16T13:46:43Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:46, 16 March 2026
Line 11:		Line 11:
	[[File:P ID2346 KC T 1 3 S1 v2.png\|right\|frame\|Various single parity-check codes  $(n = k + 1)$\|class=fit]]		[[File:P ID2346 KC T 1 3 S1 v2.png\|right\|frame\|Various single parity-check codes  $(n = k + 1)$\|class=fit]]
	:$$\underline{u} = (u_1, u_2,\hspace{0.05cm} \text{...} \hspace{0.05cm} , u_k) \hspace{0.3cm}$$		:$$\underline{u} = (u_1, u_2,\hspace{0.05cm} \text{...} \hspace{0.05cm} , u_k) \hspace{0.3cm}$$
	:$$\Rightarrow \hspace{0.3cm}		:$$\Rightarrow \hspace{0.3cm}\underline{x} = (x_1, x_2,\hspace{0.05cm}\text{...} \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} \text{...}\hspace{0.05cm} , u_k, p)\hspace{0.05cm}.$$
	\underline{x} = (x_1, x_2,\hspace{0.05cm}\text{...} \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} \text{...}\hspace{0.05cm} , u_k, p)
	\hspace{0.05cm}.$$

	The graphic shows three coding examples:		The graphic shows three coding examples:

Maintenance script: Add German interlanguage link

2026-03-16T12:27:32Z

Add German interlanguage link

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

	{{Display}}		{{Display}}
			[[de:Kanalcodierung/Beispiele_binärer_Blockcodes]]

Hwang at 14:42, 23 January 2023

2023-01-23T14:42:45Z

← Older revision		Revision as of 16:42, 23 January 2023
Line 68:		Line 68:

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 1:}$  We consider the  $\text{SPC (4, 3, 2)}$  and assume that the all-zero word was sent.  The table shows all possibilities that  $f$  bits are ~~corrupted~~ falsified and gives the respective syndrome  $s \in \{0, 1\}$.		$\text{Example 1:}$  We consider the  $\text{SPC (4, 3, 2)}$  and assume that the all-zero word was sent.  The table shows all possibilities that  $f$  bits are falsified and gives the respective syndrome  $s \in \{0, 1\}$.
	[[File:P ID2382 KC T 1 3 S1c.png\|right\|frame\|Possible received values at the  $\text{SPC (4, 3, 2)}$ \|class=fit]]		[[File:P ID2382 KC T 1 3 S1c.png\|right\|frame\|Possible received values at the  $\text{SPC (4, 3, 2)}$ \|class=fit]]

Guenter at 09:26, 22 November 2022

2022-11-22T09:26:22Z

Hwang at 10:10, 18 November 2022

2022-11-18T10:10:05Z

← Older revision		Revision as of 12:10, 18 November 2022
Line 312:		Line 312:
	*If two of the three parity equations are satisfied,  such as for the received word  $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,  then one parity bit has been corrupted '''KORREKTUR: falsified''' and the following also applies here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>		*If two of the three parity equations are satisfied,  such as for the received word  $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,  then one parity bit has been corrupted '''KORREKTUR: falsified''' and the following also applies here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>

	*With  $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$  only the equation  $\rm (I)$  is satisfied and the other two are not.  Thus,  the corruption of the fourth binary symbol can be corrected,  and it is also valid here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>		*With  $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$  only the equation  $\rm (I)$  is satisfied and the other two are not.  Thus,  the corruption '''KORREKTUR: falsification ''' of the fourth binary symbol can be corrected,  and it is also valid here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>

	*A transmission error of the second bit   ⇒   $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$  leads to the fact that all three parity equations are not fulfilled.  This error can also be clearly corrected since only  $u_2$  occurs in all equations.}}<br>		*A transmission error of the second bit   ⇒   $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$  leads to the fact that all three parity equations are not fulfilled.  This error can also be clearly corrected since only  $u_2$  occurs in all equations.}}<br>

Hwang at 10:03, 18 November 2022

2022-11-18T10:03:34Z

← Older revision		Revision as of 12:03, 18 November 2022
Line 268:		Line 268:


	[[File:P ID2351 KC T 1 3 S3c v2.png\|right\|frame\|Assignment  $\underline{u} → \underline{x}$  of the systematic $\text{(7, 4, 3)}$ Hamming code.\|class=fit]]		[[File:P ID2351 KC T 1 3 S3c v2.png\|right\|frame\|Assignment  $\underline{u} → \underline{x}$  of the systematic $\text{(7, 4, 3)}$ Hamming code\|class=fit]]
	In systematic coding of the  $\text{(7, 4, 3)}$ Hamming code		In systematic coding of the  $\text{(7, 4, 3)}$ Hamming code

Hwang at 09:59, 18 November 2022

2022-11-18T09:59:32Z

← Older revision		Revision as of 11:59, 18 November 2022
Line 227:		Line 227:
	\hspace{0.05cm}.$		\hspace{0.05cm}.$

	*For the AWGN channel,  no  [[Channel_Coding/Decoding_of_Linear_Block_Codes#~~Codiergewinn_.E2.80.93_Bitfehlerrate_bei_AWGN~~\|$\text{coding gain}$]]  can be achieved by a repetition code.}}<br>		*For the AWGN channel,  no  [[Channel_Coding/Decoding_of_Linear_Block_Codes#Coding_gain_-_bit_error_rate_with_AWGN\|$\text{coding gain}$]]  can be achieved by a repetition code.}}<br>

	== Hamming Codes ==		== Hamming Codes ==

Hwang at 09:52, 18 November 2022

2022-11-18T09:52:42Z

← Older revision		Revision as of 11:52, 18 November 2022
Line 190:		Line 190:

	where the following physical quantities are to be used:		where the following physical quantities are to be used:
	*the signal-to-noise ~~ration~~  $\rm (SNR)$  $\rho= 1/\sigma^2 = 2 \cdot E_{\rm S}/N_0$,<br>		*the signal-to-noise ratio  $\rm (SNR)$  $\rho= 1/\sigma^2 = 2 \cdot E_{\rm S}/N_0$,<br>

	*the energy  $E_{\rm S}$  per code symbol   ⇒   "symbol energy",<br>		*the energy  $E_{\rm S}$  per code symbol   ⇒   "symbol energy",<br>

Hwang at 09:51, 18 November 2022

2022-11-18T09:51:30Z

← Older revision		Revision as of 11:51, 18 November 2022
Line 182:		Line 182:
	<br>		<br>

	We now consider the  [[Channel_Coding/Channel_Models_and_Decision_Structures#~~AWGN_channel_at_Binary_Input~~\|$\text{AWGN channel}$]].  For uncoded transmission  $($or the repetition code with  $n=1)$  the received value is  $y = \tilde{x}+\eta$ , where  $\tilde{x} \in \{+1, -1\}$  denotes the information bit in bipolar signaling and  $\eta$  denotes the noise term.  To avoid confusion with the code parameter  $n$  we have renamed the noise:   $n → \eta$.<br>		We now consider the  [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input\|$\text{AWGN channel}$]].  For uncoded transmission  $($or the repetition code with  $n=1)$  the received value is  $y = \tilde{x}+\eta$ , where  $\tilde{x} \in \{+1, -1\}$  denotes the information bit in bipolar signaling and  $\eta$  denotes the noise term.  To avoid confusion with the code parameter  $n$  we have renamed the noise:   $n → \eta$.<br>

	For the error probability, with the  [[Theory_of_Stochastic_Signals/Gaussian_Distributed_Random_Variables#Exceedance_probability\|$\text{complementary Gaussian error integral}$]]  ${\rm Q}(x)$		For the error probability, with the  [[Theory_of_Stochastic_Signals/Gaussian_Distributed_Random_Variables#Exceedance_probability\|$\text{complementary Gaussian error integral}$]]  ${\rm Q}(x)$

Hwang at 09:46, 18 November 2022

2022-11-18T09:46:56Z

← Older revision		Revision as of 11:46, 18 November 2022
Line 122:		Line 122:
	*The probability for three or five bit errors,  however,  is orders of magnitude smaller than that for a single error.  The assumption of  "one bit error"  is therefore not unreasonable.<br>		*The probability for three or five bit errors,  however,  is orders of magnitude smaller than that for a single error.  The assumption of  "one bit error"  is therefore not unreasonable.<br>

	*Since the received value  $y_3$  is very close to the threshold  $G = 0$  it is assumed that exactly this bit has been corrupted '''KORREKTUR: falsified'''.  Thus,  with "~~Soft Decision~~",  the decision is for  $\underline{z} = (0, 1, 0, 0, 1)$   ⇒   $\underline{v} = (0, 1, 0, 0)$.  The block error probability  ${\rm Pr}(\underline{v} \ne \underline{u})$  is thus lowest.}}<br><br>		*Since the received value  $y_3$  is very close to the threshold  $G = 0$  it is assumed that exactly this bit has been corrupted '''KORREKTUR: falsified'''.  Thus,  with "soft decision",  the decision is for  $\underline{z} = (0, 1, 0, 0, 1)$   ⇒   $\underline{v} = (0, 1, 0, 0)$.  The block error probability  ${\rm Pr}(\underline{v} \ne \underline{u})$  is thus lowest.}}<br><br>

	== Repetition Codes==		== Repetition Codes==

← Older revision		Revision as of 11:26, 22 November 2022
Line 68:		Line 68:

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 1:}$  We consider the  $\text{SPC (4, 3, 2)}$  and assume that the all-zero word was sent.  The table shows all possibilities that  $f$  bits are corrupted ~~'''KORREKTUR:~~ falsified~~'''~~ and gives the respective syndrome  $s \in \{0, 1\}$.		$\text{Example 1:}$  We consider the  $\text{SPC (4, 3, 2)}$  and assume that the all-zero word was sent.  The table shows all possibilities that  $f$  bits are corrupted falsified and gives the respective syndrome  $s \in \{0, 1\}$.
	[[File:P ID2382 KC T 1 3 S1c.png\|right\|frame\|Possible received values at the  $\text{SPC (4, 3, 2)}$ \|class=fit]]		[[File:P ID2382 KC T 1 3 S1c.png\|right\|frame\|Possible received values at the  $\text{SPC (4, 3, 2)}$ \|class=fit]]

Line 118:		Line 118:
	::<math>\underline{Y} = (+1, -1, -1, +1, -1) \hspace{0.05cm}.</math>		::<math>\underline{Y} = (+1, -1, -1, +1, -1) \hspace{0.05cm}.</math>

	*In symbol notation,  this gives  $(0, 1, 1, 0, 1)$,  which is not a valid code word of  $\text{SPC (5, 4, 2)}$  ⇒   syndrome  $s = 1$.  So one,  three or five bits must have been ~~corrupted '''KORREKTUR:~~ falsified~~'''~~.<br>		*In symbol notation,  this gives  $(0, 1, 1, 0, 1)$,  which is not a valid code word of  $\text{SPC (5, 4, 2)}$  ⇒   syndrome  $s = 1$.  So one,  three or five bits must have been falsified.<br>

	*The probability for three or five bit errors,  however,  is orders of magnitude smaller than that for a single error.  The assumption of  "one bit error"  is therefore not unreasonable.<br>		*The probability for three or five bit errors,  however,  is orders of magnitude smaller than that for a single error.  The assumption of  "one bit error"  is therefore not unreasonable.<br>

	*Since the received value  $y_3$  is very close to the threshold  $G = 0$  it is assumed that exactly this bit has been ~~corrupted '''KORREKTUR:~~ falsified~~'''~~.  Thus,  with "soft decision",  the decision is for  $\underline{z} = (0, 1, 0, 0, 1)$   ⇒   $\underline{v} = (0, 1, 0, 0)$.  The block error probability  ${\rm Pr}(\underline{v} \ne \underline{u})$  is thus lowest.}}<br><br>		*Since the received value  $y_3$  is very close to the threshold  $G = 0$  it is assumed that exactly this bit has been falsified.  Thus,  with "soft decision",  the decision is for  $\underline{z} = (0, 1, 0, 0, 1)$   ⇒   $\underline{v} = (0, 1, 0, 0)$.  The block error probability  ${\rm Pr}(\underline{v} \ne \underline{u})$  is thus lowest.}}<br><br>

	== Repetition Codes==		== Repetition Codes==
Line 171:		Line 171:
	1.46\,\%\hspace{0.05cm}. </math>		1.46\,\%\hspace{0.05cm}. </math>

	*An  (undetected)  decoding error  $(v \ne u)$  results only when four or more bits have been ~~corrupted '''KORREKTUR:~~ falsified~~'''~~ within the six bit word.  As an approximation,  assuming that five or six bit errors are much less likely than four:		*An  (undetected)  decoding error  $(v \ne u)$  results only when four or more bits have been falsified within the six bit word.  As an approximation,  assuming that five or six bit errors are much less likely than four:

	::<math>{\rm Pr}(v \ne u) \approx {6 \choose 4} \cdot \varepsilon^{4} \cdot (1 - \varepsilon)^{2}=		::<math>{\rm Pr}(v \ne u) \approx {6 \choose 4} \cdot \varepsilon^{4} \cdot (1 - \varepsilon)^{2}=
Line 307:		Line 307:
	In the following  $\underline{v}$  denotes the decoding result; this should always match  $\underline{u} = (1,\ 0,\ 1,\ 0)$.		In the following  $\underline{v}$  denotes the decoding result; this should always match  $\underline{u} = (1,\ 0,\ 1,\ 0)$.

	Provided that at most one bit is ~~corrupted '''KORREKTUR:~~ falsified~~'''~~ in each code word,  the following statements are then valid:		Provided that at most one bit is falsified in each code word,  the following statements are then valid:
	*The received word  $\underline{y} = (1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1)$  satisfies all three parity equations. This means that not a single transmission error has occurred   ⇒   $\underline{y} = \underline{x}$   ⇒   $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>		*The received word  $\underline{y} = (1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1)$  satisfies all three parity equations. This means that not a single transmission error has occurred   ⇒   $\underline{y} = \underline{x}$   ⇒   $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>

	*If two of the three parity equations are satisfied,  such as for the received word  $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,  then one parity bit has been ~~corrupted '''KORREKTUR:~~ falsified~~'''~~ and the following also applies here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>		*If two of the three parity equations are satisfied,  such as for the received word  $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,  then one parity bit has been falsified and the following also applies here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>

	*With  $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$  only the equation  $\rm (I)$  is satisfied and the other two are not.  Thus,  the ~~corruption '''KORREKTUR:~~ falsification ~~'''~~ of the fourth binary symbol can be corrected,  and it is also valid here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>		*With  $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$  only the equation  $\rm (I)$  is satisfied and the other two are not.  Thus,  the falsification of the fourth binary symbol can be corrected,  and it is also valid here  $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>

	*A transmission error of the second bit   ⇒   $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$  leads to the fact that all three parity equations are not fulfilled.  This error can also be clearly corrected since only  $u_2$  occurs in all equations.}}<br>		*A transmission error of the second bit   ⇒   $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$  leads to the fact that all three parity equations are not fulfilled.  This error can also be clearly corrected since only  $u_2$  occurs in all equations.}}<br>