Aufgaben:Exercise 1.07Z: Classification of Block Codes

• Return to book

Block codes of length  $n = 4$

We consider block codes of length  $n = 4$:

• the  single parity–check  code  $\text{SPC (4, 3)}$   ⇒   "code 1"   with the generator matrix

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

• the  repetition code   $\text{RC (4, 1)}$   ⇒   "code 2"   with the parity-check matrix

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

• the   $\text{(4, 2)}$ block code   ⇒   "code 3"   with the generator matrix

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

• the  $\text{(4, 2)}$ block code   ⇒   "code 4"   with the generator matrix

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

• another "Code 5"   with the code cardinality (Überstetzung von Codeumfang laut Wachter-Zeh VL)  $|\hspace{0.05cm}C\hspace{0.05cm}| = 6$.

The individual codes are explicitly indicated in the graphic. The questions for these tasks are about the terms

• linear codes,

• systematic codes,

• dual codes.

Hints :

• This exercise belongs to the chapter  General description of linear block codes.
• Reference is also made to the pages  single parity–check codes  andrepetition codes.

Questions

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

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