Difference between revisions of "Aufgaben:Exercise 1.10: Some Generator Matrices"
From LNTwww
(Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes }} [[File:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-C…“) |
|||
| (25 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
| − | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes |
| + | }} | ||
| + | |||
| + | [[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 | ||
| + | :$$\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 [[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.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=== | ||
<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? |
|type="[]"} | |type="[]"} | ||
| − | - | + | - It could be a $(5, \, 2)$ code. |
| − | + | + | + It could be a $(6, \, 2)$ code. |
| + | + It could be a $(6, \, 3)$ code. | ||
| + | |||
| + | |||
| + | {What are the four code words of the linear $(6, \, 2)$ code explicitly? | ||
| + | |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).$ | ||
| + | - $(0 0 0 0 0 0), \ (0 1 0 1 0 1), \ (1 0 0 1 1 0), \ (1 1 1 0 0 0).$ | ||
| + | |||
| + | |||
| + | {Which statements are true for this $(6, \, 2)$ code $\mathcal{C}$? | ||
| + | |type="[]"} | ||
| + | + For all code words $(i = 1,\hspace{0.05cm} \text{ ...} \ , 4)$ ⇒ $\underline{x}_{i} \in {\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}$ and $\mathbf{H}$ are each $2×6$ matrices. | ||
| + | |||
| + | |||
| + | {Which of the generator matrices given in the graphic result in a $(6, \, 3)$ code? | ||
| + | |type="[]"} | ||
| + | + The generator matrix $\boldsymbol{ {\rm G}}_{\rm A}$, | ||
| + | + the generator matrix $\boldsymbol{ {\rm G}}_{\rm B}$, | ||
| + | - the generator matrix $\boldsymbol{ {\rm G}}_{\rm C}$. | ||
| − | |||
| − | |||
| − | |||
| Line 23: | Line 74: | ||
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''1 | + | '''(1)''' Correct are the <u>suggested solutions 2 and 3</u>: |
| − | '''2 | + | *The code word length is $n = 6$ ⇒ the $(5, \, 2)$ code is not eligible. |
| − | '''3 | + | |
| − | '''4 | + | *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>: | ||
| + | *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 <u>statements 1 to 3</u>: | ||
| + | *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$. | ||
| + | |||
| + | |||
| + | <u>Note:</u> 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 <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 | ||
| + | :$$\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)$. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
| − | [[Category: | + | [[Category:Channel Coding: Exercises|^1.4 Linear Block Code Description^]] |
| − | |||
| − | ^]] | ||
Latest revision as of 18: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)$.
