These Int's Are Made for Countin'   01-Mar-2009

Introduction

This is an essay about elementary arithmetic with integers. In other words, it talks about the basic math operations that we learned in school and routinely use in daily life, such as counting and addition.

You must be wondering how this can be an interesting subject. The answer is that we will discuss these matters in the context of a specific engineering discipline: digital design using hardware description languages (HDLs). As we shall discover, describing arithmetic in mainstream HDLs, such as Verilog and VHDL, is anything but simple. It is in fact complicated and confusing.

Usually, the complexity of arithmetic in HDL-based design is taken for granted. Engineers seem to think that the complexity is a natural byproduct of hardware descriptions. This essay defends the thesis that the complexity is neither useful nor unavoidable. It shows what is wrong with the traditional approach, and proposes a better one.

Perspective

Since ancient times, natural numbers have been used to represent the size of a set of items. Techniques were developed to keep track of set sizes in various applications. This is what we call arithmetic.

The most straightforward way to determine the size of a set is by counting the items. This is a process of repeatedly incrementing a number until all of the items have been addressed. When the sizes of two subsets are known, a more efficient direct method is available; addition. Some applications require the inverse operations; counting down or subtraction.

At some point, people realized that certain problems become easier to solve by introducing a more abstract number type into arithmetic; the negative numbers. Together with zero and the natural numbers, these form the integers.

Of course, the history of arithmetic did not stop with integers, but this brief overview is sufficient for our purposes. In this essay, we are discussing HDL code that can be synthesized into a hardware implementation. Synthesis puts significant constraints on the kind of code that can be written. In particular, arithmetic is limited to integer arithmetic.

A natural consequence of the synthesis limitations is that integer arithmetic is omnipresent in HDL-based design. To make a problem suitable for implementation, it is often transformed and simplified so that integer arithmetic can be employed. Hardware designers talk about counters, incrementers, decrementers, adders and subtracters, which are all hardware implementations of basic integer arithmetic operators.

Because of its importance, one would expect that describing integer arithmetic in HDLs is elegant and straightforward. The reality is rather disappointing.

Integer arithmetic in Verilog and VHDL

A demonstrator example

I will explain my viewpoint by using a simple example of integer addition. Suppose we add two numbers, a and b, where a is a positive integer between 0 and 7 and b is an integer between -8 and 7. The result c is therefore an integer between -8 and 14.

The goal is to write synthesizable HDL code that adds a to b and assigns the result to c. Then we can use an HDL simulator to check the result for certain input values. For example, when a == 7 and b == -2, we expect the following result:

  7 + -2 = 5

Verilog

In a Verilog description, the first task is to declare the objects:

  reg [2:0] a;
  reg signed [3:0] b;
  reg signed [4:0] c;

Note that we use the minimal bit widths required to represent the range of possible values. Furthermore, note that reg a is unsigned, which is the default in Verilog, while regs b and c are signed because they need to be able to represent negative values.

Ideally, we would like to calculate the addition, somewhere in the code, as follows:

  c <= a + b

With some additional test-bench code, we can use a Verilog simulator to check the result. Doing this with the values mentioned earlier gives:

  7 + -2 = -11

You read that correctly; your Verilog simulator tells you that the result is -11 instead of 5.

At this point, a Verilog guru might feel an irresistible urge to explain this result. Actually, though the rules are awkward, even I could explain it to you, but I won't. Explaining this would be beside the point, which is that this is not how integers are supposed to behave.

Beyond explanations, Verilog die-hards might insist that nothing is wrong here. They might argue that this is simply how Verilog signed and unsigned regs behave. We should just learn the rules and deal with them. In my opinion, that is a rather weak argument. It suggests that these Verilog objects are not really intended to represent integers, but rather some obscure type with bizarre behavior. I do not see how this can be justified.

To fix the problem, we need to change the assignment as follows:

  c <= $signed({1'b0, a}) + b;

We need explicitly to cast a to signed, after extending it with a sign bit. In other words, Verilog requires us to deal with the representation explicitly in order to get the abstract behavior right. This is the main point of my critique; this should not be the case. These types of bookkeeping operations can and should be conducted by a tool. In fact, tools are much better at these operations than are humans.

Why does Verilog behave in this way? Some people might tell you that the reason is a backward compatibility. The argument goes as follows. Originally, Verilog did not have signed regs, and therefore did not take them into account. Some choices that were appropriate at the time caused issues later, when signed support was introduced.

Personally, I am not convinced by this analysis. Even early versions of the Verilog language had a type that could represent negative values, appropriately called integer. Therefore, the issues should have been clear from the start. In my opinion, integer arithmetic in Verilog is broken because of a flaw in the language’s design.

VHDL with signed and unsigned types

Let us now turn our attention to VHDL.

When describing integer arithmetic in synthesizable code, designers typically use the signed and unsigned types from a package called IEEE.numeric_std. With these types, the VHDL declarations for our example are as follows:

  signal a: unsigned(2 downto 0); 
  signal b: signed(3 downto 0); 
  signal c: signed(4 downto 0);

Ideally, we would like to calculate the addition by using an assignment as follows:

  c <= a + b;

However, your VHDL analyzer will give you an error message similar to the following:

  test1.vhd:24:10: no function declarations for operator "+" ghdl:
  compilation error.

So this does not even pass analysis. Basically, what this tells us is that you simply cannot add an unsigned to a signed object. To make things work we have to fix the assignment by using some manual interventions:

  c <= signed(resize(a, 5)) + b;

If you ask me, this is downright ugly. As in Verilog, we have to cast a to signed after zero-extending it. However, extending it by using a single sign bit is not enough. Instead, we have to resize a to a bit width of 5, so that the result of the addition has a bit width equal to the bit width of c.

In general, you will find that the use of the signed and unsigned types leads to excessive resizing and type casting. Some VHDL adepts may suggest that this is a natural consequence of VHDL's strong typing. As I am a big fan of strong typing, let me very clearly point out that this argument is false. There is no fundamental reason to attribute excessive resizing and type casting to strong typing. Rather, it is a symptom that indicates that the wrong types were used to begin with.

There has to be a better way. Interestingly, VHDL itself shows it. This is the subject of the next section.

VHDL with integer subtypes

The VHDL language contains the beautiful concept of the integer subtype, which is basically an integer with constraints on its minimum and maximum values. With integer subtypes, our declarations become:

  signal a: integer range 0 to 7; 
  signal b: integer range -8 to 7;
  signal c: integer range -8 to 14;

There are a few things to note here. First, these declarations express our original problem in a much clearer way than do the earlier methods based on bit widths. Second, the constraints serve two purposes: a simulator can check them at run time to assist in debugging, and a synthesis tool can use them to infer the bit width with which to represent the objects.

Most importantly, our initial simple assignment works as is:

  c <= a + b;

Now we get the result we want without resizing and type casting, while the code still fully benefits from the advantages of strong typing. Of course, a tool such as a synthesizer has no difficulty in working out the representation details for implementation. Therefore, things are exactly how we want them to be.

If this were all that there was to it, we could claim that VHDL was superior to Verilog on this matter, and we could recommend the general usage of integer subtypes. Indeed, I believe that integer subtypes are underutilized and that they should be used whenever possible. Unfortunately, there is one major obstacle that prevents them from providing a general solution.

The obstacle is that the VHDL integer type itself, which is the base type of integer subtypes, has impractically small constraints on its minimum and maximum values. Although the standard defines them as minimal constraints that an implementation might relax, for portability reasons they are hard constraints in practice. As a result, VHDL integers cannot represent bit widths beyond 32 bits.

Of course, it is not hard to understand where the 32 bit limit comes from. However, from a hardware designer's point of view, it is arbitrary and much too low. Why should a bit width that is popular for computer architectures restrict a hardware designer’s expressiveness?

In one sense, I believe the VHDL case is more frustrating than is the Verilog case. Verilog had it fundamentally wrong from the start, while VHDL had a great solution within close reach. By failing to clear the final hurdle, it left designers with a cumbersome, low-level solution that resulted in a lot of wasted energy and ugly code.

Analysis

My main criticism of the Verilog and VHDL approaches is that in order to describe arithmetic we are forced to deal explicitly with integer representation issues. Of course, it is not only the HDL language developers who are to blame. This situation would not persist without the widespread support of the designer community.

It is clear that hardware designers need a deep understanding of bit-oriented tasks, and that HDLs offer strong support for these. However, some designers prefer a bit-oriented approach, even when it is clearly suboptimal, as in the case of integer arithmetic. As a general observation, some designers still misunderstand or distrust the capabilities of synthesis tools.

Even if you agree with my analysis, you might still be skeptical. After all, merely pointing out problems with mainstream methodologies does not prove that a viable alternative solution exists. Therefore, it is time to go to the next stage. Not only do I believe that I know the solution, I believe that I have also implemented it. I am the author of MyHDL, a Python package that turns Python into an HDL. Of course, MyHDL implements integer arithmetic according to my viewpoints. We will see how it works in the next section.

Integer arithmetic in MyHDL

In MyHDL, the objects for our example are constructed as follows:

  a = Signal(intbv(0, min=0, max=8))
  b = Signal(intbv(0, min=-8, max=8))
  c = Signal(intbv(0, min=-8, max=15))

With this code, we are constructing signals of intbv objects. The intbv class implements the desirable features, so let's discuss it in detail.

For arithmetic, intbv works in exactly the same way as Python's native integer type, int. However, it has a number of additional features that make it useful for hardware design. As with VHDL integer subtypes, it is possible to constrain its values to a range. Moreover, intbv provides an indexing and slicing interface to access the bits of the underlying two's complement representation.

The crucial difference between the intbv and the VHDL integer is that there are no artificial limits on its minimum and maximum values. The reason is that Python's int is designed to model the mathematical integer, with unbound minimum and maximum values. This makes it fully intuitive to use. In contrast, integer-like types in other computer languages often reflect the underlying computer architecture and its limitations. They may be easy to understand by compilers, but not necessarily by users.

I consider the intbv to be an all-in-one hardware designer's dream type. For integer arithmetic, it can be used at a high level without the restrictions of the VHDL integer subtype. If you need bit vector features, such a indexing, slicing or defining a bit width explicitly, that is also possible with the same type.

The signal assignment in MyHDL is as follows:

  c.next = a + b

This, of course, gives the expected simulation result. Moreover, implementation-oriented MyHDL code can be converted to Verilog and VHDL automatically. The convertor will generate the required sign extensions, resizings and type castings. It therefore automates this tedious and error-prone bookkeeping task for you.

The MyHDL solution can serve as a prototype for other HDLs. In particular, the definition of VHDL's integer could be changed so that its range becomes unbound instead of implementation-defined. Elaborated designs would always use integer subtypes with a defined range, but these would now be able to represent integers with arbitrarily large values.

Conclusion

When writing synthesizable HDL code, integer arithmetic is omnipresent. However, with Verilog and VHDL, the descriptions are often complicated and confusing.

I have shown that there is a better way. The solution is based on a type that closely models the mathematical integer. By using MyHDL, designers can take advantage of it today.

Epilogue

These ints are made for countin'
and that's just what they'll do
one of these days ...

Or so I hope.