Deutsch
Menü

Grundlagen der Informationstheorie und Kodierung

Informationsgehalt und Entropie, Transinformation, Redundanz, Codes fester und variabler Länge, Präfixcodes und die Kraft-Ungleichung, mittlere Codewortlänge und Effizienz der Huffman-Kodierung, Lauflängenkodierung, das LZ77-Verfahren, verlustfreie und verlustbehaftete Kompression, Parität und Kreuzparität, Prüfsummen, CRC-Berechnung, Hamming-Abstand und die Fähigkeit zur Fehlererkennung und -korrektur, Hamming-Codes und SECDED, Coderate, Interleaving, ARQ und FEC, die Kapazität des binären symmetrischen Kanals, das Kanalkodierungstheorem und die Umrechnung des Gray-Codes, erarbeitet mit Multiple-Choice-Fragen, überwiegend Rechenaufgaben.

10 Fragen übenZufällige Fragen aus diesem Thema · etwa 5 Minuten Dieses Thema übenAlle Fragen dieses Themas in zufälliger Reihenfolge Schwache FragenNur zuletzt falsch beantwortete Fragen erneut üben

Grundlagen der Informationstheorie und Kodierung: Kernpunkte

„Wie viele Bit ist diese Information wert?“ „Wie klein lassen sich diese Daten machen?“ „Wie lassen sich durch Rauschen verfälschte Bits finden und korrigieren?“ Solche Fragen beantworten die von Shannon begründete Informationstheorie und die Kodierungstheorie. Sie stecken überall in Computern und in der Kommunikation: in der Dateikompression, im ECC von Speichern, in der Fehlerkorrektur auf Übertragungskanälen, in den CRCs von Speichergeräten und an vielen anderen Stellen.

Hier werden der Informationsgehalt −log₂ p und die Entropie, die Bedingung für maximale Entropie, bedingte Entropie und Transinformation, Redundanz und die zum Unterscheiden nötige Zahl von Bits rechnerisch nachvollzogen. Danach geht es um Codes fester und variabler Länge, Präfixcodes und die Kraft-Ungleichung, den Aufbau eines Huffman-Codes und seine mittlere Codewortlänge, die Effizienz im Vergleich mit der Entropie, die Wirkung der gemeinsamen Kodierung mehrerer Symbole, Lauflängenkodierung und das LZ77-Verfahren sowie die Wahl zwischen verlustfreier und verlustbehafteter Kompression. Die zweite Hälfte behandelt Parität und Kreuzparität, die Schwäche von Prüfsummen, die Berechnung von CRC-Prüfbits und die Erkennung von Bündelfehlern, den Hamming-Abstand und die Zahl der erkennbaren und korrigierbaren Bitfehler, die Lokalisierung eines Fehlers mit dem Syndrom des Hamming-Codes (7, 4), die Zahl der SECDED-Prüfbits, die Coderate, Interleaving, ARQ und FEC sowie die Kapazität des binären symmetrischen Kanals und das Kanalkodierungstheorem; zum Schluss wird die Umrechnung des Gray-Codes geübt. Das hilft auch bei der Vorbereitung auf IT-Zertifizierungsprüfungen im Bereich der theoretischen Grundlagen (Informationstheorie und Kommunikationstheorie). Die Werte der Rechenaufgaben, einschließlich der Werte der falschen Antwortmöglichkeiten und der Huffman-Bäume, wurden mit Python nachgerechnet. Binärzahlen und Gleitkommazahlen werden in „Computerarithmetik“ behandelt, die Berechnung eines Paritätsbits und die Eigenschaften des Gray-Codes in „Logikschaltungen“, die Umrechnung von Binär- in Gray-Code in „Timing-Analyse und CDC“, die Wahrscheinlichkeit der Fehler, die eine Paritätsprüfung übersieht, in „Wahrscheinlichkeitsrechnung, Statistik und Warteschlangen“, die Berechnung der Kanalkapazität nach dem Shannon-Hartley-Gesetz in „Grundlagen der Funkkommunikation“, ECC für Speicher in „DRAM“, die 8b/10b-Kodierung und die CRC von PCI Express in „Schnittstellen und Busstandards“, Base64 und gzip in „Grundlagen der Webtechnologien“, die Kreuzentropie in „Grundlagen des maschinellen Lernens“ sowie Hashes und Kryptografie in „Grundlagen der Informationssicherheit“.

Alle Fragen zu Grundlagen der Informationstheorie und Kodierung (40)
  1. Der Informationsgehalt, den man erhält, wenn man erfährt, dass ein Ereignis mit der Wahrscheinlichkeit p eingetreten ist, sei −log₂ p Bit. Wie groß ist der Informationsgehalt der Nachricht, dass ein Ereignis mit der Wahrscheinlichkeit 1/8 eingetreten ist?
  2. Welche Aussage über den Informationsgehalt (−log₂ p bei der Nachricht, dass ein Ereignis mit der Wahrscheinlichkeit p eingetreten ist) ist richtig?
  3. Eine Quelle gibt die Symbole A, B, C und D unabhängig voneinander mit den Wahrscheinlichkeiten 1/2, 1/4, 1/8 und 1/8 aus. Wie groß ist die Entropie dieser Quelle (der mittlere Informationsgehalt pro Symbol)?
  4. Welche Kombination aus dem Maximalwert der Entropie einer Quelle, die 8 verschiedene Symbole ausgibt, und der Bedingung, unter der er erreicht wird, ist richtig?
  5. Eine binäre Quelle gibt unabhängig voneinander 0 mit der Wahrscheinlichkeit 0,9 und 1 mit der Wahrscheinlichkeit 0,1 aus. Es gelte log₂ 0,9 ≈ −0,152 und log₂ 0,1 ≈ −3,32. Welcher Wert liegt der Entropie dieser Quelle am nächsten?
  6. Die Entropie einer Quelle, die 8 verschiedene Symbole ausgibt, beträgt 2,4 Bit. Die Redundanz sei als 1 − (Entropie ÷ maximale Entropie) definiert. Wie groß ist die Redundanz dieser Quelle?
  7. Welche Aussage über die bedingte Entropie H(X|Y) und die Transinformation I(X;Y) zweier Zufallsvariablen X und Y ist richtig?
  8. Für zwei Zufallsvariablen X (Wert 0 oder 1) und Y (Wert a, b oder c) gelten die Verbundwahrscheinlichkeiten P(0, a) = P(0, b) = P(1, b) = P(1, c) = 1/4; alle anderen Kombinationen haben die Wahrscheinlichkeit 0. Wie groß ist die Transinformation I(X;Y)?
  9. 36 Zeichen, nämlich 26 Großbuchstaben und 10 Ziffern, sollen durch Bitfolgen gleicher Länge (einen Code fester Länge) unterschieden werden. Wie viele Bit werden pro Zeichen mindestens benötigt?
  10. Welche Aussage über Codes variabler Länge im Vergleich zu Codes fester Länge ist richtig?
  11. Welche der folgenden Mengen von Codewörtern für 4 Symbole ist ein Präfixcode (ein Code, in dem kein Codewort der Anfang eines anderen Codeworts ist)?
  12. Ein Präfixcode ordnet den Symbolen A, B, C und D die Codewörter A = 0, B = 10, C = 110 und D = 111 zu. Was ergibt die Dekodierung der Bitfolge 110100111 von vorn?
  13. Den 4 Symbolen A bis D sollen Codewörter der folgenden Längen (in Bit) zugeordnet werden, sodass ein Präfixcode aus 0 und 1 entsteht. Mit welcher Kombination von Codewortlängen ist das möglich?
  14. Es wird ein Präfixcode aus 0 und 1 aufgebaut. Die Codewörter 00 und 01 der Länge 2 sind bereits vergeben. Wie viele Codewörter der Länge 3 lassen sich höchstens hinzufügen, ohne die Präfixbedingung zu verletzen?
  15. Eine Quelle gibt die Symbole A, B, C und D unabhängig voneinander mit den Wahrscheinlichkeiten 0,4; 0,3; 0,2 und 0,1 aus und wird mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro Symbol?
  16. Eine Quelle gibt die Symbole A bis E unabhängig voneinander mit den Wahrscheinlichkeiten 0,3; 0,25; 0,2; 0,15 und 0,1 aus und wird mit einem Huffman-Code kodiert. Je nachdem, welche von zwei gleichen Wahrscheinlichkeiten zuerst gewählt wird, können sich die Codewörter ändern, die mittlere Codewortlänge jedoch nicht. Wie groß ist die mittlere Codewortlänge pro Symbol?
  17. Eine Quelle gibt die Symbole A, B und C unabhängig voneinander mit den Wahrscheinlichkeiten 0,6; 0,3 und 0,1 aus; ihre Entropie beträgt etwa 1,30 Bit. Welcher Wert liegt der Effizienz (Entropie ÷ mittlere Codewortlänge) am nächsten, wenn diese Quelle mit einem Huffman-Code kodiert wird?
  18. Eine binäre Quelle gibt unabhängig voneinander 0 mit der Wahrscheinlichkeit 0,8 und 1 mit der Wahrscheinlichkeit 0,2 aus. Je 2 Symbole werden zusammengefasst; die 4 Kombinationen 00, 01, 10 und 11 werden jeweils als ein Symbol betrachtet und mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro ursprünglichem Symbol?
  19. Welche Aussage über den Zusammenhang zwischen verlustfreier Kompression und der Entropie einer Quelle ist richtig?
  20. Die 40 Zeichen lange Zeichenkette AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12-mal A, 4-mal B, 20-mal C, 4-mal D) wird mit einer Lauflängenkodierung komprimiert, die jede Folge gleicher Zeichen als Paar „Zeichen (1 Byte) und Anzahl (1 Byte)“ darstellt. Die ursprüngliche Zeichenkette belegt 1 Byte pro Zeichen, und die Kompressionsrate sei „Größe nach der Kompression ÷ Größe vor der Kompression“. Wie groß ist die Kompressionsrate?
  21. Bei welchen Daten lässt sich die Größe durch Lauflängenkodierung am ehesten stark verringern?
  22. Welche Aussage beschreibt das Prinzip des LZ77-Verfahrens, das in ZIP, gzip und anderen Formaten verwendet wird, richtig?
  23. Mit dem LZ77-Verfahren komprimierte Daten werden wiederhergestellt. Die Daten lauten in dieser Reihenfolge „Zeichen A“, „Zeichen B“, „(Entfernung 2, Länge 5)“. (Entfernung d, Länge L) bedeutet, L-mal Zeichen für Zeichen „das Zeichen, das d Zeichen vor dem Ende der bereits wiederhergestellten Zeichenkette steht, ans Ende kopieren“. Welche Zeichenkette ergibt sich?
  24. Bei welcher Anwendung muss beim Komprimieren verlustfreie Kompression statt verlustbehafteter Kompression verwendet werden?
  25. An eine Bitfolge von Daten wird ein gerades Paritätsbit angehängt, sodass die Zahl der Einsen gerade ist, und mitgesendet. Welche Aussage über die Prüfung, bei der der Empfänger die Einsen zählt, ist richtig?
  26. Gesendet werden 4 Zeilen mit je 4 Datenbits; an jede Zeile wird rechts ihr gerades Paritätsbit angehängt, und am Ende folgt eine Zeile mit den geraden Paritätsbits der Spalten (Kreuzparität). Empfangen wurden Zeile 1: 1011 1, Zeile 2: 0100 0, Zeile 3: 1100 0, Zeile 4: 0101 0, Paritätszeile: 0100 (das rechte Bit jeder Zeile ist die Zeilenparität). Wenn genau 1 Bit falsch ist, an welcher Position liegt es?
  27. Die Daten werden byteweise addiert, und die unteren 8 Bit der Summe werden als Prüfwert (Prüfsumme) angehängt und mitgesendet. Welchen Fehler kann diese Prüfung nicht erkennen?
  28. An die Daten 1101 werden 3 CRC-Prüfbits mit dem Generatorpolynom x³ + x + 1 (Bitfolge 1011) angehängt. Die Prüfbits sind der Rest der Division von 1101000, also den Daten mit 3 angehängten Nullen, durch 1011, wobei bei der Division statt der Subtraktion das exklusive ODER (XOR) verwendet wird. Wie lauten die Prüfbits?
  29. Welche Aussage über eine CRC, deren Generatorpolynom den Grad r hat (r Prüfbits) und deren konstantes Glied 1 ist, ist richtig?
  30. Wie groß ist der Hamming-Abstand der beiden 7-Bit-Codewörter 1011010 und 0110011?
  31. Der minimale Hamming-Abstand eines Codes (der kleinste Hamming-Abstand zwischen zwei beliebigen Codewörtern) beträgt 5. Betrachtet werden die Verwendung nur zur Fehlererkennung und die Verwendung nur zur Fehlerkorrektur. Welche Kombination aus der Zahl der Bitfehler, die sicher erkannt werden, und der Zahl der Bitfehler, die sicher korrigiert werden, ist richtig?
  32. Welche Kombination aus dem minimalen Hamming-Abstand des Codes mit den 4 Codewörtern 00000, 01011, 10101 und 11110 und der Zahl der Bitfehler, die er sicher korrigiert, ist richtig?
  33. Welcher Wert liegt der Coderate des Hamming-Codes (7, 4) am nächsten, der 4 Datenbits um 3 Prüfbits zu einem 7-Bit-Codewort ergänzt?
  34. Beim Hamming-Code (7, 4) seien die 7 Bit von links als Bit 1 bis 7 nummeriert, und die Bits 1, 2 und 4 seien Prüfbits. Prüfung 1 macht die Zahl der Einsen in den Bits 1, 3, 5, 7 gerade, Prüfung 2 die in den Bits 2, 3, 6, 7 und Prüfung 4 die in den Bits 4, 5, 6, 7. Im empfangenen Wort 0110001 ist 1 Bit falsch. Welches Bit ist es?
  35. 32 Datenbits erhalten einen SECDED-Code, der 1-Bit-Fehler korrigiert und 2-Bit-Fehler erkennt. Die Zahl r der Prüfbits eines Hamming-Codes ist der kleinste Wert mit 2^r ≥ Zahl der Datenbits + r + 1; bei SECDED kommt 1 Bit für die Parität über das gesamte Wort hinzu. Wie viele Prüfbits werden benötigt?
  36. 5 Codewörter des Hamming-Codes (7, 4) werden nebeneinandergestellt und in dieser Reihenfolge gesendet: zuerst das 1. Bit aller 5 Codewörter, dann das 2. Bit aller 5 und so weiter (Interleaving der Tiefe 5). Der Empfänger stellt die ursprüngliche Reihenfolge wieder her und korrigiert dann in jedem Codewort einen 1-Bit-Fehler. Welches ist die größte Länge eines Bündelfehlers (Fehler, die sich auf aufeinanderfolgende Bits konzentrieren), der immer korrigiert werden kann?
  37. Welche Aussage über ARQ (automatische Wiederholungsanfrage) und FEC (Vorwärtsfehlerkorrektur) als Verfahren zum Umgang mit Fehlern in der Kommunikation ist richtig?
  38. Ein binärer symmetrischer Kanal überträgt 0 und 1, wobei jedes Bit unabhängig mit der Wahrscheinlichkeit 0,1 kippt. Für die binäre Entropie H(p) = −p log₂ p − (1 − p) log₂(1 − p) gilt H(0,1) ≈ 0,469. Welcher Wert liegt der Kanalkapazität dieses Kanals pro Übertragung am nächsten?
  39. Welche Aussage beschreibt den Inhalt des Kanalkodierungstheorems von Shannon richtig?
  40. Um einen Gray-Code in eine gewöhnliche Binärzahl umzuwandeln, wird das höchstwertige Bit unverändert übernommen, und jedes niedrigere Bit ergibt sich als XOR aus dem an der nächsthöheren Stelle ermittelten Binärbit und dem Gray-Code-Bit an derselben Stelle. Welche Binärzahl ergibt sich aus dem 4-Bit-Gray-Code 1101?

Weitere Themen in Computersysteme