View source for Channel Coding/Bounds for Block Error Probability

 
{{Header
|Untermenü=Binary Block Codes for Channel Coding 
|Vorherige Seite=Decoding of Linear Block Codes
|Nächste Seite=Information Theoretical Limits of Channel Coding
}}

== Distance spectrum of a linear code ==
<br>
We further assume a linear and binary&nbsp; $(n, \hspace{0.05cm} k)$ block code&nbsp; $\mathcal{C}$.&nbsp; A major goal of code design is to keep the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Block_diagram_and_requirements|$\text{block error probability}$]]&nbsp; ${\rm Pr}(\underline{u} \ne \underline{v}) = {\rm Pr}(\underline{z} \ne \underline{x})$&nbsp; as low as possible.&nbsp; This is achieved by,&nbsp; among other things

*the minimum distance&nbsp; $d_{\rm min}$&nbsp; between two code words&nbsp; $\underline{x}$&nbsp; and&nbsp; $\underline{x}\hspace{0.05cm}'$&nbsp; is as large as possible,&nbsp; so that one can correct up to&nbsp; $t = &lfloor;(d_{\rm min}-1)/2&rfloor;$&nbsp; bit errors;<br>

*at the same time this  minimum distance&nbsp; $d_{\rm min}$&nbsp;  occurs as rarely as possible,&nbsp; given all the allowed code words.<br><br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  We denote the&nbsp; &raquo;'''number'''&laquo;&nbsp; of code words&nbsp; $\underline{x}\hspace{0.05cm}' \in \mathcal{C}$&nbsp; with Hamming distance&nbsp; $i$&nbsp; from the considered code word&nbsp; $\underline{x}$&nbsp; of the same code&nbsp; $\mathcal{C}$&nbsp; with&nbsp; $W_i(\underline{x})$,&nbsp; where holds:

::<math>W_i(\underline{x}) = \big \vert \hspace{0.05cm} \left \{ 
\underline{x}  \hspace{0.05cm}, \underline{x}{\hspace{0.05cm}' \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm}\vert\hspace{0.1cm}
d_{\rm H}(\underline{x}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}\hspace{0.05cm}'
) = i  \right \} \hspace{0.05cm} \big \vert\hspace{0.05cm}.</math>

*The magnitude strokes of the absolute value here denote the number of code words&nbsp; $\underline{x}\hspace{0.05cm}'$, that satisfy the condition&nbsp; $d_{\rm H}(\underline{x}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}\hspace{0.05cm}'
) = i $.&nbsp;

*This value is also called&nbsp; "multiplicity".}}


{{GraueBox|TEXT=  
$\text{Example 1:}$&nbsp;  We consider the&nbsp; $(5, \, 2)$ block code&nbsp; $\mathcal{C}$&nbsp; with generator matrix 
[[File:P ID2365 KC T 1 6 S1 neu.png|right|frame|Hamming distances between all code words|class=fit]]
:<math>{ \boldsymbol{\rm G} } 
=  \begin{pmatrix}
		1 &0 &1 &1 &0 \\
		0 &1 &0 &1 &1
	\end{pmatrix} \hspace{0.05cm}.</math>

The table shows the Hamming distances 
*between all code words&nbsp; $\underline{x}_i$
 
*to the reference words&nbsp; $\underline{x}_0$, ... , $\underline{x}_3$.


One recognizes: &nbsp; Independently of the reference word&nbsp; $\underline{x}_i$&nbsp; holds:

::<math>W_0 = 1 \hspace{0.05cm}, \hspace{0.5cm}W_1 = W_2 = 0 \hspace{0.05cm},\hspace{0.5cm}
 W_3 = 2 \hspace{0.05cm},\hspace{0.5cm} W_4 = 1</math>
::<math> \Rightarrow\hspace{0.3cm} d_{\rm min} = 3\hspace{0.05cm}.</math>}}
<br clear=all>

Not only in this example,&nbsp; but in any linear code,&nbsp; the same multiplicities&nbsp; $W_i$&nbsp; result for each code word.&nbsp; Furthermore,&nbsp; since the all-zero word &nbsp; $\underline{0} = (0, 0,\text{ ...} \hspace{0.05cm}, 0)$ &nbsp; is part of every linear binary code,&nbsp; the above definition can also be formulated as follows:<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  The&nbsp; &raquo;'''distance spectrum'''&laquo;&nbsp; of a linear binary&nbsp; $(n, \hspace{0.03cm} k)$&nbsp; block code is the set &nbsp; $\{W_i \}$&nbsp; with&nbsp; $i = 0,\ 1,$ ... ,&nbsp; $n$.&nbsp; 
*Here,&nbsp; $W_i$&nbsp; gives the number of code words&nbsp; $\underline{x} \in \mathcal{C}$&nbsp; with Hamming weight&nbsp; $w_{\rm H}(\underline{x}) = i$. 

*Often one describes the set&nbsp; $\hspace{0.05cm}\{W_i \}\hspace{0.05cm}$&nbsp; also as a polynomial with a pseudo-variable&nbsp; $X$:


::<math>\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm}
W(X) = \sum_{i=0  }^{n}  W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.</math>

*$W(X)$&nbsp; is also called the &nbsp;  &raquo;'''weight enumerator function'''&laquo;.}}<br>

*For example,&nbsp; the weight enumerator  function of the&nbsp;  $(5, \hspace{0.02cm} 2)$&nbsp; code&nbsp;  $\mathcal{C} = \left  \{ \hspace{0.05cm}(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) \hspace{0.05cm} \right \}$&nbsp;  of&nbsp;  $\text{Example 1}$:

::<math>W(X) = 1 + 2 \cdot X^{3} + X^{4}\hspace{0.05cm}.</math>

*As can be seen for the&nbsp; $(7, \hspace{0.02cm}4, \hspace{0.02cm}3)$ Hamming code from the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Some_properties_of_the_.287.2C_4.2C_3.29_Hamming_code |$\text{table of its code words}$]]:

::<math>W(X) = 1 + 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}\hspace{0.05cm}.</math>

*The transformation of the distance spectrum&nbsp; $\hspace{0.01cm}\{W_i \}\hspace{0.01cm}$&nbsp; into the weight enumerator function&nbsp; $W(X)$&nbsp; also offers great numerical advantages in some exercises.&nbsp; For example,&nbsp; if the weight enumerator function&nbsp; $W(X)$&nbsp; of a&nbsp; $(n, \hspace{0.03cm} k)$ block code&nbsp; $\mathcal{C}$&nbsp; is known,&nbsp; then for the corresponding&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Representation_of_SPC_and_RC_as_dual_codes|$\text{dual}$]]&nbsp; $(n, \hspace{0.03cm} n-k)$&nbsp; code&nbsp; $\mathcal{C}_{\rm dual}$:

::<math>W_{\rm dual}(X) = \frac{(1+X)^n}{2^k} \cdot W \left ( \frac{1-X}{1+X} \right )\hspace{0.05cm}.</math>

{{GraueBox|TEXT=  
$\text{Example 2:}$&nbsp;  The weight enumerator function&nbsp; $W(X)$&nbsp; of the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|$\text{single parity&ndash;check codes}$]]&nbsp; with &nbsp; $n = 6$,&nbsp; $k = 5$ &nbsp; &#8658; &nbsp; $\text{SPC (6, 5)}$&nbsp; is obtained by comparing all&nbsp; $2^5 = 32$&nbsp; code words with the all-zero word: 

::<math>W_{\rm SPC\hspace{0.03cm}(6,\hspace{0.08cm}5)}(X) = 1 + 15 \cdot X^{2} + 15 \cdot X^{4} + X^{6}\hspace{0.05cm}.</math>

Considering the above equation, you get the same result much faster:
*The dual code to&nbsp; $\text{SPC (6, 5)}$&nbsp;   is the&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|$\text{repetition code}$]]&nbsp;  $\text{RC (6, 1)}$&nbsp; with only two code words&nbsp; $(0, 0, 0, 0, 0, 0)$&nbsp; and&nbsp; $(1, 1, 1, 1, 1, 1)$:

::<math>W_{\rm RC\hspace{0.03cm}(6,\hspace{0.08cm}1)}(X) = 1 + X^{6}\hspace{0.05cm}.</math>

*From this it follows for the weight enumerator function of the&nbsp; $\text{SPC (6, 5)}$&nbsp; according to the above equation with&nbsp; $k = 1$:

::<math>W_{\rm SPC\hspace{0.03cm}(6,\hspace{0.08cm}5)}(X) = \frac{(1+X)^6}{2^1} \cdot W \left [1 \hspace{-0.05cm}+\hspace{-0.05cm} \left ( \frac {1\hspace{-0.05cm}-\hspace{-0.05cm}X}{1\hspace{-0.05cm}+\hspace{-0.05cm}X}\right )^6 \right ] =  1/2 \cdot \big [( 1\hspace{-0.05cm}+\hspace{-0.05cm}X) ^6 \hspace{-0.05cm}+\hspace{-0.05cm} ( 1-X) ^6 \big ] = 1 \hspace{-0.05cm}+\hspace{-0.05cm} 15 \cdot X^{2} \hspace{-0.05cm}+\hspace{-0.05cm} 15 \cdot X^{4} \hspace{-0.05cm}+\hspace{-0.05cm} X^{6}\hspace{0.05cm}.</math>}}<br>

== Union Bound of the block error probability ==
<br>
We consider as in&nbsp; $\text{Example 1}$&nbsp; the distance spectrum of the&nbsp; $(5, \hspace{0.02cm} 2)$&nbsp; block code&nbsp; $\mathcal{C} = \{\underline{x}_0, \underline{x}_1, \underline{x}_2, \underline{x}_3 \}$&nbsp;&nbsp; and assume that the code word&nbsp; $\underline{x}_0$&nbsp; has been sent.&nbsp; The graphic illustrates the situation.

*In the error-free case,&nbsp; the code word estimator would then return&nbsp; $\underline{z} = \underline{x}_0$.&nbsp; 

*Otherwise,&nbsp; a block error would occur&nbsp; (that is, &nbsp; $\underline{z} \ne \underline{x}_0$&nbsp; and accordingly&nbsp; $\underline{v} \ne \underline{u}_0)$&nbsp; with probability
[[File:EN_KC_T_1_6_S2b.png|right|frame|Derivation of the Union Bound |class=fit]]

:$${\rm Pr(block\:error)} = {\rm Pr}\left (\big [\underline{x}_{\hspace{0.02cm}0} \hspace{-0.07cm}\mapsto \hspace{-0.07cm}\underline{x}_{\hspace{0.02cm}1}\big ] \hspace{-0.07cm}\cup\hspace{-0.07cm}\big [\underline{x}_{\hspace{0.02cm}0} \hspace{-0.07cm}\mapsto \hspace{-0.07cm} \underline{x}_{\hspace{0.02cm}2}\big ] \hspace{-0.07cm}\cup\hspace{-0.07cm}\big [\underline{x}_{\hspace{0.02cm}0} \hspace{-0.07cm}\mapsto \hspace{-0.07cm} \underline{x}_{\hspace{0.02cm}3}\big ] \right ).$$

&rArr; &nbsp;The event&nbsp; "falsification from &nbsp; $\underline{x}_0$ &nbsp; to&nbsp; $\underline{x}_1$"&nbsp; occurs for a given received word &nbsp; $\underline{y}$ &nbsp; according to the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Definitions_of_the_different_optimal_receivers|"maximum likelihood block-wise decision rule"]]&nbsp; exactly when for the conditional probability density function  holds:

::<math>\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big ] \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm}
f(\underline{x}_{\hspace{0.02cm}0}\hspace{0.02cm} | \hspace{0.05cm}\underline{y}) < f(\underline{x}_{\hspace{0.02cm}1}\hspace{0.02cm} | \hspace{0.05cm}\underline{y})
 \hspace{0.05cm}.</math>

&rArr; &nbsp; Since the events&nbsp;  $\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big ] $,&nbsp; $\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}\big ] $,&nbsp; $\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}\big ] $&nbsp; are not necessarily&nbsp; "disjoint" &nbsp; (which would thus be mutually exclusive),&nbsp; the&nbsp; [[Theory_of_Stochastic_Signals/Set_Theory_Basics#Union_set|$\text{probability of the union set}$]]&nbsp; is less than or equal to the sum of the individual probabilities:

:<math>{\rm Pr(block\:error)} \le {\rm Pr}\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big ] \hspace{0.05cm}+\hspace{0.05cm}{\rm Pr}\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}\big ] \hspace{0.05cm}+ \hspace{0.05cm}{\rm Pr}\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}\big ]  \hspace{0.05cm}.</math>

#One calls this upper bound for the block error probability the&nbsp; &raquo;'''Union Bound'''&laquo;. 
#This was already used in the chapter&nbsp; [[Digital_Signal_Transmission/Approximation_of_the_Error_Probability#Union_Bound_-_Upper_bound_for_the_error_probability|"Approximation of the error probability"]]&nbsp; of the book&nbsp; "Digital Signal Transmission".<br>


We generalize now and formalize these results under the assumption that both&nbsp; $\underline{x}$&nbsp; and&nbsp; $\underline{x}\hspace{0.05cm}'$&nbsp; belong to the code&nbsp; $\mathcal{C}$&nbsp;. 

{{BlaueBox|TEXT=  
$\text{Then the following calculation rules apply:}$&nbsp;  
*$\rm Block\:error\:probability$:

::$${\rm Pr(block\:error)} = {\rm Pr} \left ( \bigcup_{\underline{x}\hspace{0.05cm}' \ne \underline{x} } \hspace{0.15cm}\big [\underline{x} \mapsto \underline{x}\hspace{0.05cm}'\big] \right )\hspace{0.05cm},$$

*Upper bound &nbsp; &rArr; &nbsp; $\text{Union Bound}$:

::$${\rm Pr(Union \hspace{0.15cm}Bound)} \le \sum_{\underline{x}\hspace{0.05cm}' \ne \underline{x} } \hspace{0.15cm} {\rm Pr}\big[\underline{x} \mapsto \underline{x}\hspace{0.05cm}'\big] \hspace{0.05cm},$$

* $\text{Pairwise error probability}$&nbsp; (according to the maximum-a- posteriori resp. maximum likelihood criterion):

::$${\rm Pr}\hspace{0.02cm}\big[\underline{x} \mapsto \underline{x}\hspace{0.05cm}'\big] = {\rm Pr} \big [
p(\underline{x}\hspace{0.05cm}\vert \hspace{0.05cm}\underline{y}) \le p(\underline{x}\hspace{0.05cm}'\hspace{0.05cm} \vert \hspace{0.05cm}\underline{y}) \big ]
 \hspace{0.05cm}.$$}}


In the next sections,&nbsp; these results are applied to different channels.<br>

== Union Bound for the BSC model ==
<br>
We further consider the exemplary&nbsp; $(5, \hspace{0.02cm} 2)$ code:&nbsp; 
[[File:EN_KC_T_1_6_S2.png|right|frame|BSC model and maximum likelihood detection|class=fit]] 
:$$\mathcal{C} = \left  \{ \hspace{0.05cm}(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) \hspace{0.05cm} \right \}.$$
For the digital channel we use the&nbsp; [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC| $\text{BSC model}$]]&nbsp; ("Binary Symmetric Channel"):

::<math>{\rm Pr}(y = 1 \hspace{0.05cm} | \hspace{0.05cm}x = 0 )  =  {\rm Pr}(y = 0 \hspace{0.05cm} | \hspace{0.05cm}x = 1 ) = {\rm Pr}(e = 1) = \varepsilon \hspace{0.05cm},</math>
::<math>{\rm Pr}(y = 0 \hspace{0.05cm} | \hspace{0.05cm}x = 0 )  =  {\rm Pr}(y = 1 \hspace{0.05cm} | \hspace{0.05cm}x = 1 ) = {\rm Pr}(e = 0) = 1 -\varepsilon \hspace{0.05cm}.</math>

Then holds: 
#The code words&nbsp; $\underline{x}_0 = (0, 0, 0, 0, 0)$&nbsp; and&nbsp; $\underline{x}_1 = (0, 1, 0, 1, 1)$&nbsp; differ in&nbsp; $d = 3$&nbsp; bits;&nbsp; $d$&nbsp; is the [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|$\text{Hamming distance}$]]&nbsp; between&nbsp; $\underline{x}_0$&nbsp; and&nbsp; $\underline{x}_1$. 
#An incorrect decoding result &nbsp; $\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big] $&nbsp; is obtained whenever at least two of the three bits at bit positions 2, 4, and 5 are falsified. 
#In contrast, the bit positions 1 and 3 do not matter here, since they are the same for&nbsp; $\underline{x}_0$&nbsp; and &nbsp;$\underline{x}_1$.


Since the considered code can correct&nbsp; $t = &lfloor;(d-1)/2&rfloor; = 1$&nbsp;  errors:
::<math>{\rm Pr}\big [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big ]  \hspace{-0.1cm} =  \hspace{-0.1cm}    \sum_{i=t+1  }^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i} =  {3 \choose 2} \cdot \varepsilon^{2} \cdot (1 - \varepsilon) + 
{3 \choose 3} \cdot \varepsilon^{3} =3 \cdot \varepsilon^2 \cdot (1 - \varepsilon)  + \varepsilon^3  = {\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}\big]\hspace{0.05cm}.</math>

This takes into account that &nbsp; $\underline{x}_0 = (0, 0, 0, 0, 0)$ &nbsp; and &nbsp; $\underline{x}_2 = (1, 0, 1, 1, 0)$ &nbsp; also differ in three bit positions.

On the other hand,&nbsp; the code words &nbsp; $\underline{x}_0 = (0, 0, 0, 0, 0)$ &nbsp; and &nbsp; $\underline{x}_3 = (1, 1, 1, 0, 1)$ &nbsp; differ in four bit positions: 
*Wrong decoding of the block therefore certainly occurs if four or three bits are falsified.
 
*A corruption '''KORREKTUR: falsification''' of two bits results in a block error with &nbsp;$50\%$&nbsp; probability,&nbsp; if one assumes a random decision for this&nbsp; (last term).

::<math>{\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}\big]  = \varepsilon^4 + 4 \cdot \varepsilon^3 \cdot (1 - \varepsilon)    +  {1}/{2} \cdot 6 \cdot \varepsilon^2 \cdot (1 - \varepsilon)^2 \hspace{0.05cm}.</math>

*This results in the "Union Bound":

::<math>{\rm Pr(Union \hspace{0.15cm}Bound)} = {\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}1}\big] +{\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}2}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}3}\big] \ge {\rm Pr(block\hspace{0.15cm}error)}
.</math>

{{GraueBox|TEXT=  
$\text{Example 3:}$&nbsp;  The table summarizes the results for different values of the BSC parameter&nbsp; $\varepsilon$&nbsp;.<br>
[[File:P ID2367 KC T 1 6 S3 neu.png|right|frame|Numeric Union Bound for the considered&nbsp; $\text{(5, 2)}$ code|class=fit]]

It is worth mentioning that the completely different probabilities to be calculated&nbsp; 
*${\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}1}\big]=3 \cdot \varepsilon^2 \cdot (1 - \varepsilon)  + \varepsilon^3  = {\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}\big]\hspace{0.05cm},$&nbsp;
 
*${\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}3}\big]= \varepsilon^4 + 4 \cdot \varepsilon^3 \cdot (1 - \varepsilon)    +  {1}/{2} \cdot 6 \cdot \varepsilon^2 \cdot (1 - \varepsilon)^2 \hspace{0.05cm},$&nbsp; 


give exactly the same numerical result.}}<br>

== The upper bound according to Bhattacharyya ==
<br>
Another upper bound on the block error probability was given by&nbsp; [https://en.wikipedia.org/wiki/Anil_Kumar_Bhattacharya $\text{Anil Kumar Bhattacharyya}$]&nbsp;:

::<math>{\rm Pr(block\:error)} \le W(X = \beta) -1 = {\rm Pr(Bhattacharyya)}
 \hspace{0.05cm}.</math>

It should be noted that:
*$W(X)$&nbsp; is the above defined&nbsp; [[Channel_Coding/Limits_for_Block_Error_Probability#Distance_spectrum_of_a_linear_code|$\text{weight enumerator function}$]] characterizing the channel code used.<br>

*The&nbsp; "Bhattacharyya parameter"&nbsp; $\beta$&nbsp; identifies the digital channel.&nbsp; For example:

::<math>\beta = \left\{ \begin{array}{c} \lambda \\  \sqrt{4 \cdot \varepsilon \cdot (1- \varepsilon)}\\ 
 {\rm e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm}E_{\rm B}/N_0}   \end{array} \right.\quad
\begin{array}{*{1}c} {\rm for \hspace{0.15cm}BEC\hspace{0.15cm}model},\\ 
  {\rm for \hspace{0.15cm}BSC\hspace{0.15cm}model}, \\   {\rm for\hspace{0.15cm}AWGN\hspace{0.15cm} model}. \end{array}</math>

*The&nbsp; "Bhattacharyya Bound"&nbsp; is always&nbsp; (and usually significantly)&nbsp; above the curve for the "Union Bound". With the goal of finding a uniform bound for all channels,&nbsp; much coarser estimates must be made here than for the&nbsp; "Union Bound".<br><br>

We restrict ourselves here to the&nbsp; &raquo;<b>Bhattacharyya bound for the BSC model</b>&laquo;. 
*For its pairwise error probability was derived in front:

::<math>{\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big]  =    \sum_{i= \left\lfloor (d-1)/2 \right\rfloor}^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i}  =    \sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i} \cdot \varepsilon^{i} \cdot (1 - \varepsilon)^{d-i}\hspace{0.05cm}.</math>

:Here,&nbsp; $\varepsilon = {\rm Pr}(y = 1\hspace{0.04cm}|\hspace{0.04cm} x = 0) = {\rm Pr}(y = 0\hspace{0.04cm}|\hspace{0.04cm} x = 1)< 0.5$&nbsp; denotes the BSC model,&nbsp; and&nbsp; $d = d_{\rm H}(\underline{x}_0,\, \underline{x}_1)$&nbsp; indicates the Hamming distance between all code words.<br>

*To arrive at the Bhattacharyya bound, the following estimates must be made:&nbsp; For all&nbsp; $i < d$&nbsp; holds&nbsp; $\varepsilon^{i} \cdot  (1 - \varepsilon)^{d-i} \le  (1 - \varepsilon)^{d/2}$:

::<math>{\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big]  \le  \big[\varepsilon \cdot (1 - \varepsilon)\big]^{d/2} \cdot \sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i}   \hspace{0.05cm}.</math>

*Change with respect to the lower limit of the indexing variable&nbsp; $i$:

::<math>\sum_{i= \left\lceil d/2 \right\rceil }^{d} {d \choose i} \hspace{0.15cm} < \hspace{0.15cm} \sum_{i= 0 }^{d} {d \choose i}  = 2^d\hspace{0.05cm},
\hspace{0.2cm}\beta = 2 \cdot  \sqrt{\varepsilon \cdot (1 - \varepsilon)} 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm Pr}\big[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}\big] = \beta^{d}
\hspace{0.05cm}.</math>

*Resort according to Hamming weights&nbsp; $W_i$&nbsp; $($Hamming distance&nbsp; $d = i$&nbsp; occurs&nbsp; $W_i$&nbsp; times$)$:

::<math>{\rm Pr(block\:error)} \hspace{0.1cm} \le \hspace{0.1cm} \sum_{i= 1 }^{n} W_i \cdot \beta^{i} = 1 +  W_1 \cdot \beta + W_2 \cdot \beta^2 + \hspace{0.05cm}\text{ ...} \hspace{0.05cm}+ W_n \cdot \beta^n
 \hspace{0.05cm}.</math>

*With the weight enumerator function&nbsp; $W(X)= 1 + W_1 \cdot  X + W_2 \cdot  X^2 + \text{...} + W_n \cdot  X^n$:

::<math>{\rm Pr(block\:error)} \le W(X = \beta) -1= {\rm Pr(Bhattacharyya)} 
 \hspace{0.05cm}.</math>

{{GraueBox|TEXT=  
$\text{Example 4:}$&nbsp;  The table summarizes the Bhattacharyya results for different values of the BSC parameter&nbsp; $\varepsilon$&nbsp; valid for the&nbsp; [[Channel_Coding/Limits_for_Block_Error_Probability#Distance_spectrum_of_a_linear_code|$\text{example $\text{(5, 2)}$ code}$]].
[[File:P ID2370 KC T 1 6 S4.png|right|frame|"Union Bound"&nbsp; vs.&nbsp; "Bhattacharyya Bound"&nbsp; valid for BSC model|class=fit]]
 
*For this one applies: 
:$$W_0 = 1, \ \ W_1 = W_2 = 0,  \ \ W_3 = 2,   \ \ W_4 = 1$$
:$$\Rightarrow\hspace{0.3cm} W(X) = 1 +  2 \cdot X^3 +  X^4.$$

*Thus,&nbsp; the Bhattacharyya bound can be calculated:
::<math>  {\rm Pr(Bhattacharyya)} = W(\beta) -1 = 2 \cdot \beta^3 + \beta^4\hspace{0.05cm}.</math>

*This provides a&nbsp; (often rough)&nbsp; bound on the block error probability:
::<math> {\rm Pr(block\:error)}  
 \le {\rm Pr(Bhattacharyya)}
\hspace{0.05cm}.</math>}}


{{BlaueBox|TEXT=  
$\text{Conclusions:}$&nbsp;  Based on&nbsp; [[Channel_Coding/Limits_for_Block_Error_Probability#Union_Bound_for_the_BSC_model|$\text{Example 3}$]]&nbsp; and&nbsp; $\text{Example 4}$&nbsp; (in this section)&nbsp; for the simple&nbsp; $\text{(5, 2)}$&nbsp;  block code,&nbsp; though of little practical relevance,&nbsp; and in anticipation of&nbsp; $\text{Example 5}$&nbsp; (in the next section)&nbsp; for the&nbsp; $\text{(7,&nbsp;4,&nbsp;3)}$&nbsp; Hamming code,&nbsp; we summarize:
#The block error probability of a coding system is often not analytically specifiable and must be determined by simulation.&nbsp; The same applies to the bit error probability.<br>
#The&nbsp; &raquo;'''Union Bound'''&laquo;&nbsp; provides an upper bound for the block error probability.&nbsp; For many applications&nbsp; $($especially short codes$)$&nbsp; the Union Bound is only slightly above the actual error probability.<br>
#The &nbsp;&raquo;'''Bhattacharyya Bound'''&laquo;&nbsp; for the BEC channel is about a factor&nbsp; $2$&nbsp; above the&nbsp; Union Bound&nbsp; &ndash; see&nbsp; [[Aufgaben:Exercise_1.14:_Bhattacharyya_Bound_for_BEC|$\text{Exercise 1.14}$]].&nbsp; For the BSC and the AWGN channel,&nbsp; the gap is much larger.&nbsp; The factor&nbsp; $10$&nbsp; (and more)&nbsp; is not uncommon.<br>
#The Bhattacharyya Bound &nbsp; &rArr; &nbsp; "$W(\beta) - 1$" &nbsp; looks very simple at first sight.&nbsp; Nevertheless,&nbsp; one needs also here knowledge about the exact weight function&nbsp; $W(\xi)$&nbsp; of the code.<br>
#If the transmission channel&nbsp; $($BEC,&nbsp; BSC,&nbsp; AWGN&nbsp; or variations thereof$)$&nbsp; and its parameters are known,&nbsp; there is nothing to be said against using the&nbsp; (more accurate)&nbsp; "Union Bound"&nbsp; as an upper bound for the block error probability.}}<br>

== Bounds for the (7, 4, 3) Hamming code at the AWGN channel ==
<br>
Finally,&nbsp; we consider the block error probability and its bounds&nbsp; $($"Union Bound"&nbsp; and&nbsp; "Bhattacharyya Bound")&nbsp; for the following configuration:
#AWGN channel,&nbsp; characterized by the quotient&nbsp; $E_{\rm B}/N_0$,<br>
#Hamming code&nbsp; $\text{HC(7, 4, 3)}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; rate&nbsp; $R = 4/7$, &nbsp; weight enumerator function&nbsp; $W(X)-1 =   7 \cdot X^3 +  7 \cdot X^4 + X^7$,<br>
#"Soft Decision"&nbsp; according to the maximum likelihood criterion.<br><br>

{{GraueBox|TEXT=  
$\text{Example 5:}$&nbsp;  The results are summarized in the graph.
[[File:EN_KC_T_1_6_S5.png|right|frame|Block error probability and bounds of the&nbsp; $\text{HC (7, 4, 3)}$|class=fit]]
 
*In contrast to the graph in the section&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Coding_gain_-_bit_error_rate_with_AWGN|$\text{Coding gain &ndash; bit error rate with AWGN}$]],&nbsp; the&nbsp; &raquo;'''block error rate'''&laquo;&nbsp; is given here and not the bit error rate.
 
*Approximately,&nbsp; the latter is smaller by the factor&nbsp; $d_{\rm min}/k$&nbsp; if,&nbsp; as here&nbsp; $d_{\rm min}< k$.&nbsp; In the present example:&nbsp; $d_{\rm min}/k = 0.75$.<br>

*Only the points for integer&nbsp; $\rm dB$&nbsp; values were calculated.&nbsp; The dashed lines were interpolated.

*The&nbsp; (blue)&nbsp; numerical values given on the right are for&nbsp; (blue vertical)&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0 = 8 \, \rm dB$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $E_{\rm B}/N_0 \approx 6.31$.


The green crosses mark the&nbsp; "Union Bound".&nbsp; For this applies:

::<math>{\rm Pr(block\:error)}   \le  \sum_{i= d_{\rm min} }^{n} W_i \cdot {\rm Q} \left ( \sqrt{i \cdot {2R \cdot E_{\rm B} }/{N_0} } \right )  </math>
::<math>\Rightarrow \hspace{0.3cm}{\rm Pr(block\:error)} \approx  
7 \cdot {\rm Q} (4.65) + 7 \cdot {\rm Q} (5.37) + {\rm Q} (7.10) = </math>
::<math>\hspace{2.0cm} \approx  
7 \cdot 1.66 \cdot 10^{-6} + 7 \cdot 3.93 \cdot 10^{-8}+ 10^{-9} = 1.2 \cdot 10^{-5}
 \hspace{0.05cm}.</math>
*The numerical values make it clear that the Union Bound is essentially determined by the first term:
::<math>{\rm Pr(Union\hspace{0.15cm} Bound)} \approx W_{d_{\rm min} } \cdot {\rm Q} \left ( \sqrt{d_{\rm min} \cdot {2R \cdot E_{\rm B} }/{N_0} } \right ) = 1.16 \cdot 10^{-5}
 \hspace{0.05cm}.</math>
*However,&nbsp; this so-called&nbsp; "Truncated Union Bound" &nbsp;is no longer a true bound for the block error probability in all applications,&nbsp; but is to be understood as an approximation.<br>

*The&nbsp; "Bhattacharyya Bound"&nbsp; is marked by red dots in the graph.&nbsp; This is well above the Union Bound due to the highly simplified&nbsp; [https://en.wikipedia.org/wiki/Chernoff_bound $\text{Chernoff&ndash;Rubin Bound}$]&nbsp; 
:$${\rm Q}(x) \le {\rm e}^{-x^2/2}.$$ 
*For example,&nbsp; for&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0 = 8 \, \rm dB$&nbsp; with&nbsp; $\beta = {\rm e}^{-R \hspace{0.05cm}\cdot \hspace{0.05cm}E_{\rm B}/N_0} \approx 0.027$&nbsp; a more than tenfold value compared to the Union Bound:

::<math>{\rm Pr(Bhattacharyya)} = W(\beta) -1 = 7 \cdot \beta^3 + 7 \cdot \beta^4 + \beta^7 \approx 1.44 \cdot 10^{-4}
 \hspace{0.05cm}.</math>}}

== Exercises for the chapter ==
<br>
[[Aufgaben:Exercise_1.14:_Bhattacharyya_Bound_for_BEC|Exercise 1.14: Bhattacharyya Bound for BEC]]

[[Aufgaben:Exercise_1.15:_Distance_Spectra_of_HC_(7,_4,_3)_and_HC_(8,_4,_4)|Exercise 1.15: Distance Spectra of HC (7, 4, 3) and HC (8, 4, 4)]]

[[Aufgaben:Exercise_1.16:_Block_Error_Probability_Bounds_for_AWGN|Exercise 1.16: Block Error Probability Bounds for AWGN]]

[[Aufgaben:Exercise_1.16Z:_Bounds_for_the_Gaussian_Error_Function|Exercise 1.16Z: Bounds for the Gaussian Error Function]]

{{Display}}