Gray-Code

02.12.2013, 13:59

Wess

Gray-Code

Hallo liebe Mathe-Boardler!

Ich stecke bei einem Beispiel, bzw. ich habe einige Vermutungen, die ich einfach nicht schaffe, so aufzuschreiben, wie ich mir das denke, und ich bin mir auch nicht sicher, ob ich mir das denn korrekt überlegt habe!

Es geht um folgendes:

Für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ sei $\begin{eqnarray*} L_n \end{eqnarray*}$ der binäre gespiegelte Gray-Code der Länge n.

Zeigen Sie für $\begin{eqnarray*} 0 \leq k \leq n \end{eqnarray*}$ : Der erste Vektor in $\begin{eqnarray*} L_n \end{eqnarray*}$ vom Gewicht k ist gleich
$\begin{eqnarray*} 1^k 0^{n-k} \end{eqnarray*}$ . Der letze Vektor in $\begin{eqnarray*} L_n \end{eqnarray*}$ vom Gewicht k ist gleich $\begin{eqnarray*} 1^{k-1} 0^{n-k}1 \end{eqnarray*}$ .

Zum Beweis, dass der erste Vektor die gewünschte Form hat:

Ich würde dies gern mit Induktion über k zeigen.

Induktionsverankerung: $\begin{eqnarray*} k=1 \end{eqnarray*}$ dann ist der erste Vektor vom Gewicht 1 gleich $\begin{eqnarray*} 10^{n-1} \end{eqnarray*}$ , da dies sowieso der zweite Vektor im Code ist, und der erste ist $\begin{eqnarray*} 0^n \end{eqnarray*}$ .

Gelte die Aussage nun für alle $\begin{eqnarray*} l\leq k \end{eqnarray*}$ , z.z. Sie gilt für $\begin{eqnarray*} k+1 \end{eqnarray*}$ :

Der erste Vektor $\begin{eqnarray*} f_j \end{eqnarray*}$ vom Gewicht k ist gleich $\begin{eqnarray*} 1^k 0^{n-k} \end{eqnarray*}$ .

So, und hier stockt es leider schon(ich weiß, so viel hab ich leider noch nicht allein geschafft =( ).
Ich verstehe nicht so ganz, wie ich aus dem Induktionsanfang nun wirklich was machen kann...
Vielleicht kann man irgendwie direkt beide Aussagen mit einer Induktion beweisen, sodass man ausnützen kann, dass man weiß, wie der letzte und der erste Vektor vom Gewicht k aussieht? Oder dass man den Beweis in zwei Teile aufteilt? Also einmal wenn der erste Vektor im nicht gespiegelten Teil liegt, und einmal wenn er im gespiegelten Teil liegt?

Für Anschubser, Tipps, oder Literatur, in die ich mich einlesen könnte, wäre ich sehr sehr dankbar!
Für mich im ersten Semester sind einige Dinge noch sehr unklar, wie ich manches am besten zeige :S!

mfg
Wess

02.12.2013, 17:14

Wess

Auf diesen Beitrag antworten »

RE: Gray-Code
Sollte ich eine Lückenhafte Angabe gegeben haben, oder sollte ich komplett am falschen Dampfer sein, dann wäre ich trotzdem sehr froh über Rückmeldungen!

Ich würde dieses Thema gerne verstehen, bzw. verstehen, wie man Beweise, die in diese Richtung gehen, am besten angeht!

mfg

02.12.2013, 23:25

jimmyt

Auf diesen Beitrag antworten »

Hi,

generell sollte man den Induktionanfang mit "echten" Zahlen für n und k machen.

Für $\begin{eqnarray*} L_{n+1}=(L_n*0) \cup \overline L_{n}*1) \end{eqnarray*}$ ein Vorschlag für die Herangehensweise:

Vollständige Induktion über k:

Induktionanfang
(I.A.) Induktionanker:
n=1, k=0: erste Vektor: $\begin{eqnarray*} 1^00^{1-0} ~=~ 0 \end{eqnarray*}$ , letzte Vektor: $\begin{eqnarray*} 1^{0-1}0^{1-0}1 ~=~ 0 \quad \checkmark \end{eqnarray*}$
n=1, k=1: erste Vektor: $\begin{eqnarray*} 1^10^{1-1} ~=~ 1 \end{eqnarray*}$ , letzte Vektor: $\begin{eqnarray*} 1^{1-1}0^{1-1}1 ~=~ 1 \quad \checkmark \end{eqnarray*}$
n=2, k=0: erste Vektor: $\begin{eqnarray*} 1^00^{2-0} ~=~ 00 \end{eqnarray*}$ , letzte Vektor: $\begin{eqnarray*} 1^{0-1}0^{2-0}1 ~=~ 00 \quad \checkmark \end{eqnarray*}$
n=2, k=1: erste Vektor: $\begin{eqnarray*} 1^10^{2-1} ~=~ 10 \end{eqnarray*}$ , letzte Vektor: $\begin{eqnarray*} 1^{1-1}0^{2-1}1 ~=~ 01 \quad \checkmark \end{eqnarray*}$

Induktionschluß
I.V.) Induktionvoraussetzung:
für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ und ein $\begin{eqnarray*} 0 \leq k \leq n \end{eqnarray*}$ wird angenommen, daß gilt:
erster Vektor in $\begin{eqnarray*} L_n \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} k: \quad 1^k0^{n-k} \end{eqnarray*}$
letzter Vektor in $\begin{eqnarray*} L_n \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} k: \quad 1^{k-1}0^{n-k}1 \end{eqnarray*}$

(I.B.) Induktionbehauptung:
für das Nachfolgeelement k+1 muß gelten:
erster Vektor in $\begin{eqnarray*} L_{n} \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} k+1: \quad 1^{k+1}0^{n-k+1} \end{eqnarray*}$
letzter Vektor in $\begin{eqnarray*} L_{n} \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} k+1: \quad 1^{k}0^{n-k+1}1 \end{eqnarray*}$

(I.S.) Induktionschritt:
aus (I.V.) muß (I.B.) folgen:
k -> k+1:
erster Vektor: $\begin{eqnarray*} 1^{k+1}0^{n-k+1} ~=~ \dots \end{eqnarray*}$
letzter Vektor: $\begin{eqnarray*} 1^{k}0^{n-k+1}1 ~=~ \dots \end{eqnarray*}$
Ich habe jetzt mehrere Induktionanker gewählt, einfach weil du mit n und k gleich 2 unterschiedliche Variablen hast. smile

04.12.2013, 13:58

Wess

Auf diesen Beitrag antworten »

Meine Ideen bzgl dem Induktionsschluss wären nun:

$\begin{eqnarray*} 1^{k+1}0^{n-k+1} \end{eqnarray*}$ ist ein Vektor in der ersten Hälfte des Gray-Codes, da die letzte Stelle eine 0 ist=>der Vektor $\begin{eqnarray*} 1^{k+1}0^{n-k} \end{eqnarray*}$ ist aber der erste Vektor vom Gewicht $\begin{eqnarray*} k+1 \end{eqnarray*}$ in der vorhergehenden Liste nach I.V., deshalb muss $\begin{eqnarray*} 1^{k+1}0^{n-k+1} \end{eqnarray*}$ der erste Vektor vom Gewicht $\begin{eqnarray*} k+1 \end{eqnarray*}$ sein.

der Vektor $\begin{eqnarray*} 1^k0^{n-k+1}1 \end{eqnarray*}$ steht in der zweiten Hälfte des Codes, da die letzte Ziffer eine 1 ist, d.h. in der gespiegelten Hälfte.
Der Vektor $\begin{eqnarray*} 1^k0^{n-k+1} \end{eqnarray*}$ ist nun der erste vom Gewicht k in der vorhergehenden Liste, d.h. dann dass er in verkehrter Reihenfolge der letzte sein muss. D.h. der Vektor $\begin{eqnarray*} 1^k0^{n-k+1}1 \end{eqnarray*}$ muss dann der letzte vom Gewicht $\begin{eqnarray*} k+1 \end{eqnarray*}$ sein.

Macht das so Sinn?

Danke nochmal! Big Laugh

04.12.2013, 16:04

jimmyt

Auf diesen Beitrag antworten »

Die Ideen klingen gut.
Dann mußt du aber die I.V. anders formulieren als ich es gepostet habe.

Zitat:

Original von mir
...
I.V.) Induktionvoraussetzung:
für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ und ein $\begin{eqnarray*} 0 \leq k \leq n \end{eqnarray*}$ wird angenommen, daß gilt:
erster Vektor in $\begin{eqnarray*} \textcolor{red}{L_n} \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} \textcolor{red}{k: \quad 1^k0^{n-k}} \end{eqnarray*}$
letzter Vektor in $\begin{eqnarray*} \textcolor{red}{L_n} \end{eqnarray*}$ mit Gewicht $\begin{eqnarray*} \textcolor{red}{k: \quad 1^{k-1}0^{n-k}1} \end{eqnarray*}$
...

Anmerkungen:

Zitat:

Original von Wess
...
$\begin{eqnarray*} 1^{k+1}0^{n-k+1} \end{eqnarray*}$ ist ein Vektor in der ersten Hälfte des Gray-Codes, da die letzte Stelle eine 0 ist
...
der Vektor $\begin{eqnarray*} 1^k0^{n-k+1}1 \end{eqnarray*}$ steht in der zweiten Hälfte des Codes, da die letzte Ziffer eine 1 ist, d.h. in der gespiegelten Hälfte.
...

Das stimmt. Freude

Zitat:

Original von Wess
... =>der Vektor $\begin{eqnarray*} \textcolor{red}{1^{k+1}0^{n-k}} \end{eqnarray*}$ ist aber der erste Vektor vom Gewicht $\begin{eqnarray*} \textcolor{red}{k+1} \end{eqnarray*}$ in der vorhergehenden Liste nach I.V., ...

Vergleiche mal mit der I.V. smile

Oder, wie schon gesagt, du formulierst sie anders. Das geht auch.

Zitat:

Original von Wess
... Der Vektor $\begin{eqnarray*} 1^k0^{n-\textcolor{red}{k+1}} \end{eqnarray*}$ ist nun der erste vom Gewicht k in der vorhergehenden Liste, d.h. dann dass er in verkehrter Reihenfolge der letzte sein muss. ...

Gegenbeispiel: L_3: {000, 100, 110, 010, 011, 111, 101, 001} und k=2:

erster Vektor: $\begin{eqnarray*} 1^k0^{n-k+1} ~=~ 1^20^{3-2+1} ~=~ 110 \quad \text{Gewicht 2 - korrekt!} \end{eqnarray*}$
letzter Vektor: $\begin{eqnarray*} 0^{n-k+1}1^k ~=~ 0^{3-2+1}1^2 ~=~ \textcolor{red}{001} \quad \text{Gewicht 1 - falsch!} \end{eqnarray*}$

Tipp:
Schau dir mal den I.S. an, soweit ich ihn gepostet habe. Was steckt denn da drin?
Wie gesagt: es wird angenommen, daß die I.V. stimmt, und daraus muß die I.B. folgen.

Neue Frage »

Antworten »

Gray-Code

Verwandte Themen