Hallo,
Habe eine Frage zu Codierung.
Wie kann man zeigen, dass folgender Code injektiv, also eindeutig umkehrbar ist?
{a, ba, abb, bbbb}
Kann mir da jemand auf die Sprünge helfen?
Hallo Reini,
es würde helfen, zu wissen was auf diesen Code abgebildet wird. Um festzustellen, ob eine Funktion injektiv ist, müsste man die Funktion dann schon mal anschauen können 
Gruss
Petra
Genau das ist mein Problem, ist eine Aufgabe auf einem Übungblatt für eine Vorlesung. Keine weiteren Angaben. Wenn ich Quell und Zielalphabet und die Zuordnung hätte wärs kein Problem. Aber so weiss ich leider nicht weiter.
Hallo reini,
Wie kann man zeigen, dass folgender Code injektiv, also
eindeutig umkehrbar ist?{a, ba, abb, bbbb}
Kann mir da jemand auf die Sprünge helfen?
Injektiv heißt, dass jede Codefolge eindeutig auf eine Ursprungsfolge (oder Klartext oder wie auch immer) zurückgeführt werden kann. Für diese Betrachtung ist es egal, wie das Quellalphabet aussieht, wichtig ist nur, dass es vier Zeichen umfasst.
Betrachte folgende Codierung:
(a, aa, aaa)
Die ist nicht injektiv oder eindeutig umkehrbar.
Nimm irgendein Quellalphabet, z.B. (x, y, z).
Die Zeichenkette „aaaa“ läßt sich nicht eideutig in das Quellalphabet zurückübertragen, denn alle diese Worte über dem Quellalphabet werden in die gleiche Zeichenkette kodiert:
xxxx, xxy, xyx, yxx, yy, xz, zx
Surjektiv hieße in diesem Zusammenhang übrigens, dass sich jede Codefolge sinnvoll ins Quellalphabet zurückübertragen läßt. Das ist bei deinem Beispiel nicht der Fall. Die Zeichenfolge „abbb“ läßt sich nicht ‚Rückstandsfrei‘ in Codewörter aufteilen.
Hilft das weiter?
Gruß,
Ralf
Danke für den Tipp, komm da aber nicht ganz mit
Ich nehme für mein Quellalphabet also etas an. Dezimalsystem ->
1 entspicht a
2 entspricht b
somit könnte ich ja alles eindeutg rückführen
a = 1
ba=21
abb=122
bbbb=2222
lieg ich da falsch?
Hallo reini,
[…]
lieg ich da falsch?
Leider ja.
War vielleicht nicht gut erklärt. Ich versuch’s nochmal.
Du hast einen ‚Code‘ gegeben in der Form {a, ba, abb, bbbb}. In der Aufgabe ist nicht angegeben, was kodiert wird. Das ist aber auch nicht nötig, um die Frage zu beantworten. Vielleicht sind es die Zahlen 1,2,3,4 oder die Zeichen a,e,i,o oder auch die Himmelsrichtungen N,S,O,W - wichtig ist nur, das wir so eine Codierung (= Abbildung) haben:
irgendwas\_nr\_1 -\> a
irgendwas\_nr\_2 -\> ba
irgendwas\_nr\_3 -\> abb
irgendwas\_nr\_4 -\> bbbb
Mal ein Beispiel. Du hast einen Schatz vergraben und notierst, wie Du ihn wiederfinden kannst. Du verwendest vier Anweisungen:
„1“ = gehe einen Schritt vorwärts,
„L“ = wende dich 90° nach links,
„R“ = wende dich 90° nach rechts,
„H“ = Halt, stehenbleiben und buddeln.
Wenn Du Deine Anfangsposition kennst (an der alten Eiche, Blickrichtung Norden), dann brauchst Du noch eine Anweisungsfolge etwa der Art
„111L11R11111L11L1R111H“
Du möchtest diese Anweisungsfolge kodieren. Bei verborgenen Schätzen sinnvollerweise, damit Uneingeweihte die Informationen nicht verstehen, in der Informationstechnik z.B. deshalb, um Informationen zu komprimieren (http://de.wikipedia.org/wiki/Shannon-Fano-Kodierung), binär zu übertragen (Beispiel: ASCII) oder fehlersicher(er) zu machen (Daten auf Festplatten oder CDs werden kodiert, damit nicht zu viele Nullen oder Einsen aufeinanderfolgen).
Nehmen wir mal an, Du entscheidest Dich für folgende Kodierung:
1 -> a
L -> ab
R -> ba
H -> bb
Zum Beispiel die Folge „1L1R1H“ wird dann zu „aababaabb“.
Wenn nun Deine Enkel den geheimen Plan nebst der Beschreibung der Kodierung in Deinem Nachlass finden, haben sie ein Problem:
Wenn die kodierte Anweisung lautet: „aabaabb“, dann kann das einerseits
a-ab-a-a-bb sein, aber auch
a-a-ba-a-bb.
Die beiden Informationen 1L11H und 11R1H werden auf das gleiche kodierte Wort abgebildet, die Kodierung ist nicht injektiv.
Jetzt müsstest Du bei dem Code aus Deiner Aufgabe überprüfen, ob jedes Wort über a und b eindeutig (zweifelsfrei) in die vier Fragmente a, ba, abb oder bbbb zu zerlegen ist.
Jetzt klarer?
Gruß,
Ralf
Danke, jetzt hab ichs glaub ich gekneist. Hab jetzt nur ein Problem,
du hast mir soeben verständlich erklärt dass dieser Code nicht injektiv sei. Mein LV Leiter meinen jedoch, dass er sehrwohl eindeutig umkehrbar ist. Ich versteh die Welt nicht mehr.
du hast mir soeben verständlich erklärt dass dieser Code nicht
injektiv sei. Mein LV Leiter meinen jedoch, dass er sehrwohl
eindeutig umkehrbar ist. Ich versteh die Welt nicht mehr.
Ich habe Dir mit {a, ab, ba, bb} ein Beispiel einer nicht injektiven Kodierung gegeben und erläutert, warum sie nicht injektiv ist. Über die in Deiner Aufgabe vorgegebene Kodierung {a, ba, abb, bbbb} habe ich gar nichts gesagt.
Stelle Dir irgendeine Folge von a’s und b’s vor und überlege, warum Du dem Anfang der Folge immer zweifelsfrei ansehen kannst, dass es nur eins der vier Elemente aus {a, ba, abb, bbbb} sein kann. (Warum ist das bei {a,ab,ba,bb} nicht der Fall?)
Gruss,
Ralf