Designing correct recursive circuits using semantics-preserving transformations of nets

Abstract

This paper will present a method of formal synthesis to design correct recursive circuits by using semantics-preserving transformations of nets (SPTNs). Its theoretical base is an algebraic calculus of nets. The calculus of nets is a hardware-specific calculus, and the transformations are circuit transformations themselves. Thus, it is much better adapted to the synthesis domain. The start point of the method is a conceptually simple specification for the required function. This specification can be easily proved to be correct, thereby the perplexed problem of the specification validation can be avoided. The specification is described compactly and graphically by a small kernel of recursive equations, and the synthesis task is simplified to transform these recursive equations in in the kernel. Because only semantics-preserving transformations are allowed in synthesis procedures, the synthesis result is not only a hardware implementation, but also a proof of correctness. We will illustrate two ways to transform a basic sorter into a odd-even-merging sorter, one being based on local incremantal transformations and the other being based on global partitions. The results show that there are circuits of practical interest, which can derived formally by using this method.