Exercise 1.07Z: Classification of Block Codes

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

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 $\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 2 Nullen enthalten.
	In jedem Codewort sind genau 2 Einsen enthalten.
	Nach jeder 0 sind die Symbole 0 und 1 gleichwahrscheinlich.