Informationstheorie und Kanalcodierung: Übungsaufgaben mit Lösungen

Aufgabe 1: Unsicherheit bei Sportteam-Auswahl

In einem Institut wurden gleich viele Fußballmannschaften (11 Spieler) und Handballmannschaften (7 Spieler) gebildet.

1. Angenommen, es ist bekannt, dass in einem zufällig ausgewählten Team keine zwei Studenten am selben Wochentag geboren wurden. Wie viel Unsicherheit besteht bezüglich der Sportart, die das Team spielt? Nehmen Sie an, ein Jahr hat genau 52 Wochen.
2. Dito, wenn das Team weiß, dass es Studenten gibt, die am selben Wochentag geboren wurden.

Lösung zu Aufgabe 1

1. Keine. Wenn keine zwei Studenten am selben Wochentag geboren wurden, kann es sich nicht um ein Fußballteam handeln (da 11 Spieler > 7 Wochentage). Es muss sich also um ein Handballteam handeln. Die Unsicherheit bezüglich der Sportart ist daher null.
2. Sei E das Ereignis "Studenten, die am selben Wochentag geboren wurden" und X die Art der Mannschaft. Dann ist leicht zu berechnen, dass... [Die Lösung ist im Originaldokument unvollständig.]

Aufgabe 2: Effizienz von Quellencodierung

Nehmen wir an, das Alphabet einer diskreten gedächtnislosen Quelle besteht aus 27 Einträgen. Angenommen, die Wahrscheinlichkeitsverteilung der Quelle ist gleichmäßig, und die Quellsymbole werden nacheinander kodiert.

1. Bestimmen Sie die Effizienz eines kompakten binären Encoders.
2. Bestimmen Sie die Effizienz eines kompakten ternären Encoders.

Lösung zu Aufgabe 2

1. Eine kompakte binäre Kodierung einer gleichmäßigen Quelle erzeugt Codewörter, deren Längen sich höchstens um eine Einheit unterscheiden (siehe Probleme, 10. Newsletter 2). In diesem Fall sind es 5 Codewörter der Länge 4 und 22 Codewörter der Länge 5. Die durchschnittliche Codewortlänge L beträgt daher: L = (4 × 5 + 5 × 22) / 27 ≈ 4,81. Die Effizienz η = H₂(X) / L ≈ 98,7%. Beachten Sie, dass es nicht notwendig ist, den Huffman-Kodierungsbaum zu konstruieren.
2. Die Effizienz ist 1 (oder 100%), da die Wahrscheinlichkeiten der Quellsymbole ganzzahlige Potenzen von 3 sind (entsprechend der Anzahl der Elemente des Kodierungsalphabets).

Aufgabe 3: Quellengröße und Kanalkapazität

Wie groß ist das Alphabet einer gleichverteilten Quelle, wenn sie ihre Nachrichten zuverlässig über einen idealen Kanal mit einer Kapazität von 3 Bit pro Symbol übertragen soll, wobei die Symbolgenerierungsrate die Kanalübertragungsrate nicht überschreiten darf?

Lösung zu Aufgabe 3

Es muss gelten: log₂(n) ≤ 3. Daraus folgt: n ≤ 2³ = 8.

Aufgabe 4: Analyse eines Binärcodes

Sei C der binäre Code, der durch die Prüfmatrix H definiert ist:

[Die Prüfmatrix ist im Originaldokument nicht angegeben.]

1. Bestimmen Sie die Länge, Dimension und den Minimalabstand von C.
2. Geben Sie eine Generatormatrix für C an.
3. Was ist die größte ganze Zahl t, sodass der Code alle Fehlermuster bis zu t Fehlern korrigieren kann?
4. Wie würde der empfangene Vektor 101010101 dekodiert werden?

Lösung zu Aufgabe 4

1. Dies ist ein [9, 3, 3]-Code. Die Prüfmatrix H (vermutlich 6x9) hat linear unabhängige Zeilen. Es handelt sich tatsächlich um einen Wiederholungscode der Form (xxx, yyy, zzz) mit x, y, z ∈ {0, 1}. Daraus folgt leicht, dass der Minimalabstand 3 ist.
2. Zum Beispiel: [Die Generatormatrix ist im Originaldokument nicht angegeben.]
3. t = 1. Der Code kann einen Fehler korrigieren.
4. Das nächste Codewort ist 111000111. Der empfangene Vektor unterscheidet sich in jedem Triplett von Bits um ein Symbol. Es gibt kein anderes Codewort mit geringerem Abstand, und der Minimalabstand des Codes ist 3. Daher wäre der Decoderausgang... [Die vollständige Dekodierung ist im Originaldokument nicht angegeben.]

Aufgabe 5: Eigenschaften des Binären Paritätscodes

Betrachten Sie den einfachen binären Paritätscode (n, n-1), bei dem die Redundanz so gewählt ist, dass die Anzahl der Einsen (das Gewicht) aller Codewörter gerade ist.

1. Zeigen Sie, dass er zyklisch ist, und geben Sie sein Generatorpolynom an.
2. Berechnen Sie die Wahrscheinlichkeit, dass kein Fehler erkannt wird, wenn über einen binären symmetrischen Kanal ohne Gedächtnis übertragen wird.

Lösung zu Aufgabe 5

1. Zuerst zeigen wir, dass der Code linear ist. Dies ist wahr, da der Code aus allen Vektoren von n Bits mit geradem Gewicht besteht, den Nullvektor enthält und unter der Addition abgeschlossen ist. Um zu zeigen, dass er zyklisch ist, genügt der Hinweis, dass die zyklische Verschiebung eines Codeworts dessen gerades Gewicht beibehält und somit ein weiteres Codewort ergibt. Das Generatorpolynom ist g(x) = x + 1.
2. Die Wahrscheinlichkeit, dass kein Fehler erkannt wird, ist: Sei A_2i die Anzahl der Codewörter mit Gewicht 2i. [Die Formel ist im Originaldokument nicht angegeben.]

Aufgabe 6: ARQ-Protokoll und Übertragungsrate

Betrachten Sie die folgenden Eigenschaften: Kanalkapazität C = 1 Mbit/s, Bitfehlerrate p = 5 × 10^-6, und vernachlässigbare Verarbeitungszeit. Wenn ein Stop-and-Wait-ARQ-Protokoll mit einer Fenstergröße von m = 100 verwendet wird, für welchen Wertebereich von n überschreitet die effektive Übertragungsrate 500 Kbit/s nicht?

Lösung zu Aufgabe 6

Da die effektive Übertragungsrate (oder Effizienz) des Protokolls von n abhängt, reduziert sich das Problem auf eine einfache mathematische Frage: Es geht darum, die Lösungen (falls vorhanden) der Gleichung (1 - k(n + m)) × (n / (n + m)) = 1/2 zu finden.

Wenn die Gleichung keine reelle Lösung hat oder nur eine, dann überschreitet die effektive Übertragungsrate für jeden Wert von n 500 Kbit/s.

Wenn die Gleichung jedoch zwei verschiedene reelle Lösungen hat, z.B. N₁ ≈ 100,5 und N₂ ≈ 99,799.5, dann überschreitet die effektive Übertragungsrate 500 Kbit/s nicht für n im Bereich [N₁, N₂] (oder [N₂, N₁, je nach Kontext der Ungleichung). [Der genaue Wertebereich ist im Originaldokument unklar und unvollständig.]