Gray-Code

[Felix G]

Hallo Leute,

ich suche nach einem effizienten Algorithmus, mit dem ich einen (geringfügig modifizierten) 9...11-Bit Gray-Code decodieren kann.

Gruß,
Felix


PS:
"geringfügig modifiziert" = so verschoben daß er mit 11111...1 anfängt
(aber das dürfte ja bei der Decodierung keine Rolle spielen)

[SprinterSB]

Die Frage ist, was "Effizienz" sein soll...?

-1- Laufzeit
-2- Speicherplatz
-3- Verständlichkeit / Implementierungszeit

Für -1- und -3- einfach ne Tabelle anlegen und da rauslesen, ist aber mies für -2-.

EIgentlich sollte doch was rekursives gehen für -2-, also Zurückführen des n-Gray-Code auf n-1-Gray-Code.

[jeffrey]

Hallo,
wie komme ich eigentlich einfach auf eine Graycode mit n-bit? Meistens findet man nur beispiele für 3 oder 4-bit. Wie komme ich auf einen Graycode mit 10-bit?
MfG jeffrey

[SprinterSB]

SChau mal im Wiki unter "Graycode"

[Felix G]

@SprinterSB
Naja, effizient im Sinne von "einfach"...

ein paar mathematische Formeln mit denen ich wieder an die Dezimalzahlen komme.

Irgendwie habe ich da grad eine Denkblockade, denn ich kann zwar problemlos einen Gray-Code aufschreiben (mit 4, 5 oder egal wieviel Bit, solange es noch aufs Blatt passt), bin aber nicht in der Lage die Geschichte dann wieder ins Dezimalsystem umzurechnen.


Speicherplatz ist übrigens kein Problem, da das Programm auf einem PC laufen wird, aber eine Tabelle ist mir irgendwie zu unflexibel.


edit:
hab grad ins Wiki geschaut...

111 Gray = 7-3+1 = 7-(3-1) = 5ganz genau sowas suche ich, wie kommt man da drauf?

[SprinterSB]

Achso, ich dachte, du brauchst die andere Richtung...

Hab grad aml was gehackt und das scheint es zu tun. Frag nicht, wie ich drauf komme, ist mathematische Intuition... *fg*



import java.io.*;

public class Gray
{
public static void main (String[] args)
{
System.out.println ("Hallo Welt!");

int n = 2;

try
{
if (args.length >= 1)
n = Integer.parseInt (args[0]);
}
catch (Exception ex) {}

System.out.println ("n = " + n);

for (int i=0; i < (1 << n); i++)
{
int dec = 0;
int ii = i;
for (int b = n-1; b >= 0; b--)
{
if (0 != (ii & (1 << b)))
{
dec |= (1 << b);
ii ^= 0xffffff;
}
}
System.out.println ("[" + i + "] -> " + dec);
}
}
}

i Läuft von 0 bis 2^n und wird Gray-decodiert. Scheint zu stimmen :-)

In C sieht's dann genauso aus.


D:\java\sources>java -cp . Gray 4
Hallo Welt!
n = 4
[0] -> 0
[1] -> 1
[2] -> 3
[3] -> 2
[4] -> 6
[5] -> 7
[6] -> 5
[7] -> 4
[8] -> 12
[9] -> 13
[10] -> 15
[11] -> 14
[12] -> 10
[13] -> 11
[14] -> 9
[15] -> 8

[robocat]

hab auch gebastelt, komme aber mit meiner lösung zu spät. ausserdem ist sie nicht so elegant, und ob es funktioniert, konnte ich nur mit den wiki-beispielen testen.. -.-

#include <stdio.h>
#include <conio.h> // nur fuer getch

int main(void)
{
unsigned int i,pos=1,ergebnis=0,x=15;
printf("Wert x=%d wird aufgeloest:\n",x);
for(i=0;i<32;i++)
{
int v=((x&(1<<(31-i)))<<1);
if(v)
{
v--;
if(pos)ergebnis+=v;
else ergebnis-=v;
printf("%d=%d\n",i,v);
pos=!pos;
}
}
printf("ergebnis:%d\n",ergebnis);
getch();
return 0;
}

EDIT @sprinter-code:
binär 1111 ist doch 15, da bekommst du 8 raus, in der wiki steht 10..
stimmt die wiki nicht oder dein code? *fragend guck*

[Felix G]

Vielen Dank euch beiden, ich werde das mal ausgiebig testen :)

[SprinterSB]

@robocat: 15 (1111) wird abgebildet auf 8 (weiß-schwarz-schwarz=1000), wie im Wiki :-)

Ist wie gesagt die andere Richtung von dem, was Felix gesucht hat. Also x->gray(x) und nicht gray(x)->x

[robocat]

oh. ja. ich weiß nicht ob ichs so ganz versteh, aber ich bin auch schon etwas müde. ich glaube zu verstehen, dass ich die wandlung zum graycode nicht berücksichtigt habe.
werde mir das morgen nochmal zu gemüte führen. nix für ungut.
danke sprinterSB

[Felix G]

Ich konnte zwar noch nicht testen ob es geht, aber dank dem Code und dem Wiki-Artikel weiss ich jetzt wenigstens wie man das umrechnen muss.



int graytodec(int x, int n)
{
int i = 0;
int tmp = 0;

while(i < n)
if((x & (1 << i++)) != 0)
tmp = ((1 << i) - 1) - tmp;

return tmp;
}

Ob das so funktioniert weiss ich natürlich erst wenn ich es richtig getestet habe.
Ich bin aber recht zuversichtlich, da ich nach diesem Schema gerade schon einen Wert von Hand korrekt ausrechnen konnte.


Das muss ich nurnoch für "meinen" Gray-Code anpassen und in die Matlab-Skriptsprache übersetzen, aber das klappt dann schon.