Gray code
Allan Bruce
I can do it if I create the whole lot of the numbers before, e.g. If I am
using 3 bits and I want to conver 100 to gray code I can do this
000 000 (0)
001 001 (1)
010 011 (2)
011 010 (3)
100 110 (4)
But this is very slow as I will be requiring 32 bit gray codes. What I
would like is a function that would do the above example by calling
gray_convert(3, 4)
which is use 3 bits and the 4th one or even better
gray_convert("100")
Where the function recognisese the number of bits being used?
Another small question about gray codes, I have defined a fixed point number
system where the first 16 bits represent the integer part of the number and
the remaining 16 bits represent the fraction part. so 8.5 would be
0000 0000 0000 1000 1000 0000 0000 0000 (with super exaggerated spacing
for readability!)
Anyway, can I treat this as a /normal/ binary number, and just use gray code
conversion as normal? (It is being used for a genetic algorthm if that makes
any difference)
Thanks
Allan
Simon.
and on Fri, 10 Jan 2003 21:13:46 -0000, "Allan Bruce"
<all...@dsl.pipex.com> wrote this wisdom:
There is a function available in numerical recipies for C or fortran
which tells you how. The books is available to download and has
examples of code for you to follow.
Do google serach on Numerical Recipies in C
(Sorry don't know link off hand)
--
Simon.
'Be Seeing You.
Who is number one?
KAR 120C - Nice motor.
Registered Linux User #300464
Jos A. Horsmeier
> Does anybody know how to convert a single gray code number?
> I can do it if I create the whole lot of the numbers before, e.g. If I am
> using 3 bits and I want to conver 100 to gray code I can do this
> 000 000 (0)
> 001 001 (1)
> 010 011 (2)
> 011 010 (3)
> 100 110 (4)
>
> But this is very slow as I will be requiring 32 bit gray codes. What I
> would like is a function that would do the above example by calling
> gray_convert(3, 4)
> which is use 3 bits and the 4th one or even better
> gray_convert("100")
> Where the function recognisese the number of bits being used?
Given n > 0 bits of accuracy and an index i, the following snippet
gives you the n-th Gray code:
(i^(i>>1))&((1<<n)-1)
kind regards,
Jos
Thad Smith
> Does anybody know how to convert a single gray code number?
unsigned gray_to_bin (unsigned gray) {
int bin;
for (bin=0; gray; gray >>= 1) bin ^= gray;
return bin;
}
unsigned bin_to_gray (unsigned bin) {
return bin ^ (bin >> 1);
}
> Another small question about gray codes, I have defined a fixed point number
> system where the first 16 bits represent the integer part of the number and
> the remaining 16 bits represent the fraction part. so 8.5 would be
> 0000 0000 0000 1000 1000 0000 0000 0000 (with super exaggerated spacing
> for readability!)
> Anyway, can I treat this as a /normal/ binary number, and just use gray code
> conversion as normal? (It is being used for a genetic algorthm if that makes
> any difference)
Yes.
Thad
Allan Bruce
Here it is if anyone wants a gander (please remember I am new to c, so dont
laugh too much!)
Any helpful comments appreciated
Allan
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#define RAND (rand()%(time(&now)%1024))
void cross_strings(char *string1, char*string2, char *string3, char
*string4);
double decode(char *string);
double eval_fit(double x);
void gray_encode(char *norm_ptr, char *gray_ptr);
void gray_decode(char *norm_ptr, char *gray_ptr);
void rand_mutate(char *string);
void inversion(char *string);
void rotation(char *string);
void deletion(char *string);
void insertion(char *string);
char random_bit(void);
char xor(char x, char y);
char not(char x);
int main(void){
/* set char arrays as 33 bits, as having a 32bit string with \0 at end
*/
char str1[33], str2[33], str3[33], str4[33], tempc[33];
char *string1, *string2, *string3, *string4;
double value1, value2, value3, value4, fit1, fit2, fit3, fit4, temp;
int i, conv=0;
time_t now; /* Used to get time from processor */
/* Execute a random number of time cycles based on time
Should now have slightly better random numbers */
for (i=0; i<time(&now)%65536; i++) rand();
/* Set the string pointers to the strings*/
string1=str1; string2=str2; string3=str3; string4=str4;
strcpy(string1,"00000000001011010110101011011010"); /* String is 32-bits
and then \0 */
strcpy(string2,"10000100011010110011001011010010");
printf("Press <ctrl>+c to quit the program\n");
while (conv==0){
/* Cross breed */
cross_strings(string1, string2, string3, string4);
/* Evaluate the vlaue of and fitness of individuals */
value1=decode(string1); value2=decode(string2);
value3=decode(string3); value4=decode(string4);
fit1=eval_fit(value1); fit2=eval_fit(value2); fit3=eval_fit(value3);
fit4=eval_fit(value4);
/* Sort them so str1 is the best down to str4 the worst */
for (i=0; i<4; i++){
if (fit4<fit3){
temp=fit4; fit4=fit3; fit3=temp;
strcpy(tempc, string4); strcpy(string4,
string3); strcpy(string3, tempc);
temp=value4; value4=value3; value3=temp;
}
if (fit3<fit2){
temp=fit3; fit3=fit2; fit2=temp;
strcpy(tempc, string3); strcpy(string3,
string2); strcpy(string2, tempc);
temp=value3; value3=value2; value2=temp;
}
if (fit2<fit1){
temp=fit2; fit2=fit1; fit1=temp;
strcpy(tempc, string2); strcpy(string2,
string1); strcpy(string1, tempc);
temp=value2; value2=value1; value1=temp;
}
}
printf("Best Fitness = %8g ", fit1); /* Display the best fitness
so far */
for (i=0; i<50; i++){printf("\b");}
fflush(stdout); /* Reset back to the start of the line, need both
for multi-platform */
}/*end main while */
printf("Optimal value at %g, value of the function = %g\n", value1,
fit1);
return 0;
}
void cross_strings(char *string1, char*string2, char *string3, char
*string4){
/* This function takes two strings (1 & 2), converts them to gray code
and then uses random crossovers to produce offspring (also other
genetic
properties) before converting the strings back to normal binary */
int cross1, cross2;
int i;
char grayed1[33], grayed2[33], grayed3[33], grayed4[33];
char *gray1_ptr, *gray2_ptr, *gray3_ptr, *gray4_ptr;
gray1_ptr=grayed1; gray2_ptr=grayed2; gray3_ptr=grayed3;
gray4_ptr=grayed4;
/* Encode our two fit individuals to gray code. Preparation for breeding
! */
gray_encode(string1, gray1_ptr); gray_encode(string2, gray2_ptr);
strcpy(string1, gray1_ptr); strcpy(string2, gray2_ptr);
/* Find 2 unique random numbers between 0 and 31, with cross1<cross2 */
cross1=rand()%32; cross2=cross1;
while (cross2==cross1) cross2=rand()%32;
if (cross2<cross1){i=cross2; cross2=cross1; cross1=i;}
/* Cross the parents to add 2 new offspring to the gene pool */
for (i=0; i<32; i++){
if ((i<cross1)||(i>=cross2)){ /* Between the cross points, swap the
bits */
string3[i]=string1[i];
string4[i]=string2[i];
}
else{
string3[i]=string2[i];
string4[i]=string1[i];
}
}
/* Include random mutation - much more frequent than in nature */
if (rand()%5==3){rand_mutate(string3); rand_mutate(string4);}
if (rand()%20==7){inversion(string3); inversion(string4);}
if (rand()%30==11){rotation(string3); rotation(string4);}
if (rand()%33==2){deletion(string3); deletion(string4);}
if (rand()%37==23){insertion(string3); insertion(string4);}
string3[32]='\0'; string4[32]='\0';/* Termintate the strings */
strcpy(gray3_ptr,string3); strcpy(gray4_ptr,string4);/* Make the
gray_codes the cross breeded versions */
/* Decode back to normal binary */
gray_decode(gray1_ptr, string1); gray_decode(gray2_ptr, string2);
gray_decode(gray3_ptr, string3); gray_decode(gray4_ptr, string4);
}
double decode(char *string)
{
/* This function takes in a character array of 32 bits representing binary
This number will then be decode and returned as a double */
double vtr=0;
int position, neg=0;
double num=0;
char temp[33];
/* First need to check and see if the number is -ve
If it is then use 2s complement to find the value */
if (string[0]=='1'){
/* if the first bit is set then we have a -ve number */
neg=1;
/* Therefore flip each bit - will add 1 later for 2s compliment*/
for (position=0; position<32; position++){
if (string[position]=='0')
temp[position]='1';
else
temp[position]='0';
//printf("%d ", position);
}
}
else
strcpy(temp, string);
/* Evaluate the abs() value of the number to decode */
for (position=0; position<32; position++) {
if(temp[position]=='1') num=1;
else num=0;
vtr+=(double)(num*pow(2, 15-position));
}
if (neg==1)
vtr=-(vtr+1);
return vtr;
}
double eval_fit(double x){
return (pow(x,4) -8*pow(x, 2) +x);
/* best should be at -18ish but local min at -14ish */
}
void gray_encode(char *norm_ptr, char *gray_ptr){
int bits=32, position;
/* (i^(i>>1))&((1<<n)-1) is a better way */
gray_ptr[0]=norm_ptr[0];
for (position=1; position<bits; position++)
gray_ptr[position]=xor(norm_ptr[position-1], norm_ptr[position]);
gray_ptr[bits]='\0';
}
void gray_decode(char *gray_ptr, char *norm_ptr){
int bits=32, position;
norm_ptr[0]=gray_ptr[0];
for (position=1; position<bits; position++)
norm_ptr[position]=xor(norm_ptr[position-1], gray_ptr[position]);
norm_ptr[bits]='\0';
}
void rand_mutate(char *string){
int i;
i=rand()%32;
if (string[i]=='0')
string[i]='1';
else
string[i]='0';
}
void inversion(char *string){
int cross1, cross2, position, i;
/* Find 2 unique random numbers between 0 and 31, with cross1<cross2 */
cross1=rand()%32; cross2=cross1;
while (cross2==cross1) cross2=rand()%32;
if (cross2<cross1){i=cross2; cross2=cross1; cross1=i;}
for(position=0; position<32; position++){
if ((position<cross1)||(position>cross2))
string[position]=string[position];
else
string[position]=not(string[position]);
}
string[32]='\0';
}
void rotation(char *string){
int cross1, cross2, position, i,j;
char temp[33];
time_t now;
/* Find 2 unique random numbers between 0 and 31, with cross1<cross2 */
cross1=RAND%32; cross2=cross1;
while (cross2==cross1) cross2=RAND%32;
if (cross2<cross1){i=cross2; cross2=cross1; cross1=i;}
strcpy(temp, string);
for (i=cross1, j=cross2; i<=cross2; i++, j--)
temp[i]=string[j];
temp[32]='\0';
strcpy(string,temp);
}
void deletion(char *string){
int cross1, cross2, position, i, j;
time_t now;
/* Find 2 unique random numbers between 0 and 31, with cross1<cross2 */
cross1=RAND%32; cross2=cross1;
while (cross2==cross1) cross2=RAND%32;
if (cross2<cross1){i=cross2; cross2=cross1; cross1=i;}
for (j=cross2, i=cross1; j<32; j++, i++)
string[i]=string[j];
for (i=cross2; i<32; i++)
string[i]=random_bit();
}
void insertion(char *string){
int cross1, cross2, position, i, j;
time_t now;
/* Find 2 unique random numbers between 0 and 31, with cross1<cross2 */
cross1=RAND%32; cross2=cross1;
while (cross2==cross1) cross2=RAND%32;
if (cross2<cross1){i=cross2; cross2=cross1; cross1=i;}
/* printf("\nCrossing at %d and %d\n%s\n", cross1, cross2, string);
for(i=0; i<cross1; i++)printf(" ");
printf("I");
for(i=cross1+1; i<cross2; i++) printf(" ");
printf("I\n");*/
for (j=cross2,i=cross1 ;j>32; j++,i++)
string[j]=string[i];
for (i=cross1; i<cross2; i++)
string[i]=random_bit();
//printf("%s", string);
}
char random_bit(void){
time_t now;
return (char)('0'+rand()%2);
}
char xor(char x, char y){
char result;
if (x=='0')
result=y;
else
result=not(y);
return result;
}
char not(char x){
char result;
if (x=='0')
result='1';
else
result='0';
return result;
}