Aufgabe 1.07Z: Klassifizierung von Blockcodes

• Zurück zum Buch

Blockcodes der Länge  $n = 4$

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

• den  Single Parity–check Code  $\text{SPC (4, 3)}$   ⇒   „Code 1”   mit der Generatormatrix

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

• den  Wiederholungscode   $\text{RC (4, 1)}$   ⇒   „Code 2”   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  $\text{(4, 2)}$–Blockcode   ⇒   „Code 3”   mit der Generatormatrix

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

• den  $\text{(4, 2)}$–Blockcode   ⇒   „Code 4”   mit der Generatormatrix

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

• einen weiteren „Code 5”   mit dem Codeumfang  $|\hspace{0.05cm}C\hspace{0.05cm}| = 6$.

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.

Hinweise:

• Die Aufgabe gehört zum Kapitel  "Allgemeine Beschreibung linearer Blockcodes".
• Bezug genommen wird aber auchauf die Seiten  "Single Parity–check Codes"  sowie  "Wiederholungscodes".

Fragebogen

1

Wie lässt sich „Code 5” beschreiben?

	In jedem Codewort sind genau zwei Nullen enthalten.
	In jedem Codewort sind genau zwei 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

Musterlösung

(1)  Richtig sind die  Aussagen 1 und 2:

• Deshalb gibt es auch  "$\rm 4 \ über \ 2 = 6$"  Codeworte.
• Aussage 3 ist falsch.  Ist zum Beispiel das erste Bit  "$0$",  so gibt es ein Codewort mit dem Beginn  "$00$"  und zwei Codeworte,  die mit  "$01$"  beginnen.

(2)  Richtig sind die  Aussagen 1 bis 4:

• Alle Codes,  die durch eine Generatormatrix  $\boldsymbol {\rm G}$  und/oder eine Prüfmatrix $\boldsymbol  {\rm 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  $|\mathcal{C}|$  keine Zweierpotenz,
• ergibt  $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$  kein gültiges Codewort.

(3)  Richtig sind die  Aussagen 1 bis 3:

• Bei einem systematischen Code müssen stets die ersten  $k$  Bit eines jeden Codewortes  $\underline{x}$  gleich dem Informationswort  $\underline{u}$  sein.

• Dies wird erreicht,  wenn der Beginn der Generatormatrix  $\boldsymbol {\rm 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 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)  Richtig ist die  Aussage 1:

• Von dualen Codes spricht man,  wenn die Prüfmatrix  $\boldsymbol {\rm H}$  des einen Codes gleich der Generatormatrix  $\boldsymbol {\rm G}$  des anderen Codes ist.

• Dies trifft zum Beispiel für „Code 1” und „Code 2” zu.
• Für den  $\text{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  $\text{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}.$$

• Aussage 2 ist mit Sicherheit falsch,  schon aus Dimensionsgründen:  $\boldsymbol {\rm G}$  von „Code 3” ist eine  $2×4$–Matrix und die Prüfmatrix  $\boldsymbol {\rm 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}.$$