Aufgabe 1.07Z: Klassifizierung von Blockcodes

Betrachtete Blockcodes der Länge n = 4

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

den Single Parity–check Code SPC (4, 3) ⇒ „Code 1” 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) ⇒ „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 (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 (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 $|C| = 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 Paritynddash; Codes sowie Wiederholungscodes.

Fragebogen

Musterlösung

(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 $\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 $|C|$ keine Zweierpotenz,

ergibt $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ kein gültiges Codewort.

(3) Bei einem systematischen Code müssen stets die ersten $k \ \rm Bit$ eines jeden Codewortes $\underline{x}$ gleich dem Codewort $\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 $\Rightarrow$ 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 $\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 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 $\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}.$$

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

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

	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.