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

{{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes}}

[[File:P_ID3068__KC_Z_4_11_v4.png|right|frame|Given parity-check matrices]]
In this exercise,&nbsp; the code rates of the codes&nbsp; $\mathcal {C}_1, \, \mathcal {C}_2, \, \mathcal {C}_3$&nbsp; and&nbsp; $\mathcal {C}_4$&nbsp; are to be determined,&nbsp; where the codes are given by their parity-check matrices alone.&nbsp; A lower bound on the code rate&nbsp; $R$&nbsp; reads:
:$$R \ge 1 - \frac{{\rm E}[w_{\rm C}]}{{\rm E}[w_{\rm R}]}
\hspace{0.05cm}.$$

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

Used here is the following nomenclature:
* $w_{\rm R}(j)$&nbsp; with&nbsp; $1 &#8804; j &#8804; m$&nbsp; being the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"Hamming weight"]]&nbsp; of&nbsp; $j$<sub>th</sub>&nbsp; row of&nbsp; $\mathbf{H}$&nbsp;.&nbsp; 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,&nbsp; $w_{\rm C}(i)$&nbsp; with&nbsp; $1 &#8804; i &#8804; n$&nbsp; gives the Hamming weight of&nbsp; $i$<sub>th</sub>&nbsp; column of&nbsp; $\mathbf{H}$&nbsp; 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&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes|"Basics of Low&ndash;density Parity&ndash;check Codes"]].

* Reference is made in particular to the section&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Some_characteristics_of_LDPC_codes|"Some characteristics of LDPC codes"]].




===Questions===
<quiz display=simple>
{$\mathbf{H}_1$&nbsp; describes a systematic code.&nbsp;  What are its parameters?
|type="{}"}
$n \hspace{0.27cm} = \ ${ 7 }
$k \hspace{0.3cm} = \ ${ 4 }
$m \hspace{0.15cm} = \ ${ 3 }

{What is the code rate of the code&nbsp; $\mathcal {C}_1$&nbsp; with the parity-check matrix&nbsp; $\mathbf{H}_1$?
|type="{}"}
$R \ = \ ${ 0.571 3% }

{What is the code rate of the code&nbsp; $\mathcal {C}_2$&nbsp; with the parity-check matrix&nbsp; $\mathbf{H}_2$?
|type="{}"}
$R \ = \ ${ 0.571 3% }

{What is the code rate of the code&nbsp; $\mathcal {C}_3$&nbsp; with the parity-check matrix&nbsp; $\mathbf{H}_3$?
|type="{}"}
$R \ = \ ${ 0.571 3% }

{What is the code rate of the code&nbsp; $\mathcal {C}_4$&nbsp; with the parity-check matrix&nbsp; $\mathbf{H}_4$?
|type="{}"}
$R \ = \ ${ 0.5 3% }
</quiz>

===Solution===
{{ML-Kopf}}
'''(1)'''&nbsp; The matrix&nbsp; $\mathbf{H}_1$&nbsp; ends with a&nbsp; $3 &times 3$&nbsp; diagonal matrix. 
*This is the characteristic of a systematic code with&nbsp; $\underline{m = 3}$&nbsp; parity-check equations.
 
*The code length is $\underline{n = 7}$.&nbsp; Thus,&nbsp; a code word contains&nbsp; $\underline{k = 4}$&nbsp; information bits.

 
:<u>Note:</u> This is the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Some_properties_of_the_.287.2C_4.2C_3.29_Hamming_code|"systematic (7, 4, 3)&nbsp; Hamming code"]].


'''(2)'''&nbsp; The code rate of the&nbsp; (7, 4, 3) Hamming code is&nbsp; $\underline{R = 4/7 = 0.571}$. 
*The Hamming weight for all&nbsp; $m = 3$&nbsp; rows is&nbsp; $w_{\rm R} = 4$&nbsp; 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:&nbsp; The actual code rate is equal to the lower bound &nbsp; &#8658; &nbsp; the&nbsp; $m = 3$&nbsp; parity-check equations of&nbsp; $\mathbf{H}_1$&nbsp; are linearly independent.



'''(3)'''&nbsp; The first row of&nbsp; $\mathbf{H}_2$&nbsp; is the sum of the first row&nbsp; $(r_1)$&nbsp; and the second row&nbsp; $(r_2)$&nbsp; of&nbsp; $\mathbf{H}_1$. 
*The second row is equal to&nbsp; $(r_2 + r_3)$&nbsp; and the third row is&nbsp; $(r_1 + r_3)$.
 
*This is the identical code &nbsp; &#8658; &nbsp; rate&nbsp; $\underline{R = 4/7 = 0.571}$.
 
*Further,&nbsp; $w_{\rm R} = 4$&nbsp; and&nbsp; ${\rm E}[w_{\rm C}] = 1/7 \cdot [0 + 6 \cdot 2] = 12/7$.



'''(4)'''&nbsp; For this code with&nbsp; $n = 7$&nbsp; $($column count$)$&nbsp; and&nbsp; $m = 4$&nbsp; $($row count$)$&nbsp; 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,&nbsp; which is not the case here: 
*The third row of&nbsp; $\mathbf{H}_3$&nbsp; was taken from&nbsp; $\mathbf{H}_1$.
 
*If one deletes this row,&nbsp; $\mathbf{H}_3 = \mathbf{H}_2$&nbsp; and therefore also holds:&nbsp; $\ \underline{R = 4/7 = 0.571}$.



'''(5)'''&nbsp; Here&nbsp; $n = 7$&nbsp; and&nbsp; $m = 4$,&nbsp; 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,&nbsp; the code rate is equal to the lower bound:&nbsp; $\underline{R = 1/2}$. 


:<u>Hint:</u> &nbsp; This is the&nbsp; [[Aufgaben:Exercise_1.09:_Extended_Hamming_Code| "extended (8, 4, 4) Hamming code"]].
{{ML-Fuß}}



[[Category:Channel Coding: Exercises|^4.4 Low–density Parity–check Codes^]]