Eindeutig dekodierbare Kodes

01.03.2025, 16:36

Malcang

Eindeutig dekodierbare Kodes

Hallo Leute smile

ich beschäftige mich jetzt mit Kodierungstheorie , und schon hänge ich :-(
Ich habe diese Aufgabe hier:
[attach]58166[/attach]

Im Skript haben wir folgendes:
[attach]58167[/attach]
[attach]58168[/attach]

Nun, $\begin{eqnarray*} g_1 \end{eqnarray*}$ ist ein Trennzeichencode und damit eindeutig dekodierbar.
Bei $\begin{eqnarray*} g_2 \end{eqnarray*}$ sage ich, dass ist präfixfrei, und das bestätigt mir auch die Musterlösung.
Aber ich hätte bei allen anderen auch gedacht, dass sie präfixfrei sind, also habe ich etwas noch nicht verstanden.
Nehmen wir mal $\begin{eqnarray*} g_3 \end{eqnarray*}$ . Ich hätte jetzt jedes kodewort mit jedem anderen Kodewort konkateniert und geschaut, ob das wieder ein Kodewort rauskommt. Damit hätte ich ja dann folgende Tabelle erhalten (kann ich keine "tabular" machen? Also ich habe alle Kombinationen gebildet mit den kodewörtern):
$\begin{eqnarray*} \begin{vmatrix} 0000 & 00001 & 000100 & 001010 \\ 00100 & 001001 & 0010100 & 0011010 \\ 010000 & 0100001 & 01000100 & 01001010 \\ 101000 & 1010001 & 10100100 & 10101010 \end{vmatrix} \end{eqnarray*}$

Und es kommt jeweils kein Kode raus, der von einem anderen Wort erzeugt wird.
Trotzdem ist $\begin{eqnarray*} g_3 \end{eqnarray*}$ nicht eindeutig dekodierbar, denn $\begin{eqnarray*} g_3(0310) = g_3(122) = 00101000100 \end{eqnarray*}$ .

Wo mache ich den Fehler?

01.03.2025, 16:51

IfindU

Auf diesen Beitrag antworten »

RE: Eindeutig dekodierbare Kodes

Zitat:

Original von Malcang
Und es kommt jeweils kein Kode raus, der von einem anderen Wort erzeugt wird.
Trotzdem ist $\begin{eqnarray*} g_3 \end{eqnarray*}$ nicht eindeutig dekodierbar, denn $\begin{eqnarray*} g_3(0310) = g_3(122) = 00101000100 \end{eqnarray*}$ .

Wo mache ich den Fehler?

Du hast mit deiner Tabelle nur gezeigt, dass man bei Codierung von zwei Inputsziffern, und man weiß dass es genau zwei Inputziffern gab, es zurückkodieren kann. In dem speziellen Fall gilt sogar etwas stärkeres. Was du machen müsstest, ist bis zu 4 Inputsziffern nehmen (in dem Beispiel, potentiell mehr in anderen Beispielen), alle Kombinationen bestimmen und dann vergleichen. Hier würdest du ein Gegenbeispiel finden.

Aber an der Stelle sagst du "Ich habe etwas geguckt, kein Gegenbeispiel gefunden, also wird es wohl keins geben". Und das stimmt nunmal nicht, wie du selbst schreibst.

01.03.2025, 17:15

Malcang

Auf diesen Beitrag antworten »

RE: Eindeutig dekodierbare Kodes
Danke IfindU, das verstehe ich.

Zitat:

Original von IfindUWas du machen müsstest, ist bis zu 4 Inputsziffern nehmen (in dem Beispiel, potentiell mehr in anderen Beispielen), alle Kombinationen bestimmen und dann vergleichen.

Es könnte also sein, dass ich bei einem bestimmten Kode auch mal $\begin{eqnarray*} 10^9 \end{eqnarray*}$ Möglichkeiten probieren müsste, um festzustellen, dass er präfixfrei ist?

01.03.2025, 17:37

IfindU

Auf diesen Beitrag antworten »

Ach, du wolltest Präfixfreiheit überprüfen... Dann verstehe ich deine Tabelle nicht ganz. Es sollten dort 16 Wörter stehen (wie bei dir), aber 9 davon sollten Länge 4 haben, 4 der Länge 5 und 1 Wort der Länge 6. Bei dir wirkt es deutlich anders. Und für Präfixheit musst du noch $\begin{eqnarray*} \Gamma^{0+} \end{eqnarray*}$ als Möglichkeit dazu nehmen.

Edit: Sorry, hab $\begin{eqnarray*} g_3 \end{eqnarray*}$ mit $\begin{eqnarray*} g_4 \end{eqnarray*}$ verwechselt.... Risiko wenn man teilweise bei 0 startet, und teilweise bei 1 Hammer

Edit 2: Dann vermute ich, es ist ein Fehler in der Definition 3.1.6. Es sollte wohl $\begin{eqnarray*} x,y \in \Sigma^{+} \end{eqnarray*}$ stehen. Ansonsten wäre Lemma 3.1.7 falsch.

01.03.2025, 17:49

Malcang

Auf diesen Beitrag antworten »

Ich rechne damit, eine solche Aufgabe als Prüfungsaufgabe zu bekommen. Das ist dann mal 16 Kombinationen bilde, OK. (Schriftlich. Bei einer mündlichen wäre das erklären kein Thema).
Aber 64 sicher nicht mehr. Kann ich die Präfixfreiheit schon leichter erkennen?

01.03.2025, 17:59

IfindU

Auf diesen Beitrag antworten »

An der Stelle würde ich nicht versuchen alle Kombinationen zu bilden. Der Code "sieht" aber nicht decodierbar aus, weil eben $\begin{eqnarray*} g(03) \end{eqnarray*}$ mit $\begin{eqnarray*} 001 \end{eqnarray*}$ startet, genauso wie $\begin{eqnarray*} g(1) \end{eqnarray*}$ . Was ja genau das Gegenbeispiel ist. Von zu gucken ob man es vervollständigen kann, so dass es das gleiche Wort ist, klingt nach einer besseren Strategie ein Gegenbeispiel zu finden.

Wenn die Aufgabe ist Präfixfreiheit zu beweisen...Dann hoffe ich die Codes sind einfach genug dass man etwas offensichtliches als Begründung sieht warum es ausreicht $\begin{eqnarray*} x,y \in \Sigma^1 \end{eqnarray*}$ zu untersuchen...

Edit: Kann es sein, dass es ausreicht Wörter bis zur Länge vom kgv der Codelängen zu untersuchen? Was in Fall $\begin{eqnarray*} g_3 \end{eqnarray*}$ dann Wortlänge 20 bedeutet, bei $\begin{eqnarray*} g_4 \end{eqnarray*}$ nur Wortlänge 6?

01.03.2025, 19:56

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU

Edit: Kann es sein, dass es ausreicht Wörter bis zur Länge vom kgv der Codelängen zu untersuchen? Was in Fall $\begin{eqnarray*} g_3 \end{eqnarray*}$ dann Wortlänge 20 bedeutet

Nicht 12?

Edit: Im Buch "Informations- und Kodierungstheorie" von Schönfeld et. al. finde ich diesen Passus (ich meine gerade nur die Def. 3.2.1)
[attach]58169[/attach]

Das wäre ja sehr leicht zu überprüfen und würde auch erklären, warum g_3 in meiner Aufgabe nicht dekodierbar ist, denn $\begin{eqnarray*} g_3(0) \end{eqnarray*}$ ist ein Präfix von $\begin{eqnarray*} g_3(1). \end{eqnarray*}$

Genügt das so?

Edit2: das würde ja dann auch zu meiner Definition 3.1.6 aus dem ersten Beitrag passen. Denn "der Kode" ist ja nur die Abbildung, also die Tabelle. Von daher muss ich ja laut dieser Definition nichts mehr konkatenieren.

02.03.2025, 09:52

IfindU

Auf diesen Beitrag antworten »

Ich glaube nicht, dass es so einfach ist. Wenn wir nur den Code $\begin{eqnarray*} g(0) = 0 \end{eqnarray*}$ und $\begin{eqnarray*} g(1) = 01 \end{eqnarray*}$ haben, so würde ich behaupten es ist dekodierbar. Wenigstens wie ich dekodierbar verstehe. Wenn du mir Code daraus gibst, werde ich eindeutig bestimmen können was der Input ist: Ich ersetze alle $\begin{eqnarray*} 01 \end{eqnarray*}$ durch $\begin{eqnarray*} 1 \end{eqnarray*}$ und hab den Originalcode.

02.03.2025, 11:06

Malcang

Auf diesen Beitrag antworten »

Sehe ich ein. Aber die Präfixfreiheit ist laut Lemma 3.1.7 ja auch nur hinreichend. Von daher hast du einen Kode erwischt, der nicht präfixfrei, aber trotzdem eindeutig dekodierbar ist.

Oder? verwirrt

02.03.2025, 11:16

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Das wäre ja sehr leicht zu überprüfen und würde auch erklären, warum g_3 in meiner Aufgabe nicht dekodierbar ist, denn $\begin{eqnarray*} g_3(0) \end{eqnarray*}$ ist ein Präfix von $\begin{eqnarray*} g_3(1). \end{eqnarray*}$

Genügt das so?

Wäre das aber nicht genau dein Argument?

02.03.2025, 11:29

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU

Zitat:

Wäre das aber nicht genau dein Argument?

Richtig, diese meine Aussage ging dann also daneben. Nach meinem jetzigen Verständnis hätte ich sagen sollen "Schauen wir mal, ob $\begin{eqnarray*} g_3 \end{eqnarray*}$ präfixfrei ist. Ist er nicht, also weiß ich noch nicht, ob er eindeutig dekodierbar ist. Da nicht alle Kodewörter gleiche Länge haben und auch kein Trennzeichenkode vorliegt, gehe ich von Nichtdekodierbarkeit aus und versuche, ein Gegenbeispiel zu finden."

Nach dem Lemma ist die Dekodierbarkeit sehr einfach zu zeigen, das Gegenteil allerdings scheint ein bisschen ein Glücksspiel zu sein (was in einer schriftlichen Prüfung aber sicherlich nicht darauf hinausläuft, dass man erstmal fünf Wörter konkatenieren muss).

Was meinst du?

Edit: In dem Beispiel oben sollte es dann bei K1 wohl heißen "Kode ohne präfix-Eigenschaft UND nicht dekodierbar"

02.03.2025, 14:27

IfindU

Auf diesen Beitrag antworten »

Mir fällt hierzu wenigstens nicht besseres ein. URL scheint hier mehr Erfahrung zu haben, vlt fällt ihm ja noch etwas besseres ein.

Zu K1: Ich habe das Komma im Beispieltext als "und" gelesen.

02.03.2025, 21:24

URL

Auf diesen Beitrag antworten »

Ich kenne mich damit leider auch nicht wirklich aus, folgende Überlegungen also ohne Gewähr smile

Zu $\begin{eqnarray*} g_4 \end{eqnarray*}$ fällt mir folgendes ein: Offenbar ist $\begin{eqnarray*} g_4(1) \end{eqnarray*}$ Präfix von $\begin{eqnarray*} g_4(3) \end{eqnarray*}$ . Liest man ein Codewort allerdings von rechts nach links, ist die Sache eindeutig und damit dekodierbar.

Bei $\begin{eqnarray*} g_5 \end{eqnarray*}$ hat man gewissermaßen in beiden Leserichtungen Präfixe, die Argumentation wie für $\begin{eqnarray*} g_4 \end{eqnarray*}$ zieht also nicht. Andererseits kann man sich überlegen, dass eine Kollision nur mit 01 bzw 011 beginnen kann und dass dann nur noch Einsen folgen können. Das passt aber dann von den Längen her nicht mehr.

03.03.2025, 08:45

Malcang

Auf diesen Beitrag antworten »

Guten Morgen zusammen,

Zitat:

Original von URL
Zu $\begin{eqnarray*} g_4 \end{eqnarray*}$ fällt mir folgendes ein: Offenbar ist $\begin{eqnarray*} g_4(1) \end{eqnarray*}$ Präfix von $\begin{eqnarray*} g_4(3) \end{eqnarray*}$ . Liest man ein Codewort allerdings von rechts nach links, ist die Sache eindeutig und damit dekodierbar.

Danke URL, damit hast du mir sogar meine nächste Frage vorweggenommen Big Laugh

Denn das was du schriebst ist auch genau die Musterlösung. Aber warum darf man sich das denn überhaupt mit "von rechts nach links" überlegen?

03.03.2025, 12:36

URL

Auf diesen Beitrag antworten »

Wenn ich den vorliegenden Code von links nach rechts lese und ihn auf zwei Arten als Folge von codewörtern darstellen kann, dann habe ich auch zwei Darstellungen, wenn ich ihn von rechts nach links lese.

Formal kann man sich vermutlich aus g und einer "Spiegelung" einen neuen Code definieren, der sich dann als präfixfrei erweist.

Neue Frage »

Antworten »

Eindeutig dekodierbare Kodes

Verwandte Themen