1
$\begingroup$

What formal mathematical models exist for digital hardware?

I am familiar with several non-formal models that are used as the basis of several hardware description language simulators and synthesizers. However, I'm not aware of any formal mathematical models, which I think would be greatly advantageous.

For an example of what I'm looking for, note that in computer science, there are several formal mathematical models of computation, such as the Lambda Calculus and the $\pi$-Calculus (http://en.wikipedia.org/wiki/Pi_calculus). There are several others that I have read about but am less familiar with.

I have found several papers talking about applying calculi to hardware description languages. For example, this one: A Calculus for Hardware Description Languages. However, most of these seem either are light on the details (like the previous example), or are attempting to provide models for specific existing hardware description languages instead of general digital hardware design.

EDIT: Here are more examples that I have found that are along the right lines, but each only model a subset of the digital hardware domain.

$\endgroup$
2
  • $\begingroup$ Does a Turing machine meet the requirements? $\endgroup$
    – hardmath
    Commented Jun 8, 2011 at 17:50
  • $\begingroup$ No, a Turing machine is a nice model of serial computation, but is just a single instance of what can be constructed with general, synchronous digital hardware. I would expect a model such as I'm looking for to be able to represent things like many independent memories, signals, processes that all communicate simultaneously on bounded discrete timesteps. This is how hardware description languages are modeled, but I as far as I can tell, they are modeled in a very informal way. $\endgroup$
    – wjl
    Commented Jun 8, 2011 at 19:20

1 Answer 1

2
$\begingroup$

You may want to take a look at Petri Nets. It is a formal modeling language for distributed systems. It supports simultaneous processes and state at the discrete time step level. Only thing it doesn't support is signals in the hardware sense of wave signals, but it does support signals in the software sense of raising an event.

$\endgroup$
1
  • $\begingroup$ Ah, I remember learning about Petri Nets back in college, but we never did anything useful with them. Thanks for the pointer, I will have to re-investigate them. (I see lots of google hits for Petri Nets modeling at least asynchronous digital hardware). $\endgroup$
    – wjl
    Commented Jun 9, 2011 at 1:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .