Max has written an excellent series of in-depth articles about Gray codes. In Part 2, he presents an algorithm to create a Gray code of width 'n' out of an existing one of width 'n-1.' Commencing with a gray code represented as a table, the steps are as follows:
- Create a mirror image of the existing Gray code and place this mirror image below the original one
- Prefix the original values with 0s and the mirrored values with 1s
Let's try this out in a Python interpreter. I will represent a Gray code as a list of bit strings and rearrange the steps a little. Let's start with a gray code of width 2:
Prefixing the original values with 0s can be done like this:
Did you see what happened? You can use '+' to concatenate strings. Also, you can iterate right inside list syntax. Let's do this once again, this time prefixing with 1s:
These values have to be mirrored. That's easy enough:
Finally, we add the two newly created lists:
Et voilą, we now have the Gray code of width 3.
We can make the steps above reusable by wrapping them into a recursive function that we put in a file as follows:
Now, let's import the file back into the interpreter to try it out:
Don't you agree that the "gray_code" function code is beautiful? In my opinion, it is almost clearer than an explanation of the algorithm in words. This is where Python excels.
Reference models in Python
What I've presented thus far is quite relevant for HDL design. Suppose you want to verify a Gray code counter design of a realistic width. Looking at waveforms is not going to "cut it." Instead, you want a self-checking testbench that gives you a green light for functional correctness. In this way, you can easily experiment with alternative implementations.
A self-checking testbench captures the behavior of the design under test and compares it to the behavior predicted by a reference model. In turn, a reference model describes the essential behavior of a system at the highest possible level, without implementation concerns. Our "gray_code" function is an excellent example. It can be used directly in a self-checking MyHDL test bench for Gray code counters.
The concept of a reference model is a powerful technique in any HDL verification flow. Therefore, let's consider how this example would translate to Verilog or VHDL. Both HDLs have support for "programming language" features, so of course it should be possible to write a Gray code reference model in them. However, I suspect that the process would be far less straightforward and the result far less readable than in Python. By going through the experience, some of you may start appreciating the value of Python in a verification flow (if you are not using Python already).
Of course, you shouldn't just take my word for it, so why don't we make a little modeling contest out of this? The spec is simple: Given a width 'n,' write a reference model in Verilog or VHDL that returns the corresponding Gray code in a representation of your choice. Hardware considerations are not important -- just use the language to make it as readable as possible and post your implementation as a comment to this blog. I very much look forward to seeing some interesting solutions.