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

From LNTwww
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes
+
{{quiz-Header|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes
  
 
}}
 
}}
  
[[File:P_ID2391__KC_Z_1_7_neu.png|right|frame|Blockcodes der Länge  $n = 4$ ]]
+
[[File:P_ID2391__KC_Z_1_7_neu.png|right|frame|Block codes of length  $n = 4$ ]]
  
Wir betrachten Blockcodes der Länge  $n = 4$:
+
We consider block codes of length  $n = 4$:
  
*den  [[Channel_Coding/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check]]  Code  $\text{SPC (4, 3)}$   ⇒   "Code 1"   mit der Generatormatrix
+
*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},$$
  
*den  [[Channel_Coding/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscode]]   $\text{RC (4, 1)}$   ⇒   "Code 2"   mit der Prüfmatrix
+
*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},$$
  
*den  $\text{(4, 2)}$–Blockcode   ⇒   "Code 3"   mit der Generatormatrix
+
*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},$$
  
*den  $\text{(4, 2)}$–Blockcode   ⇒   "Code 4"   mit der Generatormatrix
+
*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},$$
  
*einen weiteren "Code 5"   mit dem Codeumfang  $|\hspace{0.05cm}C\hspace{0.05cm}| = 6$.
+
*another "code 5"   with code size  $|\hspace{0.05cm}C\hspace{0.05cm}| = 6$.
  
  
In der Grafik sind die einzelnen Codes explizit angegegeben. Bei den Fragen zu diesen Aufgaben geht es um die Begriffe
+
The individual codes are explicitly indicated in the graphic.  The questions for these tasks are about the terms
  
*[[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes|lineare Codes]],
+
*[[Channel_Coding/General_Description_of_Linear_Block_Codes#Linear_codes_and_cyclic_codes|"linear codes"]],
  
*[[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|systematische Codes]],
+
*[[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"systematic codes"]],
  
*[[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Darstellung_von_SPC_und_RC_als_duale_Codes|duale Codes]].
+
*[[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"]].
  
''Hinweise'' :
 
  
*Die Aufgabe gehört zum Kapitel  [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
 
*Bezug genommen wird aber auchauf die Seiten  [[Channel_Coding/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check Codes]]  sowie [[Channel_Coding/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]].
 
  
  
 
+
===Questions===
 
 
===Fragebogen===
 
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wie lässt sich "Code 5" beschreiben?
+
{How can&nbsp; "code 5"&nbsp; be described?
 
|type="[]"}
 
|type="[]"}
+ In jedem Codewort sind genau zwei Nullen enthalten.
+
+ There are exactly two zeros in each code word.
+ In jedem Codewort sind genau zwei Einsen enthalten.
+
+ There are exactly two ones in each code word.
- Nach jeder $0$ sind die Symbole&nbsp; $0$&nbsp; und&nbsp; $1$&nbsp; gleichwahrscheinlich.
+
- After each&nbsp; "$0$",&nbsp; 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="[]"}
 
|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="[]"}
 
|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="[]"}
 
|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>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Richtig sind die <u>Aussagen 1 und 2</u>:
+
'''(1)'''&nbsp; <u>Statements 1 and 2</u>&nbsp; are correct:
* Deshalb gibt es auch $\rm 4 \ über \ 2 = 6$ Codeworte.  
+
* That is why there are&nbsp; "$\rm 4 \ over \ 2 = 6$"&nbsp; code words.  
* 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.&nbsp; For example,&nbsp; if the first bit is&nbsp; "$0$",&nbsp; there is one code word starting&nbsp; "$00$"&nbsp; and two code words starting&nbsp; "$01$".
  
  
  
'''(2)'''&nbsp; Richtig sind die <u>Aussagen 1 bis 4</u>:
+
'''(2)'''&nbsp; <u>Statements 1 to 4</u>&nbsp; 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&nbsp; $\boldsymbol {\rm G}$&nbsp; and/or a parity-check matrix&nbsp; $\boldsymbol {\rm H}$&nbsp; are linear.  
*Dagegen erfüllt "Code 5" keine der für lineare Codes erforderlichen Bedingungen. Beispielsweise
+
*In contrast,&nbsp; "code 5" does not satisfy any of the conditions required for linear codes.&nbsp; For example
  
:*fehlt das Nullwort,
+
:*is missing the all-zero word,
:*ist der Codeumfang $|\mathcal{C}|$ keine Zweierpotenz,
+
:*the code size&nbsp; $|\mathcal{C}|$&nbsp; 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&nbsp; $(0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1)$&nbsp; no valid code word.
  
  
  
'''(3)'''&nbsp; Richtig sind die <u>Aussagen 1 bis 3</u>:
+
'''(3)'''&nbsp; <u>Statements 1 to 3</u>&nbsp; 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,&nbsp; the first&nbsp; $k$&nbsp; bits of each code word&nbsp; $\underline{x}$&nbsp; must always be equal to the information word&nbsp; $\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&nbsp; $\boldsymbol {\rm G}$&nbsp; is an identity matrix&nbsp; $\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&nbsp; "code 1"&nbsp; $($with dimension&nbsp; $k = 3)$,&nbsp; "code 2" $($with&nbsp; $k = 1)$&nbsp; and&nbsp; "code 3"&nbsp; $($with $k = 2)$.
*Die Generatormatrix von "Code 2" ist allerdings nicht explizit angegeben. Sie lautet:
+
*The generator matrix of&nbsp; "code 2",&nbsp; however,&nbsp; is not explicitly stated.&nbsp; 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)'''&nbsp; Richtig ist die <u>Aussage 1</u>:
+
'''(4)'''&nbsp; <u>Statement 1</u>&nbsp; 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&nbsp; $\boldsymbol {\rm H}$&nbsp; of one code is equal to the generator matrix&nbsp; $\boldsymbol {\rm G}$&nbsp; of the other code.  
*Dies trifft zum Beispiel für "Code 1" und "Code 2" zu.
+
*For example,&nbsp; this is true for "code 1" and "code 2."  
*Für den SPC (4, 3) gilt:
+
*For the&nbsp; $\text{SPC (4, 3)}$&nbsp; 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},$$
  
:und für den Wiederholungscode RC (4, 1):
+
:and for the repetition code&nbsp; $\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}.$$
  
*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,&nbsp; already for dimensional reasons:&nbsp; The&nbsp; $\boldsymbol {\rm G}$&nbsp; matrix  of&nbsp; "code 3"&nbsp; is a&nbsp; $2×4$&nbsp; matrix and the&nbsp; $\boldsymbol {\rm H}$&nbsp; matrix of&nbsp; "code 2"&nbsp; is a $3×4$&nbsp; matrix.
  
*"Code 3" und "Code 4" erfüllen ebenfalls nicht die Bedingungen dualer Codes. Die Prüfgleichungen von
+
*"Code 3"&nbsp; and&nbsp; "code 4"&nbsp; also do not satisfy the conditions of dual codes.&nbsp; 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) \}$$
  
: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}.$$
 
:$$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,&nbsp; the generator matrix of&nbsp; "code 4"&nbsp; 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 Beschreibung linearer Blockcodes
+
[[Category:Channel Coding: Exercises|^1.4 Linear Block Code Description
  
 
^]]
 
^]]

Latest revision as of 16:59, 23 January 2023

Block codes of length  $n = 4$

We consider block codes of length  $n = 4$:

$${ \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 :



Questions

1

How can  "code 5"  be described?

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.

2

Which of the following block codes are linear?

code 1,
code 2,
code 3,
code 4,
code 5.

3

Which of the following block codes are systematic?

code 1,
code 2,
code 3,
code 4,
code 5.

4

Which code pairs are dual to each other?

code 1 and code 2,
code 2 and code 3,
code 3 and code 4.


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