Beweis dass Gray Code existiert
Neue Frage »

25.04.2016, 14:56 igor789 Auf diesen Beitrag antworten »
Beweis dass Gray Code existiert
Hallo,

ich soll beweisen, dass s es für jedes
einen Gray Code für das Intervall 0 bis (2^n)-1 bei Codewortlänge n gibt.
Leider fällt mir kein geeigneter erster Schritt ein, den Beweis anzugehen.
Ich habe auch Probleme, die Aufgabenstellung in formale Sprache zu packen, um z.B. einen Induktionsbeweis zu führen.

Wäre für Hilfe sehr dankbarsmile

Danke im Vorraus
25.04.2016, 16:16 HAL 9000 Auf diesen Beitrag antworten »

Nun, das ist doch wohl hauptsächlich ein symboltechnisches Problem, einen entsprechenden Induktionsbeweis aufzuschreiben. Inhaltlich passiert doch nichts weiter als folgendes:

Im Induktionsschritt nimmt man den laut Induktionsvoraussetzung n-stelligen Code, ergänzt um die (n+1)-te Stelle mit Wert 0. Dann nimmt man nochmal denselben n-stelligen Code, diesmal ergänzt um die (n+1)-te Stelle mit Wert 1, aber in genau umgekehrter Reihenfolge, und "klebt" dies an den ersten Teil hinten dran - fertig ist der Gray-Code mit (n+1) Stellen.

In die Behauptung würde man zweckmäßigerweise nicht nur die Aussage aufnehmen, dass ein solcher -stelliger Code existiert, sondern dass die Codebits des ersten und letzten Codewortes jeweils gleich 0 sind, das "erleichtert" die Begründung im Induktionsschritt. Augenzwinkern
25.04.2016, 21:32 igor789 Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000


Im Induktionsschritt nimmt man den laut Induktionsvoraussetzung n-stelligen Code, ergänzt um die (n+1)-te Stelle mit Wert 0. Dann nimmt man nochmal denselben n-stelligen Code, diesmal ergänzt um die (n+1)-te Stelle mit Wert 1, aber in genau umgekehrter Reihenfolge, und "klebt" dies an den ersten Teil hinten dran - fertig ist der Gray-Code mit (n+1) Stellen.


Sorry, den Part verstehe ich nicht. Magst du mir das genauer erläutern?
25.04.2016, 21:39 HAL 9000 Auf diesen Beitrag antworten »

Höchstens am Beispiel.

Ausgangspunkt (Induktionsvoraussetzung) sei der Gray-Code für n=2:

00
01
11
10

Jetzt für n=2 wie beschrieben.

Zitat:
Original von HAL 9000
nimmt man den laut Induktionsvoraussetzung n-stelligen Code, ergänzt um die (n+1)-te Stelle mit Wert 0.

000
001
011
010

Zitat:
Original von HAL 9000
Dann nimmt man nochmal denselben n-stelligen Code, diesmal ergänzt um die (n+1)-te Stelle mit Wert 1, aber in genau umgekehrter Reihenfolge

110
111
101
100

Zitat:
Original von HAL 9000
und "klebt" dies an den ersten Teil hinten dran - fertig ist der Gray-Code mit (n+1) Stellen.

000
001
011
010
110
111
101
100
25.04.2016, 21:52 igor789 Auf diesen Beitrag antworten »

Danke für die Mühe, wirklich nett!

Habe das jetzt verstanden, ich denke ich kann mich an den Beweis wagen,

vielen Dank nochmal smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Beweis dass Gray Code existiert