Aufgaben:Exercise 1.10: Some Generator Matrices - Revision history

Hwang at 16:57, 1 November 2022

2022-11-01T16:57:15Z

Guenter at 09:53, 12 July 2022

2022-07-12T09:53:48Z

Guenter at 15:18, 11 July 2022

2022-07-11T15:18:42Z

Guenter at 15:16, 11 July 2022

2022-07-11T15:16:54Z

Guenter at 14:56, 11 July 2022

2022-07-11T14:56:41Z

Noah at 22:39, 7 July 2022

2022-07-07T22:39:23Z

Show changes

Guenter at 09:50, 11 May 2022

2022-05-11T09:50:26Z

Guenter: Guenter moved page Aufgaben:Aufgabe 1.10: Einige Generatormatrizen to Aufgaben:Exercise 1.10: Some Generator Matrices

2022-05-11T09:45:26Z

Guenter moved page Aufgabe 1.10: Einige Generatormatrizen to Exercise 1.10: Some Generator Matrices

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:52:19Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

Javier: Text replacement - "[[Kanalcodierung" to "[[Channel_Coding"

2020-07-09T12:54:31Z

Text replacement - "[[Kanalcodierung" to "[[Channel_Coding"

@@ Line 86: / Line 86: @@
 '''(2)'''&nbsp;  Correct is the&nbsp; <u>solution suggestion 2</u>:
-*Since this is a linear code,&nbsp; the modulo 2 sum must also be a valid codeword:
+*Since this is a linear code,&nbsp; the modulo 2 sum must also be a valid code word:
 :$$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.$$
 *Likewise the all zero word:

@@ Line 100: / Line 100: @@
 <u>Note:</u> The code given here
-:$$\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 0, 1), (1, 0, 0, 1, 1, 0), \hspace{0.1cm}(1, 1, 0, 0, 1, 1) \}$$
+:$$\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm} (1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 0, 1, 1) \}$$
-is not very effective, since $p_{1} = x_{3}$ is always $0$. By puncturing this redundant bit you get the code
+is not very effective,&nbsp; since $p_{1} = x_{3}$&nbsp; is always zero.&nbsp; By puncturing this redundant bit you get the code
-:$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 1, 0, 1), (1, 0, 1, 1, 0), \hspace{0.1cm}(1, 1, 0, 1, 1) \}$$
+:$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 1, 0, 1), \hspace{0.3cm} (1, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 0, 1, 1) \}$$
-with the same minimum distance $d_{\rm min} = 3$, but larger code rate $R = 2/5$ compared to $R = 1/3$.
+with the same minimum distance&nbsp; $d_{\rm min} = 3$,&nbsp; but larger code rate&nbsp; $R = 2/5$&nbsp; compared to&nbsp; $R = 1/3$.
-'''(4)'''&nbsp;  Correct are the <u>suggested solutions 1 and 2</u>:
+'''(4)'''&nbsp;  Correct are the&nbsp; <u>suggested solutions 1 and 2</u>:
-*The three rows $g_1, \ g_2$ and $g_3$ of the matrix $\mathbf{G}_{\rm A}$ are suitable as basis vectors, since they are linearly independent, that is, it holds
+*The three rows&nbsp; $g_1, \ g_2$ and $g_3$&nbsp; of the matrix&nbsp; $\mathbf{G}_{\rm A}$&nbsp; are suitable as basis vectors,&nbsp; since they are linearly independent,&nbsp; that is,&nbsp; it holds
 :$$\underline{g}_1 \oplus \underline{g}_2 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_3\hspace{0.05cm},\hspace{0.5cm}
 \underline{g}_1 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_2\hspace{0.05cm},\hspace{0.5cm}
 \underline{g}_2 \oplus \underline{g}_3 \hspace{-0.15cm} \ \ne \ \hspace{-0.15cm} \underline{g}_1\hspace{0.05cm}.$$
-*The same is true for matrix $\mathbf{G}_{\rm B}$. The basis vectors are chosen here so that the code is also systematic.
+*For the last generator matrix holds:&nbsp; $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$ &nbsp; ⇒ &nbsp; the rank of matrix&nbsp; $(2)$&nbsp; is smaller than its order&nbsp; $(2)$.
-−
-*For the last generator matrix holds: $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$ &nbsp; ⇒ &nbsp; the rank of matrix (2) is smaller than its order (3).
+*Here not only&nbsp;  $\underline{u} = (0, 0, 0)$&nbsp; leads to the code word&nbsp; $(0, 0, 0, 0, 0)$,&nbsp; but also&nbsp; $\underline{u} = (1, 1, 1)$.
 {{ML-Fuß}}

@@ Line 96: / Line 96: @@
 *Basis vectors of the generator matrix&nbsp; $\mathbf{G}$&nbsp; are, for example,&nbsp; the two given code words,&nbsp; from which the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; can also be determined:
 :$${ \boldsymbol{\rm G}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1 \end{pmatrix}	\hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 0 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 1 &0 &0 &0 &1 &0\\ 0 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
-*In general,&nbsp; the&nbsp; $k$&nbsp; basis vectors of the generator matrix&nbsp; $\mathbf{G}$&nbsp; form a&nbsp; $k$-dimensional subspace and the&nbsp; $m×n$&nbsp; matrix&nbsp; $\mathbf{H}$&nbsp; $($with $m = n - k$$)$&nbsp; forms an orthogonal subspace of dimension&nbsp; $m$.
+*In general,&nbsp; the&nbsp; $k$&nbsp; basis vectors of the generator matrix&nbsp; $\mathbf{G}$&nbsp; form a&nbsp; $k$-dimensional subspace and the&nbsp; $m×n$&nbsp; matrix&nbsp; $\mathbf{H}$&nbsp; $($with $m = n - k)$&nbsp; forms an orthogonal subspace of dimension&nbsp; $m$.

@@ Line 76: / Line 76: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct are the <u>suggested solutions 2 and 3</u>:
+'''(1)'''&nbsp; Correct are the&nbsp; <u>suggested solutions 2 and 3</u>:
-*The codeword length is $n = $6 &nbsp;⇒ &nbsp;the $(5, \, 2)$ code is not eligible.
+*The code word length is&nbsp; $n = 6$ &nbsp; ⇒ &nbsp;the&nbsp; $(5, \, 2)$&nbsp; code is not eligible.
-*For a $(6, \, 2)$ code, there are $2^2 = 4$ distinct codewords, and for the $(6, \, 3)$ code, there are correspondingly $2^3 = 8$.
-*By specifying only two codewords, neither the $(6, \, 2)$ code nor the $(6, \, 3)$ code can be excluded.
+*For a&nbsp; $(6, \, 2)$&nbsp; code,&nbsp; there are&nbsp; $2^2 = 4$&nbsp; distinct code words,&nbsp; and for the&nbsp; $(6, \, 3)$&nbsp; code,&nbsp; there are correspondingly&nbsp; $2^3 = 8$.
-'''(2)'''&nbsp;  Correct is the <u>solution suggestion 2</u>:
+'''(2)'''&nbsp;  Correct is the&nbsp; <u>solution suggestion 2</u>:
-*Since this is a linear code, the modulo $2$ sum must also be a valid codeword:
+*Since this is a linear code,&nbsp; the modulo 2 sum must also be a valid codeword:
 :$$(0, 1, 0, 1, 0, 1) \oplus (1, 0, 0, 1, 1, 0) = (1, 1, 0, 0, 1, 1)\hspace{0.05cm}.$$
 *Likewise the all zero word:
@@ Line 91: / Line 93: @@
-'''(3)'''&nbsp; Correct here are the <u>statements 1 to 3</u>:
+'''(3)'''&nbsp; Correct are here  the&nbsp; <u>statements 1 to 3</u>:
-*Basis vectors of the generator matrix $\mathbf{G}$ are, for example, the two given codewords, from which the parity-check matrix $\mathbf{H}$ can also be determined:
+*Basis vectors of the generator matrix&nbsp; $\mathbf{G}$&nbsp; are, for example,&nbsp; the two given code words,&nbsp; from which the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; can also be determined:
 :$${ \boldsymbol{\rm G}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1 \end{pmatrix}	\hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 0 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 1 &0 &0 &0 &1 &0\\ 0 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
-*In general, the $k$ basis vectors of the generator matrix $\mathbf{G}$ form a $k$-dimensional subspace and the $m×n$ matrix $\mathbf{H}$ (with $m = n - k$) forms an orthogonal subspace of dimension $m$.
+*In general,&nbsp; the&nbsp; $k$&nbsp; basis vectors of the generator matrix&nbsp; $\mathbf{G}$&nbsp; form a&nbsp; $k$-dimensional subspace and the&nbsp; $m×n$&nbsp; matrix&nbsp; $\mathbf{H}$&nbsp; $($with $m = n - k$$)$&nbsp; forms an orthogonal subspace of dimension&nbsp; $m$.

@@ Line 4: / Line 4: @@
 [[File:P_ID2404__KC_A_1_10.png|right|frame|Considered generator matrices]]
-We now consider various binary codes of uniform length&nbsp; $n$. All codes of the form
+We now consider various binary codes of uniform length&nbsp; $n$.&nbsp; All codes of the form
-:$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1, x_2, \ \text{...} \  \hspace{0.05cm}, x_n) \hspace{0.5cm}\text{mit}
+:$$\underline{x} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} ( x_1,\ x_2, \ \text{...} \  \hspace{0.05cm},\ x_n) \hspace{0.5cm}\text{with}
-\hspace{0.5cm} x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0, 1 \},\hspace{0.2cm} i = 1, \hspace{0.05cm} \text{...} \ \hspace{0.05cm}, n$$
+\hspace{0.5cm} x_i \hspace{-0.15cm}\ \in \ \hspace{-0.15cm} \{ 0,\ 1 \},\hspace{0.2cm} i = 1, \hspace{0.05cm} \text{...} \ \hspace{0.05cm}, n$$
-can be represented and interpreted in an $n$-dimensional vector space. &nbsp; ⇒ &nbsp; ${\rm GF}(2^n)$.
+can be represented and interpreted in an&nbsp; $n$-dimensional vector space. &nbsp; ⇒ &nbsp; ${\rm GF}(2^n)$.
-A&nbsp; $k×n$ generator matrix&nbsp; $\mathbf{G}$&nbsp; (i.e. a matrix with&nbsp; $k$&nbsp; rows and&nbsp; $n$&nbsp; columns) yields a&nbsp; $(n, \, k)$ code, but only if the rank of the matrix&nbsp; $\mathbf{G}$&nbsp; is also equal&nbsp; $k$&nbsp;. Further holds:
+The&nbsp; $k×n$&nbsp; generator matrix&nbsp; $\mathbf{G}$&nbsp; (matrix with&nbsp; $k$&nbsp; rows and&nbsp; $n$&nbsp; columns)&nbsp; yields a&nbsp; $(n, \, k)$&nbsp; code,&nbsp; but only if the rank of the matrix&nbsp; $\mathbf{G}$&nbsp; is also equal&nbsp; $k$.&nbsp; Further holds:
-*Each code&nbsp; $\mathcal{C}$&nbsp; spans a&nbsp; $k$-dimensional linear subspace of the Galois field&nbsp; ${\rm GF}(2^n)$&nbsp;.
+*Each code&nbsp; $\mathcal{C}$&nbsp; spans a&nbsp; $k$-dimensional linear subspace of the Galois field&nbsp; ${\rm GF}(2^n)$.
-*As basis vectors of this subspace,&nbsp; $k$&nbsp; independent codewords of&nbsp; $\mathcal{C}$&nbsp; can be used. There is no further restriction for the basis vectors.
+*As basis vectors of this subspace,&nbsp; $k$&nbsp; independent code words of&nbsp; $\mathcal{C}$&nbsp; can be used.&nbsp; There is no further restriction for the basis vectors.
-*The parity-check matrix&nbsp; $\mathbf{H}$&nbsp; also spans a subspace of&nbsp; ${\rm GF}(2^n)$&nbsp; . But this has dimension&nbsp; $m = n - k$&nbsp; and is orthogonal to the subspace based on&nbsp; $\mathbf{G}$&nbsp;.
+*The parity-check matrix&nbsp; $\mathbf{H}$&nbsp; also spans a subspace of&nbsp; ${\rm GF}(2^n)$.&nbsp; But this has dimension&nbsp; $m = n - k$&nbsp; and is orthogonal to the subspace based on&nbsp; $\mathbf{G}$.
-*For a linear code,&nbsp; $\underline{x} = \underline{u} - \boldsymbol{ {\rm G}}$, where&nbsp; $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$&nbsp; indicates the information word. A systematic code exists if&nbsp; $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$&nbsp; holds.
+*For a linear code &nbsp; &rArr; &nbsp; $\underline{x} = \underline{u} \cdot \boldsymbol{ {\rm G}}$,&nbsp; where&nbsp; $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$&nbsp; indicates the information word.&nbsp; A systematic code exists if&nbsp; $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$&nbsp; holds.
-Hints :
+*For the whole exercise holds&nbsp; $n = 6$.
-*This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|General Description of Linear Block Codes]].
+*In the subtask&nbsp; '''(4)'''&nbsp; it is to be clarified which of the matrices&nbsp; $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ resp. $ \boldsymbol{ {\rm G}}_{\rm C}$&nbsp; result in a&nbsp; $(6, \, 3)$&nbsp; block code with the code words listed below:
-:$$   (  0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 0, 1, 0, 1, 1), \hspace{0.1cm}(0, 1, 0, 1, 0, 1), \hspace{0.1cm}(0, 1, 1, 1, 1, 0), \hspace{0.1cm} (  1, 0, 0, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1), \hspace{0.1cm}(1, 1, 0, 0, 1, 1), \hspace{0.1cm}(1, 1, 1, 0, 0, 0)\hspace{0.05cm}.$$
+:$$   (  0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 0, 1, 0, 1, 1), \hspace{0.3cm}(0, 1, 0, 1, 0, 1), \hspace{0.3cm}(0, 1, 1, 1, 1, 0), \hspace{0.3cm} (  1, 0, 0, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1), \hspace{0.3cm}(1, 1, 0, 0, 1, 1), \hspace{0.3cm}(1, 1, 1, 0, 0, 0)\hspace{0.05cm}.$$
@@ Line 40: / Line 40: @@
 ===Questions===
 <quiz display=simple>
-{Known are only the two code words&nbsp; $(0, 1, 0, 1, 0, 1)$&nbsp; and&nbsp; $(1, 0, 0, 1, 1, 0)$&nbsp; of a linear code. Which statements are true?
+{Known are only the two code words&nbsp; $(0, 1, 0, 1, 0, 1)$&nbsp; and&nbsp; $(1, 0, 0, 1, 1, 0)$&nbsp; of a linear code.&nbsp; Which statements are true?
 |type="[]"}
-- It could be a&nbsp; $(5, \, 2)$ code.
+- It could be a&nbsp; $(5, \, 2)$&nbsp; code.
-+ It could be a&nbsp; $(6, \, 2)$ code.
++ It could be a&nbsp; $(6, \, 2)$&nbsp; code.
-+ It could be a&nbsp; $(6, \, 3)$ code.
++ It could be a&nbsp; $(6, \, 3)$&nbsp; code.
-{What are the four code words of the linear&nbsp; $(6, \, 2)$ code explicitly?
+{What are the four code words of the linear&nbsp; $(6, \, 2)$&nbsp; code explicitly?
-|type="[]"}
+|type="()"}
 - $(0 0 1 0 1 1), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).$
 + $(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 0 0 1 1).$
@@ Line 54: / Line 54: @@
-{Which statements are true for this&nbsp; $(6, \, 2)$ code $C$?
+{Which statements are true for this&nbsp; $(6, \, 2)$&nbsp; code&nbsp; $\mathcal{C}$?
 |type="[]"}
-+ For all codewords&nbsp; $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$&nbsp; $\underline{x}_{i} \in {\rm GF}(2^6)$.
++ For all code words&nbsp; $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$ &nbsp; &rArr; &nbsp; $\underline{x}_{i} \in {\rm GF}(2^6)$.
-+ $C$&nbsp; is a two-dimensional linear subvector space of&nbsp; ${\rm GF}(2^6)$.
++ $\mathcal{C}$&nbsp; is a two-dimensional linear subvector space of&nbsp; ${\rm GF}(2^6)$.
-+ $\mathbf{G}$&nbsp; gives basis vectors of this subvector space&nbsp; ${\rm GF}(2^2)$&nbsp;.
++ $\mathbf{G}$&nbsp; gives basis vectors of this subvector space&nbsp; ${\rm GF}(2^2)$.
-- $\mathbf{G}$&nbsp; and&nbsp; $\mathbf{H}$&nbsp; are each&nbsp; $2×6$ matrices.
+- $\mathbf{G}$&nbsp; and&nbsp; $\mathbf{H}$&nbsp; are each&nbsp; $2×6$&nbsp; matrices.
-{Which of the generator matrices given in the graphic result in a&nbsp; $(6, \, 3)$ code?
+{Which of the generator matrices given in the graphic result in a&nbsp; $(6, \, 3)$&nbsp; code?
 |type="[]"}
-+ the generator matrix&nbsp; $\boldsymbol{ {\rm G}}_{\rm A}$,
++ The generator matrix&nbsp; $\boldsymbol{ {\rm G}}_{\rm A}$,
 + the generator matrix&nbsp; $\boldsymbol{ {\rm G}}_{\rm B}$,
 - the generator matrix&nbsp; $\boldsymbol{ {\rm G}}_{\rm C}$.

← Older revision		Revision as of 09:50, 11 May 2022
Line 120:		Line 120:


−	[[Category:Channel Coding: Exercises\|^1.4 ~~Beschreibung linearer Blockcodes~~^]]	+	[[Category:Channel Coding: Exercises\|^1.4 Linear Block Code Description^]]

← Older revision	Revision as of 09:45, 11 May 2022
(No difference)

← Older revision		Revision as of 12:52, 23 March 2021
Line 120:		Line 120:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^1.4 Beschreibung linearer Blockcodes^]]	+	[[Category:Channel Coding: Exercises\|^1.4 Beschreibung linearer Blockcodes^]]

@@ Line 20: / Line 20: @@
 *Bei einem linearen Code gilt&nbsp; $\underline{x} = \underline{u} · \boldsymbol{ {\rm G}}$, wobei&nbsp; $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$&nbsp; das Informationswort angibt. Ein systematischer Code liegt vor, wenn&nbsp; $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$&nbsp; gilt.
-*Bei einem systematischen Code besteht ein einfacher Zusammenhang zwischen&nbsp; $\mathbf{G}$&nbsp; und&nbsp; $\mathbf{H}$. Nähere Angaben hierzu finden Sie im&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]].
+*Bei einem systematischen Code besteht ein einfacher Zusammenhang zwischen&nbsp; $\mathbf{G}$&nbsp; und&nbsp; $\mathbf{H}$. Nähere Angaben hierzu finden Sie im&nbsp; [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Theorieteil]].
@@ Line 29: / Line 29: @@
 ''Hinweise'' :
-*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
+*Die Aufgabe gehört zum Kapitel&nbsp; [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
 * Für die gesamte Aufgabe gilt&nbsp; $n = 6$.
 *In der Teilaufgabe '''(4)''' soll geklärt werden, welche der Matrizen&nbsp; $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ bzw. $ \boldsymbol{ {\rm G}}_{\rm C}$&nbsp; zu einem&nbsp;$(6, \, 3)$–Blockcode mit den nachfolgend aufgeführten Codeworten führen: