Difference between revisions of "Aufgaben:Exercise 1.10: Some Generator Matrices"
From LNTwww
| (4 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
[[File:P_ID2404__KC_A_1_10.png|right|frame|Considered generator matrices]] | [[File:P_ID2404__KC_A_1_10.png|right|frame|Considered generator matrices]] | ||
| − | We now consider various binary codes of uniform length $n$. All codes of the form | + | We now consider various binary codes of uniform length $n$. 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{ | + | :$$\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. ⇒ ${\rm GF}(2^n)$. | + | can be represented and interpreted in an $n$-dimensional vector space. ⇒ ${\rm GF}(2^n)$. |
| − | + | The $k×n$ generator matrix $\mathbf{G}$ (matrix with $k$ rows and $n$ columns) yields a $(n, \, k)$ code, but only if the rank of the matrix $\mathbf{G}$ is also equal $k$. Further holds: | |
| − | *Each code $\mathcal{C}$ spans a $k$-dimensional linear subspace of the Galois field ${\rm GF}(2^n)$ | + | *Each code $\mathcal{C}$ spans a $k$-dimensional linear subspace of the Galois field ${\rm GF}(2^n)$. |
| − | *As basis vectors of this subspace, $k$ independent | + | *As basis vectors of this subspace, $k$ independent code words of $\mathcal{C}$ can be used. There is no further restriction for the basis vectors. |
| − | *The parity-check matrix $\mathbf{H}$ also spans a subspace of ${\rm GF}(2^n)$ | + | *The parity-check matrix $\mathbf{H}$ also spans a subspace of ${\rm GF}(2^n)$. But this has dimension $m = n - k$ and is orthogonal to the subspace based on $\mathbf{G}$. |
| − | *For a linear code | + | *For a linear code ⇒ $\underline{x} = \underline{u} \cdot \boldsymbol{ {\rm G}}$, where $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$ indicates the information word. A systematic code exists if $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$ holds. |
| + | *In a systematic code, there is a simple relationship between $\mathbf{G}$ and $\mathbf{H}$. For more details, see the [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Theory Section"]]. | ||
| − | |||
| + | Hints : | ||
| + | *This exercise belongs to the chapter [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]]. | ||
| − | + | *For the whole exercise holds $n = 6$. | |
| − | * | + | *In the subtask '''(4)''' it is to be clarified which of the matrices $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ resp. $ \boldsymbol{ {\rm G}}_{\rm C}$ result in a $(6, \, 3)$ block code with the code words listed below: |
| − | |||
| − | |||
| − | :$$ ( 0, 0, 0, 0, 0, 0), \hspace{0. | + | :$$ ( 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=== | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | {Known are only the two code words $(0, 1, 0, 1, 0, 1)$ and $(1, 0, 0, 1, 1, 0)$ of a linear code. Which statements are true? | + | {Known are only the two code words $(0, 1, 0, 1, 0, 1)$ and $(1, 0, 0, 1, 1, 0)$ of a linear code. Which statements are true? |
|type="[]"} | |type="[]"} | ||
| − | - It could be a $(5, \, 2)$ code. | + | - It could be a $(5, \, 2)$ code. |
| − | + It could be a $(6, \, 2)$ code. | + | + It could be a $(6, \, 2)$ code. |
| − | + It could be a $(6, \, 3)$ code. | + | + It could be a $(6, \, 3)$ code. |
| − | {What are the four code words of the linear $(6, \, 2)$ code explicitly? | + | {What are the four code words of the linear $(6, \, 2)$ 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 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).$ | + $(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 $(6, \, 2)$ code $C$? | + | {Which statements are true for this $(6, \, 2)$ code $\mathcal{C}$? |
|type="[]"} | |type="[]"} | ||
| − | + For all | + | + For all code words $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$ ⇒ $\underline{x}_{i} \in {\rm GF}(2^6)$. |
| − | + $C$ is a two-dimensional linear subvector space of ${\rm GF}(2^6)$. | + | + $\mathcal{C}$ is a two-dimensional linear subvector space of ${\rm GF}(2^6)$. |
| − | + $\mathbf{G}$ gives basis vectors of this subvector space ${\rm GF}(2^2)$ | + | + $\mathbf{G}$ gives basis vectors of this subvector space ${\rm GF}(2^2)$. |
| − | - $\mathbf{G}$ and $\mathbf{H}$ are each $2×6$ matrices. | + | - $\mathbf{G}$ and $\mathbf{H}$ are each $2×6$ matrices. |
| − | {Which of the generator matrices given in the graphic result in a $(6, \, 3)$ code? | + | {Which of the generator matrices given in the graphic result in a $(6, \, 3)$ code? |
|type="[]"} | |type="[]"} | ||
| − | + | + | + The generator matrix $\boldsymbol{ {\rm G}}_{\rm A}$, |
+ the generator matrix $\boldsymbol{ {\rm G}}_{\rm B}$, | + the generator matrix $\boldsymbol{ {\rm G}}_{\rm B}$, | ||
- the generator matrix $\boldsymbol{ {\rm G}}_{\rm C}$. | - the generator matrix $\boldsymbol{ {\rm G}}_{\rm C}$. | ||
| Line 76: | Line 76: | ||
===Solution=== | ===Solution=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Correct are the <u>suggested solutions 2 and 3</u>: | + | '''(1)''' Correct are the <u>suggested solutions 2 and 3</u>: |
| − | *The | + | *The code word length is $n = 6$ ⇒ the $(5, \, 2)$ code is not eligible. |
| − | *For a $(6, \, 2)$ code, there are $2^2 = 4$ distinct | + | |
| − | *By specifying only two | + | *For a $(6, \, 2)$ code, there are $2^2 = 4$ distinct code words, and for the $(6, \, 3)$ code, there are correspondingly $2^3 = 8$. |
| + | |||
| + | *By specifying only two code words, neither the $(6, \, 2)$ code nor the $(6, \, 3)$ code can be excluded. | ||
| − | '''(2)''' Correct is the <u>solution suggestion 2</u>: | + | '''(2)''' Correct is the <u>solution suggestion 2</u>: |
| − | *Since this is a linear code, the modulo | + | *Since this is a linear code, 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}.$$ | :$$(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: | *Likewise the all zero word: | ||
| Line 91: | Line 93: | ||
| − | '''(3)''' Correct here | + | '''(3)''' Correct are here the <u>statements 1 to 3</u>: |
| − | *Basis vectors of the generator matrix $\mathbf{G}$ are, for example, the two given | + | *Basis vectors of the generator matrix $\mathbf{G}$ are, for example, the two given code words, from which the parity-check matrix $\mathbf{H}$ 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}.$$ | :$${ \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$ | + | *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$. |
<u>Note:</u> The code given here | <u>Note:</u> The code given here | ||
| − | :$$\mathcal{C}_{(6,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0, 0), \hspace{0. | + | :$$\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 | + | is not very effective, since $p_{1} = x_{3}$ is always zero. By puncturing this redundant bit you get the code |
| − | :$$\mathcal{C}_{(5,\hspace{0.05cm} 2)} = \{ (0, 0, 0, 0, 0), \hspace{0. | + | :$$\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 $d_{\rm min} = 3$, but larger code rate $R = 2/5$ compared to $R = 1/3$. |
| − | '''(4)''' Correct are the <u>suggested solutions 1 and 2</u>: | + | '''(4)''' Correct are the <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 $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 |
:$$\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}_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}_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}.$$ | \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: $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$ ⇒ the rank of matrix $(2)$ is smaller than its order $(2)$. | |
| − | + | ||
| − | *For the last generator matrix holds: $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$ ⇒ the rank of matrix (2) is smaller than its order ( | + | *Here not only $\underline{u} = (0, 0, 0)$ leads to the code word $(0, 0, 0, 0, 0)$, but also $\underline{u} = (1, 1, 1)$. |
| − | *Here not only $\underline{u} = (0, 0, 0)$ leads to the | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Latest revision as of 17:57, 1 November 2022
Considered generator matrices
We now consider various binary codes of uniform length $n$. 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{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$$
can be represented and interpreted in an $n$-dimensional vector space. ⇒ ${\rm GF}(2^n)$.
The $k×n$ generator matrix $\mathbf{G}$ (matrix with $k$ rows and $n$ columns) yields a $(n, \, k)$ code, but only if the rank of the matrix $\mathbf{G}$ is also equal $k$. Further holds:
- Each code $\mathcal{C}$ spans a $k$-dimensional linear subspace of the Galois field ${\rm GF}(2^n)$.
- As basis vectors of this subspace, $k$ independent code words of $\mathcal{C}$ can be used. There is no further restriction for the basis vectors.
- The parity-check matrix $\mathbf{H}$ also spans a subspace of ${\rm GF}(2^n)$. But this has dimension $m = n - k$ and is orthogonal to the subspace based on $\mathbf{G}$.
- For a linear code ⇒ $\underline{x} = \underline{u} \cdot \boldsymbol{ {\rm G}}$, where $\underline{u} = (u_{1}, \, u_{2}, \, \text{...} \, , \, u_{k})$ indicates the information word. A systematic code exists if $x_{1} = u_{1}, \, \text{...} \, , \, x_{k} = u_{k}$ holds.
- In a systematic code, there is a simple relationship between $\mathbf{G}$ and $\mathbf{H}$. For more details, see the "Theory Section".
Hints :
- This exercise belongs to the chapter "General Description of Linear Block Codes".
- For the whole exercise holds $n = 6$.
- In the subtask (4) it is to be clarified which of the matrices $\boldsymbol{ {\rm G}}_{\rm A}, \ \boldsymbol{ {\rm G}}_{\rm B}$ resp. $ \boldsymbol{ {\rm G}}_{\rm C}$ result in a $(6, \, 3)$ block code with the code words listed below:
- $$ ( 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}.$$
Questions
Solution
(1) Correct are the suggested solutions 2 and 3:
- The code word length is $n = 6$ ⇒ the $(5, \, 2)$ code is not eligible.
- For a $(6, \, 2)$ code, there are $2^2 = 4$ distinct code words, and for the $(6, \, 3)$ code, there are correspondingly $2^3 = 8$.
- By specifying only two code words, neither the $(6, \, 2)$ code nor the $(6, \, 3)$ code can be excluded.
(2) Correct is the solution suggestion 2:
- Since this is a linear code, 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:
- $$(0, 1, 0, 1, 0, 1) \oplus (0, 1, 0, 1, 0, 1) = (0, 0, 0, 0, 0, 0)\hspace{0.05cm}.$$
(3) Correct are here the statements 1 to 3:
- Basis vectors of the generator matrix $\mathbf{G}$ are, for example, the two given code words, from which the parity-check matrix $\mathbf{H}$ 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$.
Note: The code given here
- $$\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 zero. By puncturing this redundant bit you get the code
- $$\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$.
(4) Correct are the suggested solutions 1 and 2:
- 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
- $$\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: $\underline{g}_{1}⊕\underline{g}_{2} = \underline{g}_{3}$ ⇒ the rank of matrix $(2)$ is smaller than its order $(2)$.
- Here not only $\underline{u} = (0, 0, 0)$ leads to the code word $(0, 0, 0, 0, 0)$, but also $\underline{u} = (1, 1, 1)$.
