Exercise 1.07Z: Classification of Block Codes

• Return to book

Betrachtete Blockcodes der Länge n = 4

Wir betrachten Blockcodes der Länge $n = 4$:

• den Single Parity–check Code SPC (4, 3) mit

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

• den Wiederholungscode RC (4, 1) mit der Prüfmatrix

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

• den (4, 2)–Blockcode mit der Generatormatrix

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

• den (4, 2)–Blockcode mit der Generatormatrix

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

• einen weiteren Code mit dem Codeumfang $|C| = 6$.

Diese Codes werden im Folgenden mit Code 1, ... , Code 5 bezeichnet. In der Grafik sind die einzelnen Codes explizit angegegeben.

Bei den Fragen zu diesen Aufgaben geht es um die Begriffe

• lineare Codes,

• systematische Codes,

• duale Codes.

Hinweis :

Die Aufgabe gehört zum Themengebiet von Kapitel Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes.

Fragebogen

1

Wie lässt sich Code 5 beschreiben?

	In jedem Codewort sind genau 2 Nullen enthalten.
	In jedem Codewort sind genau 2 Einsen enthalten.
	Nach jeder 0 sind die Symbole 0 und 1 gleichwahrscheinlich.

2

Welche der folgenden Blockcodes sind linear?

	Code 1,
	Code 2,
	Code 3,
	Code 4,
	Code 5.

3

Welche der folgenden Blockcodes sind systematisch?

	Code 1,
	Code 2,
	Code 3,
	Code 4,
	Code 5.

4

Welche Codepaare sind zueinander dual?

	Code 1 und Code 2,
	Code 2 und Code 3,
	Code 3 und Code 4.

Musterlösung

Solution

(1)  Richtig sind die Aussagen 1 und 2. Deshalb gibt es auch „4 über 2” $= 6$ Codeworte. Die letzte Aussage ist falsch. Ist zum Beispiel das erste Bit eine „0”, so gibt es ein Codewort mit dem Beginn „00” und zwei Codeworte, die mit „01” beginnen.

(2)  Richtig sind hier die Aussagen 1 bis 4. Alle Codes, die durch eine Generatormatrix G und/oder eine Prüfmatrix H beschrieben werden können, sind linear. Dagegen erfüllt Code 5 keine der für lineare Codes erforderlichen Bedingungen. Beispielsweise

• fehlt das Nullwort,

• ist der Codeumfang $|C|$ keine Zweierpotenz,

• ergibt (0, 1, 0, 1) ⊕ (1, 0, 1, 0) = (1, 1, 1, 1) kein gültiges Codewort.

(3)  Bei einem systematischen Code müssen stets die ersten k Bit eines jeden Codewortes x gleich dem Codewort u sein. Dies wird erreicht, wenn der Beginn der Generatormatrix G eine Einheitsmatrix $\boldsymbol{\rm I}_{k}$ darstellt. Dies trifft für Code 1 (mit Dimension k = 3), Code 2 (mit k = 1) und Code 3 (mit k = 2) zu ⇒ die Aussagen 1 bis 3 sind richtig. Die Generatormatrix von Code 2 ist allerdings nicht explizit angegeben. Sie lautet:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

(4)  Von dualen Codes spricht man, wenn die Prüfmatrix H des einen Codes gleich der Generatormatrix G des anderen Codes ist. Dies trifft zum Beispiel für Code 1 und Code 2 zu. Für den SPC (4, 3) gilt:

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm} { \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

und für den Wiederholungscode RC (4, 1):

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm} { \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$

Das heißt: Die Aussage 1 trifft zu. Aussage 2 ist mit Sicherheit falsch, schon aus Dimensionsgründen: Die Generatormatrix G von Code 3 ist eine 2×4–Matrix und die Prüfmatrix H von Code 2 eine 3×4–Matrix.

Code 3 und Code 4 erfüllen ebenfalls nicht die Bedingungen dualer Codes. Die Prüfgleichungen von

$${\rm Code}\hspace{0.15cm}3 = \{ (0, 0, 0, 0) \hspace{0.05cm},\hspace{0.1cm} (0, 1, 1, 0) \hspace{0.05cm},\hspace{0.1cm}(1, 0, 0, 1) \hspace{0.05cm},\hspace{0.1cm}(1, 1, 1, 1) \}$$

lauten:

$$x_1 \oplus x_4 = 0\hspace{0.05cm},\hspace{0.2cm}x_2 \oplus x_3 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$

Dagegen ist die Generatormatrix von Code 4 wie folgt gegeben:

$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$