Difference between revisions of "Aufgaben:Exercise 1.07Z: Classification of Block Codes"
From LNTwww
m (Guenter moved page Aufgabe 1.07Z: Klassifizierung von Blockcodes to Exercise 1.07Z: Classification of Block Codes) |
|||
(10 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes |
}} | }} | ||
− | [[File:P_ID2391__KC_Z_1_7_neu.png|right|frame| | + | [[File:P_ID2391__KC_Z_1_7_neu.png|right|frame|Block codes of length $n = 4$ ]] |
− | + | We consider block codes of length $n = 4$: | |
− | * | + | *the [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|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},$$ | :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$ | ||
− | * | + | *the [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|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},$$ | :$${ \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},$$ | :$${ \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},$$ | :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$ | ||
− | * | + | *another "code 5" with code size $|\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 | |
− | *[[Channel_Coding/ | + | *[[Channel_Coding/General_Description_of_Linear_Block_Codes#Linear_codes_and_cyclic_codes|"linear codes"]], |
− | *[[Channel_Coding/ | + | *[[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"systematic codes"]], |
− | *[[Channel_Coding/ | + | *[[Channel_Coding/General_Description_of_Linear_Block_Codes#Representation_of_SPC_and_RC_as_dual_codes|"dual codes"]]. |
+ | Hints : | ||
+ | *This exercise belongs to the chapter [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General description of linear block codes"]]. | ||
+ | *Reference is also made to the sections [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|"Single parity–check codes"]] and [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|"Repetition codes"]]. | ||
− | |||
− | |||
− | |||
− | + | ===Questions=== | |
− | |||
− | === | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {How can "code 5" be described? |
|type="[]"} | |type="[]"} | ||
− | + | + | + There are exactly two zeros in each code word. |
− | + | + | + There are exactly two ones in each code word. |
− | - | + | - After each "$0$", the symbols "$0$" and "$1$" are equally likely. |
− | { | + | {Which of the following block codes are linear? |
|type="[]"} | |type="[]"} | ||
− | + | + | + code 1, |
− | + | + | + code 2, |
− | + | + | + code 3, |
− | + | + | + code 4, |
− | - | + | - code 5. |
− | { | + | {Which of the following block codes are systematic? |
|type="[]"} | |type="[]"} | ||
− | + | + | + code 1, |
− | + | + | + code 2, |
− | + | + | + code 3, |
− | - | + | - code 4, |
− | - | + | - code 5. |
− | { | + | {Which code pairs are dual to each other? |
|type="[]"} | |type="[]"} | ||
− | + | + | + code 1 and code 2, |
− | - | + | - code 2 and code 3, |
− | - | + | - code 3 and code 4. |
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' <u>Statements 1 and 2</u> are correct: |
− | * | + | * That is why there are "$\rm 4 \ over \ 2 = 6$" code words. |
− | * | + | * Statement 3 is false. For example, if the first bit is "$0$", there is one code word starting "$00$" and two code words starting "$01$". |
− | '''(2)''' | + | '''(2)''' <u>Statements 1 to 4</u> 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 size $|\mathcal{C}|$ is not a power of two, |
− | :* | + | :*gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid code word. |
− | '''(3)''' | + | '''(3)''' <u>Statements 1 to 3</u> are correct: |
− | * | + | *In a systematic code, the first $k$ bits of each code word $\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 an identity 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}.$$ | :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$ | ||
− | '''(4)''' | + | '''(4)''' <u>Statement 1</u> 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 $\text{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},$$ | :$${ \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 $\text{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}.$$ | :$${ \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 $\boldsymbol {\rm G}$ matrix of "code 3" is a $2×4$ matrix and the $\boldsymbol {\rm H}$ matrix of "code 2" is a $3×4$ matrix. |
− | *"Code 3" | + | *"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) \}$$ | :$${\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}.$$ | :$$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}.$$ | :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$ | ||
Line 138: | Line 136: | ||
− | [[Category:Channel Coding: Exercises|^1.4 | + | [[Category:Channel Coding: Exercises|^1.4 Linear Block Code Description |
^]] | ^]] |
Latest revision as of 16:59, 23 January 2023
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 code size $|\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
Hints :
- This exercise belongs to the chapter "General description of linear block codes".
- Reference is also made to the sections "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$" code words.
- Statement 3 is false. For example, if the first bit is "$0$", there is one code word starting "$00$" and two code words 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 size $|\mathcal{C}|$ is not a power of two,
- gives $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$ no valid code word.
(3) Statements 1 to 3 are correct:
- In a systematic code, the first $k$ bits of each code word $\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 an identity 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 $\text{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 $\text{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 $\boldsymbol {\rm G}$ matrix of "code 3" is a $2×4$ matrix and the $\boldsymbol {\rm H}$ matrix 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}.$$