Exercise 2.16: Bounded Distance Decoding: Decision Regions
From LNTwww
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:
- 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". - 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". - 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
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
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}$.
