Nicht präfixfreier Code trotzdem eindeutig dekodierbar

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Nicht präfixfreier Code trotzdem eindeutig dekodierbar
Folgende Aussagen sind korrekt:

  • Präfixfreie Codes können eindeutig dekodiert werden.
  • Codes, deren Umkehr präfixfrei ist, können eindeutig dekodiert werden (siehe Why is this code uniquely decodable?)
  • Aus (2) folgt: Es gibt nicht präfixfreie Codes, die eindeutig dekodiert werden können.
  • Huffmannkodierungen liefern immer präfixfreie Codes.

Für den dritten Punkt siehe z. B. dieselbe Quelle (Why is this code uniquely decodable?): Der Code {0, 01, 110} kann eindeutig dekodiert werden, etwa 0110 muss 0-110 gewesen sein.

Ich hatte die Fehlvorstellung, dass (3) falsch wäre. Dunkel erinnere ich mich auch an Klausuraufgaben aus GTI der Form “warum bevorzugt man präfixfreie Codes”, wenn ich mich nicht ganz täusche. Deswegen dachte ich, dass ich mal den obigen Link hier teile, auf den ich gerade gestoßen bin :wink:

2 Likes