Channel Coding/Examples of Binary Block Codes - Revision history

Hwang at 14:42, 23 January 2023

2023-01-23T14:42:45Z

Guenter at 09:26, 22 November 2022

2022-11-22T09:26:22Z

Hwang at 10:10, 18 November 2022

2022-11-18T10:10:05Z

Hwang at 10:03, 18 November 2022

2022-11-18T10:03:34Z

Hwang at 09:59, 18 November 2022

2022-11-18T09:59:32Z

Hwang at 09:52, 18 November 2022

2022-11-18T09:52:42Z

Hwang at 09:51, 18 November 2022

2022-11-18T09:51:30Z

Hwang at 09:46, 18 November 2022

2022-11-18T09:46:56Z

Hwang at 12:39, 17 November 2022

2022-11-17T12:39:27Z

Hwang at 12:36, 17 November 2022

2022-11-17T12:36:43Z

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

@@ Line 68: / Line 68: @@
 {{GraueBox|TEXT=
-$\text{Example 1:}$&nbsp; We consider the&nbsp; $\text{SPC (4, 3, 2)}$&nbsp; and assume that the all-zero word was sent.&nbsp; The table shows all possibilities that&nbsp; $f$&nbsp; bits are corrupted '''KORREKTUR: falsified''' and gives the respective syndrome&nbsp; $s \in \{0, 1\}$.&nbsp;
+$\text{Example 1:}$&nbsp; We consider the&nbsp; $\text{SPC (4, 3, 2)}$&nbsp; and assume that the all-zero word was sent.&nbsp; The table shows all possibilities that&nbsp; $f$&nbsp; bits are corrupted falsified and gives the respective syndrome&nbsp; $s \in \{0, 1\}$.&nbsp;
 [[File:P ID2382 KC T 1 3 S1c.png|right|frame|Possible received values at the&nbsp; $\text{SPC (4, 3, 2)}$ |class=fit]]
@@ Line 118: / Line 118: @@
 ::<math>\underline{Y} =  (+1, -1, -1, +1, -1)  \hspace{0.05cm}.</math>
-*In symbol notation,&nbsp; this gives&nbsp; $(0, 1, 1, 0, 1)$,&nbsp; which is not a valid code word of&nbsp; $\text{SPC (5, 4, 2)}$&nbsp; &#8658; &nbsp; syndrome&nbsp; $s = 1$.&nbsp; So one,&nbsp; three or five bits must have been corrupted '''KORREKTUR: falsified'''.<br>
+*In symbol notation,&nbsp; this gives&nbsp; $(0, 1, 1, 0, 1)$,&nbsp; which is not a valid code word of&nbsp; $\text{SPC (5, 4, 2)}$&nbsp; &#8658; &nbsp; syndrome&nbsp; $s = 1$.&nbsp; So one,&nbsp; three or five bits must have been falsified.<br>
 *The probability for three or five bit errors,&nbsp; however,&nbsp; is orders of magnitude smaller than that for a single error.&nbsp; The assumption of&nbsp; "one bit error"&nbsp; is therefore not unreasonable.<br>
-*Since the received value&nbsp; $y_3$&nbsp; is very close to the threshold&nbsp; $G = 0$&nbsp; it is assumed that exactly this bit has been corrupted '''KORREKTUR: falsified'''.&nbsp; Thus,&nbsp; with "soft decision",&nbsp; the decision is for&nbsp; $\underline{z} = (0, 1, 0, 0, 1)$ &nbsp; &#8658; &nbsp; $\underline{v} = (0, 1, 0, 0)$.&nbsp; The block error probability&nbsp; ${\rm Pr}(\underline{v} \ne \underline{u})$&nbsp; is thus lowest.}}<br><br>
+*Since the received value&nbsp; $y_3$&nbsp; is very close to the threshold&nbsp; $G = 0$&nbsp; it is assumed that exactly this bit has been falsified.&nbsp; Thus,&nbsp; with "soft decision",&nbsp; the decision is for&nbsp; $\underline{z} = (0, 1, 0, 0, 1)$ &nbsp; &#8658; &nbsp; $\underline{v} = (0, 1, 0, 0)$.&nbsp; The block error probability&nbsp; ${\rm Pr}(\underline{v} \ne \underline{u})$&nbsp; is thus lowest.}}<br><br>
 == Repetition Codes==
@@ Line 171: / Line 171: @@
 .46\,\%\hspace{0.05cm}. </math>
-*An&nbsp; (undetected)&nbsp; decoding error&nbsp; $(v \ne u)$&nbsp; results only when four or more bits have been corrupted '''KORREKTUR: falsified''' within the six bit word.&nbsp; As an approximation,&nbsp; assuming that five or six bit errors are much less likely than four:
+*An&nbsp; (undetected)&nbsp; decoding error&nbsp; $(v \ne u)$&nbsp; results only when four or more bits have been falsified within the six bit word.&nbsp; As an approximation,&nbsp; 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}=
@@ Line 307: / Line 307: @@
 In the following&nbsp; $\underline{v}$&nbsp; denotes the decoding result; this should always match&nbsp; $\underline{u} = (1,\ 0,\ 1,\ 0)$.&nbsp;
-Provided that at most one bit is corrupted '''KORREKTUR: falsified''' in each code word,&nbsp; the following statements are then valid:
+Provided that at most one bit is falsified in each code word,&nbsp; the following statements are then valid:
 *The received word&nbsp; $\underline{y} = (1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1)$&nbsp; satisfies all three parity equations. This means that not a single transmission error has occurred &nbsp; &#8658; &nbsp; $\underline{y} = \underline{x}$ &nbsp; &#8658; &nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
-*If two of the three parity equations are satisfied,&nbsp; such as for the received word&nbsp; $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,&nbsp; then one parity bit has been corrupted '''KORREKTUR: falsified''' and the following also applies here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
+*If two of the three parity equations are satisfied,&nbsp; such as for the received word&nbsp; $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,&nbsp; then one parity bit has been falsified and the following also applies here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
-*With&nbsp; $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$&nbsp; only the equation&nbsp; $\rm (I)$&nbsp; is satisfied and the other two are not.&nbsp; Thus,&nbsp; the corruption '''KORREKTUR: falsification ''' of the fourth binary symbol can be corrected,&nbsp; and it is also valid here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
+*With&nbsp; $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$&nbsp; only the equation&nbsp; $\rm (I)$&nbsp; is satisfied and the other two are not.&nbsp; Thus,&nbsp; the falsification of the fourth binary symbol can be corrected,&nbsp; and it is also valid here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
 *A transmission error of the second bit &nbsp; &#8658; &nbsp; $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$&nbsp; leads to the fact that all three parity equations are not fulfilled.&nbsp; This error can also be clearly corrected since only&nbsp; $u_2$&nbsp; occurs in all equations.}}<br>

@@ Line 312: / Line 312: @@
 *If two of the three parity equations are satisfied,&nbsp; such as for the received word&nbsp; $\underline{y} =(1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 0)$,&nbsp; then one parity bit has been corrupted '''KORREKTUR: falsified''' and the following also applies here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
-*With&nbsp; $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$&nbsp; only the equation&nbsp; $\rm (I)$&nbsp; is satisfied and the other two are not.&nbsp; Thus,&nbsp; the corruption of the fourth binary symbol can be corrected,&nbsp; and it is also valid here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
+*With&nbsp; $\underline{y} = (1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1)$&nbsp; only the equation&nbsp; $\rm (I)$&nbsp; is satisfied and the other two are not.&nbsp; Thus,&nbsp; the corruption '''KORREKTUR: falsification ''' of the fourth binary symbol can be corrected,&nbsp; and it is also valid here&nbsp; $\underline{v} = \underline{u} = (1,\ 0,\ 1,\ 0)$.<br>
 *A transmission error of the second bit &nbsp; &#8658; &nbsp; $\underline{y} = (1,\ 1,\ 1,\ 0,\ 0,\ 1,\ 1)$&nbsp; leads to the fact that all three parity equations are not fulfilled.&nbsp; This error can also be clearly corrected since only&nbsp; $u_2$&nbsp; occurs in all equations.}}<br>

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

@@ Line 227: / Line 227: @@
 \hspace{0.05cm}.$
-*For the AWGN channel,&nbsp; no&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Codiergewinn_.E2.80.93_Bitfehlerrate_bei_AWGN|$\text{coding gain}$]]&nbsp; can be achieved by a repetition code.}}<br>
+*For the AWGN channel,&nbsp; no&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Coding_gain_-_bit_error_rate_with_AWGN|$\text{coding gain}$]]&nbsp; can be achieved by a repetition code.}}<br>
 == Hamming Codes ==

@@ Line 190: / Line 190: @@
 where the following physical quantities are to be used:
-*the signal-to-noise ration&nbsp; $\rm (SNR)$&nbsp; $\rho= 1/\sigma^2 =  2 \cdot E_{\rm S}/N_0$,<br>
+*the signal-to-noise ratio&nbsp; $\rm (SNR)$&nbsp; $\rho= 1/\sigma^2 =  2 \cdot E_{\rm S}/N_0$,<br>
 *the energy&nbsp; $E_{\rm S}$&nbsp; per code symbol &nbsp; &#8658; &nbsp; "symbol energy",<br>

@@ Line 182: / Line 182: @@
 <br>
-We now consider the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input|$\text{AWGN channel}$]].&nbsp; For uncoded transmission&nbsp; $($or the repetition code with&nbsp; $n=1)$&nbsp; the received value is&nbsp; $y = \tilde{x}+\eta$&nbsp;, where&nbsp; $\tilde{x} \in \{+1, -1\}$&nbsp; denotes the information bit in bipolar signaling and&nbsp; $\eta$&nbsp; denotes the noise term.&nbsp; To avoid confusion with the code parameter&nbsp; $n$&nbsp; we have renamed the noise: &nbsp; $n &#8594; \eta$.<br>
+We now consider the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input|$\text{AWGN channel}$]].&nbsp; For uncoded transmission&nbsp; $($or the repetition code with&nbsp; $n=1)$&nbsp; the received value is&nbsp; $y = \tilde{x}+\eta$&nbsp;, where&nbsp; $\tilde{x} \in \{+1, -1\}$&nbsp; denotes the information bit in bipolar signaling and&nbsp; $\eta$&nbsp; denotes the noise term.&nbsp; To avoid confusion with the code parameter&nbsp; $n$&nbsp; we have renamed the noise: &nbsp; $n &#8594; \eta$.<br>
 For the error probability, with the&nbsp; [[Theory_of_Stochastic_Signals/Gaussian_Distributed_Random_Variables#Exceedance_probability|$\text{complementary Gaussian error integral}$]]&nbsp; ${\rm Q}(x)$

@@ Line 103: / Line 103: @@
 {{GraueBox|TEXT=
-$\text{Example 3:}$&nbsp; Also with the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_Binary_Input|$\text{AWGN model}$]]&nbsp; error correction is possible when applying&nbsp; "soft decision".&nbsp; For the following we assume bipolar signaling:
+$\text{Example 3:}$&nbsp; Also with the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#AWGN_channel_at_binary_input|$\text{AWGN model}$]]&nbsp; error correction is possible when applying&nbsp; "soft decision".&nbsp; For the following we assume bipolar signaling:
 [[File:P ID2387 KC T 1 3 S1d v2.png|right|frame|To clarify&nbsp; "soft decision"&nbsp; at AWGN|class=fit]]
 *$x=0$  &nbsp; &rArr; &nbsp; $\tilde{x}= +1$,&nbsp; as well as

@@ Line 77: / Line 77: @@
 *The decoder detects that transmission errors have occurred&nbsp; (green background):
-:$${\rm Pr}(s=1) \hspace{-0.1cm} =  \hspace{-0.1cm}   \sum_{f=1 \atop f \hspace{0.1cm}{\rm ungerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f}$$
+:$${\rm Pr}(s=1) \hspace{-0.1cm} =  \hspace{-0.1cm}   \sum_{f=1 \atop f \hspace{0.1cm}{\rm odd} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f}$$
 :$$\Rightarrow \hspace{0.3cm} {\rm Pr}(s=1) \hspace{-0.1cm} =    {4 \choose 1} \cdot 0.01 \cdot 0.99^3 + {4 \choose 3} \cdot 0.01^3 \cdot 0.99 \approx 3.9\,\%\hspace{0.05cm}.$$