Exercise 2.16: Bounded Distance Decoding: Decision Regions

• Return to book

Two 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 falsified 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 \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$  is exactly zero.
	${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$  is nonzero,  but negligible.
	It holds   ${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} 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 \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$   is exactly zero.
	${\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} not \hspace{0.15cm} decodable)$  is nonzero,  but negligible.
	It holds   ${\rm Pr}(\underline{y} {\rm \ is \ not \ decodable}) > {\rm Pr}(\underline{y} \rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} 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 Hamming code property  $d_{\rm min} = 3$,  all spheres in the  $n$–dimensional space have radius  $t = 1$.  Thus in all spheres there are  $2^{n-k}$ points.

• $\text{HC (7, 4, 3)}$:   One point for error-free transmission and seven points for one bit error   ⇒   $1 + 7 = 8 = 2^3 = 2^{7-4}$.
• $\text{HC (15, 11, 3)}$:   One point for error-free transmission and now fifteen points for one 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".

• 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$  hyperspheres 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 error probability is given in the literature:

$${\rm Pr}(\underline{y} {\rm \hspace{0.15cm} is \hspace{0.15cm} incorrectly \hspace{0.15cm} decoded}) = {\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}$.