Optimaler Code und Längenpolynom

16.03.2025, 11:23

Malcang

Optimaler Code und Längenpolynom

Huhu mal wieder smile

ich habe gerade diese Aufgabe vor mir:
[attach]58195[/attach]

Ich bin mit der Optimalität noch nicht so vertraut...
Der Code ist doch sicher
$\begin{eqnarray*} 0\;\;\; 00 \end{eqnarray*}$
$\begin{eqnarray*} 1\;\;\; 01 \end{eqnarray*}$
$\begin{eqnarray*} 2\;\;\; 10 \end{eqnarray*}$
$\begin{eqnarray*} 3\;\;\; 110 \end{eqnarray*}$
$\begin{eqnarray*} 4 \;\;\;111 \end{eqnarray*}$

und damit ist das Längenpolynom ja auch das Gesuchte.

Aber was spricht denn gegen den Code
$\begin{eqnarray*} 0\;\;\; 00 \end{eqnarray*}$
$\begin{eqnarray*} 1\;\;\; 01 \end{eqnarray*}$
$\begin{eqnarray*} 2 \;\;\;10 \end{eqnarray*}$
$\begin{eqnarray*} 3\;\;\; 110 \end{eqnarray*}$
$\begin{eqnarray*} 4 \;\;\;1110 \end{eqnarray*}$

verwirrt

16.03.2025, 14:10

URL

Auf diesen Beitrag antworten »

RE: Optimaler Code und Längenpolynom
Der zweite Code hat doch eine andere Länge. Von daher sind beide doch nicht vergleichbar, oder? verwirrt

Was ist denn das Längenpolynom eine Codes?

16.03.2025, 14:19

Malcang

Auf diesen Beitrag antworten »

RE: Optimaler Code und Längenpolynom

Zitat:

Original von URL
Was ist denn das Längenpolynom eine Codes?

Sorry

Hier direkt die Definition aus dem Skript:
[attach]58197[/attach]

Was meinst du mit andere Länge? Ich kann da leider nicht folgen.

Ich tue mir im allgemeinen mit der Optimalität schwer. Wir haben diese Definition:
[attach]58198[/attach]
Das besagt mir doch, dass der optimale die kleinste erwartete Codewortlänge hat.
Für meine Aufgabe hier wäre es doch dann zu zeigen, dass der Code
a) kein noch kürzeres Codewort als $\begin{eqnarray*} xx \end{eqnarray*}$
b) kein längere Codewort als $\begin{eqnarray*} xxx \end{eqnarray*}$
haben kann.

Richtig?

16.03.2025, 14:41

URL

Auf diesen Beitrag antworten »

RE: Optimaler Code und Längenpolynom

Zitat:

Was meinst du mit andere Länge? Ich kann da leider nicht folgen.

Ich kannte den Begriff optimaler Code nur im Kontext von Blockcodes mit fester Codewortlänge.

16.03.2025, 17:50

Malcang

Auf diesen Beitrag antworten »

Ich glaube ich habe es raus.
zuerstmal können nicht die vier Wörter $\begin{eqnarray*} 00,01,10,11 \end{eqnarray*}$ vorkommen, denn das fünfte Wort braucht mindestens $\begin{eqnarray*} 3 \end{eqnarray*}$ Zeichen. Dieses könnte ich dann zweimal hintereinander schreiben. Dies könnte ich dann aber auch als $\begin{eqnarray*} 3 \end{eqnarray*}$ Wörter der Länge jeweils $\begin{eqnarray*} 2 \end{eqnarray*}$ auffassen und damit wäre der Code nicht eindeutig dekodierbar.
Es kann also höchstens 3 Wörter der Länge 2 geben.

Wir haben $\begin{eqnarray*} g(0) = 00 \end{eqnarray*}$ und $\begin{eqnarray*} g(1) = 01 \end{eqnarray*}$ gegeben. Gäbe es nun ein $\begin{eqnarray*} i\in\{2,3,4\} \end{eqnarray*}$ $\begin{eqnarray*} g(i) = 0 \end{eqnarray*}$ , dann würde $\begin{eqnarray*} g(ii) = g(0) \end{eqnarray*}$ gelten und damit wäre der Code nicht eindeutig dekodierbar.
Es kann also höchstens ein Wort der Länge 1 geben, nämlich das Wort $\begin{eqnarray*} 1 \end{eqnarray*}$ . Würde es das aber geben, bliebe für die verbleibenden zwei nur noch die Wörter $\begin{eqnarray*} 110, 010 \end{eqnarray*}$ übrig, und auch da finde ich ein Gegenbeispiel.
Damit kann es kein Wort der Länge 1 geben.

Betrachte den Code $\begin{eqnarray*} g(0) = 00, g(1) = 01, g(2) = 10, g(3) = 110, g(4) = 111 \end{eqnarray*}$ . Dieser ist eindeutig dekodierbar und hat die geringste erwartete Codewortlänge. Sein Polynom ist das gesuchte.

Ist das so schlüssig?

17.03.2025, 11:51

URL

Auf diesen Beitrag antworten »

So habe ich die Sache auch angegangen. Allerdings sehe ich nicht, wie man damit zum Ende kommen soll. Warum kommt z.B. ein Code mit den codewörtern 00,01,1 und zwei vierstelligen codewörtern icht in Betracht?
Wenn man das einstellige Codewort weg diskutiert hat, ist die Sache allerdings erledigt.

25.03.2025, 14:11

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
So habe ich die Sache auch angegangen. Allerdings sehe ich nicht, wie man damit zum Ende kommen soll. Warum kommt z.B. ein Code mit den codewörtern 00,01,1 und zwei vierstelligen codewörtern icht in Betracht?
Wenn man das einstellige Codewort weg diskutiert hat, ist die Sache allerdings erledigt.

Hallo nochmal, URL.
Ich habe noch eine Frage zu dieser Sache. Wir haben in der Musterlösung stehen, dass Codewörter der Länge drei und mehr nicht in Frage kommen, weil das bzgl. Optimalität gegen den Satz von McMillan und Kraft spricht.

[attach]58214[/attach]

Aber der macht doch darüber gar keine Aussage verwirrt

25.03.2025, 14:51

URL

Auf diesen Beitrag antworten »

Das ist meiner Meinung nach schlichtweg Unsinn, zumal das angegebene Polynom $\begin{eqnarray*} 3X^2+2X^3 \end{eqnarray*}$ doch bedeutet, dass der Code genau zwei Codewörter der Länge drei enthält.
Immerhin kann man mit dem genannte Satz begründen, dass es kein Codewort der Länge eins geben kann und damit ist man dann doch fertig.

25.03.2025, 15:02

Malcang

Auf diesen Beitrag antworten »

Oh Entschuldige bitte URL, ich habe zwei Aufgaben durcheinander geworfen Tränen

Dein Argument mit der Länge 1 habe ich jetzt aber verstanden!

Vielleicht hast du ja Lust, auch bei dieser einen blick zu werfen.
[attach]58215[/attach]
Falls ein Codewort die Länge 1 hat, dann kann ich den Code angeben:
$\begin{eqnarray*} g(0) = 1, g(1) = 10, g(2) = 110, g(3) = 111 \end{eqnarray*}$ und damit ist das Polynom $\begin{eqnarray*} X+X^2+2X^3 \end{eqnarray*}$ .
Falls eines Länge 2 hat, ist das Polynom eben $\begin{eqnarray*} 4X^2 \end{eqnarray*}$ .

Aber was spricht gegen einen Code, dessen kürzestes Wort die Länge 3 hat?

25.03.2025, 16:05

URL

Auf diesen Beitrag antworten »

Der Kode, den du angegeben hast, ist nicht einmal eindeutig dekodierbar. Der kann es also nicht sein, und ohne Kenntnis der Verteilung des Quellalphabetes wird man den auch nicht angeben können.
Auf der Suche nach einem optimalen Kode wird man mit möglichst kurzen Kodewörtern starten. Vier Kodewörter der Länge eins wären optimal, aber ein solcher Kode widerspricht McMillan-Kraft (und ist im Fall eines binären Kodes offenbar auch nicht eindeutig dekodierbar).
Also fängt man mit einem Kodewort der Länge eins an und McMillan-Kraft gibt einem $\begin{eqnarray*} X+X^2+2X^3 \end{eqnarray*}$ als möglichen Kandidaten für ein zugehöriges Längenpolynom. Kandidat, weil man bisher keinen passenden eindeutig dekodierbaren Kode angegeben hat.
Ganz analog geht es, wenn man mit kürzestem Kodewort der Länge zwei startet.

Jeder eindeutig dekodierbare Kode mit Kodewörtern der Länge mindestens drei kann nicht optimal sein, wenn man gezeigt hat, dass es einen eindeutig dekodierbare Kode zum Längenpolynom $\begin{eqnarray*} 4X^2 \end{eqnarray*}$ gibt.

25.03.2025, 17:53

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von URL
Auf der Suche nach einem optimalen Kode wird man mit möglichst kurzen Kodewörtern starten. Vier Kodewörter der Länge eins wären optimal, aber ein solcher Kode widerspricht McMillan-Kraft (und ist im Fall eines binären Kodes offenbar auch nicht eindeutig dekodierbar).
Also fängt man mit einem Kodewort der Länge eins an und McMillan-Kraft gibt einem $\begin{eqnarray*} X+X^2+2X^3 \end{eqnarray*}$ als möglichen Kandidaten für ein zugehöriges Längenpolynom.

Verstehe. "Besser" wäre $\begin{eqnarray*} X+2X^2+X^3 \end{eqnarray*}$ , aber das ergibt einen Wert $\begin{eqnarray*} >1 \end{eqnarray*}$ beim binären Code und geht deshalb nicht.

Zitat:

Original von URL
Kandidat, weil man bisher keinen passenden eindeutig dekodierbaren Kode angegeben hat.
Ganz analog geht es, wenn man mit kürzestem Kodewort der Länge zwei startet.

Ok, für diesen Fall hätte ich ja dann $\begin{eqnarray*} 4X^2 \end{eqnarray*}$ .

Hm ich überlge nochmal, so ganz 100% hat es nicht klick gemacht, aber 95% Big Laugh

Ich schreibe mal gerade was auf

Neue Frage »

Antworten »

Optimaler Code und Längenpolynom

Verwandte Themen