0
\$\begingroup\$

I've been asked to complete the following 5 bit Gray code: enter image description here

I know how to generate a Gray code (create a mirror image, pad the original values with a 0 and the reflected part with a 1), but I'm not sure how to generate the Gray code when a portion of it has already been given to me. I can see that in the third row, the A column starts with a 1, so it probably reflects over the second row. Any hints on how I should approach the problem? Or am I not seeing something that I should be?

\$\endgroup\$
2
  • \$\begingroup\$ Gray codes are simply full hamiltonian cycles on N-dim hypercubes. A 3-dim cube is two 2-dim "cubes" (squares) connected at their vertices. A 4-dim hypercube is two 3-dim cubes connected at their vertices. A 5-dim hypercube (your case) is two 4-dim hypercubes connected again at their vertices. Complete the walk on one (N-1)-dim hypercube before going to the other. In your case, you can easily see that A and E have changed and therefore neither can determine which of the two 4-dim hypercubes is being walked first. So it must be B, C, or D. You can choose which, so there's more than one answer. \$\endgroup\$
    – jonk
    Commented Feb 10, 2019 at 6:26
  • \$\begingroup\$ You have 15 lines for a 5 bits code, which should be able to code 32 unique values. So, you can ignore one column completely. This exercise don't make sense for me. You can add a specific line (I will let you guess the values) to complete a symmetric bloc of 4, and then apply the reflecting method you are used to. That, or you can go wild, change one bit at each new line and check you did not used it before. After all you only have space for less than half of the possibilities... \$\endgroup\$
    – pserra
    Commented Feb 10, 2019 at 6:41

1 Answer 1

Reset to default
2
\$\begingroup\$

This is one way of doing it logically. Convert the gray code to binary code so you get to linear space. Add one, or some other number, then go back to gray code and insert it into the table.

Converting gray code to binary code can be done according to these boolean equations:

\$ B_4 = G_4 \\ B_3 = B_4\oplus G_3\\ B_2 = B_3\oplus G_2\\ B_1 = B_2\oplus G_1\\ B_0 = B_1\oplus G_0 \$

So let's do this for the last one you have so we can get to binary code.

\$ B_4 = 1 \\ B_3 = 1\oplus 1 = 0\\ B_2 = 0\oplus 1 = 1\\ B_1 = 1\oplus 1 = 0\\ B_0 = 0\oplus 1 = 1 \$

So the binary value is \$10101_2\$, which is \$21_{10}\$ in ordinary decimal. Let's increment it by 1 so we can get to our next gray code value. Adding one gives us \$10110_2=22_{10}\$. What we have here could be useful for incrementing the value again by 1 so we can get the next consecutive gray code. Or we could identify the white rows in the table with this information, and calculate the gray code with that information.

Converting binary code to gray code can be done according to these boolean equations:

\$ G_4 = B_4\\ G_3 = B_4 \oplus B_3\\ G_2 = B_3 \oplus B_2\\ G_1 = B_2 \oplus B_1\\ G_0 = B_1 \oplus B_0 \$

So let's do this for the last one you have so we can get to binary code.

\$ G_4 = 1\\ G_3 = 1 \oplus 0 = 1\\ G_2 = 0 \oplus 1 = 1\\ G_1 = 1 \oplus 1 = 0\\ G_0 = 1 \oplus 0 = 1 \$

So the next gray code is \$11101_2\$. The white space that I assume you are supposed to fill in are the numbers 26 to 29 in binary, meaning the gray code I've calculated won't help you. So I will leave the actual part of the homework to you.

Though I believe the easiest thing to do, realistically for you as a human, would be to simply make the 5 bit gray code table and identify the positions of the missing entries and fill them in accordingly.

Or another thing that is also easy to do is to just simply learn the pattern. The leftmost column is a copy of the binary system. The second to leftmost column is the same as leftmost binary column just half way up. The third to leftmost column is the same as second to leftmost binary column just 1/4th way moved up. And I presume you can see the pattern by now.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.