Information Theory and Coding - Exam

Aufgabe 1)

Stelle Dir eine Quelle vor, die Nachrichten aus einem Alphabet von vier verschiedenen Zeichen \{A, B, C, D\} erzeugt. Die Wahrscheinlichkeiten der Zeichen sind: \(p(A) = 0.1, p(B) = 0.2, p(C) = 0.4, p(D) = 0.3\)\. Basierend auf diesen Informationen, beantworte die folgenden Fragen:

a)

Berechne die Entropie der Quelle mit der Shannon-Entropie-Formel. Verwende dazu die Wahrscheinlichkeiten der einzelnen Zeichen und zeige jeden Schritt der Berechnung.

Lösung:

Um die Entropie der Quelle mit der Shannon-Entropie-Formel zu berechnen, folge bitte den folgenden Schritten:

• Schritt 1: Notiere die Wahrscheinlichkeiten für die Zeichen aus dem Alphabet:

  • (1) p(A) = 0.1 (2) p(B) = 0.2 (3) p(C) = 0.4 (4) p(D) = 0.3

• Schritt 2: Verwende die Shannon-Entropie-Formel, die wie folgt lautet: \[H(X) = - \bigg( \text{p(A)} \times \text{log}_2(\text{p(A)}) + \text{p(B)} \times \text{log}_2(\text{p(B)}) + \text{p(C)} \times \text{log}_2(\text{p(C)}) + \text{p(D)} \times \text{log}_2(\text{p(D)}) \bigg)\]
• Schritt 3: Setze die Wahrscheinlichkeiten in die Shannon-Entropie-Formel ein und berechne die einzelnen Terme:
  • \[ \text{p(A)} \times \text{log}_2(\text{p(A)}) = 0.1 \times \text{log}_2(0.1) \]
  • \[\text{p(B)} \times \text{log}_2(\text{p(B)}) = 0.2 \times \text{log}_2(0.2) \]
  • \[\text{p(C)} \times \text{log}_2(\text{p(C)}) = 0.4 \times \text{log}_2(0.4) \]
  • \[ \text{p(D)} \times \text{log}_2(\text{p(D)}) = 0.3 \times \text{log}_2(0.3) \]
• Schritt 4: Berechne die Werte der einzelnen Terme:
  • \[0.1 \times \text{log}_2(0.1) = 0.1 \times (-3.32193) = -0.332193 \]
  • \[0.2 \times \text{log}_2(0.2) = 0.2 \times (-2.32193) = -0.464386\]
  • \[ 0.4 \times \text{log}_2(0.4) = 0.4 \times (-1.32193) = -0.528772\]
  • \[0.3 \times \text{log}_2(0.3) = 0.3 \times (-1.73697) = -0.521091\]
• Schritt 5: Summiere die berechneten Werte auf, um die Entropie zu erhalten:\[H(X) = - \bigg( -0.332193 + (-0.464386) + (-0.528772) + (-0.521091) \bigg) \]
• \[H(X) = -(-1.846442) \]
• \[H(X) = 1.846442\]
• Berechnete Entropie: Die Entropie der Quelle beträgt 1.846442 bits.

Damit hast Du die Entropie der Quelle erfolgreich berechnet!

b)

Bestimme die maximale Entropie, die diese Quelle haben könnte, falls die Wahrscheinlichkeiten aller Zeichen gleich verteilt wären. Zeige ebenfalls den Berechnungsweg.

Lösung:

Um die maximale Entropie zu bestimmen, wenn die Wahrscheinlichkeiten aller Zeichen gleich verteilt wären, kannst Du die folgenden Schritte befolgen:

• Schritt 1: Wenn alle Zeichen gleich verteilt sind, sind die Wahrscheinlichkeiten für jedes Zeichen gleich.
  • \[p(A) = p(B) = p(C) = p(D)\] Da es vier Zeichen gibt, ist die Wahrscheinlichkeit für jedes Zeichen \[\frac{1}{4}\]. Das bedeutet:\[p(A) = p(B) = p(C) = p(D) = 0.25\]
• Schritt 2: Verwende die Shannon-Entropie-Formel, um die maximale Entropie zu berechnen:
  • \[H(X) = - \sum_{i=1}^{n} p(x_i) \cdot \log_2(p(x_i))\]
  Da es vier Zeichen gibt \[n=4\] und \[p(x_i) = 0.25\] für alle Zeichen, sieht die Entropie-Formel wie folgt aus:
  • \[H(X) = - (p(A) \cdot \log_2(p(A)) + p(B) \cdot \log_2(p(B)) + p(C) \cdot \log_2(p(C)) + p(D) \cdot \log_2(p(D)))\]
  • \[H(X) = - (4 \cdot (0.25 \cdot \log_2(0.25)))\]
  • \[H(X) = - (4 \cdot (0.25 \cdot -2))\]
  • \[H(X) = - (4 \cdot -0.5)\]
  • \[H(X) = - (-2)\]
  • \[H(X) = 2\]
• Berechnete maximale Entropie: Die maximale Entropie, wenn die Wahrscheinlichkeiten aller Zeichen gleich verteilt sind, beträgt 2 bits.

Damit hast Du die maximale Entropie der Quelle erfolgreich berechnet!

c)

Vergleiche die berechnete Entropie der Quelle aus dem ersten Teil mit der maximalen Entropie aus dem zweiten Teil. Was sagt dir dieser Vergleich über die Struktur oder den Zufallsgrad der Nachrichtenquelle?

Lösung:

Um die berechnete Entropie der Quelle aus dem ersten Teil mit der maximalen Entropie aus dem zweiten Teil zu vergleichen, schauen wir uns die Werte an:

• Berechnete Entropie der Quelle: Im ersten Teil haben wir berechnet, dass die Entropie der Quelle 1.846442 bits beträgt.
• Maximale Entropie der Quelle: Im zweiten Teil haben wir festgestellt, dass die maximale Entropie der Quelle 2 bits beträgt, wenn die Wahrscheinlichkeiten aller Zeichen gleich verteilt sind.

Lassen wir uns nun diese beiden Werte miteinander vergleichen:

• Die berechnete Entropie (1.846442 bits) ist sehr nahe an der maximalen Entropie (2 bits), jedoch etwas niedriger.

Was sagt uns dieser Vergleich über die Struktur oder den Zufallsgrad der Nachrichtenquelle?

• Hohe Entropie bedeutet mehr Zufall: Da die berechnete Entropie nahe an der maximalen Entropie liegt, deutet dies darauf hin, dass die Quelle eine relativ hohe Unvorhersehbarkeit oder Zufälligkeit in der Nachrichtenproduktion aufweist.
• Eine perfekte Gleichverteilung führt zur maximalen Entropie: Die maximale Entropie wird erreicht, wenn alle Zeichen gleich wahrscheinlich sind. In unserer Quelle sind die Wahrscheinlichkeiten jedoch leicht unterschiedlich (0.1, 0.2, 0.4, 0.3), was zu einer minimal geringeren Entropie führt.
• Ungleichverteilung der Wahrscheinlichkeiten: Die leicht ungleichen Wahrscheinlichkeiten der Zeichen führen dazu, dass die Quelle etwas geordnet oder strukturiert ist, verglichen mit einer Quelle, bei der alle Zeichen gleichwahrscheinlich sind.

Zusammenfassend lässt sich sagen, dass die Quelle eine relativ hohe, aber nicht maximale, Zufälligkeit aufweist. Dies bedeutet, dass es eine gewisse Struktur oder Regelmäßigkeit in der Nachrichtenproduktion gibt, wenn auch nur geringfügig.

d)

Angenommen, die Quelle würde nun ein fünftes Zeichen \(E\) mit einer Wahrscheinlichkeit von 0.2 hinzufügen und die Wahrscheinlichkeiten der Originalzeichen proportional anpassen. Berechne die neue Entropie der Quelle und vergleiche sie mit der bisherigen Entropie. Welchen Effekt hat das Hinzufügen eines weiteren Zeichens auf die Entropie und warum?

Lösung:

Um die neue Entropie der Quelle zu berechnen, wenn ein fünftes Zeichen hinzugefügt wird und die Wahrscheinlichkeiten der Originalzeichen proportional angepasst werden, folge diesen Schritten:

• Schritt 1: Notiere die Wahrscheinlichkeit des neuen Zeichens E.\[p(E) = 0.2\]
• Schritt 2: Berechne die neuen Wahrscheinlichkeiten der Originalzeichen. Da die Gesamtsumme der Wahrscheinlichkeiten 1 betragen muss, wird die Summe der Wahrscheinlichkeiten der Originalzeichen nun \[1 - p(E) = 1 - 0.2 = 0.8\].Die Wahrscheinlichkeiten müssen proportional angepasst werden, das bedeutet:\[p(A)_{neu} = 0.1 \times 0.8\]\[p(B)_{neu} = 0.2 \times 0.8\]\[p(C)_{neu} = 0.4 \times 0.8\]\[p(D)_{neu} = 0.3 \times 0.8\]
• Schritt 3: Berechne die neuen Wahrscheinlichkeiten:\[p(A)_{neu} = 0.1 \times 0.8 = 0.08\]\[p(B)_{neu} = 0.2 \times 0.8 = 0.16\]\[p(C)_{neu} = 0.4 \times 0.8 = 0.32\]\[p(D)_{neu} = 0.3 \times 0.8 = 0.24\]Somit sind die neuen Wahrscheinlichkeiten:\[p(A)_{neu} = 0.08\]\[p(B)_{neu} = 0.16\]\[p(C)_{neu} = 0.32\]\[p(D)_{neu} = 0.24\]\[p(E) = 0.2\]
• Schritt 4: Verwende die Shannon-Entropie-Formel, um die neue Entropie zu berechnen:\[H(X) = - \sum_{i=1}^{5} p(x_i) \cdot \log_2(p(x_i))\]
• Schritt 5: Berechne jeden einzelnen Term:\[\begin{align*} p(A)_{neu} \cdot \log_2(p(A)_{neu}) & = 0.08 \cdot \log_2(0.08) = 0.08 \cdot (-3.643856) = -0.291508 \ \ p(B)_{neu} \cdot \log_2(p(B)_{neu}) & = 0.16 \cdot \log_2(0.16) = 0.16 \cdot (-2.643856) = -0.423017 \ \ p(C)_{neu} \cdot \log_2(p(C)_{neu}) & = 0.32 \cdot \log_2(0.32) = 0.32 \cdot (-1.643856) = -0.526433 \ \ p(D)_{neu} \cdot \log_2(p(D)_{neu}) & = 0.24 \cdot \log_2(0.24) = 0.24 \cdot (-2.059906) = -0.494377 \ \ p(E) \cdot \log_2(p(E)) & = 0.2 \cdot \log_2(0.2) = 0.2 \cdot (-2.321928) = -0.464386 \ \ \,\end{align*}\]
• Schritt 6: Summiere die berechneten Werte auf, um die neue Entropie zu erhalten:\[H(X_{neu}) = -(-0.291508 + (-0.423017) + (-0.526433) + (-0.494377) + (-0.464386))\]
\[H(X_{neu}) = -(-2.199721)\]\[H(X_{neu}) = 2.199721\]

Vergleich und Interpretation:

• Neue Entropie: Die neue Entropie der Quelle beträgt 2.199721 bits.
• Bisherige Entropie: Die bisherige Entropie der Quelle betrug 1.846442 bits.
• Effekt des Hinzufügens eines weiteren Zeichens: Das Hinzufügen eines weiteren Zeichens hat die Entropie der Quelle erhöht.

Warum hat das Hinzufügen eines weiteren Zeichens die Entropie erhöht? Der Grund dafür ist, dass die Entropie ein Maß für die Unvorhersehbarkeit oder den Informationsgehalt der Quelle ist. Wenn ein zusätzliches Zeichen hinzugefügt wird, insbesondere wenn es eine signifikante Wahrscheinlichkeit hat (in diesem Fall 0.2), erhöht sich die Unvorhersehbarkeit der Quelle. Dies führt dazu, dass die Entropie steigt, da es mehr mögliche Varianten für die erzeugten Nachrichten gibt.

Aufgabe 2)

Das Shannon'sche Kommunikationsmodell bietet eine Grundlage zur Analyse und Beschreibung von Kommunikationsprozessen. Es umfasst die Elemente Informationsquelle, Sender, Kanal, Empfänger und Informationsziel und wird mathematisch durch die Formel zur Kanalkapazität beschrieben:

• Informationsquelle: Ursprung der Nachricht
• Sender: wandelt Nachricht in Signal um
• Kanal: Übertragungspfad, kann Störungen enthalten
• Empfänger: wandelt das empfangene Signal zurück in die Nachricht
• Informationsziel: Enddestination der Nachricht
• Mathematische Beschreibung: \( C = B \cdot \log_2(1 + \frac{S}{N}) \) wobei C die Kanalkapazität, B die Bandbreite und \( \frac{S}{N} \) das Signal-Rausch-Verhältnis ist

.

a)

Erkläre das Shannon'sche Kommunikationsmodell, indem Du die verschiedenen Bestandteile des Modells benennst und deren jeweilige Rolle innerhalb des Kommunikationsprozesses beschreibst. Verwende dazu die Informationen aus dem gegebenen Kontext.

Lösung:

Erklärung des Shannon'schen KommunikationsmodellsDas Shannon'sche Kommunikationsmodell ist eine fundamentale Methode zur Analyse und Beschreibung von Kommunikationsprozessen. Es besteht aus mehreren wesentlichen Komponenten, von denen jede eine spezifische Rolle im Kommunikationsprozess einnimmt. Hier sind die einzelnen Bestandteile des Modells und deren jeweilige Funktion:

• Informationsquelle: Die Informationsquelle ist der Ursprung der Nachricht. Hier erarbeitet sich die zu übermittelnde Information. Ein Beispiel für eine Informationsquelle wäre ein Mensch, der eine Nachricht verfasst oder ein Sensor, der Messdaten generiert.
• Sender: Der Sender hat die Aufgabe, die Nachricht in ein Signal umzuwandeln. Dieser Vorgang wird als Kodierung bezeichnet. Zum Beispiel kann ein Radio-Sender audioelektrische Signale in elektromagnetische Wellen umwandeln.
• Kanal: Der Kanal stellt den Übertragungspfad dar, durch den das Signal gesendet wird. Der Kanal kann verschiedene Formen annehmen, wie z.B. eine Telefonleitung, Luft (für Funkkommunikation) oder ein Glasfaserkabel. Störungen oder Rauschen können die Qualität der Übertragung beeinflussen.
• Empfänger: Der Empfänger wandelt das empfangene Signal zurück in die ursprüngliche Nachricht um. Dieser Vorgang wird als Dekodierung bezeichnet. Ein Beispiel wäre ein Radioempfänger, der die empfangenen elektromagnetischen Wellen zurück in hörbare Töne umwandelt.
• Informationsziel: Das Informationsziel ist die Enddestination der Nachricht. Dies kann ein Mensch, ein Computer oder ein anderes Gerät sein, das die Information nutzt oder weiterverarbeitet.

Zusätzlich zur strukturellen Beschreibung des Kommunikationsprozesses bietet das Modell auch eine mathematische Beschreibung der Kapazität des Kanals:

• Mathematische Beschreibung: Die Kanalkapazität (C) gibt die maximale Datenmenge an, die über einen Kanal unter gegebenen Bedingungen übertragen werden kann. Die Formel hierfür lautet:
  • C = B \, \log_2(1 + \frac{S}{N})
  Dabei stehen folgende Variablen:
  • C für die Kanalkapazität in Bits pro Sekunde (bps),
  • B für die Bandbreite des Kanals in Hertz (Hz), und
  • \frac{S}{N} für das Signal-Rausch-Verhältnis, welches das Verhältnis von Signalstärke zu Rauschstärke beschreibt.

b)

Berechne die Kanalkapazität C in Bit/s für einen Telekommunikationskanal mit einer Bandbreite von 3 MHz und einem Signal-Rausch-Verhältnis von 15 dB. Gehe dabei von den dargestellten Gleichungen aus und zeige alle Zwischenschritte auf. Beachte, dass das Signal-Rausch-Verhältnis in dB in ein gewöhnliches Verhältnis umgerechnet werden muss. Nutze dazu die Formel: \( SNR_{linear} = 10^{\frac{SNR_{dB}}{10}} \).

Lösung:

Berechnung der Kanalkapazität CGegeben:

• Bandbreite: \( B = 3 \, \text{MHz} = 3.000.000 \, \text{Hz} \)
• Signal-Rausch-Verhältnis: \( SNR = 15 \, \text{dB} \)

Schritte zur Berechnung der Kanalkapazität C:

1. Umrechnung des Signal-Rausch-Verhältnisses von dB in ein gewöhnliches Verhältnis:Verwende die Formel:\[ SNR_{linear} = 10^{\frac{SNR_{dB}}{10}} \]Setze den gegebenen Wert ein:\[ SNR_{linear} = 10^{\frac{15}{10}} \]Berechne den Exponenten:\[ SNR_{linear} = 10^{1.5} \]Nutze einen Taschenrechner, um den Wert zu erhalten:\[ SNR_{linear} \approx 31.62 \]
2. Berechnung der Kanalkapazität C mit der Shannon-Formel:Die Shannon-Formel lautet:\[ C = B \cdot \log_2(1 + \frac{S}{N}) \]Setze die bekannten Werte ein:\[ C = 3.000.000 \cdot \log_2(1 + 31.62) \]Berechne den Ausdruck in der Klammer:\[ 1 + 31.62 = 32.62 \]Berechne den logarithmischen Ausdruck (\( \, \log_2(32.62) \)):\[ \log_2(32.62) = \frac{\log_{10}(32.62)}{\log_{10}(2)} \]Nutze einen Taschenrechner, um die Logarithmen zu berechnen:\[ \log_{10}(32.62) \approx 1.5132 \]\[ \log_{10}(2) \approx 0.3010 \]Setze die Werte ein:\[ \log_2(32.62) \approx \frac{1.5132}{0.3010} \approx 5.027 \]
3. Finale Berechnung der Kanalkapazität:Setze \( \log_2(32.62) \) in die Gleichung ein:\[ C = 3.000.000 \cdot 5.027 \approx 15.081.000 \, \text{Bit/s} \]

Somit beträgt die Kanalkapazität \( C \) etwa 15.081.000 Bit/s (oder 15.081 Mbit/s).

c)

Diskutiere, wie sich Störungen im Kanal auf die Kanalkapazität auswirken können. Berücksichtige in deiner Beantwortung die mathematischen Zusammenhänge, insbesondere die Abhängigkeit der Kanalkapazität (C) vom Signal-Rausch-Verhältnis (S/N). Veranschauliche deine Antwort mit einem Beispiel, indem Du die Kanalkapazität vor und nach einer Veränderung des Signal-Rausch-Verhältnisses berechnest.

Lösung:

Auswirkungen von Störungen im Kanal auf die KanalkapazitätStörungen im Kanal beeinflussen direkt das Signal-Rausch-Verhältnis (SNR). Ein niedrigeres SNR bedeutet, dass das Signal stärker von Rauschen überlagert wird, was die Kanalkapazität verringert. Die Beziehung zwischen der Kanalkapazität (C), der Bandbreite (B) und dem Signal-Rausch-Verhältnis (\( \frac{S}{N} \)) wird durch die Shannon-Formel beschrieben:

• \[ C = B \cdot \log_2(1 + \frac{S}{N}) \]

Durch diese Formel wird deutlich, dass die Kanalkapazität C proportional zum Logarithmus des Signal-Rausch-Verhältnisses plus Eins ist. Wenn das Signal-Rausch-Verhältnis sinkt, nimmt auch der Wert von \( \log_2(1 + \frac{S}{N}) \) ab, was die Kanalkapazität vermindert.Beispiel: Gegeben seien:

• Bandbreite: \( B = 3 \, \text{MHz} = 3.000.000 \, \text{Hz} \)
• Signal-Rausch-Verhältnis: \( SNR_1 = 20 \, \text{dB} \) und \( SNR_2 = 10 \, \text{dB} \) (nach einer Verschlechterung durch Störungen)

Berechne die Kanalkapazitäten vor und nach der Verschlechterung.

1. Signal-Rausch-Verhältnis in lineare Werte umrechnen:Vor der Veränderung:
   • \[ SNR_{linear_1} = 10^{\frac{SNR_1}{10}} = 10^{\frac{20}{10}} = 10^2 = 100 \]
   Nach der Veränderung:
   • \[ SNR_{linear_2} = 10^{\frac{SNR_2}{10}} = 10^{\frac{10}{10}} = 10^1 = 10 \]
2. Kanalkapazität mit der Shannon-Formel berechnen:Vor der Veränderung:
   • \[ C_1 = B \cdot \log_2(1 + \frac{S}{N_1}) \]
   • \[ C_1 = 3.000.000 \cdot \log_2(1 + 100) \]
   • \[ C_1 = 3.000.000 \cdot \log_2(101) \]
   • \[ \log_2(101) \approx 6.6582 \]
   • \[ C_1 \approx 3.000.000 \cdot 6.6582 \approx 19.974.600 \, \text{Bit/s} \]
   Nach der Veränderung:
   • \[ C_2 = B \cdot \log_2(1 + \frac{S}{N_2}) \]
   • \[ C_2 = 3.000.000 \cdot \log_2(1 + 10) \]
   • \[ C_2 = 3.000.000 \cdot \log_2(11) \]
   • \[ \log_2(11) \approx 3.4594 \]
   • \[ C_2 \approx 3.000.000 \cdot 3.4594 \approx 10.378.200 \, \text{Bit/s} \]

Die Kanalkapazität hat sich durch die Verschlechterung des Signal-Rausch-Verhältnisses erheblich reduziert:Vor der Veränderung lag die Kanalkapazität bei etwa 19.974.600 Bit/s, während sie nach der Veränderung auf etwa 10.378.200 Bit/s gesunken ist. Dies zeigt, dass Störungen im Kanal, die das Signal-Rausch-Verhältnis verschlechtern, einen signifikanten Einfluss auf die Datenübertragungsrate haben. Ein niedrigeres Signal-Rausch-Verhältnis reduziert die Fähigkeit des Kanals, Daten effizient zu übertragen.

Aufgabe 3)

Betrachte einen linearen Block-Code, der zur Fehlerkorrektur genutzt wird. Der Code hat die Codewortlänge n = 7 und die Informationswortlänge k = 4. Gegeben ist die folgende Generator-Matrix G und Kontrollmatrix H:

G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

H = \begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}

Bestimme die Lösungen folgender Aufgaben basierend auf den gegebenen Informationen.

a)

Ermittle die Codewörter des Codes, indem Du die Generator-Matrix G auf den Informationsvektor u = [1, 0, 1, 1] anwendest.

Lösung:

• Problemstellung: Basierend auf einem linearen Block-Code mit der Codewortlänge n = 7 und der Informationswortlänge k = 4 sollst Du die Codewörter ermitteln, indem Du die Generator-Matrix G auf den Informationsvektor u = [1, 0, 1, 1] anwendest.
• Gegebene Matrizen:

  G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

  H = \begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}

• Schritt-für-Schritt-Lösung:
  1. Erinnere Dich daran, dass das Codewort c durch Multiplikation des Informationsvektors u mit der Generator-Matrix G ermittelt wird. Mathematisch formuliert: c = u * G.
  2. Gegeben der Informationsvektor u = [1, 0, 1, 1], multipliziere diesen mit der Generator-Matrix G:

  u = [1, 0, 1, 1]G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

              c = [1, 0, 1, 1] * \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} = [1, 0, 1, 1] * \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}        

  • Berechnung des ersten Elements des Codewortes:

  c_1 = 1*1 + 0*0 + 1*0 + 1*0 = 1 

• Berechnung des zweiten Elements des Codewortes:

c_2 = 1*0 + 0*1 + 1*0 + 1*0 = 0

Berechnung des dritten Elements des Codewortes:

c_3 = 1*0 + 0*0 + 1*1 + 1*0 = 1

Berechnung des vierten Elements des Codewortes:

c_4 = 1*0 + 0*0 + 1*0 + 1*1 = 1

Berechnung des fünften Elements des Codewortes:

c_5 = 1*1 + 0*0 + 1*1 + 1*1 = 3 mod 2 = 1 (in der Binärarithmetik)

Berechnung des sechsten Elements des Codewortes:

c_6 = 1*1 + 0*1 + 1*0 + 1*1 = 2 mod 2 = 0 (in der Binärarithmetik)

Berechnung des siebten Elements des Codewortes:

c_7 = 1*0 + 0*1 + 1*1 + 1*1 = 2 mod 2 = 0 (in der Binärarithmetik)

Daher ist das resultierende Codewort:

c = [1, 0, 1, 1, 1, 0, 0]

b)

Bestimme den minimalen Hamming-Abstand \(d_{\text{min}}\) dieses Codes. Zeige alle Schritte Deiner Berechnung.

Lösung:

• Problemstellung: Bestimme den minimalen Hamming-Abstand (d_min) des gegebenen linearen Block-Codes mit der Generator-Matrix G und Kontrollmatrix H.
• Gegebene Matrizen:

  G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

  H = \begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}

• Schritt-für-Schritt-Lösung:
  1. Erinnere Dich daran, dass der minimale Hamming-Abstand d_min eines linearen Codes die minimale Anzahl der Stellen ist, in denen sich zwei unterschiedliche Codewörter unterscheiden.
  2. Für einen linearen Code ist d_min auch das Minimum der Anzahl der Einsen in einem beliebigen nicht-trivialen Codewort (d.h., das Gewicht des Codewortes).
  3. Das bedeutet, wir müssen alle möglichen Codewörter berechnen.
  4. Berechne die Codewörter für jeden möglichen Informationsvektor u, indem Du c = u \times G berechnest:
  • u = [0, 0, 0, 0] \rightarrow c = [0, 0, 0, 0, 0, 0, 0]
  • u = [0, 0, 0, 1] \rightarrow c = [0, 0, 0, 1, 1, 1, 1]
  • u = [0, 0, 1, 0] \rightarrow c = [0, 0, 1, 0, 1, 0, 1]
  • u = [0, 0, 1, 1] \rightarrow c = [0, 0, 1, 1, 0, 1, 0]
  • u = [0, 1, 0, 0] \rightarrow c = [0, 1, 0, 0, 0, 1, 1]
  • u = [0, 1, 0, 1] \rightarrow c = [0, 1, 0, 1, 1, 0, 1]
  • u = [0, 1, 1, 0] \rightarrow c = [0, 1, 1, 0, 1, 1, 0]
  • u = [0, 1, 1, 1] \rightarrow c = [0, 1, 1, 1, 0, 0, 0]
  • u = [1, 0, 0, 0] \rightarrow c = [1, 0, 0, 0, 1, 1, 0]
  • u = [1, 0, 0, 1] \rightarrow c = [1, 0, 0, 1, 0, 0, 1]
  • u = [1, 0, 1, 0] \rightarrow c = [1, 0, 1, 0, 0, 1, 1]
  • u = [1, 0, 1, 1] \rightarrow c = [1, 0, 1, 1, 1, 0, 0]
  • u = [1, 1, 0, 0] \rightarrow c = [1, 1, 0, 0, 0, 0, 0]
  • u = [1, 1, 0, 1] \rightarrow c = [1, 1, 0, 1, 1, 1, 1]
  • u = [1, 1, 1, 0] \rightarrow c = [1, 1, 1, 0, 1, 0, 1]
  • u = [1, 1, 1, 1] \rightarrow c = [1, 1, 1, 1, 0, 1, 0]
• Berechne das Gewicht (d.h. die Anzahl der Einsen) jedes Codeworts, um den minimalen Hamming-Abstand zu ermitteln.
• [0, 0, 0, 0, 0, 0, 0] hat Gewicht 0 (das triviale Codewort wird nicht berücksichtigt)
• [0, 0, 0, 1, 1, 1, 1] hat Gewicht 4
• [0, 0, 1, 0, 1, 0, 1] hat Gewicht 3
• [0, 0, 1, 1, 0, 1, 0] hat Gewicht 3
• [0, 1, 0, 0, 0, 1, 1] hat Gewicht 3
• [0, 1, 0, 1, 1, 0, 1] hat Gewicht 4
• [0, 1, 1, 0, 1, 1, 0] hat Gewicht 4
• [0, 1, 1, 1, 0, 0, 0] hat Gewicht 3
• [1, 0, 0, 0, 1, 1, 0] hat Gewicht 3
• [1, 0, 0, 1, 0, 0, 1] hat Gewicht 3
• [1, 0, 1, 0, 0, 1, 1] hat Gewicht 4
• [1, 0, 1, 1, 1, 0, 0] hat Gewicht 4
• [1, 1, 0, 0, 0, 0, 0] hat Gewicht 2
• [1, 1, 0, 1, 1, 1, 1] hat Gewicht 5
• [1, 1, 1, 0, 1, 0, 1] hat Gewicht 5
• [1, 1, 1, 1, 0, 1, 0] hat Gewicht 5
• Daher ist der minimale Hamming-Abstand d_min 2, da [1, 1, 0, 0, 0, 0, 0] das nicht-triviale Codewort mit dem geringsten Gewicht ist.
• Fazit: Der minimale Hamming-Abstand d_min dieses Codes ist 2.

c)

Gegeben ist das empfangene Wort r = [1, 0, 1, 1, 1, 0, 1]. Prüfe, ob dieses empfangene Wort ein gültiges Codewort ist. Falls nicht, bestimme das Fehlervektor e und korrigiere das empfangene Wort. Nutze die Kontrollmatrix H zur Fehlererkennung und -korrektur.

Lösung:

• Problemstellung: Gegeben ist das empfangene Wort r = [1, 0, 1, 1, 1, 0, 1]. Prüfe, ob dieses empfangene Wort ein gültiges Codewort ist, und falls nicht, bestimme den Fehlervektor e und korrigiere das empfangene Wort. Nutze die Kontrollmatrix H zur Fehlererkennung und -korrektur.
• Gegebene Matrizen:

  G = \begin{bmatrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \ 0 & 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

  H = \begin{bmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \ 0 & 1 & 1 & 0 & 1 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}

• Schritt-für-Schritt-Lösung:
  1. Um zu überprüfen, ob das empfangene Wort r ein gültiges Codewort ist, berechnen wir das Syndrom s des empfangenen Wortes r durch Multiplikation mit der Kontrollmatrix H.
  2. Das Syndrom s erhält man durch:

     s = r \times H^T

  3. Das transponierte H (H^T) ist:

     H^T = \begin{bmatrix}1 & 0 & 1 \ 1 & 1 & 0 \ 0 & 1 & 0 \ 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ 0 & 0 & 1 \end{bmatrix}

  4. Berechne das Syndrom s:

     r = [1, 0, 1, 1, 1, 0, 1] \ s = r \times H^T \ s = [1, 0, 1, 1, 1, 0, 1] \times \begin{bmatrix}1 & 0 & 1 \ 1 & 1 & 0 \ 0 & 1 & 0 \ 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ 0 & 0 & 1 \end{bmatrix}

  • s_1 = (1 \times 1) + (0 \times 1) + (1 \times 0) + (1 \times 1) + (1 \times 0) + (0 \times 0) + (1 \times 0) = 2 \mod 2 = 0

  • s_2 = (1 \times 0) + (0 \times 1) + (1 \times 1) + (1 \times 0) + (1 \times 1) + (0 \times 0) + (1 \times 0) = 2 \mod 2 = 0

  • s_3 = (1 \times 1) + (0 \times 0) + (1 \times 0) + (1 \times 0) + (1 \times 0) + (0 \times 1) + (1 \times 1) = 2 \mod 2 = 0

  s = [0, 0, 0]

• Da das Syndrom s der Nullvektor ist (s = [0,0,0]), handelt es sich um ein gültiges Codewort.
• Fazit: Das empfangene Wort r = [1, 0, 1, 1, 1, 0, 1] ist ein gültiges Codewort.

Aufgabe 4)

In einer Kommunikationssituation sind folgende Kanäle gegeben:

• AWGN-Kanal: Additive White Gaussian Noise, Rauschen mit konstanter Leistungsdichte.
• SNR (Signal-to-Noise Ratio): Verhältnis von Signalleistung zu Rauschleistung.
• BSC (Binary Symmetric Channel): Bitübertragungskanal mit fester Fehlerwahrscheinlichkeit.
• Übergangswahrscheinlichkeit: Wahrscheinlichkeit, dass ein Bit falsch übertragen wird, bezeichnet als \(p\).
• Erweiterte Modelle: Realistischere Abbildungen von Übertragungskanälen, z. B. Markov-Modelle.
• Kanalmodelle mit Gedächtnis: Abhängigkeit gegenwärtiger Zustände von vorherigen Zuständen.
• Mehrwegeausbreitung, Fading: Realistische Störungen in drahtlosen Kommunikationskanälen.

a)

(a) Berechne die Kapazität eines AWGN-Kanals, gegeben seien eine Bandbreite von 1 MHz und ein Signal-zu-Rausch-Verhältnis (SNR) von 20 dB. Verwende die Formel:

\[C = B \log_2(1 + \text{SNR})\]

wobei \(C\) die Kapazität, \(B\) die Bandbreite und \(\text{SNR}\) das Signal-zu-Rausch-Verhältnis ist. Der logarithmische Ausdruck sollte entsprechend der dB-Skala umgerechnet werden.

Lösung:

(a) Um die Kapazität eines AWGN-Kanals zu berechnen, verwenden wir die folgende Formel:

\[ C = B \log_2(1 + \text{SNR}) \]

Die gegebenen Werte sind:

• Bandbreite (\( B \)) : 1 MHz = 1 × 10⁶ Hz
• SNR: 20 dB

Da die SNR in dB gegeben ist, müssen wir sie in den linearen Maßstab umrechnen. Das Verhältnis SNR (in dB) kann mit folgender Formel in den linearen Maßstab umgerechnet werden:

\[ \text{SNR}_{\text{linear}} = 10^{\frac{\text{SNR}_{\text{dB}}}{10}} \]

Für SNR = 20 dB ergibt sich:

\[ \text{SNR}_{\text{linear}} = 10^{\frac{20}{10}} = 10^2 = 100 \]

Nun können wir die Kapazität (\( C \)) berechnen:

\[ C = 1 \times 10^6 \log_2(1 + 100) = 1 \times 10^6 \log_2(101) \]

Der logarithmische Ausdruck auf Basis 2 kann umgeschrieben werden mittels:

\[ \log_2(x) = \frac{\log_{10}(x)}{\log_{10}(2)} \]

Alternativ können wir den Wert von \( \log_2(101) \) direkt mit einem Taschenrechner berechnen:

\[ \log_2(101) ≈ 6.6582 \]

Somit ergibt sich die Kapazität wie folgt:

\[ C = 1 \times 10^6 \times 6.6582 ≈ 6.6582 \times 10^6 \text{ bits/second} \]

Daher beträgt die Kapazität des AWGN-Kanals bei den gegebenen Parametern etwa 6.6582 Mbit/s.

b)

(b) Bestimme die Übergangswahrscheinlichkeit \(p\) in einem Binary Symmetric Channel (BSC), in dem die Kanalkapazität \(C\) 0.8 bits pro Sekunde beträgt. Nutze hierzu die Formel der Kanalkapazität eines BSC:

\[C = 1 - H(p)\]

und der Binären Entropiefunktion:

\[H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)\]

Lösung:

(b) Um die Übergangswahrscheinlichkeit \( p \) in einem Binary Symmetric Channel (BSC) zu bestimmen, verwenden wir die gegebene Kanalkapazitätsformel:

\[ C = 1 - H(p) \]

und die Binäre Entropiefunktion:

\[ H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p) \]

Gegeben, dass die Kanalkapazität \( C \) 0.8 bits pro Sekunde beträgt:

\[ 0.8 = 1 - H(p) \]

Das Gleichgewicht wird umgestellt, um \( H(p) \) zu berechnen:

\[ H(p) = 1 - 0.8 \]

Also:

\[ H(p) = 0.2 \]

Jetzt setzen wir \( H(p) \) in die Entropiefunktion ein:

\[ 0.2 = -p \log_2(p) - (1 - p) \log_2(1 - p) \]

Diese Gleichung ist nicht trivial analytisch zu lösen, aber man kann sie numerisch lösen, z. B. durch den Einsatz eines Rechners oder numerischer Methoden wie dem Newton-Raphson-Verfahren. Alternativ können wir eine Näherungslösung finden, indem wir verschiedene Werte für \( p \) ausprobieren und diejenige wählen, die am besten passt.

Durch numerische Approximation finden wir, dass:

Wenn \( p ≈ 0.109 \), dann \( -0.109 \log_2(0.109) - (1 - 0.109) \log_2(1 - 0.109) \approx 0.2 \).

Daher ist die Übergangswahrscheinlichkeit \( p \) in einem BSC mit einer Kanalkapazität von 0.8 bits pro Sekunde ungefähr 0.109.

c)

(c) Beschreibe die wesentlichen Merkmale eines Markov-Modells zur Darstellung eines Kanals mit Gedächtnis. Diskutiere kurz, wie Übergangsmatrizen verwendet werden, um die Zustandsübergänge zu modellieren.

Lösung:

(c) Ein Markov-Modell wird verwendet, um Kanäle mit Gedächtnis zu modellieren, bei denen die aktuelle Übertragung nicht unabhängig von den vorherigen Übertragungen ist. Wesentliche Merkmale eines Markov-Modells zur Darstellung eines solchen Kanals sind:

• Zustände: Das Modell besteht aus verschiedenen Zuständen, die die verschiedenen Bedingungen oder Störungen des Kanals repräsentieren.
• Übergangswahrscheinlichkeiten: Jeder Zustand hat eine bestimmte Wahrscheinlichkeit, in einen anderen Zustand überzugehen. Diese Wahrscheinlichkeiten sind in einer Übergangsmatrix organisiert.
• Gedächtnis: Der kommende Zustand eines Kanals hängt nur vom aktuellen Zustand und nicht von weiter zurückliegenden Zuständen ab (Markov-Eigenschaft).

Eine Übergangsmatrix, auch bekannt als stochastische Matrix oder Übergangswahrscheinlichkeitsmatrix, wird verwendet, um die Wahrscheinlichkeiten der Zustandsübergänge zu modellieren. Die Matrix zeigt die Wahrscheinlichkeit an, von einem Zustand in einen anderen zu wechseln. Eine typische Übergangsmatrix \( P \) für ein System mit \( n \) Zuständen könnte wie folgt dargestellt werden:

\[ P = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1n} \ p_{21} & p_{22} & \cdots & p_{2n} \ \vdots & \vdots & \ddots & \vdots \ p_{n1} & p_{n2} & \cdots & p_{nn} \end{pmatrix} \]

• \( p_{ij} \) gibt die Wahrscheinlichkeit an, vom Zustand \( i \) in den Zustand \( j \) zu wechseln.

Ein Beispiel für einen Markov-Kanal könnte zwei Zustände haben: Ruhe und Störung (mit entsprechenden Übergangswahrscheinlichkeiten).

Angenommen, die Übergangsmatrix lautet:

\[ P = \begin{pmatrix} 0.9 & 0.1 \ 0.4 & 0.6 \end{pmatrix} \]

• Der Wert 0.9 gibt die Wahrscheinlichkeit an, dass der Kanal im nächsten Zeitintervall im Ruhezustand bleibt, wenn er im aktuellen Zeitintervall im Ruhezustand ist.
• Der Wert 0.1 gibt die Wahrscheinlichkeit an, dass der Kanal von Ruhe zu Störung übergeht.
• Der Wert 0.4 gibt die Wahrscheinlichkeit an, dass der Kanal von Störung zu Ruhe übergeht.
• Der Wert 0.6 gibt die Wahrscheinlichkeit an, dass der Kanal im Störzustand bleibt.

Durch die Analyse der Übergangsmatrix können Ingenieure und Wissenschaftler Vorhersagen über das Verhalten des Kanals treffen und Strategien zur Fehlerkorrektur und besseren Übertragung entwickeln.

d)

(d) Gegeben sei ein drahtloser Kommunikationskanal, der durch Fading und Mehrwegeausbreitung beeinflusst wird. Erläutere kurz, wie die Kapazität dieses Kanals bestimmt werden kann. Welche zusätzlichen Faktoren müssen bei der Berechnung berücksichtigt werden?

Lösung:

(d) Ein drahtloser Kommunikationskanal, der durch Fading und Mehrwegeausbreitung beeinflusst wird, ist komplexer zu modellieren als ein einfacher Additive White Gaussian Noise (AWGN) Kanal. Die Bestimmung der Kanalkapazität in solchen Kanälen erfordert eine Berücksichtigung mehrerer zusätzlicher Faktoren.

Hier sind einige grundlegende Schritte und Überlegungen zur Bestimmung der Kapazität eines drahtlosen Kanals mit Fading und Mehrwegeausbreitung:

• Modellwahl: Wähle ein adäquates Modell zur Beschreibung des Fadings (z.B. Rayleigh-Fading, Rician-Fading). Diese Modelle beschreiben die statistischen Eigenschaften der Signalabschwächung durch Fading.
• Signal-zu-Rausch-Verhältnis (SNR): Berechne das SNR unter Berücksichtigung von Fading. Das SNR ist nicht mehr konstant, sondern eine Zufallsvariable, die durch das Fading verändert wird.
• Erwartungswert der Kapazität: Da das SNR sich ändert, wird die Kapazität auch eine Zufallsvariable. Die erwartete Kanalkapazität kann durch die Integrationsrechnung über die Wahrscheinlichkeitsdichtefunktion (pdf) des SNR bestimmt werden. Eine typische Formel dafür ist:

\[C = \mathbb{E}[\log_2(1 + \text{SNR})]\]

• Hierbei ist \(\mathbb{E}[\cdot]\) der Erwartungswert.
• Kanalverzerrung und Interferenz: Berücksichtige zusätzliche Verzerrungen und Interferenzen, die durch Mehrwegeausbreitung entstehen können. Mehrwegeausbreitung führt zu Überlagerungen der Signalpfade, was sowohl destruktive als auch konstruktive Interferenzen verursachen kann.
• Diversitätsmethoden: Nutze Mechanismen wie Antennendiversität, Zeitdiversität oder Frequenzdiversität zur Minderung der negativen Effekte des Fadings. Diese Methoden können helfen, die effektive Kanalkapazität zu erhöhen.
• Kanalcodierung und Modulationsschema: Die Wahl der verwendeten Kanalcodierung (z.B. LDPC-Codes, Turbo-Codes) und das Modulationsschema (z.B. QAM, PSK) beeinflussen ebenfalls die effektive Kapazität des Kanals.

Zusätzlich zu den oben genannten Faktoren müssen reale Systeme auch weitere praktische Aspekte beachten, wie z.B.:

• Kanalvariation: In drahtlosen Kanälen ändert sich die Kanalantwort oft schnell, besonders in mobilen Anwendungen. Daher muss die Systemgestaltung adaptiv sein und sich dynamisch an veränderte Kanalbedingungen anpassen.
• Kanalschätzung: Eine genaue Schätzung der momentanen Kanalzustände ist essenziell für die Anpassung von Sende- und Empfangsparametern.
• Betriebsfrequenz und Bandbreite: Die verfügbaren Bandbreiten und die Betriebsfrequenzen beeinflussen direkt die Kapazität des Kanals.

Insgesamt bleibt die Bestimmung der Kapazität eines drahtlosen Kommunikationskanals mit Fading und Mehrwegeausbreitung eine komplexe Aufgabe, die sowohl theoretische Modelle als auch praktische Anpassungen erfordert.