Browse Prior Art Database

The TAU Algorithm

IP.com Disclosure Number: IPCOM000038408D
Original Publication Date: 1987-Jan-01
Included in the Prior Art Database: 2005-Jan-31

Publishing Venue

IBM

Related People

Authors:
Ditlow, GS [+details]

Abstract

VLSI design automation algorithms can take advantage of a new algorithm called TAU. The herein described tautology-testing algorithm solves Boolean equations by taking advantage of multi-valued logic notation. The algorithm has demonstrated exponential improvement on certain dataflow-type Boolean functions, but it has been experimentally established that it also works well on control logic which is less structured. A 2-bit partitioned PLA (programmable logic array) is an efficient hardware realization of Boolean functions [1]. One reason for this efficiency is that multi-valued logic uses a 3-level (DECODE, AND, OR) form as opposed to the traditional 2-level (AND, OR) form. Cascading 2-bit partitioned PLAs for most functions use less hardware than one PLA with large decoders.