Aufgaben:Exercise 1.2Z: Three-dimensional Representation of Codes

• Return to book

Space  $\rm GF(2^3)$  and 
code of length  $n = 3$

Codes for error detection or error correction can be represented very clearly in an  $n$-dimensional space.  We restrict ourselves here to binary codes of length  $n = 3$:

$$\underline{x} = (x_{1},\ x_{2},\ x_{3}) \hspace{0.1cm} \in \hspace{0.1cm}{\rm GF}(2^3) \hspace{0.05cm},\hspace{0.5cm} x_i = \{0,\ 1 \}\hspace{0.05cm},\hspace{0.2cm} i = 1, 2, 3\hspace{0.05cm}.$$

In general,  for block coding:

• The information word  $\underline{u} = (u_{1},\ u_{2}, \ \text{...} , \ u_{k})$  is uniquely transformed into the code word  $\underline{x} =(x_{1},\ x_{2}, \ \text{...} , \ , x_{n})$.

• The code rate is  $R = k/n$.

• The Hamming distance  $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$  between two code words  $x ∈ \mathcal{C}$  and  $x\hspace{0.05cm}' ∈ \mathcal{C}$  indicates the number of bit positions in which  $x$  and  $x\hspace{0.05cm}'$  differ.

• The minimum distance  $d_{\rm min} = {\rm min}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$  is a measure of the correctability of a code.

• It can detect  $e =d_{\rm min} - 1$  errors and can correct  $t =(d_{\rm min} - 1)/2$  errors.

• The last statement,  however,  is valid only for odd  $d_{\rm min}$.

Hints:

• This exercise belongs to the chapter  "Objective of Channel Coding"

• In addition,  some simple questions about the chapter  "Examples of binary block codes"  are anticipated.

Questions

1

Which statements hold if all points in  $\rm GF(2^3)$  are occupied?

	The assignment  $\underline{u} = (u_{1},\ u_{2},\ u_{3})$   →   $\underline{x} = (x_{1},\ x_{2},\ x_{3})$  holds.
	The identity  $\underline{x} = \underline{u}$  holds.
	The code rate is  $R = 1$.
	The minimum distance between two code words is  $d_{\rm min} = 2$.

2

Which statements are true for a  $(3, 2, 2)$  block code?

	Code  $\mathcal{C}_{1} = \{(0, 0, 0),\ (0, 1, 1),\ (1, 0, 1),\ (1, 1, 0)\}$  is possible.
	Code  $\mathcal{C}_{2} = \{(0, 0, 1),\ (0, 1, 0),\ (1, 0, 0),\ (1, 1, 1)\}$  is possible.
	Code  $\mathcal{C}_{3} = \{(0, 0, 0),\ (0, 1, 1),\ (1, 0, 0),\ (1, 1, 1)\}$  is possible.

3

What properties does the code  $\mathcal{C}_{1}$  defined in subtask  (2)  show?

	A bit error can be detected.
	A bit error can be corrected.

4

What properties does the code  $\mathcal{C}_{4}= \{(0, 0, 0),\ (1, 1, 1)\}$  show?

	The code rate is  $R = 1/4$.
	The code rate is  $R = 1/3$.
	A bit error can be detected.
	A bit error can be corrected.

Solution

Solution

(1)  Correct  statements 1 and 3:

• In this assignment,  $k = 3$  information bits are mapped to  $n = 3$  code bits   ⇒   $R = k/n = 1$.
• The statement  $\underline{x} = \underline{u} $  would only hold in the case of systematic coding.
• For example,  in principle.  $(0, 0, 0)$   →   $(0, 1, 1)$  would also be possible.
• The last statement is certainly false:  From the graph one can see the minimum distance  $d_{\rm min} = 1$.

Two  $(3, 2, 2)$  block codes

(2)  Correct  statements 1 and 2:

• $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$ actually  describe codes with rate  $R = 2/3$  and minimum distance  $d_{\rm min} = 2$.
• In the graph,  the green dots mark the code  $\mathcal{C}_{1}$  and the blue dots mark the code  $\mathcal{C}_{2}$.
• For the code  $\mathcal{C}_{3}$  – also with rate  $R = 2/3$  – the minimum distance between two code words is  $d_{\rm min} = 1$, 
  for example between  $(0, 0, 0)$  and  $(1, 0, 0)$  or between  $(0, 1, 1)$  and  $(1, 1, 1)$.

(3)  Correct is only  statement 1:

• Only a bit error can be detected with the minimum distance  $d_{\rm min} = 2$.
• In the upper graph,  the green dots indicate allowed code words of  $\mathcal{C}_{1}$. 
  If a blue dot is received,  this indicates a transmission error.
• On the other hand,  error correction is not possible with  $d_{\rm min} = 2$.
• The code  $\mathcal{C}_{1}$  corresponds to the  single parity-check code  $(3, 2, 2)$.

$(3, 1, 3)$  block code

(4)  Correct  answers 2, 3, and 4:

• $C_{4}$  describes the  $(3, 1, 3)$ repetition code.  In this code,  two of the total eight possible points are occupied,  from which one could incorrectly conclude the code rate $R = 1/4$.
• However,  the code rate is calculated according to $R = k/n = 1/3$.
• From the lower diagram one recognizes that because of  $d_{\rm min} = 3$  now also one bit error can be corrected.
• During decoding,  all light green points  (with black outline)  are transferred to the green point  $(0, 0, 0)$  and all light blue points are transferred to the blue point  $(1, 1, 1)$.
• Up to two bit errors can be detected at the same time  (one of course).