Browse Prior Art Database

Succinct and Maintainable Representation of Combinational Logic

IP.com Disclosure Number: IPCOM000248463D
Publication Date: 2016-Dec-01
Document File: 4 page(s) / 56K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method to succinctly express the behavior of an arbitrary combinational logic block such that it can be input to a logic minimizer. This representation is flexible and easily maintainable.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 33% of the total text.

Page 01 of 4

Succinct and Maintainable Representation of Combinational Logic

Disclosed is a method to succinctly express the behavior of an arbitrary combinational logic block such that it can be input to a logic minimizer. This representation is flexible and easily maintainable. The core idea is to use a hierarchical data structure to store the behavior of the circuit. A tool is used to make modifications to this data structure. The tool can then easily flatten this data structure to be input into a logic minimizer.Figure 1 illustrates a summary of this process.

Figure 1

    
Modern complex instruction set computing (CISC)architectures have instruction set architectures (ISAs) with many instructions requiring complex decode logic. Broadly speaking, combinational logic can be categorized into two groups: formulaic and non-formulaic, or random. Formulaic functions are ones which can be represented succinctly while non-formulaic functions require more explicit and verbose descriptions. An example of a formulaic combinational function is a 64-bit adder. Due to the frequency with which that particular logic function is required, a logic designer need not specify the output of such a circuit for every input scenario. When synthesized, the circuit may require many gates, but a logic designer can represent the function by simply using the + symbol. There are a handful of other commonly used functions which can be trivially extended to circuits with n-bits of input, such as arithmetic and bitwise operations and shifting.

    On the other hand, a non-formulaic combinational logic block - which may implement any arbitrary combinational behavior - is one which cannot be represented succinctly (it is

1


Page 02 of 4

impossible for all functions to be represented succinctly under the same schema). Thus, if a logic designer desires a circuit which implements a non-formulaic function, they are required to more explicitly specify the behavior of the circuit. While not the most succinct way to represent the function of the circuit (depending on the degree of randomness versus patterns, the information can be compressed to some extent), a straight-forward method of representing the function of the circuit is to simply enumerate all the meaningful input patterns and their corresponding output patterns (this enumeration need not be exhaustive if the designer does not care about the output for some input patterns). This will be referred to as a "tabulated representation". Once a non-formulaic combinational function has been expressed in this tabulated form, it can then be used as input by a logic minimizer to create a set of Boolean equations which efficiently implement the behavior of the function.

    It is important to note that while data compression algorithms may be able to compress the representation of such a function to some extent, the designer does not have an opportunity to save effort during the process of tabulating the behavior of the function. By definition,...