Deutsch
Menü

Was ist Präfixcode?

Ein Code, in dem kein Codewort der Anfang eines anderen Codeworts ist. {0, 10, 110, 111} ist zum Beispiel ein Präfixcode: Liest man die empfangene Bitfolge von vorn und trennt, sobald ein Codewort übereinstimmt, lässt sie sich eindeutig dekodieren, ohne auf folgende Bits zu warten. Deshalb heißt er auch sofort dekodierbarer Code. Erfüllen die Codewortlängen die Kraft-Ungleichung, lässt sich ein Präfixcode mit diesen Längen bilden. Huffman-Codes sind Präfixcodes. Manche Codes, die keine Präfixcodes sind, etwa {0, 01, 11}, lassen sich ebenfalls eindeutig dekodieren, erfordern beim Dekodieren aber einen Blick auf folgende Bits.

Japanische Bezeichnung: 接頭符号

„Präfixcode“ kommt in 5 Übungsfragen aus 1 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung.

Fachgebiet: Grundlagen der Informationstheorie und Kodierung

Jetzt üben: Fragen zu Präfixcode

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)?

  1. A{0, 01, 011, 111}
  2. B{0, 10, 110, 111}
  3. C{00, 01, 1, 10}
Antwort und Erläuterung anzeigen

Antwort: B. {0, 10, 110, 111}

Bei einem Präfixcode steht schon nach dem letzten Bit eines Codeworts fest, um welches Symbol es sich handelt, sodass sofort dekodiert werden kann, ohne auf folgende Bits zu warten (sofort dekodierbarer Code). In {0, 10, 110, 111} ist kein Codewort der Anfang eines anderen. In {0, 01, 011, 111} ist 0 der Anfang von 01 und 011, in {00, 01, 1, 10} ist 1 der Anfang von 10.

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?

  1. ACABD
  2. BCBDA
  3. CCBAD
Antwort und Erläuterung anzeigen

Antwort: C. CBAD

Man liest von vorn und trennt, sobald ein Codewort übereinstimmt: 110 ergibt C, die folgende 10 ergibt B, 0 ergibt A und die restliche 111 ergibt D, also CBAD. Da es ein Präfixcode ist, ist die Trennung auf diese Weise eindeutig, und es lässt sich ohne Trennzeichen dekodieren.

„Präfixcode“ in den Erläuterungen

Fragen mit „Präfixcode“ (5)

  1. 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)?
  2. 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?
  3. 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?
  4. 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?
  5. Welche Aussage über Codes variabler Länge im Vergleich zu Codes fester Länge ist richtig?

Verwandte Begriffe

Kraft-Ungleichung Mittlere Codewortlänge Binärer symmetrischer Kanal Hamming-Abstand Hamming-Code Huffman-Kodierung Informationsentropie Informationsgehalt Lauflängenkodierung Paritätsbit

Zur Glossarübersicht