Combinational logic optimization techniques in sequential logic synthesis

Designing an integrated circuit with over one hundred thousand components is a significantly complicated task; impossible to handle without computing aids. Computer-aided design tools are used in all aspects of the design: logical design of functional units, physical design of gates and modules, placement and interconnect routing, logical and timing verification, and management of design data. Of these, the automatic design of the logic components, referred to as logic synthesis, was the last to come about; an indication of the inherent difficulty of this task. There was a lack of sophisticated logic optimization techniques needed to generate high quality results. This prompted research in this area and as a result there are now several commercially available design aids. Thus far, logic synthesis has largely concentrated on combinational logic. This is an incomplete view, since digital circuits are, in general, sequential in nature. This thesis attempts to overcome this limitation. It presents techniques for the optimization of sequential logic circuits. In particular, it considers extensions of known combinational logic optimization techniques that are applicable in sequential logic synthesis. The contributions are in two areas. In the first part it is shown how existing combinational logic optimization techniques can be directly applied in the expanded context of sequential logic synthesis. The presented approach maximally exploits combinational logic optimization techniques, i.e. it can potentially detect any logical relationships that exist between any two gates in the circuit, they need not be part of the same combinational logic block. In the second part, techniques for the optimization of multi-level circuits with multiple-valued inputs are presented. Logic optimization techniques used in multi-level circuits have been extended to handle multiple-valued inputs. In addition to being a significant result in its own right, this has direct application in the state assignment problem in sequential logic synthesis. In both these areas, theoretical results are presented and implementation issues and practical experiences discussed.