0 Daumen
283 Aufrufe

Aufgabe:

Man hat die Codierung
0 -> 00
1 -> 01
$ -> 1


Problem/Ansatz:
Wie beweise ich die Injektivität dieser Codierung?
f(x1)=f(x2) kann ich ja schwer nutzen, da ich ja Variablen schlecht codieren kann

Avatar von

1 Antwort

+1 Daumen

Sei w ein Wort über dem Alphabet {0, 1}.

Dann gibt es ein w', so das

        w = 00w'

oder

        w = 01w'

oder

        w = 1w'

ist. w' ist eindeutig durch die Anzahl der führenden Nullen von w bestimmt. w kann also eindeutig dekodiert werden, falls w' eindeutig dekodiert werden kann.

Es ist |w'| < |w|. Nach endlich vielen Dekodierungsschritten kommt man entweder zu

        w' = 00

oder

        w' = 01

oder

        w' = 11

oder

        w' = 10.

In den ersten drei Fällen ist die Dekodierung eindeutig. Im letzten gibt es keine Dekodierung.

Avatar von 106 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community