Exercise 2.16: Bounded Distance Decoding: Decision Regions

• Return to book

Considered coding space schemes

We assume a block code of length  $n$  with symbols  $c_i ∈ {\rm GF}(2^m)$  that can correct up to  $t$  symbols. 

• Each possible received word  $\underline{y}_i$  can then be viewed as a point in a high-dimensional space.

• Assuming the basis  ${\rm GF}(2) = \{0, \, 1\}$  the dimension is  $n \cdot m$.

The diagram shows such spaces in schematic two-dimensional representation.  The illustration is to be interpreted as follows:

1. The red dot  $\underline{c}_j$  was sent.  All red outlined points  $\underline{y}_i$  in a hypersphere around this point  $\underline{c}_j$  with the parameter  $t$  as radius can be corrected.  Using the nomenclature according to the  $\rm graph$  in the theory section,  then  $\underline{z}_i = \underline{c}_j$  
   ⇒   "Error correction is successful".
2. For very many symbol errors,  $\underline{c}_j$  may be corrupted into a blue  $($or white-blue$)$  dot  $\underline{y}_j$  belonging to the hypersphere of another code word  $\underline{c}_{k ≠ j}$.  In this case the decoder makes a wrong decision  
   ⇒   "The received word  $\underline{y}_j$  is decoded incorrectly".
3. Finally,  as in the sketch below,  there may be yellow dots that do not belong to any hypersphere  
   ⇒   "The received word  $\underline{y}_j$  is not decodable".

In this exercise you are to decide which of the two code space schemes is suitable for describing

• "Bounded Distance Decoding of Hamming codes",  resp.

• "Bounded Distance Decoding by Reed–Solomon codes".

Hints:

• The exercise complements the topic of the chapter  "Error Probability and Application Areas".

• It is intended to illustrate significant differences in decoding Reed–Solomon codes and Hamming codes.

Questions

1

Which coding space scheme applies to the Hamming codes?

	Coding space scheme  $\rm A$,
	Coding space scheme  $\rm B$.

2

Which statement is true for the probability that a received word  $\underline{y}$  cannot be decoded with Hamming coding?

	The probability  ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$  is exactly zero.
	${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$  is nonzero,  but negligible.
	It holds   ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.

3

Which coding space scheme applies to the Reed–Solomon codes?

	Coding space scheme  $\rm A$,
	Coding space scheme  $\rm B$.

4

Which statement applies to the probability that a received word  $\underline{y}$  cannot be decoded after Reed–Solomon coding?

	The probability   ${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$   is exactly zero.
	${\rm Pr}(\underline{y} \rm \ is \ not \ decodable)$  is nonzero,  but negligible.
	It holds   ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \ is \ incorrectly \ decoded)$.

Solution

Solution

(1)  Correct is solution 1, since the coding space scheme  $\rm A$  describes a perfect code and each Hamming code $(n, \, k, \, 3)$ is a perfect code:

• For any Hamming code $(n, \, k, \, 3)$, there are a total of $2^n$ possible received words $\underline{y}_i$, which are assigned to one of $2^k$ possible code words $\underline{c}_j$ during syndrome decoding.
• Because of the HC property $d_{\rm min} = 3$, all spheres in $n$ dimensional space have radius $t = 1$. Thus in all spheres there are $2^{n-k}$ points, for example.

• $\text{HC (7, 4, 3)}$:   one point for error-free transmission and seven points for a bit error   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.
• $\text{HC (15, 11, 3)}$:   one point for error-free transmission and now 15 points for a bit error   ⇒   $1 + 15 = 16 = 2^4 = 2^{15-11}$.

Note:  Since the Hamming code is a binary code, here the code space has the dimension  $n$.

(2)  Correct is answer 1:

• In the gray area outside "spheres" there is not a single point in a perfect code.
• This was also shown in the calculation for subtask (1).

(3)  The Reed–Solomon codes are described by the coding space scheme  $\rm B$   ⇒  Answer 2.

• Here there are numerous yellow points in the gray area, i.e. points that cannot be assigned to any sphere in Bounded Distance Decoding (BDD).
• For example, if we consider the $\rm RSC \, (7, \, 3, \, 5)_8$ with code parameters $n = 7, \, k = 3$ and $t = 2$, there are a total of $8^7 = 2097152$ points and $8^3 = 512$ hypersphere here.
• If this code were perfect, then there should be $8^4 = 4096$ points within each sphere. However, it holds:

$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}lies\hspace{0.1cm} within\hspace{0.1cm} the\hspace{0.1cm} red\hspace{0.1cm} sphere)} = {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079 \hspace{0.05cm}.$$

• For ${\rm Pr}(f = 1)$ it is considered that there can be "$7 \rm \ over \ 1$" $= 7$ error positions, and for each error position also seven different error values. The same is considered for ${\rm Pr}(f = 2)$.

(4)  Correct is answer 3:

• A point in gray no-man's land is reached with fewer symbol errors than a point in another hypersphere.
• For long codes, an upper bound on the corruption probability is given in the literature:

$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)} = {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!} \hspace{0.05cm}.$$

• For the ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$, this upper bound yields the value $1/(16!) < 10^{-14}$.