Datenkompression von Bitstreams

16.05.2013, 23:43	GroovyChuc	Auf diesen Beitrag antworten »
Datenkompression von Bitstreams Hey Ich komme bei folgender Aufgabenstellung nicht weiter. http://pic-upload.eu/index.php?Section=Picture&Action=ShowPicBig&p=4976d6f5b50db445b6bef502ee953301 Ich glaube es liegt daran, dass man bei der Dekomprimierung die Komprimierfunktion "rückwarts" anwenden müsste. Das geht natürlich nicht, wieso es zu Datenverlust kommt. Aber generell fehlt mir der Ansatz um das zu beweisen. Ich hoffe ihr könnt mir helfen
17.05.2013, 00:44	RavenOnJ	Auf diesen Beitrag antworten »
zu a) Die Menge aller Bitstrings der Länge n hat Mächtigkeit $\begin{eqnarray} 2^n \end{eqnarray}$ . Ein Algorithmus, der verlustlos codiert, muss injektiv abbilden. Da die Menge aller Bitstrings mit Länge $\begin{eqnarray} < n \end{eqnarray}$ gleich $\begin{eqnarray} \sum_{k=1}^{n-1}2^{k}= 2^n -2 \end{eqnarray}$ ist, kann es keine injektive Abbildung der Menge aller n-Bitstrings auf die Menge aller Bitstrings mit einer Länge kleiner n geben. Es muss also mindestens zwei Bitstrings der Länge n geben, die auf denselben Bitstring kürzerer Länge abgebildet werden.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »