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.
Functions
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.
jandecaluwe 12/15/2012 7:44:17 PM User Rank Blogger
Re: Clear as a bug!
@aj1s "I read your other article. Sorry, but it is not useful to me other than as entertainment."
That's disappointing because I try to write things that are relevant.
"Virtually all of the responses are completely off-topic."
Absolutely right.
"Maybe that ought to be a hint."
I agree. I took it as a hint that currently, I don't really have an audience here for reference models (let alone for their robustness).
"I like your angle for promoting myhdl for its advantage of being a subset of a generic SW programming language. Unfortunately, you chose an (albeit interesting) example that is not at all applicable to HW design to make your point."
Wait a moment here - I didn't choose this example out of the blue at all. I responded to a reasonable suggestion to use this example because it is currently "hot" on APP (3 people working on HW solutions, myself not included). So I used this example to try to convey a message about reference models (in which I appear to have failed, that is correct.)
I don't understand what you mean with "not applicable to HW design". Of course, this particular application may seem simple spielerei but with just a little imagination I can make a direct connection with the things I am doing professionally (DSP and image processing applications).
I certainly don't understand how any characteristic of this example would prevent you from commenting on the way you do reference models currently. I notice I haven't heard anything about that so far.
"Who in their right mind would use anything other than a CPU (or maybe a GPU) to implement such a game?"
This statement I find rather surprizing. Again, this may just seem like a simple game, but to me the connection with industrial image processing is obvious. I'm constantly seeing image processing applications where a number of DSPs is replaced by a single FPGA, or mixed-signal ASICs where the image processing engine is embedded next to the analog functions.
Personally, I would never want to make such a strong statement about what is meaningful for hardware or not. For example, I admit that I found it very strange when I heard that FPGAs were used for financial trading. Similarly, I can perfectly imagine that FPGAs would be useful for scientific research on the characteristics of cellular automata.
"For example, can MyHDL abstract pipelining? Can it abstract HW interfaces? These are areas that are dreadfully needed to help raise the level of abstraction in HDL based design."
No, MyHDL doesn't do any of these things. It is not an RTL or HLS synthesis tool, but an event-driven hardware description language (like VHDL/Verilog) embedded in Python.
I read your other article. Sorry, but it is not useful to me other than as entertainment. Virtually all of the responses are completely off-topic. Maybe that ought to be a hint.
I like your angle for promoting myhdl for its advantage of being a subset of a generic SW programming language. Unfortunately, you chose an (albeit interesting) example that is not at all applicable to HW design to make your point (that HDLs don't make good SW programming languages?). Who in their right mind would use anything other than a CPU (or maybe a GPU) to implement such a game?
Given that most HDL simulators support PLIs to ordinary SW for reference models, myhdl needs to do something in HW better than the current crop of HDLs do. For example, can MyHDL abstract pipelining? Can it abstract HW interfaces? These are areas that are dreadfully needed to help raise the level of abstraction in HDL based design. We can only get so far if we always have to describe behavior of every register on every clock edge.
Don't forget, you are also competing against C-to-HDL synthesis tools that can (with help) translate untimed SW models to HW.
jandecaluwe 12/15/2012 1:27:03 PM User Rank Blogger
Re: Clear as a bug!
@a1js "I'm taking exception to the assertion that myhdl is better than existing HDLs based on the code you posted"
To be precise, the article makes the case for Python (the general purpose language) as a great way to write reference models, and points out that those models can be readily used in a MyHDL verification environment (because MyHDL is implemented as a Python package). It then asks the question how to do the equivalent with VHDL/Verilog. The response so far: one nice solution (by @josyb) for VHDL, and NO for Verilog.
"I want to know whether it is better for real-world examples."
Did you read my follow-up article "A reference model for cellular automata"? Still quite simple, but already closer to my own "real-life". In that article, I suggest that a VHDL or Verilog equivalent solution is unfeasible. (So far, there was zero response to that statement.) In other words: thanks to its Python heritage, there is fully contained MyHDL solution, but no equivalent VHDL or Verilog solution - you would need to bring in other tools/languages/methodologies. Do you think I am making some sense here? If so, could it be relevant to your type of work?
I'm taking exception to the assertion that myhdl is better than existing HDLs based on the code you posted (without the error checking, and thus creating a potentially fatal infinite loop), which is not a suitable example of real-world code, with real-world robustness. It matters little to me whether Myhdl is better for academic examples; I want to know whether it is better for real-world examples. Had the posted example included the necessary error checking, the comparison would be different (even if not the conclusion).
The example you posted is like going to buy a car, and thinking you're getting a really good deal, only to find out that it does not include the wheels, and they cost extra. Maybe its still a good deal after the cost of the wheels is included, maybe not, but the initial evaluation is flawed nonetheless.
If anything, I'm simply chiding you a little to include the robustness in your examples, so your audience can see what a robust, reusable solution looks like, no matter what HDL is used. If the robustness obscures the intended point of the example, then at least (in the original article) mention where additional robustness is needed for a deployable solution. Having worked with numerous recent college graduate new-hires, a basic understanding of what a reusable, deployable solution means is often missing until they learn the hard way. Perhaps we can make it a little easier for them to learn.
I am a huge fan of taking frequent, difficult problems and creating reusable, deployable functions/procedure/modules/etc. to solve them. But I also believe those solutions, since we don't know how they might be used, must be as bullet-proof as possible. The last thing we want is for a user of that solution to have to dive deeply into it to figure out what he did wrong when he called it. This is the essence of robust, reusable, deployable solutions.
That robustness, at least in VHDL, is often dismissed as needlessly requiring additional coding to satisfy. Trust me; after 20 years of VHDL design, the extra coding has saved far more time in debug that it took to type!
I think you do really good work raising many issues that slip by under the radar when people talk about HDLs and HDL based design. Keep up your good work!
jandecaluwe 12/13/2012 5:43:20 PM User Rank Blogger
Re: Clear as a bug!
@aj1s Not sure what you are still arguing about. I fully agree with you, and pointed out that my local code has an assertion that avoids the issue. If you have a better, more robust, "established" solution, please show it, that was the design challenge in this post.
Sure, nobody would intentionally ask for a gray code of length < 1. Nobody intentionally adds bugs to their code either. But somehow it happens nonetheless. And when it happens, finding the source of that bug is just as important as is writing the next module. If your UUT crashes, the most extensive self checking test bench is of little help.
If you are trying to illustrate how easy an algorithm is to implement in python (presumably in comparsion with VHDL, et al), don't leave out the robustness that makes it more than just an academic exercise. It may turn out that once the robustness is provided, the solution may not be any better than an established one.
jandecaluwe 12/13/2012 4:39:25 AM User Rank Blogger
Re: Clear as a bug!
@aj1s "Sure, the python solution is clear. It also has a bug. Hint: what happens if n < 1? (it's not pretty)"
Correct. The code as shown doesn't cater for gray codes with negative bit widths. I found that overkill for the article.
"VHDL lets you constrain the argument (or any signal/variable/port) to automatically prevent such a problem. How would you do that in python?"
First of all, for a case like this with recursion, I suspect VHDL will also depend on the run-time and not on the compiler to flag the issue.
In Python, one would use assert statements. Actually, my full code for this has the following assertion on the parameter to keep things reasonable:
assert 1 <= n <= 20
"I also fail to see how using '+' for concatenation is more clear. Does '1' + '1' = '10' or '11'?"
'11' because '+' for concatenation is standard Python for sequence types. I don't find this an issue, because everything is still strongly typed: you can do '1' + '1' ('11') or 1 + 1 (2) but not '1' + 1 (traceback exception.)
Sure, the python solution is clear. It also has a bug.
Hint: what happens if n < 1? (it's not pretty)
VHDL lets you constrain the argument (or any signal/variable/port) to automatically prevent such a problem. How would you do that in python? Would the solution still be as clear and concise?
The only thing better than a self checking testbench is a self checking solution!
I also fail to see how using '+' for concatenation is more clear. Does '1' + '1' = '10' or '11'?
Don't get me wrong, I kinda like your approach to myhdl, particularly arithmetic.
jandecaluwe 10/23/2012 6:22:09 PM User Rank Blogger
Re: Actually a VHDL function would be pretty nice too:
"Ok I ll carry on doing it the way everyone else does but I think you are mistaken in your idea of how difficult it is to do using the standard approach"
@JezmoSSL Actually, the standard approach for industrial projects is to use a reference model and a self-checking test bench. I am pretty confident you do it like that, and all I am asking is how you write it.
Re: Actually a VHDL function would be pretty nice too:
Ok I ll carry on doing it the way everyone else does but I think you are mistaken in your idea of how difficult it is to do using the standard approach, if there was a problem then it would have been raised, but nobody else seems to share your concerns
Here is an example of solving a hardware design problem by first developing an algorithm, and then using HDL language features to write code that resembles this algorithm as closely as possible.
Until a few weeks ago, I knew next to nothing about cellular automata. Therefore, my first step was to try to discover as much as possible as quickly as possible about this application domain.
VHDL and Verilog have served us exceptionally well, but they also have significant issues. In order to realize the full potential of HDL design, we need a better HDL. In this blog, the creator of MyHDL -- Jan Decaluwe -- considers the concept of signal assignments.
To save this item to your list of favorite All Programmable Planet content so you can find it later in your Profile page, click the "Save It" button next to the item.
If you found this interesting or useful, please use the links to the services below to share it with other readers. You will need a free account with each service to share an item via that service.
Tweet This
