Aufgaben:Exercise 4.11: Analysis of Parity-check Matrices

• Return to book

Produktcode und dessen Beschreibung durch die Prüfmatrix

In nebenstehender Grafik ist oben ein Produktcode angegeben, der durch folgende Prüfgleichungen gekennzeichnet ist:

$$p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_1 \oplus u_2\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_4 = u_2 \oplus u_4\hspace{0.05cm}.$$

Darunter sind die Prüfmatrizen $\mathbf{H}_1, \ \mathbf{H}_2$ und $\mathbf{H}_3$ angegeben. Zu prüfen ist, welche der Matrizen den gegebenen Produktcode entsprechend der Gleichung $\underline{x} = \underline{u} \cdot \mathbf{H}^{\rm T}$ richtig beschreiben, wenn von folgenden Definitionen ausgegangen wird:

• dem Codewort $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$,
• dem Codewort $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.

Alle $\mathbf{H}$–Matrizen beinhalten weniger Einsen als Nullen. Dies ist ein Kennzeichen der so genannten Low–density Parity–check Codes (kurz: LDPC–Codes). Bei den praxisrelevanten LDPC–Codes ist der Einsen–Anteil allerdings noch geringer als bei diesen Beispielen.

Weiterhin ist für die Aufgabe anzumerken:

• Ein $(n, \ k)$–Blockcode ist systematisch, wenn die ersten $k \ \rm Bit$ des Codewortes das Informationswort $\underline{u}$ beinhaltet. Mit der Codewortdefinition $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$ muss dann die Prüfmatrix $\mathbf{H}$ mit einer $k × k$–Diagonalmatrix enden.
• Ein regulärer Code (hinsichtlich LDPC–Anwendung) liegt vor, wenn das Hamming–Gewicht aller Zeilen  ⇒  $w_{\rm Z}$ und das Hamming–Gewicht aller Spalten  ⇒  $w_{\rm S}$ jeweils gleich ist. Andernfalls spricht man von einem irregulären LDPC–Code.
• Die Prüfmatrix $\mathbf{H}$ eines herkömmlichen linearen $(n, \ k)$–Blockcodes besteht aus exakt $m = n - k$ Zeilen und $n$ Spalten. Bei den LDPC–Codes lautet dagegen die Forderung: $m ≥ n - k$. Das Gleichheitszeichen trifft dann zu, wenn die $m$ Prüfgleichungen statistisch unabhängig sind.
• Aus der Prüfmatrix $\mathbf{H}$ lässt sich eine untere Schranke für die Coderate $R$ angeben:

$$R \ge 1 - \frac{{\rm E}[w_{\rm S}]}{{\rm E}[w_{\rm Z}]} \hspace{0.5cm}{\rm mit}\hspace{0.5cm} {\rm E}[w_{\rm S}] =\frac{1}{n} \cdot \sum_{i = 1}^{n}w_{\rm S}(i) \hspace{0.5cm}{\rm und}\hspace{0.5cm} {\rm E}[w_{\rm Z}] =\frac{1}{m} \cdot \sum_{j = 1}^{ m}w_{\rm Z}(j) \hspace{0.05cm}.$$

1. Diese Gleichung gilt für reguläre und irreguläre LDPC–Codes gleichermaßen, wobei den regulären Codes ${\rm E}[w_{\rm S}] = w_{\rm S}$ und ${\rm E}[w_{\rm Z}] = w_{\rm Z}$ berücksichtigt werden kann.

Hinweis:

• Die Aufgabe gehört zum Kapitel Grundlegendes zu den Low–density Parity–check

Fragebogen

1

Welche Prüfmatrix beschreibt den vorgegebenen Produktcode (obere Skizze)?

	$\mathbf{H}_1$ unter der Voraussetzung $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$.
	$\mathbf{H}_1$ unter der Voraussetzung $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.
	$\mathbf{H}_2$ unter der Voraussetzung $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.
	$\mathbf{H}_3$ unter der Voraussetzung $\underline{x} = (u_1, \, p_1, \, u_2, \, p_2, \, u_3, \, p_3, \, u_4, \, p_4)$.

2

Für die restlichen Teilaufgaben soll stets von $\underline{x} = (u_1, \, u_2, \, u_3, \, u_4, \, p_1, \, p_2, \, p_3, \, p_4)$ ausgegangen werden. Welche Aussagen gelten für die Prüfmatrix $\mathbf{H}_1$?

	Der Code ist systematisch.
	Der Code ist regulär.
	Für die Coderate gilt $R > 1/2$.
	Für die Coderate gilt $R = 1/2$.

3

Welche Aussagen gelten für die Prüfmatrix $\mathbf{H}_3$?

	Es ist kein Zusammenhang zwischen $\mathbf{H}_1$ und $\mathbf{H}_3$ erkennbar.
	$\mathbf{H}_3$–Zeilen sind Linearkombinationen von je zwei $\mathbf{H}_1$–Zeilen.
	Die vier Prüfgleichungen gemäß $\mathbf{H}_3$ sind linear unabhängig.

4

Welche Aussagen gelten für den durch $\mathbf{H}_3$ gekennzeichneten Code?

	Der Code ist systematisch.
	Der Code ist regulär.
	Für die Coderate gilt $R ≥ 1/2$.
	Die Coderate ist $R = 1/2$.

Musterlösung

Solution

(1) 

(2) 

(3) 

(4) 

(5)