Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Exercise 1.07Z: Classification of Block Codes

From LNTwww
Revision as of 16:21, 8 May 2019 by Guenter (talk | contribs)

Blockcodes der Länge  n=4

Wir betrachten Blockcodes der Länge  n=4:

  • den  Single Parity–check  Code  SPC (4, 3)   ⇒   „Code 1”   mit der Generatormatrix
{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &1\\ 0 &1 &0 &1\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},
  • den  Wiederholungscode   \text{RC (4, 1)}   ⇒   „Code 2”   mit der Prüfmatrix
{ \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
{ \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
{ \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.


In der Grafik sind die einzelnen Codes explizit angegegeben. Bei den Fragen zu diesen Aufgaben geht es um die Begriffe




Hinweise :



Fragebogen

1

Wie lässt sich „Code 5” beschreiben?

In jedem Codewort sind genau zwei Nullen enthalten.
In jedem Codewort sind genau zwei Einsen enthalten.
Nach jeder 0 sind die Symbole  0  und  1  gleichwahrscheinlich.

2

Welche der folgenden Blockcodes sind linear?

Code 1,
Code 2,
Code 3,
Code 4,
Code 5.

3

Welche der folgenden Blockcodes sind systematisch?

Code 1,
Code 2,
Code 3,
Code 4,
Code 5.

4

Welche Codepaare sind zueinander dual?

Code 1 und Code 2,
Code 2 und Code 3,
Code 3 und Code 4.


Musterlösung

(1)  Richtig sind die Aussagen 1 und 2:

  • Deshalb gibt es auch \rm 4 \ über \ 2 = 6 Codeworte.
  • 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.


(2)  Richtig sind die Aussagen 1 bis 4:

  • Alle Codes, die durch eine Generatormatrix \boldsymbol {\rm G} und/oder eine Prüfmatrix \boldsymbol {\rm H} beschrieben werden können, sind linear.
  • Dagegen erfüllt „Code 5” keine der für lineare Codes erforderlichen Bedingungen. Beispielsweise
  • fehlt das Nullwort,
  • ist der Codeumfang |\mathcal{C}| keine Zweierpotenz,
  • ergibt (0, 1, 0, 1) \oplus (1, 0, 1, 0) = (1, 1, 1, 1) kein gültiges Codewort.


(3)  Richtig sind die Aussagen 1 bis 3:

  • Bei einem systematischen Code müssen stets die ersten k Bit eines jeden Codewortes \underline{x} gleich dem Informationswort \underline{u} sein.
  • Dies wird erreicht, wenn der Beginn der Generatormatrix \boldsymbol {\rm G} eine Einheitsmatrix \boldsymbol{\rm I}_{k} darstellt.
  • Dies trifft für „Code 1” (mit Dimension k = 3), „Code 2” (mit k = 1) und „Code 3” (mit k = 2) zu.
  • Die Generatormatrix von „Code 2” ist allerdings nicht explizit angegeben. Sie lautet:
{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.


(4)  Richtig ist die Aussage 1:

  • 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.
  • Dies trifft zum Beispiel für „Code 1” und „Code 2” zu.
  • Für den SPC (4, 3) gilt:
{ \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):
{ \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.
  • „Code 3” und „Code 4” erfüllen ebenfalls nicht die Bedingungen dualer Codes. Die Prüfgleichungen von
{\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:
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:
{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &0 &0\\ 0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.