design flow

Truth Table Models for EDA Tools The guidelines here can help ASIC library modelers create a consistent truth table style for commonly used EDA tools that minimizes debugging problems and aids the automated creation or translation of the tables. by Greg Haynes

Many EDA tools use truth table formats to model ASIC library cell functionality. Some important examples are Verilog User Defined Primitives (UDPs), the VHDL Initiative toward ASIC Libraries (Vital) standard format, Mentor Graphics' Quickpart tables (for use with Quicksim II), and the Synopsys state table group. Because truth tables provide an explicit mapping from input values to output values, they may seem straightforward to construct. However, as anyone who has built an ASIC library knows, sign-off-quality truth table models can be very difficult to design. Also, there are significant differences among table formats, so the experience gained from designing one library may not be useful with a library for another EDA tool. Programs to translate from one format into another may be excessively complex if ad hoc techniques are used to derive the source tables.

A set of guidelines described here can help ASIC library modelers create a consistent truth table style for commonly used EDA tools. This style minimizes debugging problems and facilitates the automated creation or translation of the tables by simplifying the software. Also, the key features proposed can be incorporated in any new library format or standards to provide support for a uniform modeling style for truth tables.

Table 1		Base truth table (D flip-flop)
CLK	D	Preset	Clear	Qprev	Q	QB
-	-	0	1	-	0	1
R	0	0	-	-	0	1
~R	-	0	-	0	0	1
-	0	0	-	0	0	1
-	-	1	0	-	1	0
R	1	-	0	-	1	0
~R	-	-	0	1	1	0
-	1	-	0	1	1	0
-	-	-	1	-	-	1
-	-	1	-	-	1	-

Some of the variations in EDA tool formats may result from different implementations and objectives of the tools, such as whether they're used for synthesis or simulation. In other cases, such as Vital tables, the justification may be merely a desire to provide as much flexibility as possible.

Logic values

Truth table models for an ASIC library must be based on a set of values that are adequate to describe the functionality of all the cells in the library, including features such as pull-up or pull-down resistors on input ports and three-state output ports. Because we focus on tables for sequential cells, the following simplified set of values is adequate:

Symbol	Description
0	Low
1	High
R	0 -. 1
~R	Not 0 -. 1
-	Don't care

Edge specifications are meaningful only on clock ports. The "don't care" specification denotes 0, 1, or X on level-sensitive ports and R, ~R, or X on edge-sensitive inputs. On output ports, "-" indicates that the value of the output is not determined uniquely. The following portion of the truth table for a 2-to-1 multiplexer cell shows a typical use of don't cares on input ports:

Select	D0	D1	Y
0	0	-	0
1	-	0	0
-	0	0	0

A truth table is nonpessimistic if it describes all possible conditions under which the outputs of a cell have known values, including conditions where inputs are unknown. The last line of the table above, for example, specifies that if D0 and D1 are both 0, the output is known regardless of the value of the Select input. Don't cares are useful abbreviations for constructing nonpessimistic tables of reasonable size. Without this symbol, each line in the table must be duplicated three times with "-" replaced by 1, 0, and X.

Table 2	Verilog truth table symbols
Symbol	Description
0	Low
1	High
x	Unknown
?	Don't care (input)
b	0 or 1
-	No change (output)
r	0 -. 1
p	Potential rising edge
f	1 -. 0
n	Potential falling edge
*	All transitions

Some EDA tools allow additional symbols, variables, or expressions as abbreviations to make tables even more compact. For example, a D flip-flop might contain the lines shown in the table below. Qprev is used to denote the internal state of the flip-flop, which is also the previous value of the Q output port.

CLK	Data	Qprev	Q	QB
R	d	-	d	~d
~R	-	-	nc	nc

The first line uses the variable "d" to represent the value of the data input (0 or 1) and describes the Q and QB outputs in terms of this variable. The second line indicates that, when the clock input is stable or falling, the Q and QB outputs do not change ("nc"). These conventions are not universally supported and aren't used in the base format described here.

Table 3	Vital truth table symbols
Symbol	Description	Symbol	Description
'/'	0 -. 1	'^'	X -. 1
'\'	1 -. 0	'v'	X -. 0
'P'	'/' U '^'	'E'	'v' U '^'
'N'	'\' U 'v'	'A'	'r' U '^'
'r'	0 -. X	'D'	'f' U 'v'
'f'	1 -. X	'*'	'R' U 'F'
'p'	'/' U 'r'	'X'	Unknown
'n'	'\' U 'f'	'0'	Low
'R'	'^' U 'p'	'1'	High
'F'	'v' U 'n'	'B'	0 or 1
'-'	Don't care	'Z'	High impedance
'S'	Steady state

Constructing truth tables

From a Boolean equation or other logical description, you can construct a truth table by assigning all combinations of values to the inputs. For level-sensitive inputs, the values include 0, 1, and -, and for rising edge-sensitive inputs they include R, ~R, and -. For each combination, evaluate the logical description and keep a list of all input combinations that yield a known value on the output. Then reduce the resulting list of input combinations by comparing each line with every other line of the table. A less general line is one that specifies a known value rather than a don't care for an input and is deleted. For example, for the multiplexer cell table the assignments for Select, D0, and D1 that yield 0 on the output are [1, 0, 0], [0, 0, 0], and [-, 0, 0]. The first two assignments are less general than the third and so are deleted.

The result of this process is a list of assignments that yield known values on the outputs with minimal constraints on the inputs. Table 1 illustrates a minimal, nonpessimistic table constructed by this method. It is the table for a D flip-flop with asynchronous, active-high Preset and Clear, which we'll call the base table.

The first four lines yield 0 on the Q output port from the following conditions:

Clear active (1); Preset inactive (0); CLK, D, and Qprev = don't care

CLK rising, D = 0, Preset inactive, Clear and Qprev = don't care

CLK not rising, Preset inactive, Qprev = 0, Clear and D = don't care

D and Qprev = 0, Preset inactive, CLK and Clear = don't care

The next four lines of the table are the corresponding conditions yielding 1 on the Q output. In lines 9 and 10, either Preset or Clear is don't care, so one of the outputs is unspecified. All conditions not covered by a line of this table yield unknown on the outputs.

The functionality shown in the table is representative for this cell, but some details may vary depending on the implementation. For example, if Preset and Clear are both active, the two outputs may both be 0 or both be 1.

Evaluating truth tables

Each EDA tool imposes its own unique requirements on truth table formats. These formats are mostly consistent with the basic concepts described so far. The differences generally arise from features added by EDA vendors to support additional requirements and various methods they implement to make the tables more compact. Also, EDA tools employ different methods for searching tables to find the appropriate line to apply.

If a cell has multiple output ports, there may be lines with some of the outputs unspecified, such as the last two lines of Table 1. In this situation, both lines must be used to determine all output values. Most EDA tools don't have the capability of merging information from multiple lines, so redundant lines like the following may need to be included. This line shows what happens if Preset and Clear are both active, namely, that Q and QB are both 1.

CLK	D	Preset	Clear	Qprev	Q	QB
-	-	1	1	-	1	1

In this case, order is important, and lines with unspecified outputs should be placed last. The line above should be placed before the last two lines of the base table. Otherwise, the input assignment [0, 0, 1, 1, 0] would match line 9, which doesn't specify the value of Q.

Truth tables for the four representative formats listed in the beginning illustrate the differences among these EDA tools. Each of the following examples is based on the D flip-flop of the base table.

Verilog truth tables use the symbols shown in Table 2, and the Verilog truth table for the D flip-flop with asynchronous preset and clear is shown in Listing 1. The truth table includes a notify signal that's toggled by a timing violation to set the output to X in line 9. The last three lines of the table specify edges on D, Preset, and Clear that cause no change on the output.

Models based on the Vital standard use truth tables to define sequential cell functionality. Vital truth tables use the values shown in Table 3. This comprehensive set of values includes symbols to represent many sets of possible input values. However, symbols for "not rising" and "not falling" are omitted. Therefore a line such as line 3 in the base table must be expanded to the following two lines, one for CLK falling and one for CLK stable: <

CLK	D	Preset	Clear	Qprev	Q	QB
F	-	0	-	0	0	1
S	-	0	-	0	0	1

The Vital table for the D flip-flop with preset and clear is shown in Listing 2. Many of the Vital symbols representing compound values don't provide significant advantages in constructing truth tables for commonly used cells and could easily be omitted. Only a few useful symbols are missing, and the Vital truth table in Listing 2 is very close to the form of the base table.

Mentor Quicksim II truth tables represent edges with the notation "[AB]" for a signal transition from state A to state B; "!" denotes negation, and "?" denotes don't care. For sequential cells, the tables specify the values of inputs and the current value of the internal state of the register, followed by the new internal state and the values of the outputs. The truth table for the D flip-flop with Preset and Clear is shown in Listing 3. This truth table is similar to the base table. The internal state is the first column labeled "QIN," and the new value of the internal state is the second column labeled "QIN." The three lines at the end of the table must be added. The reason for including those lines isn't clear, since they specify X on the outputs, but the outputs should be X by default if the three lines aren't included.

The Synopsys state table group supports truth tables that use the following symbols:

Symbol	Description	Symbol	Description
L	Low	H	High
L/H	First L, then H	H/L	First H, then L
R	0 -. 1	~R	Not 0 -. 1
F	1 -. 0	~F	Not 1 -. 0
X	Unknown	N	No change
-	Don't care

State table groups are used in libraries for the Synopsys Design Compiler and associated tools and reflect the objectives of those tools, which are mainly used for logic synthesis and optimization rather than simulation. State table groups can be used to create Vital simulation models using the Synopsys Library Compiler, but simulation aspects of those models are secondary. Another factor is that Library Compiler requires each internal node of a sequential cell to have at least one line with an "N" (no change) specification.

The state table for the D flip-flop with Preset and Clear takes the form of Listing 4. In this table, columns 5 and 6 (labeled "IQ" and "IQB") are the current values of two internal states, and the last two columns (which are unlabeled) are the new values of the internal states. These internal states are assigned to the Q and QB outputs of the cell.

This state table does not contain some lines that are included in the base model, for example:

~R - L - : L H : L H,

- L L - : L H : L H,

These lines are in the base table to reduce pessimism, but if they're added to the Synopsys model, they prevent Library Compiler from recognizing the functionality of the cell. The reason for this problem isn't clear. A unique feature supported by Synopsys is the inclusion of the "~R" symbol, which denotes "not rising" and allows simpler tables to be constructed.

From the standpoint of a library developer, any new standard formats for EDA libraries should include truth table syntax that supports descriptions of the form shown in Table 1. Additional abbreviations for compressing tables are important only if they improve the speed of table lookup. Reliable construction of ASIC libraries depends on uniform support for the common aspects of cell functionality, especially nonpessimistic behavior of sequential cells illustrated by the examples.

References

Verilog-XL Reference Manual, Vol. 1, Cadence Design Systems, Inc., San Jose, 1991.

Vital Model Development Specification, Version 2.2b, VHDL Initiative toward ASIC Libraries, March 1994.

Mentor BOLD Browser, QuickPart Table Model Development Manual, Mentor Graphics Corp., Beaverton, Ore. 1996.

Synopsys Online Documentation, v1998-02, Library Compiler User Guide, Synopsys, Inc., Mountain View, Calif., 1998.

Greg Haynes is a senior principal CAD engineer at UTMC Microelectronic Systems in Colorado Springs where he has worked since 1993. He's responsible for creating libraries for the front-end EDA tools that UTMC uses.

To voice an opinion on this or any Integrated System Design article, please email your message to miker@isdmag.com.

integrated system design  April 1999