Exercise 1.07Z: Classification of Block Codes

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

Musterlösung

Solution

(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 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}.$$

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.