Gray code is an alternate way to code numbers using 1s and 0s. Grey coding takes the same number of digits to encode the same size number -- but the patterns of 1s and 0s are different. There is one big advantage to using grey code: when you increment a grey code string, only one digit changes. When you increment a binary code string, the "carry" can ripple down the entire length of the string.

- Skill level:
- Moderate

### Other People Are Reading

## Instructions

- 1
Start with an algorithm for converting grey code to binary code. The standard algorithm is to work from left to right across the grey code string, writing the binary code string below it. Start by setting the entire binary string to 1s. Then set the leftmost digit of the binary string to be the same as the leftmost digit in the grey code string. Set the remaining digits in the binary string according to this rule: Set binary string position k to 0, if grey string position k is equal to binary string position k + 1, where position k + 1 is to the left of position k.

- 2
Develop a pseudo-code algorithm for the process. If the grey code is in array G and the binary code will be in array B, start by setting every element of B to 1. Then set the leftmost element of B to be equal to the leftmost element of G. Then you can go through the array and set each element of B correctly by asking if it is equal to the appropriate element of the G array. The pseudo-code would be: Set all of B to 1s, set B(max) to G(max), then possibly reset each element of B using the rule "if B(n) = G(n - 1) then set B(n - 1) to 0."

- 3
Write the C code for the pseudo-code algorithm. It would look like this:

begin for(k = 0; k less-than array_size;k++) B[k] = 1; B[array_size - 1] = G[array_size - 1]; for(k = array_size;k greater-than 0;k--) if (B[k] == G[k - 1]) B[k - 1] = 0 end.

Where G is the array that contains the gray code, B is the array that contains the binary code and the size of both arrays are the same: array_size.

#### Tips and warnings

- Write the example code as a function. It would look like this:
- int* G2B(int* B, int array_size) {int k; int* G[array_size]; for(k = 0; k less-than array_size;k++) B[k] = 1; B[array_size - 1] = G[array_size - 1]; for(k = array_size;k greater-than 0;k--) if (B[k] == G[k - 1]) B[k - 1] = 0; return G}
- This example assumes that the binary strings are in an array with the high order digits in the low numbered indexes. If it is the other way around the code would read:
- begin for(k = 0; k less-than array_size;k++) B[k] = 1; B[0] = G[0]; for(k = 0;k less-than 0;k++) if (B[k] == G[k + 1]) B[k + 1] = 0 end.