Codewort-Gültigkeit < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:16 Sa 26.01.2013 | | Autor: | giotto |
| Aufgabe | | Thema: Zyklischer Hamming-Code. Gegeben sei das Generatorpolynom [mm] p(x)=1+x+x^{4} [/mm] und das dazugehörende rückgekoppelte Schieberegister. Geben Sie mit Hilfe des Schieberegisters an, ob das folgende Codewort gültig ist (Weg muss ersichtlich sein). Codewort: 000 0000 1011 1101 |
Hallo
Vorweg: ich bin nicht sicher, ob ich das richtige Unterforum erwischt habe.
Es geht um eine Frage zur angegebenen Aufgabe, die im Rahmen unseres Kurses "Informations- und Codierungstheorie" an der Uni gestellt wurde.
Die Inhalte des Schieberegisters konnte ich ermitteln.
Inputzeichen | Schieberegisterinhalt von links nach rechts mit Reihenfolge der Polynome zwischen den einzelnen Registerinhalten [mm] x^{4}, x^{3}, x^{2}, x^{1}, x^{0}:
[/mm]
0 | 0 0 0 0 (theoretisch 7mal)
1 | 0 0 1 1
0 | 0 1 1 0
1 | 1 1 1 1
1 | 1 1 1 0
1 | 1 1 0 0
1 | 1 0 0 0
0 | 0 0 1 1
1 | 0 1 0 1
Das heisst, die Kontrollstellen zum obigen Codewort lauten 0101.
Nun steht aber nichts mehr in der Lösung.
Mir ist nun nicht ganz klar, wie ich denn damit nun "angegeben" habe, dass das Codewort gültig ist... Ich meine, so könnte ich einen beliebigen Input ins Register schieben und das würde mir dann dazu passende Kontrollstellen ausspucken - somit wäre ja "jedes" Codewort/jede Inputzeichenkette gültig, die ich da einspeisen.
Könnte mir vielleicht jemand einen Denkanstoss geben, wo ich denn nun einen Denkfehler mache? Oder ist die Aufgabe unsinnig formuliert (was ich irgendwie vermute)?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:02 So 27.01.2013 | | Autor: | Infinit |
Hallo giotto,
ich vermute, dass in der Informatik Dir besser geholfen werden kann. Ich verschiebe Deine Frage mal dorthin.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:51 So 27.01.2013 | | Autor: | felixf |
Moin,
> ich vermute, dass in der Informatik Dir besser geholfen
> werden kann. Ich verschiebe Deine Frage mal dorthin.
ich hab's mal weiterverschoben in der Informatik. Ist nicht 100% das passende Forum, aber passt wohl am besten dorthin :)
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:53 So 27.01.2013 | | Autor: | felixf |
Moin!
> Thema: Zyklischer Hamming-Code. Gegeben sei das
> Generatorpolynom [mm]p(x)=1+x+x^{4}[/mm] und das dazugehörende
> rückgekoppelte Schieberegister. Geben Sie mit Hilfe des
> Schieberegisters an, ob das folgende Codewort gültig ist
> (Weg muss ersichtlich sein). Codewort: 000 0000 1011 1101
>
> Hallo
>
> Vorweg: ich bin nicht sicher, ob ich das richtige
> Unterforum erwischt habe.
>
> Es geht um eine Frage zur angegebenen Aufgabe, die im
> Rahmen unseres Kurses "Informations- und Codierungstheorie"
> an der Uni gestellt wurde.
>
> Die Inhalte des Schieberegisters konnte ich ermitteln.
Ich weiss nicht genau wie man das mit Schieberegistern macht - ich komme eher von der mathematischen Seite. Aber:
> Inputzeichen | Schieberegisterinhalt von links nach rechts
> mit Reihenfolge der Polynome zwischen den einzelnen
> Registerinhalten [mm]x^{4}, x^{3}, x^{2}, x^{1}, x^{0}:[/mm]
> 0 | 0
> 0 0 0 (theoretisch 7mal)
> 1 | 0 0 1 1
> 0 | 0 1 1 0
> 1 | 1 1 1 1
> 1 | 1 1 1 0
> 1 | 1 1 0 0
> 1 | 1 0 0 0
> 0 | 0 0 1 1
> 1 | 0 1 0 1
>
> Das heisst, die Kontrollstellen zum obigen Codewort lauten
> 0101.
Codewoerter sind normalerweise genau die Eingabebitstreams, deren Kontrollstellen im Ergebnis 0000 (bei anderen Codes mit anderer Anzahl Kontrollstellen die entsprechende Anzahl Nullen) sind. Wenn also nicht 0000 herauskommt, ist es kein Codewort.
> Nun steht aber nichts mehr in der Lösung.
> Mir ist nun nicht ganz klar, wie ich denn damit nun
> "angegeben" habe, dass das Codewort gültig ist... Ich
> meine, so könnte ich einen beliebigen Input ins Register
> schieben und das würde mir dann dazu passende
> Kontrollstellen ausspucken - somit wäre ja "jedes"
> Codewort/jede Inputzeichenkette gültig, die ich da
> einspeisen.
Nein, nur die, bei denen 0000 herauskommt.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:45 Mo 28.01.2013 | | Autor: | giotto |
Hallo Felix
Danke für die Antwort.
Mit dem Hinweis mit 0000 hast mir gut auf die Sprünge geholfen 
Wir hatten da noch das Verfahren mit der "schnellen Mehrfachaddition" - ich bin nun sicher, dass die Aufgabenstellung falsch war - man also nicht mit dem Schieberegister die Korrektheit zeigen soll, sondern mit der Mehrfachaddition, welche ich kurz der Vollständigkeit halber noch aufführen möchte:
Codewort: 000 0000 1011 1101
Generatorpolynom ist ja [mm] x^{4}+x+1, [/mm] demenentsprechend hat der Code 4 Kontrollstellen (höchster Grad des Polynoms).
Generator zum Generatorpolynom: 10011
000 0000 1011 1101
--- ---- 1001 1
--- ---- --10 011
===================
000 0000 0000 0011
[das Generator-Polynom wird so oft dazugezählt, bis alle Nachrichtenstellen aufaddiert Modulo2 Null ergeben. Anschliessend gibt die Summe bei den Kontrollstellen die Korrektheit an.]
Wie du schon gesagt hast, müsste bei einem gültigen Codewort das Fehlersyndrom/die Kontrollstellen 0000 sein - in diesem Fall ist es aber 0011, womit das Codewort nicht gültig ist.
Danke nochmals für den Hinweis.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:42 Mo 28.01.2013 | | Autor: | felixf |
Moin,
> Danke für die Antwort.
> Mit dem Hinweis mit 0000 hast mir gut auf die Sprünge
> geholfen
freut mich :)
> Wir hatten da noch das Verfahren mit der "schnellen
> Mehrfachaddition" - ich bin nun sicher, dass die
Die Mathematiker bezeichnen das auch als Division mit Rest in [mm] $\IF_2[x]$ [/mm] 
> Aufgabenstellung falsch war - man also nicht mit dem
> Schieberegister die Korrektheit zeigen soll, sondern mit
> der Mehrfachaddition, welche ich kurz der Vollständigkeit
> halber noch aufführen möchte:
>
> Codewort: 000 0000 1011 1101
> Generatorpolynom ist ja [mm]x^{4}+x+1,[/mm] demenentsprechend hat
> der Code 4 Kontrollstellen (höchster Grad des Polynoms).
> Generator zum Generatorpolynom: 10011
>
> 000 0000 1011 1101
> --- ---- 1001 1
> --- ---- --10 011
> ===================
> 000 0000 0000 0011
> [das Generator-Polynom wird so oft dazugezählt, bis alle
> Nachrichtenstellen aufaddiert Modulo2 Null ergeben.
> Anschliessend gibt die Summe bei den Kontrollstellen die
> Korrektheit an.]
Genau. Bei Division durch [mm] $x^4 [/mm] + x + 1$ laesst das Polynom [mm] $x^7 [/mm] + [mm] x^5 [/mm] + [mm] x^4 [/mm] + [mm] x^3 [/mm] + [mm] x^2 [/mm] + 1$ den Rest $x + 1$, womit es nicht im von [mm] $x^4 [/mm] + x + 1$ erzeugten Ideal liegt und damit nicht im Code. (So wuerde ich das als Mathematiker ausdrucken. Wenn es dir nichts sagt, kein Problem )
> Wie du schon gesagt hast, müsste bei einem gültigen
> Codewort das Fehlersyndrom/die Kontrollstellen 0000 sein -
> in diesem Fall ist es aber 0011, womit das Codewort nicht
> gültig ist.
Genau.
LG Felix
|
|
|
|
