Difference between revisions of "Aufgaben:Exercise 1.09: Extended Hamming Code"

From LNTwww
Line 28: Line 28:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
+
 
 +
{Geben Sie die Coderaten von $C_{1}$ und $C_{2}$ an.
 +
|type="{}"}
 +
$\C_{1}:  \ \ \ R$ = { 0.571 3% }
 +
$\C_{2}:  \ \ \ R$ = { 0.5 3% }
 +
 
 +
 
 +
{Geben Sie die minimalen Distanzen von $C_{1}$ und $C_{2}$ an.
 +
|type="{}"}
 +
$\C_{1}: \  \  \ d_{\rm min}$ = { 3 3% }
 +
$\C_{2}: \  \  \ d_{\rm min}$ = { 4 3% }
 +
 
 +
 
 +
{Welches Format besitzt die Prüfmatrix von $C_{2}$?
 +
|type="{}"}
 +
$\ { \boldsymbol{\rm H}}_{2}{\rm :}  \ \ \  {\rm Spaltenzahl}$ = { 8 3% }
 +
$\ { \boldsymbol{\rm H}}_{2}{\rm :}  \ \ \  {\rm  Zeilenzahl}$ = { 4 3% }
 +
 
 +
{Leiten Sie aus der Codetabelle die Gleichung für das Codebit $x_ {8} (= p_{4})$ ab.
 
|type="[]"}
 
|type="[]"}
- Falsch
+
 
+ Richtig
+
- $x_{8} = 0.$
 +
- $x_{8} = x_{1}⊕x_{2}⊕x_{4}⊕x_{5}.$
 +
+ $x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$
 +
 
 +
{Welche Aussagen gelten für ${ \boldsymbol{\rm H}}_{2}$? ''Hinweis:'' Richtig sind 3 von 4 Antworten.
 +
|type="[]"}
 +
 
 +
+ Die erste Zeile lautet:  $1 1 0 1 1 0 0 0$.
 +
+ Die zweite Zeile lautet: $0 1 1 1 0 1 0 0$.
 +
- Die dritte Zeile lautet:  $0 0 0 0 1 1 1 1$.
 +
+ Die letzte Zeile lautet:  $1 1 1 1 1 1 1 1$.
 +
 
 +
{Welche Umformung ist für die letzte Zeile von ${ \boldsymbol{\rm H}}_{2}$ zulässig?
 +
|type="[]"}
 +
- $1 1 1 1 1 1 1 1  →  0 0 0 0 0 0 0 0,$
 +
+ $1 1 1 1 1 1 1 1  →  1 1 1 0 0 0 0 1,$
 +
- $1 1 1 1 1 1 1 1  →  0 0 1 0 1 0 0 0.$
 +
 
 +
{Geben Sie die zugehörige Generatormatrix ${ \boldsymbol{\rm G}}_{2}$ an. Welche Aussagen treffen zu?
 +
|type="[]"}
 +
- ${ \boldsymbol{\rm G}}_{2}$ hat gleiches Format wie die Matrix ${ \boldsymbol{\rm G}}_{1}$  des (7, 4)–Codes.
 +
+ ${ \boldsymbol{\rm G}}_{2}$  beginnt wie ${ \boldsymbol{\rm G}}_{1}$  mit einer Diagonalmatrix ${ \boldsymbol{\rm I}}_{4}$ .
 +
+ ${ \boldsymbol{\rm G}}_{2}$  hat im betrachteten Beispiel das gleiche Format wie ${ \boldsymbol{\rm H}}_{2}$ .
 +
 
  
  
{Input-Box Frage
 
|type="{}"}
 
$\alpha$ = { 0.3 }
 
  
  

Revision as of 19:07, 7 December 2017

(7, 4) Hamming – (8, 4) Erweiterung

Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind. Die ersten vier Bit eines jeden Codewortes x geben das jeweilige Informationswort u wider (schwarze Schrift). Danach folgen $m = n – k$ Prüfbit (rote Schrift).

  • Der systematische (7, 4)–Hamming–Code wurde bereits in Aufgabe 1.6 sowie Aufgabe 1.07 behandelt. Prüfmatrix und Generatormatrix dieses Codes sind wie folgt gegeben:
$${ \boldsymbol{\rm H}}_1 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},$$
$${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$

Im weiteren Verlauf der Aufgabe wird dieser (gelb hinterlegte) Code $C_{1}$ genannt.

  • Die rechte Spalte in obiger Tabelle gibt einen Blockcode mit den Parametern $n = 8$ und $k = 4$ an, der in der Literatur meist als „erweiteter Hamming–Code” bezeichnet wird. Wir nennen diesen (grün hinterlegten) Code im Folgenden $C_{2}$ und bezeichnen dessen Prüfmatrix mit ${ \boldsymbol{\rm H}}_{2}$ und die dazugehörige Generatormatrix mit ${ \boldsymbol{\rm G}}_{2}$ .

Die Fragen zu dieser Aufgabe beziehen sich auf


Hinweis :

Die Aufgabe gehört zu Kapitel Allgemeine Beschreibung linearer Blockcodes. Beachten Sie bei der Lösung, dass $C_{1}$ und $C_{2}$ jeweils systematische Codes sind. Die nachfolgende Aufgabe 1.09Z behandelt die Erweiterung von Codes in etwas allgemeinerer Form.

Fragebogen

1

Geben Sie die Coderaten von $C_{1}$ und $C_{2}$ an.

$\C_{1}: \ \ \ R$ =

$\C_{2}: \ \ \ R$ =

2

Geben Sie die minimalen Distanzen von $C_{1}$ und $C_{2}$ an.

$\C_{1}: \ \ \ d_{\rm min}$ =

$\C_{2}: \ \ \ d_{\rm min}$ =

3

Welches Format besitzt die Prüfmatrix von $C_{2}$?

$\ { \boldsymbol{\rm H}}_{2}{\rm :} \ \ \ {\rm Spaltenzahl}$ =

$\ { \boldsymbol{\rm H}}_{2}{\rm :} \ \ \ {\rm Zeilenzahl}$ =

4

Leiten Sie aus der Codetabelle die Gleichung für das Codebit $x_ {8} (= p_{4})$ ab.

$x_{8} = 0.$
$x_{8} = x_{1}⊕x_{2}⊕x_{4}⊕x_{5}.$
$x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$

5

Welche Aussagen gelten für ${ \boldsymbol{\rm H}}_{2}$? Hinweis: Richtig sind 3 von 4 Antworten.

Die erste Zeile lautet: $1 1 0 1 1 0 0 0$.
Die zweite Zeile lautet: $0 1 1 1 0 1 0 0$.
Die dritte Zeile lautet: $0 0 0 0 1 1 1 1$.
Die letzte Zeile lautet: $1 1 1 1 1 1 1 1$.

6

Welche Umformung ist für die letzte Zeile von ${ \boldsymbol{\rm H}}_{2}$ zulässig?

$1 1 1 1 1 1 1 1 → 0 0 0 0 0 0 0 0,$
$1 1 1 1 1 1 1 1 → 1 1 1 0 0 0 0 1,$
$1 1 1 1 1 1 1 1 → 0 0 1 0 1 0 0 0.$

7

Geben Sie die zugehörige Generatormatrix ${ \boldsymbol{\rm G}}_{2}$ an. Welche Aussagen treffen zu?

${ \boldsymbol{\rm G}}_{2}$ hat gleiches Format wie die Matrix ${ \boldsymbol{\rm G}}_{1}$ des (7, 4)–Codes.
${ \boldsymbol{\rm G}}_{2}$ beginnt wie ${ \boldsymbol{\rm G}}_{1}$ mit einer Diagonalmatrix ${ \boldsymbol{\rm I}}_{4}$ .
${ \boldsymbol{\rm G}}_{2}$ hat im betrachteten Beispiel das gleiche Format wie ${ \boldsymbol{\rm H}}_{2}$ .


Musterlösung

1. 2. 3. 4. 5. 6. 7.