Truth Tables in the Iowa Logic Specification Language

by Douglas W. Jones

Oct 29, 1998

The table preprocessor extends the Iowa Logic Specification Language to allow automatic generation of combinational logic from truth table specifications. Someday, this extension may be incorporated into the logic simulator itself, but for now, this preprocessor will have to do.

The preprocessor is written in C; it operates as a filter, copying from standard input to standard output, and making no changes except to text between the keywords table and end. Version one of this program is unforgiving about syntax errors, but appears to be otherwise functional. If an input file name is given as a command-line parameter, the table preprocessor will read from that file instead of standard input. In any case, output is always delivered to standard output.

The table preprocessor accepts truth tables of the form illustrated by the following example:

    table adder;
       a b cin | s cout
      ---------+--------
       0 0  0  | 0  0
       0 0  1  | 1  0
       0 1  0  | 1  0
       0 1  1  | 0  1
       1 0  0  | 1  0
       1 0  1  | 0  1
       1 1  0  | 0  1
       1 1  1  | 1  1
    end.
The example specifies a one bit binary adder, and the preprocessor reading this text, either standing alone or embedded in a larger circuit, will translate it to something like the following:
    circuit adder;
      { generated by table preprocessor }
      inputs a, b, cin;
      outputs s, cout;
      parts
	{ inverters for inputs (if needed) }
	IN1BAR: not;
	IN2BAR: not;
	IN3BAR: not;
	{ and gates for each table row }
	ROW2: and(3);
	ROW3: and(3);
	ROW4: and(3);
	ROW5: and(3);
	ROW6: and(3);
	ROW7: and(3);
	ROW8: and(3);
	{ or gates for each output column }
	OUT1: or(4);
	OUT2: or(4);
      wires
	{ inputs to input inverters (if needed) }
	a to IN1BAR.in;
	b to IN2BAR.in;
	cin to IN3BAR.in;
	{ the matrix wiring, arranged row by row }
	IN1BAR.out to ROW2.in(3);
	IN2BAR.out to ROW2.in(2);
	cin to ROW2.in(1);
	  ROW2.out to OUT1.in(4);
	IN1BAR.out to ROW3.in(3);
	b to ROW3.in(2);
	IN3BAR.out to ROW3.in(1);
	  ROW3.out to OUT1.in(3);
	IN1BAR.out to ROW4.in(3);
	b to ROW4.in(2);
	cin to ROW4.in(1);
	  ROW4.out to OUT2.in(4);
	a to ROW5.in(3);
	IN2BAR.out to ROW5.in(2);
	IN3BAR.out to ROW5.in(1);
	  ROW5.out to OUT1.in(2);
	a to ROW6.in(3);
	IN2BAR.out to ROW6.in(2);
	cin to ROW6.in(1);
	  ROW6.out to OUT2.in(3);
	a to ROW7.in(3);
	b to ROW7.in(2);
	IN3BAR.out to ROW7.in(1);
	  ROW7.out to OUT2.in(2);
	a to ROW8.in(3);
	b to ROW8.in(2);
	cin to ROW8.in(1);
	  ROW8.out to OUT1.in(1);
	  ROW8.out to OUT2.in(1);
	{ wires needed to connect outputs }
	OUT1.out to s;
	OUT2.out to cout;
      { end of automatically generated text }
    end.
Note that the preprocessor uses identifiers of the form OUTn, ROWn and INnBAR within the circuit that implements the gable. If the table contains identifiers that have this form in its lists of inputs and outputs, problems are likely to result! Also, note that the preprocessor obsessively generates commas and semicolons even though these are optional in the logic specification language.

The truth table preprocessor rigidly enforces the rule that the vertical bar joining the lines of the table must be aligned, and it rigidly enforces the rule that each line of the table must be indented at least as far as the margin established by the table keyword. Alignment of the actual data within the table is more flexible. Table entries are one letter each and spaces are optional. It is nice to align table entries under the identifiers for the corresponding inputs and outputs, but there are occasions where this is not appropriate so such alignment is not required.

The truth table processor does not perform any optimization! In theory, this could be done using something like an automated version of Karnaugh maps or Quine-McCluskey minimization, but for the moment, all such optimization must be done by the user! The user may input tables in reduced form, specifying don't care conditions on inputs and outputs. A don't care input is traditionally represented by an X in the truth table, while a don't care output is traditionally represented by a -. Our truth table software will accept either of these for don't-care entries on either inputs or outputs.

Note that the use of - (dash) for don't care entries causes problems when spaces are omitted between columns! In this case, what may be intended as two adjacent don't cares is coded as -- and interpreted as the start of a comment!

Note that the logic simulator does not complain if some input to a circuit is unused or if the output of some gate is unused, but the truth table processor does not generate parts that are ignored. Thus, if there are no zeros in some input column of the truth table for which all outputs are also zero, no inverter is generated to invert that input, and if all outputs given for some row are zero, no gate will be generated to compute that term.

Time Delays

By default, the logic simulator will assign default delays to each gate and wire in the system. This default may be overridden wire by wire and gate by gate. This default may be overridden for a table by specifying the table with a time parameter, as follows:

	table adder ( time );
The time parameter causes the table preprocessor to generate a parameterized subcircuit that starts as follows:
	circuit adder( time TD );
	  { generated by table preprocessor }
	  time GTD = TD * 0.2;
	  time WTD = TD * 0.1;
	  inputs
            ...
A specific time delay must be given for each instance of this subcircuit, so it is possible to create different instances with different delays:
	parts
	  fastadd: adder( 2 * ns );
	  slowadd: adder( 2 * us );
Note that the current version of the table preprocessor spreads the specified delay fairly uniformly over the gates and wires used to implement the table. There are 3 layers of gates in the table, each given a delay of GTD, and 4 layers of wires, each given a delay of WTD.

The Iowa Logic Specification language does not currently allow a user to specify default values for parameters to subcircuits. If such defaults are ever supported, it would be nice to extend the table notation so that default time delays can be specified, for example, using a notation like:

	table adder ( time = 20 * ns );

Arrays of Inputs and Outputs

ROM chips, in particular, are best described using subscrips for each wire. The following illustrates a reasonable notation:

    table coderom;
       addr(3..0) | data(5..0)
      ------------+------------
          0000    |   000x00
          0001    |   010x00
          0010    |   000x00
          0011    |   010000
          0100    |   01xx00
          0101    |   010000
          0110    |   000x00
          0111    |   000x10
          1000    |   000x00
          1001    |   010000
          1010    |   000110
          1011    |   000000
          1100    |   0000x0
          1101    |   0000x0
          1110    |   001x01
          1111    |   100x00
    end.
The inputs to this table are addr(3), addr(2), addr(1) and addr(0), and the outputs are similarly subscripted. Note that the order of the subscripts given in the table headings is significant! These specify the order of the columns in the table!

The output from the prepocessor, on seeing the above table, begins as follows:

    circuit coderom;
      { generated by table preprocessor }
      inputs addr(0 .. 3)
      outputs data(0 .. 5)
Note that the order of the subscripts on the range of an input or output connections is reversed from the table heading given for this example. Normally, the logic simulator interprets subranges with elements out of order as empty ranges, so 1..0 is an empty range. Therefore, the output of the table processor must put all ranges into canonical ascending order.