Aufgaben:Exercise 4.11Z: Code Rate from the Parity-check Matrix

• Return to book

Given parity-check matrices

In this exercise,  the code rates of the codes  $\mathcal {C}_1, \, \mathcal {C}_2, \, \mathcal {C}_3$  and  $\mathcal {C}_4$  are to be determined,  where the codes are given by their parity-check matrices alone.  A lower bound on the code rate  $R$  reads:

$$R \ge 1 - \frac{{\rm E}[w_{\rm C}]}{{\rm E}[w_{\rm R}]} \hspace{0.05cm}.$$

If the  $m$  parity-check equations of all matrix rows are linearly independent,  then the equal sign in the above inequality holds.

Used here is the following nomenclature:

• $w_{\rm R}(j)$  with  $1 ≤ j ≤ m$  being the  "Hamming weight"  of  $j$_th  row of  $\mathbf{H}$ .  By expectation value formation results:

$${\rm E}[w_{\rm R}] =\frac{1}{m} \cdot \sum_{j = 1}^{m} w_{\rm R}(j)\hspace{0.05cm}.$$

• Accordingly,  $w_{\rm C}(i)$  with  $1 ≤ i ≤ n$  gives the Hamming weight of  $i$_th  column of  $\mathbf{H}$  with expected value

$${\rm E}[w_{\rm C}] =\frac{1}{n} \cdot \sum_{i = 1}^{n} w_{\rm C}(i)\hspace{0.05cm}.$$

Hints:

• This exercise belongs to the chapter  "Basics of Low–density Parity–check Codes".

• Reference is made in particular to the section  "Some characteristics of LDPC codes".

Questions

1

$\mathbf{H}_1$  describes a systematic code.  What are its parameters?

$n \hspace{0.27cm} = \ $

$k \hspace{0.3cm} = \ $

$m \hspace{0.15cm} = \ $

2

What is the code rate of the code  $\mathcal {C}_1$  with the parity-check matrix  $\mathbf{H}_1$?

$R \ = \ $

3

What is the code rate of the code  $\mathcal {C}_2$  with the parity-check matrix  $\mathbf{H}_2$?

$R \ = \ $

4

What is the code rate of the code  $\mathcal {C}_3$  with the parity-check matrix  $\mathbf{H}_3$?

$R \ = \ $

5

What is the code rate of the code  $\mathcal {C}_4$  with the parity-check matrix  $\mathbf{H}_4$?

$R \ = \ $

Solution

Solution

(1)  The matrix  $\mathbf{H}_1$  ends with a  $3 × 3$  diagonal matrix.

• This is the characteristic of a systematic code with  $\underline{m = 3}$  parity-check equations.

• The code length is $\underline{n = 7}$.  Thus,  a code word contains  $\underline{k = 4}$  information bits.

Note: This is the  "systematic (7, 4, 3)  Hamming code".

(2)  The code rate of the  (7, 4, 3) Hamming code is  $\underline{R = 4/7 = 0.571}$.

• The Hamming weight for all  $m = 3$  rows is  $w_{\rm R} = 4$  and for the mean Hamming weight over all columns holds:

$${\rm E}[w_{\rm C}] =\frac{1}{n} \cdot \sum_{j = 1}^{ n} w_{\rm S}(j) = 1/7 \cdot [2 + 3 + 2+2 + 1+1 +1] = 12/7 \hspace{0.05cm}.$$

• This applies to the specified lower bound of the code rate:

$$R \ge 1 - \frac{{\rm E}[w_{\rm C}]}{w_{\rm R}} = 1 - \frac{12/7}{4}\hspace{0.15cm} \underline{= 4/7 \approx 0.571}\hspace{0.05cm}.$$

• This means:  The actual code rate is equal to the lower bound   ⇒   the  $m = 3$  parity-check equations of  $\mathbf{H}_1$  are linearly independent.

(3)  The first row of  $\mathbf{H}_2$  is the sum of the first row  $(r_1)$  and the second row  $(r_2)$  of  $\mathbf{H}_1$.

• The second row is equal to  $(r_2 + r_3)$  and the third row is  $(r_1 + r_3)$.

• This is the identical code   ⇒   rate  $\underline{R = 4/7 = 0.571}$.

• Further,  $w_{\rm R} = 4$  and  ${\rm E}[w_{\rm C}] = 1/7 \cdot [0 + 6 \cdot 2] = 12/7$.

(4)  For this code with  $n = 7$  $($column count$)$  and  $m = 4$  $($row count$)$  holds:

$$w_{\rm R} = 4\hspace{0.05cm},\hspace{0.3cm} {\rm E}[w_{\rm C}] =\frac{1}{n} \cdot \sum_{j = 1}^{ n}w_{\rm S}(j) = 1/7 \cdot [3 + 1 + 2 +3+2 + 2+3] = 16/7\hspace{0.3cm} \Rightarrow \hspace{0.3cm} R \ge 1 - \frac{16/7}{4}= 3/7 \hspace{0.05cm}.$$

The equal sign would only apply to linearly independent parity-check equations,  which is not the case here:

• The third row of  $\mathbf{H}_3$  was taken from  $\mathbf{H}_1$.

• If one deletes this row,  $\mathbf{H}_3 = \mathbf{H}_2$  and therefore also holds:  $\ \underline{R = 4/7 = 0.571}$.

(5)  Here  $n = 7$  and  $m = 4$,  as well as

$${\rm E}[w_{\rm C}] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1/8 \cdot [4 + 3 + 4 + 3 + 3+2 + 2+2] = 23/8\hspace{0.05cm},\hspace{0.8cm} {\rm E}[w_{\rm R}] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1/4 \cdot [8 + 5 + 5+5] = 23/4$$

$$\Rightarrow \hspace{0.3cm}R \ge 1 - \frac{{\rm E}[w_{\rm C}]}{{\rm E}[w_{\rm R}]} = 1 - \frac{23/8}{23/4} = 1/2 \hspace{0.05cm}.$$

• Since all four equations are linearly independent,  the code rate is equal to the lower bound:  $\underline{R = 1/2}$.

Hint:   This is the  "extended (8, 4, 4) Hamming code".