Aufgaben:Exercise 4.11: Analysis of Parity-check Matrices - Revision history

Guenter at 16:20, 19 December 2022

2022-12-19T16:20:28Z

Guenter at 17:03, 16 December 2022

2022-12-16T17:03:43Z

Guenter at 16:41, 16 December 2022

2022-12-16T16:41:42Z

Guenter at 16:41, 16 December 2022

2022-12-16T16:41:03Z

Noah at 19:09, 10 December 2022

2022-12-10T19:09:37Z

Show changes

Guenter: Guenter moved page Aufgaben:Exercise 4.11: Analysis of Parity-Check Matrices to Aufgaben:Exercise 4.11: Analysis of Parity-check Matrices

2022-11-22T13:02:32Z

Guenter moved page Exercise 4.11: Analysis of Parity-Check Matrices to Exercise 4.11: Analysis of Parity-check Matrices

Guenter: Guenter moved page Aufgaben:Aufgabe 4.11: Analyse von Prüfmatrizen to Aufgaben:Exercise 4.11: Analysis of Parity-Check Matrices

2022-11-22T11:42:10Z

Guenter moved page Aufgabe 4.11: Analyse von Prüfmatrizen to Exercise 4.11: Analysis of Parity-Check Matrices

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:51:35Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

Javier: Text replacement - "[[Kanalcodierung" to "[[Channel_Coding"

2020-07-09T12:52:59Z

Text replacement - "[[Kanalcodierung" to "[[Channel_Coding"

Guenter at 12:57, 10 July 2019

2019-07-10T12:57:03Z

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes}}
-[[File:P_ID3067__KC_A_4_11_v2.png|right|frame|Product code described by the parity-check matrix&nbsp; $\mathbf{H}$]]
+[[File:EN_KC_A_4_11_v2.png|right|frame|Product code described by the parity-check matrix&nbsp; $\mathbf{H}$]]
 In the adjacent graphic,&nbsp; a product code is indicated at the top,&nbsp; which is characterized by the following parity-check equations:
 :$$p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_2\hspace{0.05cm},$$

@@ Line 76: / Line 76: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct are the <u>solutions 1 and 3</u>:
+'''(1)'''&nbsp; Correct are the&nbsp; <u>solutions 1 and 3</u>:
-*With the code word definition $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$, the parity-check matrix $\mathbf{H}_1$ denotes the following check equations:
+*With the code word definition &nbsp; $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$,&nbsp; the parity-check matrix&nbsp; $\mathbf{H}_1$&nbsp; denotes the following check equations:
 :$$u_1 \oplus u_2 \oplus p_1 = 0\hspace{0.05cm},\hspace{0.3cm}
 u_3 \oplus u_4 \oplus p_2 = 0\hspace{0.05cm},\hspace{0.3cm}
 u_1 \oplus u_3 \oplus p_3 = 0\hspace{0.05cm},\hspace{0.3cm}
 u_2 \oplus u_4 \oplus p_4 = 0\hspace{0.05cm}.$$
-*This corresponds exactly to the assumptions made above. The same result is obtained for $\mathbf{H}_2$ and the code word definition  $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.
+*This corresponds exactly to the assumptions made above.
@@ Line 98: / Line 100: @@
-'''(2)'''&nbsp; Correct are the <u>proposed solutions 1 and 4</u>:
+'''(2)'''&nbsp; Correct are the&nbsp; <u>proposed solutions 1 and 4</u>:
-* The code is systematic because $\mathbf{H}_1$ ends with a $4 &times 4$ diagonal matrix.
+* The code is systematic because&nbsp; $\mathbf{H}_1$ &nbsp;ends with a&nbsp; $4 &times 4$&nbsp; diagonal matrix.
 *For a regular (LDPC) code, there should be an equal number of ones in each row and in each column.
-*The first condition is satisfied $(w_{\rm Z} = 3)$, but not the second. Rather, there is (equally often) one one or two ones per column &nbsp;&#8658;&nbsp; ${\rm E}[w_{\rm S}] = 1.5$.
+*For a regular (LDPC) code,&nbsp; there should be an equal number of&nbsp; "ones"&nbsp; in each row and in each column.
 * For an irregular code, the lower bound for the code rate is:
-:$$R \ge 1 - \frac{{\rm E}[w_{\rm S}]}{{\rm E}[w_{\rm Z}]}
+*The first condition is satisfied&nbsp; $(w_{\rm R} = 3)$,&nbsp; but not the second.&nbsp; Rather,&nbsp; there is&nbsp; (equally often)&nbsp; one&nbsp; "one"&nbsp; or two&nbsp; "ones"&nbsp; per column &nbsp; &#8658; &nbsp; ${\rm E}[w_{\rm C}] = 1.5$.
 = 1 - \frac{1.5}{3} = 1/2
 \hspace{0.05cm}.$$
-* Because of the given code structure ($k = 4$ information bits, $m = 4$ check bits &nbsp;&#8658;&nbsp; $n = 8$ code bits) the code rate can also be given in the conventional form: $R = k/n$ &nbsp; &#8658; &nbsp; Correct is solution 4 in contrast to answer 3.
+* Because of the given code structure&nbsp; $(k = 4$&nbsp; information bits,&nbsp; $m = 4$&nbsp; check bits &nbsp; &#8658; &nbsp; $n = 8$&nbsp; encoded bits$)$&nbsp; the code rate can also be given in the conventional form:&nbsp; $R = k/n$ &nbsp; &#8658; &nbsp; Correct is solution 4 in contrast to answer 3.
-By linear combinations, the four linearly independent equations with respect to $\mathbf{H}_1$ now become four linearly independent equations with respect to $\mathbf{H}_3$ &nbsp; <br>&#8658; &nbsp;  Therefore, the <u>proposed solutions 2 and 3</u> are correct.
+* The Hamming weights of all rows are equal&nbsp; $(w_{\rm R} = 4)$&nbsp; and also all columns each have the same Hamming weight&nbsp; $(w_{\rm C} = 2)$ &nbsp; &#8658; &nbsp; the code is regular.
-'''(4)'''&nbsp; Here, <u>solutions 2, 3, and 4</u> are correct:
+*But since the four rows of&nbsp; $\mathbf{H}_3$&nbsp; also describe four independent equations,&nbsp; the equal sign &nbsp; &#8658; &nbsp; $R = 1/2$&nbsp; also holds.
 {{ML-Fuß}}

@@ Line 38: / Line 38: @@
 <u>Hints:</u>
-* This exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes|"Basics of the Low&ndash;density Parity&ndash;check"]].
+* This exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes|"Basics of the Low&ndash;density Parity&ndash;check codes"]].
 * Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Some_characteristics_of_LDPC_codes|"Some characteristics of LDPC codes"]].

@@ Line 2: / Line 2: @@
 [[File:P_ID3067__KC_A_4_11_v2.png|right|frame|Product code described by the parity-check matrix&nbsp; $\mathbf{H}$]]
-In the adjacent graphic, a product code is indicated at the top, which is characterized by the following parity-check equations:
+In the adjacent graphic,&nbsp; a product code is indicated at the top,&nbsp; which is characterized by the following parity-check equations:
-:$$p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_2\hspace{0.05cm},\hspace{0.3cm}
+:$$p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_2\hspace{0.05cm},$$
-p_2 = u_3 \oplus u_4\hspace{0.05cm},\hspace{0.3cm}
+:$$p_2 = u_3 \oplus u_4\hspace{0.05cm},$$
-p_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_3\hspace{0.05cm},\hspace{0.3cm}
+:$$p_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_3\hspace{0.05cm},$$
-p_4 = u_2 \oplus u_4\hspace{0.05cm}.$$
+:$$p_4 = u_2 \oplus u_4\hspace{0.05cm}.$$
-Below are given the check matrices&nbsp; $\mathbf{H}_1, \ \mathbf{H}_2$ and $\mathbf{H}_3$&nbsp;. To be checked is which of the matrices has the given product code according to the equation&nbsp; $\underline{x} = \underline{u} \cdot \mathbf{H}^{\rm T}$&nbsp; correctly describing the given product code, assuming the following definitions:
+Below are given the check matrices&nbsp; $\mathbf{H}_1, \ \mathbf{H}_2$&nbsp; and&nbsp; $\mathbf{H}_3$.&nbsp; To be checked:&nbsp; Which of the matrices correctly describe the given product code according to the equation&nbsp; $\underline{x} = \underline{u} \cdot \mathbf{H}^{\rm T}$&nbsp; assuming the following definitions:
 * the code word&nbsp; $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$,
 * the code word&nbsp; $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.
-All $\mathbf{H}$&ndash;matrices contain fewer ones than zeros. This is a characteristic of the so-called low&ndash;density parity&ndash;check codes&nbsp; (short: &nbsp;$\rm LDPC$ codes). In the case of LDPC codes relevant to practice, however, the share of ones is still significantly lower than in these examples.
+All&nbsp; $\mathbf{H}$&nbsp; matrices contain fewer&nbsp; "ones"&nbsp; than&nbsp; "zeros".&nbsp; This is a characteristic of the so-called&nbsp; "low&ndash;density parity&ndash;check codes"&nbsp; $($short: &nbsp;$\rm LDPC$ codes$)$.&nbsp; In the case of LDPC codes relevant to practice,&nbsp; however,&nbsp; the share of&nbsp; "ones"&nbsp; is still significantly lower than in these examples.
 Furthermore, note for the exercise:
-* A&nbsp; $(n, \ k)$&ndash;block code is systematic if the first&nbsp; $k$&nbsp; bits of the code word&nbsp; $\underline{x}$&nbsp; contains the information word&nbsp; $\underline{u}$&nbsp;. With the code word definition&nbsp; $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$&nbsp; the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; must then end with a&nbsp; $k &times k$ diagonal matrix.
+* An&nbsp; $(n, \ k)$&nbsp; $\underline{x} = \underline{u} \cdot \mathbf{H}^{\rm T}$&nbsp; block code is systematic if the first&nbsp; $k$&nbsp; bits of the code word&nbsp; $\underline{x}$&nbsp; contains the information word&nbsp; $\underline{u}$.&nbsp; With the code word&nbsp; $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$&nbsp; the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; must then end with a&nbsp; $k &times k$ diagonal matrix.
-*This equation applies equally to regular and irregular LDPC&ndash;codes, where the regular codes&nbsp; ${\rm E}[w_{\rm S}] = w_{\rm S}$&nbsp; and&nbsp; ${\rm E}[w_{\rm Z}] = w_{\rm Z}$&nbsp; can be considered.
+* A&nbsp; "regular code"&nbsp; $($with respect to the LDPC application$)$&nbsp; exists,&nbsp; if the Hamming weight of all rows &nbsp; &#8658; &nbsp; $w_{\rm R}$ and the Hamming weight of all columns &nbsp; &#8658; &nbsp; $w_{\rm C}$ are equal in each case.&nbsp; Otherwise,&nbsp; one speaks of an&nbsp; "irregular LDPC code".
@@ Line 36: / Line 37: @@
 * Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Some_characteristics_of_LDPC_codes|"Some characteristics of LDPC codes"]].
@@ Line 62: / Line 63: @@
 |type="[]"}
 - No relation between&nbsp; $\mathbf{H}_1$&nbsp; and&nbsp; $\mathbf{H}_3$&nbsp; is discernible.
-+ The&nbsp; $\mathbf{H}_3$&ndash;rows are linear combinations of two&nbsp; $\mathbf{H}_1$ ;rows each.
++ The&nbsp; $\mathbf{H}_3$&nbsp; rows are linear combinations of two&nbsp; $\mathbf{H}_1$&nbsp; rows each.
 + The four parity-check equations according to&nbsp; $\mathbf{H}_3$&nbsp; are linearly independent.

← Older revision		Revision as of 12:51, 23 March 2021
Line 129:		Line 129:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^4.4 Low–density Parity–check Codes^]]	+	[[Category:Channel Coding: Exercises\|^4.4 Low–density Parity–check Codes^]]

← Older revision	Revision as of 13:02, 22 November 2022
(No difference)

← Older revision	Revision as of 11:42, 22 November 2022
(No difference)

@@ Line 38: / Line 38: @@
 ''Hinweise:''
-* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes| Grundlegendes zu den Low&ndash;density Parity&ndash;check]].
+* Die Aufgabe gehört zum Kapitel&nbsp; [[Channel_Coding/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes| Grundlegendes zu den Low&ndash;density Parity&ndash;check]].
-* Bezug genommen wird insbesondere auf die Seite&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low–density_Parity–check_Codes#Einige_Charakteristika_der_LDPC.E2.80.93Codes|Einige Charakteristika der LDPC&ndash;Codes]].
+* Bezug genommen wird insbesondere auf die Seite&nbsp; [[Channel_Coding/Grundlegendes_zu_den_Low–density_Parity–check_Codes#Einige_Charakteristika_der_LDPC.E2.80.93Codes|Einige Charakteristika der LDPC&ndash;Codes]].

@@ Line 84: / Line 84: @@
-Bei gleicher Codewortdefinition $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$ lifern die anderen Prüfmatrizen keinen sinnvollen Gleichungssatz:
+Bei gleicher Codewortdefinition $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$ liefern die anderen Prüfmatrizen keinen sinnvollen Gleichungssatz:
 * Entsprechend Prüfmatrix $\mathbf{H}_1$:
 :$$u_1 \oplus p_1 \oplus u_3 = 0\hspace{0.05cm},\hspace{0.3cm}
@@ Line 99: / Line 99: @@
 '''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 4</u>:
 * Der Code ist systematisch, weil $\mathbf{H}_1$ mit einer $4 &times 4$&ndash;Diagonalmatrix endet.
-* Bei einem regulären (LDPC)&ndash;Code müssten in jeder Zeile und in jeder Spalte gleich viele Einsen sein. Die erste Bedingung ist erfüllt $(w_{\rm Z} = 3)$, nicht aber die zweite. Vielmehr gibt es (gleich oft) eine Eins bzw. zwei Einsen pro Spalte &nbsp;&#8658;&nbsp; ${\rm E}[w_{\rm S}] = 1.5$.
+* Bei einem regulären (LDPC)&ndash;Code müssten in jeder Zeile und in jeder Spalte gleich viele Einsen sein.
 * Bei einem irregulären Code lautet die untere Schranke für die Coderate:
 :$$R \ge 1 - \frac{{\rm E}[w_{\rm S}]}{{\rm E}[w_{\rm Z}]}
@@ Line 106: / Line 107: @@
 * Wegen der gegebenen Codestruktur ($k = 4$ Informationsbits, $m = 4$ Prüfbits &nbsp;&#8658;&nbsp; $n = 8$ Codebits) ist hier die Coderate auch in der herkömmlichen Form angebbar: $R = k/n$ &nbsp; &#8658; &nbsp; Richtig ist Lösungsvorschlag 4 im Gegensatz zur Antwort 3.
@@ Line 115: / Line 117: @@
-Durch Linearkombinationen werden aus den vier linear unabhängigen Gleichungen bezüglich $\mathbf{H}_1$ nun vier linear unabhängige Gleichungen bezüglich $\mathbf{H}_3$. Richtig sind also die <u>Lösungsvorschläge 2 und 3</u>.
+Durch Linearkombinationen werden aus den vier linear unabhängigen Gleichungen bezüglich $\mathbf{H}_1$ nun vier linear unabhängige Gleichungen bezüglich $\mathbf{H}_3$ &nbsp; <br>&#8658; &nbsp;  Richtig sind also die <u>Lösungsvorschläge 2 und 3</u>.