Aufgaben:Exercise 1.07Z: Classification of Block Codes: Difference between revisions

← Older edit Newer edit →

Revision as of 23:18, 30 June 2022

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 and repetition codes.

Questions

Solution

(1) Statements 1 and 2 are correct:

That is why there are $\rm 4 \ over \ 2 = 6$ codewords.
Statement 3 is false. For example, if the first bit is $0$, there is one codeword starting $00$ and two codewords starting $01$.

(2) Statements 1 to 4 are correct:

All codes that can be described by a generator matrix $\boldsymbol {\rm G}$ and/or a parity-check matrix $\boldsymbol {\rm H}$ are linear.
In contrast, "Code 5" does not satisfy any of the conditions required for linear codes. For example

is missing the all zero word,
the code cardinality $|\mathcal{C}|$ is not a power of two,
gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid codeword.

(3) Statements 1 to 3 are correct:

In a systematic code, the first $k$ bits of each codeword $\underline{x}$ must always be equal to the information word $\underline{u}$.
This is achieved if the beginning of the generator matrix $\boldsymbol {\rm G}$ is a unit matrix $\boldsymbol{\rm I}_{k}$.
This is true for "Code 1" (with dimension $k = 3$), "Code 2" (with $k = 1$) and "code 3" (with $k = 2$).
The generator matrix of "Code 2", however, is not explicitly stated. It is:

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

(4) Statement 1 is correct:

Dual codes are those where the parity-check matrix $\boldsymbol {\rm H}$ of one code is equal to the generator matrix $\boldsymbol {\rm G}$ of the other code.
For example, this is true for "Code 1" and "Code 2."
For the SPC (4, 3) holds:

$${ \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},$$

and for the repetition code 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}.$$

Statement 2 is certainly wrong, already for dimensional reasons: The generator matrix $\boldsymbol {\rm G}$ of "Code 3" is a $2×4$ matrix and the parity-check matrix $\boldsymbol {\rm H}$ of "Code 2" is a $3×4$ matrix.

"Code 3" and "Code 4" also do not satisfy the conditions of dual codes. The parity-check equations of

$${\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) \}$$

are as follows:

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

In contrast, the generator matrix of "Code 4" is given as follows:

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

@@ Line 51: / Line 51: @@
 <quiz display=simple>
-{Wie lässt sich "Code 5" beschreiben?
+{How can "Code 5" be described?
 |type="[]"}
-+ In jedem Codewort sind genau zwei Nullen enthalten.
++ There are exactly two zeros in each codeword.
-+ In jedem Codewort sind genau zwei Einsen enthalten.
++ There are exactly two ones in each codeword.
-- Nach jeder $0$ sind die Symbole&nbsp;  $0$&nbsp;  und&nbsp;  $1$&nbsp;  gleichwahrscheinlich.
+- After each $0$, the symbols&nbsp; $0$&nbsp; and&nbsp; $1$&nbsp; are equally likely.
-{Welche der folgenden Blockcodes sind linear?
+{Which of the following block codes are linear?
 |type="[]"}
-+ Code 1,
++ code 1,
-+ Code 2,
++ code 2,
-+ Code 3,
++ code 3,
-+ Code 4,
++ code 4,
-- Code 5.
+- code 5.
-{Welche der folgenden Blockcodes sind systematisch?
+{Which of the following block codes are systematic?
 |type="[]"}
-+ Code 1,
++ code 1,
-+ Code 2,
++ code 2,
-+ Code 3,
++ code 3,
-- Code 4,
+- code 4,
-- Code 5.
+- code 5.
-{Welche Codepaare sind zueinander dual?
+{Which code pairs are dual to each other?
 |type="[]"}
-+ Code 1 und Code 2,
++ code 1 and code 2,
-- Code 2 und Code 3,
+- code 2 and code 3,
-- Code 3 und Code 4.
+- code 3 and code 4.
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Richtig sind die <u>Aussagen 1 und 2</u>:
+'''(1)'''&nbsp; <u>Statements 1 and 2</u> are correct:
-* Deshalb gibt es auch $\rm 4 \ über \ 2 = 6$ Codeworte.
+* That is why there are $\rm 4 \ over \ 2 = 6$ codewords.
-* 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.
+* Statement 3 is false. For example, if the first bit is $0$, there is one codeword starting $00$ and two codewords starting $01$.
-'''(2)'''&nbsp; Richtig sind die <u>Aussagen 1 bis 4</u>:
+'''(2)'''&nbsp; <u>Statements 1 to 4</u> are correct:
-* Alle Codes, die durch eine Generatormatrix $\boldsymbol {\rm G}$ und/oder eine Prüfmatrix $\boldsymbol {\rm H}$ beschrieben werden können, sind linear.
+* All codes that can be described by a generator matrix $\boldsymbol {\rm G}$ and/or a parity-check matrix $\boldsymbol {\rm H}$ are linear.
-*Dagegen erfüllt "Code 5" keine der für lineare Codes erforderlichen Bedingungen. Beispielsweise
+*In contrast, "Code 5" does not satisfy any of the conditions required for linear codes. For example
-:*fehlt das Nullwort,
+:*is missing the all zero word,
-:*ist der Codeumfang $|\mathcal{C}|$ keine Zweierpotenz,
+:*the code cardinality $|\mathcal{C}|$ is not a power of two,
-:*ergibt $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ kein gültiges Codewort.
+:*gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid codeword.
-'''(3)'''&nbsp; Richtig sind die <u>Aussagen 1 bis 3</u>:
+'''(3)'''&nbsp; <u>Statements 1 to 3</u> are correct:
-*Bei einem systematischen Code müssen stets die ersten $k$ Bit eines jeden Codewortes $\underline{x}$ gleich dem Informationswort $\underline{u}$ sein.
+*In a systematic code, the first $k$ bits of each codeword $\underline{x}$ must always be equal to the information word $\underline{u}$.
-*Dies wird erreicht, wenn der Beginn der Generatormatrix $\boldsymbol {\rm G}$ eine Einheitsmatrix $\boldsymbol{\rm I}_{k}$ darstellt.
+*This is achieved if the beginning of the generator matrix $\boldsymbol {\rm G}$ is a unit matrix $\boldsymbol{\rm I}_{k}$.
-*Dies trifft für "Code 1" (mit Dimension $k = 3$), "Code 2" (mit $k = 1$) und "Code 3" (mit $k = 2$) zu.
+*This is true for "Code 1" (with dimension $k = 3$), "Code 2" (with $k = 1$) and "code 3" (with $k = 2$).
-*Die Generatormatrix von "Code 2" ist allerdings nicht explizit angegeben. Sie lautet:
+*The generator matrix of "Code 2", however, is not explicitly stated. It is:
 :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
-'''(4)'''&nbsp; Richtig ist die <u>Aussage 1</u>:
+'''(4)'''&nbsp; <u>Statement 1</u> is correct:
-*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.
+*Dual codes are those where the parity-check matrix $\boldsymbol {\rm H}$ of one code is equal to the generator matrix $\boldsymbol {\rm G}$ of the other code.
-*Dies trifft zum Beispiel für "Code 1" und "Code 2" zu.
+*For example, this is true for "Code 1" and "Code 2."
-*Für den SPC (4, 3) gilt:
+*For the SPC (4, 3) holds:
 :$${ \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):
+:and for the repetition code 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.
+*Statement 2 is certainly wrong, already for dimensional reasons: The generator matrix $\boldsymbol {\rm G}$ of "Code 3" is a $2×4$ matrix and the parity-check matrix $\boldsymbol {\rm H}$ of "Code 2" is a $3×4$ matrix.
-*"Code 3" und "Code 4" erfüllen ebenfalls nicht die Bedingungen dualer Codes. Die Prüfgleichungen von
+*"Code 3" and "Code 4" also do not satisfy the conditions of dual codes. The parity-check equations of
 :$${\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:
+:are as follows:
 :$$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:
+:In contrast, the generator matrix of "Code 4" is given as follows:
 :$${ \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.

	There are exactly two zeros in each codeword.
	There are exactly two ones in each codeword.
	After each $0$, the symbols $0$ and $1$ are equally likely.