Aufgaben:Exercise 1.08: Identical Codes - Revision history

Hwang at 16:00, 23 January 2023

2023-01-23T16:00:04Z

Guenter at 15:05, 10 July 2022

2022-07-10T15:05:47Z

Guenter at 14:14, 10 July 2022

2022-07-10T14:14:00Z

Guenter at 14:13, 10 July 2022

2022-07-10T14:13:04Z

Noah at 12:33, 6 July 2022

2022-07-06T12:33:47Z

Show changes

Noah at 20:42, 5 July 2022

2022-07-05T20:42:15Z

Guenter at 09:48, 11 May 2022

2022-05-11T09:48:19Z

Guenter: Guenter moved page Aufgaben:Aufgabe 1.08: Identische Codes to Aufgaben:Exercise 1.08: Identical Codes

2022-05-11T09:39:31Z

Guenter moved page Aufgabe 1.08: Identische Codes to Exercise 1.08: Identical Codes

Javier: Text replacement - "„" to """

2021-05-28T14:22:52Z

Text replacement - "„" to """

Javier: Text replacement - "”" to """

2021-05-28T14:18:10Z

Text replacement - "”" to """

@@ Line 30: / Line 30: @@
 *This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
-*Reference is made in particular to the page&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Systematic Codes"]].
+*Reference is made in particular to the section&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Systematic Codes"]].
 *Reference is also made to the so-called&nbsp; "Singleton bound".&nbsp;
@@ Line 137: / Line 137: @@
 *For&nbsp; $\underline{u} = (0, 1, 0)$,&nbsp; the code word is thus&nbsp; $(0, 1, 0, ?, ?, ?)$.&nbsp;
-*A comparison with the code table of&nbsp; $\mathcal{C}$&nbsp; on the information page leads to&nbsp; $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.
+*A comparison with the code table of&nbsp; $\mathcal{C}$&nbsp; in the information section leads to&nbsp; $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.

@@ Line 82: / Line 82: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The given code $\mathcal{C}$ is characterized by the following parameters:
+'''(1)'''&nbsp; The given code&nbsp; $\mathcal{C}$&nbsp;is characterized by the following parameters:
 *Number of bits of the code words:&nbsp; $\underline{n = 6}$,
 *Number of bits of information words:&nbsp; $\underline{k = 3}$,
 *Number of parity bit equations:&nbsp; $\underline{m = n - k = 3}$,
 *Code rate:&nbsp; $R = k/n = 3/6  \Rightarrow  \underline{R = 0.5}$,
-*Number of code words (code cardinality):&nbsp; $|\mathcal{C}| = 2^k  \Rightarrow  \underline{|C| = 8}$,
 *minimum Hamming distance (see table):&nbsp; $\underline{d}_{\rm min} \underline{= 3}$.
-'''(2)'''&nbsp; Correct is $\underline{\rm YES}$:
+'''(2)'''&nbsp; Correct is $\underline{\rm Yes}$:
-*According to the singleton bound $d_{\rm min} ≤ n - k + 1$ holds. With $n = 6$ and $k = 3$ one obtains $d_{\rm min} ≤ 4$.
+*According to the singleton bound &nbsp; &rArr; &nbsp;  $d_{\rm min} ≤ n - k + 1$.&nbsp; With&nbsp; $n = 6$&nbsp; and&nbsp; $k = 3$&nbsp; one obtains $d_{\rm min} ≤ 4$.
 *It is thus quite possible to construct a (6, 3) block code with larger minimal distance. How such a code looks, was kindly not asked.
-The minimum distance of all Hamming codes is $d_{\rm min} = 3$, and only the special case with $n = 3$ and $k = 1$ reaches the limit. In contrast, the maximum reach according to the Singleton bound:
+The minimum distance of all Hamming codes is&nbsp; $d_{\rm min} = 3$,&nbsp; and only the special case with&nbsp; $n = 3$&nbsp; and&nbsp; $k = 1$&nbsp; reaches the limit.&nbsp; In contrast,&nbsp; the maximum reach according to the Singleton bound:
-*all [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|repetition codes]] (RC) because $k = 1$ and $d_{\rm min} = n$; this includes the (3, 1) Hamming code, which is known to be identical to RC (3, 1),
+*all&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|repetition codes]]&nbsp; $\rm (RC)$&nbsp; because&nbsp; $k = 1$&nbsp; and&nbsp; $d_{\rm min} = n$;&nbsp; this includes the&nbsp; $\rm (3, 1)$&nbsp; Hamming code,&nbsp; which is known to be identical to&nbsp; $\rm RC\ (3, 1)$,
-*all [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|single parity–check codes]] (SPC): $k = n – 1, d_{\rm min} = 2$.
+*all&nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|single parity–check codes]]&nbsp; $\rm (SPC)$:&nbsp; $k = n - 1,\  d_{\rm min} = 2$.
-'''(3)'''&nbsp; Correct are the <u>solutions 2 and 3</u>:
+'''(3)'''&nbsp; Correct are th&nbsp;e <u>solutions 2 and 3</u>:
-*If we swap rows in the generator matrix $\boldsymbol {\rm G}$, we arrive at an identical code $\mathcal{C}'$. That is, the codes $\mathcal{C}$ and $\mathcal{C}'$ contain the exact same code words.
+*If we swap rows in the generator matrix&nbsp; $\boldsymbol {\rm G}$,&nbsp; we arrive at an identical code&nbsp; $\mathcal{C}'$.&nbsp; That is,&nbsp; the codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}'$&nbsp; contain the exact same code words.
 *For example, after cyclic row swapping $2 \rightarrow 1, 3 \rightarrow 2$, and $1 \rightarrow 3$, one obtains the new matrix
 :$${ \boldsymbol{\rm G}}' = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
-*The first and the last row of the new matrix already comply with the requirements of a systematic code, namely that its generator matrix ${ \boldsymbol{\rm G}_{\rm sys}}$ must start with a diagonal matrix.
+*The first and the last row of the new matrix already comply with the requirements of a systematic code &nbsp; &rArr; &nbsp; matrix ${ \boldsymbol{\rm G}_{\rm sys}}$ must start with a diagonal matrix.
 *Replacing row 2 by the modulo 2 sum of rows 2 and 3, we get:
 :$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
-*This systematic code contains exactly the same codewords as the codes $\mathcal{C}$ and $\mathcal{C}'$.
+*This systematic code contains exactly the same code words as the codes&nbsp; $\mathcal{C}$&nbsp; and&nbsp; $\mathcal{C}'$.
-'''(4)'''&nbsp; Correct are the <u>solutions 1 and 2</u>:
+*For&nbsp; $\underline{u} = (0, 1, 0)$,&nbsp; the code word is thus&nbsp; $(0, 1, 0, ?, ?, ?)$.&nbsp;
-:*the systematic codeword $\underline{x}_{\rm sys}$ must start with $\underline{u}$,
+*A comparison with the code table of&nbsp; $\mathcal{C}$&nbsp; on the information page leads to&nbsp; $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.
-'''(5)'''&nbsp; Only <u>statement 1</u> is correct. The statements for $p_{2}$ and $p_{3}$, on the other hand, are exactly reversed.
+*With systematic coding,&nbsp; the following relationship exists between the generator matrix and the parity-check matrix:
 :$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$
 [[File:P_ID2395__KC_A_1_8_ML.png|right|frame|Chart of parity-check equations]]
-*Applied to the current example, we obtain thus:
+*Applied to the current example,&nbsp; we obtain thus:
 :$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{\rm sys} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
-This results in parity-check equations (see graph):
+*This results in parity-check equations&nbsp; (see graph):
 :$$u_1 \oplus u_2 \oplus p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_1 = u_1 \oplus u_2 \hspace{0.05cm},$$
 :$$ u_1 \oplus u_3 \oplus p_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_2 = u_1 \oplus u_3 \hspace{0.05cm},$$

@@ Line 30: / Line 30: @@
 *This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
-*Reference is made in particular to the page&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematische_Codes|"Systematic Codes"]].
+*Reference is made in particular to the page&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Systematic Codes"]].
 *Reference is also made to the so-called&nbsp; "Singleton bound".&nbsp;

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2393__KC_A_1_8_neu.png|right|frame|Assignment of the&nbsp; $(6, 3)$ block code]]
+[[File:P_ID2393__KC_A_1_8_neu.png|right|frame|Assignment of the&nbsp; $(6, 3)$&nbsp; block code]]
-We consider a block code&nbsp; $\mathcal{C}$ described by the following generator matrix:
+We consider a block code&nbsp; $\mathcal{C}$&nbsp; described by the following generator matrix:
 :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
-The mapping between the information words&nbsp; $\underline{u}$&nbsp; and the code words&nbsp; $\underline{x}$&nbsp; can be seen in the table. It can be seen that this is not a systematic code.
+The mapping between the information words&nbsp; $\underline{u}$&nbsp; and the code words&nbsp; $\underline{x}$&nbsp; can be seen in the table.&nbsp; It can be seen that this is not a&nbsp; "systematic code".
 The following operations are allowed to obtain identical code:
 *swapping or permuting the rows,
-*Multiplying all rows by a constant vector not equal to&nbsp; $0$,
 *Replacing a row with a linear combination between this row and another one.
-Hints:
+*This states that the minimum Hamming distance of a&nbsp; $(n, k)$&nbsp; block code is upper bounded: &nbsp; $d_{\rm min} \le n - k +1.$
@@ Line 51: / Line 52: @@
 $d_{\rm min} \hspace{0.01cm} = \ $ { 3 }
-{Is there a&nbsp; $(6, 3)$ block code with larger minimum distance?
+{Is there any&nbsp; $(6, 3)$&nbsp; block code with larger minimum distance?
 |type="()"}
-+ Ja.
++ Yes.
-- Nein.
+- No.
 {What is the generator matrix&nbsp; ${\boldsymbol{\rm G}}_{\rm sys}$&nbsp; of the identical systematic code?
@@ Line 69: / Line 70: @@
-{Which parity bits has the systematic code&nbsp; $\underline{x}_{\rm sys} = (u_{1}, u_{2}, u_{3}, p_{1}, p_{2}, p_{3})$?
+{Which parity bits has the systematic code&nbsp; $\underline{x}_{\rm sys} = (u_{1},\ u_{2},\ u_{3},\ p_{1},\ p_{2},\ p_{3})$?
 |type="[]"}
 +$p_{1} = u_{1} \oplus u_{2},$

@@ 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_ID2393__KC_A_1_8_neu.png|right|frame|Zuordnung des&nbsp; $(6, 3)$–Blockcodes]]
+[[File:P_ID2393__KC_A_1_8_neu.png|right|frame|Assignment of the&nbsp; $(6, 3)$ block code]]
-Wir betrachten einen Blockcode&nbsp; $\mathcal{C}$, der durch folgende Generatormatrix beschrieben wird:
+We consider a block code&nbsp; $\mathcal{C}$ described by the following generator matrix:
 :$${ \boldsymbol{\rm G}} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
-Die Zuordnung zwischen den Informationsworten&nbsp; $\underline{u}$&nbsp; und den Codeworten&nbsp; $\underline{x}$&nbsp; kann der Tabelle entnommen werden. Man erkennt, dass es sich dabei nicht um einen systematischen Code handelt.
+The mapping between the information words&nbsp; $\underline{u}$&nbsp; and the code words&nbsp; $\underline{x}$&nbsp; can be seen in the table. It can be seen that this is not a systematic code.
-Durch Manipulation der Generatormatrix&nbsp; $\boldsymbol {\rm G}$&nbsp; lassen sich daraus identische Codes konstruieren. Darunter versteht man Codes mit gleichen Codeworten, jedoch unterschiedlicher Zuordnung&nbsp; $\underline{u} \rightarrow \underline{x}$.
+By manipulating the generator matrix&nbsp; $\boldsymbol {\rm G}$&nbsp; identical codes can be constructed from it. This refers to codes with the same code words but different assignments&nbsp; $\underline{u} \rightarrow \underline{x}$.
-*Vertauschen oder Permutieren der Zeilen,
+The following operations are allowed to obtain identical code:
-*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich&nbsp; $0$,
-*Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.
+*swapping or permuting the rows,

← Older revision		Revision as of 09:48, 11 May 2022
Line 150:		Line 150:


−	[[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:39, 11 May 2022
(No difference)

@@ Line 58: / Line 58: @@
 {Wie lautet die Generatormatrix&nbsp; ${\boldsymbol{\rm G}}_{\rm sys}$&nbsp; des identischen systematischen Codes?
 |type="[]"}
-- Die 1. Zeile lautet &nbsp; &bdquo;$1 \ 0 \ 1 \ 1 \ 0 \ 1$".
+- Die 1. Zeile lautet &nbsp; "$1 \ 0 \ 1 \ 1 \ 0 \ 1$".
-+ Die 2. Zeile lautet &nbsp;  &bdquo;$0 \ 1 \ 0 \ 1 \ 0 \ 1$".
++ Die 2. Zeile lautet &nbsp;  "$0 \ 1 \ 0 \ 1 \ 0 \ 1$".
-+ Die 3. Zeile lautet &nbsp;  &bdquo;$0 \ 0 \ 1 \ 0 \ 1 \ 1$".
++ Die 3. Zeile lautet &nbsp;  "$0 \ 0 \ 1 \ 0 \ 1 \ 1$".
 {Welche Zuordnungen ergeben sich bei dieser Codierung?